当先锋百科网

首页 1 2 3 4 5 6 7

RU大神手册上要再“做”的题

?《》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
 
⚪️【靠背的】
 
 
 -------------------------
?《TREE》
?【知识点都不懂的】
  1.  segment tree：做了求sum那道题
⚫️【要新写的】
  1. tag 174：lca in bst: traverse
  2. pre order:有parent节点的 184
  3. tag kth smallest in bst: in-order recursive: https://leetcode.com/problems/kth-smallest-element-in-a-bst/discuss/63783/Two-Easiest-In-Order-Traverse-(Java)
  4. m no tag verify bst is pre-order: dc: 209 or https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/discuss/68139/Divide-Conquer-Java-Solution
  5. hard no tag 两个数放错了，recover bst：前序https://leetcode.com/problems/recover-binary-search-tree/discuss/32535/No-Fancy-Algorithm-just-Simple-and-Powerful-In-Order-Traversal
  6. m ms最大的bst子树：要传递的信息太多就自定义一个tuple 表示范围和尺寸 然后用一个点做参数 
    Result left = traverse(root.left);
    ：https://leetcode.com/problems/largest-bst-subtree/discuss/78891/Share-my-O(n)-Java-code-with-brief-explanation-and-comments 
  7. univalue:同上 tuple中包括value
  8. BT中的相同子树：要传递的信息太多就自定义一个tuple，相同的树用group id 表示
  9. m amz bt中从右边看过来的节点：bfs,依次看本节点 右节点 左节点 https://leetcode.com/problems/binary-tree-right-side-view/discuss/56076/Reverse-Level-Order-Traversal-java
  10. bt前序遍历拆成linkedlist：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/My-short-post-order-traversal-Java-solution-for-share ：定义一个prev节点，然后背
  11. 254把bt转为双向链表：用prev记录前一个节点，背
  12. m ms从前中、中后序遍历中构建bt：preorder决定root，inorder决定左右（dc）
  13. Unique Binary Search Trees II 就用dc构建二叉树就行了
  14. path sum 2输出等于路径和的数组：dfs（root.left起点，list过程，sum - root.val过程，ans结果） path sum 1是否有：dfs（root.left起点，curSum过程，targetSum结果）
  15. 298bt中的“最长连续路径”的长度：还是路径问题。dfs（root.left起点，root length过程，max结果）
  16. lintcode flatten list嵌套数组的展开/加权求和：DFS 是整数就添加 否则继续递归，用isinteger getinteger getlist方法
  17. 299上一题权重相反：要传递的信息太多就自定义一个tuple 表示sum和深度
  18. 310返回最小高度树的根节点：
⚪️【靠背的】
  1. 174：lca in bst: dc ：左右分开 谁不空返回谁
  2. preorder inorder的非递归 
  3. 三种顺序的dc和traverse 
  4. bt/bst中的中序后继：比root大时直接扔右边递归，比root小时 考虑是左边递归还是就是root
  5. vertical traversal：完全不知道怎么找出数学关系，找出变化关系：列数从小到大，同一列时行数从小到大，从左到右 BFS
  6. 198 max depth: recursive但是不在过程中+1，在结果+1 min depth：改成min 然后左边空了去右边 才满足depth要求 banlanced tree:左右是整数 差超过1就返回-1了
  7. 202距离目标节点最近的节点：定义一个res,如果root离target的距离小 就替换成为新的res 
  8. 204validate bst 直接在isvalidate函数中定义节点为空或者大小不对就行了
  9. 208Convert Sorted Array to bst 还是recursive，只不过recursive里创建treenode（mid mid+-1即可）
  10. same tree: 就用traverse判断都空/一空/左右都相等即可
  11. symmetric bt：想象图形：helper（l.l, r.r） && helper(l.r, r.l)
  12. 统计complete tree中的节点个数：用l = getHeight(root.l)统计各自的深度 再比较左右的关系
  13. bt的层遍历：取Queue的size,添加node的非空左右节点 不需要哈希查重/ recursive做法：先左后右 先上后下/从下到上：Collections.reverse
  14. 241bt的z型遍历：沿用q的bfs，通过normalOrder控制变量，来回交换，实现逆序
  15. 245连接右侧的下一位节点：用dummy node形成队列，右侧节点就对应linked list中的下一个节点
  16. bt upside down反转：反转链表4步翻转法基础上的6步翻转法
  17. bt的序列化&反序列化：用dfs-dc构建出左右节点
  18. BST中取值最近的节点：while(root != null)，尾递归root变成left或right
  19. bt中any to any距离最大：左端divide,右端divide，总体conquer相加
  20. 写出Binary Tree Paths：dfs（root.left起点，path+root.val+"->"过程，ans结果）
  21. bt中any 2 any，tuple中定义root 2 any & any 2 any，求两次
  22. 多层数组interator/BST iterator：用stack+中序遍历，next拿出来，hasnext放进去
  23. 融合二叉树：node.left = mergeTrees(t1.left, t2.left);

 

 -------------------------

