LeetCode—剑指 Offer学习计划

Author： wzy1999
发布时间：December 26, 2021
1171 views
No comments
11621 words
Categories： LeetCode

持续更新中......

# 第 1 天 栈与队列（简单）

## [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

```cpp
class CQueue {
public:
    CQueue() {

}
    stack<int>s1,s2;
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        if(s2.empty())
            return -1;
        int tmp=s2.top();
        s2.pop();
        return tmp;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
```

## [剑指 Offer 30. 包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)

构造一个辅助栈，使辅助栈顶元素始终为当前栈内元素的最小值

```cpp
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    stack<int>st;
    stack<int>m;
    void push(int x) {
        st.push(x);
        if(m.empty()||m.top()>=x)
            m.push(x);
    }
    
    void pop() {
        if(st.top()==m.top())
            m.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int min() {
        return m.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */
```

# 第 2 天  链表（简单）

## [剑指 Offer 06. 从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)

存入数组中然后反转一下

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int>v;
        while(head)
        {
            v.push_back(head->val);
            head=head->next;
        }
        reverse(v.begin(),v.end());
        return v;
    }
};
```

## [剑指 Offer 24. 反转链表](https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/)

让当前节点的下一个节点指向上一个节点，使用一个临时的指针来实现

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cnt=head,*ans=NULL;
        while(cnt)
        {
            ListNode *tmp=cnt->next;
            cnt->next=ans;
            ans=cnt;
            cnt=tmp;
        }
        return ans;
    }
};
```

## [剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)

待补

# 第三天 字符串（简单）

## [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)

直接遍历

```cpp
class Solution {
public:
    string replaceSpace(string s) {
        string ans;
        for(auto i:s)
        {
            if(i==' ')
                ans+="%20";
            else
                ans+=i;
        }
        return ans;
    }
};
```

## [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

```cpp
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string ans="";
        ans+=s.substr(n,s.size());
        ans+=s.substr(0,n);
        return ans;
    }
};
```

# 第 4 天 查找算法（简单）

## [剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

构建元素的索引和值为一对一的关系，如果当前索引已经有值并且和当前值相同，则出现多次

```cpp
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int l=nums.size();
        int i=0;
        while(i<l)
        {
            if(nums[i]==i)
            {
                i++;
                continue;
            }
            if(nums[nums[i]]==nums[i])
                return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }
};
```

## [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)

`lower_bound`和`upper_bound`的使用

```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l_place=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
        int r_place=upper_bound(nums.begin(),nums.end(),target)-nums.begin();
        return r_place-l_place;
    }
};
```

## [剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/)

### 遍历

```cpp
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=nums.size();
        for(int i=0;i<l;i++)
        {
            if(nums[i]!=i)
                return i;
        }
        return l;
    }
};
```

### 二分

```cpp
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(nums[mid]>mid)
                r=mid-1;
            else
                l=mid+1;
        }
        return l;
    }
};
```

# 第 5 天 查找算法（中等）

## [剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)

### 二分

对每一行进行二分，时间复读$O(n \log(m))$
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-94ef18be7b6e5f2f85132f69665154a029" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-94ef18be7b6e5f2f85132f69665154a029" class="collapse collapse-content"><p></p>

```cpp
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(auto i:matrix)
        {
            int place=lower_bound(i.begin(),i.end(),target)-i.begin();
            if(place!=i.size()&&i[place]==target)
                return true;
        }
        return false;
    }
};
```

### 线性查找

从右上角开始，如果当前元素比target大，往左走；如果比target小，向下走。时间复杂度为$O(n+m)$
<span style='color:red'>注意数组为空的情况</span>

```cpp
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();
        if(!n) return false;
        int m=matrix[0].size();
        int i=0,j=m-1;
        while(i<n&&j>=0)
        {
            if(matrix[i][j]<target)
                i++;
            else if(matrix[i][j]>target)
                j--;
            else
                return true;
        }
        return false;
    }
};
```

