萤火小屋

优律的知识库

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

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

分治算法

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

分治简介

分治算法的基本思想是将一个规模为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个升序链表-分治题解分析
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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