?《图》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  310返回高度最小的树的根节点：BFS时每层添加叶子数=1的根节点，扩展添加-1后叶子数=1的根节点
  2. 无障碍的曼哈顿开会距离：结果位于所有点中间，收集所有‘1’的横坐标后逐渐检查，收集所有‘1’的纵坐标后逐渐检查
  3. 有障碍的曼哈顿开会距离：添加一个等于1的建筑，扩展添加=0且未访问过的路径，保证距离最短。
  4. 332机票排序：不是排序。遍历所有边是DFS，而且只走一次所以是欧拉回路。
  5. 329gg 矩阵中的最长递增路径（滑雪）：recursive四周扩散，用tempMax记录全局最大值。是dc，也是记忆化搜索。
 
⚪️【靠背的】
 
  1.  course shcedule：BFS时 每层添加先修课程数（入度）=0，扩展添加-1后（入度）=0的点，依次放入结果res中
  2. alien dictionary根据词语返回字典顺序：BFS时每层添加字母（入度）=0，扩展添加-1后（入度）=0的字母，依次放入结果res中
  3. 261. Graph Valid Tree树中是否有环：添加第一个点，扩展添加邻居节点，如果访问过 visited[cur]==1就不行
  4. 133clone graph：先BFS克隆点(一个点+扩展所有邻居)，再克隆邻居(一个点+扩展所有邻居)。
  5. 每个房间到门的最短距离：转成单起点，所有门先进q，扩展添加四周空房间，已有房间数+1。
  6. 286中央岛屿注水：转成四周注水，所有盆地先进q，扩展添加四周盆地，可被注水则变回X。

--------------------------------------------------------------------------

 

?《搜索》

?【知识点都不懂的】
  1.  
⚪️【靠背的】
  1.  lintcode 指定上限和个数的combination：i = prev + 1，递归中只考虑比上一层递增的值，从而去重
  2. 78subsets没有重复元素的所有子集：不管remain，都要add到tempList中去。没有重复：相同的数continue调。
  3. PDF19页 permutations没有重复的：涉及所有元素，不传idx。定义用过就退出的规则、用过、DFS、没用过。有重复的：相同的数字放在同一个DFS中
  4. https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)
  5.  Combination Sum:
  6.  6.Palindrome Partitioning:先写个判断回2文串基本函数，再从startIndex新切字符串来回溯出所有解法。 
    String sb = s.substring(startIndex, i + 1);
  7. N皇后：需要判断行列的和差是否符合不碰撞的要求，再用col进行dfs。第二题：行列的和差不能重复出现，还是backtracing，计数就行。
  8. word search：vistied true- 四周扩展是否返回true - vistied false 返回存在的单词：已有单词建trie树，四周扩展 看是否存在
  9. 电话号码的数字组合：for遍历字符串数组phone[d]中的字母c来进行DFS
  10. 494在一堆1中加符号凑成和：就是最一般的dfs(sum+nums[pos]或者sum-nums[pos])
  11. 282在一堆数中加符号凑成结果：就是最一般的dfs(sum+nums[pos]或者sum-nums[pos])，乘法用lastF记录最后状态
  12. 1矩阵被2染色：四周dfs，sr+-1 sc+-1
  13. 695最大的岛屿面积：就是最一般的dfs(i+-1)或者dfs(j+-1),返回1+四个方向的dfs
  14. 200岛屿的个数：四周dfs完了之后，岛屿个数计为1 添加岛屿：用union find，合并后count-1
  15. 20判断括号的匹配性：stack中有左就有右，有右就对比
  16. 301去除不匹配的括号：通过）（用不用 调节dfs中的L R参数
  17. word ladder1返回经历的最少单词数：bfs(所有能变出来的单词)，在字典中的进q
  18. Strobogrammatic Number2 给出指定长度：iterative每一位 举例11 69 88找出所有对称情况
  19. Strobogrammatic Number3 给出上下限范围：讨论出所有长度 recursive 列出69 88 11所有对称情况
  20. word pattern单词串匹配字符串：map.put(word, i) vs map.put(char, i) isomorphic string：m1[a] = m2[p] = 3，相同字母角标要相同，用了.split()
  21. gg flip game++变-- 翻一次：arr[i][i+1] = '-',add char,arr[i][i+1] = '+' 。翻多次：中间加个canWin就break
