【LeetCode】﹝回溯法ி﹞组合、火柴拼正方形、n皇后

本是古典何须时尚 2022-11-14 10:14 158阅读 0赞

## \[LeetCode\]﹝回溯法ி﹞组合、火柴拼正方形、n皇后 ##

### 文章目录 ###

*   *  \[LeetCode\]﹝回溯法ி﹞组合、火柴拼正方形、n皇后
     *   *  组合总和Ⅱ★★
         *  火柴拼正方形★★
         *  将数组拆分成斐波那契序列★★
         *  N皇后★★★

### 组合总和Ⅱ★★ ###

[40. 组合总和 II][40. _ II]

【**题目**】  
给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

`candidates` 中的每个数字在每个组合中只能使用一次。

**说明：**

*  所有数字（包括目标数）都是正整数。
 *  解集不能包含重复的组合。

【**示例**】

输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

【**解题思路**】

class Solution {
        
        List<Integer> list;
        List<List<Integer>> res;
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            list = new ArrayList<Integer>();
            res = new ArrayList();
            Arrays.sort(candidates);
            backtrack(candidates, 0, target);
            return res;
        }
        private void backtrack(int[] candidates, int begin, int target) {
        
            if (target < 0) {
        
                return;
            }
            if (target == 0) {
        
                res.add(new ArrayList(list));
                return;
            }
            for (int i = begin; i < candidates.length; i++) {
        
                if (i != begin && candidates[i] == candidates[i - 1]) {
        
                    continue;
                }
                list.add(candidates[i]);
                backtrack(candidates, i + 1, target - candidates[i]);
                list.remove(list.size() - 1);
            }
        }
    }

--------------------

### 火柴拼正方形★★ ###

[473. 火柴拼正方形][473.]

【**题目**】还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

**注意:**

1.  给定的火柴长度和在 `0` 到 `10^9`之间。
2.  火柴数组的长度不超过15。

【**示例**】

输入: [1,1,2,2,2]
    输出: true
    解释: 能拼成一个边长为2的正方形，每边两根火柴。

【**解题思路**】

首先要判断数组元素之和是否能整除4，不能返回false，否则执行下一步，使用回溯法试探性填充。

对数组排序并且逆序遍历，可以减少回溯的次数。

class Solution {
        
        public boolean makesquare(int[] nums) {
        
            if (nums.length < 4) return false;
            int sum = 0;
            for (int num : nums) sum += num;
            if (sum % 4 != 0) return false;
            int a = sum / 4;
            Arrays.sort(nums);
            return helper(nums, nums.length - 1, new int[4], a);
        }
    
        private boolean helper(int[] nums, int k, int[] sum, int avg) {
        
            if (k == -1) {
        
                return sum[0] == avg && sum[1] == avg && sum[2] == avg;
            }
            for (int i = 0; i < 4; i++) {
        
                if (sum[i] + nums[k] > avg) continue;
                sum[i] += nums[k];
                if (helper(nums, k - 1, sum, avg)) {
        
                    return true;
                }
                sum[i] -= nums[k];
            }
            return false;
        }
    }

--------------------

### 将数组拆分成斐波那契序列★★ ###

[842. 将数组拆分成斐波那契序列][842.]

【**题目**】给定一个数字字符串 `S`，比如 `S = "123456579"`，我们可以将它分成斐波那契式的序列 `[123, 456, 579]`。

形式上，斐波那契式序列是一个非负整数列表 `F`，且满足：

`0 <= F[i] <= 2^31 - 1`，（也就是说，每个整数都符合 `32` 位有符号整数类型）；  
`F.length >= 3`；  
对于所有的`0 <= i < F.length - 2`，都有 `F[i] + F[i+1] = F[i+2]` 成立。  
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 `0` 本身。

返回从 `S` 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 `[]`。

**提示：**

1.  `1 <= S.length <= 200`
2.  字符串 `S` 中只含有数字。

【**示例**】

输入："123456579"
    输出：[123,456,579]
    ---------------------
    输入: "11235813"
    输出: [1,1,2,3,5,8,13]

【**解题思路**】

详细见官方题解[将数组拆分成斐波那契序列][Link 1]

class Solution {
        
        List<Integer> res;
        public List<Integer> splitIntoFibonacci(String S) {
        
            res = new ArrayList<Integer>();
            backtrack(S, 0, S.length(), 0, 0);
            return res;
        }
    
        public boolean backtrack(String S, int index, int length, int sum, int pre) {
        
            if (index == length) {
        
                return res.size() >= 3;
            }
            long curLong = 0;
            for (int i = index; i < length; i++) {
        
                if (i > index && S.charAt(index) == '0') {
        
                    break;
                }
                curLong = curLong * 10 + (S.charAt(i) - '0');
                if (curLong > Integer.MAX_VALUE) {
        
                    break;
                }
                int cur = (int)curLong;
                if (res.size() >= 2) {
        
                    if (cur < sum) {
        
                        continue;
                    } else if(cur > sum) {
        
                        break;
                    }
                }
                res.add(cur);
                if (backtrack(S, i + 1, length, pre + cur, cur)) {
        
                    return true;
                }else {
        
                    res.remove(res.size() - 1);
                }
            }
            return false;
        }
    }

--------------------

### N皇后★★★ ###

[51. N 皇后][51. N]

【**题目**】`n` 皇后问题 研究的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 `n` ，返回所有不同的 `n` 皇后问题 的解决方案。

每一种解法包含一个不同的 `n` 皇后问题 的棋子放置方案，该方案中 `'Q'` 和 `'.'` 分别代表了皇后和空位。

【**示例**】

输入：n = 4
    输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释：如上图所示，4 皇后问题存在两个不同的解法。

【**解题思路**】

回溯法

class Solution {
        
        int[] x;
        List<List<String>> res;
    
        public List<List<String>> solveNQueens(int n) {
        
            x = new int[n];
            Arrays.fill(x, -1);
            res = new ArrayList();
            backtrack(n);
            return res;
        }
    
        private void backtrack(int n) {
        
            int k = 0;
            while (k >= 0) {
        
                x[k]++;
                while (x[k] < n && isClash(k)) {
        
                    x[k]++;
                }
                if (x[k] != n && k == n - 1) {
        
                    res.add(getBoard(n));
                }
                if (x[k] != n && k < n - 1) {
        
                    k++;
                } else {
        
                    x[k--] = -1;
                }
            }
        }
    
        private boolean isClash(int j) {
        
            for (int i = 0; i < j; i++) {
        
                if (x[j] == x[i] || Math.abs(i - j) == Math.abs(x[i] - x[j])) {
        
                    return true;
                }
            }
            return false;
        }
    
        private ArrayList<String> getBoard(int n) {
        
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
        
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < n; j++) {
        
                    sb.append(x[i] == j ? "Q" : ".");
                }
                list.add(sb.toString());
            }
            return list;
        }
    
    }

[40. _ II]: https://leetcode-cn.com/problems/combination-sum-ii/
[473.]: https://leetcode-cn.com/problems/matchsticks-to-square/
[842.]: https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/
[Link 1]: https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/jiang-shu-zu-chai-fen-cheng-fei-bo-na-qi-ts6c/
[51. N]: https://leetcode-cn.com/problems/n-queens/