【程序员刷题必备 | 《剑指offer》】（二）-阿里云开发者社区

26.礼物的最大价值(剑指offer原47题)

解题思路：经典的边界问题，还是要考虑三个问题，状态怎么表示；状态的计算问题；怎么定义边界。f[i,j]表示从左上角出发，到达当格子获得的最大价值。状态计算[i, j] = max(f[i-1, j],f[i, j-1]) + gifts[i,j]；边界f[i,0] = f[0, j] = 0。所要求的答案是f[n,m]。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution{
public:
    int getMaxValue(vector<vector<int>>& grid){
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[i][j] = max(f[i -1][j], f[i][j-1]) + grid[i-1][j-1];
            }
        }
        return grid[n][m];
    }
};

27.最长不含重复字符的子字符串(剑指offer原48题)

解题思路：双指针i、j算法，当j指针每向后移动一位时，判断i到j中是否有重复字符，如果出现了重复字符，就将i指向的重复字符删除，同时i指针向后移动一次。当j移动到字符串末尾时，j-i+1的距离就是不含重复字符的子字符串。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution{
public:
    int lengthLongestSubString(string s){
        unordered_map<char, int> hash;
        int res = 0;
        for(int i = 0, j = 0; j < s.size(); j++){
            hash[s[j]]++;
            while(hash[s[j]] > 1) hash[s[i++]]--;
            res = max(res, j - i + 1);
        }
        return res;
    }
};

28.丑数(剑指offer原49题)------求第n个丑数的值

解题思路：丑数：一个数的质因子中只包含2 3 5的数！首先将1加入丑数集合中去，然后分别用三个i,j,k指针指向1.。其中i表示2，j表示3，k表示5；然后用1分别与i、j、k三个指针相乘，取相乘后所有结果中的最小值放在1的下一个位置。同时，将指针向后移动一个位置。当有多个相等的最小值出现时，需要将多个指针分别向后移动一个位置。依次循环下去，就可以找到整个丑数组成的集合了。（实际上是3路归并排序，将包含因子2的排好序丑数放入一个数组、包含因子3的排好序丑数放入一个数组、包含因子5的排好序丑数放入一个数组；前面的三个数组中，是不包含因子1。然后将三个数组分别除以数字2 数字3 数字5得到的结果仍然是一个丑数序列，将得到的3个丑数序列合并后进行判重处理，就得到了最终结果）

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int getUglyNumber(int n){
        vector<int> q(1, 1);
        int i = 0, j = 0, k = 0;
        while(--n){  // 循环n-1次    while(n--){}是循环n次
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if(q[i] * 2 == t) i++;
            if(q[j] * 3 == t) j++;
            if(q[k] * 5 == t) k++;
        }
        return q.back();
    }
};

29.字符串中第一个只出现一次的字符(剑指offer原50题---题目一)

解题思路：先定义一个hash表，统计每个字符出现多少次，然后从前往后遍历hash表，扫描到第一个值是1对应的key，也就是最终的结果。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution{
public:
    char firstNotRepeatingChar(string s){
        unordered_map<char, int> hash;
        for(auto c : s) hash[c]++;  // 统计字符串s中每个字符出现的次数
        char res = '#';  // 无解的情况
        for(auto c : s)
            if(hash[c] == 1){
                res = c;
                break;
            }
        return res;
    }
};

30.字符流中第一个只出现一次的字符(剑指offer原50题---题目二)

解题思路：每次输入字符时，将输入的字符流中出现次数大于1的字符删除。使用队列的数据结构来存储插入的字符！

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
class Solution{
public:
    unordered_map<char, int> hash;
    queue<char> q;
    // 插入字符到一个队列queue中
    // 利用hash表判断当前正在插入的字符是否出现在当前的队列中
    void insert(char ch){
        if(++hash[ch] > 1){  // 插入的字符已经出现在队列中
            while(q.size() && hash[q.front()] > 1) q.pop();
        }
        else q.push(ch); // 插入的字符没有出现在队列中
    }
    char firstAppearingOnce(){
        if(q.empty()) return '#';
        return q.front();
    }
};

