一、回溯算法
回溯算法要做的事情很基础，就是穷举，可以说就是暴力穷举。解决回溯问题，实际上就是对一个决策树的遍历过程。回溯，我们可以这么理解，比如我们走迷宫，沿着一条路，走到底发现是思路，就要回到原来的出发点，再次选择一条新的路劲，其实这就是回溯。
在回溯的过程中，需要注意以下几点：
（1）路径
（2）选择的列表
（3）结束条件
1️⃣全排列问题
给定一个不含重复数字的数组 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]]
方法签名： List<List<Integer>> permute(int[] nums)
代码如下：
class Solution { public static void main(String[] args) { Solution solution = new Solution(); List<List<Integer>> permute = solution.permute(new int[]{2, 4, 5, 6}); System.out.println(permute); } public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); // 定义数组的长度 int n = nums.length; // 定义一个栈用来存放数据，使用队列，集合也行 Deque<Integer> deque = new ArrayDeque<>(); // 用来保存一个数字有没有使用过 boolean[] used = new boolean[n]; backtrack(n, nums, res, 0,deque,used); return res; } public void backtrack(int n, int[] nums, List<List<Integer>> res, int first, Deque<Integer> deque, boolean[] used) { // 所有数都填完了 if (first == n) { res.add(new ArrayList<>(deque)); return; } for (int i = 0; i < n; i++) { // 已经使用过的就不管了 if(used[i]){ continue; } // 给栈中添加元素 deque.addLast(nums[i]); used[i] = true; // 继续递归填下一个数 backtrack(n, nums, res, first + 1,deque,used); // 撤销状态 deque.removeLast(); used[i] = false; } } }
2️⃣N皇后问题
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
代码如下：
public class Find8Queen { public static void main(String[] args) { Find8Queen find8Queen = new Find8Queen(); find8Queen.solveNQueens(4); } public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<>(); check(0, new int[n], res); System.out.println(res); return res; } /** * 该方法用来检测当前列放置的queen，是否能满足条件 * * @param current 当前列 * @param queens 保存满足条件的一种情况的数组 * @param res 结果 */ private void check(int current, int[] queens, List<List<String>> res) { // 已经试探到了最后一列了 if (current == queens.length) { // 生成改种情况的棋牌，每个棋盘都是一个List<String> [.Q.., ...Q, Q..., ..Q.] List<String> board = generateBoard(queens); // 将棋盘加入结果集当中 res.add(board); return; } for (int i = 0; i < queens.length; i++) { // 一个一个的放皇后去尝试， queens[current] = i; // 检查这个皇后是否满足条件，行、列、斜线都没有 // 如果满足条件，就结束了，否则回溯 if (judge(current, queens)) { check(current + 1, queens, res); } } } /** * @param n 当前列 * @param queens 当前情况的 [1,3,0.2] * @return 是否满足条件 */ private boolean judge(int n, int[] queens) { // n代表要检验的列 i代表每一列 for (int i = 0; i < n; i++) { // 同一行: 不需要判断 // 同一列：queens[i] == queens[n]，过一遍看看有没有 // 统一斜线： Math.abs(n-i) == Math.abs(queens[n] - queens[i]) if (queens[i] == queens[n] || Math.abs(n - i) == Math.abs(queens[n] - queens[i])) { return false; } } return true; } // 根据结果生成棋盘 [1,3] 第一行第一个，第二行第三个 public List<String> generateBoard(int[] queens) { List<String> board = new ArrayList<>(); for (int i = 0; i < queens.length; i++) { char[] row = new char[queens.length]; Arrays.fill(row, '.'); row[queens[i]] = 'Q'; board.add(new String(row)); } return board; } }
二、滑动窗口
给你两个字符串S和T，请在S中找到包含T中全部字母的最短子串。如果S中没有这样一个子串，则返回空，如果存在这样一个子串，则可以认为答案是唯一的
比如： 输入 “ABCDEFGHIG” T=“CGI” 应该返回 “CDEFGHI”
这个题目是可以进行暴力破解的，但是时间复杂度太高，我们需要使用一些更加优雅的解决方案：
【滑动窗口】 的思路是这个样子的：
（1）我们可以使用双指针中的左右指针技巧，初始化 left = right = 0，把索引【左闭右开）称之为一个窗口；
（2）我们可以不断的增加right指针扩大窗口[left,right）,直至窗口中的字符串满足要求；
（3）此时我们在不断的缩小left，同时，每次增加left，都要更新一轮结果；
（4）重复以上步骤，直至left到达S的尽头。
暴力破解代码如下：
public class SildingWindow { public static String minWindow(String s, String t) { // 排除一些特殊情况 if(s == null || t == null || "".equals(s) || "".equals(t) || t.length() > s.length()){ return ""; } if (s.equals(t)) return s; // 将字符串转化成字符数组方便操作 char[] charS = s.toCharArray(); char[] charT = t.toCharArray(); // 定义两个指针，空来控制范围 [left,right) int left = 0,right = 1; // 定义保存结果的变量 int offset = 0,minLen = Integer.MAX_VALUE; // 核心的迭代逻辑 while (left < charS.length){ while (right < charS.length + 1){ // 检查left和right之间的字符是否满足条件 if(check(charS,left,right,charT)){ if(minLen > right - left){ minLen = right - left; offset = left; } } right++; } left++; right = left+1; } return new String(charS,offset,minLen == Integer.MAX_VALUE ? 0: minLen ); } private static boolean check(char[] charS, int left, int right, char[] charT) { // 特殊情况 if(right - left < charT.length){ return false; } // 转化charT中的每个字符出现的次数一定小于等于charS中对应字符的次数 int[] numsS = new int[128]; int[] numsT = new int[128]; for (int i = left; i < right; i++) { numsS[charS[i]]++; if(i-left < charT.length){ numsT[charT[i-left]]++; } } for (int i = 0; i < numsT.length; i++) { if(numsS[i] < numsT[i]){ return false; } } return true; } public static void main(String[] args) { System.out.println(minWindow("a","a")); } }
滑动窗口解法代码如下：
public class SildingWindow2 { public static String minWindow(String s, String t) { // 排除一些特殊情况 if(s == null || t == null || "".equals(s) || "".equals(t) || t.length() > s.length()){ return ""; } if (s.equals(t)) return s; // 将字符串转化成字符数组方便操作 char[] charS = s.toCharArray(); char[] charT = t.toCharArray(); // 定义两个指针，空来控制范围 [left,right) int left = 0,right = 1; // 定义保存结果的变量 int offset = 0,minLen = Integer.MAX_VALUE; // // 转化charT中的每个字符出现的次数一定小于等于charS中对应字符的次数 int[] numsS = new int[128]; int[] numsT = new int[128]; char currentWord = 128; boolean flag = false; for (int i = 0; i < charT.length; i++) { numsT[charT[i]]++; } // 核心的迭代逻辑 while (left < charS.length && right <= charS.length) { while (right < charS.length + 1) { numsS[charS[right - 1]]++; if(flag && charS[right-1] != currentWord){ right++; continue; } // 检查left和right之间的字符是否满足条件 // 如果满足条件，1、记录最优解，2、右指针暂定 if (right-left >= charT.length && check(numsS, numsT)) { // 右指针如果满足条件，左指针开始走 while (left < right) { if (check(numsS, numsT)) { if (minLen > right - left) { minLen = right - left; offset = left; } numsS[charS[left]]--; currentWord = charS[left]; left++; } else { flag = true; break; } } numsS[charS[right - 1]]--; break; } right++; } } return new String(charS,offset,minLen == Integer.MAX_VALUE ? 0: minLen ); } private static boolean check(int[] numsS, int[] numsT) { for (int i = 0; i < numsT.length; i++) { if(numsS[i] < numsT[i]){ return false; } } return true; } public static void main(String[] args) { System.out.println(minWindow("DSACDFESDECDS","ECDF")); } }
性能分析 ：
时间复杂度： 最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 C，则渐进时间复杂度为：
O ( C ⋅ ∣ s ∣ + ∣ t ∣ )
空间复杂度： 这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为：
O ( C )
三、分治思想
1️⃣归并排序
归并排序是一种稳定的排序方法，它也是一种十分高效的排序，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。
归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n·logn）的时间复杂度。代价是需要额外的内存空间。
代码如下：
public class MergeSort { public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间 int []temp = new int[arr.length]; sort(arr,0,arr.length-1,temp); } // 核心的递归方法 private static void sort(int[] arr,int left,int right,int []temp){ if(left < right){ int mid = (left+right)/2; //左边归并排序，使得左子序列有序 sort(arr,left,mid,temp); //右边归并排序，使得右子序列有序 sort(arr,mid+1,right,temp); //将两个有序子数组合并操作 merge(arr,left,mid,right,temp); } } private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left; //左序列指针 int j = mid+1; //右序列指针 int t = 0;//临时数组指针 while (i<=mid && j<=right){ if(arr[i]<=arr[j]){ temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } //将左边剩余元素填充进temp中 while(i<=mid){ temp[t++] = arr[i++]; } //将右序列剩余元素填充进temp中 while(j<=right){ temp[t++] = arr[j++]; } t = 0; //将temp中的元素全部拷贝到原数组中 while(left <= right){ arr[left++] = temp[t++]; } } }
2️⃣快速排序
快速排序同样使用分治法来把一个串（list）分为两个子串（sub-lists），然后分别进行排序。具体算法描述如下：
从数组中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
public class QuickSort { public static void main(String[] args) { int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 }; quickSort(arr, 0, arr.length - 1); System.out.println("排序后:"); for (int i : arr) { System.out.println(i); } } private static void quickSort(int[] arr, int low, int high) { if (low >= high) { return; } // 找寻排序后的基准数据所处的正确索引 int index = getIndex(arr, low, high); // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序 // quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议 quickSort(arr, low, index - 1); quickSort(arr, index + 1, high); } private static int getIndex(int[] arr, int low, int high) { // 基准数据 int pivot = arr[low]; while (low < high) { // 当队尾的元素大于等于基准数据时,向前挪动high指针 while (low < high && arr[high] >= pivot) { high--; } // 如果队尾元素小于pivot了,需要将其赋值给low arr[low] = arr[high]; // 当队首元素小于等于tmp时,向前挪动low指针 while (low < high && arr[low] <= pivot) { low++; } // 当队首元素大于pivot时,需要将其赋值给high arr[high] = arr[low]; } // 跳出循环时low和high相等,此时的low或high就是pivot的正确索引位置 // 由原理部分可以很清楚的知道low位置的值并不是pivot,所以需要将pivot赋值给arr[low] arr[low] = pivot; return low; // 返回tmp的正确位置 } }
