啊我太菜了-CSDN博客

原创 404. 左叶子之和

404. 左叶子之和难度：简单2020/9/19每日一题打卡√题目描述解题思路为啥都说这个是弱智题哇，我还想了好久来着最后写出的答案画风跟评论里的也有点不一样想的是分情况，如果已经是左叶子节点，就累加结果，否则继续遍历public int sumOfLeftLeaves(TreeNode root) { if(root == null) { return 0; } if(root.left == null){

2020-09-19 10:18:54 177

原创 637. 二叉树的层平均值

637. 二叉树的层平均值难度：简单题目描述解题思路普普通通的层序遍历/* * 637. 二叉树的层平均值 * 2020/9/14 * easy */ public List<Double> averageOfLevels(TreeNode root) { List<Double> res = new LinkedList<>(); if(root == null)

2020-09-14 12:55:17 165

原创 79. 单词搜索 DFS回溯

79. 单词搜索难度：中等前几天小米笔试的真题来着，但是当时没给二维矩阵题目描述解题思路回溯+剪枝+状态重置 /* * 79. 单词搜索 * 2020/9/14 * medium */ public boolean exist(char[][] board, String word) { char[] str = word.toCharArray(); int m = board.l

2020-09-14 10:46:37 204

原创 216. 组合总和 III

216. 组合总和 III难度：中等2020/9/11每日一题打卡题目描述解题思路也是回溯+剪枝，貌似好像也只要套模板1 和2都是给定数组，这个是1-9里面选数字，其实也能被看作是数组，每个数字只能被选一次最后不仅仅要求总和等于给定值，长度也要满足要求 /* * 216. 组合总和 III * 2020/9/11 * medium */ public List<List<Integer>> comb

2020-09-11 21:40:42 133

原创 40. 组合总和 II

40. 组合总和 II难度：中等题目描述解题思路和组合总和的区别是：1、这个每个数字只能选一次，所以下次要从i+1开始选2、可能有重复数字，所以要进行判重重复发生的情况主要是在比如说1 1 2 ，第一次选了1 2，第二次还能再选1 2，就重复了。关键在于不同递归深度的数字不能一样，可以用同一个语句来实现巧妙的判重：if(i != cur && candidates[i] == candidates[i-1])continue;/* * 40. 组合总和 II

2020-09-11 21:02:06 51

原创 39. 组合总和

39. 组合总和难度：中等这个月是回溯专题嘛题目描述解题思路回溯+剪枝，套模板的题/* * 39. 组合总和 * 2020/9/9 */ public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList&

2020-09-09 10:11:06 74

原创 416. 分割等和子集 0/1背包问题

416. 分割等和子集难度：中等就是很经典的0/1背包问题，背包容量有限，对于每个物品要么全选要么不选，而且每个位置只能选一次，看最后能不能装满背包题目描述解题思路1、二维dpdp[i][j]表示前i个物品能不能组合成等于j的先计算target，就是整个数组和的一半，然后开始装背包初始化第一列，就是不管多少个物品都能组成容量为0的背包状态转移方程：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];对于每个位置要么选要么不选，不选就是dp[i-1

2020-09-08 16:03:49 138

原创 77. 组合回溯+剪枝

77. 组合难度：中等题目描述解题思路1、自己写的憨憨思路就是用全排列的代码+剪枝，每次只往里面添加更大的数字但是其实可以不用这样public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new LinkedList<>(); if(n == 0 || k == 0) return res

2020-09-08 10:05:20 99

原创 347. 前 K 个高频元素

347. 前 K 个高频元素难度：中等题目描述解题思路搞得花里胡巧，还不是top k问题嘛就是多了个用hashmap统计频次的操作/* * 347. 前 K 个高频元素 * 2020/9/7 * medium */ public int[] topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> hashMap = new

2020-09-07 21:04:37 78

原创 60. 第k个排列回溯法+数学法

60. 第k个排列难度：中等题目描述解题思路1、回溯法就是很正常的全排列，然后设置一个计数位，如果count == k，就提前终止递归过程/* * 60. 第k个排列 * 2020/9/5 * medium */ int count1 = 0; String res = ""; public String getPermutation(int n, int k) { StringBuild

2020-09-05 10:42:35 169

原创 486. 预测赢家

486. 预测赢家难度：中等题目描述解题思路1、记忆化递归每次做出一个选择之后，比如1 4 2 19选了1，那对方可以选19，我只能选4，对方选2，我就输了选19，那对方选2，我选4，就赢了大概的递归代码是： //做出这一轮选择之后，还要让下一轮对手拿到的比较小 //这一轮选左边的 int num1 = nums[low] + Math.min(predictHelper(nums,low+1,high-1,memo), predictHelper(nums,low+2,high,

2020-09-01 17:44:29 370

原创 841. 钥匙和房间 DFS

841. 钥匙和房间难度：中等题目描述解题思路就是很正常的图搜索，看看能不能全部访问到BFS和DFS都行，但是我对dfs不太熟，就用dfs写啦/* * 841. 钥匙和房间 * 2020/8/31 * medium */ public boolean canVisitAllRooms(List<List<Integer>> rooms) { int n = rooms.size(); bo

2020-08-31 21:42:09 93

原创 541. 反转字符串 II

541. 反转字符串 II难度：简单题目描述解题思路类似k个一组反转链表那样 /* * 541. 反转字符串 II * 2020/8/30 * easy */ public String reverseStr(String s, int k) { char[] str = s.toCharArray(); for (int i = 0; i < str.length; i

2020-08-30 12:13:49 77

原创 557. 反转字符串中的单词 III

557. 反转字符串中的单词 III难度：简单今天周末居然是简单题题目描述解题思路很友好了，只有空格，直接spilt/* * 557. 反转字符串中的单词 III * 2020/8/30 * easy */ public String reverseWords3(String s) { String[] words = s.split(" "); StringBuilder sb =

2020-08-30 10:33:33 78

原创剑指 Offer 30. 包含min函数的栈

剑指 Offer 30. 包含min函数的栈难度：简单题目描述解题思路因为栈是先进后出，出栈是有一定规律的，不是随机的，所以每个元素在入栈的时候其实就已经确定当前最小的元素是哪个，所以可以在入栈的时候顺便保存最小元素信息。可以用两个栈来进行同步，但是也可以只用一个栈import java.lang.Integer;import java.util.Stack;class Node{ int val; int min; public Node(int v,int m) { val

2020-08-29 17:33:54 91

原创 214. 最短回文串

214. 最短回文串难度：困难题目描述解题思路发现一个问题，substring害挺慢的，一开始用substring老超时，后来改成直接用下标之后就不超时了渣渣不会KMP和马拉车，直接暴力法得了困难+1 积分+10public String shortestPalindrome(String s) { char[] str = s.toCharArray(); String right = ""; //找最长回文前缀 for (int i = str.length

2020-08-29 17:06:27 113

原创 47. 全排列 II 回溯

47. 全排列 II难度：中等题目描述解题思路全排列1是没有重复数字生成全排列，这个是有重复数字。先复习一下没有重复数字的写法：public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); b

2020-08-28 21:52:57 111

原创 17. 电话号码的字母组合 DFS

17. 电话号码的字母组合难度：中等最近好多DFS回溯的题欸题目描述解题思路回溯其实就是暴力递归遍历，一般如果是求所有可能的排列这种，大概就是用回溯做模板：backtracking() { if (终止条件) { 存放结果; } for (枚举同一个位置的所有可能性，可以想成节点孩子的数量) { 递归，处理节点; backtracking(); 回溯，撤销处理结果 }}对于这个题，用一个S

2020-08-28 21:03:44 117

原创 332. 重新安排行程 DFS欧拉回路

332. 重新安排行程难度：中等好几天前的每日一题，偷懒今天才写题目描述解题思路主要思想大概是先建图，然后从起点开始dfs吗，但是和传统回溯不同，在递归到最后的时候才把这次结果加入到结果集合里，并且要逆序插入/* * 332. 重新安排行程 * 2020/8/27 * medium */ public List<String> findItinerary(List<List<String>> t

2020-08-28 20:42:28 108

原创 657. 机器人能否返回原点

657. 机器人能否返回原点难度：简单好久不见的简单题题目描述解题思路1、模拟走的过程/* * 657. 机器人能否返回原点 * 2020/8/28 */ public boolean judgeCircle(String moves) { int x = 0,y = 0; for (int i = 0; i < moves.length(); i++) { char mo

2020-08-28 17:55:27 68

原创 695. 岛屿的最大面积 dfs模板题

695. 岛屿的最大面积难度：中等题目描述解题思路标准DFS加剪枝模板题了 /* * 695. 岛屿的最大面积 * 2020/8/25 */ public int maxAreaOfIsland(int[][] grid) { int m = grid.length; int n = grid[0].length; boolean [][] visit = new boolean[m][n];

2020-08-25 23:16:48 90

原创剑指 Offer 54. 二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第k大节点难度：简单题目描述解题思路中序遍历对二叉搜索树的中序遍历就是升序数组public int kthLargest(TreeNode root, int k) { List<Integer> res = new ArrayList<>(); inOrderHelper(root,res); for (int i = 0; i < res.size(); i++) { Syste

2020-08-25 13:30:42 72

原创 491. 递增子序列回溯法

491. 递增子序列难度：中等2020/8/25题目描述解题思路1、抄官方题解递归枚举子序列的模板：对于这个题，判断是否合法就是当前这个选择是不是能和前一个元素组成升序序列还需要判断是否重复/* * 491. 递增子序列 * 2020/8/25 * 难度：中等 */ public List<List<Integer>> findSubsequences(int[] nums) { List&

2020-08-25 11:37:59 237

原创 678. 有效的括号字符串

678. 有效的括号字符串难度：中等题目描述解题思路1、抄的答案思路好巧妙，反正我自己肯定想不出来/* * 678. 有效的括号字符串 * 2020/8/24 */ public boolean checkValidString(String s) { int left = 0,right = 0; //加上*号之后，未匹配左括号的数量从一个值变成了一个范围，用两个变量来记录这个范围的上界和下界

2020-08-24 21:45:41 180

原创 201. 数字范围按位与

201. 数字范围按位与难度：中等题目描述解题思路1、找mn的最长公共前缀因为是对一系列连续的数字进行与运算，所以在最长公共前缀后面的数字，一定会有某一个数的那一位是0，在做与运算的时候都会被清除掉变成0。所以这个问题就等价于求m和n对应的二进制数字的最长公共前缀所表示的数字。每次右移就是去掉最右边一位，直到m=n，要注意的是最后还得左移对应的次数/* * 201. 数字范围按位与 * 2020/8/24 * 实际上就是求m和n的最长公共前缀 */

2020-08-24 17:54:26 146

原创 986. 区间列表的交集双指针法

986. 区间列表的交集难度：中等题目描述解题思路双指针依次判断两个区间是不是有交集，如果有的话，把在前面的区间指针后移，因为区间是有序的，在后面的区间有可能还会跟别的相交，在前面的不会跟后面的相交了/* * 986. 区间列表的交集 * 2020/8/24 */ public int[][] intervalIntersection(int[][] A, int[][] B) { int m = A.le

2020-08-24 12:34:21 89

原创 459. 重复的子字符串

459. 重复的子字符串难度：简单2020/8/24每日一题打卡题目描述解题思路1、构造重复字符串想法很巧妙啊，大概是这辈子我也想不出来的方法哈哈哈比如说abcabc，两个拼一起就是 a【bcabcabcab】c去掉首尾两个字符，实际上就是破除了循环看剩下的字符中是否包含原来的子串，如果包含则说明存在循环，如果不包含则不存在相当于模拟那个滑动窗口的过程/* * 459. 重复的子字符串 * 2020/8/24 */ public boolean

2020-08-24 10:48:54 218

原创 529. 扫雷游戏 DFS

529. 扫雷游戏2020/8/20每日一题打卡√题目描述解题思路感觉这个题最难的点还是在于理解题意和样例理解了之后就很明确了，就是正常的DFS如果点击了雷，就爆炸如果没点到雷，就判断这个位置旁边有没有雷；如果有雷，把这个位置设置成周围雷的数量如果没有雷，把这个位置标记成B，然后递归的标记标记位置周围的位置 /* * 529. 扫雷游戏 * 2020/8/20 * medium */ public char[][] updateBoard(

2020-08-20 21:01:46 171

原创 647. 回文子串 dp+中心拓展法

647. 回文子串难度：中等2020/8/19每日一题打卡题目描述解题思路1、动态规划法定义的状态就是 dp[i][j]表示从i-j这个是不是回文对于长度是一个字符的直接是回文，两个字符的话就比较是不是相等对于两个以上，就看中间部分能不能组成回文串，然后比较两边是不是相等dp[i][j] = dp[i+1][j-1] && dp[i] == dp[j]，要用到右边的，所以第一层循环反着遍历/* * 647. 回文子串 * 2020/8/19 *

2020-08-19 11:23:40 168

原创 110. 平衡二叉树自底向上和自顶向下

110. 平衡二叉树难度：简单题目描述解题思路这个题好像做过的样子自底向上可以避免很多重复的运算自底向上/* * 110. 平衡二叉树 * 2020/8/17 */ public boolean isBalanced(TreeNode root) { return isBalancedHelper(root) == -1; } public int isBalance

2020-08-17 09:36:21 227

原创剑指 Offer 50. 第一个只出现一次的字符

剑指 Offer 50. 第一个只出现一次的字符难度：简单题目描述解题思路因为给的限制是只会出现小写字母，所以就用一个数组来存储，也可以用哈希表，还有有序哈希表/* * 剑指 Offer 50. 第一个只出现一次的字符 * 2020/8/16 */ public char firstUniqChar(String s) { int[] num = new int[26]; for (int i =

2020-08-16 23:29:25 88

原创 733. 图像渲染简单DFS

733. 图像渲染难度：简单2020/8/16每日一题打卡√题目描述解题思路题目真的又臭又长，但是读懂之后发现就是单纯的简单的图搜索问题，dfs或者bfs都能搞定DFS写dfs的时候总忘记加访问数组，结果就爆栈 /* * 733. 图像渲染 * 2020/8/16 * 难度：简单 */ public int[][] floodFill(int[][] image, int sr, int sc, int newC

2020-08-16 17:19:30 172

原创 148. 排序链表归并排序

148. 排序链表难度：中等题目描述解题思路/* * 148. 排序链表 * 2020/8/13 * 1对链表进行归并排序 * 1、快慢指针找中间节点 * 2、递归调用mergeSort * 3、合并有序链表 */ public ListNode sortList(ListNode head) { return listMergeSort(head);

2020-08-13 19:11:57 68

原创 43. 字符串相乘

43. 字符串相乘2020/8/13每日一题打卡难度：中等题目描述解题思路1、常规思路大概就是按照平时做数学题的方式，一位一位乘上去然后最后相加注意要对于第二个数字个位以外的数字，最后要补充相应位数的0 /* * 43. 字符串相乘 * 2020/8/13 * 1难度：中等 */ public String multiply(String num1, String num2) { //让num1是长度比较长

2020-08-13 11:41:09 128

原创 696. 计数二进制子串

696. 计数二进制子串难度：简单题目描述解题思路今天的简单题但是感觉思路有点不好想诶重点在于连续出现相同的字符，大概是滑动窗口的思想？用两个变量来计数，pre记录上一个连续出现的字符长度，cur记录当前字符出现的次数。例如00110，那到0011的时候，pre = 2,cur=2只要cur <= pre，就一定能组成符合要求的字串。用last来保存上次连续出现的字符（也可以不用），如果这个跟上一个相同，就cur++当遇到不同的情况时，让pre = cur,当前的cur = 1/*

2020-08-10 15:21:58 103

原创 93. 复原IP地址快乐暴力

93. 复原IP地址难度：中等面试oppo的时候有被问道这道题，不过没手撕，就是单纯的讲思路。当时就说的暴力三重循环，面试官也没说啥。今天居然出了每日一题~题目描述解题思路1、快乐暴力三重循环if else选手前来报道要排除掉001，01这样的影响，是不满足条件的/* * 93. 复原IP地址 * 2020/8/9 * 难度：中等 */ public List<String> restoreIpAddresse

2020-08-10 14:29:22 103

原创剑指 Offer 28. 对称的二叉树

剑指 Offer 28. 对称的二叉树难度：简单题目描述解题思路这个总结的好好啊左右子树同时等于空，说明匹配完成了，都一样；如果其中一个为空另外一个还没，说明没匹配上；如果都不为空，就判断对应的值是否相等，对应的值相等，再判断孩子是不是满足以上镜像条件 /* * 剑指 Offer 28. 对称的二叉树 * 2020/8/7 * 难度：简单 */ public boolean isSymmetric(TreeNode root) {

2020-08-07 10:26:47 113

原创剑指 Offer 26. 树的子结构

剑指 Offer 26. 树的子结构难度：中等题目描述解题思路也说不上来思路，反正就是递归，对于A的每个节点都判断能不能形成子结构B判断的时候递归终止条件是B是不是等于空，如果等于空说明全部匹配完了，如果B还不为空但是A已经空了，就说明没匹配上/* * 剑指 Offer 26. 树的子结构 * 2020/8/6 * 中等 */ public boolean isSubStructure(TreeNode A, TreeNode B) {

2020-08-06 14:51:45 100

原创面试题 04.10. 检查子树

面试题 04.10. 检查子树难度：中等题目描述解题思路在写剑指 Offer 26. 树的子结构的时候突然看到评论里有提到这道题，感觉思路差不多又有区别，所以就翻出来写了。最大的区别在于子结构和子树的定义差别子结构只要求一部分相同，只要B能匹配上A中的一部分就可以了子树要求的是从A里对应的B跟开始，一直到最后的叶子节点都要全部匹配所以在递归的时候可以先进行判断，如果两个全部都是空，那么说明匹配完成，如果其中一个是空而另外一个不是，则说明匹配不上。如果字符不相等，就递归的去判断左子树

2020-08-06 11:06:55 123

原创 336. 回文对暴力解法+前缀树

336. 回文对难度：困难题目描述解题思路1、万能暴力最直接的想法当然就是暴力法，嘿嘿，能过一大半/* * 336. 回文对 * *困难 * 2020/8/6 */ public List<List<Integer>> palindromePairs(String[] words) { int n = words.length; List<List<Integ

2020-08-06 10:19:45 141

空空如也

空空如也