## [剑指 Offer 11. 旋转数组的最小数字](https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)

### 遍历

```cpp
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int ans=numbers[0];
        for(auto i:numbers)
            ans=min(ans,i);
        return ans;
    }
};
```

### 二分

注意相等的情况，需要遍历

```cpp
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l=0,r=numbers.size()-1;
        int ans=10000000;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(numbers[mid]>numbers[r])
                l=mid+1;
            else if(numbers[mid]<numbers[r])
                r=mid;
            else
            {
                for(int i=l;i<=r;i++)
                    ans=min(ans,numbers[i]);
                return ans;
            }
        }
        return numbers[l];
    }
};
```

## [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/)

直接用`map`存就行，可以把字符去一下重优化时间
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-87894366db904936b290e6045162a6c226" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-87894366db904936b290e6045162a6c226" class="collapse collapse-content"><p></p>

```cpp
class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char,int>mp;
        char ans=' ';
        vector<char>v;
        for(auto i:s)
        {
            if(!mp[i])
                v.push_back(i);
            mp[i]++;
        }
        for(auto i:v)
        {
            if(mp[i]==1)
                return i;
        }
        return ans;
    }
};
```

# 第 6 天 搜索与回溯算法（简单）

## [剑指 Offer 32 - I. 从上到下打印二叉树](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*>que;
        que.push(root);
        vector<int>ans;
        if(!root)
            return ans;
        while(!que.empty())
        {
            TreeNode *tmp=que.front();
            que.pop();
            if(tmp->left)
                que.push(tmp->left);
            if(tmp->right)
                que.push(tmp->right);
            ans.push_back(tmp->val);
        }
        return ans;
    }
};
```

## [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)

在当前节点的下一层放入队列之前，把当前节点存下来

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*>que;
        que.push(root);
        vector<vector<int> >ans;
        while(!que.empty())
        {
            vector<int>tmp;
            int sz=que.size();
            for(int i=0;i<sz;i++)
            {
                TreeNode *now=que.front();
                tmp.push_back(now->val);
                que.pop();
                if(now->left)
                    que.push(now->left);
                if(now->right)
                    que.push(now->right);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};
```

## [剑指 Offer 32 - III. 从上到下打印二叉树 III](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)

和上一题一样，只不过在存入到最终结果之前需要判断一下当前在第几层，翻转一下
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-728a0d45dc4426f03f27b90cb0edff3689" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-728a0d45dc4426f03f27b90cb0edff3689" class="collapse collapse-content"><p></p>

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*>que;
        que.push(root);
        vector<vector<int> >ans;
        while(!que.empty())
        {
            vector<int>tmp;
            int sz=que.size();
            for(int i=0;i<sz;i++)
            {
                TreeNode *now=que.front();
                tmp.push_back(now->val);
                que.pop();
                if(now->left)
                    que.push(now->left);
                if(now->right)
                    que.push(now->right);
            }
            if(ans.size()%2)
                reverse(tmp.begin(),tmp.end());
            ans.push_back(tmp);
        }
        return ans;
    }
};
```

# 第 7 天  搜索与回溯算法（简单）

## [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/)

先从A开始往下遍历，如果出现了与B的根节点相等的节点，开始A和B同时向下递归

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A||!B)
            return false;
        if(dfs(A,B))
            return true;
        return isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
    bool dfs(TreeNode *A,TreeNode *B)
    {
        if(!B)
            return true;
        if(!A)
            return false;
        if(A->val!=B->val)
            return false;
        return dfs(A->left,B->left)&&dfs(A->right,B->right);
    }
};
```

## [剑指 Offer 27. 二叉树的镜像](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/)

### BFS

