网站建设g,7zwd一起做网店官网,西安微信网站开发,专业移动微网站建设目录 二维数组中的查找
重建二叉树
矩阵中的路径
剪绳子 剪绳子②
数值的整数次方
表示数值的字符串
树的子结构
栈的压入、弹出序列
从上到下打印二叉树①
从上到下打印二叉树③
二叉搜索树的后序遍历序列
二叉树中和为某一值的路径
复杂链表的复制
二叉搜索树与…目录 二维数组中的查找
重建二叉树
矩阵中的路径
剪绳子 剪绳子②
数值的整数次方
表示数值的字符串
树的子结构
栈的压入、弹出序列
从上到下打印二叉树①
从上到下打印二叉树③
二叉搜索树的后序遍历序列
二叉树中和为某一值的路径
复杂链表的复制
二叉搜索树与双向链表
字符串的排列
数字序列中某一位的数字
把数字翻译成字符串
礼物的最大价值
最长不含重复字符的子字符串
丑数
数组中数字出现的次数
数组中数字出现的次数②
n个骰子的点数
股票的最大利润
求12...n
构建乘积数组
只出现一次的数字
单词长度的最大乘积
数组中和为0的三个数
和大于等于target的最短子数组
乘积小于K的子数组
和为k的子数组
0和1个数相同的子数组
二维子矩阵的和
字符串中的变位词
字符串中的所有变位词
不含重复字符的最长子字符串
回文子字符串的个数
删除链表的倒数第n个结点
链表中环的入口节点
链表中的两数相加
重排链表 展平多级双向链表
排序的循环链表
插入、删除和随机访问都是O(1)的容器
最近最少使用缓存
变位词组 最小时间差
后缀表达式
小行星碰撞 每日温度
往完全二叉树添加节点 二叉树最底层最左边的值
二叉树的右侧视图
二叉树剪枝 从根节点到叶节点的路径数字之和
向下的路径节点之和
二叉搜索树中的中序后继
所有大于等于节点的值之和 二叉搜索树迭代器 值和下标之差都在给定的范围内
日程表
出现频率最高的k个数字 和最小的k个数对
先到这里吧后面就好多是没学过的知识比如前缀树有时间精力再做吧 二维数组中的查找 剑指 Offer 04. 二维数组中的查找 方法1Z字形查找 class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {if(matrix.length0 || matrix[0].length0)return false;int n0;int mmatrix[0].length-1;while(nmatrix.length m0){if(targetmatrix[n][m]){n;}else if(targetmatrix[n][m]){m--;}else{return true;}}return false;}
} 重建二叉树 剑指 Offer 07. 重建二叉树 方法1分治算法大佬讲的很清楚 我的代码过程展示 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {int[] preorder;HashMapInteger,Integer mapnew HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorderpreorder;if(preorder.length0)return null;for(int i0;iinorder.length;i){map.put(inorder[i],i);}return buildTree2(0,0,inorder.length-1);}public TreeNode buildTree2(int root,int left,int right){if(leftright)return null;TreeNode nodenew TreeNode(preorder[root]);int imap.get(preorder[root]);node.leftbuildTree2(root1,left,i-1);node.rightbuildTree2(i-leftroot1,i1,right);return node;}
} 矩阵中的路径 剑指 Offer 12. 矩阵中的路径 方法1深度优先搜索DFS剪枝思路 class Solution {public boolean exist(char[][] board, String word) {char[] wordsword.toCharArray();for(int i0;iboard.length;i){for(int j0;jboard[0].length;j){if(dfs(board,words,i,j,0))return true;}}return false;}public boolean dfs(char[][]board,char[] words,int i,int j,int k){//这个是终止条件边界if(i0 || iboard.length || j0 || jboard[0].length || board[i][j]!words[k])return false;//如果k已经是单词的长度那么说明单词存在于网格中if(kwords.length-1)return true;//给他做上标记此坐标中的字母已经使用过了board[i][j]0;//找下一个字母boolean resdfs(board,words,i-1,j,k1)||dfs(board,words,i1,j,k1)||dfs(board,words,i,j-1,k1)||dfs(board,words,i,j1,k1);//到这一步就已经是递归完成了因此我们需要把网格中的字母还原以备后面查找使用board[i][j]words[k];return res;}
} 剪绳子 剑指 Offer 14- I. 剪绳子 方法1动态规划 思路 class Solution {public int cuttingRope(int n) {int[] dpnew int[n1];dp[2]1;for(int i3;in1;i){for(int j2;ji;j){dp[i]Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
} 方法2贪心算法 class Solution {public int cuttingRope(int n) {if(n 4){return n - 1;}int res 1;while(n 4){res * 3;n - 3;}return res * n;}
} 剪绳子② 剑指 Offer 14- II. 剪绳子 II 方法1贪心算法思路 class Solution {public int cuttingRope(int n) {if(n4){return n-1;}long res1;while(n4){resres*3%1000000007;n-3;}return (int)(res*n%1000000007);}
} 数值的整数次方 剑指 Offer 16. 数值的整数次方 方法1快速幂使用二分法二进制方法实现思路 class Solution {public double myPow(double x, int n) {if(x0)return 0;if(n0)return 1;long bn;double res1.0;int zhengfu1;if(b0){zhengfu*-1;b-b;}while(b0){if((b1)1){res*x;}x*x;b1;}if(zhengfu-1){res1/res;}return res;}
} 表示数值的字符串 剑指 Offer 20. 表示数值的字符串 思路 class Solution {public boolean isNumber(String s) {//去掉首位空格s s.trim();//是否出现数字boolean numFlag false;//是否出现小数点boolean dotFlag false;boolean eFlag false;for (int i 0; i s.length(); i) {//判定为数字则标记numFlagif (s.charAt(i) 0 s.charAt(i) 9) {numFlag true;//小数点只可以出现再e之前且只能出现一次.num num.num num.都是被允许的} else if (s.charAt(i) . !dotFlag !eFlag) {dotFlag true;//判定为e需要没出现过e并且出过数字了} else if ((s.charAt(i) e || s.charAt(i) E) !eFlag numFlag) {eFlag true;//避免e以后没有出现数字numFlag false;//判定为-符号只能出现在第一位或者紧接e后面} else if ((s.charAt(i) || s.charAt(i) -) (i 0 || s.charAt(i - 1) e || s.charAt(i - 1) E)) {//其他情况都是非法的} else {return false;}}//是否出现了数字 return numFlag;}
} 树的子结构 剑指 Offer 26. 树的子结构 方法1先序遍历思路 class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {return (A ! null B ! null) (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));}boolean recur(TreeNode A, TreeNode B) {if(B null) return true;if(A null || A.val ! B.val) return false;return recur(A.left, B.left) recur(A.right, B.right);}
} 栈的压入、弹出序列 剑指 Offer 31. 栈的压入、弹出序列 方法1模拟栈思路 class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {StackInteger stacknew Stack();int i0;for(int num:pushed){stack.push(num);while(!stack.isEmpty() stack.peek()popped[i]){stack.pop();i;}}return stack.isEmpty();}
} 从上到下打印二叉树① 剑指 Offer 32 - I. 从上到下打印二叉树 方法1借助队列实现思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public int[] levelOrder(TreeNode root) {if(rootnull)return new int[0];QueueTreeNode queuenew LinkedList();queue.offer(root);ListInteger resnew ArrayList();while(!queue.isEmpty()){TreeNode tmpqueue.poll();res.add(tmp.val);if(tmp.left!null){queue.offer(tmp.left);}if(tmp.right!null){queue.offer(tmp.right);}}int[] arrnew int[res.size()];for(int i0;iarr.length;i){arr[i]res.get(i);}return arr;}
} 从上到下打印二叉树③ 剑指 Offer 32 - III. 从上到下打印二叉树 III 方法1借助双端队列实现思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resnew ArrayList();DequeTreeNode denew LinkedList();if(root!null)de.offer(root);while(!de.isEmpty()){ListInteger listnew ArrayList();for(int ide.size();i0;i--){TreeNode tmpde.pollFirst();list.add(tmp.val);if(tmp.left!null)de.offerLast(tmp.left);if(tmp.right!null)de.offerLast(tmp.right);}res.add(list);if(de.isEmpty())break;listnew ArrayList();for(int ide.size();i0;i--){TreeNode tmpde.pollLast();list.add(tmp.val);if(tmp.right!null)de.offerFirst(tmp.right);if(tmp.left!null)de.offerFirst(tmp.left);}res.add(list);}return res;}
} 二叉搜索树的后序遍历序列 剑指 Offer 33. 二叉搜索树的后序遍历序列 方法1递归分治class Solution {public boolean verifyPostorder(int[] postorder) {if(postorder.length0)return true;return postOrder(postorder,0,postorder.length-1);}public boolean postOrder(int[] postorder,int start,int end){if(startend)return true;int istart;for(;iend;i){if(postorder[i]postorder[end]){break;}}for(int ji;jend;j){if(postorder[j]postorder[end]){return false;}}return postOrder(postorder,start,i-1) postOrder(postorder,i,end-1);}
} 二叉树中和为某一值的路径 剑指 Offer 34. 二叉树中和为某一值的路径 方法1深度优先搜索/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {ListListInteger resnew ArrayList();ListInteger listnew ArrayList();public ListListInteger pathSum(TreeNode root, int target) {return dfs(root,target);}public void dfs(TreeNode root,int target){if(rootnull)return;target-root.val;list.add(root.val);if(target0 root.leftnull root.rightnull){res.add(list);}dfs(root.left,target);dfs(root.right,target);list.remove(list.size()-1);}
} 复杂链表的复制 剑指 Offer 35. 复杂链表的复制 方法1哈希表/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;}
}
*/
class Solution {public Node copyRandomList(Node head) {if(headnull)return null;MapNode,Node mapnew HashMap();Node curhead;while(cur!null){map.put(cur,new Node(cur.val));curcur.next;}curhead;while(cur!null){map.get(cur).nextmap.get(cur.next);map.get(cur).randommap.get(cur.random);curcur.next;}return map.get(head);}
} 二叉搜索树与双向链表 剑指 Offer 36. 二叉搜索树与双向链表 方法1中序遍历自己写出来的 /*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val _val;}public Node(int _val,Node _left,Node _right) {val _val;left _left;right _right;}
};
*/
class Solution {Node tmpnew Node(-1);Node pretmp;public Node treeToDoublyList(Node root) {if(rootnull)return null;Node curroot;inOrder(cur);tmp.right.leftpre;pre.righttmp.right;return tmp.right;}public void inOrder(Node cur){if(curnull)return;inOrder(cur.left);pre.rightcur;cur.leftpre;precur;inOrder(cur.right);}
} 字符串的排列 剑指 Offer 38. 字符串的排列 方法1深度优先搜索dfs)思路 class Solution {ListString resnew ArrayList();char[] c;public String[] permutation(String s) {cs.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}public void dfs(int x){if(xc.length-1){res.add(String.valueOf(c));}SetCharacter setnew HashSet();for(int ix;ic.length;i){if(set.contains(c[i]))continue;set.add(c[i]);swap(i,x);dfs(x1);swap(i,x);}}public void swap(int i,int x){char tmpc[i];c[i]c[x];c[x]tmp;}
} 数字序列中某一位的数字 剑指 Offer 44. 数字序列中某一位的数字 方法1思路目前做过可能两遍了但是靠自己想只能想出一半还有不懂的地方下次做的时候看看能不能想通 1.题目说从下标0开始计数这个条件在代码的哪里应用了 2.关于算num和算最终返回值的思路 class Solution {public int findNthDigit(int n) {int weishu1;long start1;long count9;while(ncount){n-count;weishu1;start*10;countweishu*start*9;}long numstart(n-1)/weishu;return Long.toString(num).charAt((n-1)%weishu)-0;}
} 把数字翻译成字符串 剑指 Offer 46. 把数字翻译成字符串 方法1动归通过字符串遍历的方式实现动归class Solution {public int translateNum(int num) {String sString.valueOf(num);int a1;int b1;for(int i2;is.length();i){String tmps.substring(i-2,i);int ctmp.compareTo(10)0 tmp.compareTo(25)0?ab:a;ba;ac;}return a;}
} 礼物的最大价值 剑指 Offer 47. 礼物的最大价值 方法1动态规划思路 class Solution {public int maxValue(int[][] grid) {int[][] dpnew int[grid.length][grid[0].length];dp[0][0]grid[0][0];for(int i1;igrid.length;i){dp[i][0]dp[i-1][0]grid[i][0];}for(int j1;jgrid[0].length;j){dp[0][j]dp[0][j-1]grid[0][j];}for(int i1;igrid.length;i){for(int j1;jgrid[0].length;j){dp[i][j]Math.max(dp[i-1][j],dp[i][j-1])grid[i][j];}}return dp[grid.length-1][grid[0].length-1];}
} 最长不含重复字符的子字符串 剑指 Offer 48. 最长不含重复字符的子字符串 方法1动态规划哈希表思路 这道题下次还得再做啊 class Solution {public int lengthOfLongestSubstring(String s) {int tmp0;int res0;MapCharacter,Integer mapnew HashMap();for(int j0;js.length();j){int imap.getOrDefault(s.charAt(j),-1);map.put(s.charAt(j),j);tmptmpj-i?tmp1:j-i;resMath.max(res,tmp);}return res;}
} 丑数 剑指 Offer 49. 丑数 方法1动态规划思路 class Solution {public int nthUglyNumber(int n) {int[] dpnew int[n];dp[0]1;int a0;int b0;int c0;for(int i1;idp.length;i){dp[i]Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);if(dp[a]*2dp[i])a;if(dp[b]*3dp[i])b;if(dp[c]*5dp[i])c;}return dp[dp.length-1];}
} 数组中数字出现的次数 剑指 Offer 56 - I. 数组中数字出现的次数 一开始我想的是用HashMap虽然能通过但是题目要求时间复杂度是O(n)空间复杂度是O(1)如果使用HashMap空间复杂度就超了 所以看了大佬的思路用下面这种方法做的 方法1位运算思路 class Solution {public int[] singleNumbers(int[] nums) {int x0;//x为其中一个只出现一次的数字int y0;//y为另外一个只出现一次的数字int n0;//n为遍历数组各数字异或运算的结果int m1;//m为x^y二进制位首位出现1时的对应的数字for(int num:nums){n^num;}while((n m)0){m1;}for(int num:nums){if((num m)0){x^num;}}return new int[]{x,x^n};}
} 数组中数字出现的次数② 剑指 Offer 56 - II. 数组中数字出现的次数 II 方法1位运算利用遍历统计法实现 思路 class Solution {public int singleNumber(int[] nums) {int[] countsnew int[32];for(int num:nums){for(int j0;jcounts.length;j){counts[j]num1;num1;}}int res0; for(int i0;icounts.length;i){res1;res|counts[31-i]%3;}return res;}
} 写的过程中这里大意写错了报了这样的错误就去了解下这个错误啥意思 required variable found value_qq_44842466的博客-CSDN博客 n个骰子的点数 剑指 Offer 60. n个骰子的点数 方法1动态规划 思路 这道题我真的还是没看懂也就是刚看完题解自己依旧做不出来的程度所以这里不放代码提醒自己这道题相当于还没做大家可以直接看上面的思路思路里有大佬写的代码哦 股票的最大利润 剑指 Offer 63. 股票的最大利润 方法1动态规划思路 class Solution {public int maxProfit(int[] prices) {int costInteger.MAX_VALUE;//cost将来用来存放当前股票的最小价格int profit0;//profit将来用来存放当前最大利润for(int price:prices){costMath.min(cost,price);profitMath.max(profit,price-cost);}return profit;}
} 求12...n 剑指 Offer 64. 求12…n 方法1逻辑符短路思路 class Solution {public int sumNums(int n) {boolean xn1 (nsumNums(n-1))0;return n;}
} 我一开始想的是二分法位运算但是失败了然后去看题解看有没有和自己想法一样的位运算解法之类的官方题解里到时有位运算快速乘的但是...emmmm算了还是先放弃位运算的方法吧 构建乘积数组 剑指 Offer 66. 构建乘积数组 方法1动态规划我先看的这个思路但代码没有按这个大佬的写而是看的下面评论区的另一位大佬用动态规划的思路写的 class Solution {public int[] constructArr(int[] a) {if(anull || a.length0)return new int[0];int lena.length;int[] leftOfInew int[len];int[] rightOfInew int[len];leftOfI[0]1;rightOfI[len-1]1;for(int i1;ilen;i){leftOfI[i]leftOfI[i-1]*a[i-1];}for(int ilen-2;i0;i--){rightOfI[i]rightOfI[i1]*a[i1];}int[] resnew int[len];for(int i0;ilen;i){res[i]leftOfI[i]*rightOfI[i];}return res;}
} 只出现一次的数字 剑指 Offer II 004. 只出现一次的数字 这道题和之前做的这道题题目不一样提示不一样但做法代码一模一样你会数组中数字出现的次数②这道题那么此题你也就会不过我把这道题还是贴在这儿了大家可以找找不同同时要建立一个警报系统对于做过的题要有条件反射拥有这种意识和能力这对未来大家面试做没做过或相似的题的时候有帮助~大家想看此题代码去数组中数字出现的次数②这道题中看代码就行就在这篇博客里我这里就不放了 单词长度的最大乘积 剑指 Offer II 005. 单词长度的最大乘积 方法1位运算模拟 这道题我最终搞懂是靠的这三位大佬 首先我先看的大佬1思路然后对于或运算和左移那一行代码不是很明白因此我就又看了大佬2的图以及大佬3的视频讲解 最终明白了或运算和左移那一行代码的意思最终自己了一遍代码思路还是大佬1的 class Solution {public int maxProduct(String[] words) {int[] wordnew int[words.length];int index0;for(String w:words){int res0;for(int i0;iw.length();i){int tmpw.charAt(i)-a;res|(1tmp);}word[index]res;}int max0;for(int i0;iword.length;i){for(int j0;ji;j){if((word[i]word[j])0){maxMath.max(max,words[i].length()*words[j].length());}}}return max;}
} 数组中和为0的三个数 剑指 Offer II 007. 数组中和为 0 的三个数 方法1排序双指针 思路 使用HashSet进行去重 class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);SetListInteger setnew HashSet();for(int i0;inums.length-2;i){if(i0 nums[i]nums[i-1])continue;int target-nums[i];int lefti1;int rightnums.length-1;while(leftright){int sumnums[left]nums[right];if(sumtarget){set.add(Arrays.asList(nums[i],nums[left],nums[right]));left;right--;}else if(sumtarget){right--;}else{left;}}}return new ArrayList(set);}
} 优化是上面思路里面评论区赵四儿大佬的优化思路 class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger resnew ArrayList();for(int i0;inums.length-2;i){if(nums[i]0)break;if(i0 nums[i]nums[i-1])continue;int target-nums[i];int lefti1;int rightnums.length-1;while(leftright){int sumnums[left]nums[right];if(sumtarget){res.add(Arrays.asList(nums[i],nums[left],nums[right]));left;right--;while(leftright nums[left]nums[left-1]){left;}while(leftright nums[right]nums[right1]){right--;}}else if(sumtarget){left;}else{right--;}}}return res;}
} 和大于等于target的最短子数组 剑指 Offer II 008. 和大于等于 target 的最短子数组 方法1滑动窗口 思路 class Solution {public int minSubArrayLen(int target, int[] nums) {int left0;int sum0;int resInteger.MAX_VALUE;for(int right0;rightnums.length;right){sumnums[right];while(sumtarget){resMath.min(res,right-left1);sum-nums[left];left;}}return restarget?0:res;}
} 乘积小于K的子数组 剑指 Offer II 009. 乘积小于 K 的子数组 方法1滑动窗口思路 class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {int left0;int sum1;int count0;for(int right0;rightnums.length;right){sum*nums[right];while(leftright sumk){sum/nums[left];}if(leftright){countright-left1;}}return count;}
} 和为k的子数组 剑指 Offer II 010. 和为 k 的子数组 这题还得再看再做 方法1前缀和哈希表这道题如果nums[i]的取值范围不包括负数的话那么就可以用滑动窗口 但是这样看来这道题不能用滑动窗口 因此我们要找一个其他的方法——前缀和 这个大佬的思路 加上 这个大佬的图 看完相信你应该懂得差不多了 class Solution {public int subarraySum(int[] nums, int k) {int sum0;//记录前缀和int count0;//记录个数MapInteger,Integer mapnew HashMap();map.put(0,1);for(int i:nums){sumi;countmap.getOrDefault(sum-k,0);map.put(sum,map.getOrDefault(sum,0)1);}return count;}
} 0和1个数相同的子数组 剑指 Offer II 011. 0 和 1 个数相同的子数组 这题还得再看再做 方法1前缀和哈希表思路 class Solution {public int findMaxLength(int[] nums) {int sum0;//记录前缀和int count0;//记录个数MapInteger,Integer mapnew HashMap();map.put(0,-1);for(int i0;inums.length;i){sumnums[i]0?-1:1;if(map.containsKey(sum)){countMath.max(count,i-map.get(sum));}else{map.put(sum,i);}}return count;}
} 二维子矩阵的和 剑指 Offer II 013. 二维子矩阵的和 没懂没懂没懂 方法1前缀和思路 class NumMatrix {int[][] mat;public NumMatrix(int[][] matrix) {int m matrix.length;int n matrix[0].length;mat new int[m 1][n 1];for (int i 1; i m; i) {mat[i][1] matrix[i-1][0];}for (int i 1; i m; i) {for (int j 1; j n; j) {mat[i][j] mat[i][j-1] matrix[i-1][j-1];}}for (int i 2; i m; i) {for (int j 1; j n; j) {mat[i][j] mat[i-1][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return mat[row2 1][col2 1] - mat[row1][col2 1] - mat[row2 1][col1] mat[row1][col1];}
} 字符串中的变位词 剑指 Offer II 014. 字符串中的变位词 方法1滑动窗口思路 class Solution {public boolean checkInclusion(String s1, String s2) {if(s1.length()s2.length())return false;int[] arr1new int[26];int[] arr2new int[26];for(int i0;is1.length();i){arr1[s1.charAt(i)-a];arr2[s2.charAt(i)-a];}for(int is1.length();is2.length();i){if(Arrays.equals(arr1,arr2)){return true;}arr2[s2.charAt(i-s1.length())-a]--;arr2[s2.charAt(i)-a];}return Arrays.equals(arr1,arr2);}
} 字符串中的所有变位词 剑指 Offer II 015. 字符串中的所有变位词 方法1滑动窗口思路有了这道题上面的题——字符串中的变位词的基础 这道题不是手到擒来嘛哇哈哈哈哈哈哈 class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger listnew ArrayList();if(p.length()s.length())return list;int[] arrsnew int[26];int[] arrpnew int[26];for(int i0;ip.length();i){arrs[s.charAt(i)-a];arrp[p.charAt(i)-a];}for(int ip.length();is.length();i){if(Arrays.equals(arrs,arrp)){list.add(i-p.length());}arrs[s.charAt(i-p.length())-a]--;arrs[s.charAt(i)-a];}if(Arrays.equals(arrs,arrp)){list.add(s.length()-p.length());}return list;}
} 不含重复字符的最长子字符串 剑指 Offer II 016. 不含重复字符的最长子字符串 还得再做 方法1滑动窗口思路 class Solution {public int lengthOfLongestSubstring(String s) {int left0;int count0;if(s.length()1)return s.length();MapCharacter,Integer mapnew HashMap();int right0;for(;rights.length();right){if(map.containsKey(s.charAt(right))){countMath.max(count,right-left);leftMath.max(left,map.get(s.charAt(right))1);}map.put(s.charAt(right),right);}countMath.max(count,right-left);return count;}
} 回文子字符串的个数 剑指 Offer II 020. 回文子字符串的个数 还得再做 方法1中心扩展class Solution {public int countSubstrings(String s) {int count 0;//字符串的每个字符都作为回文中心进行判断中心是一个字符或两个字符for (int i 0; i s.length(); i) {count countPalindrome(s, i, i);count countPalindrome(s, i, i1);}return count;}//从字符串的第start位置向左end位置向右比较是否为回文并计数private int countPalindrome(String s, int start, int end) {int count 0;while (start 0 end s.length() s.charAt(start) s.charAt(end)) {count;start--;end;}return count;}
} 删除链表的倒数第n个结点 剑指 Offer II 021. 删除链表的倒数第 n 个结点 方法1双指针傀儡节点/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode prenew ListNode(-1);pre.nexthead;ListNode fastpre;ListNode slowpre;while(n!0){fastfast.next;n--;}while(fast.next!null){fastfast.next;slowslow.next;}slow.nextslow.next.next;return pre.next;}} 链表中环的入口节点 剑指 Offer II 022. 链表中环的入口节点 方法1快慢指针/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!null fast.next!null){fastfast.next.next;slowslow.next;if(fastslow)break;}if(fastnull || fast.nextnull)return null;slowhead;while(fast!slow){fastfast.next;slowslow.next;}return slow;}
} 链表中的两数相加 剑指 Offer II 025. 链表中的两数相加 方法1反转链表/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {l1reserveList(l1);l2reserveList(l2);ListNode prenew ListNode(-1);int sum0;int jinwei0;int num10,num20;while(l1!null || l2!null || jinwei!0){if(l1!null){num1l1.val;l1l1.next;}else{num10;}if(l2!null){num2l2.val;l2l2.next;}else{num20;}sumnum1num2jinwei;jinweisum/10;ListNode nodenew ListNode(sum%10);node.nextpre.next;pre.nextnode;}return pre.next;}public ListNode reserveList(ListNode head){ListNode prenull;while(head!null){ListNode headNhead.next;head.nextpre;prehead;headheadN;}return pre;}
} 重排链表 剑指 Offer II 026. 重排链表 方法1快慢指针反转链表链表合并class Solution {public void reorderList(ListNode head) {// 找到中间节点ListNode mid findMid(head);// 通过中间节点将链表分为两部分左边一部分不动将右边一部分翻转ListNode curA head;ListNode curB reverse(mid.next);// 中间节点划分到左边部分mid.next null;// 将链表一分为二// 将两个链表合并merge(curA, curB);}private ListNode findMid(ListNode head){// 创建一个辅助头节点ListNode tmp new ListNode(0);tmp.next head;// 从辅助头节点开始快指针一次走2个单位慢指针一次走1个单位// 当快指针.next null 或者 快指针 null 则表明slow 指向了中间节点。ListNode slow tmp, fast tmp;while (fast ! null fast.next ! null){slow slow.next;fast fast.next.next;}return slow;}private ListNode reverse(ListNode head){ListNode reversedList null;while (head ! null){ListNode next head.next;head.next reversedList;reversedList head;head next;}return reversedList;}private ListNode merge(ListNode l1, ListNode l2){int flag 1;// 设定一个标记辅助交叉遍历两个链表// flag 为奇数则插入 l1 的节点 flag 为偶数则插入 l2 的节点ListNode head new ListNode(0);ListNode curhead;while (l1 ! null || l2 ! null){if (flag % 2 0){cur.next l2;l2 l2.next;}else{cur.next l1;l1 l1.next;}flag;cur cur.next;}return head.next;}
} 展平多级双向链表 剑指 Offer II 028. 展平多级双向链表 方法1深度优先搜索/*
// Definition for a Node.
class Node {public int val;public Node prev;public Node next;public Node child;
};
*/class Solution {public Node flatten(Node head) {Node lastdfs(head);return head; }public Node dfs(Node node){Node curnode;Node lastnull;// 记录链表的最后一个节点while(cur!null){Node nextcur.next;if(cur.child!null){Node childLastdfs(cur.child);cur.nextcur.child;cur.child.prevcur;// 如果 next 不为空就将 last 与 next 相连if(next!null){childLast.nextnext;next.prevchildLast;}cur.childnull;// 将 child 置为空lastchildLast;//这一步也很重要想想为什么}else{lastcur;}curnext;}return last;}
} 排序的循环链表 剑指 Offer II 029. 排序的循环链表 还得再写 方法1链表模拟思路 我是先看的上面这个思路然后自己写的代码我感觉写的没问题但是可能有很多代码的冗余因此导致运行超时 这时回头去看思路当中的代码发现大佬写的代码很妙~ class Solution {public Node insert(Node he, int x) {Node t new Node(x);t.next t;if (he null) return t;Node ans he;int min he.val, max he.val;while (he.next ! ans) {he he.next;min Math.min(min, he.val);max Math.max(max, he.val);}if (min max) {t.next ans.next;ans.next t;} else {while (!(he.val max he.next.val min)) he he.next;while (!(x min || x max) !(he.val x x he.next.val)) he he.next;t.next he.next;he.next t;}return ans;}
} 插入、删除和随机访问都是O(1)的容器 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 还需要再练练 方法1变长数组哈希表思路 class RandomizedSet {ListInteger list;MapInteger,Integer map;Random random;/** Initialize your data structure here. */public RandomizedSet() {listnew ArrayList();mapnew HashMap();randomnew Random();}/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */public boolean insert(int val) {if(!map.containsKey(val)){int listIndexlist.size();list.add(val);map.put(val,listIndex);return true;}return false;}/** Removes a value from the set. Returns true if the set contained the specified element. */public boolean remove(int val) {if(map.containsKey(val)){int mapIndexmap.get(val);int lastlist.get(list.size()-1);list.set(mapIndex,last);map.put(last,mapIndex);list.remove(list.size()-1);map.remove(val);return true;}return false;}/** Get a random element from the set. */public int getRandom() {int rrrandom.nextInt(list.size());return list.get(rr);}
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj new RandomizedSet();* boolean param_1 obj.insert(val);* boolean param_2 obj.remove(val);* int param_3 obj.getRandom();*/ 最近最少使用缓存 剑指 Offer II 031. 最近最少使用缓存 还要再做 方法1哈希表双向链表思路 class LRUCache {class DLinkedNode {int key; //初始化keyint value; //初始化value//初始化双向链表前后联系指针DLinkedNode prev;DLinkedNode next;//初始化双向链表public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key _key;value _value;}}//创建哈希表HashMapInteger, DLinkedNode map new HashMap();//链表当前大小int size;//链表当前容量int capacity;//链表头部尾部节点DLinkedNode head;DLinkedNode tail;public LRUCache(int capacity) {//大小初始化this.size 0;//容量初始化this.capacity capacity;//使用伪头部和伪尾部节点head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {//在哈希表中找到key所对应的节点DLinkedNode node map.get(key);//如果这个节点不存在则返回-1if (node null) {return -1;}//将这个节点移到头部再返回这个节点所对应的值movetohead(node);return node.value;}public void put(int key, int value) {//在哈希表中找到key所对应的节点DLinkedNode node map.get(key);//如果这个节点不存在则创建一个新的节点进行添加if (node null) {//创建新节点DLinkedNode newnode new DLinkedNode(key, value);//将节点加入哈希表map.put(key, newnode);//将这个节点添加到双向链表头部addtohead(newnode);//双向链表容量1size;//如果容量超过最大容量则需将双向链表尾部的节点移除if (size capacity) {//在链表中删去尾部节点同时哈希表中也移除掉这个节点并且双向链表容量-1DLinkedNode tail removetail();map.remove(tail.key);size--;}} else {//如果这个节点存在则直接修改valuenode.value value;//将这个节点在双向链表中移到头部movetohead(node);}}//在头部添加节点的方法public void addtohead(DLinkedNode node) {//head为虚拟头结点由于是双向链表添加一个节点需要建立四个连接关系node.prev head;node.next head.next;head.next.prev node;head.next node;}//移除节点方法public void removenode(DLinkedNode node) {//跳过这个节点重新建立双向连接关系node.prev.next node.next;node.next.prev node.prev;}//将节点移到头部的方法public void movetohead(DLinkedNode node) {removenode(node);addtohead(node);}//将节点从尾部移除的方法public DLinkedNode removetail() {//尾部的待删除节点即为虚拟尾结点的前一个节点DLinkedNode res tail.prev;//将这个节点删除removenode(res);return res;}
} 变位词组 剑指 Offer II 033. 变位词组 方法1哈希表排序 思路看的是方法1排序方法2计数有时间可以看看 class Solution {public ListListString groupAnagrams(String[] strs) {MapString,ListString mapnew HashMap();for(String str:strs){char[] ccstr.toCharArray();Arrays.sort(cc);String keynew String(cc);ListString listmap.getOrDefault(key,new ArrayListString());//妙啊妙啊这思路list.add(str);map.put(key,list);}return new ArrayList(map.values());}
} 最小时间差 剑指 Offer II 035. 最小时间差 这道题代码看懂了但自己没有单独写一遍有时间自己要写一遍 方法1排序 思路看的方法1哦 解释下1440怎么来的 class Solution {public int findMinDifference(ListString timePoints) {Collections.sort(timePoints);int ans Integer.MAX_VALUE;int t0Minutes getMinutes(timePoints.get(0));int preMinutes t0Minutes;for (int i 1; i timePoints.size(); i) {int minutes getMinutes(timePoints.get(i));ans Math.min(ans, minutes - preMinutes); // 相邻时间的时间差preMinutes minutes;}ans Math.min(ans, t0Minutes 1440 - preMinutes); // 首尾时间的时间差return ans;}public int getMinutes(String t) {return ((t.charAt(0) - 0) * 10 (t.charAt(1) - 0)) * 60 (t.charAt(3) - 0) * 10 (t.charAt(4) - 0);}
} 后缀表达式 剑指 Offer II 036. 后缀表达式 方法1栈class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new LinkedListInteger();int n tokens.length;for (int i 0; i n; i) {String token tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 stack.pop();int num1 stack.pop();switch (token) {case :stack.push(num1 num2);break;case -:stack.push(num1 - num2);break;case *:stack.push(num1 * num2);break;case /:stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !(.equals(token) || -.equals(token) || *.equals(token) || /.equals(token));}
} 小行星碰撞 剑指 Offer II 037. 小行星碰撞 方法1栈思路 class Solution {public int[] asteroidCollision(int[] asteroids) {StackInteger snew Stack();int p0;while(pasteroids.length){if(s.empty() || s.peek()0 || asteroids[p]0){s.push(asteroids[p]);}else if(s.peek()-asteroids[p]){if(s.pop()-asteroids[p]){continue;}}p;}int[] arrnew int[s.size()];for(int iarr.length-1;i0;i--){arr[i]s.pop();}return arr;}
} 每日温度 剑指 Offer II 038. 每日温度 方法1栈思路 class Solution {public int[] dailyTemperatures(int[] temperatures) {StackInteger stack new Stack();int[] ret new int[temperatures.length];for (int i 0; i temperatures.length; i) {while (!stack.empty() temperatures[stack.peek()] temperatures[i]) {int index stack.pop();ret[index] i - index;}stack.push(i);}return ret;}
} 往完全二叉树添加节点 剑指 Offer II 043. 往完全二叉树添加节点 方法1层序遍历队列思路 class CBTInserter { private QueueTreeNode queue;private TreeNode root;public CBTInserter(TreeNode root) {this.root root;queue new LinkedList();queue.offer(root);//在初始化树时就层序遍历到第一个没有左或右子树的节点即为待插入位置的父节点在队列头部while (queue.peek().left ! null queue.peek().right ! null) {TreeNode node queue.poll();queue.offer(node.left);queue.offer(node.right);}}public int insert(int v) {//队列头部节点即为待插入位置的父节点TreeNode parent queue.peek();TreeNode node new TreeNode(v);//插入左子树父节点仍无右子树父节点不变//插入右子树左右子树入列并将该父节点出列待插入位置更改为下一个if (parent.left null) {parent.left node;} else {parent.right node;queue.poll();queue.offer(parent.left);queue.offer(parent.right);}return parent.val;}public TreeNode get_root() {return root;}
}二叉树每层的最大值 剑指 Offer II 044. 二叉树每层的最大值 这道题完完全全是自己写出来的呱唧呱唧当然也是因为自己之前做题思路的积累在这基础上结合题目进行匹配~ 方法1队列下面这个未通过的例子帮助我修改代码最终AC /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger largestValues(TreeNode root) {ListInteger listnew ArrayList();if(rootnull)return list;QueueTreeNode queuenew LinkedList();queue.offer(root);list.add(root.val);while(!queue.isEmpty()){int curSizequeue.size();int sscurSize;int curCengMaxInteger.MIN_VALUE;int flag0;while(curSize!0){TreeNode tmpqueue.poll();if(tmp.left!null tmp.right!null){curCengMaxMath.max(curCengMax,Math.max(tmp.left.val,tmp.right.val));queue.offer(tmp.left);queue.offer(tmp.right);flag0;}else{if(tmp.left!null){curCengMaxMath.max(curCengMax,tmp.left.val);queue.offer(tmp.left);flag0;}else if(tmp.right!null){curCengMaxMath.max(curCengMax,tmp.right.val);queue.offer(tmp.right);flag0;}else{flag1;}}curSize--;}if(flagss){list.add(curCengMax);}}return list;}
} 二叉树最底层最左边的值 剑指 Offer II 045. 二叉树最底层最左边的值 方法1层序遍历队列原来这道题也是用这样的思路啊有点没想到哈哈哈还是经验优先啊举一反三能力还差点再加油 思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int findBottomLeftValue(TreeNode root) {QueueTreeNode queuenew LinkedList();queue.offer(root);int res0;while(!queue.isEmpty()){int curSizequeue.size();for(int i0;icurSize;i){TreeNode curRootqueue.poll();if(i0){rescurRoot.val;}if(curRoot.left!null){queue.offer(curRoot.left);}if(curRoot.right!null){queue.offer(curRoot.right);}}}return res;}
} 二叉树的右侧视图 剑指 Offer II 046. 二叉树的右侧视图 方法1层序遍历队列这道题导致我没做出来我觉得还是没有把层序遍历队列的思路融会贯通导致遇到套用这个思路的题他变了一些就还是会卡壳。 另外这道题也因为有侧视图如果右子树比左子树短会不会能看到左子树那边在纠结这个问题。。。就比如下面这个 思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger rightSideView(TreeNode root) {QueueTreeNode queuenew LinkedList();ListInteger listnew ArrayList();if(root!null){queue.offer(root);}while(!queue.isEmpty()){int curSizequeue.size();for(int i0;icurSize;i){TreeNode curRootqueue.poll();if(icurSize-1){list.add(curRoot.val);}if(curRoot.left!null){queue.offer(curRoot.left);}if(curRoot.right!null){queue.offer(curRoot.right);}}}return list;}
} 二叉树剪枝 剑指 Offer II 047. 二叉树剪枝 有时间可以再做做这个思路需要自己看到就能想到才算真的成功 方法1深度优先搜索 思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode pruneTree(TreeNode root) {if(rootnull)return null;root.leftpruneTree(root.left);root.rightpruneTree(root.right);if(root.val0 root.leftnull root.rightnull){rootnull;}return root;}
} 从根节点到叶节点的路径数字之和 剑指 Offer II 049. 从根节点到叶节点的路径数字之和 这道题还得再写思路还得自己想出来才行啊啊啊啊啊 方法1深度优先搜索思路 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int sumNumbers(TreeNode root) {return dfs(root,0);}public int dfs(TreeNode node,int val){if(nodenull)return 0;valval*10node.val;if(node.leftnull node.rightnull){return val;}return dfs(node.left,val)dfs(node.right,val);}
} 向下的路径节点之和 剑指 Offer II 050. 向下的路径节点之和 两个思路的代码都是直接拿过来的自己没写呢还得再看这道题这种题怎么这么难啊对我来说... 两个方法的思路 方法1深度优先搜索 class Solution {public int pathSum(TreeNode root, int targetSum) {if (root null) {return 0;}int ret rootSum(root, targetSum);ret pathSum(root.left, targetSum);ret pathSum(root.right, targetSum);return ret;}public int rootSum(TreeNode root, int targetSum) {int ret 0;if (root null) {return 0;}int val root.val;if (val targetSum) {ret;} ret rootSum(root.left, targetSum - val);ret rootSum(root.right, targetSum - val);return ret;}
} 方法2前缀和 class Solution {public int pathSum(TreeNode root, int targetSum) {HashMapLong, Integer prefix new HashMap();prefix.put(0L, 1);return dfs(root, prefix, 0, targetSum);}public int dfs(TreeNode root, MapLong, Integer prefix, long curr, int targetSum) {if (root null) {return 0;}int ret 0;curr root.val;ret prefix.getOrDefault(curr - targetSum, 0);prefix.put(curr, prefix.getOrDefault(curr, 0) 1);ret dfs(root.left, prefix, curr, targetSum);ret dfs(root.right, prefix, curr, targetSum);prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);return ret;}
} 二叉搜索树中的中序后继 剑指 Offer II 053. 二叉搜索树中的中序后继 还得再做思路得是自己想出来的才行 以下两种方法思路 方法1中序遍历迭代解法使用栈class Solution {public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {DequeTreeNode stack new ArrayDequeTreeNode();TreeNode prev null, curr root;while (!stack.isEmpty() || curr ! null) {while (curr ! null) {stack.push(curr);curr curr.left;}curr stack.pop();if (prev p) {return curr;}prev curr;curr curr.right;}return null;}
} 方法2利用二叉搜索树特点class Solution {public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode successor null;if (p.right ! null) {successor p.right;while (successor.left ! null) {successor successor.left;}return successor;}TreeNode node root;while (node ! null) {if (node.val p.val) {successor node;node node.left;} else {node node.right;}}return successor;}
} 所有大于等于节点的值之和 剑指 Offer II 054. 所有大于等于节点的值之和 还得再做 方法1反序中序遍历思路 class Solution {int sum 0;public TreeNode convertBST(TreeNode root) {if (root ! null) {convertBST(root.right);sum root.val;root.val sum;convertBST(root.left);}return root;}
} 二叉搜索树迭代器 剑指 Offer II 055. 二叉搜索树迭代器 两个方法都看懂了会做了但是自己没有写只是把代码贴上来了下次自己写 以下两个方法的思路 方法1递归class BSTIterator {private int idx;private ListInteger arr;public BSTIterator(TreeNode root) {idx 0;arr new ArrayListInteger();inorderTraversal(root, arr);}public int next() {return arr.get(idx);}public boolean hasNext() {return idx arr.size();}private void inorderTraversal(TreeNode root, ListInteger arr) {if (root null) {return;}inorderTraversal(root.left, arr);arr.add(root.val);inorderTraversal(root.right, arr);}
} 方法2迭代class BSTIterator {private TreeNode cur;private DequeTreeNode stack;public BSTIterator(TreeNode root) {cur root;stack new LinkedListTreeNode();}public int next() {while (cur ! null) {stack.push(cur);cur cur.left;}cur stack.pop();int ret cur.val;cur cur.right;return ret;}public boolean hasNext() {return cur ! null || !stack.isEmpty();}
} 值和下标之差都在给定的范围内 剑指 Offer II 057. 值和下标之差都在给定的范围内 没看懂所以还没写 思路 日程表 剑指 Offer II 058. 日程表 方法1直接遍历思路 class MyCalendar {Listint[] booked;public MyCalendar() {booked new ArrayListint[]();}public boolean book(int start, int end) {for (int[] arr : booked) {int l arr[0], r arr[1];if (l end start r) {return false;}}booked.add(new int[]{start, end});return true;}
} 方法2平衡二叉树思路 class MyCalendar {private TreeMapInteger, Integer map;public MyCalendar() {this.map new TreeMap();}public boolean book(int start, int end) {Map.EntryInteger, Integer entry1 map.floorEntry(start);Map.EntryInteger, Integer entry2 map.ceilingEntry(start);if (entry1 ! null entry1.getValue() start) {return false;}if (entry2 ! null entry2.getKey() end) {return false;}map.put(start, end);return true;}
}/*** Your MyCalendar object will be instantiated and called as such:* MyCalendar obj new MyCalendar();* boolean param_1 obj.book(start,end);*/ 出现频率最高的k个数字 剑指 Offer II 060. 出现频率最高的 k 个数字 方法1堆优先级队列思路 class Solution {public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer mapnew HashMap();for(int n: nums){map.put(n,map.getOrDefault(n,0)1);}PriorityQueueint[] pqnew PriorityQueue(new Comparatorint[](){public int compare(int[] m,int[] n){return m[1]-n[1];}});for(Map.EntryInteger,Integer entry:map.entrySet()){int kkentry.getKey();int vventry.getValue();if(pq.size()k){if(pq.peek()[1]vv){pq.poll();pq.offer(new int[]{kk,vv});}}else{pq.offer(new int[]{kk,vv});}}int[] resnew int[k];for(int i0;ik;i){res[i]pq.poll()[0];}return res;}
} 和最小的k个数对 剑指 Offer II 061. 和最小的 k 个数对 代码自己没写但差不多看懂了还得自己写出来才行 方法1优先级队列代码来自这里 思路来自这里 class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {PriorityQueueint[] pq new PriorityQueue((o1, o2) - {return (nums1[o1[0]] nums2[o1[1]]) - (nums1[o2[0]] nums2[o2[1]]);});// Math.min(nums1.length, k)加快处理速度for(int i 0; i Math.min(nums1.length, k); i ) {pq.offer(new int[] {i, 0});}ListListInteger list new ArrayList();while(k -- 0 !pq.isEmpty()) {int[] arr pq.poll();list.add(Arrays.asList(nums1[arr[0]], nums2[arr[1]]));// 上一个循环已经考虑完所有nums1的数这个循环考虑nums2中的数if(arr[1] nums2.length) {pq.offer(new int[] {arr[0], arr[1]});}}return list;}
} 先到这里吧后面就好多是没学过的知识比如前缀树有时间精力再做吧