31.数组中的逆序对(剑指offer原51题）

解题思路：暴力做法的时间复杂度是O(n**2)，考虑能否使用归并排序的方法来优化算法为O(nlogn)。首先分别对统计同时在左右两个子序列中一共有多少个逆序对（递归方法）；然后计算逆序对不在同一个子序列时，对第二个序列中的每一个数a[j]，计算第一个序列中一共有多少个数a[i]比a[j]要大。因此一共有r-i+1个数比a[j]]要大！最后的结果是上面三个部分的和。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution{
public:
    int merge(vector<int>& nums, int l, int r){
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);  // 第一和第二部分
        // 第三个部分
        int i = l, j = mid + 1;
        vector<int> temp;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) temp.push_back(nums[i++]);
            else{
                temp.push_back(nums[j++]);
                res += mid - i + 1;
            }
            while(i <= mid) temp.push_back(nums[i++]);
            while(j <= r) temp.push_back(nums[j++]);
            i = l;
            for(auto x : temp) nums[i++] = x;
            return res;
        }
    }
    int inversePairs(vector<int>& nums){
        int res = 0;
        return merge(nums, 0, nums.size() - 1);
    }
};

32.两个链表的第一个公共结点(剑指offer原52题）

思路：使用两个指针p和q，p指针指向第一个链表的头结点，q指针指向第二个链表的头结点。当p指针遍历到第一个链表的末尾时，接着回到第二链表的头结点位置；当q指针遍历到第二个链表的末尾时，接着回到第一链表的头结点位置。注意两个指针所走的总距离是相等的！当进行了多次循环后，两个指针一定会在某个结点处相遇，即公共结点。

#include <iostream>
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};
using namespace std;
class Solution{
public:
    ListNode* findFirstCommonNode(ListNode* headA, ListNode* headB){
        auto p = headA, q = headB;
        while(p != q){
            if(p) p = p->next;
            else p = headB;
            if(q) q = q->next;
            else q = headA;
        }
        return p;
    }
};

33.二叉搜索树的后序遍历序列(剑指offer原33题)

题目：给定一个数组，判断此数组是否是某二叉搜索树的后序遍历结果！
解题思路：先找出数组中的最后一个元素作为树根root，然后找到二叉搜索树的左子树的最后一个位置（左子树中的结点值均小于root，右子树的结点值均大于root）。接着找到二叉搜索树的右子树的最后一个位置。判断结点的值是否满足二叉搜索树的定义！

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    vector<int> seq;
    bool verifySequenceOFBST(vector<int> sequence){
        seq = sequence;
        return dfs(0, seq.size() - 1);
    }
    bool dfs(int l, int r){
        if(l >= r) return true;
        int root = seq[r];
        int k = l;
        while(k < r && seq[k] < root) k++;  // 二叉搜索树的左子树
        for(int i = k; i < r; i++){  // 判断二叉搜索树的右子树是否合法
            if(seq[i] < root) return false;
        }
        return dfs(l, k-1) && dfs(k+1, r);
    }
};

34.二叉树中和为某一值的路径(剑指offer原34题)

解题思路：直接遍历一遍二叉树，当遍历到叶节点时，判断从根节点到当前节点的路径上的节点值之和是否等于给定值。如果等于的话，就记录当前的路径。

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum){
        dfs(root, sum);
        return ans;
    }
    void dfs(TreeNode* root, int sum){
        if(!root) return;  // 当前节点是空的，就不是叶子节点
        path.push_back(root->val);
        sum -= root->val;
        // 如果当前节点的左右子树都是空的，则当前节点是叶子节点
        if(!root->left && !root->right && !sum) ans.push_back(path);
        // 递归处理左右子树
        dfs(root->left, sum);
        dfs(root->right, sum);
        path.pop_back();
    }
};

35.复杂链表的复制(剑指offer原35题)

解题思路：第一步将每个节点复制出来，然后将当前节点的next指针指向复制出来的节点；第二步将原先节点p的random指针指向第3个节点；那么，被复制出来的p节点是p->next，其random指针即p->next->random指向p->random->next节点。最后将复制出来的节点全部连接起来！

