关于LeetCode刷题及题目列表归纳-白红宇

关于LeetCode刷题及题目列表归纳

阅读量：210 次

发布时间：2019-03-01

本文共 18326 字，大约阅读时间需要 61 分钟。

leetcode题目简评

言简意赅，持续更新，利于速览复习。有导航、有代码、有细节、有引申。

已记录题目编号：1, 3, 5, 10, 15, 20, 21, 26, 53, 54, 56, 65, 72, 79, 84, 88, 101, 102, 103, 104, 105, 121, 122, 123, 125, 136, 137, 138, 145, 146, 153, 154, 155, 161, 167, 169, 170, 172, 190, 191, 198, 203, 206, 215, 217, 219, 220, 226, 229, 240, 295, 297, 343,426, 653, 946, 974, 1209

0000.资料

0001.two-sum

one-pass hash table

0003.longest-substring-without-repeating-characters

滑窗：O(n)复杂度，可以用字典储存i跳转的位置，把计算量从2n降到n，类似KMP的思想。

0005.longest-palindromic-substring

法1:中心扩散

法2:动态规划

法3:

0010.regular-expression-matching

和0072.Edit-Space类似

在这里插入图片描述

0015.3sum

方法一：先排序，在排序的基础上，虽然也是O(n^2)复杂度，但可以利用双指针尽量提高效率

方法二：hash，先预处理排序，并把重复元素合并

0020.valid-parentheses

栈的使用；利用map定义括号和反括号的映射关系

0021.merge-two-sorted-lists

，经典题，引入一个头节点

代码模版：

ListNode*head=new ListNode(0);ListNode*p=head;...return head->next;

0026.remove-duplicates-from-sorted-array

O(n)的解法，注意原地操作

0053.maximum-sum-subarray

less is more，O(n)的简洁解法，也可用分治

int maxSubArray(vector
   
    & nums) {    if(nums.size()==0)return 0;    int i=1;    int maxsum=nums[0];    int sum=maxsum;    while(i<=nums.size()-1){        if(sum<0){              sum=nums[i];        }        else            sum+=nums[i];        if(sum>=maxsum)        {            maxsum=sum;        }         i++;    }    return maxsum;}

0054.spiral-matrix

最简洁的写法

vector
   
     spiralOrder(vector
    
     
      >& matrix) {        vector
      
       ret;        int m=matrix.size();        if(!m)return ret;        int n=matrix[0].size();        int b=0,t=m-1,l=0,r=n-1;        while(1){            for(int j=l;j<=r;j++)ret.push_back(matrix[b][j]);            if(++b>t)break;            for(int i=b;i<=t;i++)ret.push_back(matrix[i][r]);            if(--r
       
        =l;j--)ret.push_back(matrix[t][j]);            if(--t
        
         =b;i--)ret.push_back(matrix[i][l]); if(++l>r)break; } return ret;}

0056.merge-intervals

先sort再遍历

复习sort的cmp函数定义（这题不需要cmp函数）

static bool cmp1(vector
   
     &a, vector
    
      &b){		return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);}

0065.valid-number

，书上的代码结构很简洁，值得学习

