lintcode解题记录

本文章是一个系列,主要记录自己解算法题的一个记录,每道题会出一篇解题报告,作为自己算法功底的沉淀。每次迭代全部从头开始,并且记录以日期。

下面记录的必须在ide和lintcode上提交过,并且写过代码的。

解题七步曲:1 倾听问题,2样本确认, 3 动口不动手的暴力天然解, 4 动口也动手的最优解,5 路演你的思路,6 结构化的编码,7 单元测试

我的笔记:here (复习时候,刷这个效率更高)

我AC的题目:here

No Problem Describe Type Diffculty Note Date1 Date2 Date3
1 13-implement-strstr 字符串查找 string Easy 2020/6/19
2 594-strstr-ii 字符串查找 II hash,kmp Hard 2020/6/19
3 17-subsets 子集(无重复) combination,dfs Medium 2020/6/19
4 18-subsets-ii 子集 II(有重复) dfs,backtracking Medium 2020/6/19
5 1361-text-justification 文字并排 simulation Hard 2020/6/19
6 38-search-a-2d-matrix-ii 搜索二维矩阵 II sort-matrix Medium 2020/6/19
7 39-recover-rotated-sorted-array 恢复旋转排序数组 sort-array Easy 2020/6/19
8 573-build-post-office-ii 邮局的建立 II bfs Medium 2020/6/21
9 616-course-schedule-ii 安排课程 bfs,topological-sort Medium 2020/6/21
10 598-zombie-in-matrix 僵尸矩阵 bfs Medium 2020/6/21
11 127-topological-sorting 拓扑排序 bfs or dfs Medium 2020/6/21
12 433-number-of-islands 岛屿的个数 bfs or union-find Easy 2020/6/21
13 677-number-of-big-islands 大岛的数量 bfs Medium 2020/6/22
14 109-triangle 数字三角形 dp,坐标型 Medium 2020/6/22
15 110-minimum-path-sum 最小路径和 dp Easy 2020/6/22
16 114-unique-paths 不同的路径 dp,坐标型号dp Easy 2020/6/22
17 99-reorder-list 重排链表 LinkedList Medium 2020/6/22
18 174-remove-nth-node-from-end-of-list 删除链表中倒数第n个节点 LinkedList Easy 2020/6/23
19 102-linked-list-cycle 带环链表 LinkedList Medium 2020/6/23
20 103-linked-list-cycle-ii 带环链表 返回环起点值 LinkedList Hard 2020/6/23
21 104-merge-k-sorted-lists 合并k个排序链表 LinkedList Medium 2020/6/23
22 105-copy-list-with-random-pointer 复制带随机指针的链表 LinkedList Medium 2020/6/23
23 106-convert-sorted-list-to-binary-search-tree 有序链表转换为二叉搜索树 LinkedList Medium 2020/6/23
24 177-convert-sorted-array-to-binary-search-tree-with-minimal-height 把排序数组转换为高度最小的二叉搜索树 LinkedList Easy 2020/6/23
25 74 first-bad-version 第一个错误的代码版本 binarysearch Medium 2020/6/24
26 1496 implement-rand10-using-rand7 用Rand7()实现Rand10() simulation Medium 2020/6/24
27 66 binary-tree-preorder-traversal 二叉树的前序遍历 Tree,recursion and iteration(Stack) Easy 2020/6/24
28 67 binary-tree-inorder-traversal 二叉树的中序遍历 Tree,recursion and iteration(Stack) Easy 2020/6/24
29 68 binary-tree-postorder-traversal 二叉树的后序遍历 Tree,recursion and iteration(Stack) Easy 2020/6/24
30 86 binary-search-tree-iterator 二叉查找树迭代器 Tree Hard 2020/6/24
31 97 maximum-depth-of-binary-tree 二叉树的最大深度 DC Easy 2020/6/24
32 93 balanced-binary-tree 是否是平衡二叉树 DC,Recursion Easy 2020/6/24
33 31 partition-array 数组划分 Array,Quick Sort,Two Pointer Medium 2020/6/25
34 94 binary-tree-maximum-path-sum 二叉树中的最大路径和 DC Medium 2020/6/25
35 88 lowest-common-ancestor-of-a-binary-tree 最近公共祖先(LCA) DC,RE,LCA Medium 2020/6/25
36 69 binary-tree-level-order-traversal 二叉树的层次遍历 BFS,Queue Easy 2020/6/25
37 70 binary-tree-level-order-traversal-ii 二叉树的层次遍历 II BFS Medium 2020/6/25
38 95 validate-binary-search-tree 验证二叉查找树 traversal Medium 2020/6/25
39 85 insert-node-in-a-binary-search-tree 在二叉查找树中插入节点 BST,分治 Medium 2020/6/25
40 86 binary-search-tree-iterator 在二叉查找树中插入节点 BST,分治 Hard 2020/6/25
41 87 remove-node-in-binary-search-tree 删除二叉查找树的节点 BST,分治 Hard 2020/6/25
42 11 search-range-in-binary-search-tree 二叉查找树中搜索区间 tree-traversal Medium 2020/6/25
42 12 min-stack 最小栈 stack,Simulation Medium 2020/6/25
43 40 implement-queue-by-two-stacks 双栈实现队列 stack,Simulation Medium 2020/6/25
44 494-implement-stack-by-two-queues 双队列实现栈 queue Medium 2020/6/25
45 130 heapify 堆化 heap Medium 2020/6/25
46 158 valid-anagram 两个字符串是变位词 string,map Easy 2020/6/26
47 122 largest-rectangle-in-histogram 直方图最大矩形覆盖 monotonic stack Hard 2020/6/26
48 126-max-tree 最大树 monotonic stack Hard 2020/6/26
49 134-lru cache LRU缓存策略 hash Hard 2020/6/26
50 24-lfu cache LFU缓存 hash Hard 2020/6/26
51 129-rehashing 重哈希 hash Medium 2020/6/26
52 171-anagrams 变位词 hash Medium 2020/6/26
53 138-subarray-sum 子数组之和 hash,前缀和 Easy 2020/6/26
54 124-longest-consecutive-sequence 最长连续序列 hash Medium 2020/6/26 2021/2/13
55 81-find-median-from-data-stream 数据流中位数 heap Hard 2020/6/26
56 132-word-search-ii 单词搜索 II trie Hard 2020/6/26
57 442-implement-trie-prefix-tree 实现 Trie(前缀树) trie 2020/6/27
58 61-search-for-a-range 搜索区间(对比138) binarysearch Medium 2020/6/27 2021/2/13
59 60-search-insert-position 搜索插入位置 binarysearch Easy 2020/6/27
60 28-search-a-2d-matrix 搜索二维矩阵 binarysearch Easy 2020/6/27
61 75-find-peak-element 寻找峰值 binarysearch Medium 2020/6/27
62 62-search-in-rotated-sorted-array(无重复) 搜索旋转排序数组 binarysearch Medium 2020/6/27
63 63-search-in-rotated-sorted-array-ii(有重复) 搜索旋转排序数组 62 follow up Medium 2020/6/27
64 6-merge-two-sorted-arrays 合并排序数组 II Two Pointers Easy 2020/6/27
65 64-merge-sorted-array 合并排序数组 Two Pointers Easy 2020/6/27
66 159-find-minimum-in-rotated-sorted-array 寻找旋转排序数组中的最小值(无重复) binarysearch Medium 2020/6/27
67 160-find-minimum-in-rotated-sorted-array-ii 寻找旋转排序数组中的最小值(有重复) binarysearch Medium 2020/6/27
68 65-median-of-two-sorted-arrays 两个排序数组的中位数 binarysearch,FindKMax Hard 2020/6/27
69 8-rotate-string 旋转字符串 string,simulation,三步翻转法 Easy 2020/6/27
70 53-reverse-words-in-a-string 翻转字符串中的单词 string Easy 2020/6/27
71 241-string-to-integer 转换字符串到整数 string Easy 2020/6/28
72 1510-buddy-strings 亲密字符串 string Easy 2020/6/28
73 415-valid-palindrome 有效回文串 string,双指针 Medium 2020/6/28
74 767-reverse-array 翻转数组 string,reverse Easy 2020/6/28
75 1283-reverse-string 翻转字符串 string,reverse Easy 2020/6/28
76 78-longest-common-prefix 最长公共前缀 (LCP) string。Simulation Medium 2020/6/28
77 1263-is-subsequence 是子序列吗 string,Simulation Medium 2020/6/28
78 384-longest-substring-without-repeating-characters 最长无重复字符的子串 string,two pointer Medium 2020/6/29 2021/2/14
79 213-string-compression 字符串压缩 string Easy 2020/6/29
80 1352-compare-version-numbers 比较版本号 string Medium 2020/6/29
81 1542-nexttime-norepeat 下一个不重复的时间 string Medium 2020/6/29
82 192-wildcard-matching 通配符匹配 string,DFS Hard 2020/6/30
83 98-sort-list(排序链表) 链表排序(归并和快速) sort Medium 2020/6/30
84 463-sort-integers 整数排序 sort【直接选择(选择),冒泡排序(交换),直接插入排序(插入)】 Native 简单排序 2020/6/30
85 464-sort-integers-ii 整数排序2 sort【堆排序(选择),快排(交换),归并排序(归并)】 Medium 分治排序 2020/6/30
86 136-palindrome-partitioning 分割回文串 组合型DFS+Backtracking Medium 2020/7/1
87 77-longest-common-subsequence 最长公共子序列(LCS) match-dp Medium 2020/7/2
88 79-longest-common-substring 最长公共子串(LCS) Two Sequences DP Medium 2020/7/2
89 680-spilt-string 分割字符串 组合型DFS+Backtracking Medium 2020/7/2
90 15-permutations 全排列 排列型DFS+Backtracking Medium 2020/7/2
91 16-permutations-ii 全排列 排列型DFS+Backtracking Medium 2020/7/2
92 669-coin-change 换硬币 无限背包,DFS,DP,不用回溯 2020/7/3
93 816-traveling-salesman-problem 旅行商问题 排列型DFS,pruning,dp,旅行售货员问题,TSP问题,组合优化 Hard 2020/7/3
94 1147-work-plan 工作安排 coordinate-dp Medium 2020/7/3
95 76-longest-increasing-subsequence 最长上升子序列(LIS) match-dp,LIS Medium 2020/7/3
96 91-minimum-adjustment-cost 最小调整代价 dp Medium 2020/7/3
97 34-n-queens-ii N皇后问题(方案数) Backtracking+DFS Medium 2020/7/4
98 33-n-queens N皇后问题(具体方案) Backtracking+DFS Medium 2020/7/4
99 622-frog-jump 青蛙跳 DFS,DP Hard 2020/7/4
100 602-russian-doll-envelopes 俄罗斯套娃信封 dfs(指数级),dp(正解) Hard 2020/7/4
101 116-jump-game 跳跃游戏 单序列dp(可行性),贪心 Medium 2020/7/4
102 117-jump-game-ii 跳跃游戏 单序列dp(最小值) Medium 2020/7/4
103 149-best-time-to-buy-and-sell-stock 买卖股票的最佳时机(一次交易) 单序列dp(最大值) Medium 2020/7/4
104 115-unique-paths-ii 不同的路径 II 坐标DP Easy 2020/7/4
105 111-climbing-stairs 爬楼梯 单序列dp(计数问题) Easy 2020/7/4
106 563-backpack-v 背包问题 V Backpack DP Medium 2020/7/4
107 630-knight-shortest-path-ii 骑士的最短路径II 坐标dp, 单向BFS->双向BFS Medium 2020/7/6
108 564-combination-sum-iv(backpack-vi) 组合总和 IV 单序列dp,Backpack DP Medium 2020/7/6
109 512-decode-ways 解码方法 dp Medium 2020/7/7
110 589-connecting-graph 连接图 union-find Medium 2020/7/7 2021/2/14
111 752-rogue-knight-sven 流浪剑客斯温 dp Medium 2020/7/7
112 590-connecting-graph-ii 连接图 union-find Medium 2020/7/8
113 360-sliding-window-median 滑动窗口的中位数 heap,Sliding Window Hard 2020/7/8
114 401-kth-smallest-number-in-sorted-matrix 排序矩阵中的从小到大第k个数 heap Medium 2020/7/8
115 362-sliding-window-maximum 滑动窗口的最大值 monotonic-queue Hard 2020/7/8
116 178-graph-valid-tree 图是否是树 union-find Medium 2020/7/8
117 434-number-of-islands-ii 岛屿的个数II union-find Medium 2020/7/9
118 430-scramble-string 攀爬字符串 dfs+pruning Hard 2020/7/9
119 802-sudoku-solver 数独 dfs+pruning+backtracking Hard 2020/7/10
120 121-word-ladder-ii 单词接龙 II dfs+pruning+backtracking Hard 2020/7/10
121 582-word-break-ii 单词拆分II dfs+pruning+backtracking Hard 2020/7/11
122 652-factorization 因式分解 dfs+pruning+backtracking Medium 2020/7/11
123 119-edit-distance 编辑距离 匹配性dp Medium 2020/7/11
124 787-the-maze 迷宫 bfs Medium 2020/7/11
125 788-the-maze-ii 迷宫 bfs Medium 2020/7/11
126 789-the-maze-iii 迷宫 bfs Hard 2020/7/11
127 691-recover-binary-search-tree 恢复二叉搜索树 bst Medium 2020/7/12
128 82-single-number 落单的数2n*1,两次 bit,hash Easy 2020/7/12
129 83-single-number-ii 落单的数 II 3n*1,三次 bit,hash Medium 2020/7/12
130 84-single-number-iii 落单的数2*n + 2 bit,hash Medium 2020/7/12
131 46-majority-element 主元素(不是众数) 1/2 Enumerate Easy 2020/7/12
132 1018-champagne-tower(triangle) 香槟塔 二维坐标dp Medium 2020/7/12
133 200-longest-palindromic-substring 最长回文子串 区间dp Medium 2020/7/14
134 1565-modern-ludo-i 飞行棋 I 一维坐标dp Medium 2020/7/16
135 1141-the-months-days 月份天数 闰年 Easy 2020/7/16
136 254-drop-eggs 丢鸡蛋 归纳法 Easy 2020/7/16
137 47-majority-element-ii 主元素1/3 Enumerate Medium 2020/7/19
138 48-majority-element-iii 主元素1/k HashTable Medium 2020/7/20
139 150-best-time-to-buy-and-sell-stock-ii 买卖股票的最佳时机 II(多次交易) 贪心 Medium 2020/7/20
140 151-best-time-to-buy-and-sell-stock-iii 买卖股票的最佳时机 III(两笔交易) Enumerate Medium 2020/7/20
141 393-best-time-to-buy-and-sell-stock-iv 买卖股票的最佳时机 III(K笔交易) dp Medium 2020/7/20
142 44-minimum-subarray 最小子数组 贪心 Easy 2020/7/20
143 45-maximum-subarray-difference 最大子数组差 贪心 Easy 2020/7/20
144 138-subarray-sum 子数组之和 hashmap Easy 2020/7/20
145 139-subarray-sum-closest 最接近零的子数组和 Two Pointers,hashmap Medium 2020/7/20
146 56-two-sum 两数之和 Two Pointers Easy 2020/7/20
147 608-two-sum-ii-input-array-is-sorted 两数和 II-输入已排序的数组 Two Pointers Medium 2020/7/20
148 57-3sum 三数之和 Two Pointers Medium 2020/7/20
149 533-two-sum-closest-to-target 两数和的最接近值 Two Pointers Medium 2020/7/20
150 89-k-sum K数之和 dp Hard 2020/7/20
151 140-fast-power 快速幂 DC Medium 2020/7/21
152 1324-count-primes 质数的个数 Mathmatics Easy 2020/7/21
153 141-sqrtx 对x开根 Mathmatics Easy 2020/7/21
154 2-trailing-zeros 尾部的零 Mathmatics Easy 2020/7/21
155 142.o1-check-power-of-2 O(1)时间检测2的幂次 Binary Easy 2020/7/21
156 49-sort-letters-by-case 字符大小写排序 Two Pointers Medium 2020/7/21
157 1563-shortest-path-to-the-destination 目的地的最短路径 bfs Medium 2020/7/21
158 108-palindrome-partitioning-ii 分割回文串 II dp Medium 2020/8/2
159 107-word-break 单词拆分 I dp Medium 2020/8/2
160 41-maximum-subarray 最大子数组 dp Easy 2020/8/3
161 29-interleaving-string 交叉字符串 dp Medium 2020/8/9
162 513-perfect-squares 完美平方 dp Medium 2020/8/9
163 394-coins-in-a-line 硬币排成线 dp Medium 2020/8/9
164 92-backpack 背包问题 dp Medium 2020/8/9
165 118-distinct-subsequences 不同的子序列 dp Medium 2020/8/9
166 604-window-sum 滑动窗口内数的和 two-pointer Easy 2020/8/9
167 539-move-zeroes 移动0 two-pointer Easy 2020/8/10
168 521.remove-duplicate-numbers-in-array 数组去重 two-pointer Easy 2020/8/10
169 638. Isomorphic Strings 字符同构 string Easy 2021/2/10
170 626. Rectangle Overlap 矩形重叠 string Easy 2021/2/10
171 637. Valid Word Abbreviation 检查缩写单词 string Easy 2021/2/10
172 639. Word Abbreviation 单词缩写 string Hard 2021/2/11
173 642. Moving Average from Data Stream 数据流滑动窗口平均值 Prefix Sum Array,rolling array Easy 2021/2/11
174 644. Strobogrammatic Number 镜像数字 Enumerate Easy 2021/2/11
175 640. One Edit Distance 一次编辑距离 Enumerate Medium 2021/2/11
176 660. Read N Characters Given Read4 用Read4从文件中读取N个字符 II-多次调用 Enumerate Hard 2021/2/12
177 659. Encode and Decode Strings 编码和解码字符串 Enumerate Medium 2021/2/12
178 419. Roman to Integer 罗马数字转整数 Enumerate Medium 2021/2/12
179 418. Integer to Roman 整数转罗马数字 Enumerate Medium 2021/2/12
180 645. Find the Celebrity 识别名人 Enumerate Medium 2021/2/12
181 641. Missing Ranges 丢失的间隔 Enumerate Medium 2021/2/12
182 156. Merge Intervals 合并区间 Enumerate Easy 2021/2/12
183 30. Insert Interval 插入区间 Enumerate Medium 2021/2/12
184 646. First Position Unique Character 第一个不重复字符位置 Hash Easy 2021/2/12
185 647. Find All Anagrams in a String 子串字谜 Hash+Siding Windows Medium 2021/2/12
186 423. Valid Parentheses 有效的括号序列 Stack Easy 2021/2/13
187 526. Load Balancer 负载均衡 DS 2021/2/13
188 662. Guess Number Higher or Lower 猜数游戏 Binary Search Easy 2021/2/13
189 661. Convert BST to Greater Tree 把二叉搜索树转化成更大的树 BST Easy 2021/2/13
190 649. Binary Tree Upside Down 二叉树翻转 BST Medium 2021/2/13
191 650. Find Leaves of Binary Tree 二叉树叶子顺序遍历 BST Medium 2021/2/13
192 651. Binary Tree Vertical Order Traversal 二叉树垂直遍历 Hash+BFS Medium 2021/2/13
193 448. Inorder Successor in BST 二叉查找树的中序后继 BST Medium 2021/2/13
194 477. Surrounded Regions 被围绕的区域 BFS Medium 2021/2/13
195 663. Walls and Gates 墙和门 BFS Medium 2021/2/13
196 32. Minimum Window Substring 最小子串覆盖 Two pointer Medium 2021/2/14
197 543. Kth Largest in N Arrays N数组第K大元素(一个数组第K大) Heap Hard 2021/2/14
198 465. Kth Smallest Sum In Two Sorted Arrays 两个排序数组和的第K小 Heap Hard 2021/2/14
199 591. Connecting Graph III 连接图 III UF Medium 2021/2/14
200 1179. Friend Circles 朋友圈 UF Medium 2021/2/14
201 152. Combinations 组合 DFS,组合 Medium 2021/2/15
202 135. Combination Sum I 组合数之和 DFS,组合 Medium 2021/2/15
203 153. Combination Sum II 组合数之和 DFS,组合 Medium 2021/2/15
204 1321. Combination Sum III 组合数之和 DFS,组合 Medium 2021/2/15
205 457. Classical Binary Search 经典二分查找问题 Binary Search Easy 2021/2/15
206 366. Fibonacci 斐波那契 iteration/recursion,多项公式 Naive 2021/2/16
207 1807. Fibonacci easy 斐波那契 iteration Easy 2021/2/16
208 428. Pow(x, n) x的n次幂 recursion,decrease-and-conquer Medium 2021/2/16
209 451. Swap Nodes in Pairs 两两交换链表中的节点 2021/2/16
210 450. Reverse Nodes in k-Group K组翻转链表 2021/2/16
211 1425. Backspace String Compare 比较含退格的字符串 2021/2/16
212 5.Kth Largest Element 数组第k大元素 2021/2/16
213 471. Top K Frequent Words 最高频的K个单词 2021/2/16
214 1311. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先 Easy 2021/2/16
215 1509. Lemonade Change 柠檬水找零 Greedy Easy 2021/2/16
216 1230. Assign Cookies 分饼干 Greedy Easy 2021/2/16
217 1493. Walking Robot Simulation 模拟行走机器人 Greedy 2021/2/16
218 155. Minimum Depth of Binary Tree 二叉树的最小深度 2021/2/16
219 1360. Symmetric Tree 对称树 2021/2/16
220 1244. Minimum Genetic Mutation 最小基因变化 2021/2/16
221 427. Generate Parentheses 生成括号 2021/2/16
222 1195. Find Largest Value in Each Tree Row 找出树中每行的最大值 Medium 2021/2/16
223 120. Word Ladder 单词接龙 2021/2/16
224 615. Course Schedule 课程表 2021/2/16
225 1189. Minesweeper 扫雷游戏 BFS Medium 2021/2/16
226 389. Valid Sudoku 判断数独是否合法 Simulation Easy 2021/2/16
227 123. Word Search 单词搜索 DFS Medium 2021/2/16
228 664. Counting Bits 数 1 Bit,DP Medium 2021/2/16
229 191. Maximum Product Subarray 乘积最大子序列 线性dp Medium 2021/2/16
230 556. Standard Bloom Filter 标准型布隆过滤器 Medium 2021/2/16
231 555. Counting Bloom Filter 计数型布隆过滤器 Medium 2021/2/16
232 1332. Number of 1 Bits 判断一个整数中有多少个1 Bit Easy 2021/2/16
233 204. Singleton 单例 OOD Easy 2021/2/16
234 496. Toy Factory 工厂 OOD Easy 2021/2/16
235 175. Invert Binary Tree 反转二叉树 Tree Easy 2021/2/16