回溯——算法

延年有余 2023-03-28 原文

一、算法

1. 22. 括号生成

问题

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

示例1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtracking(n, result, 0, 0, "");
        return result;
    }
    private static void backtracking(int n, List<String> result, int left, int right, String str) {
      if(right > left) {
         return;
      }
      if(left == right && right == n) {
         result.add(str);
         return;
      }
      if(left < n) {
         backtracking(n, result, left + 1, right, str + "(");
      }
      if(right < left) {
         backtracking(n, result, left, right + 1, str + ")");
      }
   }
}

2. 77. 组合

问题

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例2：

输入：n = 1, k = 1
输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

代码

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int startIndex) {
        // 终止条件
        if(path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <= n; i++) {
            path.add(i);
            backtracking(n, k, i + 1); // 遍历 下一个 纵向 元素
            path.remove(path.size() - 1); // 遍历下一个 横向 元素(言外之意就是纵向元素已经遍历完回溯了，需要移除)
        }
    }

}

剪枝优化

搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
其中，接下来要选择的元素个数 = k - path.size()，整理得到：

搜索起点的上界 = n - (k - path.size()) + 1
所以，我们的剪枝过程就是：把 i <= n 改成 i <= n - (k - path.size()) + 1 ：

for(int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtracking(n, k, i + 1); // 遍历 下一个 纵向 元素
            path.remove(path.size() - 1); // 遍历下一个 横向 元素
        }

3. 216. 组合总和 III

问题

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例1：

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例2：

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例3：

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

2 <= k <= 9
1 <= n <= 60

代码

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1, 0);
        return result;
    }
    private void backtracking(int k, int n, int startIndex, int sum) {
        if(path.size() == k) {
            if(sum == n) {
                result.add(new ArrayList<>(path));
                return;
            }
        }
        for(int i = startIndex; i <= 9; i++) {
            sum += i;
            path.add(i);
            backtracking(k, n, i + 1, sum);
            sum -= i;
            path.remove(path.size() - 1);

        }
    }
}

剪枝优化：

if(sum > n) {
	return;
}
if(path.size() == k) {
    if(sum == n) {
        result.add(new ArrayList<>(path));
        return;
    }
}

4. 17. 电话号码的字母组合

问题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例2：

输入：digits = ""
输出：[]

示例3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

代码

class Solution {
    private final String[] letterMap = {
        "",       // 0
        "",       // 1
        "abc",    // 2
        "def",    // 3
        "ghi",    // 4
        "jkl",    // 5
        "mno",    // 6
        "pqrs",   // 7
        "tuv",    // 8
        "wxyz"    // 9
    };
    private List<String> result = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if("".equals(digits)) {
            return result;
        }
        backtracking(digits, 0, new StringBuilder());
        return result;
    }

    private void backtracking(String digits, int index, StringBuilder subString) {
        if(index == digits.length()) {
            result.add(subString.toString());
            return;
        }
        int digit = digits.charAt(index) - '0';
        String letters = letterMap[digit];
        for(int i = 0; i < letters.length(); i++) {
            subString.append(letters.charAt(i));
            backtracking(digits, index + 1, subString);
            subString.delete(subString.length() - 1, subString.length());
        }
    }
}

5. 39. 组合总和树枝剪枝或for循环剪枝

问题

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例3：

输入: candidates = [2], target = 1
输出: []

代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candiates);
        backtracking(result, new ArrayList<>(), candidates, target, 0, 0);
        return result;
    }

    private void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int startIndex, int sum) {
        if(sum > target) {
            return;
        }
        if(sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, i, sum);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

剪枝优化

/*
if(sum > target) {
    return;
}
*/

for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
    sum += candidates[i];
    path.add(candidates[i]);
    backtracking(res, path, candidates, target, i, sum);
    sum -= candidates[i];
    path.remove(path.size() - 1);
}

6. 40. 组合总和 II 排序树层去重

问题

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

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

注意：解集不能包含重复的组合。

示例1：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例2：

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

