Leetcode

总结

这是本人在7个月刷了500道Leetcode题目并成功拿到几家北美Software Engineer Offer之后总结的Leetcode高频面试题目分类总结。这篇是高频题目的概述性总结，以后有时间打算单独给每个门类写一个详细的总结。希望对准备刷题面试的你有所帮助吧，谢谢！

这里还有一篇我写的关于码农算法面试的Q&A:

TimothyL：北美码农算法面试Q&A56 赞同 · 7 评论文章

注：本文一共200多道题，算上一些附加的衍生题差不多有250+，基本上很少有easy题目，大部分都是medium，少部分hard，按照大多数人30% Easy，60% Medium， 10% Hard的刷题标准，刷好下面全部的题目相当于300题，足够应对大部分的算法面试了。如果你对算法与数据结构基础知识掌握的不够的情况下，先按照上面链接提到的基础补好再开始刷对应门类的题目，不然很容易“一个人一包烟，一道题目刷一天”。

注：作者后来在北美各个大厂几乎全部面过，G家 A家 U家之类的大厂offer也都拿到过，可以确定刷好本文中的所有题以及掌握每道题对应知识点可以应对绝大多数的码农算法面试了。

如果题目/答案看不懂又不喜欢看discussion的话，现在有很多视频资源可以看。个人比较喜欢花花酱的讲解（花花酱的表世界的个人空间_哔哩哔哩_Bilibili），墙外的同学们也可以看关神的视频讲解（https://www.youtube.com/channel/UCY5Z0of98W-YSdmPgAe1DaA）。

不建议刷的题目类型：

非高频的hard题目，费时费力又很难在面试中遇到，性价比太低。
贪心法题目，每道题都不一样，解法没有通用性。

以下8个门类是面试中最常考的算法与数据结构知识点。

排序类（Sort）：

基础知识：快速排序（Quick Sort），归并排序（Merge Sort）的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度平均状态下O（NlogN），空间复杂度O（1），归并排序最坏情况下时间复杂度O（NlogN），空间复杂度O（N）
入门题目：
- Leetcode 148. Sort List
  - Leetcode 56. Merge Intervals
  - Leetcode 27. Remove elements
进阶题目：
- Leetcode 179. Largest Number
  - Leetcode 75. Sort Colors
  - Leetcode 215. Kth Largest Element （可以用堆的解法替代）
  - Leetcode 4. Median of Two Sorted Arrays

注意：后两题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考

链表类（Linked List）：

基础知识：链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是O（1），查找任意元素位置O（N）
基础题目：
- Leetcode 206. Reverse Linked List
  - Leetcode 876. Middle of the Linked List

注意：快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。

进阶题目:
- Leetcode 160. Intersection of Two Linked Lists
  - Leetcode 141. Linked List Cycle (Linked List Cycle II)
  - Leetcode 92. Reverse Linked List II
  - Leetcode 328. Odd Even Linked List

堆（Heap or Priority Queue）、栈（Stack）、队列（Queue）、哈希表类（Hashmap、Hashset）：

基础知识：各个数据结构的基本原理，增删查改复杂度。
Queue题目：
- Leetcode 225. Implement Stack using Queues
  - Leetcode 346. Moving Average from Data Stream
  - Leetcode 281. Zigzag Iterator
  - Leetcode 1429. First Unique Number
  - Leetcode 54. Spiral Matrix
  - Leetcode 362. Design Hit Counter
Stack题目：
- Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack)
  - Leetcode 232. Implement Queue using Stacks
  - Leetcode 150. Evaluate Reverse Polish Notation
  - Leetcode 224. Basic Calculator II (I, II, III, IV)
  - Leetcode 20. Valid Parentheses
  - Leetcode 1472. Design Browser History
  - Leetcode 1209. Remove All Adjacent Duplicates in String II
  - Leetcode 1249. Minimum Remove to Make Valid Parentheses
  - Leetcode 735. Asteroid Collision
Hashmap/ Hashset题目：
- Leetcode 1. Two Sum
  - Leetcode 146. LRU Cache (Python中可以使用OrderedDict来代替)
  - Leetcode 128. Longest Consecutive Sequence
  - Leetcode 73. Set Matrix Zeroes
  - Leetcode 380. Insert Delete GetRandom O(1)
  - Leetcode 49. Group Anagrams
  - Leetcode 350. Intersection of Two Arrays II
  - Leetcode 299. Bulls and Cows
  - Leetcode 348 Design Tic-Tac-Toe
Heap／Priority Queue题目：
- Leetcode 973. K Closest Points
  - Leetcode 347. Top k Largest Elements
  - Leetcode 23. Merge K Sorted Lists
  - Leetcode 264. Ugly Number II
  - Leetcode 1086. High Five
  - Leetcode 88. Merge Sorted Arrays
  - Leetcode 692. Top K Frequent Words
  - Leetcode 378. Kth Smallest Element in a Sorted Matrix
  - Leetcode 295. Find Median from Data Stream （标准解法是双heap，但是SortedDict会非常容易）
  - Leetcode 767. Reorganize String
  - Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (这个题用单调双端队列、TreeMap、双heap都可以)
  - Leetcode 895. Maximum Frequency Stack

二分法（Binary Search）：