用栈辅助遍历来实现二叉树的镜像
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-7a88737e4f97465f873833f8a03d335579" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-7a88737e4f97465f873833f8a03d335579" class="collapse collapse-content"><p></p>

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return root;
        stack<TreeNode*>st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode *node=st.top();
            st.pop();
            if(node->left)
                st.push(node->left);
            if(node->right)
                st.push(node->right);
            TreeNode *tmp=node->left;
            node->left=node->right;
            node->right=tmp;
        }
        return root;
    }
};
```

### DFS

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return root;
        TreeNode *node=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(node);
        return root;
    }
};
```

## [剑指 Offer 28. 对称的二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)

对左子树和右子树同时向下遍历
<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-626b8098231a40496a58d4e1c4f4231722" aria-expanded="true"><div class="accordion-toggle"><span style="">代码</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-626b8098231a40496a58d4e1c4f4231722" class="collapse collapse-content"><p></p>

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode *A,TreeNode *B)
    {
        if(!A&&!B)
            return true;
        if((!A||!B)||A->val!=B->val)
            return false;
        return dfs(A->left,B->right)&&dfs(A->right,B->left);
    }
};
```

# 第 8 天  动态规划（简单）

## [剑指 Offer 10- I. 斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)

别用递归写就行了

```cpp
class Solution {
public:
    int a[3];
    const int mod=1e9+7;
    int fib(int n) {
        if(n<2)
            return n;
        a[0]=0;a[1]=1;
        for(int i=2;i<=n;i++)
        {
            a[2]=(a[1]%mod+a[0]%mod)%mod;
            a[0]=a[1];a[1]=a[2];
        }
        return a[2];
    }
};
```

## [剑指 Offer 10- II. 青蛙跳台阶问题](https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)

$dp[i]=dp[i-1]+dp[i-2]$

```cpp
class Solution {
public:
    int dp[101];
    const int mod=1e9+7;
    int numWays(int n) {
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=2;i<=n;i++)
            dp[i]=(dp[i-1]+dp[i-2])%mod;
        return dp[n];
    }
};
```

## [剑指 Offer 63. 股票的最大利润](https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/)

不断更新当前元素与当前最小值的差值就行了

```cpp
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sz=prices.size();
        if(!sz)
            return 0;
        int m=prices[0];
        int ans=0;
        for(int i=1;i<sz;i++)
        {
            m=min(prices[i],m);
            ans=max(ans,prices[i]-m);
        }
        return ans;
    }
};
```

# 第 9 天 动态规划（中等）

## [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)

```cpp
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0];
        int tmp=0;
        for(auto i:nums)
        {
            tmp=max(tmp+i,i);
            ans=max(ans,tmp);
        }
        return ans;
    }
};
```

## [剑指 Offer 47. 礼物的最大价值](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/)

$dp[i][j]=\max\{dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j],dp[i][j] \}$

```cpp
class Solution {
public:
    int dp[202][202];
    int maxValue(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        dp[0][0]=grid[0][0];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(!i&&!j)
                    continue;
                if(!i)
                    dp[i][j]=max(dp[i][j-1]+grid[i][j],dp[i][j]);
                else if(!j)
                    dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j]);
                else 
                    dp[i][j]=max({dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j],dp[i][j]});
            }
        }
        return dp[n-1][m-1];
    }
};
```

# 第 10 天 动态规划（中等）

## [剑指 Offer 46. 把数字翻译成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/)

$dp[i]$表示在位置$i$有多少种方案，如果$i$和$i-1$位置能够在一起翻译成字母，则$dp[i]=dp[i-1]+dp[i-2]$，否则$dp[i]=dp[i-1]$

```cpp
class Solution {
public:
    int dp[20];
    int translateNum(int num) {
        if(num<10)
            return 1;
        vector<int>v;
        while(num)
        {
            v.push_back(num%10);
            num/=10;
        }
        reverse(v.begin(),v.end());
        int sz=v.size();
        dp[0]=1;
        if(v[0]*10+v[1]<26)
            dp[1]=2;
        else
            dp[1]=1;
        for(int i=2;i<sz;i++)
        {
            if(v[i-1]*10+v[i]<26&&v[i-1]*10+v[i]>=10)
                dp[i]=dp[i-1]+dp[i-2];
            else
                dp[i]=dp[i-1];
        }
        return dp[sz-1];
    }
};
```

## [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)

向后遍历，保证遍历过程中子字符串包含的字符只出现了一次。当出现第二次时，让子字符串开始的位置变成该字符出现第二次的位置。

```cpp
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l=s.length();
        map<char,int>mp;
        int ans=0;
        int place=0;
        for(int i=0;i<l;i++)
        {
            if(mp[s[i]])
                place=max(place,mp[s[i]]);
            ans=max(i-place+1,ans);
            mp[s[i]]=i+1;
        }
        return ans;
    }
};
```

# 第 11 天 双指针（简单）

## [剑指 Offer 18. 删除链表的节点](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/)

设置一个当前节点的前驱结点，如果当前节点为删除节点，停止查找，让前驱结点的下一个节点变成当前节点的下一个节点，即可实现删除

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val==val)
            return head->next;
        ListNode *pre=head,*now=head->next;
        while(now->val!=val&&now)
            pre=now,now=now->next;
        if(now)
            pre->next=now->next;
        return head;
    }
};
```

