本文对回溯算法，前缀和，矩阵，DFS和BFS进行一个例题整理和思路分析。

回溯算法（Backtracking）

题目：字母大小写全排列

该问题是比较典型的全排列问题。

通用解法的步骤有点类似于BFS，都是保留一个可执行的选择列表（队列），但是回溯算法需要在递归调用之前做选择，在递归调用之后撤销选择。这也是回溯问题的精髓所在，用递归剪枝的思路解决枚举方法。（剪枝就是知道问题是错的，马上退出来，不往下接着走。）

全排列问题

List<List<Integer>> res = new LinkedList<>();

List<List<Integer>> permute(int[] nums) {
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做这一层的决策选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择，来获取在所有可能的选择列表中平行的决策。
        track.removeLast();
    }
}

前缀和

题目：和可被 K 整除的子数组

思路：该题用到前缀和的思想，因为被K整除可以采用同余的思想，即利用hashmap进行判定，如果存在，则添加。

前缀和其实就是一个数学表达式： \(preSum[i] = A[0]+A[1]+...+ A[i]\\ preSum[j]-preSum[i] = A[i+1]+....+A[j]\) 前缀和用到了转化的想法，因为题目要求是连续数组，就换一种方式表示连续数组，通过前缀和表示连续数组的任意元素和加和，前缀和和差分数组是相同的，都是申请diff(n+1)和pre(n+1)的数组。

矩阵

题目：N皇后

思路：典型的回溯法，关键在矩阵元素的处理上。

矩阵最大的性质还是它的有序性，其中一条对对角线元素，在和主对角线平行的元素上，x-y=const，主对角线上的元素最小，两边对称。在次对角线上的所有元素，x+y=const，次对角线上的元素最大，之后两边对称。

位运算

题目：只出现一次的数字 II

题意：有数字只出现１次，其他的都出现３次，求只有１次那个。

普通的异或运算：1^0 = 1, 1^1 = 0，这里每一位只有两个状态，因此同一个数作用也只有两个状态。

对于位运算，可以统计每位出现的次数，然后对3取余判断是否为1，最后判定num =total«i;

题目：颠倒二进制位

位运算翻转，即得到对应位，然后转换到对称的位置，即0转到31位。

python：

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            res = res|((n>>(32-i-1))&1)<<i
        return res

图+BFS/DFS

题目：克隆图

思路：图的遍历，不涉及到路径问题，就用传统的DFS和BFS;

其中DFS需要vis的标记，dfs的函数目的是将结点copy并返回copy后的结点。

BFS需要vis的标记，没有标记过的结点copy后，将copy结点加queue，之后进行遍历。

dfs：

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}
        # 这个visited是对原图的处理进行记录，字典存储的是图中节点在深拷贝图中对应的节点，一种map关系。
        def dfs(node):
            if node == None:
                return 
            if node in visited:
                return visited[node]
            new = Node(node.val)
            visited[node] = new
            # 然后对深拷贝的节点进行修改。
            for n in node.neighbors:
                new.neighbors.append(dfs(n))
            return new
        return dfs(node)

BFS：

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}
        def bfs(node):
            if not node: return
            new = Node(node.val)
            visited[node] = new  
            queue = [node]
            while queue:
                temp = queue.pop(0)
                for n in temp.neighbors:
                    if n not in visited:
                        visited[n] = Node(n.val)
                        queue.append(n)
                    visited[temp].neighbors.append(visited[n])
            return new # 返回root节点。
        return bfs(node)

DFS/BFS/回溯

题1：Word Ladder II

思路1：首先采用回溯的方法，onechange函数来判断关联性，通过长度来剪枝，通过endword==beginword来返回。

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        ArrayList<String> temp = new ArrayList<String>();
        // ans结果，temp存储当前路径
        temp.add(beginWord);
        findLadderHelper(beginWord, endWord, wordList, temp, ans);
        return ans;
    }
    int min = Integer.MAX_VALUE;
    private void findLadderHelper(String beginWord, String endWord, List<String> wordList, ArrayList<String> temp, List<List<String>> ans){
        // 这里做了一个回溯函数，寻找可能的路径。
        if(beginWord.equals(endWord)){
            if(min > temp.size()){
                ans.clear();
                min = temp.size();
                ans.add(new ArrayList<String>(temp));
            }else if (min == temp.size()){
                ans.add(new ArrayList<String>(temp));
            }
            return;
        }
        // 剪枝
        if(temp.size() >= min){
            return;
        }

        for(int i = 0; i < wordList.size(); i++){
            String curr = wordList.get(i);
            if(temp.contains(curr)){
                continue;
            }
            if(onechange(beginWord, curr)){
                temp.add(curr);
                findLadderHelper(curr,endWord,wordList,temp,ans);
                temp.remove(temp.size()-1);
            }
        }
    }

    private boolean onechange(String beginWord, String curWord){
        int count = 0;
        for(int i = 0; i < beginWord.length(); i++){
            if(beginWord.charAt(i) != curWord.charAt(i)){
                count += 1;
            }
            if(count==2){
                return false;
            }
        }
        return count == 1; //是否只有一个不同，不可以相同，主要是与自身重合。
    }
}

思路2：回溯的方法会多出来比较多的无用路径，超时了，BFS可以直接判断最小路径。

class Solution {
   public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Set<String> distSet = new HashSet<>(wordList);
        if (!distSet.contains(endWord)) {
            return res;
        }
       
        Set<String> visited = new HashSet<>();
       	// 这个queue是关于list<String>的queue，也就是在queue中保存了路径。
        Queue<List<String>> queue= new LinkedList<>();
        List<String> list = new ArrayList<>(Arrays.asList(beginWord));
        queue.add(list);
        visited.add(beginWord);

        boolean flag = false;
        while (!queue.isEmpty() && !flag) {
            int size = queue.size();
            Set<String> subVisited = new HashSet<>();
            for (int i = 0; i < size; i++) {
                List<String> path = queue.poll();
                String word = path.get(path.size() - 1);
                List<String> neighbor = neighbors(word,distSet);
                for(String str: neighbor){
                    if (!visited.contains(str)) {
                        List<String> pathList = new ArrayList<>(path);
                        pathList.add(str);
                        if (str.equals(endWord)) {
                            flag = true;
                            res.add(pathList);
                        }
                        queue.add(pathList); 
                        subVisited.add(str);
                    }
                }
            }
            visited.addAll(subVisited);
        }
        return res;    
   } 

    private List<String> neighbors(String cur, Set<String> dict){
        List<String> res = new ArrayList<>();
        char[] chars = cur.toCharArray();
        for(int i = 0; i < chars.length; i++){
            char temp = chars[i];
            for(char ch = 'a'; ch <= 'z'; ch++){
                if(ch==temp){
                    continue;
                }
                chars[i] = ch;
                String n = new String(chars);
                if(dict.contains(n)){
                    res.add(n);
                }
            }
            chars[i] = temp;
        }
        return res;
    }
}