基础知识：二分法是用来解法基本模板，时间复杂度logN；常见的二分法题目可以分为两大类，显式与隐式，即是否能从字面上一眼看出二分法的特点：要查找的数据是否可以分为两部分，前半部分为X，后半部分为O
显式二分法：
- Leetcode 34. Find First and Last Position of Element in Sorted Array
  - Leetcode 33. Search in Rotated Sorted Array
  - Leetcode 1095. Find in Mountain Array
  - Leetcode 162. Find Peak Element
  - Leetcode 278. First Bad Version
  - Leetcode 74. Search a 2D Matrix
  - Leetcode 240. Search a 2D Matrix II
隐式二分法：
- Leetcode 69. Sqrt(x)
  - Leetcode 540. Single Element in a Sorted Array
  - Leetcode 644. Maximum Average Subarray II
  - Leetcode 528. Random Pick with Weight
  - Leetcode 1300. Sum of Mutated Array Closest to Target
  - Leetcode 1060. Missing Element in Sorted Array
  - Leetcode 1062. Longest Repeating Substring
  - Leetcode 1891. Cutting Ribbons
  - Leetcode 410. Split Array Largest Sum (与1891类似)

双指针（2 Pointer）：

基础知识：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）
背向双指针：(基本上全是回文串的题)
- Leetcode 409. Longest Palindrome
  - Leetcode 125. Valid Palindrome (I、II)
  - Leetcode 5. Longest Palindromic Substring
  - Leetcode 647. Palindromic Substrings
相向双指针：(以two sum为基础的一系列题)
- Leetcode 1. Two Sum (这里使用的是先排序的双指针算法，不同于hashmap做法)
  - Leetcode 167. Two Sum II - Input array is sorted
  - Leetcode 15. 3Sum
  - Leetcode 16. 3Sum Closest
  - Leetcode 18. 4Sum
  - Leetcode 454. 4Sum II
  - Leetcode 277. Find the Celebrity
  - Leetcode 11. Container With Most Water
  - Leetcode 186 Reverse Words in a String II
同向双指针：（个人觉得最难的一类题，可以参考下这里 TimothyL：Leetcode 同向双指针/滑动窗口类代码模板）
- Leetcode 283. Move Zeroes
  - Leetcode 26. Remove Duplicate Numbers in Array
  - Leetcode 395. Longest Substring with At Least K Repeating Characters
  - Leetcode 340. Longest Substring with At Most K Distinct Characters
  - Leetcode 424. Longest Repeating Character Replacement
  - Leetcode 76. Minimum Window Substring
  - Leetcode 3. Longest Substring Without Repeating Characters
  - Leetcode 1004 Max Consecutive Ones III
  - Leetcode 1658 Minimum Operations to Reduce X to Zero

宽度优先搜索（BFS）：面试中最常考的

基础知识：
- 常见的BFS用来解决什么问题？(1) 简单图（有向无向皆可）的最短路径长度，注意是长度而不是具体的路径（2）拓扑排序（3）遍历一个图（或者树）
BFS基本模板（需要记录层数或者不需要记录层数）
多数情况下时间复杂度空间复杂度都是O（N+M），N为节点个数，M为边的个数
基于树的BFS：不需要专门一个set来记录访问过的节点
- Leetcode 102 Binary Tree Level Order Traversal
  - Leetcode 103 Binary Tree Zigzag Level Order Traversal
  - Leetcode 297 Serialize and Deserialize Binary Tree （很好的BFS和双指针结合的题）
  - Leetcode 314 Binary Tree Vertical Order Traversal
基于图的BFS：（一般需要一个set来记录访问过的节点）
- Leetcode 200. Number of Islands
  - Leetcode 133. Clone Graph
  - Leetcode 127. Word Ladder
  - Leetcode 490. The Maze
  - Leetcode 323. Connected Component in Undirected Graph
  - Leetcode 130. Surrounded Regions
  - Leetcode 752. Open the Lock
  - Leetcode 815. Bus Routes
  - Leetcode 1091. Shortest Path in Binary Matrix
  - Leetcode 542. 01 Matrix
  - Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination
  - Leetcode 417. Pacific Atlantic Water Flow
拓扑排序：（https://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F）
- Leetcode 207 Course Schedule （I, II）
  - Leetcode 444 Sequence Reconstruction
  - Leetcode 269 Alien Dictionary
  - Leetcode 310 Minimum Height Trees
  - Leetcode 366 Find Leaves of Binary Tree

深度优先搜索（DFS）：面试中最常考的（分类的稍微有点粗糙了，没有细分出回溯/分治来，准备找个时间给每个DFS的题标记下是哪种DFS）

基础知识：
- 常见的DFS用来解决什么问题？(1) 图中（有向无向皆可）的符合某种特征（比如最长）的路径以及长度（2）排列组合（3）遍历一个图（或者树）（4）找出图或者树中符合题目要求的全部方案
  - DFS基本模板（需要记录路径，不需要返回值 and 不需要记录路径，但需要记录某些特征的返回值）
  - 除了遍历之外多数情况下时间复杂度是指数级别，一般是O(方案数×找到每个方案的时间复杂度)
  - 递归题目都可以用非递归迭代的方法写，但一般实现起来非常麻烦