int pointer;bool isNumber(string s) {    if(s=="")return -1;    scanSpace(s);    bool numeric=scanInteger(s);    if(s[pointer]=='.'){        ++pointer;        numeric=scanUnsignedInteger(s)||numeric;        //用||因为整数、小数部分有一即可    }    if(s[pointer]=='e'||s[pointer]=='E'){        ++pointer;        numeric=numeric&&scanInteger(s);    }    scanSpace(s);    return numeric&&s[pointer]=='\0';}

也可以用有限状态机来做

0072.edit-distance

很漂亮的动态规划

$KaTeX parse error: Undefined control sequence: \notag at position 108: …i]\\\end{cases}\̲n̲o̲t̲a̲g̲ ̲$

0079.word-search

经典回溯法

0084.largest-rectangle-in-histogram

单调栈，，但有小错，纠正代码如下：

int largestRectangleArea(vector
   
     &heights){    stack
    
      st;    int top = 0;    int maxarea = 0;    heights.insert(heights.begin(), 0);    heights.push_back(0);  //左右插0，利于边界条件    for (int i = 0; i < heights.size(); i++)    {        top = i;        while (!st.empty() && heights[i] < heights[st.top()])        {            top = st.top();            st.pop();            maxarea = max(maxarea, heights[top] * (i-1 - st.top()));        }//求出栈处往左右延伸的最大矩形面积        st.push(i);    }    return maxarea;}

单调栈模版

stack
   
     st;//此处一般需要给数组最后添加结束标志符for (遍历这个数组){  while (栈不为空 && 栈顶元素小于当前元素)  {    栈顶元素出栈;    更新结果;  }  当前数据入栈;}

0088.merge-sorted-array

注意原地操作

0101.symmetric-tree

递归

bool isSymmetric(TreeNode* root) {    if(!root)return 1;    else return isSymmetric1(root->left,root->right);}bool isSymmetric1(TreeNode* a,TreeNode* b) {    if(!(a||b))return 1;    else if(!(a&&b))return 0;    else return a->val==b->val&&isSymmetric1(a->left,b->right)&&isSymmetric1(a->right,b->left);}

0102.binary-tree-level-order-traversal (medium)

队列，设变量curNum和nextNum分别保存本层和下层的数的个数

引申：
- 方法一：clear
- 方法二：vector<int>().swap(nums);
- 方法三：利用代码块和临时变量
  { vector<int> tmp = curLevel; curLevel.swap(tmp); }
- clear虽然不会deallocate释放空间，但是会destroy执行析构函数，所以可以用同一个空间构造节点，如果swap了就要重新分配空间再构造节点。由于本题是对同一个vector的重复利用，可以直接用clear();，空间复杂度是单层最大节点数。
- 如果要每次都释放空间，也可以用res.emplace_back(std::move(curLevel))，涉及, , ,

0103.binary-tree-zigzag-level-order-traversal

在0102的基础上保存层数的奇偶性

0104.maximum-depth-of-binary-tree

方法一：递归

方法二：BFS，queue

方法三：DFS，stack，，或者python的tuple

0105. construct-binary-tree-from-preorder-and-inorder-traversal

找到中间节点，递归

0121. best-time-to-buy-and-sell-stock

O(n)遍历，记录之前的数组最小值

0122. best-time-to-buy-and-sell-stock-ii

0123. best-time-to-buy-and-sell-stock-iii

，本质上是贪心的思想，先记录maxp的位置，一定会取到股票的最大最小值high、low处，再做处理

class Solution:    def maxProfit(self, prices: List[int]) -> int:        def max_p(ps):            if not ps or len(ps) == 1:                return 0, 0, 0            very_low = 0            low = 0            high = 0            profit = 0            for i, p in enumerate(ps):                if p < ps[low]:                    low = i                elif p - ps[low] > profit:                    high = i                    very_low = low                    profit = p - ps[low]                                return very_low, high, profit                low, high, profit = max_p(prices)        _, _, profit_right = max_p(prices[0:low])        _, _, profit_left = max_p(prices[high+1:])        _, _, profit_middle = max_p(prices[low:high+1][::-1])                return profit + max(profit_left, profit_middle, profit_right)

0125.valid-palindrome

def isPalindrome(self, s: str) -> bool:		s = ''.join(i for i in s if i.isalnum()).lower()		return s == s[::-1]

0136.single-number

位运算，xor性质

0137.single-number-II

非常巧妙的方法，多设一个数记录状态，位运算与有限状态机的结合，本质上，位运算的意义在于将n位信息转化为O(1)

def singleNumber(self, nums: List[int]) -> int:    seen_once = seen_twice = 0    for num in nums:        # first appearance:         # add num to seen_once, don't add to seen_twice because of presence in seen_once        # second appearance:         # remove num from seen_once, add num to seen_twice            # third appearance:         # don't add to seen_once because of presence in seen_twice, remove num from seen_twice                seen_once = ~seen_twice & (seen_once ^ num)        seen_twice = ~seen_once & (seen_twice ^ num)    return seen_once

0138.copy-list-with-random-pointer

思路值得学习，在原链表的主线上复制节点，进行删改操作。

0145.binary-tree-postorder-traversal

方法一：教科书，先一路向左，用tag记录节点的右子树是否遍历

struct WTreeNode{TreeNode* TNode;bool tag;};vector
   
     postorderTraversal(TreeNode* root) {    vector
    
      ret;    stack
     
      s;    TreeNode* p=root;    if(root==NULL) return ret;    WTreeNode* l;    while(!s.empty()||p){        if (p!=NULL){ //左子树不断入栈            l=new WTreeNode;             l->TNode=p;l->tag=0;            s.push(l);            p=p->left;        }        else{            l=s.top();            s.pop();            if(l->tag==1){                ret.push_back(l->TNode->val);            }            else{   //右子树没输出                l->tag=1;                s.push(l);                p=l->TNode->right;            }        }      }    return ret;}

引申：二叉树非递归遍历的模版

while(!s.empty()||p){	if (p!=NULL){	}	else{	}}

方法二：后序遍历是左右根，倒过来是根右左，相当于左右遍历顺序相反的DFS，用栈即可，得到结果再reverse

vector
   
     postorderTraversal1(TreeNode* root) {    vector
    
      ret;    stack
     
      s;    vector
      
       invert;    s.push(root);    while(!s.empty()){        TreeNode *p=s.top();s.pop();        if(p!=NULL){            invert.push_back(p->val);            s.push(p->left);            s.push(p->right);        }    }    reverse(invert.begin(),invert.end());    return invert;}

0146.lru-cache

双向链表+Map，自己实现双向链表可以高效实现move to head操作，也可以用STL的list

0153.find-minimum-in-rotated-sorted-array

二分法，注意相等的情况

0154.find-minimum-in-rotated-sorted-array-ii

如果有重复数字，则难以判断mid是在左边还是右边，r-=1是解决这一问题的关键代码

int findMin(vector
   
    & numbers) {    //if(numbers.size()==0)return -1;    int l=0,r=numbers.size()-1;    int mid;    while(l
    
     numbers[r]) l=mid;        else if(numbers[mid]

0155.min-stack

用另一个栈记录min的变化值

0161.one-edit-distance

遍历较短的数字，直到遇到第一个和长数组对应位置不等的元素，再做判断处理

0167.two-sum-ii-input-array-is-sorted

先二分查找到中间，再往两边扩散，这样当N很大时时间复杂度近似 $O(log_{2}N)$

0169. majority-element

方法一：hashmap

方法二：随机算法，先取再验证

方法三：：核心是利用这个数据的前缀特性，用军队打仗理解；每个非众数都会和一个数配对

int majorityElement(vector
   
     nums) {    int solider = nums[0];    int count=0;    for(int i=0;i

0170.two-sum-iii-data-structure-design

与两数之和联系的数据结构

有序数组：因此可以用sort排序，或者用multiset维持数据结构的有序性

Hash表

0172.factorial-trailing-zeroes

$n/5+n/5^2+n/5^3+…$ 递归即可

0190.reverse-bits

法一：位运算

uint32_t reverseBits(uint32_t n) { //注意定义uint32_t，如果是int要小心算术移位    unsigned int t = 0;     int i = 0;    while (n >= 1)    {        t = (t << 1) | (n & 1);        i++;        n = n >> 1;    }    if (i == 0)  //细节：左移不要越界        return t;    return t << (32 - i);}

法二：按字节操作

def reverseByte(byte):    return (byte * 0x0202020202 & 0x010884422010) % 1023

0191.number-of-1-bits

n=n&(n-1);

易错点：return n&1+hammingWeight(n>>=1);
- 位运算优先级很低，n&1应该打括号

复习

基本的优先级需要记住：
- 指针最优，单目运算优于双目运算，如正负号。
- 先算术运算，后移位运算，最后位运算。1 << 3 + 2 & 7等价于 (1 << (3 + 2))&7，逻辑运算最后结合。

0198.house-robber

简单DP

0203.remove-linked-list-elements

直接遍历，也可以用sentinel node简化操作（在LRU cache也有应用）

class Solution {public:    ListNode* deleteNode(ListNode* head, int val) {        if(head==NULL)return NULL;        if(head->val==val)return head->next;        ListNode *p=head;        while(p->next){            if(p->next->val==val){                p->next=p->next->next;                break;            }            p=p->next;        }        return head;    }};

0206.reverse-linked-list

ListNode* reverseList(ListNode* head) {    if(!head||!head->next) return head;    ListNode *p=head,*q=head->next;   	p->next=NULL;  	ListNode* temp;    while(q!=NULL){    	temp=q->next;			q->next=p;			p=q;      q=temp;    }    return p;}

0215.kth-largest-element-in-an-array

方法1: 快排

方法2: 利用小顶堆，保证size不大于k; C++中用priority_queue, 配合unordered_map

方法3: 快排变体，

引申：堆的实现

#define ElemType pair
   
    class CMaxHeap {  //小顶堆private:	ElemType *heap;	int heapSize, MaxHeapSize;public:    CMaxHeap(int size) {        heapSize = 0;        MaxHeapSize = size;        heap = new ElemType[size + 1];    }    ~CMaxHeap() { delete[] heap; }    void ClearHeap() { heapSize = 0; }    bool IsEmpty() { return heapSize == 0; }    bool IsFull() { return heapSize == MaxHeapSize; }    int getLength() { return heapSize; }    ElemType top() { return heap[0]; }    void push(ElemType e);	ElemType pop();	//去堆顶元素	void FixUp(int k);	void FixDown(int k);};void CMaxHeap::FixDown(int k) {	int i;	i = 2 * k + 1;	while (i < heapSize) {		if (i < heapSize - 1 && heap[i] > heap[i + 1])			i++;			//取孩子结点中较小者		if (heap[k] < heap[i])			break;		swap(heap[k], heap[i]);		k = i;		i = 2 * k + 1;	}}void CMaxHeap::FixUp(int k) {	int i;	i = (k - 1) / 2;	while (k > 0 && heap[i] > heap[k]) {		swap(heap[k], heap[i]);		k = i;		i = (k - 1) / 2;	}}void CMaxHeap::push(ElemType e) {	heap[heapSize] = e;	heapSize++;	FixUp(heapSize - 1);}ElemType CMaxHeap::pop() { //去掉堆顶	swap(heap[0], heap[heapSize - 1]);	heapSize--;	FixDown(0);	return heap[heapSize];}void heap_sort(ElemType *a, int l, int r) {//	int N = r - l;	ElemType *p = a + l;	for (int k = (N - 1) / 2; k >= 0; k--)		FixDown(p, k, N);	while (N > 0) {		exch(p, p + N);		N--;		FixDown(p, 0, N);	}}

引申：快排代码

template
   
    void quick_sort(T*a, int l, int r) {//递归实现	if (r <= l)return;	int i = partition(a, l, r);//划分操作	quick_sort(a, l, i - 1);	quick_sort(a, i + 1, r);}template
    
     int partition(T*a, int l, int r) {//思想，从两边向中间扫描	int i = l - 1,j = r;	T e = a[r];//最右端元素为划分元素	while (1) {		while (a[++i] < e);		while (e < a[--j])if (j == left)break;		if (i >= j)break;		exch(a + i, a + j);	}	exch(a + i, a + right);	return i;}//改进：中间元素法和小序列处理template
     
      void quick_sort(T*a, int l, int r) {//递归实现	if (r-l< 5)return;	exch(a[(l + r) / 2], a[r - 1]);	compExch(a[l], a[r - 1]);//取三个值的中间值	compExch(a[l], a[r]);	compExch(a[r], a[r - 1]);	int i = partition(a, l, r);//划分操作	quick_sort(a, l, i - 1);	quick_sort(a, i + 1, r);}

0217.contains-duplicate

排序或者hash

0219.contains-duplicate-ii

本题关注点在于是否有邻近的重复，因此除了用hash，可以尝试利用数据的邻近特性，例如JAVA的treeset：self-balancing Binary Search Tree (BST)，C++的multiset

0220.contains-duplicate-iii

方法一：+滑窗法，利用

bool containsNearbyAlmostDuplicate(vector
   
    & nums, int k, int t) {    int size = nums.size(); if(size <= 1) return false;    if(k==0) return t==0;    multiset
    
      window;    //construct the first window    for(int i=0; i
     
      & window, int val, int t) {    auto itlower = window.lower_bound(val);    if(itlower != window.end() && (*itlower)-val <= t) return true;    if(itlower != window.begin()) {        --itlower;        if(val - (*itlower) <= t) return true;    }    return false;}

方法二：巧妙的方法，注意到数据结构特点，要求没有邻近数，因此可以用bucket数据结构
- 引申：桶排序 =>

public class Solution {
       // Get the ID of the bucket from element value x and bucket width w    // In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.    private long getID(long x, long w) {
           return x < 0 ? (x + 1) / w - 1 : x / w;    }    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
           if (t < 0) return false;        Map
   
     d = new HashMap<>();        long w = (long)t + 1;        for (int i = 0; i < nums.length; ++i) {
               long m = getID(nums[i], w);            // check if bucket m is empty, each bucket may contain at most one element            if (d.containsKey(m))                return true;            // check the neighbor buckets for almost duplicate            if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)                return true;            if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)                return true;            // now bucket m is empty and no almost duplicate in neighbor buckets            d.put(m, (long)nums[i]);            if (i >= k) d.remove(getID(nums[i - k], w));        }        return false;    }}

0226.invert-binary-tree

0229.majority-element-ii

Boyer-Moore，

0240.search-a-2d-matrix-ii

关键在于起点的选取，从左下角或者右上角开始

0295.find-median-from-data-stream

思路1: AVL树的平衡因子改为左、右子树节点数目之差

思路2: 左边最大堆，右边最小堆
- 书上代码：push_heap和pop_heap
- 也可直接用priority_queue，注意小顶堆的定义：priority_queue<int, vector<int>, greater<int>> hi;

min.push_back(num);push_heap(min.begin(),min.end(),greater
   
    ());

字节后端面试：变式题，在本题基础上增加erase功能，需要把堆改成BST（即set），保证删除性能

0297.serialize-and-deserialize-binary-tree

思路上可以使用DFS或者BFS

C++具体实现，利用stringstream

class Codec {public:    // Encodes a tree to a single string.    string serialize(TreeNode* root) {        if(root==NULL)return "";        ostringstream ostr;        queue
   
    q;        TreeNode*temp;        q.push(root);        int curNum=1;        while(!q.empty()){            temp=q.front();            q.pop();            if(!temp){                if(curNum) ostr<<"null,";            }            else {                ostr<
    
     val<<",";                curNum--;                q.push(temp->left);                if(temp->left)curNum++;                q.push(temp->right);                if(temp->right)curNum++;            }        }        return ostr.str();    }    // Decodes your encoded data to tree.    TreeNode* deserialize(string data) {        if(data=="")return NULL;        istringstream istr(data);        queue
     
      q;        TreeNode* root=new TreeNode;        TreeNode **number=new TreeNode*;        if(ReadStream (istr,number)){            root=number[0];            if(!root)return NULL;            q.push(root);        }        else return NULL;        TreeNode *temp;        while(!q.empty()){            temp=q.front();            q.pop();            if(!temp)continue;            if(ReadStream(istr,number)){                temp->left=number[0];                q.push(temp->left);            }            else break;            if(ReadStream(istr,number)){                temp->right=number[0];                q.push(temp->right);            }            else break;        }        return root;    }    bool ReadStream(istringstream &istr,TreeNode **number){        string s;        if(getline(istr,s,',')){            if(s=="null")number[0]=NULL;            else number[0]=new TreeNode(stoi(s));            return 1;        }        return 0;    }};

0343.integer-break

简单DP

0426.convert-binary-search-tree-to-sorted-doubly-linked-list

方法一：二叉搜索树特性，中序遍历的递归/非递归实现，用nonlocal last记录上一次遍历的末尾节点

方法二：用flag指示返回最左/最右节点，递归后序遍历操作

Node *treeToDoublyList(Node *root){    root = treeToDoublyList(root, 0);    if (root == NULL)        return NULL;    Node *p = root;    while (p->right) p = p->right;    p->right = root;    root->left = p;    return root;}Node *treeToDoublyList(Node *root, int flag){ //flag=0:left, flag=1:right    if (root == NULL)        return NULL;    Node *l = treeToDoublyList(root->left, 1);    Node *r = treeToDoublyList(root->right, 0);    root->left = l;    root->right = r;    if (l)        l->right = root;    if (r)        r->left = root;    Node *p = root;    if (!flag) while (p->left) p = p->left;    else while (p->right) p = p->right;    return p;}

0653.two-sum-iv-input-is-a-bst

我用的方法比较奇怪：分治的思想，利用BST特性减少运算量，直接递归即可通过。

其它的常见方法：
- 方法一：使用HashSet
- 方法二：中序遍历BST树，转化为排序数组的两数之和问题

class Solution {public:    typedef TreeNode* Link;    bool searchR(Link p,int x){ //判断子树内是否存在x        if(p==NULL)return 0;        int key=p->val;        if(x==key)return 1;        if(x
   
    left,x);        else return searchR(p->right,x);    }    bool findTarget(TreeNode* root, int k) {        int result=0;        if(root==NULL)return 0;        if(k>2*root->val){  //利用BST特性减少运算量            if(findTarget(root->right,k))return 1;        }        else if(k<2*root->val){            if(findTarget(root->left,k))return 1;        }        if(searchR(root->left,k-root->val))return 1;        if(searchR(root->right,k-root->val))return 1;        if(findinAB(root->left,root->right,k))            return 1;        return 0;    }        bool findinAB(TreeNode* A,TreeNode* B,int k){ //在A、B中各取一个节点        int result=0;        if(A==NULL||B==NULL)            return 0;        if(searchR(B,k-A->val))return 1;        if(findinAB(A->left,B,k))return 1;        if(findinAB(A->right,B,k))return 1;        return 0;    }};