## [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

设置两个所指位置不同的指针，保证在前面的指针和在后面的指针相差$k$个节点，当在前面的指针指向链表末尾时，在后面的指针恰好指向倒数第$k$个节点

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *slow=head,*fast=head;
        for(int i=0;i<k;i++)
        {
            if(!fast)
                return NULL;
            fast=fast->next;
        }
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};
```

# 第 12 天 双指针（简单）

## [剑指 Offer 25. 合并两个排序的链表](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)

同时遍历两个链表，每次添加两个链表中较小的那个节点，知道有一个链表遍历结束

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(0,NULL);
        ListNode *tmp=head;
        while(l1&&l2)
        {
            if(l1->val>l2->val)
            {
                tmp->next=l2;
                l2=l2->next;
            }
            else
            {
                tmp->next=l1;
                l1=l1->next;
            }
            tmp=tmp->next;
        }
        if(l2)
            tmp->next=l2;
        if(l1)
            tmp->next=l1;
        return head->next;
    }
};
```

## [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)

双指针，[官方题解](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/liang-ge-lian-biao-de-di-yi-ge-gong-gong-pzbs/)有证明

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB)
            return NULL;
        ListNode *nodeA=headA,*nodeB=headB;
        while(nodeA!=nodeB)
        {
            nodeA=nodeA?nodeA->next:headB;
            nodeB=nodeB?nodeB->next:headA;
        }
        return nodeA;
    }
};
```

# 第 13 天 双指针（简单）

## [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)

两个指针分别指向数组的开头和结尾，如果左边的数为偶数，右边的数为奇数，交换两数的位置；如果左边为奇数，左指针右移；如果右边为偶数，右指针左移

```cpp
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            if(!(nums[l]%2)&&nums[r]%2)
                swap(nums[l++],nums[r--]);
            else if(nums[l]%2)
                l++;
            else if(!(nums[r]%2))
                r--;
        }
        return nums;
    }
};
```

## [剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)

### 哈希

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int>mp;
        for(auto i:nums)
        {
            if(mp[target-i])
                return {i,target-i};
            mp[i]++;
        }
        return {};
    }
};
```

### 双指针

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            if(nums[l]+nums[r]<target)
                l++;
            else if(nums[l]+nums[r]>target)
                r--;
            else return {nums[l],nums[r]};
        }
        return {};
    }
};
```

## [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/)

直接py

cpp的话用栈来做吧，挺麻烦的

```python
class Solution:
    def reverseWords(self, s: str) -> str:
        s=s.strip().split()
        s.reverse()
        return ' '.join(s)