基于树的DFS：需要记住递归写前序中序后序遍历二叉树的模板
- Leetcode 543 Diameter of Binary Tree (分治)
  - Leetcode 124 Binary Tree Maximum Path Sum (分治)
  - Leetcode 226 Invert Binary Tree (分治)
  - Leetcode 101 Symmetric Tree (回溯 or 分治)
  - Leetcode 951 Flip Equivalent Binary Trees (分治)
  - Leetcode 236 Lowest Common Ancestor of a Binary Tree (相似题：235、1650) (回溯 or 分治)
  - Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal (分治)
  - Leetcode 104 Maximum Depth of Binary Tree (回溯 or 分治)
  - Leetcode 987 Vertical Order Traversal of a Binary Tree
  - Leetcode 1485 Clone Binary Tree With Random Pointer
  - Leetcode 572 Subtree of Another Tree (分治)
  - Leetcode 863 All Nodes Distance K in Binary Tree
  - Leetcode 1110 Delete Nodes And Return Forest (分治)
二叉搜索树（BST）：BST特征：中序遍历为单调递增的二叉树，换句话说，根节点的值比左子树任意节点值都大，比右子树任意节点值都小，增删查改均为O（h）复杂度，h为树的高度；注意不是所有的BST题目都需要递归，有的题目只需要while循环即可
- Leetcode 230 Kth Smallest element in a BST
  - Leetcode 98 Validate Binary Search Tree
  - Leetcode 270 Cloest Binary Search Tree Value
  - Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
  - Leetcode 669 Trim a Binary Search Tree (分治)
  - Leetcode 700 Search in a Binary Search Tree
  - Leetcode 108 Convert Sorted Array to Binary Search Tree (分治)
  - Leetcode 333 Largest BST Subtree (与98类似) (分治)
  - Leetcode 285 Inorder Successor in BST (I, II)
基于图的DFS: 和BFS一样一般需要一个set来记录访问过的节点，避免重复访问造成死循环; Word XXX 系列面试中非常常见，例如word break，word ladder，word pattern，word search。
- Leetcode 341 Flatten Nested List Iterator (339 364)
  - Leetcode 394 Decode String
  - Leetcode 51 N-Queens (I II基本相同)
  - Leetcode 291 Word Pattern II (I为简单的Hashmap题)
  - Leetcode 126 Word Ladder II （I为BFS题目）
  - Leetcode 93 Restore IP Addresses
  - Leetcode 22 Generate Parentheses
  - Leetcode 856 Score of Parentheses
  - Leetcode 301 Remove Invalid Parentheses
  - Leetcode 37 Sodoku Solver
  - Leetcode 212 Word Search II （I, II）
  - Leetcode 1087 Brace Expansion
  - Leetcode 399 Evaluate Division
  - Leetcode 1274 Number of Ships in a Rectangle
  - Leetcode 1376 Time Needed to Inform All Employees
  - Leetcode 694 Number of Distinct Islands
  - Leetcode 131 Palindrome Partitioning
基于排列组合的DFS: 其实与图类DFS方法一致，但是排列组合的特征更明显
- Leetcode 17 Letter Combinations of a Phone Number
  - Leetcode 39 Combination Sum（I, II, III相似， IV为动态规划题目）
  - Leetcode 78 Subsets （I, II 重点在于如何去重）
  - Leetcode 46 Permutation (I, II 重点在于如何去重)
  - Leetcode 77 Combinations (I, II 重点在于如何去重)
  - Leetcode 698 Partition to K Equal Sum Subsets
  - Leetcode 526 Beautiful Arrangement (similar to 46)
记忆化搜索（DFS + Memoization Search）：算是用递归的方式实现动态规划，递归每次返回时同时记录下已访问过的节点特征，避免重复访问同一个节点，可以有效的把指数级别的DFS时间复杂度降为多项式级别; 注意这一类的DFS必须在最后有返回值（分治法），不可以用回溯法; for循环的dp题目都可以用记忆化搜索的方式写，但是不是所有的记忆化搜索题目都可以用for循环的dp方式写。
- Leetcode 139 Word Break II
  - Leetcode 72 Edit Distance
  - Leetcode 377 Combination Sum IV
  - Leetcode 1235 Maximum Profit in Job Scheduling
  - Leetcode 1335 Minimum Difficulty of a Job Schedule
  - Leetcode 1216 Valid Palindrome III
  - Leetcode 97 Interleaving String
  - Leetcode 472 Concatenated Words
  - Leetcode 403 Frog Jump
  - Leetcode 329 Longest Increasing Path in a Matrix

前缀和（Prefix Sum）

基础知识：前缀和本质上是在一个list当中，用O（N）的时间提前算好从第0个数字到第i个数字之和，在后续使用中可以在O（1）时间内计算出第i到第j个数字之和，一般很少单独作为一道题出现，而是很多题目中的用到的一个小技巧
常见题目：
- Leetcode 53 Maximum Subarray
  - Leetcode 1423 Maximum Points You Can Obtain from Cards
  - Leetcode 1031 Maximum Sum of Two Non-Overlapping Subarrays
  - Leetcode 523 Continuous Subarray Sum
  - Leetcode 304 Range Sum Query 2D - Immutable

以上内容皆为面试中高频的知识点，以下知识点和题目在面试中属于中等频率（大概面10道题会遇到一次），时间不足的情况下，请以准备上面的知识点为主。

