回溯的本质是穷举，所以不是高效的算法
回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
注意区分一个集合取组合和多个集合取组合的细节。
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
需要注意问题是有一个解还是多个解，一个解的需要返回值，一旦找到解就逐级返回，多个解的不需要返回值
因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
77、组合
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
int index = 1;
travesal(n,k,index);
return result;
}
public void travesal(int n, int k, int index){
// 终止条件，得到k个数的组合
if(temp.size() == k){
result.add(new ArrayList<>(temp));
return;
}
for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
temp.add(i);
travesal(n,k,i+1);//递归
temp.remove(temp.size() - 1);//回溯
}
}
}
216、组合总和 III
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<>();
public int sum;
public List<List<Integer>> combinationSum3(int k, int n) {
sum = 0;
find(k,1,n);
return result;
}
public void find(int k, int left, int right){
if(temp.size() == k){
if(sum == right){
result.add(new ArrayList<>(temp));
}
return;
}
for(int i = left; i <= 9 - (k - temp.size()) + 1; i++){
if(sum > right){
continue;
}
temp.add(i);
sum += i;
find(k,i+1,right);
sum -= temp.get(temp.size() - 1);
temp.remove(temp.size() - 1);
}
}
}
17、电话号码的字母组合
class Solution {
public List<String> result = new ArrayList<String>();
public StringBuffer str = new StringBuffer();
public List<String> letterCombinations(String digits) {
// 边界条件
if(digits == null || digits.length() == 0){
return result;
}
char[] digitsArr = digits.toCharArray();
// 映射关系
String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int index = 0;
letterCombinationsHelper(digitsArr, find, index);
return result;
}
public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
if(index == digitsArr.length){
result.add(new String(str));
return;
}
// 第index个数字对应的字母
String strTemp = find[digitsArr[index] - '0'];
for(int i = 0; i < strTemp.length(); i++){
str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个
letterCombinationsHelper(digitsArr,find,index+1);
str.deleteCharAt(str.length() - 1);
}
}
}
39、组合总和
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates,index,sum,target);
return result;
}
public void combinationSumHelper(int[] candidates, int index, int sum,int target){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<Integer>(temp));
}
return;
}
for(int i = index; i < candidates.length; i++){
sum += candidates[i];
temp.add(candidates[i]);
combinationSumHelper(candidates,i,sum,target);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
40、 组合总和 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates, target, index, sum);
return result;
}
public void combinationSumHelper(int[] candidates, int target, int index, int sum){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<>(temp));
}
return;
}
// 每个数字在每个组合中只能使用一次
for(int i = index; i < candidates.length; i++){
// 去重逻辑，同层剪枝，同枝可取
if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){
continue;
}
temp.add(candidates[i]);
sum += candidates[i];
combinationSumHelper(candidates, target, i + 1, sum);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
131、分割回文串
class Solution {
public List<List<String>> result = new ArrayList<List<String>>();
public List<String> temp = new ArrayList<String>();
public List<List<String>> partition(String s) {
int index = 0;
partitionHelper(s, index);
return result;
}
public void partitionHelper(String s, int index){
if(index == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = index; i < s.length(); i++){
String s1 = s.substring(index, i + 1);
if(!check(s1,0,s1.length() - 1)){
continue;//字符子串不回文的话直接跳过该次分割方案
}
temp.add(s1);
partitionHelper(s,i+1);
temp.remove(temp.size() - 1);
}
}
// 判断是否回文
public boolean check(String s1, int left, int right){
while(left < right){
if(s1.charAt(left) == s1.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}
93、复原 IP 地址
class Solution {
public List<String> result = new ArrayList<>();
public List<String> temp = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
find(0,s,s.length());
return result;
}
public void find(int index, String s, int length){
if(index == length){
if(temp.size() == 4){
StringBuffer buf = new StringBuffer();
for(int i = 0; i < 3; i++){
buf.append(temp.get(i)).append(".");
}
buf.append(temp.get(3));
result.add(new String(buf));
}
return;
}
for(int i = index; i < length; i++){
int num = Integer.parseInt(s.substring(index,i+1));
if(num > 255){
break;
}
if(s.charAt(index) == '0'){
temp.add(s.substring(index,i+1));
find(i+1,s,length);
temp.remove(temp.size() - 1);
break;
}
temp.add(s.substring(index,i+1));
find(i+1,s,length);
temp.remove(temp.size() - 1);
}
}
}
78、子集
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsets(int[] nums) {
subsetsHandler(nums, 0);
return result;
}
public void subsetsHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
temp.add(nums[i]);
subsetsHandler(nums,i+1);
temp.remove(temp.size() - 1);
}
}
}
90、子集 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsWithDupHandler(nums, 0);
return result;
}
public void subsetsWithDupHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
// 不能 包含重复的子集
if(i > 0 &&i > index && nums[i] == nums[i - 1]){
continue;
}
temp.add(nums[i]);
subsetsWithDupHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
491、递增子序列
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> findSubsequences(int[] nums) {
// 递增子序列中 至少有两个元素
findSubsequencesHandler(nums, 0);
return result;
}
public void findSubsequencesHandler(int[] nums, int index){
if(temp.size() > 1){
result.add(new ArrayList<>(temp));
}
int[] used = new int[201];
for(int i = index; i < nums.length; i++){
if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
continue;
}
used[nums[i] + 100] = 1;
temp.add(nums[i]);
findSubsequencesHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
46、全排列
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permute(int[] nums) {
used = new int[nums.length];
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
47、全排列 II
class Solution {
public List<List<Integer>> result = new ArrayList<>();
public List<Integer> temp = new ArrayList<>();
public int[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new int[nums.length];
Arrays.sort(nums);
find(nums);
return result;
}
public void find(int[] nums){
if(temp.size() == nums.length){
result.add(new ArrayList<Integer>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){
continue;
}
if(i > 0 && nums[i] == nums[i - 1] && used[i-1] != 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
find(nums);
temp.remove(temp.size()-1);
used[i] = 0;
}
}
}
332、重新安排行程
//基本参考代码随想录
class Solution {
public LinkedList<String> result;
public LinkedList<String> path = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));//字典排序
path.add("JFK");
int[] used = new int[tickets.size()];
findItineraryHanlder(tickets, used);
return result;
}
public boolean findItineraryHanlder(List<List<String>> tickets, int[] used){
if(path.size() == tickets.size() + 1){
result = new LinkedList<String>(path);
return true;
}
for(int i = 0; i < tickets.size(); i++){
if(used[i] != 1 && tickets.get(i).get(0).equals(path.getLast())){
path.add(tickets.get(i).get(1));
used[i] = 1;
if(findItineraryHanlder(tickets,used)){
return true;
}
path.removeLast();
used[i] = 0;
}
}
return false;
}
}
51、N 皇后
class Solution {
public List<List<String>> result = new ArrayList<List<String>>();
public int[][] arr;
public List<List<String>> solveNQueens(int n) {
arr = new int[n][n];
find(n,0);
return result;
}
public void find(int n, int count){
if(count == n){
List<String> temp = new ArrayList<>();
for(int i = 0; i < n; i++){
String str = "";
for(int j= 0; j < n; j++){
if(arr[i][j] == 1){
str = str + "Q";
}else{
str = str + ".";
}
}
temp.add(str);
}
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < n; i++){
if(check(i,n,count)){
arr[count][i] = 1;
find(n,count+1);
arr[count][i] = 0;
}
}
}
public boolean check(int index,int n,int count){
for(int j = count - 1; j >= 0; j--){
if(arr[j][index] == 1){
return false;
}
}
for(int j = count - 1, index1 = index - 1; j >= 0 &&index1 >= 0; j-- , index1--){
if(arr[j][index1]==1){
return false;
}
}
for(int j = count - 1, index2 = index + 1; j >= 0 && index2<n; j-- ,index2++){
if(arr[j][index2]==1){
return false;
}
}
return true;
}
}
37、解数独
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHander(board);
}
public boolean solveSudokuHander(char[][] board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
continue;
}
for(char k = '1'; k <= '9'; k++){
if(judge(board,i,j,k)){
board[i][j] = k;
if(solveSudokuHander(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public boolean judge(char[][] board, int i, int j, char k){
for(int m = 0; m < 9; m++){
if(board[i][m]==k){
return false;
}
}
for(int n = 0; n < 9; n++){
if(board[n][j]==k){
return false;
}
}
int startRow = (i/3)*3;
int startCol = (j/3)*3;
for(int m = startRow; m < startRow+3; m++){
for(int n = startCol; n < startCol+3; n++){
if(board[m][n]==k){
return false;
}
}
}
return true;
}
}
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
一、知识框架二、练习题调节一个装瓶机使其对每个瓶子的灌装量均值为μ盎司，通过观察这台装瓶机对每个瓶子的灌装量服从标准差σ＝1.0盎司的正态分布。随机抽取这台机器灌装的9个瓶子组成一个样本，并测定每个瓶子的灌装量。试确定样本均值偏离总体均值不超过0.3盎司的概率。解：设每个瓶子的灌装量为X，X为样本均值，样本容量为n。由于总体X服从正态分布，样本均值X也服从正态分布，且均值相同，标准差为所以三、简述题1什么是统计量？为什么要引进统计量？统计量中为什么不含任何未知参数？答：（1）统计量的定义：设X1，X2，…，Xn是从总体X中抽取的容量为n的一个样本，如果由此样本构造一个函数T（X1，X2，…，X
一、题目给你一个整数数组ranks和一个字符数组suit。你有5张扑克牌，第i张牌大小为ranks[i]，花色为suits[i]。下述是从好到坏你可能持有的手牌类型：“Flush”：同花，五张相同花色的扑克牌。“ThreeofaKind”：三条，有3张大小相同的扑克牌。“Pair”：对子，两张大小一样的扑克牌。“HighCard”：高牌，五张大小互不相同的扑克牌。请你返回一个字符串，表示给定的5张牌中，你能组成的最好手牌类型。注意：返回的字符串大小写需与题目描述相同。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-poker-hand/d
一.面试总结 4月20号下午进行了一场大数据视频面试，总结一下踩坑点： 1.确定面试后，第一件事要和HR确定面试方式，具体时间、地点、什么软件、岗位JD等必须信息。 这里很多人有一个思想误区，认为问的太多会给HR不好的印象；其实大可不必，如果你通过了简历筛选，你就有权力使用公司招聘的人力资源。 2.要在面试10分钟前就进入面试的环境中，以防突发事件。 3.面试最开始都会有一个自我介绍环节，这个自我介绍环节，一定要慎之又慎，最好写下来，让朋友、长辈等审核多遍。 注：我面试时，在这踩了一个坑，自我介绍的时候踩了我要面试的岗位一脚，被技术面试官抓住了这一点
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123一、🌱344.反转字符串题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。来源：力扣（LeetCode）难度：简单提示：1s[i]都是ASCII码表中的可打印字符示例1：输入：s=[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]示例2：输入：s=[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”
数据规模->时间复杂度10^8内容二维数组中的路径问题买卖股票的最佳时机lc62【剑指098】【top100】：不同路径https://leetcode.cn/problems/unique-paths/提示：1题目数据保证答案小于等于2*10^9#方案一：dfs+记忆化classSolution:defuniquePaths(self,m:int,n:int)->int:memo=[[-1]*nfor_inrange(m)]defdfs(i,j):ifi==m-1andj==n-1:return1ifi>=morj>=n:return0ifmemo[i][j]!=-1:returnmemo[
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123hash是什么，哈希表为什么叫哈希表？一、🌱454.四数相加II题目描述：给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i,j,k,l)能满足：0nums1[i]+nums2[j]+nums3[k]+nums4[l]==0来源：力扣（LeetCode）难度：中等提示：n==nums1.lengthn==nums2.lengthn==nums3.lengthn==nums4.length1-2^28示例1：输入：nums1=[1,2],nums2=[-2,-1],n
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接 我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接 目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:111. 二叉树的最小深度题解:代码实现:题目:700. 二叉搜索树中的搜索题解:代码实现:题目:701. 二叉搜索树中的插入操作题解:代码实现:题目:450. 删除二叉搜索树中的节点题解:代码实现:完结撒花：人生苦短，
👻内容专栏：《LeetCode刷题专栏》🐨本文概括：189.轮转数组🐼本文作者：花碟🐸发布时间：2023.4.12目录思想1暴力求解代码实现：思想2三次倒置代码实现： 思想3memcpy零时拷贝代码实现：189.轮转数组 点击跳转到LeetCode平台OJ页面题目：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例1：输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]