萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

分治算法

发表于 2021-03-27 | 分类于 算法学习日记 | 0 | 阅读次数 321

分治简介

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。
归并排序就是分治的一种应用。

image.png

例题分析

例题

题目:为运算表达式设计优先级(题目来自力扣241题)
题干:给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含+,-以及*。

样例1:
输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

样例2:
输入: "23-45"
输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(45))) = -34
((2
3)-(45)) = -14
((2
(3-4))5) = -10
(2
((3-4)5)) = -10
(((2
3)-4)*5) = 10

题解

import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Question241 {
	public static void main(String[] args) {
		Solution241 s = new Solution241();
		List<Integer> res = s.diffWaysToCompute("2*3-4*5");
		System.out.println(res);
	}
}


class Solution241 {
	
	// 定义一个map用来记录每次计算的结果,存储为key:String, value:List的结构
    Map<String, List<Integer>> mem = new HashMap<String, List<Integer>>();
    
    public List<Integer> diffWaysToCompute(String expression) {
        
        if (mem.containsKey(expression)) {  // 每次调用方法时,先查一下map有无记录
            return mem.get(expression);  // 如果有记录值直接返回
        }
        List<Integer> res = new ArrayList<Integer>();  // 定义一个List用来记录一个字符串的结果
        for (int i = 0; i < expression.length(); i++) {  // 遍历字符串的每个值
            char ch = expression.charAt(i);  // 去出这个字符
            if (ch == '+' || ch == '-' || ch == '*') {  // 如果是运算符
                List<Integer> leftres = diffWaysToCompute(expression.substring(0, i));    // 该运算符左侧进行递归(分治的核心操作)
                List<Integer> rightres = diffWaysToCompute(expression.substring(i + 1));  // 该运算符右侧进行递归
                // 注意:返回的是两个List的结果,其中存储的是结果,类型是Integer
                
                for (int x : leftres) {  // 二重循环遍历左右两个结果,将他们的值通过运算符ch进行运算操作
                    for (int y : rightres) {
                        if (ch == '+') {
                            res.add(x + y);
                        } else if (ch == '-') {
                            res.add(x - y);
                        } else {
                            res.add(x * y);
                        }
                    }
                }
            }
        }
        if (res.size() == 0) {  // 如果该字符串只有一个数字,就将其加入res
            res.add(Integer.parseInt(expression));
        }
        mem.put(expression, res);  // 最后记录一下本次方法执行得到的res
        return res;
    }
}
题解参考自该视频讲解

递归树状结构图

image

# 算法 # 程序设计 # 分治算法
手撕二路归并排序-Java代码
力扣23题-合并K个升序链表-分治题解分析
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持