- 博客(178)
- 收藏
- 关注
RSS订阅原创 力扣解题思路：分割回文串
131. 分割回文串思路：因为题目要求不是分割的方法种数，而是具体的分割方法，所以用dfs比较合适，那如果直接用dfs暴力遍历各种可能显然是不高效的，因此我们可以用一个set记录所有出现的回文子串（记忆化递归），这就不用每遇到一个子串就判断一次是不是回文字串了：class Solution { List<List<String>> res = new ArrayList<>(); Set<String> set = new HashSe
2021-07-04 11:31:15
224
1
原创 力扣解题思路：面试题 17.26. 稀疏相似度
面试题 17.26. 稀疏相似度思路：暴力法显然是可以，但是如何简化呢？思维转变一下，不是把两个数组比较，看有没有重复的。而是每次的数字出现，都去检查一下是否出现过，在哪个数组里出现的。 public List<String> computeSimilarities(int[][] docs) { int n = docs.length; List<String> ans = new ArrayList<>();
2021-06-03 09:19:54
175
原创 力扣解题思路：面试题 17.13. 恢复空格 纠错记录
面试题 17.13. 恢复空格思路：先看错误答案： public int respace(String[] dictionary, String sentence) { int[] dp = new int[sentence.length()+1]; for(int i=0;i<=sentence.length();i++) dp[i] = i; for(int i=1;i<=sentence.length();++i){
2021-05-27 16:49:37
165
1
原创 力扣解题思路：面试题 16.26. 计算器 纠错记录
面试题 16.26. 计算器思路：先看错误答案： public int calculate(String s) { Stack<Integer> stack = new Stack<>(); char sign = ' '; int i = 0; int res = 0; while(i < s.length()){ while(i < s.length(
2021-05-25 09:03:23
113
原创 力扣解题思路：面试题 16.06. 最小差
面试题 16.06. 最小差思路：给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差。首先暴力法可行，但是时间复杂度太高，那么要想降低时间复杂度首先需要排序，不排序是没有任何规律的，排序后可以采用双指针的方法，不断移动指针使指针指向的两个值越来越接近，哪一个指针更大我们就移动另一个指针使其接近： public int smallestDifference(int[] a, int[] b) { /* 对两个数组进行排序
2021-05-20 09:16:43
215
原创 力扣解题思路：面试题 05.03. 翻转数位
面试题 05.03. 翻转数位思路：两种方法：//使用数组记录连续 1 的个数。 如果遇见一段连续的 1，那么会在数组中同一个位置进行累加。// 如果遇见了 0，数组下标指针加 1。 稍微思考一下，不难明白此时本题就转换为数组中最大的相邻元素之和。 public int reverseBits(int num) { int[] arr = new int[32]; int idx = 0, max = 0; while(num != 0){
2021-05-14 09:30:46
110
原创 力扣解题思路：面试题 04.01. 节点间通路 纠错记录
面试题 04.01. 节点间通路思路：这一题dfs和bfs都是可以的，先写bfs：public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { Map<Integer, List<Integer>> map = new HashMap<>(); for(int[] p : graph){ if(!map.containsKey(
2021-05-13 09:24:58
89
原创 力扣解题思路：983. 最低票价
983. 最低票价思路：我们可以从后往前考虑，如果第 i 天需要出行，那么我们上一次的通行证必须能维持到第 i 天，也就是再第 i-1 天是否买一天通行证， 第 i-7 天是否买七天通行证，如果不出行，只需要保留昨天所花的代价就好了，这样就能推导出dp方程：dp[i] = min(dp[i-1]+costs[0] ,dp[i-7]+costs[1] ,dp[i-30]+costs[2]);由于所给的旅行日期是不连续的，且买票也可以在不旅行的日子买，所以我们动态数组的长度应该设置为：int[] d
2021-03-09 15:46:38
187
原创 力扣解题思路：双指针问题 纠错记录
剑指 Offer 57. 和为s的两个数字思路：实际上是很简单的题目，hashmap是肯定可以解决的，这里直接给出不解释： public int[] twoSum(int[] nums, int target) { Set<Integer> set = new HashSet<>(); for (int num : nums) { if (!set.contains(target - num))
2021-03-09 10:46:57
99
1
原创 力扣解题思路：862. 和至少为 K 的最短子数组 纠错记录
862. 和至少为 K 的最短子数组思路：我最初的思路是，先求出前缀和数组，然后使用双指针来定位长度，先移动至两指针差值大于K（移动j），然后再移动i来缩小范围： public int shortestSubarray(int[] A, int K) { if(A.length == 0) return -1; int[] sum = new int[A.length+1]; sum[0] = 0; for(int i=1;i<
2021-02-14 11:05:49
247
原创 力扣解题思路：670. 最大交换/parseInt和valueOf的区别
670. 最大交换思路：看到这题我第一反应就是想到下一个排列，不过很快发现这两题并没办法使用同一种思路，因为这一题是要求最大，且只能交换一次，相当于多了很多别的限制。初步的思路是，直接将数组排序，然后和原来的数组从左往右不断对比，如果一样就下一位，如果不一样则往数组后面找到这个最大数，然后交换位置，交换完就直接break即可： public int maximumSwap(int num) { if(num<10) return num; char[] a
2021-02-12 11:48:54
167
1
原创 力扣解题思路：剑指 Offer 54. 二叉搜索树的第k大节点 纠错记录
剑指 Offer 54. 二叉搜索树的第k大节点思路：这是一道简单题，但是我竟然做了几遍都没做对。。。先贴上我的错误答案： TreeNode pre = null; public int kthLargest(TreeNode root, int k) { inOrder(root,k); return pre.val; } public void inOrder(TreeNode root,int k){ if(root!
2021-02-09 10:30:31
81
原创 力扣解题思路：224. 基本计算器
224. 基本计算器思路：记录一下本菜鸡的做法：public int calculate(String s) { Stack<Character> stack = new Stack<>(); s = "(" + s + ")"; int i = 0; int res = 0; while(i<s.length()){ if(s.charAt(i) == ' '){ i++;
2021-02-06 18:11:39
162
原创 力扣解题思路：662. 二叉树最大宽度 纠错记录
662. 二叉树最大宽度思路：最开始我的想法是直接BFS，然后记录每一层从左到右的节点，遍历完一层后去掉左右的空节点，中间的节点数就是宽度了，然后就有： public int widthOfBinaryTree(TreeNode root) { if(root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root);
2021-02-03 09:18:08
150
原创 力扣解题思路：41. 缺失的第一个正数
41. 缺失的第一个正数思路：我之前想到的是桶排序，但是考虑到元素波动范围太大就放弃了，但是却发现了另外一个规律，就是缺失的第一个正数一定范围在[1, N+1]中，那么我们无需创建无限长的桶数组，只需和原数组一样长即可，每当遇到在当前几个桶中的数，我们就将该数置为负数，代表已出现过。具体是这样，我们对数组进行遍历，对于遍历到的数 x，如果它在 [1, N]的范围内，那么就将数组中的第 x-1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N
2021-01-30 09:10:18
106
原创 力扣解题思路：958. 二叉树的完全性检验 纠错记录
958. 二叉树的完全性检验思路：判断一棵树是否为完全二叉树。这题我有思路，首先就是BFS遍历整颗数，然后存入队列，从队列头部一个一个取出，如果遇到null则队列中不可以再有节点了，有就代表不是完全二叉树，于是有： public boolean isCompleteTree(TreeNode root) { if (root == null) return true; Queue<TreeNode> queue = new LinkedList<
2021-01-29 10:51:52
86
原创 力扣解题思路：128. 最长连续序列
128. 最长连续序列思路：先讲一下我的思路，最开始我的想法就是使用map，从头往后遍历寻找map.get(curNum - 1)，后来发现行不通，因为后面出现 curNum - 1 前面无法预知.所以需要先将全部的数加入到set中，然后再遍历整个数组，从当前数组两边扩散来找，我一想，这两层嵌套循环不得时间复杂度o（n2）啊！不行不行，再换一种思路。后来我又想到用桶排序的方法，但是考虑到题目所给的测试用例数字太大，太大的数组太浪费空间，所以也放弃了这种想法，还是第一种更靠谱。那么如何优化第一种思路
2021-01-28 10:52:03
269
2
原创 力扣解题思路：23. 合并K个升序链表
23. 合并K个升序链表思路：方法1：可以采用归并排序的思路，先两组两组分开，然后两两合并，自然而然要用到递归了。首先定义递归出口： if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2) return mergeTwoLists(lists[0],lists[1]);然后将数组分为两组： int mid = lists.lengt
2021-01-27 09:43:10
108
原创 力扣解题思路：54. 螺旋矩阵/矩阵遍历 纠错记录
54. 螺旋矩阵思路：把矩阵螺旋输出。做法也很简单，我们只需要每次输出一圈后更新横排的左右边界和竖排的上下边界即可，但是要保证左边界小于等于右边界，上边界小于等于下边界：public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); if(matrix.length == 0 || matrix[0].length == 0) retu
2021-01-24 08:44:25
100
原创 力扣解题思路：110. 平衡二叉树 纠错记录
110. 平衡二叉树思路：判断一棵树是否是平衡二叉树。属于简单题，用dfs记录每条路径的长度，比较每个节点的左右子树长度，只要不满足就是false。但是做到一半我竟然卡住了：public boolean flag = true;public boolean isBalanced(TreeNode root) { dfs(root); return flag;}public int dfs(TreeNode root){ if(root == null) return 0;
2021-01-23 15:53:32
82
原创 力扣解题思路：69. x 的平方根
69. x 的平方根思路：首先最简单的暴力法：public int mySqrt(int x) { long i = 0; long n = 0; while(n<=x){ i++; n = i*i; } return (int)i-1;}然后就是二分法了，我第一版本是这样的：public int mySqrt(int x){ int left = 0; int right = x/2+1;// 为了
2021-01-22 11:02:39
198
原创 力扣解题思路：92. 反转链表 II 纠错记录
92. 反转链表 II思路：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ n ≤ 链表长度。输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL先看我的错误答案：public ListNode reverseBetween(ListNode head, int m, int n) { ListNode p = head; //L
2021-01-22 09:34:14
66
原创 力扣解题思路：15. 三数之和 纠错记录
15. 三数之和思路：这一题数组多次做错，所以记录一下。思路很简单，固定一个数，再用双指针找另外两个数：public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); if(nums.length < 3) return res; for(in
2021-01-19 10:20:46
68
原创 力扣解题思路：3. 无重复字符的最长子串 纠错记录
3. 无重复字符的最长子串思路：题目很简单，就是普通的双指针+哈希表，于是我寻思用数组也行啊：public int lengthOfLongestSubstring(String s) { if(s.length() == 0) return 0; boolean[] arr = new boolean[26]; int i = 0; int j = 0; int count = 1; while(i<s.length() && j
2021-01-18 10:20:12
67
原创 力扣解题思路：215. 数组中的第K个最大元素
215. 数组中的第K个最大元素思路：用堆很简单，我就不多说了：public int findKthLargest(int[] nums, int k) { // init heap 'the smallest element first'（小顶堆） PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); //new PriorityQueue<Integer>((n1,
2021-01-17 10:55:08
94
原创 力扣解题思路：581. 最短无序连续子数组
581. 最短无序连续子数组思路：这一题有点类似脑筋急转弯，我最开始的思路是先将原数组复制一遍排序，排序后从两边开始与原数组对比，找到两边不一样的数的索引，这段长度即为所求，但是这显然有点刻意，而且时间复杂度也不低。那么是否可以不排序直接找到两边的端点呢？从左到右循环，记录最大值为 max，若 nums[i] < max, 则表明位置 i 需要调整, 直到遍历完所有数结束，记录需要调整的最大位置 i 为 high;。同理，从右到左循环，记录最小值为 min, 若 nums[i] > mi
2021-01-16 10:43:20
118
1
原创 力扣解题思路：543. 二叉树的直径/687. 最长同值路径/双重递归 纠错记录
543. 二叉树的直径思路：首先题目中说可以不穿过根节点，我自然就想到了双重递归，把每个节点都作为起点然后再遍历：int max = 0;public int diameterOfBinaryTree(TreeNode root) { if(root == null) return 0; dfs(root); diameterOfBinaryTree(root.left); diameterOfBinaryTree(root.right); return ma
2021-01-12 11:11:58
96
原创 力扣解题思路：542. 01 矩阵 纠错记录
542. 01 矩阵思路：先说我的思路，我想的是BFS+记忆数组，但是逻辑上出了点问题，先看我的错误代码：private int[][] vector = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};public int[][] updateMatrix(int[][] matrix) { if(matrix.length == 0) return new int[][]{}; int[][] visited = new int[mat
2021-01-11 11:27:49
148
原创 力扣解题思路：535. TinyURL 的加密与解密
535. TinyURL 的加密与解密思路：TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原
2021-01-08 10:03:24
171
1
原创 力扣解题思路：532. 数组中的 k-diff 数对 纠错记录
532. 数组中的 k-diff 数对思路：首先看我第一版本的错误代码（这里的map可以直接改成set，因为本身也没用到value）：public int findPairs(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>(); int sum = 0; for(int i=0;i<nums.length;i++){ int a = map.contains
2021-01-08 09:51:43
111
原创 力扣解题思路：523. 连续的子数组和
523. 连续的子数组和思路：因为求的是连续数组，我们可以用前缀和的方法，用map保存每个前缀和对k的余数，两个前缀和对k取余数的差为0，则证明中间的数和为k的倍数（0倍也算），所以先简单的写出代码框架：public boolean checkSubarraySum(int[] nums, int k) { if(nums.length < 2) return false; Map<Integer, Integer> map = new HashMap<
2021-01-07 09:29:46
230
原创 使用Postman调API接口的方法
https://blog.csdn.net/weixin_44069425/article/details/86217874
2021-01-06 11:31:43
398
原创 力扣解题思路：最长回文子序列/最长回文子串/数组拷贝问题 纠错记录
516. 最长回文子序列思路：这一题思路比较巧妙，记录一下。设dp[i][j]表示s[i:j]中的最长回文子序列长度，则(1) s[i] == s[j] ==> dp[i][j] = dp[i+1][j-1] + 2;(2) s[i] != s[j] ==> dp[i][j] = max(dp[i+1][j], dp[i][j-1])初始化: dp[i][i] = 1由i,j的更新方式知道i应该逆序，j应该正序，且j应该比i大：for (int i = n - 1; i >=
2021-01-05 11:16:05
108
1
原创 力扣解题思路：508. 出现次数最多的子树元素和 纠错记录
508. 出现次数最多的子树元素和思路：也是很简单一个题目，错就错在我手贱多加了个递归出口????private int max = 0;public int[] findFrequentTreeSum(TreeNode root) { if(root == null) return new int[0]; Map<Integer,Integer> map = new HashMap<>(); helper(root,map); List<
2021-01-04 10:46:36
83
原创 力扣解题思路：501. 二叉搜索树中的众数 纠错记录
501. 二叉搜索树中的众数思路：实际上很简单的一个题目，但是我错了一次又一次，所以再记录下：最初版本count被我初始化成0了，然而应该初始化为1，因为每个数字默认个数为1：TreeNode pre = null;int count = 1;int lastcount = -1;//TreeNode lastpre = null;List<Integer> list = new ArrayList<>();public int[] findMode(TreeNod
2021-01-04 09:27:11
114
原创 力扣解题思路：496. 下一个更大元素 I
496. 下一个更大元素 I思路：这个题目真的相当恶心，首先题目就没有说清楚，我们要找的是在nums1中出现的数出现在nums2中的位置对应的下一个更大元素！！一定也要找到nums2中对应数的位置！然后再用栈解题，我们直接先对nums2遍历一遍，记录nums2中出现的所有数的下一个更大数，然后将其保存在map中，这样就可以在求解nums1中的数时能够直接通过map.get(nums1[i])来得到nums1中数在nums2中对应的下一个更大数public int[] nextGreaterEleme
2020-12-31 10:23:24
115
2
原创 力扣解题思路：491. 递增子序列 纠错记录
491. 递增子序列思路：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]其实最开始我想到的是按照之前动态规划的方式来遍历数组，但是动态数组记录个数比较方便，不太适合记录链表，并且还有去重操作，总体实施起来比较麻烦，所以还不如直接DFS，用集合来去重。public Lis
2020-12-30 09:31:32
178
原创 力扣解题思路：488. 祖玛游戏
488. 祖玛游戏思路：实际上就是简单的消消乐，如果时间允许，最简单的暴力递归法也是可以的，就是把所有字母插入所有的位置，取最短且可以消去的插入球数即可。但是这样无脑插入是很浪费时间的，所以我们在插入的时候应该先选好合适的位置，分一下两种情况：（1）插入一个或两个颜色相同的球引发连锁反响。（2）往两个颜色相同的球中间插入一个颜色不同的球（为什么要这么做呢？见特殊测试用例二）。注意两个特殊的测试用例：测试用例一："WWRRGGRRWWRRGGRRWW", "GG"无论怎么插入，都无法完全消除，
2020-12-29 10:34:50
548
2
原创 力扣解题思路：486. 预测赢家
486. 预测赢家思路：这一题我也是没想出来，题目都看错了，我以为是随便取数，没想到是从两端取。。。首先这个题目可以观察出一个规律，就是当数组长度为偶数时，先手必胜。假设数组为[1, 2, 3, 4]，则可以将数组分为奇数列[1, 3]和偶数列[2, 4]，其和分别为4，6。此时如果先手选择了右边的4，也就是偶数列中的数，那么数组变为[1, 2, 3]，此时数组两边的数都是原数组中奇数列中的数，所以后手被迫只能选择奇数列中的数，比如3，然后先手再选择偶数列中的数字，也就是2，那么后手也是只能选择奇数列
2020-12-28 11:06:46
231
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人