动态规划
动态规划解决的问题有
背包问题 01背包 多重背包 完全背包问题
打家劫舍
股票问题
子序列问题
动态规划的本质性解题步骤
1.dp数组的含义，以及下标的含义
//到底是定义一维的dp数组 还是二维的dp数组
求子序列 求背包 二维数组
i j都是什么意思？
dp[i][j];
2.递推公式 阅读题目，寻找关系。 //理解题目的大概意思3.dp数组初始化 //这个好难，dp数组的初始化。4.dp数组遍历顺序(关键)5.打印dp数组滚动数组
dp[i][j]=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);
//当前层是由上一层推到出来的
// 滚动数组将二维数组转为一维数组
//当前层是由上一层拷贝而来的，将上一层拷贝给当前层，把新的层覆盖到当前层
dp[j] 容量为j的背包能装的最大价值是多少？
一维dp数组
dp[j]=max(dp[j]//不妨物品i，将上一层数据拷贝下来了，dp[j-wegiht[i]+value[i]]);
//初始化dp[0]=0; 背包容量为0的时候，装的价值为0;
//遍历顺序一维数组遍历的顺序 for（）for（倒叙遍历）j=weight[i]，j>=weight[i]，j--;//保证物品只添加了一次//一维dp数组，每次重复利用的，比较讲究遍历的顺序。//
0-1背包
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mZ32HGZR-1691505556706)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230708163034444.png)]
class Solution {//思维转化，求出来的子集它的和等于数组总和的一半，那么求出总和然后再除以2，得到一半，即在这个背包里面找到价值为一半的石头，它的价值和体积是相同的。public boolean canPartition(int[] nums) {int sum= Arrays.stream(nums).sum();//给定一个非空的数组 nums,是否可以将这个数组分割成两个子集// 一个数组，里面的元素的值既是体积也是价值// 首先求和，然后求出target，target就是最大的价值，这个背包的最大价值int target=sum/2;//剪枝优化，如果是奇数，那么就直接返回了if (sum%2==1){return false;}int dp[]=new int[target+1];dp[0]=0;for (int i = 0; i < nums.length; i++) {//先遍历物品for (int j = target; j >=nums[i] ; j--) {//重后往前进行遍历，可以找到。//每个数都使用一次dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);//把上衣行复制下来的，本质没有改变。}if(dp[target] == target)return true;}return dp[target] == target;}//给一个集合，把集合分为两个集合，使得两个子集的元素和相等// 元素不能重复使用 01背包问题
}
完全背包问题
和零一背包的区别在于每个物品可以使用无数次;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-InjjRy8i-1691505556707)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230714092231195.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h8zHn92t-1691505556708)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230714092638955.png)]
先遍历物品在遍历背包，结果是相同的。
滑动窗口
//算法实现的大致思路
int left=0，right=0;//双指针
while（letf<right&&right<s.size()）window.add（s[right]）;right++;while(window needs shrink){winodw.remove（s[left]）;letf++;}
算法框架
/* 滑动窗口算法框架 */
void slidingWindow(String s) {// 用合适的数据结构记录窗口中的数据HashMap<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时，可能导致超时System.out.printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (left < right && window needs shrink) {// d 是将移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 缩小窗口left++;// 进行窗口内数据的一系列更新...}}
}
算法常用模板，直接在上面进行修改
public class 模板 {public static void main(String[] args) {}public static String minWindow(String s,String t){//s是原来的字串，t是目标字串Map<Character,Integer> need=new HashMap<>();Map<Character,Integer> window=new HashMap<>();for (char c:t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);//API getOrDefault的用法，如果存在返回对应的值，如果不存在返回-1；}int left=0,right=0; //左指针和右指针int valid=0; //有效数字int start=0,len=Integer.MAX_VALUE;while (right<s.length()){char c=s.charAt(right);right++;if (need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if (window.get(c).equals(need.get(c))){valid++; //找到满足的数字}}while(valid==need.size()){if (right-left<len){start=left;//从left开始len=right-start;}char d =s.charAt(left);left++;if (need.containsKey(d)){if (window.get(d).equals(need.get(d))){valid--;window.put(d,window.get(d)-1);}}}}return len==Integer.MAX_VALUE?"":s.substring(start,start+left);}
}
//理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。
leetcode 76题最小覆盖字串
leetcode 567 字符串的排列
leetcode 438 找到字符串中所有的字母异位词
java大数
BigInteger 和BigDecimal;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-edFGH31t-1691505556708)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230703102133493.png)]
在 java.math 包下面的。
public class 大数 {public static void main(String[] args) {BigInteger B1 =new BigInteger("123");BigInteger B2 =new BigInteger("125");System.out.println(B1.multiply(B2));System.out.println(B1.add(B2));System.out.println(B1.max(B2));System.out.println(B2.subtract(B1));System.out.println(B2.divide(B1));}
}[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qPERDjcT-1691505556709)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230703102905433.png)]
数组
二分法
二分法的原型 有序 搜索一个target 返回对应索引的值 二分最基础的框架
int binarySearch(int[] nums, int target) {int left = 0, right = ...;while(...) {int mid = left + (right - left) / 2;if (nums[mid] == target) {...} else if (nums[mid] < target) {left = ...} else if (nums[mid] > target) {right = ...}}return ...;
}
left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了letf和right太大，直接相加导致溢出的情况。二分查找的模板，以后都采用左闭右闭的思路
基础的查找int binary_search(int[] nums, int target) {int left = 0, right = nums.length - 1; while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1; } else if(nums[mid] == target) {// 直接返回return mid;}}// 直接返回return -1;
}想左搜索，这是由于 12223，如果寻找2，右三个的下标都是2，左寻找，是找到左边界那个int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 别返回，锁定左侧边界right = mid - 1;}}// 判断 target 是否存在于 nums 中if (left < 0 || left >= nums.length) {return -1;}// 判断一下 nums[left] 是不是 targetreturn nums[left] == target ? left : -1;
}
//最后判断 left 是否越界，这个很重要。//向右进行搜索
int right_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 别返回，锁定右侧边界left = mid + 1;}}// 判断 target 是否存在于 nums 中// if (left - 1 < 0 || left - 1 >= nums.length) {// return -1;// }// 由于 while 的结束条件是 right == left - 1，且现在在求右边界// 所以用 right 替代 left - 1 更好记if (right < 0 || right >= nums.length) {return -1;}return nums[right] == target ? right : -1;
}
二分模板题
leetcode 1011
在传送带上面包裹必须在days天内从一个港口运送到另一个港口，给出包裹的质量，包裹是依次运出的，给出天数，在这些天内都运出去，返回days天内将传送带上所有包裹去拿不运出去的最低能力
class Solution {public int shipWithinDays(int[] weights, int days) {//运输 涉及到赵左边的最小值或者右边的最大值问题，都可以采用二分查找来解决//二分 letf 和right是如何确定的呢？//days天运出，最多一天，最迟每天云一趟，那么最大承载量就是所有的和// 最小的承载力就是最大的包裹的质量int left=Arrays.stream(weights).max().getAsInt();int right=Arrays.stream(weights).sum(); //求得和while (left<right){//往左搜索int mid =left+(right-left)/2;if (isC(weights,days,mid)) {//搜索左边界的题目 //运的比较多了，我们要往小的进行寻找right=mid;}else{//每天云的太少了left=mid+1;}}//不断的往左进行搜索的，结束的条件是left=rightreturn right;}public static boolean isC(int weights[],int Days,int H){//如何判断呢int count=1; //记录当前的天数int leiji=0;for (int i = 0; i < weights.length; i++) {leiji+=weights[i];if (leiji>H){count++;leiji=weights[i];}if (count>Days){return false;//运载量是现实太小了根部运输不了}}return true;}
}
leetcode 875爱吃香蕉
有n堆香蕉，存在数组里面了，i下标对应的索引就是多少跟香蕉，警卫离开了，将在h小时后回来。
珂珂决定他吃香蕉的速度，一个小时吃掉k跟，如果这堆香蕉小于k跟，那么就直接吃掉，现在求h小时内吃掉所有香蕉的最小速度
//你可以一个小时内吃掉所有的香蕉，也可以旋转慢慢吃香蕉
确定边界 left是左边界，每个小时必须吃1个
right是右边界，每个小时最多全部吃完
这是第一版写的答案，没有处理好时间关系
int left=1;//不太好确定左边界int right= Arrays.stream(piles).max().getAsInt();//因为一个小时吃完，那么最快就吃一堆//向左进行搜索的while(left<right){int mid=left+(right-left)/2;if (isS(piles,h,mid)){//符合的话，是向左进行逼近的right=mid; //不断的向左进行收缩 这个速度是可以直接吃完的}else {left=mid+1;}}return left;}public static boolean isS(int []piles,int h,int speed){//如何判断是否满足呢？//每一个小时吃一推，多了就不吃了int time=1;for (int i = 0; i < piles.length; i++) {int temp=0;//这是这一推的东西time++;temp=piles[i]-speed;while (piles[i]>speed) {time++;//ear>s,ear-s第一次吃完，ear-s-s第二次吃完，//下一次就再减去temp=temp-speed;if (temp<=0){break;}}//时间边了，就返回falseif (time>h){return false;}}return true;}//正确处理时间关系
class Solution {public int minEatingSpeed(int[] piles, int h) {int right=Arrays.stream(piles).max().getAsInt();int left=1;while (left<right){int mid =left+(right-left)/2;int costTime=0;for (int pile:piles){int currentTime=pile/mid;if (mid*currentTime<pile){currentTime++;}costTime+=currentTime;}if (costTime<=h){//比给定的时间小，要继续向左搜索right=mid;}else{left=mid+1;//说明比时间大，速度要加快了}}return left;}
}
晚上看完 前缀和 和差分数组 和哈希表
明天早上看 滑动窗口和双指针
前缀和技巧 用于快速、频繁的计算一个索引区间的值之和
返回两个索引之间的值，一般方法
class NumArray {private int[] nums;public NumArray(int[] nums) {this.nums = nums;}public int sumRange(int left, int right) {int res = 0;for (int i = left; i <= right; i++) {res += nums[i];}return res;}
}
//但是这样时间复杂度会特别的高。//如何进行优化呢？
class NumArray {// 前缀和数组private int[] preSum;/* 输入一个数组，构造前缀和 */public NumArray(int[] nums) {// preSum[0] = 0，便于计算累加和preSum = new int[nums.length + 1];// 计算 nums 的累加和for (int i = 1; i < preSum.length; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];}}/* 查询闭区间 [left, right] 的累加和 */public int sumRange(int left, int right) {return preSum[right + 1] - preSum[left];}
}
//这样时间复杂度就是o1了想要计算nums[i,j]的累加和，只要计算preSum[j+1]-preSum[i]即可;
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
差分数组
应用场景是 频繁的原始数组的某个子区间的元素进行增减
比如要将区间nums[2,6]全部加1，再给nums[2,9]全部减3，最后nums是多少
如果用for循环去写的话，时间复杂度很高。
类似于前缀和数组
我们构造一个diff差分数组 diff就是nums[i]-nums[i-1]；
差分数组
leetcode 1109
右n个航班，它们分别重1-n进行编号，有一份航班表，表中第i条预定记录bookings[i]=[i,j,k] 意味着从i-j上每个航班预定了k个座位，实质上就是差分数组，对应的数组加1，我们可以构建一个差分数组哈希表
hash table 也叫做散列表
一般用来快速判断一个元素是否出现在集合里面数组本身也是一个哈希表
leetcode 242 有效的字母异位词
给定两个字符串 s t，编写一个函数判断t是否是s的字母异位词
采用哈希表
字母对应26个，创建数组，对应的下标索引转换成字母，索引对应的值就是出现的次数class Solution {public boolean isAnagram(String s, String t) {int [] record=new int[26]; //字母的长度为26.for (int i = 0; i <s.length(); i++) {record[s.charAt(i)-'a']++; //对应的下标++;}for (int i = 0; i <t.length() ; i++) {record[t.charAt(i)-'a']--;}for(int count:record){if (count!=0){return false;}}return true;}
}leetcode 349 求两个数组之间的交集
//方法一set集合class Solution {public int[] intersection(int[] nums1, int[] nums2) {Integer> set2 =new HashSet<>();for (int a:nums1){set1.add(a);}for (int b:nums2){if (set1.contains(b)){set2.add(b);}}//set2就是两个数组之间重复的元素，在将set转为数组int arr [] =new int[set2.size()];int j=0;for (int arrs:set2){arr[j++]=arrs;}return arr;}//数组常用的hash结构
数组 集合 set 映射（散列表）map;
双指针算法
得到单链表的倒数第k个节点7.4今天需要学习的内容时
滑动窗口 14届蓝桥杯省赛的真题 百度之星真题 两个小时用来看vue和element。
滑动窗口
就是 维护一个窗口，不断滑动，然后更新答案，时间复杂度是ON，比字符串算法要高效很多。 困难点 如何向窗口中添加新元素，如何缩小窗口
letf=0，right=0;
while（）
window.add（）while（window need shrink){window.remove();left++;}
//滑动窗口
//列题一 一个字符串 s和t，返回s中股改t所有字符的最小字串，如果s中不存在覆盖所有字符额字串，则返回空字符"";
滑动窗口就算结束了螺旋矩阵 54；
晚上需要回看的题目 leetcode209
链表
链表就是右节点组成的
虚拟头节点，可以避免处理空指针的情况，降低代码的复杂度leetcode21 合并两个链表
leetcode22 和21题刚好相反，是分开一个链表
单链表的倒数第k给节点
//找到链表倒数第k个节点
链表有n个节点，倒数第k个节点就是n-k+1 个节点
但是现在不知道有多少个节点，如果先遍历一遍得到n的值，在遍历链表得到第n-k+1的值，相当于遍历的两次先让p1走k步，还剩n-k步，再让一个p2指向head，p1和p2同时向前移动，p1走到链表的结尾空指针的时候前进了n-k步
p2也从head开始前进了n-k步，停留在n-k+1的节点上。刚好倒数第k个节点
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy=new ListNode(-1);dummy.next=head;ListNode x =find(dummy,n+1);//删除倒数第k个节点，需要找到倒数第k+1个节点，// 让倒数k+1节点指向倒数k-1，相当于删除了倒数第k个节点x.next=x.next.next; //删除中间的节点return dummy.next;}public static ListNode find(ListNode head,int k){//找到倒数第k个节点ListNode p1=head;for (int i = 0; i <k ; i++) {p1=p1.next;}ListNode p2=head;while (p1!=null){p2=p2.next;p1=p1.next;}
return p2;}
}
栈和队列
栈 先进后出的 入栈 和出栈的操作
压栈叫做 push 出栈叫做pop
实列 碗的摆放 羽毛球摆放
栈是一个特殊的结构，用链表和数组都可以实现
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vnSoXBvY-1691505556709)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230705084110234.png)]
栈常用操作的代码实现
import java.util.Arrays;public class MyStack{private int[] arr;// size 记录栈中元素个数private int size;public MyStack(){// 调用无参构造方法 默认最大容量12this(12);}public MyStack(int MaxSize){this.arr = new int[MaxSize];}// 入栈public int push(int value){if(this.size == arr.length){// 栈满 ,需要扩容int[] copyArr;// 复制arr 数组并扩容一倍copyArr = Arrays.copyOf(arr,2 * arr.length);arr = copyArr;}//将元素添加到size位置this.arr[size] = value;// 元素个数加一this.size++;// 返回添加元素return value;}// 出栈public int pop(){if(isEmpty()){//没有元素//抛出运行时异常,此处也可以自定义异常throw new RuntimeException("栈中没有元素,不能出栈....");}// 获得栈顶元素int value = this.arr[size - 1];// size - 1 之后, 下一次插入时会覆盖原数据,利用覆盖替代删除this.size--;return value;}// 获取栈顶元素public int peek(){if(isEmpty()){//没有元素//抛出运行时异常,此处也可以自定义异常throw new RuntimeException("栈中没有元素,不能出栈....");}return this.arr[this.size - 1];}//获取元素个数public int getSize(){return this.size;}//判断元素是否为空public boolean isEmpty(){return this.size == 0;}
}队列 只允许在一端进行操作，在另一端进行删除操作的特殊线性表，队列具有先进先出的特点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XPsrn3HT-1691505556710)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230705084621325.png)]
生活中的列子，排队
linkedlist实现了queue队列的接口，可以通过linkedlist来实例化，
添加元素 offer 删除元素 poll;
栈一般采用链表作为底层结构基本方法的实现代码
public class MyLinkedListQueue {// 结点static class Node {public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;public Node last;public int useSize;public MyLinkedListQueue(){head = null;last = null;}public void offer(int val) {Node tmp = new Node(val);if(head == null){head = tmp;last = tmp;}else{last.next = tmp;last = tmp;}useSize++;}public int poll() {if(isEmpty()) {throw new RuntimeException("队列为空");}int val = head.val;head = head.next;if(head == null){last = null;}useSize--;return 0;}public int peek() {if(isEmpty()){throw new RuntimeException("链表为空");}return head.val;}public int size() {return useSize;}public boolean isEmpty(){return useSize==0;}leetcode 232 用栈来模拟队列
我们知道 栈是先进后出的，队列是先进先出的，可以用两个栈来模拟队列
队列 1 2 3 4 栈一[1234栈二 1234] //代码//使用两个栈来模拟队列的。class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn= new Stack<>(); //栈1stackOut=new Stack<>(); //栈2}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty()&&stackOut.isEmpty(); //两个都为空，说明队列才为0}//实现很多类都需要一个函数,直接将这个函数抽象出来。private void dumpstackIn(){//if (!stackOut.isEmpty()) return; //out里面还有值;while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}用一个队列来模拟栈
队列是先进先出的 leetcode 225
后 先
3 2 1 要来模拟栈，添加元素的时候，在末尾加一个，然后将前面的元素全部弹出来，即这个数就添加到了队首，就模拟了栈，即先进后出，即模拟了队列后进来的先出去。
class MyStack {//用队列来模拟栈Queue<Integer> queue;public MyStack() {queue=new LinkedList<>();}public void push(int x) {queue.offer(x);int size=queue.size();while (size-- > 1){queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}
leetcode 20题
// 符号匹配，用栈来。
class Solution {public boolean isValid(String s) {//判断一个括号，用栈来写。Stack<Character> stack =new Stack<>();if (s.length()%2!=0){return false;}//如果刚开始就是左括号，那么一定不对for (int i = 0; i < s.length(); i++) {char c=s.charAt(i);if (c=='('||c=='{'||c=='['){stack.push(c); //将字母放进去}else{if (c==')'||c==']'||c=='}'){if (stack.size()==0){return false; //想要出栈，一定要考虑长度是否为0，如果长度为0，直接返回false}char d=stack.peek(); //找出来d;if (d=='('&&c==')'||d=='['&&c==']'||d=='{'&&c=='}'){stack.pop();}else {return false;}}}}if (stack.isEmpty()==true){//为空return true;}else {return false;}}}
栈解决字符串问题
leetcode 1047;
class Solution {public String removeDuplicates(String s) {Stack<Character> stack =new Stack<>();for (int i = 0; i < s.length(); i++) {char c=s.charAt(i);if (stack.isEmpty() ||stack.peek()!=c){stack.push(c); //相邻之间不能相等，不相等进栈}else{stack.pop(); //如果有相等就出战}}String str="";while (!stack.isEmpty()){str=stack.pop()+str; //拼接的时候注意顺序}return str;}
}还可以使用双指针的思想class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray(); // 将输入的字符串转换为字符数组int fast = 0; // 快指针，用于遍历原始字符数组int slow = 0; // 慢指针，用于指示处理后的字符数组的尾部位置while (fast < s.length()) {ch[slow] = ch[fast]; // 用快指针的值覆盖慢指针的值if (slow > 0 && ch[slow] == ch[slow - 1]) { // 如果当前字符与前一个字符相同slow--; // 慢指针退后一步，表示将当前重复的字符删除} else {slow++; // 否则，慢指针前进一步}fast++; // 快指针前进一步}return new String(ch, 0, slow); // 根据慢指针位置创建新的字符串，表示处理后的结果，即去除重复字符的字符串}
}
优先队列
leetocde973
class Solution {public int[][] kClosest(int[][] points, int k) {PriorityQueue<long[]> queue =new PriorityQueue<>((a,b)->Long.compare(b[0],a[0]));//比较的就是距离远点的平方; //比较规则的时候，需要使用long的包装类for (int i = 0; i < points.length; i++) {int []cur=points[i]; //当前数组//队列里面存放的是数组，数组的零索引是对应的平方和，1索引是对应的下标;queue.add(new long[]{1L*cur[0]*cur[0]+cur[1]*cur[1],1l*i}); //将平方和加到队列中去， if(queue.size()>k){}//把对应的距离 和索引都加到数组中去，数组在加到队列中去//一共需要k个，找一个出队列的条件if (queue.size()>k){//寻找k个元素，如果大于了k，就需要讲小的进行返回，规则就是小的在·前面queue.poll();}}int [][]ans=new int[k][];int p=0;while (!queue.isEmpty()) {ans[p++] = points[(int)queue.poll()[1]];}return ans;}
}
U307988 数组操作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//java代码
import java.util.PriorityQueue;
import java.util.Scanner;public class Seg implements Comparable<Seg>{int len,l,r;public Seg(int len, int l, int r) {this.len = len;this.l = l;this.r = r;}//比较多个内容，长度和左节点，就需要构建一个对象，实现comparable接口，重写compareTo方法@Overridepublic int compareTo(Seg o) {if (len==o.len){return l-o.l; //返回一共数，升序排序}else {//长度不等，就看谁的长度大return o.len-len;//进行降序排序}}
}
class m {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int kase = scanner.nextInt();while (kase-- > 0) {int n = scanner.nextInt();solve(n);}}public static void solve(int n){PriorityQueue<Seg> queue =new PriorityQueue<>();queue.add(new Seg(n,1,n));int []ans=new int[n+1]; //存储结果int cnt=1;while (!queue.isEmpty()){Seg s=queue.poll();//出来的是长度最大，左端点最小的段int mid=s.l+s.r; //取中间值if (mid%2==1){mid=(mid-1)>>1;}else{mid>>=1;}ans[mid]=cnt;//中间的数改变cnt++; //还需要再++;//都添加到优先队列中去，用规则进行比较，先看长度，长度相等比位置//如果长度不等就看长度，先出来的都是靠左，或者是长度比较长的if (mid-1>=s.l){//说明左边还有0queue.add(new Seg(mid-s.l,s.l,mid-1));}if (s.r >= mid + 1) {queue.add(new Seg(s.r - mid, mid + 1, s.r));}}for (int i = 1; i <= n; i++) {System.out.print(ans[i] + " ");}System.out.println();}
}
leetcode 347 前k个高频元素
//347
class Solution {public int[] topKFrequent(int[] nums, int k) {//一个元素出现的次数，可以想到用hash表来存放这个元素，需要k个，那么就用优先队列，将哈希表里面的元素都添加到优先队列中去，设置比较的规则;Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();//定义了一个hash表·for (int num : nums) {//讲数组中的元素·全部都·加入·到·哈希表中去occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);}// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {//比较的是后面出现的次数return m[1] - n[1];}});//lamada表达式还可以再进行简化书写for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {//用entrySet来遍历集合，得到对应的键和值//将值和键添加到优先队列中去，排序是按照右低到高来排序的//当队列里面的数据都满了的时候，将队列里面最小的拿出来进行比较//如果小于，如果队列里面小于count，那么就把这个出队，再把新的添加到优先队列中去int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[]{num, count});}} else {queue.offer(new int[]{num, count});}}int[] ret = new int[k];//需要取k个出来for (int i = 0; i < k; ++i) {//取出的来是对应map集合的键ret[i] = queue.poll()[0];}return ret;}
}
二叉树
需要掌握的内容有
二叉树的遍历方式 dfs（前序 中序 后序） bfs层序;
二叉树的属性 最小深度 最大深度 平衡二叉树等二叉树的种类
满二叉树 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树 除了底层节点可能没有填满，其余每层节点数都到达了最大值，并且最下面一层节点都集中再该层最左边的若干位置；
二叉搜索树 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树
平衡二叉搜索树 AVL树，如果它是一棵空树，或者左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。存储方式 链式存储就是用的指针 顺序存储方式用的数组
顺便存储 如果父节点的数组下标是i，那么左孩子就是2*i+1,右孩子是i*2+2;
遍历两种方式
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
二叉树遍历 前序遍历 中序遍历 后序遍历
深度优先搜索 dfs 栈，一般使用递归的方式，前序 中序 后序 都是递归的方式来遍历的
也可以用迭代法来实现，用递归解决都可以用迭代来解决。广度优先搜索 bfs 一层一层的去遍历，再图论中使用的多。队列，迭代法。前序遍历 中左右
中序遍历 左中右
后续遍历 左右中遍历方式，递归方法进行遍历，// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val); // 注意这一句inorder(root.right, list);}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意这一句}
}//迭代法模拟递归，遍历二叉树
//普通方法遍历二叉树
// 采用栈来遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list =new ArrayList<>();if (root==null){return list;}Stack<TreeNode> stack =new Stack<TreeNode>();stack.push(root);while (!stack.isEmpty()){TreeNode node =stack.pop();list.add(node.val);if (node.right!=null){stack.push(node.right);}if (node.left!=null){stack.push(node.left);}//第二次遍历的时候直接弹出来的是左节点，刚刚最后一次添加的左节点}return list;}}
//可以右前序遍历快速得到后序遍历的代码。
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result); //这个找出来的是中右左，犯规来就是左右中。达到的是后序遍历。return result;}
}
//迭代中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();if (root==null){return list;}Stack<TreeNode> stack =new Stack<TreeNode>();TreeNode cur=root;while (cur!=null||!stack.isEmpty()){if (cur!=null){//如何进行遍历//从跟节点开始，这样的效率肯定不如递归遍历stack.push(cur);cur=cur.left;//不断的向左进行遍历}else{//遇到null了//弹出栈cur= stack.pop();list.add(cur.val);//左中右的顺序进行遍历cur=cur.right;}}return list;}
}
//中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}
之前不管是递归或者是迭代遍历用栈，都是dfs，现在层序遍历是bfs;
层序遍历 广度优先搜索，相当于图论里面的广度优先搜索//使用的是队列的结构
class Solution {// 用bfs实现遍历二叉树，层序遍历二叉树public List<List<Integer>> result = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {checkFun02(root);return result;}public void checkFun02(TreeNode node) {if (node == null) return;Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}result.add(itemList);}}}
刷题
leetcode 226 翻转二叉树
//bfs
class Solution {public TreeNode invertTree(TreeNode root) {//先遍历，然后遍历的时候完成交换if (root==null) return null;//用层序去遍历Queue<TreeNode> queue =new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){//将队列中的第一个取出来int len=queue.size();while (len>0){//每次要取出来TreeNode poll = queue.poll();reverse(poll);if (poll.left!=null){queue.offer(poll.left);}if (poll.right!=null){queue.offer(poll.right);}len--;}}return root;}public static void reverse(TreeNode t){ //实现翻转功能{TreeNode temp=t.left;t.left=t.right;t.right=temp;}}
}//递归方法//前序遍历 和后序遍历都可以
class Solution {public TreeNode invertTree(TreeNode root) {//得考虑一下if (root==null){return null;}//前序遍历 中左右invertTree(root.right);invertTree(root.left);swap(root);return root;}public void swap(TreeNode root){TreeNode tmp=root.left;root.left=root.right;root.right=tmp;}}101对称二叉树
class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left,root.right);//智能使用后序//不断收集左右孩子的信息 返回给上一个节点// 左右 中 }boolean compare(TreeNode left,TreeNode right){if (left==null &&right!=null){return false;}if (left!=null &&right==null){return false;}if (left == null && right == null) {return true;}if (left.val != right.val) {return false;}boolean outside=compare(left.left,right.right);//后序遍历 boolean inside=compare(left.right,right.left);//左节点的左孩子 和右节点的右孩子return outside&&inside;}
}
leetcode 二叉树的最大深度
深度和高度是不同的，高度是到叶子节点的距离，深度是到跟节点求高度是从下网上遍历，后序遍历 求深度 可以是前序遍历 中左右，往前遍历一个就+1，往下遍历再加1;//后序遍历，求得是高度
class solution {/*** 递归法*///后序遍历的过程，左右中的遍历顺序public int maxDepth(TreeNode root) {if (root == null) { return 0; }int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);//左节点和右节点孩子最大的高度 然后+1;return Math.max(leftDepth, rightDepth) + 1;}
}
//前序遍历
class Solution {//类似于回溯法/*** 递归法(求深度法)*///定义最大深度int maxnum = 0;public int maxDepth(TreeNode root) {ans(root,0);return maxnum;}//递归求解最大深度void ans(TreeNode tr,int tmp){if(tr==null) return;tmp++;maxnum = maxnum<tmp?tmp:maxnum;ans(tr.left,tmp);ans(tr.right,tmp);tmp--; //需要进行回溯}
}//思路最清晰的就是迭代法
class solution {/*** 迭代法，使用层序遍历*/public int maxDepth(TreeNode root) {if(root == null) {return 0;}Deque<TreeNode> deque = new LinkedList<>();deque.offer(root);int depth = 0;while (!deque.isEmpty()) {int size = deque.size();depth++;for (int i = 0; i < size; i++) {TreeNode node = deque.poll();if (node.left != null) {deque.offer(node.left);}if (node.right != null) {deque.offer(node.right);}}}return depth;}
二叉树最小深度
//bfs搜索
class Solution {int minDepth(TreeNode root) {if (root==null){return 0;}//dfs 广度优先搜索Queue<TreeNode> queue =new LinkedList<>();queue.offer(root); //将根节点添加进来int depth=1; //原始的深度//用队列来模拟功能while (!queue.isEmpty()){int size=queue.size();for (int i = 0; i <size ; i++) {TreeNode cur = queue.poll();if (cur.left==null&&cur.right==null){//左右都为null，说明了是根节点了return depth;}if (cur.left!=null){queue.offer(cur.left);}if (cur.right!=null){queue.offer(cur.right);}}depth++;}return depth;}
}
//递归方法
//后序求高度
class Solution {/*** 递归法，相比求MaxDepth要复杂点* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量*/public int minDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);//如果左边为空，返回右子树的高度+1;//后序遍历 ，左右中遍历的方式;if (root.left == null) {return rightDepth + 1;}if (root.right == null) {return leftDepth + 1;}// 左右结点都不为nullreturn Math.min(leftDepth, rightDepth) + 1;}
}
完全二叉树节点的数量
//bfs层序遍历
class Solution {// 迭代法public int countNodes(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int result = 0;while (!queue.isEmpty()) {int size = queue.size();while (size -- > 0) {TreeNode cur = queue.poll();result++;if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return result;}
}
//dfs
class Solution {/*** 针对完全二叉树的解法** 满二叉树的结点数为：2^depth - 1*/public int countNodes(TreeNode root) {if (root == null) return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便while (left != null) { // 求左子树深度left = left.left;leftDepth++;}while (right != null) { // 求右子树深度right = right.right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0}//如果不是局部满二叉树的化，就相当于是直接进行递归操作;return countNodes(root.left) + countNodes(root.right) + 1;}
}
//正常的递归
class Solution {// 通用递归解法//当成普通的二叉树去遍历public int countNodes(TreeNode root) {if(root == null) {return 0;}//后序遍历，左右中；return countNodes(root.left) + countNodes(root.right) + 1;}
}
leetcode112路径总和
class Solution {//用递归解决public boolean hasPathSum(TreeNode root, int targetSum) {//题目要求从根节点到叶子节点的路径，这条路径上所有节点相加等于目标和targetSum;if (root==null){return false;}//找到最后的叶子节点if (root.left==null && root.right==null){return targetSum==root.val;}return hasPathSum(root.left,targetSum-root.val) ||hasPathSum(root.right,targetSum-root.val);//和答题那一题很相似}leetcode 124 二叉树中的最大路径和
多天农民画文化赋能 乡村振兴；素材组需要剪辑一个视频,加分的一点，网站的投稿；图
图的表示方式 邻接矩阵 和临界表
DFS题目
P1294 高手去散步 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
找一个最长的方案
用邻接矩阵存储图;从一个点开始寻找，不断的找下去
定义一个二维的矩阵，存储两个点之间距离;for (int i = 1; i <= n; i++) {x = scanner.nextInt();y = scanner.nextInt();c = scanner.nextInt();Edge[x][y] = c;Edge[y][x] = c;}// dfs代码import java.util.*;
//所有的变量都是设置的全部变量class Main {static int[][] Edge;static int n, s, an, t, ans;static boolean[]b;static int x, y, c;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);t = scanner.nextInt();n = scanner.nextInt();Edge = new int[21][21];b = new boolean[t+1]; //用布尔数组存放节点for (int i = 1; i <= n; i++) {x = scanner.nextInt();y = scanner.nextInt();c = scanner.nextInt();Edge[x][y] = c;Edge[y][x] = c;}for (int i = 1; i <= t; i++) {//当前路径为tureb[i] = true;dfs(i, 0);an = Math.max(an, ans);//找了一次之后，需要访问的结果全部都归为false;Arrays.fill(b, false);}System.out.println(an);}// static void dfs(int k, int su) {
// ans = Math.max(ans, su);
// for (int i = 1; i <= t; i++) {
//
// if (Edge[k][i] > 0 && b[i]==false) {
//
// b[i] = true;
// dfs(i, su + Edge[k][i]);
// b[i] = false;
// }
// }
// }static void dfs(int k,int su){ans=Math.max(ans,su);for (int i = 0; i < t; i++) {if (Edge[k][i]>0&&b[i]==false){b[i]=true;dfs(i,su+ Edge[k][i]);b[i]=false; //撤销操作;}}}
}并查集
集合关系
自反 对称 传递 ；
并查集的基本操作，初始化init，查询find，合并unionn;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xO4TShjb-1691505556711)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230723155321947.png)]
初始化，用一个数组fa[]来存储每一个元素的父节点
查询 find，寻找i的祖先，
合并操作，将i和j进行一共合并的操作，需要找到id的祖先，在找到j的祖先，将i的祖先指向j的祖先；
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NjjZHPzr-1691505556711)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230723160241626.png)]
路径压缩，原来是一很长的链表，变为了图;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KGpuwuOS-1691505556712)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230723160544138.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uNuzyE6a-1691505556725)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230723161017940.png)]
//并查集的代码
import java.util.Scanner;public class BING {static int fa[];public static void main(String[] args) {int n ,m,x,y;Scanner scanner =new Scanner(System.in);n=scanner.nextInt();m=scanner.nextInt();fa=new int[n+1];init(n);for (int i = 1; i <=m; i++) {x=scanner.nextInt();y=scanner.nextInt();union(x,y);}int q=scanner.nextInt();for (int i = 0; i < q; i++) {if (find(scanner.nextInt())!=find(scanner.nextInt())){System.out.println("NO");}else {System.out.println("YES");}}}//路径压缩的代码static void init(int n){for (int i = 1; i <=n; i++) {fa[i]=i;}}static int find(int i){if (fa[i]==i){return i;}else{fa[i]=find(fa[i]);//将i的父节点加入进来，进行递归return fa[i];}}//通过这一段代码，将所有的节点都指向了一个父节点static void union(int i,int j){int i_fa=find(i);int j_fa=find(j);fa[i_fa]=j_fa;}
}
牛客刷题总结
数据结构就都先了解一下，不用深挖数据结构得内容，直接过来看算法题，难度可能会有点大，但是必须得坚持下去。
回溯算法
回溯算法是自上而下的
回溯算法可以解决的问题 组合问题 分割问题 子集问题 排列问题 棋盘问题 递增子序列组合问题 就是 给定两个整数n和k，返回1-n中所有可能的k个数的组合
输入 n=4，k=2; 输出 24 34 23 13 12 14;
抽象为树形的样子
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NbqGamGR-1691505556726)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711150012046.png)]
回溯的模板内容
void backtracking(参数 n k startIndex){
if（终止条件）存放结果;return;
}for（选择：本层集合中元素（树中节点孩子的数量就是集合的大小））{处理节点;backtracking(路径，选择列表); //递归回溯，撤销处理的结果；}
组合问题的代码
class Solution {List<List<Integer>> result = new ArrayList<>(); //数组LinkedList<Integer> path = new LinkedList<>(); //链表// 定义了两个集合内容public List<List<Integer>> combine(int n, int k) {backTracking(n, k, 1); //索引位置return result;}public void backTracking(int n,int k,int startIndex){//回溯算法if (path.size()==k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <=n-(k-path.size())+1 ; i++) {// k是需要这么多元素，比如需要3个。 path.size是已经添加进去的元素，k-path.size还需要添加的元素// 最后+1 这个看做实列来//这边进行剪枝优化，可以加大搜索的效率path.add(i); //将当前元素加进来backTracking(n,k,i+1);path.removeLast(); //撤销操作}}}//leetcode submit region end(Prohibit modification and deletion)组合问题|||
找出所有相加之和为n的k个数的组合，组合中只允许含有1-9的正整数，并且每种组合中不存在重复的数字
k=3 n=9 ; 和组合基本问题相同，引入一个sum变量，在回溯之前加上sum的值，回溯之后减去sum的值即可结束的条件就是path.size==k，且sum==9;
class Solution {public List<List<Integer>> result =new ArrayList<>();public LinkedList<Integer> path=new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {combine(k,n,1,0);return result;}public void combine(int k,int n,int startIndex,int sum){if (sum>n){return;}if (path.size()==k){if (sum==n) result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <=9-(k-path.size())+1; i++) {//有一剪枝优化的操作//还需要进行剪枝的操作path.add(i);sum+=i;combine(k,n,i+1,sum);//回溯操作 不仅需要将集合里面的元素去除吊，还要将sum减去i;path.removeLast();//移除最后一个sum-=i;}}
}
电话号码的字母组合
首先需要完成的是映射关系，字母和数字需要完成映射，可以用一个字符数组来解决，字符串操作可以想到的是StringBuilder
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NHkBGaXV-1691505556726)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711152057254.png)]
数是这样的，取出abc中的字母，再去def中的字母，
代码
class Solution {List<String> list =new ArrayList<>();public List<String> letterCombinations(String digits) {//需要解决的问题// 数字和字母如何进行映射//输入 1 * # 等等异常的情况if (digits==null||digits.length()==0){return list;}String [] numString={"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backTracking(digits,numString,0);return list;}StringBuilder temp =new StringBuilder();//如果这个放在里面的话，每一次回溯都会重新创建一个字符串，不太划算的。public void backTracking(String digits,String []numString,int num){//拼接字符串的if (num==digits.length()){list.add(temp.toString());return;}String str=numString[digits.charAt(num)-'0']; //找到对应的字母了//digits.charAt(num)-‘0’ 得到的是对应数组的下标，str代表数字对应的字符串for (int i = 0; i < str.length() ; i++) {temp.append(str.charAt(i));backTracking(digits,numString,num+1);temp.deleteCharAt(temp.length()-1); //删除最后一个}}
}组合总和问题
1 是 给定一个无重复的元素，candidates中的数字可以无重复的选取使用
组合问题2 是给定一个数组candidates 和一个目标书target，找出candidates中所有可以使数字和为target的组合，数字都只能使用一次。数组里面元素是可以重复的
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bgVuDLVd-1691505556727)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711152702638.png)]
先取 2 5 3 ，取2的可以继续取253， 取5的只能取53，不能再取2，如果取2了，求出来的结果会重复出现。
代码如下需要先进行排序，便于后面进行剪枝操作，如果sum+candidates[i]>target了，说明没有必要再进行递归了，直接结束即可。class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path= new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {//Arrays.sort(candidates);backTracking(path,candidates,target,0,0);return result;}public void backTracking(List<Integer>path,int []candidates,int target,int sum,int start){if (sum>target){return;}if (sum==target){result.add(new ArrayList<>(path));return; //结束了}for (int i = start; i <candidates.length; i++) {sum+=candidates[i];
// if (sum>target){
// break;//剪枝优化
// }path.add(candidates[i]);backTracking(path,candidates,target,sum,i);////组合问题，对应的 start;path.remove(path.size()-1);sum-=candidates[i];}}
}
组合总和||的思路
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YFzN61PW-1691505556727)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711153055250.png)]
需要进行树层去重，对于里面的元素是不能重复取得，使用过的元素不能重复选取，
组合问题抽象为树形结构，两个维度，一个是树枝上使用过，一个是树层上使用过。
树层上面已经取了1之后，就不能再取1了，不然就会造成重复的现象，这个叫做树层去重，用一个used[]数组来记录结果。
子集问题二 和上面组合问题一个是树枝去重 一个是树层去重
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bChxv79X-1691505556728)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711153855335.png)]
子集问题
子集问题1
子集问题，收获结果，要去每一个节点取收获，之前都是在终点进行收获结果。
nums[123]; 求子集不能出现重复的。给出的nums是不含有重复的;
class Solution {//这两个设置的是全局变量List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> path =new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {//如果startindex>=nums.size;// 此时已经到了叶子节点，需要进行return;dfs(0,nums);return result;}public void dfs(int startIndex,int [] nums){result.add (new ArrayList<>(path));if (startIndex>=nums.length){return;}//需要startIndex索引，控制位置。for (int i = startIndex; i < nums.length; i++){path.add(nums[i]);dfs(i+1,nums);//撤销上一次的操作path.removeLast();}}
}
子集问题2
**输入：**nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 给出的元素是有重复元素的，
用一个used数组，防止出现重复，used数组还需要进行排序，是为了让相同的元素埃在一起
用startIndex往后进行取元素，需要进行数层的去重，如果元素相同，前面已经用过了，后面就不能再用了;
树层进行去重
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9WrQ54Lz-1691505556728)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230719151544419.png)]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {List<List<Integer>> result =new ArrayList<>();LinkedList<Integer> path =new LinkedList<>();boolean [] used;public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length==0){result.add(path);return result;}Arrays.sort(nums);used=new boolean[nums.length];dfs(nums,0);return result;}public void dfs(int []nums,int startIndex){result.add(new ArrayList<>(path)); //将每一个节点上面的元素都添加进来//和之前不同的是，需要收获每一个节点的元素//结束条件还没有确定呢if (startIndex>=nums.length){//到结尾了return;}for (int i = startIndex; i < nums.length; i++) {//需要进行数层的去重if (i>0&&nums[i]==nums[i-1]&&used[i-1]==false){//刚刚出现了失误的情况continue;//直接跳过;}path.add(nums[i]);used[i]=true;dfs(nums,i+1);path.removeLast();used[i]=false;}}
}
全排列问题
给定一个没有重复的数字序列，返回所有可能的排列
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I9iV2BWY-1691505556729)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711154624917.png)]
全排列问题 2，给定一个可能包含重复数字的序列nums，返回所有不重复的全排列
应该是树层进行去重[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f2rbAk07-1691505556729)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711155156611.png)]
组合问题和排列问题都是在树形结构的叶子节点收集结果，子集问题是取树上所有节点的结果
搜索专题
深度搜索 dfs 广度搜索 bfs 回溯 剪枝
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zyqKPB7M-1691505556729)(C:\Users\周鑫\AppData\Roaming\Typora\typora-user-images\image-20230711164315303.png)]
搜索bfs
bfs 常见的场景，问题的本质是让你在一幅图中找到从start到target的最近距离
要说框架的话，我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿，把枯燥的本质搞清楚了，再去欣赏各种问题的包装才能胸有成竹嘛。这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？再比如……净整些花里胡哨的，本质上看这些问题都没啥区别，就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质，框架搞清楚了直接默写就好。
bfs的框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {Queue<Node> q; // 核心数据结构Set<Node> visited; // 避免走回头路q.offer(start); // 将起点加入队列visited.add(start);while (q not empty) {int sz = q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i = 0; i < sz; i++) {Node cur = q.poll();/* 划重点：这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj()) {if (x not in visited) {q.offer(x);visited.add(x);}}}}// 如果走到这里，说明在图中没有找到目标节点
}
岛屿问题
岛屿问题的核心是用bfs/dfs算法遍历二维数组;
岛屿问题的小模版
// 方向数组，分别代表上、下、左、右
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};void dfs(int[][] grid, int i, int j, boolean[][] visited) {int m = grid.length, n = grid[0].length;if (i < 0 || j < 0 || i >= m || j >= n) {// 超出索引边界return;}if (visited[i][j]) {// 已遍历过 (i, j)return;}// 进入节点 (i, j)visited[i][j] = true;// 递归遍历上下左右的节点for (int[] d : dirs) {int next_i = i + d[0];int next_j = j + d[1];dfs(grid, next_i, next_j, visited);}// 离开节点 (i, j)
}
岛屿的数量
class Solution {// 主函数，计算岛屿数量int numIslands(char[][] grid) {int res = 0;int m = grid.length, n = grid[0].length;// 遍历 gridfor (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//如果开始遇到一个岛屿了，开始dfs淹没岛屿if (grid[i][j] == '1') {// 每发现一个岛屿，岛屿数量加一res++;// 然后使用 DFS 将岛屿淹了dfs(grid, i, j);}}}return res;}// 从 (i, j) 开始，将与之相邻的陆地都变成海水void dfs(char[][] grid, int i, int j) {int m = grid.length, n = grid[0].length;if (i < 0 || j < 0 || i >= m || j >= n) {// 超出索引边界return;}if (grid[i][j] == '0') {// 已经是海水了return;}// 将 (i, j) 变成海水grid[i][j] = '0';// 淹没上下左右的陆地//四个方向进行运动;dfs(grid, i + 1, j);dfs(grid, i, j + 1);dfs(grid, i - 1, j);dfs(grid, i, j - 1);}
}
岛屿的最大面积如何计算
类似于求岛屿的数量问题，只不过在每一次遍历的时候需要更新当时的最大面积即可;
单调栈
放入的元素是有序的，要么单调递减，要么单调递增;
递增：从栈底到栈顶的数据是从小到大的
递减：从栈底到栈顶的数据是从大到小的;单调栈的伪代码
stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 && 栈顶元素小于当前元素){栈顶元素出栈;更新结果;}当前数据入栈;}
}
数学逻辑问题
leetcode 292
leetcode 319
leetcode 877877
class Solution {public int bulbSwitch(int n) {return (int)Math.sqrt(n);//刚开始都是关闭的，如果某一栈灯是最后点亮的，那么他一定要被按奇数次开关//比如有六栈灯，需要进行六次操作，// 对于第六个灯会被按多少次呢？// 1 2 3 6都会被按// 求16的平方跟，因为最后会有4栈灯亮着// 第1 4 9 16;//一般情况下一个数的因子都是成对出现的//比如3=1*3//只有n的平方是只出现了一次的 4=2*2，那么这样就相当于操作了奇数次//最后就一定会亮着了，需要对一个数求它的平方根;}
}
贪心算法
局部最优推导全局最优
简单题目
455 分发饼干
技巧类算法
位运算
//打印十进制的二进制位数
public class 位运算 {public static void main(String[] args) {Scanner sc= new Scanner(System.in);solve(sc.nextInt());}public static void solve(int num){//1->0000 0000 0000 0000 0000 0000 0000 0001for (int i = 31; i >=0 ; i--) {//将十进制转为二进制;System.out.print((num&(1<<i))==0?"0":"1");}System.out.println();}
}
