题目描述：力扣 解题思路：参考（https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/solution/zi-fu-chuan-de-zui-da-gong-yin-zi-by-leetcode-solu/）    class Solution { public String gcdOfStrings(String str1, String str2) { // 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。 if (!(str1 + str2).equals(st...

   class Solution { public int lengthOfLIS(int[] nums) { int len =nums.length; if(len == 0) return 0; int[] record = new int[len]; int max_index = len-1; for(int i = len-1; i >= 0 ; i-- ){ if(nums[i]<nums[max_index]){ record[i]= record[max_index]+1; max_index = i; } else{ int j = i+1; while(j ...

题目描述：力扣 解题思路： 直接去判断矩形重叠比较困难，考虑不重叠的情况，不重叠的情况比较简单。 有四种情形不重叠，可以自己画一下。  class Solution { //p1: x1:rec1[0], y1:rec1[1], x2:rec1[2], y2:rec1[3] //p2: x1:rec2[0], y1:rec2[1], x2:rec2[2], y2:rec2[3] public boolean isRectangleOverlap(int[] rec1, int[] rec2) { if(rec1[0]>=rec2[2]||rec1[2]<=rec2[0]||rec1...

题目描述：力扣 思路：快速排序的变形，不需要完全排序 由partition函数返回的下标将数组分成2部分，前边大于等于下标元素，后边小于等于下标元素， 当该下标等于K-1时（因为数组下标是从0开始的，所以是K-1），直接返回数组的前K个元素； 当返回的下标大于K-1时，只需要对下标前部分进行排序，后部分元素不需要； 当返回的下标小于K-1时，需要对后部分进行排序，前面的不需要； 在Partition函数中需要注意的是以第一个元素为基准时，先进行的是从后往前遍历，找到小于基准值的元素，将其值赋给low指向的位置，再进行从前向后的遍历，找到大于基准值的元素，将其值赋给high指向的元素。   cl...

题目描述：力扣 解题思路：参考自链接 一、使用bfs模拟6种倒水的操作  将水壶1的水倒满； 将水壶1的水清空； 将水壶2的水倒满； 将水壶2的水清空； 将水壶1的水倒入水壶2中，知道水壶2满了或者水壶1没水了就停止倒； 将水壶2的水倒入水壶1中，知道水壶1满了或者水壶2没水了就停止倒；  而且，不同的操作，中间过程会有很多重复的状态。因此可以用一个HashSet来记录已经访问过的状态(x,y) 二、 可以使用数学方法贝祖定理；连接：https://leetcode-cn.com/problems/water-and-jug-problem/solution/shui-hu-wen-ti-by...

题目描述：力扣 解题思路： （一） 我们将上述问题建模为函数 f(n, m)，该函数的返回值为最终留下的元素的序号。 首先，长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n - 1 的序列。那么，我们可以递归地求解 f(n - 1, m)，就可以知道对于剩下的 n - 1 个元素，最终会留下第几个元素，我们设答案为 x = f(n - 1, m)。 由于我们删除了第 m % n 个元素，将序列的长度变为 n - 1。当我们知道了 f(n - 1, m) 对应的答案 x 之后，我们也就可以知道，长度为 n 的序列最后一个删除的元素，应当是从 m % n 开始数的第 x 个...

 题目：力扣  class Solution { public int[] sortArray(int[] nums) { if(nums.length<=1){ return nums; } //quicksort(nums,0,nums.length-1); mergesort(nums,0,nums.length-1); return nums; } public int Partition(int[] nums,int start, int end){ int base = nums[start]; while(end>start){ while(end>start ...

题目描述：力扣 思路：使用了BFS，看官方解答并没有用到算法，而是复制了数组，是复制的数组保持不变，判断的时候也是利用复制的数组判断是否改变。  class Solution { public void gameOfLife(int[][] board) { int row = board.length; int col = board[0].length; int[][] state = new int[row][col]; for(int i = 0 ; i < row; i++){ for(int j = 0 ; j < col; j++){ state[i][j]=0; }...

题目描述：力扣 解题思路：参考链接 用了双指针的方法，其实就是按列求方法的改良，最重要的点就是求左右的最大值，再将求得过程一步步来优化。  class Solution { public int trap(int[] height) { int res = 0; int max_left = 0; int[] max_right = new int[height.length]; for(int i = height.length-2; i > 0; i--){ max_right[i]=Math.max(height[i+1], max_right[i+1]); } for(int i...

题目描述：力扣 解题思路：定义一个Map<Integer, int[]> dictionary; 数组的长度为3，index=0的位置存储value值，index=1的位置存储操作次数，index=2的位置存储最近一次操作的编号(cnt)。  class LFUCache { int cnt = 0;//操作编号，无论是put操作还是get操作都会加1 int capacity = 0;//容量 Map<Integer, int[]> dictionary; public LFUCache(int capacity) { this.capacity = capacity...

题目描述：力扣 解题思路： 一. 广度优先搜索 思路： 对于 「Tree 的 BFS」 （典型的「单源 BFS」） 大家都已经轻车熟路了： 首先把 root 节点入队，再一层一层无脑遍历就行了。 对于 「图 的 BFS」 （「多源 BFS」） 做法其实也是一样滴～，与 「Tree 的 BFS」的区别注意以下两条就 ok 辣～ Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队； Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！【 看见很多人说自己的 BFS 超...

题目：全排列1  全排列2 解题思路： 回溯法，有大佬总结了回溯法的模板，在这里借用，链接：回溯法 在递归之前做选择，在递归之后撤销选择 其中，全排列2用到了剪枝  全排列1  class Solution { List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { //记录路径 List<Integer> track = new LinkedList<>(); //回溯 bac...

题目：力扣  class Solution { public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for (int i = 0; i < length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } } return steps; } }     超时代码：  cl...

建树的地方有一点问题，0也是结点了，但应该不影响结果  import java.util.*; class TreeNode{ int val; TreeNode left = null; TreeNode right = null; TreeNode(int x){ val = x; } } public class Main { public static int res = Integer.MIN_VALUE; private static int maxSum(TreeNode root) { if(null == root) { return 0; } int l_max = Mat...