并查集（Union Find）：把两个或者多个集合合并为一个集合

基础知识：如果数据不是实时变化，本类问题可以用BFS或者DFS的方式遍历，如果数据实时变化（data stream）则并查集每次的时间复杂度可以视为O（1）；需要牢记合并与查找两个操作的模板
常见题目：
- Leetcode 721 Accounts Merge
  - Leetcode 547 Number of Provinces
  - Leetcode 737 Sentence Similarity II
  - Leetcode 305 Number of Islands II

字典树（Trie）

基础知识：（https://zh.wikipedia.org/wiki/Trie）；多数情况下可以通过用一个set来记录所有单词的prefix来替代，时间复杂度不变，但空间复杂度略高
常见题目：
- Leetcode 208 Implement Trie (Prefix Tree)
  - Leetcode 211 Design Add and Search Words Data Structure
  - Leetcode 1268 Search Suggestions System
  - Leetcode 212 Word Search II
  - Leetcode 1166 Design File System

单调栈与单调队列（Monotone Stack／Queue）

基础知识：单调栈一般用于解决数组中找出每个数字的第一个大于／小于该数字的位置或者数字；单调队列只见过一道题需要使用；不论单调栈还是单调队列，单调的意思是保留在栈或者队列中的数字是单调递增或者单调递减的
常见题目：
- Leetcode 85 Maximum Rectangle
  - Leetcode 84 Largest Rectangle in Histogram
  - Leetcode 907 Sum of Subarray Minimums (与84类似)
  - Leetcode 739 Daily Temperatures
  - Leetcode 901 Online Stock Span
  - Leetcode 503 Next Greater Element II
  - Leetcode 239 Sliding Window Maximum （唯一的单调队列题）

扫描线算法（Sweep Line）

基础知识：一个很巧妙的解决时间安排冲突的算法，本身比较容易些也很容易理解
常见题目：
- Leetcode 253 Meeting Room II（Meeting Room I也可以使用）
  - Leetcode 1094 Car Pooling
  - Leetcode 218 The Skyline Problem
  - Leetcode 759 Employee Free Time

TreeMap

基础知识：基于红黑树（平衡二叉搜索树）的一种树状 hashmap，增删查改、找求大最小均为logN复杂度，Python当中可以使用SortedDict替代；SortedDict继承了普通的dict全部的方法，除此之外还可以peekitem(k)来找key里面第k大的元素，popitem(k)来删除掉第k大的元素，弥补了Python自带的heapq没法logN时间复杂度内删除某个元素的缺陷；最近又在刷一些hard题目时候突然发现TreeMap简直是个神技，很多用别的数据结构写起来非常麻烦的题目，TreeMap解决起来易如反掌。
常见题目：
Leetcode 729 My Calendar I
Leetcode 981 Time Based Key-Value Store
Leetcode 846 Hand of Straights
Leetcode 218 The Skyline Problem
Leetcode 480. Sliding Window Median (这个题用TreeMap超级方便)
Leetcode 318 Count of Smaller Numbers After Self (这个题线段树、二分索引树、TreeMap都可以)

动态规划（Dynamic Programming）

基础知识：这里指的是用for循环方式的动态规划，非Memoization Search方式。DP可以在多项式时间复杂度内解决DFS需要指数级别的问题。常见的题目包括找最大最小，找可行性，找总方案数等，一般结果是一个Integer或者Boolean。动态规划有很多分支，暂时还没想好怎么去写这部分，后面想好了再具体写吧。
常见题目：
- Leetcode 674 Longest Continuous Increasing Subsequence (接龙型dp)
  - Leetcode 62 Unique Paths II
  - Leetcode 70 Climbing Stairs
  - Leetcode 64 Minimum Path Sum
  - Leetcode 368 Largest Divisible Subset (接龙型dp)
  - Leetcode 300 Longest Increasing Subsequence (接龙型dp)
  - Leetcode 354 Russian Doll Envelopes (接龙型dp， 300的2D版)
  - Leetcode 256 Paint House
  - Leetcode 121 Best Time to Buy and Sell Stock
  - Leetcode 55 Jump Game
  - Leetcode 45 Jump Game II
  - Leetcode 132 Palindrome Partitioning II
  - Leetcode 312 Burst Balloons (区间型dp)
  - Leetcode 1143 Longest Common Subsequence (前缀型dp)
  - Leetcode 1062 Longest Repeating Substring (dp方法与longest common substring一致)
  - Leetcode 718 Maximum Length of Repeated Subarray (和1062本质上一样)
  - Leetcode 174 Dungeon Game
  - Leetcode 115 Distinct Subsequences
  - Leetcode 72 Edit Distance
  - Leetcode 91 Decode Ways
  - Leetcode 639 Decode Ways II
  - Leetcode 712 Minimum ASCII Delete Sum for Two Strings
  - Leetcode 221 Maximal Square
  - Leetcode 1277 Count Square Submatrices with All Ones (可以使用221一样的解法)
  - Leetcode 198 House Robber
  - Leetcode 213 House Robber II
  - Leetcode 740 Delete and Earn
  - Leetcode 87 Scramble String
  - Leetcode 1140 Stone Game II
  - Leetcode 322 Coin Change
  - Leetcode 518 Coin Change II (01背包型)
  - Leetcode 1048 Longest String Chain
  - Leetcode 44 Wildcard Matching
  - Leetcode 10 Regular Expression Matching
  - Leetcode 32 Longest Valid Parentheses
  - Leetcode 1235 Maximum Profit in Job Scheduling (DP + binary search)
  - Leetcode 1043 Partition Array for Maximum Sum
  - Leetcode 926 Flip String to Monotone Increasing