#include <iostream>
#include <vector>
using namespace std;
struct ListNode{
    int val;
    ListNode* next, *random;
    ListNode(int x): val(x), next(nullptr), random(nullptr){}
};
class Solution{
public:
    ListNode* copyRandomList(ListNode* head){
        // 第一步复制所有的节点，并将当前节点指向复制出来的节点
        for(auto p = head; p;)
        {
            auto np = new ListNode(p->val);  // 复制出来的新节点
            auto next = p->next;   // 备份一下p->next;
            p->next = np;   // 复制出来的点接在当前节点的后面
            np->next = next;
            p = next;
        }
        // 第二步复制random指针
        for(auto p = head; p; p = p->next->next){
            if(p->random)
                p->next->random = p->random->next;
        }
        // 第三步将所有复制出来的节点连接起来
        auto dummy = new ListNode(-1);
        auto cur = dummy;   // 当前新链表的尾节点
        for(auto p = head; p; p = p->next){
            cur->next = p->next;
            cur = cur->next;
            p = p->next;
        }
        return dummy->next;
    }
};

36.二叉搜索树与双向链表(剑指offer原36题)

解题思路：首先获取根节点；然后分别递归左右子树，左右子树分别返回一个首尾节点(即当前子树中最左边的节点和当前子树中最右边的节点)；接着将三部分拼接起来；最后将左子树的最左侧和右子树的最右侧节点返回就是最后的答案。

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    TreeNode* convert(TreeNode* root){
        if(!root) return nullptr;
        auto sides = dfs(root);
        return sides.first;
    }
    pair<TreeNode*, TreeNode*> dfs(TreeNode* root){
        if(!root->left && !root->right) return {root, root};  // 当前节点是叶子节点
        if(root->left && root->right){
            auto lsides = dfs(root->left), rsides = dfs(root->right);
            lsides.second->right = root, root->left = lsides.second;
            root->right = rsides.first, rsides.first->left = root;
            return {lsides.first, rsides.second};
        }
        if(root->left){
            auto lsides = dfs(root->left);
            lsides.second->right = root, root->left = lsides.second;
            return {lsides.first, root};
        }
        if(root->right){
            auto rsides = dfs(root->right);
            root->right = rsides.first, rsides.first->left = root;
            return {root, rsides.second};
        }
    }
};

37.序列化二叉树(剑指offer原37题)

题目：确保二叉树可以序列化为字符串；并且可以将此字符串反序列化为原始树结构。
解题思路：利用二叉树的前序遍历实现从二叉树到字符串的序列化操作；反序列化实现的是从字符串到二叉树的转换，注意将字符串类型的数字转成整数的方法！

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    // 序列化
    string serialize(TreeNode* root){
        string res;
        dfs_s(root, res);
        return res;
    }
    // 前序遍历实现序列化
    void dfs_s(TreeNode* root, string& res){
        if(!root){
            res += "null ";
            return;
        }
        res += to_string(root->val) + ' ';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }
    // 反序列化
    TreeNode* deserialize(string data){
        int u = 0;
        return dfs_d(data, u);
    }
    TreeNode* dfs_d(string data, int& u){
        if(u == data.size()) return nullptr;
        int k = u;
        while(data[k] != ' ') k++;
        if(data[u] == 'n'){ // 'n'是null的开始字符
            u = k + 1;
            return nullptr;
        }
        int val = 0;
        for(int i = u; i < k; i++) val = val * 10 + data[i] - '0';  // 将字符串整数"123"转换成整数123
        u = k + 1;
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);
        return root;
    }
};

38.数字排列---（与剑指offer38题不同）

题目：输入一组数字(可能包含重复数字)，输出其所有的全排列
解题思路：先对输入的数字进行排序，然后开辟与输入一组数字相同长度的数组，接着从输入数字中按顺序取一个数字放在数组的任意一个位置上。接下来，取第二个数字放在数组中剩下空间的任意一个位置上，如果第二个数字与第一个数字值是相同的，则规定第二个数字只能放在第一个数字的后面的位置，依次将输入的数字放入数组中，直到数组的各位都已经占满为止。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution{
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums){
        path.resize(nums.size());   // 开辟的数组空间大小
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0, 0);   // 用一个二进制位来表示哪些位置是空的
        return ans;
    }
    void dfs(vector<int>& nums, int u, int start, int state){
        // u:当前枚举的位置   start: 当前这个数应该从哪个位置开始枚举？（即上一个数的后一个位置开始枚举）
        // state: 存储的是状态，表示哪些数被用过
        if(u == nums.size()){
            ans.push_back(path);
            return;
        }
        if(!u || nums[u] != nums[u-1]) start = 0;
        for(int i = start; i < nums.size(); i++){
            if(!(state >> i & 1)){   // state >> i & 1：看一下state的二进制表示中第i位是否表示为1
                path[i] = nums[u];
                dfs(nums, u + 1, i + 1, state + (1 << i));
            }
        }
    }
};