⚫️【要新写的】
  1. 36输入已有的数独 看discuss：双重循环 每个格子过一遍，分别在rows,cols,cubes三个hashset中判断存在性
  2. 37求出所有数独的解：开三个数组rows[i][num] cols[i][num] blocks[i][num]同时限制，做backtracing
  3. 2.22给出数字 产生所有匹配括号的情况：dfs的string中直接加）（
  4. 93产生IP地址：三个点分别枚举123位数，再拼接所有情况
  5.  word ladder2:返回所有可行的路径：BFS最短+DFS求所有路径。
  6. 351手机解锁：返回路径中跳过的元素分几类 所以分别用backtracking，不用dp
  7. 320产生全部压缩字符串组合w2d：对每个字母，分为拿的recursion和不拿的recursion
  8. uber dropbox hard word pattern2无空格：map.put-dfs(str.subsrting(j+1))-map.remove调整得出匹配长度
  9. 824山羊拉丁文：用.split("\\s")分开单词，用+=连接新单词

---------------------------

 

?《动态规划》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  364house robber2首尾相连：（1（759）2）分别从第0、1位开始，即可覆盖全部
  2. 368二叉树上的house robber3: 计算奇葩值用dc: max(left+right, subleft+subright+val)
  3. gg 375猜数字2:tmp = x + Math.max(DP(t, s, x
  4. sum[j][i] = a[j]+sum[j+1][i]
  5. left=dp(start, i - 1), right = dp(i+1,end) 和cur相乘积最大
  6. 比较，global和local[i]比较
  7. ,然后都取反
  8. 存起来
  9. ，localMax[i][j]表示j组中第i个必须取，依次循环到n k
  10. 求2个不重叠子数组 差的绝对值最大：左右依次存leftmax leftmin，|leftmax-rightmin|作差用记忆化搜索存起来
  11. 442one edit distance：第一串.substring(删一位用i+1)，增一位和对方（i+1）比较
  12. edit distance最少编辑次数：次数都减1。不变/替换时dp[i][j]继承之前的dp[i-1][j-1]，dp[i-1][j]+1代表多编辑一步
  13. 447形成palindrome（i到j）的最少插入次数：回文看两边。不变/替换时dp[i][j]继承之前的dp[i-1][j+1]，dp[i-1][j]+1代表多编辑一步。
  14. 一堆公司 h word break2找出所有空格插入的方式：DFS搜出所有单词，暂存，再DFS组合。
  15. 97h 判断s1 s2是否能交错形成s3：dp[i-1][j]管c1 c3匹配，dp[i][j-1]管c2 c3匹配
  16. 背包基础 无价值不重复限制位置 ：数组A[],凑出目标m: dp[现实][目标值] ,循环中目标j-实际A[i-1]要>=0
  17. 有价值数组的背包：dp[现实][目标值] dp[i][j] = Math.max(dp[(i-
  18. 。dp[j] = max(dp[j], dp[j-v[i]] + v[i])
  19. 要+1
  20. n元素中取k个，指定sum：dp[总数量][当前位置][求和]，要求目标t >= 实际值A[i -
 
⚪️【靠背的】
  1.  362house robber1 只和前2个状态有关，都mod2 可以省空间：f[i % 2] = Math.max(f[(i - 1) % 2], f[(i - 2) % 2] + A[i - 1]);
  2. 涂色：k色，最多2个相邻：dp[n-1] dp[n-2]都直接减少到只有k-1色：dp[i%3] = (k-1)*max(dp[(i - 1)%3], dp[(i - 2)%3])
  3. 涂色：3色，最多1个相邻：枚举
  4. 涂色，k色，最多1个相邻：dp[i][j] = Math.min(dp[i][j], dp[i - 1][s] + costs[i][j]) ，先涂成s色，再加当前的cost[i][j]
  5. unique path1：标准坐标型 按方向分类 从上来或从左来 paths[i][j] = paths[i - 1][j] + paths[i][j - 1]; unique path2：obstacle[i][j] != 1时同上，否则path[i][j] 变成0
  6.  左上角到右下角的最短路径：标准坐标型 f[i][j] = grid[i][j] + Math.min(f[i - 1][j],f[i][j - 1]);返回f[m-1][n-1]
  7. maximal square：状态转移公式是向三个方向往回拓展：f[i % 2][j] = 1 + Math.min(f[(i - 1) % 2][j],Math.min(f[i % 2][j - 1], f[(i - 1) % 2][j - 1])); maximal rectan:用单调栈掐出来histogram
  8. 674最长连续递增子数组：maxHere递增就+1，不递增就是1 
  9. palindrome2每个子串都是回文串的最少分割次数：串的区间是j到i f[i] = Math.min(f[i], f[j] + 1);
  10. 买卖股票问题：买=max（不买，赔钱）；卖=max(不卖，赚钱)
  11. 最长公共字符串LCSC：标准双序列：匹配就dp[i-1][j-1]+1,不匹配就取Max（dp[i-1][j]，dp[i][j-1]）
  12. 44wildcard一位和多位matching：s和p一位对一位时dp[i][j]继承之前的dp[i-1][j-1]，dp[i-1][j] s退一位也能比，说明匹配了很多位
  13. regular expression一位和多位之前的matching：dp[i][j-1]匹配了p的一位，dp[i][j-2]不正常没匹配，dp[i-1][j] s退一位也能比，说明匹配了很多位
  14. word break切分单词是否在字典中：for循环0-j-i,两段都在才返回true，优化空间：只存0到i，化成一维数组
  -------------------------

 

 

?《string》

 

?【知识点都不懂的】

 

  1. KMP 214成为回文串添加的最少字符数：自制回文串，返回KMP共有长度表的最后一位（移动位数=已匹配值-部分匹配值）

 

⚫️【要新写的】

 

  1.  151翻转句子中的单词顺序：新三步-翻句子，翻单词，清空格
  2. 186打碎成字母后翻转：新三步-翻句子，翻单词，翻最后一个
  3. 39把前面揪下来的翻数组：老三步-翻前面，翻后面，翻全部

 

⚪️【靠背的】

  1. 3最长的无重复字母的字符串：把能出现的最长串存在map里
  2. 409最长回文串：set中存储之后，重复就remove。用count*2+1返回最大长度。
  3. 5求一串中最长的回文串：写个extendPalindrome(s, i, i)扩展奇数长度串，extendPalindrome(s, i, i+1)扩展偶数长度串
  4. 125有大小写、空格的句子是不是回文串：!Character.isLetterOrDigit(cHead)不是字母就跳过，Character.toLowerCase(cHead)小写字母不想等就返回false
  5. 266排列能否构成palindrome：set统计单个字母，超过一个就不行
  6. 267排列输出所有palindrome：取出map中一半的字母，用deleteCharAt（i）做permutation
  7. 14最长的公共字符串开头：若strs[i].indexOf(pre) ！= 0，则有此前缀。这是判断前缀的新方法。
  8. 520判断单词是否大写开头：用word.toCharArray()全转成字符，word.charAt(0)判断第一个字母
  9. 443字符串相同数字个数统计：用.valueOf(count)计数，char[start++]=arrs[i++]两边同时赋值加
  10. 345翻转元音字符：s.toCharArray()转数组，start++ end--往中间换
  11. 383字典数组中找笔记数组：.toCharArray()转数组，magazine c++, note c--，最终检查是否为0
  12. 273数字转为单词：10，20，100以下单独列，其他直接连接"thousand"/"hundred" 13罗马字转整数：switch case各个字母，返回数字 整数转罗马字：(n / 1000) % 10 先取数，然后建立M C X I各位数组
  13. 551学生出勤字符串：直接不能.contains(LLL)
  14. 535压缩字符串：String.valueOf(urls.size() - 1)形成新的字符串  恢复字符串 urls.get(index)从存储结构中取出来
  15. 171excel字母转数字：26进位，s.charAt(i) - 'A' + 1可以把大写字母转数字
  16. 408验证w3c的有效性：i和j共同比，用Integer.valueOf(abbr.substring(start, j)切出数字
  17. 680能否通过删除字母构成回文串：删除其实就是跳过一位，isPalindrome(s, l - 1, r) || isPalindrome(s, l, r + 1)，然后继续traverse
 

   -------------------------

 

?《binary search》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  154找有重复rotated sorted array中的最小值：无重复的方法依然成立，a[mid]=a[right]时，right重复了 往左挪一格
  2. 354俄罗斯套娃的数量：二分查找当前套娃的位置pos,如果比index大就加1
 
⚪️【靠背的】
  1. 240不严格递增的2维矩阵搜索：无法二分，从左下角开始可控制一加一减，x-- or y ++ or count++
  2. 34search for a range: start是原点可找出boud[0]，start是终点可找出bound[1]
  3. 278first bad version：把判断条件换成isBadVersion(mid) 就行了
  4. 35返回索引值或插入索引值：找个范围，然后返回区间的左、中、右
  5. 33 search in a rotated sorted array: 分为nums[mid]大于和小于nums[start]两种情况，确定之后再二分。恢复：老三步-之前、剩下、整体的。
  6. 153找无重复rotated sorted array中的最小值：画图，根据中点落点的位置继续下一步二分。
  7. 找峰值：起点是1，终点是len - 2，然后就可以根据a[mid +- 1]的关系进行查找了 
  8. 4要求用二分法的两个数组的中位数：如果A_key < B_key，强行丢掉A的前一半 没用，traverse的起点变成A_start + k / 2
  9. 用-1 0 1 猜数字：模版二-不重合所以left<right,比较右邻居left= mid+1,最后比较得出一个相等值left==right
  10. 744找出比目标字母大的最小字母：模版二-最终只找一个字母。target < letters[mid]字母可以直接比较。
  11. 410论文引用量：模板一，left <= right，用citations[mid] == n - mid找，最后返回n-start
 
-------------------------

 

?《stack》

 

?【知识点都不懂的】

 

  1.  

 

⚫️【要新写的】

 

  1.  

 

 

 

⚪️【靠背的】
  1.  支持push pop min操作的stack：用一个minstack来辅助实现。
  2. 在nums2中找出比nums1更大的元素：有大小关系就将元素按从小到大存在单调栈stack中，对应关系存在hashmap中。
  3. 85求最大的由1构成的矩形的大小：矩形就类似histogram，用stack挤出来
  4. 636进程执行时间：更新结果数组、更新设置的起点preTime、更新stack
  5. 682字符串处理棒球分数：pop出temp1 temp2来进行加减操作
  6. 20检验括号匹配的有效性：进左就进右，进右就检验

-------------------------

 

?《括号类》

 

?【知识点都不懂的】

 

  1.  

 

⚫️【要新写的】

 

  1. 返回算式中所有添加括号得到的运算值：用dc避免重复结果。0-i的list划为left, i+1 以后划为right，然后枚举。
  2. 754页 最长的有效括号的长度：dp[i]表示以i结尾的最长括号的长度，(为0。)和上一个有效元素leftPos是（时+2
  3. 224计算器 有无空格的算式输出运算结果：用SY和RPN算法，就是先存stack，再pop两个数出来运算。

 

⚪️【靠背的】
 

------------------------- 

?《设计实现数据结构 & Iterator类》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  z字型iterator：用两个list交换顺序实现
  2. 284取next&peek的Iterator：用一个Iterator<Integer>来调用自己的API
  3. 251二维数组转成一维Iterator：用一个Iterator<List<Integer>>来调用自己的API
  4. 341flatten nested多重数组：NestedInteger是一种类型的数据，用它的stack来实现
  5. 嵌套列表加权求和 括号多的权重大：traverse中depth加1就行了helper(e.getList(), depth + 1) 括号少的权重大：按变量分为是否unweighted，用list实现
  6. 173BST iterator：内部用stack做中序遍历来实现
  7. 779页BST 后序遍历iterator：用stack+cur+prev附加2个指针来实现
  8. LRU cache：通过双向链表+hashmap，实现get set move_to_tail三个函数
  9. 295find median from data stream：小数放maxheap，大数放minheap，调整peek作为中点
  10. 239Sliding Window Maximum用双向队列取出第一个值、最后一个值来做
  11. 380增加、删除和产生随机数（不重复）：用数组nums, 一个map，和rand.nextInt(nums.size()来产生。有重复：加一个布尔型contain变量即可。
  12. 389找出s-t乱序后的插入字母：字母数字互相联系的题，用alpha[t.charAt(i) - 'a']++控制有无
 
⚪️【靠背的】
 
------------------------- 

?《随机数类》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  面筋blacklist出现过的元素需要剔除：用rand随机生成index，然后维护一个list
  2. 蓄水池采样算法：result[r] = pool[i]，从而保证第k+1个元素被抽中的概率也是k/n
  3. 382随机返回链表节点：cur节点非空时，产生随机数，用cur = cur.next一直迭代
 
⚪️【靠背的】
 
 ------------------------- 

?《OOD算法题》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
 
⚪️【靠背的】 
  1. 359十秒计数器 十秒内不允许重复出现单词：当timestamp - map.get(message)) >= 10时存hashmap
  2. 362hit counter返回五分钟内的敲打次数：用times[i] hits[i]数组实现
  3. 348设计Tic-Tac-Toe：用rows cols数组添加元素
  4. 353snake game贪食蛇：用二维数组[][] food
  5. 355设计推特：用pq<twitter>来设计newsfeed
  6. 379设计电话目录本：用q和set
  7. 158从文件中调用字符-多次:一次只能调用4个字符，用大小为4的buffer[]暂存
 ------------------------- 

?《两个指针》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1. 字符串小写在前、大写在后：Character.isLowerCase(chars[i]) 时i++,Character.isUpperCase(chars[j])时j--，否则交换
  2.  wiggle sort1 相邻元素可以相等：用boolean变量findbigger控制，小于换一次，大于再换一次 wiggle sort2 相邻元素不能相等：变index 然后用partition
  3. gg hard:包含2/k个不同字母的最长子串覆盖 ：窗口一直右移，所以是前向窗口型。
 
⚪️【靠背的】
  1.  2sum3sum4sumksum：n-2层循环，剩下的left/right做指针对撞。
  2. 2sum 等于目标值的对数：一旦等于目标值就left++ right--，同时count++，多线程并行。
  3. 2sum 小于等于目标值的对数：一旦求和大于target就全加上cnt += right - left，然后right再减
  4. 2sum closest返回和target最接近的sum：放在全局变量diff中，小了就left++，大了就right--。
  5. 3sum closest返回和target最接近的sum：放在全局变量bestSum中，小了就left++，大了就right--。
  6. 3sum smaller返回比target小的所有对数：right--初始化到sum较小，count+=(right-left),最后用left++微调。
  7. 4sum两两求和：枚举所有，a[i]+b[j]在map中存一次，map中c[p]+d[q]取一次
  8. 11用高度数组表示装最多水的容器：水往低处流，指针往高处走。如果height[right] > height[left]就left++
  9. trapping water平面版：如果height[right] > height[left]就left++，长高后灌水result += (left_max - heights[left])；从右往左是变矮后灌水
  10. trapping water立体版：从低往高注水，BFS的q中扩展四周更高的高度，越往外越高才能积水
  11. 快速排序：设区间为j-i，小于j的在左边traverse，大于i的在右边traverse.二维不严格递增矩阵版：target换成matrix[left/rows][left%rows]即可
  12. 快速选择：为了选择，每次丢一半，T(N) =n +n/2+n/4+n/8+n/2^k = n*(1-2^-k)/(1-2^-1) =2N
  13. 基于quicksort的划分数组：双色：就是指针对撞复杂度为n，三色：nums[left] 和1比较时qs一次，nums[left] 和2比较时qs一次，k色：用traverse 颜色和index同时做参数 rainbowSort(colors, left, right, colors_left, colors_right)
  14. 和 ≥ s 的最小长度子数组，和《s时j++，达到后更新j-i。再扫更大，所以此处打止。每次清空nums[i]不再用。（j不用回去，否则会变成原来的i）。绝对值差为k的数组对数：排序后，j从i开始且不用回去，否则差更小，且会变成原来的i。
  15.  3最长的无重复字符的子串：出现过的字符j，用map[256 s.charAt(j)] == 1标记即可
  16. minimum window substring最小子串覆盖 EBANC中找ABC: 窗口一直右移，所以是前向窗口型。256中每个字母都要更多，sourcehash[i] < targethash[i]时为false。
  17. 217index相隔为k的重复元素：i超过k后，把最后一位nums[i - k - 1]删掉，维持一个k长区间，set中加不进nums[i]则说明重复


 ------------------------- 

?《linked list》

 

?【知识点都不懂的】

 

  1.  

 

⚫️【要新写的】
  1. 237删除链表中的某个node：删除一个node就是跳过它：dummy.next.val = node.next.val。然后继续往后移，因为可能有别的node。 

 

⚪️【靠背的】

 

  1.  翻转全部链表：prev=null，temp = head.next，三步换完之后还是返回prev 就是不用dummy。翻转第m-n个节点：转完后要再连起来。
  2. 从后往前删除第n个元素：慢指针后走x-n,自动剩下n
  3. 两个链表的交叉节点：把不一样长的length剪掉，再同时开始找
  4. 判断回文链表：把后半部分逆过来，再p1.val == p2.val走到头
  5. 合并k个排序链表：写一个node的comparator，然后把链表都放进heap里
  6. 给乱序的链表排序：先把reverse(mid.next)存在right中，把后半截删掉，再merge(head, right)

------------------------- 

?《hash》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
 
⚪️【靠背的】
  1. 690[[1, 5, [2, 3]]输出所有直属员工的重要性之和：每个员工存hashmap后，枚举一遍for (int subordinate : root.subordinates)，直接用就行
  2. 447求[[0,0],[1,0],[2,0]]i-j距离等于i-k的回力镖组数：map中存（距离，次数），组合数公式=次数*（次数-1）
  3. 49乱序词合并：字符串转chars[]数组，排序数组arrays，再转回string。hashmap存（anagram, 所有str）
  4. 128最长连续子序列：看似不难但是有trick，map中存(n,sum)，取sum=left + right +
  5. 统计种类，小于糖果数一半就返回
  6. 266随便重排后是否构成pldr：没出现过就add,重复就remove，看最后剩余个数是否为0/1
  7. 734有字典数组的相似句子：看map.get(word1)的set是否包含word2，反之亦然
  8. 第一个独特字符的位置：先统计，看哪个index的数量第一个为1即可 cnt[c[i]] == 1
  9. 返回substring中anagram的坐标：窗口型。往右时cnt[r++]，cnt[l--],det差值数组同样
  10. 205egg和add的对应位匹配：循环一遍，看m1[256]的i和m2[256]的i是否相等

-------------------------

?《array》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
 
⚪️【靠背的】
  1. intersection相同元素出现一次：用temp数组控制。多次：hashmap(n,count-1)
  2. 645挑出重复元素和正确元素:数字游戏nums[num - 1] * （-1）
  3. 507 2-根号n的因数求和：直接加到sum上，不开数组，省空间
  4. 624最大距离差：用get(n-1)做最大最小值互相减。118杨辉三角形：先后添加get(n-1)
  5. merge有无空位：都是尾插
  6. 661中和色阶：冒号表达式列举r、c是{-1, 0, 1}
  7. 566矩阵元素重排：result[row][col] = nums[i][j]，先col++，满了之后再row++
  8. 747第二大元素 不准排序：直接放Max1 Max2
  9. 283把0元素放在最后：非零位直接正常添加：nums[insertPos++] = num
  10. 243字符串数组中最短的单词index之差：都初始化为-1，找到p1 p2后再作差
  11. 665只允许修改一位的非递减数组：数学游戏，酌情修改谁
  12. 717由0/10/11组成的数字：是0就加一，否则加二，最后check i 是否等于 n - 1
  13. 605[1,0,0,0,1]数组之间种n朵花：prev是数组flowerbed[i - 1]本身，next是0，两者都为0才能种花flowerbed[i] = 1
  14. 303范围求和：做差法sum[j] - sum[i]，省时间
  15. 485最长的连续为1的个数：是1时maxHere就加一
  16. 238数组中除开自己以外的元素乘积：从左往右累乘一遍存res[i]，从右往左再乘一遍
  17. 334是否存在三元上升的序列：存n,max,min, 三者满了就行
  -------------------------

?《扫描线》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
  1.  370. Range Addition 用[1, 3, 2]表示对数组的操作，要求返回最终结果：k步影响首尾，n位影响中间。分开操作复杂度是n+k
  2. gg m 228. Summary Ranges合并区间0,1,2变成0，2:开始设start=end,nums[i] = end + 1的话end++
  3. 163. Missing Ranges返回0, 1, 3中缺失的区间2:维护lower、high、n之间的关系，通过lower右移推进
  4. 352Disjoint Intervals返回1, 3, 7, 2, 6产生的所有可能区间：用tree维持大小关系，l h元素排序
 
⚪️【靠背的】
 
  1.  253会议室1 能否开会：直接.start来用 intervals[i + 1].start < intervals[i].end。几间房：存heap。617页重合最多的区间：存最大的start&最小的end
  2. merge interval：用lambda表达式比较快 直接(i -> i.start),复杂度nlgn。insert interval 复杂度+n
  3. 天际线：用pq

  -------------------------

?《trie & union find》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
⚪️【靠背的】
  1. 实现trie树：用数组 children[pos].insert(word, index + 1)
  2. add&search word：对now节点的children[i]进行操作
  3. 岛屿数量2:给出二维数组的岛屿坐标，返回岛屿数量：动态添加。根据范围，0<x<m时要合并，0<y<n时也要合并
  4. graph valid tree图是不是树：用uf遍历所有边并且缩点，一旦出现公共祖先就退出。

     

 ------------------------- 
 

?《PQ》

?【知识点都不懂的】
  1.  
⚫️【要新写的】
 
 
⚪️【靠背的】
  1.  263 是不是235构成的丑数：除以235看最后是否为1 第n大的丑数：235不重复的放在set中，总体维持大小为n的pq 给定因数的第n大丑数：用ugly[times[j]]数组表示相乘的次数
  2. 前k频繁单词：存的是pair,不是单词

 ------------------------- 

 

?《不包括7/29》

 

?【知识点都不懂的】

 

  1.  

 

⚫️【要新写的】

 

   

 

⚪️【靠背的】

 

  1.  按照点添加的并查集 求岛：由root找next_id，由next_id找real_root（三连击），然后一言不合就合并。
  2. 323按照线段添加的并查集 求岛：每次更新的都是roots数组，把新的root指定给roots数组中的元素
  3. graph valid tree图是否是树：添加每一条边 root1 == root0代表有环，不行。count > 1代表分块，不行

  4. Decode String 解码icc字符串3[i2[c]]：nested用字母数组2个stack，左括号就之前的不加了，右括号就开始append求和

  5. 384. Shuffle an Array数组洗牌：random出j，nums[i] [j]交换即可

  6. 149. Max Points on a Line同一条线上的最多点数：分子分母同时约分掉gcd之后，用双重hashmap存储（x,(y,次数)）

  7. 65. Valid Number 判断字符串是不是数字：e之前必须有数，之后nseen重置为0

  8. 152. Maximum Product Subarray最大乘积子数组/是否连续：A[i]保证二者之间相对较大，只能保证负号之前的局部最优解

  9. 150. Evaluate Reverse Polish Notation逆波兰表达式：用stack，注意一下：先pop出来的是晚进去的。a-b a/b都当作b。

  10. 187. Repeated DNA Sequences重复的DNA子串序列：set的判断语句 没加就自己自动加 没必要再写一遍

  11. 244. Shortest Word Distance II 实现数组中的最短距离单词：找到之后index1 - index2，然后i/j中较小的只走一个

  12. 698. Partition to K Equal Sum Subsets 数组分成和相同的k组：dfs找到k组之后，继续找k - 1 组，变量变化之后就要控制它的最后值 是否为0或1 

  13. 156. Binary Tree Upside Down反转二叉树：六步里面：temp节点存起来，传递给cur.left

  14. 364. Nested List Weight Sum II 大小反向的括号加权求和：每一层剥皮的时候，把剩下的都加进去，用array的.addAll(ni.getList())方法

  15. 515. Find Largest Value in Each Tree Row查找一行中的最大值：其中q每次只存了一行，所以size就是当前数组的大小

  16. 716. Max Stack实现一个最大stack：stack maxstack必须要保持相同的长度，功能就是维持最大值而已

  17. 366. Find Leaves of Binary Tree输出层数相同的叶子节点：res.get(level).add(node.val)可以实现精确添加，指定哪一层添加哪个数

  18. 254. Factor Combinations 返回所有因数组合：退出条件是n<= 1就肯定要用return退出，是否添加取决于item的size是否大于而不是等于1

  19. 245. Shortest Word Distance III 单词可以重复的最短单词距离：p1 p2相等的时候，暂存一下之前的p1 = p2; p2 = i;

  20. 8. String to Integer (atoi) 字符串转成整数：先设置一个bound变量，-2147483648/10。当前num > bound || num == bond & digit > 7都不行

  21. 22. Generate Parentheses产生所有匹配括号的方案：定义open和close整数，分open < max 和close < open两个阶段来回溯

 

 

转载于:https://www.cnblogs.com/immiao0319/p/9154398.html