{% span red, 1. %}if-else if应当这样写
if (*s == 'V')         sum += 5;     
else if (*s == 'L')    sum += 50

{% span red, 2. %}执行代码是检查语法错误，提交是检查算法错误,
 1.执行出错是有语法错误
  (1)可能是漏掉了了一个单词
  (2)也可以是少打了一个,就是没有检查出来
 2.给你指出错误来了,一定是自己搞错了,反向思考一下,适当修改一下
 3.考试的时候只能自己一个一个的检查出哪里有问题,不要怀疑自己的算法,不要考虑换算法,肯定是自己哪里错了,因为自己的语法知识并没有完全掌握,甚至&&会搞错成||
 4.有调试就调试,没有调试就写下一题,然后重新写

{% span red, 3. %}C语言语法基本没有问题，C++可能有语法错误

{% span red, 4. %}自己有代码错误可以用Chatgpt,不懂用Chatgpt,同时注意它的使用技巧,它会记住你之前对它问过的问题来重新会答你,还要结合Bing来写,首先使用chargpt

{% span red, 5. %}注意多使用while()在没有a[], a>b?a:b的使用，输入一个值n,有一个长度为a数组，
输出长度为n的新数组,n可能大于a,可能小于a,选择b=a<n:a,b
即遇到if时可以使用?条件语句
for (int i = 0; i < numsSize; i++)
  int limit = i+k >= numsSize? numsSize: i+k+1;
放在for循环中有满足某个条件时一直等于munsSize


{% span red, 6. %}注意严谨的思维,在读完题以后,回想一下要完成的内容是什么,然后对比题目看遗漏了什么没有

{% span red, 7. %}删除有序数组中的重复项
设置两个指针分别为快指针和慢指针s[a],s[b],比起一个i的s[i]更好控制,先让两个指针指向同一个位置
让后面的值先出现,使用！=,它的目的是空出空位来,在原数组中重新存放元素,而不设置新数组,nums[j]!=nums[j-1]找出不是重复的元素,nums[i]用来存放
双指针的好处是可以记忆元素和直接对数组操作不需要重新创建新的数组

{% span red, 8. %}示例是对if语句的形式的提示

{% span red, 9. %}二分查找法是在数组中找到与指定目标值相同的下标,但必须是有序数组

{% span red, 10. %}一般对字符串的处理函数是可以用的在leetcode

11.在leetcode用到的算法
二分查找法 是在数组中用较少的时间找到要找的数(搜索插入位置),有搜索二字就代表了要二分查找,并且找到下标, while(i<=j)必修等于防止target在最后一个找到
两个指针分别为快指针和慢指针或者更多的指针,指针可以是从数组的第二个元素开始,但一般是从第一个元素开始
两个for循环实现后面的数组元素前移并覆盖一个数组元素
C中的算法
while()
二进制进位法
累加和sum

12.在一个函数中返回一个字符数组的地址,并且需要在该函数中建立一个数组,需使用动态分配,并且不需要free(),注意动态分配的是数组

13. nums1[j--]=nums2[j--]这个代表的是赋值以后要减一 j--

14.c语言注意&& || 的综合运用
 1.if((flowerbed[i]==0) && (i==0 || flowerbed[i-1]==0) && (i==flowerbedSize-1 || flowerbed[i+1]==0));
 与山顶元素一样的在特殊位置与一般位置的分析情况少一点,都是一排过去(||)中有一个是为真的,但要把特殊情况放在里面

15.在一个简单的题目中也要分步骤进行思考例如
 1.先排序
 2.再找出第三大的数

