算法07-分治、回溯

《算法练习-文章汇总》

分治:是递归的细分类，是一种特殊或较为复杂的递归

找重复性，最近的重复性，最优的重复性
最优重复性是动态规划
一个大问题会由许多子问题组成
分解问题，组合最后每个子问题的结果

为什么是这样一种思路呢，因为程序语言只支持if else for loop recursion,变成重复性不断反复的迭代

什么地方不需要划分成子问题的:n的阶乘n(n-1)...

泛型递归模板

//1.递归终止条件  terminator
if(level > MAX_LEVEL){
process_result
return;
}
//2.处理当前层 process current logic
process(level,param);
//3.下探下一层 drill down 
recur(level:level+1,newParam);
//4.清理当前层 restore current status

分治模板
相比递归多了一步,在下探下一层和清理当前层之间增加一层，集中子结果
process and generate the final result

Java
private static int divide_conquer(Problem problem, ) {    
if (problem == NULL)//recursion terminator 
{    int res = process_last_result();   
     return res;      
}  
subProblems = split_problem(problem)//处理当前逻辑
res0 = divide_conquer(subProblems[0])//下探到下一层
res1 = divide_conquer(subProblems[1])
result = process_result(res0, res1);
return result;
}

# Python
def divide_conquer(problem, param1, param2, ...):   
# recursion terminator   
if problem is None:     print_result    return   
# prepare data   
data = prepare_data(problem)
subproblems = split_problem(problem, data)   
# conquer subproblems   
subresult1 = self.divide_conquer(subproblems[0], p1, ...)   subresult2 = self.divide_conquer(subproblems[1], p1, ...)   subresult3 = self.divide_conquer(subproblems[2], p1, ...)   …  
# process and generate the final result   
result = process_result(subresult1, subresult2, subresult3, …)    
# revert the current level states

C/C++
//C/C++
int divide_conquer(Problem *problem, int params) 
{  // recursion terminator  
if (problem == nullptr) 
{    process_result   
 return return_result;  
 }   
 // process current problem  
 subproblems = split_problem(problem, data)  
 subresult1 = divide_conquer(subproblem[0], p1)  
 subresult2 = divide_conquer(subproblem[1], p1)  
 subresult3 = divide_conquer(subproblem[2], p1)  
 ...  
 // merge  
 result = process_result(subresult1, subresult2, subresult3)  
 // revert the current level status   return 0;}
 
JavaScript
//Javascript
const divide_conquer = (problem, params) => {  
// recursion terminator  
if (problem == null) { 
   process_result    return  
 }   
 // process current problem  
subproblems = split_problem(problem, data)  
subresult1 = divide_conquer(subproblem[0], p1) 
subresult2 = divide_conquer(subproblem[1], p1)  
subresult3 = divide_conquer(subproblem[2], p1)  
...  
// merge  
result = process_result(subresult1, subresult2,subresult3) 
// revert the current level status
}

回溯

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况:

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后，宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

 private List<String> result;

    public List<String> generateParenthesis(int n) {
        result = new ArrayList<>();
        _generate(0,0,n,"");
        return result;
    }

    private void _generate(int left,int right,int n,String s){
        //递归终止条件
        if (left == n && right ==n){
            result.add(s);
            return; 
        }
        //处理当前层逻辑
        if (left < n)
            _generate(left+1, right, n, s + "(");
        if (left>right)
            _generate(left,right+1, n, s + ")");
        //下探到下一层
        //清理当前层
    }

Pow(x,n)(Facebook)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

    public double myPow(double x, int n) {
        if (n < 0){
            x = 1/x;
        }
        return fastPow(x,n);
    }
    public double fastPow(double x,int n){
        if (n == 0)
            return 1.0;
        double result = fastPow(x,n/2);
        if (n%2==0)
            return  result * result;
        else
            return  result * result * x;
    }

子集(Facebook,字节跳动,亚马逊)

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length == 0)return  ans;
        dfs(ans,nums,new ArrayList<>(),0);
        return ans;
    }
    public void dfs(List<List<Integer>> ans,int[] nums,List<Integer> list,int index){
        //terminator
        if (index == nums.length){
            ans.add(new ArrayList<>(list));
            return;
        }
        //processs current logic
        dfs(ans,nums,list,index+1);// not pick the number of the index
        list.add(nums[index]);
        //drill down
        dfs(ans,nums,list,index+1);//pick the number of the index
        //reverse current state
        list.remove(list.size() -1);
    }

多数元素(亚马逊、字节、Facebook)