代码

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, target, res, new ArrayList<Integer>(), 0, new boolean[candidates.length], 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, List<List<Integer>> res,  List<Integer> path, int startIndex, boolean[] used, int sum) {
        if(sum > target) {
			return;
        }
        if(sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <  candidates.length; i++) {
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, res, path, i + 1, used, sum + candidates[i]);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

剪枝优化

/*
if(sum > target) {
    return;
}
*/
for(int i = startIndex; i <  candidates.length && sum + candidates[i] <= target; i++) {
    
}

另一种代码

使用 i > startIndex 巧妙设计成深度可重复数字，横向不允许重复数字

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, target, res, new ArrayList<Integer>(), 0, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, List<List<Integer>> res,  List<Integer> path, int startIndex, int sum) {
        if(sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <  candidates.length && sum + candidates[i] <= target; i++) {
            if(i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            backtracking(candidates, target, res, path, i + 1, sum + candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}

7. 131. 分割回文串判断剪枝

问题

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

代码

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtracking(res, new ArrayList<String>(), s, 0);
        return res;
    }

    private void backtracking(List<List<String>> res, List<String> path, String s, int startIndex) {
        if(startIndex == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i < s.length(); i++) {       
            if(isPartition(s, startIndex, i)) {
                String substring = s.substring(startIndex, i + 1);
                path.add(substring);
            } else {
                continue;
            }
            backtracking(res, path, s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPartition(String s, int start, int end) {
        for(int i = start,j = end; i < j; i++, j--) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

}

8. 93. 复原 IP 地址 for循环和判断剪枝

问题

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例2：

输入：s = "0000"
输出：["0.0.0.0"]

示例3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

代码

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        backtracking(res, new StringBuilder(), s, 0, 0);
        return res;
    }

    private void backtracking(List<String> res, StringBuilder substring, String s, int startIndex, int pointCount) {
        if(startIndex == s.length() && pointCount == 4) {
            String withPointString = substring.toString();
            res.add(withPointString.substring(0, withPointString.length() - 1));
            return;
        }
        // 直接 在 for 循环  剪枝 长度 大于 3 或者 点数 大于等于 4 位的（等于4 位 已经在 前面 判断了）
        for(int i = startIndex; i < s.length() && pointCount < 4 && i - startIndex < 3; i++) {
            if((i > startIndex && s.charAt(startIndex) == '0')) {
                continue;
            }

            String str = s.substring(startIndex, i + 1);
            if(Integer.parseInt(str) >= 0 && Integer.parseInt(str) <= 255) {
                substring.append(str).append(".");
            } else {
                continue;
            }
            backtracking(res, substring, s, i + 1, pointCount + 1);
            substring.deleteCharAt(substring.lastIndexOf("."));
            substring.delete(substring.lastIndexOf(".") + 1, substring.length());
        }
    }

}

9. 78. 子集不剪枝

问题

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }

    private void backtracking(List<List<Integer>> res, List<Integer> path ,int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        if(startIndex == nums.length) {
            return;
        }
        for(int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(res, path, nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

模板

result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
if (startIndex >= nums.size()) { // 终止条件可以不加
    return;
}

10. 90. 子集 II 排序树层去重

问题

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例2：

输入：nums = [0]
输出：[[],[0]]

提示

1 <= nums.length <= 10
-10 <= nums[i] <= 10

代码

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }

    private void backtracking(List<List<Integer>> res, List<Integer> path, int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        if(startIndex == nums.length) {
            return;
        }
        for(int i = startIndex; i < nums.length; i++) {
            // 去重 条件 只对 广度 有效，也就是 对不同 子集去重
            if(i > startIndex && nums[i] == nums[i - 1]) {
                continue;   
            }
            path.add(nums[i]);
            backtracking(res, path, nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

11. 491. 递增子序列非排序树层去重

问题

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示

1 <= nums.length <= 15
-100 <= nums[i] <= 100

代码

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }

    private void backtracking(List<List<Integer>> res, List<Integer> path, int[] nums, int startIndex) {
         if (path.size() > 1) {
            res.add(new ArrayList<>(path));
            // 注意这里不要加return，要取树上所有的节点
        }
        // 生命周期 存活在 递归函数中，所以对 同一层有效
        Set<Integer> uset = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++) {
            // 当 path 有值 时，判断 当前 i 所在下标的 值 是否 小于 path 有序列表最后 一个元素 或者 同一层出现 重复元素
            if(path.size() > 0 && nums[i] < path.get(path.size() - 1) || !uset.add(nums[i])) {
                continue;
            }
            //uset.add(nums[i]);
            path.add(nums[i]);
            backtracking(res, path, nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

12. 46. 全排列树枝去重

问题

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return res;
    }
    
    private void backtracking(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] used) {
        // 全排列，每个元素只能用一次并且全部要用到
        if(path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            // 递归（纵向遍历）不能出现重复，一个元素只能用一次
            if(used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(res, path, nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

13. 47. 全排列 II 树枝和树层去重

问题

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtracking(res, new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return res;
    }

    private void backtracking(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        Set<Integer> uset = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            // 纵向 遍历 同一个下标元素 重复，跳过
            // 否则 横向 遍历 到 重复元素(不同下标)，跳过
            if(used[i] || !uset.add(nums[i])) 
                continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(res, path, nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

二、结束语

评论区可留言，可私信，可互相交流学习，共同进步，欢迎各位给出意见或评价，本人致力于做到优质文章，希望能有幸拜读各位的建议！
—— 与 51cto 同步：https://blog.51cto.com/fyphome
—— 与 csdn 同步：https://blog.csdn.net/F15217283411
—— 转发于个人博客对应回溯题型
—— GitHub 专栏：Fyupeng

专注品质，热爱生活。
交流技术，寻求同志。
—— 延年有余 QQ：1160886967

mdash 回溯 code lt path 算法与数据结构

有关回溯——算法的更多相关文章

区块链之加解密算法&数字证书 - 2
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
100个python算法超详细讲解：画直线 - 2
1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva
ruby - 在 Ruby 中实现 Luhn 算法 - 2
我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s
Ruby 斐波那契算法 - 2
下面是我写的一个计算斐波那契数列中的值的方法:deffib(n)ifn==0return0endifn==1return1endifn>=2returnfib(n-1)+(fib(n-2))endend它工作到n=14，但在那之后我收到一条消息说程序响应时间太长(我正在使用repl.it)。有人知道为什么会这样吗？最佳答案 Naivefibonacci进行了大量的重复计算-在fib(14)fib(4)中计算了很多次。您可以将内存添加到您的算法中以使其更快:deffib(n,memo={})ifn==0||n==1returnnen
ruby-on-rails - Rails add_index 算法 : :concurrently still causes database lock up during migration - 2
为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti
ruby - 趋势算法 - 2
我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP
Ruby - 不支持的密码算法 (AES-256-GCM) - 2
我收到错误:unsupportedcipheralgorithm(AES-256-GCM)(RuntimeError)但我似乎具备所有要求:ruby版本:$ruby--versionruby2.1.2p95OpenSSL会列出gcm:$opensslenc-help2>&1|grepgcm-aes-128-ecb-aes-128-gcm-aes-128-ofb-aes-192-ecb-aes-192-gcm-aes-192-ofb-aes-256-ecb-aes-256-gcm-aes-256-ofbRuby解释器:$irb2.1.2:001>require'openssl';puts
java实现Dijkstra算法 - 2
文章目录一.Dijkstra算法想解决的问题二.Dijkstra算法理论三.java代码实现一.Dijkstra算法想解决的问题解决的问题:求解单源最短路径,即各个节点到达源点的最短路径或权值考察其他所有节点到源点的最短路径和长度局限性:无法解决权值为负数的情况二.Dijkstra算法理论参数:S记录当前已经处理过的源点到最短节点U记录还未处理的节点dist[]记录各个节点到起始节点的最短权值path[]记录各个节点的上一级节点(用来联系该节点到起始节点的路径)Dijkstra算法步骤:(1）初始化:顶点集S:节点A到自已的最短路径长度为0。只包含源点，即S={A}顶点集U:包含除A外的其他顶
对于体育新闻中文文本关键字提取有哪些关键字提取算法及其步骤 - 2
对于体育新闻中文文本的关键字提取，常用的算法包括TF-IDF、TextRank和LDA等。它们的基本步骤如下：1.TF-IDF算法： -将文本进行分词和词性标注处理。-统计每个词在文本中的词频（TF）。-计算每个词在整个语料库中出现的文档频率（DF）和逆文档频率（IDF）。-计算每个词的TF-IDF值，并按照值的大小进行排序，选择排名前几的词作为关键字。2.TextRank算法：-将文本进行分词和词性标注处理。-将分词结果转化成图模型，每个词语为节点，根据词语之间的共现关系建立边。-对图模型进行迭代计算，计算每个节点的PageRank值，表示该节点的重要性。-选择排名前几的节点作为关键字。3.
arrays - ruby 中的最佳排列计数算法 - 2
我正在尝试计算由二进制形式的1和0的P数表示的数字的数量。如果P=2，则表示的数字为0011、1100、0110、0101、1001、1010，所以计数为6。我试过:[0,0,1,1].permutation.to_a.uniq但这不是大数的最佳解决方案(P可以什么可能是最好的排列技术，或者我们是否有任何直接的数学来做到这一点？最佳答案 Numberofpermutationcanbecalculatedusingfactorial.a=[0,0,1,1](1..a.size).inject(:*)#=>4!=>24要计算重复项，

回溯——算法

一、算法

1. 22. 括号生成

问题

代码

2. 77. 组合

问题

代码

剪枝优化

3. 216. 组合总和 III

问题

代码

剪枝优化：

4. 17. 电话号码的字母组合

问题

代码

5. 39. 组合总和 树枝剪枝或for循环剪枝

问题

代码

剪枝优化

6. 40. 组合总和 II 排序树层去重

问题

代码

剪枝优化

另一种代码

7. 131. 分割回文串 判断剪枝

问题

代码

8. 93. 复原 IP 地址 for循环和判断剪枝

问题

代码

9. 78. 子集 不剪枝

问题

代码

模板

10. 90. 子集 II 排序树层去重

问题

代码

11. 491. 递增子序列 非排序树层去重

问题

代码

12. 46. 全排列 树枝去重

问题

代码

13. 47. 全排列 II 树枝和树层去重

问题

代码

二、结束语

有关回溯——算法的更多相关文章

随机推荐

5. 39. 组合总和树枝剪枝或for循环剪枝

7. 131. 分割回文串判断剪枝

9. 78. 子集不剪枝

11. 491. 递增子序列非排序树层去重

12. 46. 全排列树枝去重