```

Last modification：January 2, 2022

如果觉得我的文章对你有用，请随意赞赏

LeetCode—剑指 Offer学习计划

wzy1999 • 2021 年 12 月 26 日

持续更新中......

# 第 1 天 栈与队列（简单）

## [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

```cpp
class CQueue {
public:
    CQueue() {

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
```

## [剑指 Offer 30. 包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)

构造一个辅助栈，使辅助栈顶元素始终为当前栈内元素的最小值

# 第 2 天  链表（简单）

## [剑指 Offer 06. 从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)

存入数组中然后反转一下

## [剑指 Offer 24. 反转链表](https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/)

让当前节点的下一个节点指向上一个节点，使用一个临时的指针来实现

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cnt=head,*ans=NULL;
        while(cnt)
        {
            ListNode *tmp=cnt->next;
            cnt->next=ans;
            ans=cnt;
            cnt=tmp;
        }
        return ans;
    }
};
```

## [剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)

待补

# 第三天 字符串（简单）

## [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)

直接遍历

## [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

```cpp
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string ans="";
        ans+=s.substr(n,s.size());
        ans+=s.substr(0,n);
        return ans;
    }
};
```

# 第 4 天 查找算法（简单）

## [剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

构建元素的索引和值为一对一的关系，如果当前索引已经有值并且和当前值相同，则出现多次

## [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)

`lower_bound`和`upper_bound`的使用

## [剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/)

### 遍历

### 二分

# 第 5 天 查找算法（中等）

## [剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)

### 二分

### 线性查找

从右上角开始，如果当前元素比target大，往左走；如果比target小，向下走。时间复杂度为$O(n+m)$
<span style='color:red'>注意数组为空的情况</span>

## [剑指 Offer 11. 旋转数组的最小数字](https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)

### 遍历

```cpp
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int ans=numbers[0];
        for(auto i:numbers)
            ans=min(ans,i);
        return ans;
    }
};
```

### 二分

注意相等的情况，需要遍历

## [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/)

# 第 6 天 搜索与回溯算法（简单）

## [剑指 Offer 32 - I. 从上到下打印二叉树](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)

## [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)

在当前节点的下一层放入队列之前，把当前节点存下来

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*>que;
        que.push(root);
        vector<vector<int> >ans;
        while(!que.empty())
        {
            vector<int>tmp;
            int sz=que.size();
            for(int i=0;i<sz;i++)
            {
                TreeNode *now=que.front();
                tmp.push_back(now->val);
                que.pop();
                if(now->left)
                    que.push(now->left);
                if(now->right)
                    que.push(now->right);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};
```

## [剑指 Offer 32 - III. 从上到下打印二叉树 III](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*>que;
        que.push(root);
        vector<vector<int> >ans;
        while(!que.empty())
        {
            vector<int>tmp;
            int sz=que.size();
            for(int i=0;i<sz;i++)
            {
                TreeNode *now=que.front();
                tmp.push_back(now->val);
                que.pop();
                if(now->left)
                    que.push(now->left);
                if(now->right)
                    que.push(now->right);
            }
            if(ans.size()%2)
                reverse(tmp.begin(),tmp.end());
            ans.push_back(tmp);
        }
        return ans;
    }
};
```

# 第 7 天  搜索与回溯算法（简单）

## [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/)

先从A开始往下遍历，如果出现了与B的根节点相等的节点，开始A和B同时向下递归

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A||!B)
            return false;
        if(dfs(A,B))
            return true;
        return isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
    bool dfs(TreeNode *A,TreeNode *B)
    {
        if(!B)
            return true;
        if(!A)
            return false;
        if(A->val!=B->val)
            return false;
        return dfs(A->left,B->left)&&dfs(A->right,B->right);
    }
};
```

## [剑指 Offer 27. 二叉树的镜像](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/)

### BFS

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return root;
        stack<TreeNode*>st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode *node=st.top();
            st.pop();
            if(node->left)
                st.push(node->left);
            if(node->right)
                st.push(node->right);
            TreeNode *tmp=node->left;
            node->left=node->right;
            node->right=tmp;
        }
        return root;
    }
};
```

### DFS

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return root;
        TreeNode *node=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(node);
        return root;
    }
};
```

## [剑指 Offer 28. 对称的二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode *A,TreeNode *B)
    {
        if(!A&&!B)
            return true;
        if((!A||!B)||A->val!=B->val)
            return false;
        return dfs(A->left,B->right)&&dfs(A->right,B->left);
    }
};
```