39.数组中出现次数超过一半的数字（寻找数组中的众数）(剑指offer原39题)

解题思路：初始化一个计数变量count = 0，然后遍历数组中的每个元素，当val等于第一个元素时，count加1。接着遍历第二个元素，如果第二个元素的值与第一个元素的值相同时，则count加1；如果第二个元素的值与第一个元素的值不同时，count减1；最后遍历完整个数组后，最终结果存储在val变量中。摩尔投票法原理

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution{
public:
    int moreThanHalfNum(vector<int>& nums){
        int cnt = 0, val = -1;
        for(auto x : nums)
        {
            if(!cnt) val = x, cnt = 1;
            else
            {
                if(x == val) cnt++;
                else cnt--;
            }
        }
        return val;
    }
};

40.最小的k个数(剑指offer原40题)

解题思路：维护一个大顶堆，当最小的k个数存放在大顶堆中。遍历输入数组中的每个元素，然后将每个元素与大顶堆中的堆顶元素进行比较，如果比堆顶元素小，就更新堆顶元素。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution{
public:
    vector<int> getLeastNumbers(vector<int> input, int k){
        priority_queue<int> heap;
        for(auto x : input)
        {
            heap.push(x);
            if(heap.size() > k) heap.pop();
        }
        vector<int> res;
        while(heap.size()) res.push_back(heap.top()), heap.pop();  // heap存放的是从大到小的顺序
        reverse(res.rbegin(), res.rend());  // 翻转一下变成从小到大
        return res;
    }
};

41.数据流中的中位数(剑指offer原41题)

题目：如果从数据流中读出奇数个数值，则中位数就是所有数值排序后位于中间的数值；如果从数据流中读出偶数个数值，则中位数就是所有数值排序之后中间两个数的平均值。
解题思路：将当前所有的数维护成两个集合，第一个集合是一个小顶堆，存的是比较大的那一部分数；第二个集合是一个大顶堆，存的是比较小的那一部分数。可以发现，大顶堆的堆顶元素和小顶堆的堆顶元素实际就是输入数据流中间的两个数。规定，数据流中读出的是奇数个数值时，大顶堆比小顶堆中的元素多一个。如何维护这个结构？每次插入一个新的元素到大顶堆中，如果下面大顶堆的堆顶元素比上面小顶堆的堆顶元素的大（即逆序了），则交换；如果下面大顶堆中的元素太多了，就要直接转移当中的一个元素到小顶堆中。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution{
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if(min_heap.size() && max_heap.top() > min_heap.top())
        {
            auto maxv = max_heap.top(), minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }
        if(max_heap.size() > min_heap.size() + 1)
        {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    double getMedian(){
        if(max_heap.size() + min_heap.size() & 1) return max_heap.top();   // 数据流中是奇数个数值
        return (max_heap.top() + min_heap.top()) / 2.0;    // 数据流中是偶数个数值
    }
};

42.连续子数组的最大和(剑指offer原42题)

解题思路：s表示遍历到当前数x前一个位置为结尾的子数组的和最大值，s如何更新？当s > 0时，s = s + x；当s <= 0时，s = x；

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int maxSubArray(vector<int>& nums){
        int res = INT_MIN, s = 0;
        for(auto x : nums)
        {
            if(s < 0) s = 0;
            s += x;
            res = max(res, s);
        }
        return res;
    }
};

43.从1到n整数中1出现的次数(剑指offer原43题)