哈希表法

    public int majorityElement(int[] nums) {
        Map<Integer,Integer> countMaps = new HashMap<>();
        for (int num : nums) {
       countMaps.put(num,countMaps.getOrDefault(num,0)+1);
        }
        Map.Entry<Integer,Integer> maxEntry = null;
        for (Map.Entry<Integer,Integer> en:countMaps.entrySet()) {
            if (maxEntry == null||en.getValue()>maxEntry.getValue()){
                maxEntry = en;
            }
        }
        return maxEntry.getKey();
    }

大顶堆

    public int majorityElement0(int[] nums) {
        Map<Integer,Integer> countMaps = new HashMap<>();
        for (int num : nums) {
            countMaps.put(num,countMaps.getOrDefault(num,0)+1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> priorityQueue = new PriorityQueue<>(((o1, o2) -> (o2.getValue() - o1.getValue())));//大顶堆
        for (Map.Entry<Integer,Integer> en:countMaps.entrySet()) {
            priorityQueue.add(en);
        }
        return priorityQueue.poll().getKey();
    }

大顶堆一次循环

    public int majorityElement1(int[] nums) {
        Map<Integer,Integer> countMaps = new HashMap<>();
        PriorityQueue<Map.Entry<Integer,Integer>> priorityQueue = new PriorityQueue<>(((o1, o2) -> (o2.getValue() - o1.getValue())));//大顶堆
        for (int num : nums) {
            countMaps.put(num,countMaps.getOrDefault(num,0)+1);
        }
        priorityQueue.addAll(countMaps.entrySet());
        return priorityQueue.poll().getKey();
    }

电话号码的字母组合(亚马逊)

public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0)return new ArrayList<>();
        Map<Character,String> hashMap = new HashMap<>();
        hashMap.put('2',"abc");
        hashMap.put('3',"def");
        hashMap.put('4',"ghi");
        hashMap.put('5',"jkl");
        hashMap.put('6',"mno");
        hashMap.put('7',"pqrs");
        hashMap.put('8',"tuv");
        hashMap.put('9',"wxyz");
        List<String> list = new LinkedList<>();
        dfs("",digits,0,list,hashMap);
        return list;
    }
    public void dfs(String s,
                    String digits,
                    int level,
                    List<String>list,
                    Map<Character,String>hashMap){
        //terminator
        if (level == digits.length()){
            list.add(s);
            return;
        }
        //process current logic
        String letters = hashMap.get(digits.charAt(level));
        for (int i = 0;i < letters.length();i++){
            //drill down
            dfs(s+letters.charAt(i),digits,level+1,list,hashMap);
        }
    }

N皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]

    //创建一个N行的数组，下标i对应N*N棋盘格子第i行的皇后位置
    List<List<String>> res = new ArrayList<List<String>>();
    //三个集合，分别判断某一列，左斜线(左上到右下的斜线)，右斜线(左下到右上的斜线)
    Set<Integer> columns = new HashSet<Integer>();
    Set<Integer> hypotenuse1 = new HashSet<Integer>();
    Set<Integer> hypotenuse2 = new HashSet<Integer>();
    public List<List<String>> solveNQueens(int n) {
        int[] arr = new int[n];
        dfs(n,0,arr);
        return res;
    }
    private void dfs(int n,int x,int[] arr) {
        if(x==n) {
            //如果x==n说明所有的皇后都摆放完了
            //将arr数组中保存的结果拼接起来
            List<String> tmp = new ArrayList<String>();
            for(int k=0;k<n;++k) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[arr[k]] = 'Q';
                tmp.add(new String(row));
            }
            res.add(tmp);
            return;
        }
        //遍历一行中的每一列，并检查竖线、左斜线、右斜线是否有皇后
        for(int y=0;y<n;++y) {
            if(columns.contains(y)) {
                continue;
            }
            if(hypotenuse1.contains(x-y)) {
                continue;
            }
            if(hypotenuse2.contains(x+y)) {
                continue;
            }
            //如果检查通过，设置这一行的皇后位置，并将竖线、左斜线、右斜线的值放入集合中，并继续下一行递归
            //当下一层的所有递归遍历完后，回到本轮需要将之前集合、arr数组中保存的结果都清空
            arr[x] = y;
            columns.add(y);
            hypotenuse1.add(x-y);
            hypotenuse2.add(x+y);
            dfs(n,x+1,arr);
            arr[x] = -1;
            columns.remove(y);
            hypotenuse1.remove(x-y);
            hypotenuse2.remove(x+y);
        }
    }