# 第 8 天  动态规划（简单）

## [剑指 Offer 10- I. 斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)

别用递归写就行了

## [剑指 Offer 10- II. 青蛙跳台阶问题](https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)

$dp[i]=dp[i-1]+dp[i-2]$

## [剑指 Offer 63. 股票的最大利润](https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/)

不断更新当前元素与当前最小值的差值就行了

# 第 9 天 动态规划（中等）

## [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)

## [剑指 Offer 47. 礼物的最大价值](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/)

$dp[i][j]=\max\{dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j],dp[i][j] \}$

# 第 10 天 动态规划（中等）

## [剑指 Offer 46. 把数字翻译成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/)

$dp[i]$表示在位置$i$有多少种方案，如果$i$和$i-1$位置能够在一起翻译成字母，则$dp[i]=dp[i-1]+dp[i-2]$，否则$dp[i]=dp[i-1]$

## [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)

向后遍历，保证遍历过程中子字符串包含的字符只出现了一次。当出现第二次时，让子字符串开始的位置变成该字符出现第二次的位置。

# 第 11 天 双指针（简单）

## [剑指 Offer 18. 删除链表的节点](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/)

设置一个当前节点的前驱结点，如果当前节点为删除节点，停止查找，让前驱结点的下一个节点变成当前节点的下一个节点，即可实现删除

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val==val)
            return head->next;
        ListNode *pre=head,*now=head->next;
        while(now->val!=val&&now)
            pre=now,now=now->next;
        if(now)
            pre->next=now->next;
        return head;
    }
};
```

## [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *slow=head,*fast=head;
        for(int i=0;i<k;i++)
        {
            if(!fast)
                return NULL;
            fast=fast->next;
        }
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};
```

# 第 12 天 双指针（简单）

## [剑指 Offer 25. 合并两个排序的链表](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)

同时遍历两个链表，每次添加两个链表中较小的那个节点，知道有一个链表遍历结束

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(0,NULL);
        ListNode *tmp=head;
        while(l1&&l2)
        {
            if(l1->val>l2->val)
            {
                tmp->next=l2;
                l2=l2->next;
            }
            else
            {
                tmp->next=l1;
                l1=l1->next;
            }
            tmp=tmp->next;
        }
        if(l2)
            tmp->next=l2;
        if(l1)
            tmp->next=l1;
        return head->next;
    }
};
```

## [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)

双指针，[官方题解](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/liang-ge-lian-biao-de-di-yi-ge-gong-gong-pzbs/)有证明

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA||!headB)
            return NULL;
        ListNode *nodeA=headA,*nodeB=headB;
        while(nodeA!=nodeB)
        {
            nodeA=nodeA?nodeA->next:headB;
            nodeB=nodeB?nodeB->next:headA;
        }
        return nodeA;
    }
};
```

# 第 13 天 双指针（简单）

## [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)

## [剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)

### 哈希

### 双指针

## [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/)

直接py

cpp的话用栈来做吧，挺麻烦的

```python
class Solution:
    def reverseWords(self, s: str) -> str:
        s=s.strip().split()
        s.reverse()
        return ' '.join(s)
```

LeetCode—剑指 Offer学习计划

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

记一次失败的面试经历

使用电脑本地代理加速GitHub clone的速度

线代基础课公式（持续更新中......）

有馬公生様への手紙

【论文翻译】Hyperspectral Image Classification with Mixed Link Networks

2020/03/26

2020/06/04

2020/08/05

2007年数学二（119/150）

2020/07/20

LeetCode—剑指 Offer学习计划

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

LeetCode—剑指 Offer学习计划

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款