解题思路：假设输入13015，则万位上的1个数：10000-13015共3016个；千位上的1个数：1000-1999,11000-11999，一共有2000个；百位上的1个数：情况有很多种！十位上的1个数：情况有很多种！总结出的一般规律：输入的数字是abcedf，第一种情况：假设c位置上的数字是1，则ab位置上的取值范围是00到ab-1；def位置上的取值范围是000到999，则总方案数是ab*1000。第二种情况：最高位恰好取到ab时，分两种情况讨论。1.c位等于0时，就只有0个1；2.c位等于1时，则def的取值范围是0到def，一共有def+1种方案；3.c大于1时，def位置上的取值范围是000到999，则总方案数是1000！

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int numberOfBetween1AndN(int n){
        if(!n) return 0;
        vector<int> number;
        // 取出n中的每位数字放入number中
        while(n)
        {
            number.push_back(n % 10);
            n /= 10;
        }
        int res = 0;
        for(int i = number.size() -  1; i >= 0; i--)
        {
            auto left = 0, right = 0, t = 1;
            for(int j = number.size() - 1; j > i; j--)
            {
                left = left * 10 + number[j];
            }
            for(int j = i - 1; j >= 0; j--)
            {
                right = right * 10 + number[j];
                t *= 10;  // t表示右边一共有多少位数
            }
            res += left * t;
            if(number[i] == 1) res += right + 1;
            else if(number[i] > 1) res += t;
        }
        return res;
    }
};

44.反转链表(剑指offer原24题)

解题思路：因为反转的是一个单向链表，所以无法直接遍历当前节点的前驱结点，因此利用一个变量pre记录当前节点的前驱结点。然后从头开始遍历给定的单向链表，直到遍历到空结点为止。

#include <iostream>
#include <vector>
using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};
class Solution{
public:
    ListNode* reverseList(ListNode* head){
        ListNode* pre = nullptr;   // 记录当前结点的前驱结点
        auto cur = head;
        while(cur)
        {
            auto next = cur->next;    // 用next变量缓存cur->next，用来使得cur向后移动一位
            cur->next = pre;                   // 每次遍历时，将当前结点的next指针指向其前驱结点
            pre = cur;        // 将pre指针向后移动一位，此时pre指向cur
            cur = next;
        }
        return pre;                 // pre就是反转后链表的头结点
    }
};

45.合并两个排序的链表(剑指offer原25题)

解题思路：归并排序的方法来实现即可！

#include <iostream>
#include <vector>
using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};
class Solution{
public:
    ListNode* merge(ListNode* l1, ListNode* l2){
        auto dummy = new ListNode(-1);
        auto cur = dummy;   // 因为往合并后的链表中添加元素时，是尾部插入的。因此，需要一个cur指针来记录当前链表的尾结点在哪。
        while(l1 && l2)
        {
            if(l1->val < l2->val){
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }
        // 将两个链表中更长者中剩余的部分链接到已合并链表的末尾
        if(l1) cur->next = l1;
        else cur->next = l2;
        return dummy->next;
    }
};

46.树的子结构---树的匹配(剑指offer原26题)

解题思路：类比字符串匹配的方法，从根结点root开始枚举，看一下树根root是否是子树的根节点；不是的话，判断树的左孩子结点是否是子树的树根结点；不是的话，判断树的右孩子结点是否是子树的树根结点。然后利用前序遍历树和子树即可。

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    bool hasSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
        if(!pRoot1 || !pRoot2) return false;
        // 前序遍历树pRoot1，然后与pRoot2结点进行对比
        if(isPart(pRoot1, pRoot2)) return true;
        return hasSubTree(pRoot1->left, pRoot2) || hasSubTree(pRoot1->right, pRoot2);
    }
    bool isPart(TreeNode* p1, TreeNode* p2){
        if(!p2) return true;
        if(!p1 || p1->val != p2->val) return false;
        return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
    }
};

47.二叉树的镜像(剑指offer原27题)

解题思路：所有结点的左右孩子结点都交换了一下，遍历树中的所有结点，每次遍历完后，将每个结点的左右孩子结点交换一下就可以了。

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    void mirror(TreeNode* root){
        if(!root) return;
        mirror(root->left);
        mirror(root->right);
        swap(root->left, root->right);
    }
};

48.对称的二叉树(剑指offer原28题)

