解法1：快慢指针① 设链表长度为n，定义两个指针a、b都指向头结点，当a指针指向最后一个结点时，a的下标是n-1② 倒数第k个结点的下标是n-k，两者相差k-1个距离。所以让a指针先遍历向前走k-1步，此时a与b也相差k-1了，符合。③ 然后让它们一起向前走即可。 public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head==null || k<1){ return null; } ListNode fast=head,slow=head; for (int i = 0; i &...

方法1：递归 如果表1当前值小于表2当前值，表1当前值成为新链表的表头，否则返回表2的当前值作为新链表的表头。比较当前链表的值，较小的取其子链表继续递归。当有一个链表取到子链表为空时，说明已经比较完成，可以直接返回非空的链表，返回值赋给了l1.next或者l2.next，但无论如何，最终还是沿着递归链不断返回，最终返回的是新有序链表的表头。  public ListNode MergeTwoList1(ListNode list1,ListNode list2){ if(list1==null){ return list2; } if(list2==null){ return list1; }...

第一步，找环中相汇点。分别用p1，p2指向链表头部， p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。   那么我们可以知道fast指针走过a+b+c+b slow指针走过a+b 那么2*(a+b) = a+b+c+b 所以a = c 那么此时让slow回到起点，fast依然停在z，两个同时开始走，一次走一步 那么它们最终会相遇在y点，正是环的起始点/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val ...

方法1：排序方法2：Set方法3：哈希表方法4：并查集 解法1：排序+统计  排序数组 统计连续序列长度：遇到重复元素跳过；遇到不连续元素重置；遇到连续元素加一并更新max import java.util.*; public class Solution { /** * max increasing subsequence * @param arr int整型一维数组 the array * @return int整型 */ public int MLS (int[] arr) { if(arr == null || arr.length == 0){ return 0; } int len...

链接：https://blog.csdn.net/c1052981766/article/details/79130139java 三种方法实现最大公约数 import java.util.Collections; import java.util.HashSet; import java.util.Set; public class GCD { /** * 求最大公约数 辗转相除法(欧几里德算法) 例如，求（319，377）： ∵ 319÷377=0（余319） * ∴（319，377）=（377，319）； ∵ 377÷319=1（余58） ∴（377，319）=（319，58）； ∵ *...

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？ 面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。 解决办法：声明一个大小为 dp[n][V] 的二维数组， dp[i][j] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出dp[i][j] 的计算方法（1） j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿 dp[ i ][ j ] = d...

LRU (Least recently used) 最近最少使用 像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算***将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。下面谈谈如何实现LRU缓存：   新数据插入到链表头部 每当缓存命中（即缓存数据被访问），则将数据移到链表头部 当链表满的时候，将链表尾部的数据丢弃  LRU Cache具备的操作：  set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除...

构造两个优先级队列：左边大根堆放较小的数，右边小根堆放较大的数。  构建两个堆，左边大根堆放较小的数，右边小根堆放较大的数。 插入第一个数时，先插到左边，然后将左边最大的值传给右边的堆； 插入第二个数时，先插到右边，然后将右边最小的值传给左边的堆;如此往复，平衡两个堆的大小，最后得到的结果是右边堆的值都比左边的大。 import java.util.*; public class Solution { /** * the medians * @param operations int整型二维数组 ops * @return double浮点型一维数组 */ public double[] fl...

解法1：记忆化+深度优先 链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/javashi-xian-shen-du-you-xian-chao-ji-jian-dan-yi-/著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。---先从一个格子开始找，对比它4周的格子，有没有比它小的，如果有，比如有A，B，C三个格子都比它小，那么当前格子的最大连续递增长度就是这3个格子的最大连续递增长度中的最大值+1（有点绕，多读两遍应该就可以理解了），那么A，B，C的最大长度从...

解法1：贪心 要计算买卖两次的收益，只需要找到一天k，使得f(0, k) + f(k + 1, n - 1)最大即可;运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。case通过率为0.00%  public int maxProfit (int[] prices) { // write code here if(prices==null || prices.length==0){ return 0; } int max=Integer.MIN_VALUE; for(int i=0;i<prices.length;i++){ int temp=getMax...

解法1：利用数组记录已访问过的元素 import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> permute(int[] nums) { if (nums == null || nums.length < 1) return res; Arrays.sort(nums); A...

拓展：有重复项字符的所有排列解法1：Boolean+数组记录 import java.lang.*; import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>(); if(num == null || num.length == ...

力扣官方题解: https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/ 解法一：动态规划 思路和算法：复杂度分析时间复杂度： O(n)； n 为字符串的长度，只需遍历整个字符串一次，dp 数组即可求出来。空间复杂度： O(n)；我们需要一个大小为 n 的dp 数组。 public class Solution { public int longestValidParentheses(String s) { int ma...

调用库函数Arrays.sort 冒泡排序BubbleSort 快速排序QuickSort 归并排序MergeSort 堆排序HeapSort 优先级队列PriorityQueue  解法1：调用库函数Arrays.sort import java.util.Arrays; public class Solution { public int[] MySort (int[] arr) { //调用库函数sort； Arrays.sort(arr); return arr; } }解法2：冒泡排序BubbleSort 以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置...