16. for(i = 0; i < nums1Size; i++)      //遍历数组1，记录出现的元素
    {
        count[nums1[i] = 1;            //这里置1，而不++，以便后面操作
    }
这样count[]会把nums1中出现过的数字记录下来,并且还会记录下重复出现的次数，可作用于重复的数字

17.int* returnSize中returnSize是指针,但也是这样用的 ret[(*returnSize)] = nums2[i]; *returnSize++;

18.快速排序
函数声明
int Cmp_int(const void* p1, const void* p2)     是一个自定义的比较函数
{	
	return (*(int*)p1 - *(int*)p2);
}
注意快速排序是对无序的数组进行的,对从小到大还是从大到小都是无操作的

qsort(nums1, nums1Size, sizeof(int), Cmp_int);

19.int* returnSize,作为参数
1.传递过来时对它取值增时要注意(*returnSize)++,而不是这样的 *returnSize++
2.对它赋值时同时也应该注意是*returnSize=0,而不是int *returnSize=0
3.看到它要记住对它的处理,但不返回它的值,我们是通过地址来改变它在主函数里的值

20.选择排序
int temp
for(k=0;k<numsSize-1;k++){
        index=k;
        for(i=k+1;i<numsSize;i++){
            if(a[i]<a[index]){
                index=i;
            }
        }
        temp=a[index];
        a[index]=a[k];
        a[k]=temp;
   }
要使用下标来表示最小值,而不是一个值,还有就是在交换时不是使用i,其实i要比index大

21.在内部创建的字符串数组结束以后记得加上a[i]='\0',如果不返回这还要释放它， char* ch=(char*)malloc(size+1)，free()

22. for(i=0;i<size;i++){
        if((s[i]>='a'&&s[i]<='z')||(s[i]>='0'&&s[i]<='9')){
        ch[j]=s[i];
        j++;
        }else if(s[i]>='A'&&s[i]<='Z'){
        ch[j]=s[i]-'A'+'a';
        j++;
        }
    }
j++以后是要比当前大一些的加1后并没有使用,所以在后面的使用要减1

23.char a[0]='/0'表示空字符串,strs[0][0]='\0',return strs[0]表示返回空字符串,使用'\0',直接截断了字符串的长度
    1.1 <= strs.length <= 200表示二维字符串strs = ["flower","flow","flight"],"flower"的长度
    2.0 <= strs[i].length <= 200表示["flower","flow","flight"]的长度

24.while(flag){
        for(j=1;j<strsSize;j++){
            if(strs[j][i]!=flag) break;    
        }
        if(j<strsSize) break;      
        flag=strs[0][++i];
    }
两次break跳出循环

25. char *c=(char*)malloc(sizeof(char)*length);
    c[length-1]='\0';
在字符串动态内存分配以后,要立马给它a[size-1]='/0'

26.if(*src=='\0') 
    return NULL;
有src[0]='\0'可以返回NULL空字符

27.三数之和
输出的顺序和三元组的顺序并不重要,一般要涉及到排序来解决,如果是和下标有关系的话就不能排序

28.三数之和
1.for(j=i+1;k<numsSize-1;j<k;){j++;k++}两个指针相向运动for写的情况,只有排好序,为了才好逐个遍历,消重也可以用来控制有重复出现要输出时,输出第一种的情况,省略了++的情况
2.三个指针使用分布的情况,注意continue的使用用来跳过当前循环
3.for(i=0;i<(numsSize-2);i++){
    if((nums[i]+nums[i+1]+nums[i+2])>0) break;
能够提升算法的效率,在该题中还用了除去相同的结果
29.二维数组的动态内存分配
 1.整个二维数组int **res=(int **)malloc(sizeof(int *) * (numsSize + 1) * 6);
 2.对行指针的分配 res[*returnSize]=(int*)malloc(sizeof(int)*3);
 3.对列指针的分配 *returnColumnSizes=(int*)malloc(sizeof(int)*(*returnSize));
 4.申请内存，此时不确定合并之后的数组大小，只能按照intervalSize进行申请
   int **target = (int **)malloc(sizeof(int *)*intervalsSize);
   *returnColumnSizes = (int *)malloc(sizeof(int) * intervalsSize);
 4.int** threeSum() return a返回的是一级指针

30.自己创建一个数组来记录前面出现过的重复的数,主要是前面与后面比较
最长子串的题都是用双指针来移动

31.字符串转换整数
看似只遍历了字符串的第一字符,但实则遍历了很多字符
 1.while(*str == ' ')			//删除空格 
		++str;
 对空格多次遍历
 2.if(*str == '-'){
		flag = -1;
		++str;
 对'-'遍历了一次
 3.while(*str>='0' && *str<='9'){
		temp = *str-'0';
		if(res<div || (res==div&&temp<8)){
			res = res*10 + temp;
			++str;
		}
		else
			return (flag==1?INT_MAX:INT_MIN);
	}
	return res*flag;	
 对数字遍历了多次
 4.return res*flag;
 并且遇到英文字符时就结束
 5.int div = INT_MAX/10;
   temp = *str-'0';
   if(res<div||(res==div&&temp<8))
 确保不会超出整数的范围

32.如何将找到的元素存放到数组中

33.在找出字符串中第一个匹配项的下标中
 1.for(i=0;i<strlen(haystack);i++){
        if(i+strlen(needle)>strlen(haystack)){
 也是用来提升效率的
 2.for(i=0;i<strlen(haystack);i++){
        if(i+strlen(needle)>strlen(haystack)){
            break;
        }
        for(j=0;j<strlen(needle);j++){
            if(haystack[i+j]!=needle[j]){
                break;
            }
            if(j==strlen(needle)-1){
                return i;
            }
        }
    }
 使得能找准对的下标位置来比较

34 1.reverse函数来对字符串反转,直接使用库函数
   2.split函数,就给它拆成一个个独立的单词了
   3.erase函数就能在字符串里删除字符   

35.空间复杂度是o(1)的不能去申请一个新的字符串,做字符串的一般都有申请新的字符串,移除数组,移除多余空格都需要双指针来操作,并且是原地移除

36.1 <= num <= 3999
char* result = (char*)malloc(sizeof(char) * 20)有时候是要自己计算来分配多少内存的

37. memcpy(result + strIndex, rom[numIndex], strlen(rom[numIndex]));将字符串放到字符数组中的函数

38.char* result = (char*)malloc(sizeof(char) * 20)
*(result + strIndex) = '\0';在申请内存中最后还不知道为多少时,要在后面加上'\0'

39. 在排序数组中查找元素的第一个和最后一个位置   记得有查找二字一定用二分查找法

40.在i进行了一次for循环后,注意i的值要比原先大
 for(j=0;j<len;j++){
        
        if(s[j]==' '){
            if(flag==0&&i!=0){
                s[i++]=' ';
                flag=1;
            }
        }else{
            s[i++]=s[j];
            flag=0;
        }
        
    }
    if(i>=1&&s[i-1]==' '){
        s[i-1]='\0';

41.移除元素的本质是利用双指针来覆盖不要的元素

42.将字符串反转时必需有i< j不能i<=j,不然会进入死循环
 //将整个字符串反转
    len=strlen(s);
    i=0,j=len-1;
    while(i<j){
        char temp=s[i];
        s[i++]=s[j];
        s[j--]=temp; 

43.使用了二维数组的动态内存分配的题目有
三数之和
合并区间

44.交换数组中元素可以使用直接赋值
 if(nums[i] == 0){
            nums[i] = nums[j];
            nums[j++] = 0;

45.在for循环中i--是重新查看该位置的元素
 for(i=0;i<=k;i++){
    i--;

46.哈希法
哈希表的数据结构有三种   数组 set map
1.在哈希值比较小的情况下,而且范围也比较小,长度可控,用数组  1 <= nums1.length, nums2.length <= 1000   0 <= nums1[i], nums2[i] <= 1000 就是自定义一个数组不是动态内存分配
2.如果数值很大的话,我们就用set     值是二的次方  unorderset其实它就是一个可以无限存装的一个数组,可以去重,做映射和取值的效率是很高的,在unorderset result中放入100个2最终也会存入一个2
3.如果这个k对应的value的话,我们就用map
4.哈希表最擅长的是解决就是给你一个元素,判断在这个集合里是否出现过

47.既可以对数字数组做计数也可以对字符串数组做计数
for(i=0;i<lens;i++){
        flags[s[i]-'a']++;
    }
记录的是字符串的差值而不是ASCLL码值
如果数字数组的值太大就不好计数了

48.在不需要返回自己创建的数组的时候可以直接定义数组
 int flags[26]=0;
 int flagt[26]=0;

49.有这种关键词就要想到二分查找法
1.在数组中找到目标值
2.搜索
3.在连续的数组中查找
4.在不连续的但是有排序得到数组中查找
5.int mid = left + (right - left) / 2;这个也是找到中间值的方法,并且能缩小时间复杂度  int mid = (l + r) >> 1也可以找到中间值
6. if(mid*mid<=x){
           a=mid;
           left=mid+1;
重复赋值获得比mid小的最大数
7.二分查找的本质是二段性，二分查找的过程本质是对可行区间的压缩。
8.中等题的二分查找法都不满足有序不重复的数组,有序重复的数组是可以用二分查找法

50.long long mid;
0 <= x <= 2的31次方 - 1
mid*mid<=x
可以防止整数的溢出long long
* / + - 要考虑发生有溢出
-104 <= nums[i] <= 104 还是很小的

51.模拟一个旋转圆,把螺旋矩阵的过程模拟出来了

52.滑动窗口的最重要的一个思路
1.是用了一个for循环来做两个for循环的事情
2.如何移动起始位置
3.动态的去调整我们的起始位置
4.i表示起始位置,j表示终止位置
5.用于求解子数组的问题
6.两个指针却包括了很大的空间

53.前缀和是某个数的前面的元素

54.有时候还得想一些暴力解法比如两个元素进行比较看是否有重复的元素出现,并且if语句中使用&&可解决问题
for (int k = 0; k < *boardColSize; k++)
				{
					if (j != k && board[i][j] == board[i][k])
						return false;
				}

55.二维数组中是这样用列数的,最好使用数组的方式来表示元素,但长度使用的是指针表示的
for(int i=0;i<boardSize;i++){
    for(int j=0;j<*boardcloSize;j++){
            
        }
}
2.int size = matrixSize*(*matrixColSize);二维矩阵的长度是这样计算的
3.int rows = matrixSize, columns = matrixColSize[0];列的长度也可以这样表示
4.螺旋矩阵要保持好循环不变量
5.二维数组中一定要用双重for循环

56.用于把二维数组分块并进行遍历每一个子块的方法
//查找每个子块
				int x = i / 3 * 3;//每个字块中的x开端
				int y = j / 3 * 3;
for (int m = 0; m < 3; m++)
				{
					for (int n = 0; n < 3; n++)
					{
						if (x + m != i && y + n != j && board[x + m][y + n] == board[i][j])//**
							return false;
					}
				}

57.一维数组的下标转换成二维数组的下标
a为一位数组的下标,n为列的长度
int x = matrix[a / n][a % n];

58.int* runningSum(int* nums, int numsSize, int* returnSize){
    int *runningSum=(int *)malloc(sizeof(int)*numsSize);
    runningSum[0]=nums[0];
    for(int i=1;i<numsSize;i++){
        runningSum[i]=nums[i]+runningSum[i-1];
    }
    *returnSize=numsSize;
    return runningSum;
}
是一个指针值函数,但返回的却是指针地址

59.为了在 O(1) 的时间内得到每个子数组的和，可以使用前缀和

60.for(int j=i+1,k=numsSize-1;j<k) 两个指针相向运动结束的判断条件

61res[*returnSize][0]=nums[i];
                res[*returnSize][1]=nums[j];
                res[*returnSize][2]=nums[k];
                (*returnSize)++;
这是一种往二维数组存放元素的方式

61.s=nums[0]+nums[1]+nums[2]-target用来得到与目标值最接近的元素
m=abs(k);n=abs(s)用来取绝对值的函数

62.对矩阵的快速排序
int cmp(const void* a, const void* b){
    int* aa = *(int**)a;
    int* bb = *(int**)b;
    return aa[0] - bb[0];
}
qsort(intervals, intervalsSize, sizeof(int*), cmp);

62.
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    *returnColumnSizes = malloc(sizeof(int) * intervalsSize);
    int** res = malloc(sizeof(int*) * intervalsSize);
    赋值给二维数组时注意点,2表示列的长度
    (*returnColumnSizes)[(*returnSize)] = 2;
    res[(*returnSize)] = malloc(sizeof(int) * 2);
    res[(*returnSize)][0] = left;
    res[(*returnSize)][1] = right;
    (*returnSize)++;
}

63.字符串题要看由什么字符组成
s 由英文字母、数字、符号和空格组成

64.新建一个数组用来记录出现的元素,并且可以发现重复出现的个数

65.无重复字符的最长子串
左指针移动是因为右指针找到了重复的元素

66.for循环必须这样写
for (; i < maxlen; i++)
		{
			arr[i] = s[start++];
		}

67.负数总是用flag=-1与乘法来表示的return res*flag;	

68.div=INT_MAX是整数的最大值的取法









/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* rowAndMaximumOnes(int** mat, int matSize, int* matColSize, int* returnSize){
    int col = matColSize[0];
    int row = matSize;
    int cnt = 0;
    int maxNum = 0;
    int index = 0;
    int *res = (int *)malloc(sizeof(int) * 2);
    memset(res, 0, sizeof(int) * 2);
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == 1) {
                cnt++;
            }
        }
        if (maxNum < cnt) {
            index = i;
        }
        maxNum = fmax(maxNum, cnt);
        cnt = 0;
    }
    *returnSize = 2;
    res[0] = index;
    res[1] = maxNum;
    return res;
}


int maxDivScore(int* nums, int numsSize, int* divisors, int divisorsSize){
    int max = 0;
    int max1 = 0;
    for(int k = 0; k < divisorsSize; k++){
        for(int m = k + 1; m < divisorsSize; m++){
            if(divisors[k] > divisors[m]){
                int temp = divisors[m];
                divisors[m] = divisors[k];
                divisors[k] = temp;
            }
        }
    }
    for(int i = 0; i < divisorsSize; i++){
        int temp = 0;
        for(int j = 0; j < numsSize; j++){
            if(nums[j] % divisors[i] == 0)
                temp++;
                    
        }
        if(temp > max){
            max = temp;
            max1 = divisors[i];
        }
    }
    if(max1 == 0)
        return divisors[0];
    return max1;
}


int addMinimum(char * word){
    int count = 0, len = strlen(word);
    for(int i = 0; i < len; count++, i++)
    {
        while(count % 3 != word[i] - 'a')
        {
            count++;
        }
    }
    while(count % 3 != 0)
    {
        count++;
    }
    return count - len;
}




2
bool isPrime(int x)
{
    int i = 2;
    while(i * i <= x)
    {
        if(x % i == 0)
        {
            return false;
        }
        i++;
    }
    return x >= 2;
}

int diagonalPrime(int** nums, int numsSize, int* numsColSize){
    int ans = 0;
    for(int i = 0; i < numsSize; i++)
    {
        if(isPrime(nums[i][i]))
        {
            ans = fmax(ans, nums[i][i]); 
        }
        if(isPrime(nums[i][numsSize-i-1]))
        {
            ans = fmax(ans, nums[i][numsSize-i-1]);
        }
    }
    return ans;
}

# C++部分
1. 常用的类
```c++
vector<string>  //strs = ["flower","flow","flight"]
vector<vector<char>>  //{["5","3",".",".","7",".",".",".","."],["3","4","1",".","8",".",".",".","."]}
vector<char>  //["h","e","l","l","o"]

常用的类成员

reverse(nums.begin() + i + 1, nums.end()) //将从索引 i + 1 到数组末尾的元素进行反转

swap(nums[i], nums[j]) //用于交换两个值的内容

vector<vector> ans
ans.push_back({nums[first], nums[second], nums[third]}) //将一个包含三个整数的向量添加到二维向量

memset(rows,0,sizeof(rows)) //于将指定的内存区域的每个字节都设置为特定的值。在这个特定的上下文中，它被用来将数组 rows 中的每个元素都设置为 0。

常用的函数

sort(nums1.begin(), nums1.end()) //排序函数

这是一种初始化列表语法，它允许你在返回语句中用一个花括号括起来的列表来初始化一个对象，这里是一个 vector

class Solution {
public:
vector twoSum(vector& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j}; //这里有问题，这样就不用再分配一个数组了
}
}
}
return {};
}
};

或者这样

return vector{i, j};