Backtrack是DFS的一种形式，基本写法类似于Top Down DFS，但是引入状态回溯。
每次搜索一个分支，会首先记录当前节点的状态，尝试完某个分支后，把状态回溯到记录的状态，再去尝试另外的分支。
为什么要回溯状态？
如果不回溯，A分支的状态可能会被带入B分支，但他们又是独立的，所以会影响结果。
/*
给定一个仅包含数字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'] 的一个数字。
*/
public class LeetCode17 {
public static void main(String[] args) {
//todo 回溯-backtrack
System.out.println(new Solution().letterCombinations("234"));
System.out.println(new Solution2().letterCombinations("234"));
System.out.println(new Solution3().letterCombinations("234"));
System.out.println(new Solution4().letterCombinations("234"));
System.out.println(new Solution5().letterCombinations("234"));
}
/*
Backtrack是DFS的一种形式，基本写法类似于Top Down DFS，但是引入状态回溯。
每次搜索一个分支，会首先记录当前节点的状态，尝试完某个分支后，把状态回溯到记录的状态，再去尝试另外的分支。
**为什么要回溯状态？**
如果不回溯，A分支的状态可能会被带入B分支，但他们又是独立的，所以会影响结果。
*/
/*
回溯是一种通过穷举所有可能情况来找到所有解的算法。
如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
*/
static class Solution {
Map<String, String> phone = new HashMap<String, String>() {{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};
List<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits) {
//如果没有更多数字要检查
if (next_digits.length() == 0) {
//组合完成
output.add(combination);
} else {//如果还有数字要检查
//遍历映射下一个可用数字的所有字母
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
for (int i = 0; i < letters.length(); i++) {
String letter = phone.get(digit).substring(i, i + 1);
//将当前字母附加到组合并继续下一个数字
backtrack(combination + letter, next_digits.substring(1));
}
}
}
public List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
}
static class Solution2 {
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>(); //使用一个集合来存储所有的字母组合结果
if (digits == null || digits.length() == 0) return res;
//将号码字母对应关系存储进Map
Map<Character, String[]> map = new HashMap<Character, String[]>() {{ //存储为数组更好操作
put('2', new String[]{"a", "b", "c"});
put('3', new String[]{"d", "e", "f"});
put('4', new String[]{"g", "h", "i"});
put('5', new String[]{"j", "k", "l"});
put('6', new String[]{"m", "n", "o"});
put('7', new String[]{"p", "q", "r", "s"});
put('8', new String[]{"t", "u", "v"});
put('9', new String[]{"w", "x", "y", "z"});
}};
//定义一个队列来存储所有的组合结果
Queue<String> queue = new LinkedList<>();
//遍历Digits，取到对应号码对应的字母数组
for (int i = 0; i < digits.length(); i++) {
queue_letterCombinations(queue, map.get(digits.charAt(i)));
}
//要求返回List
res.addAll(queue);
return res;
}
private Queue<String> queue_letterCombinations(Queue<String> queue, String[] letters) {
//Queue<String> queue = new LinkedList<String>();
//初始定义的queue一定是空的，所以这时候把第一个号码的字母放入队列
if (queue.size() == 0) {
queue.addAll(Arrays.asList(letters));
} else {
//对于后面到来字母，把queue出队列然后拼接以后进入队列
int queueLength = queue.size(); //记录本次需要进行出列组合的元素数量
for (int i = 0; i < queueLength; i++) {
String s = queue.poll(); //队列头元素出队列
for (String letter : letters) {
queue.add(s + letter); //将出来的队列元素和电话号码对应的字母依次进行拼接并添加进队列
}
}
}
return queue;
}
}
/*
我们可以利用队列的先进先出特点，再配合循环完成题目要求。
比如，我们先将对应的字符 a,b,c依次放入队列中
之后再从队列中拿出第一个元素a，跟3对应的字符d,e,f挨个拼接
*/
static class Solution3 {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return new ArrayList<String>();
}
//一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
//这里也可以用map，用数组可以更节省点内存
//前两个只是占位
String[] letter_map = {
"#", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
List<String> res = new ArrayList<>();
//先往队列中加入一个空字符
res.add("");
for (int i = 0; i < digits.length(); i++) {
//由当前遍历到的字符，取字典表中查找对应的字符串
String letters = letter_map[digits.charAt(i) - '0'];
int size = res.size();
//计算出队列长度后，将队列中的每个元素挨个拿出来
for (int j = 0; j < size; j++) {
//每次都从队列中拿出第一个元素
String tmp = res.remove(0);
//然后跟"def"这样的字符串拼接，并再次放到队列中
for (int k = 0; k < letters.length(); k++) {
res.add(tmp + letters.charAt(k));
}
}
}
return res;
}
}
/*
方法一：回溯
方法1：深度优先搜索
- 关键词：所有组合
- 模式识别：搜索算法
-自顶向下的递归实现神搜
-定义子问题
-在当前递归层结合子问题结果解决原问题
*/
static class Solution4 {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);
}
}
}
}
/*
回溯-队列 按层遍历
*/
static class Solution5 {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>(); //使用一个集合来存储所有的字母组合结果
if (digits == null || digits.length() == 0) return combinations;
//将号码字母对应关系存储进Map
HashMap<Character, String[]> map = new HashMap<Character, String[]>() {{ //存储为数组更好操作
put('2', new String[]{"a", "b", "c"});
put('3', new String[]{"d", "e", "f"});
put('4', new String[]{"g", "h", "i"});
put('5', new String[]{"j", "k", "l"});
put('6', new String[]{"m", "n", "o"});
put('7', new String[]{"p", "q", "r", "s"});
put('8', new String[]{"t", "u", "v"});
put('9', new String[]{"w", "x", "y", "z"});
}};
//定义一个队列来存储所有的组合结果
Queue<String> queue = new LinkedList<>();
//遍历Digits，取到对应号码对应的字母数组
for (int i = 0; i < digits.length(); i++) {
queue_letterCombinations(queue, map.get(digits.charAt(i)));
}
//要求返回List
combinations.addAll(queue);
return combinations;
}
private Queue<String> queue_letterCombinations(Queue<String> queue, String[] letters) {
//Queue<String> queue = new LinkedList<String>();
//初始定义的queue一定是空的，所以这时候把第一个号码的字母放入队列
if (queue.size() == 0) {
queue.addAll(Arrays.asList(letters));
} else {
//对于后面到来字母，把queue出队列然后拼接以后进入队列
int queueLength = queue.size(); //记录本次需要进行出列组合的元素数量
for (int i = 0; i < queueLength; i++) {
String s = queue.poll(); //队列头元素出队列
for (String letter : letters) {
queue.add(s + letter); //将出来的队列元素和电话号码对应的字母依次进行拼接并添加进队列
}
}
}
return queue;
}
}
}
/*
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
*/
public class LeetCode46 {
//todo 回溯-backtrack
public static void main(String[] args) {
System.out.println(new Solution().permute(new int[]{1, 2, 3}));
System.out.println(new Solution2().permute(new int[]{1, 2, 3}));
}
/*
回溯
深度优先遍历+状态重置
*/
static class Solution {
public List<List<Integer>> permute(int[] nums) {
// 初始化输出列表
List<List<Integer>> res = new LinkedList<>();
// 将 nums 转换为列表，因为输出是列表的列表
ArrayList<Integer> path = new ArrayList<Integer>();
for (int num : nums)
path.add(num);
int n = nums.length;
backtrack(n, path, res, 0);
return res;
}
public void backtrack(int n, ArrayList<Integer> path, List<List<Integer>> res, int depth) {
// 如果所有整数都用完了
if (depth == n) {
//拷贝进去
res.add(new ArrayList<Integer>(path));
}
for (int i = depth; i < n; i++) {
// 维护动态数组 将第 i 个整数放在当前排列的首位
Collections.swap(path, depth, i);
// 继续递归填下一个数 使用下一个整数来完成排列
backtrack(n, path, res, depth + 1);
// 回溯
Collections.swap(path, depth, i);
}
}
}
/*
回溯
深度优先遍历+状态重置
状态：每个结点表示求解问题的不同阶段
状态变量：
1，递归到第几层 depth
2，已经选了哪些数 path
3，布尔数组 used
*/
static class Solution2 {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) return res;
//栈
Deque<Integer> path = new ArrayDeque<>();
boolean[] used = new boolean[len];
dfs(nums, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
if (depth == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
//入栈
path.addLast(nums[i]);
used[i] = true;
//继续递归
dfs(nums, depth + 1, path, used, res);
//回溯
path.removeLast();
used[i] = false;
}
}
}
}
/*
给定一个可包含重复数字的序列 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
*/
public class LeetCode47 {
//todo 回溯-backtrack 参考17、46
public static void main(String[] args) {
System.out.println(new Solution().permuteUnique(new int[]{1, 1, 2, 3}));
System.out.println(new Solution2().permuteUnique(new int[]{1, 1, 2, 3}));
}
/*
回溯
深度优先遍历+状态重置
状态：每个结点表示求解问题的不同阶段
状态变量：
1，递归到第几层 depth
2，已经选了哪些数 path
3，布尔数组 used
*/
static class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 排序（升序或者降序都可以），排序是剪枝的前提
Arrays.sort(nums);
boolean[] used = new boolean[len];
// 使用 Deque 是 Java 官方 Stack 类的建议
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, 0, used, path, res);
return res;
}
private void dfs(int[] nums, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (depth == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (used[i]) {
continue;
}
// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, depth + 1, used, path, res);
// 回溯部分的代码，和 dfs 之前的代码是对称的
used[i] = false;
path.removeLast();
}
}
}
/*
搜索回溯
*/
static class Solution2 {
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
used = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, res, 0, path);
return res;
}
public void backtrack(int[] nums, List<List<Integer>> res, int depth, List<Integer> path) {
if (depth == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, res, depth + 1, path);
used[i] = false;
path.remove(depth);
}
}
}
}
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析： 在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1: print(k)k=k/2A.1000 B.10C.11D.9解析： 按照题意每次循环K/2，直到K值小于等
1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva
我一直在尝试用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
下面是我写的一个计算斐波那契数列中的值的方法: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
为了防止在迁移到生产站点期间出现数据库事务错误，我们遵循了https://github.com/LendingHome/zero_downtime_migrations中列出的建议。(具体由https://robots.thoughtbot.com/how-to-create-postgres-indexes-concurrently-in概述)，但在特别大的表上创建索引期间，即使是索引创建的“并发”方法也会锁定表并导致该表上的任何ActiveRecord创建或更新导致各自的事务失败有PG::InFailedSqlTransaction异常。下面是我们运行Rails4.2(使用Acti
我正在开发一个类似微论坛的项目，其中一个特殊用户发布一条快速(接近推文大小)的主题消息，订阅者可以用他们自己的类似大小的消息来响应。直截了当，没有任何形式的“挖掘”或投票，只是每个主题消息的响应按时间顺序排列。但预计会有很高的流量。我们想根据它们引起的响应嗡嗡声来标记主题消息，使用0到10的等级。在谷歌上搜索了一段时间的趋势算法和开源社区应用示例，到目前为止已经收集到两个有趣的引用资料，但我还没有完全理解它们:Understandingalgorithmsformeasuringtrends，关于使用基线趋势算法比较维基百科页面浏览量的讨论，在SO上。TheBritneySpearsP
我收到错误: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
文章目录一.Dijkstra算法想解决的问题二.Dijkstra算法理论三.java代码实现一.Dijkstra算法想解决的问题解决的问题:求解单源最短路径,即各个节点到达源点的最短路径或权值考察其他所有节点到源点的最短路径和长度局限性:无法解决权值为负数的情况二.Dijkstra算法理论参数:S记录当前已经处理过的源点到最短节点U记录还未处理的节点dist[]记录各个节点到起始节点的最短权值path[]记录各个节点的上一级节点(用来联系该节点到起始节点的路径)Dijkstra算法步骤:(1）初始化:顶点集S:节点A到自已的最短路径长度为0。只包含源点，即S={A}顶点集U:包含除A外的其他顶
对于体育新闻中文文本的关键字提取，常用的算法包括TF-IDF、TextRank和LDA等。它们的基本步骤如下：1.TF-IDF算法： -将文本进行分词和词性标注处理。-统计每个词在文本中的词频（TF）。-计算每个词在整个语料库中出现的文档频率（DF）和逆文档频率（IDF）。-计算每个词的TF-IDF值，并按照值的大小进行排序，选择排名前几的词作为关键字。2.TextRank算法：-将文本进行分词和词性标注处理。-将分词结果转化成图模型，每个词语为节点，根据词语之间的共现关系建立边。-对图模型进行迭代计算，计算每个节点的PageRank值，表示该节点的重要性。-选择排名前几的节点作为关键字。3.