解题思路：除了根节点之外，其他的每个结点它的左边的结点和右边的结点是对应的！并且左边结点的左孩子和右边结点的右孩子是对称的，左边结点的右孩子和右边结点的左孩子是对称的！

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};
class Solution{
public:
    bool isSymmetric(TreeNode* root){
        if(!root) return true;
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* p, TreeNode* q){
        if(!p || !q) return !p && !q;
        if(p->val != q->val) return false;
        return dfs(p->left, q->right) && dfs(p->right, q->left);
    }
};

49.顺时针打印矩阵(剑指offer原29题)

解题思路：顺时针定义四个方向：右下左上；先按右的方向走，走到不能走为止；然后向下移动一个位置，按下的方向走，走到不能走为止；再向左移动一个位置，按左的方向走，走到不能走为止；最后向上移动一个位置，按上的方向走，走到不能走为止！直到总完n*m步就完成了！不能走的定义是：要么走出了边界，要么你已经走过了这个格子了。

#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    vector<int> printMatrix(vector<vector<int>> matrix){
        vector<int> res;
        int n = matrix.size(), m = matrix[0].size();
        if(!n) return res;
        vector<vector<bool>> st(n, vector<bool>(m, false));   // 二维数组记录每个格子是否被访问过
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上 右 下 左
        int x = 0, y = 0, d = 1;  // 起始方向是向右移动，故d = 1
        for(int i = 0; i < n * m; i++)
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;   // 当前点被标记成已经访问
            int a = x + dx[d], b = y + dy[d];  // 下一个点的坐标
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){  // 当前点已经出界或者被访问过
                d = (d + 1) % 4;   // d向下移动
                a = x + dx[d], b = y + dy[d];
            }
        }
        return res;
    }
};

50.包含min函数的栈(剑指offer原30题)

题目：设计一个支持push pop top等操作并可以在O(1)的时间复杂度内检索出最小元素的堆栈。
解题思路：利用一个辅助栈(单调栈)来操作。单调栈：即栈中的元素是单调的！维护一个单调栈，单调栈中的元素大小是单独变化的，当插入一个新的元素到主栈中时，将其与单调栈中的栈顶元素进行比较，当插入的元素比单调栈中的栈顶元素大，则不会将新的元素插入到主栈中；当插入的元素比单调栈中的栈顶元素小或者与单调栈中的栈顶元素相等时，则将新的元素插入到主栈中去。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class MinStack{
public:
    stack<int> stk, min_stk;   // stk是主栈  min_stk是单调栈
    MinStack(){
    }
    void push(int x){
        stk.push(x);
        if(min_stk.empty() || min_stk.top() >= x) min_stk.push(x);
    }
    void pop(){
        if(stk.top() == min_stk.top()) min_stk.pop();
        stk.pop();
    }
    int top(){
        return stk.top();
    }
    int getMin(){
        return min_stk.top();
    }
};

【程序员刷题必备 | 《剑指offer》】（二）

26.礼物的最大价值(剑指offer原47题)

27.最长不含重复字符的子字符串(剑指offer原48题)

28.丑数(剑指offer原49题)------求第n个丑数的值

29.字符串中第一个只出现一次的字符(剑指offer原50题---题目一)

30.字符流中第一个只出现一次的字符(剑指offer原50题---题目二)

31.数组中的逆序对(剑指offer原51题）

32.两个链表的第一个公共结点(剑指offer原52题）

33.二叉搜索树的后序遍历序列(剑指offer原33题)

34.二叉树中和为某一值的路径(剑指offer原34题)

35.复杂链表的复制(剑指offer原35题)

36.二叉搜索树与双向链表(剑指offer原36题)

37.序列化二叉树(剑指offer原37题)

38.数字排列---（与剑指offer38题不同）

39.数组中出现次数超过一半的数字（寻找数组中的众数）(剑指offer原39题)

40.最小的k个数(剑指offer原40题)

41.数据流中的中位数(剑指offer原41题)

42.连续子数组的最大和(剑指offer原42题)

43.从1到n整数中1出现的次数(剑指offer原43题)

44.反转链表(剑指offer原24题)

45.合并两个排序的链表(剑指offer原25题)

46.树的子结构---树的匹配(剑指offer原26题)

47.二叉树的镜像(剑指offer原27题)

48.对称的二叉树(剑指offer原28题)

49.顺时针打印矩阵(剑指offer原29题)

50.包含min函数的栈(剑指offer原30题)

热门文章

最新文章

相关课程

相关电子书