CUFMH2Blog

LeetCode - 剑指Offer - Part3

LeetCode 剑指Offer
Word count: 2.2k Reading time: 10 min
2020-09-04 calculating Share

练得身形似鹤形，千株松下两函经。

我来问道无余说，云在青天水在瓶。

剑指 Offer 21. 使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
      	//	双指针
        //  85.78%  85.49%
        int len=nums.size();
        int a=0;
        for(int i=0;i<len;i++) {
            if(nums[i]%2) {
                if(a!=i) {
                    int temp=nums[i];
                    nums[i]=nums[a];
                    nums[a]=temp;
                }
                a++;
            }
        }
        return nums;
    }
};

剑指 Offer 22. 链表倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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) {
        //  快慢指针
        //  55.14%  97.10%
        //  先让快指针走k步，然后两个指针同步走，
        //  当快指针走到头时，慢指针就是链表倒数第k个节点。
        ListNode *p=head;
        while(k-->1) {
            p=p->next;
        }
        while(p->next) {
            p=p->next;
            head=head->next;
        }
        return head;
    }
};

剑指 Offer 23. 链表环的入口节点

快慢指针即可

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //  96.09%  57.89%
    ListNode* reverseList(ListNode* head) {
        if(!head) return head;
        ListNode *c=head, *p=head, *temp=nullptr;
        while(c->next) {
            temp=c->next;
            c->next=c->next->next;
            temp->next=p;
            p=temp;
        }
        return p;
    }
};

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //  98.22%  90.66%
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * head=nullptr;
        if(!l1) {return l2;}
        else if(!l2) {return l1;}
        else if(l1->val<l2->val) {head=l1; l1=l1->next;}
        else {head=l2; l2=l2->next;}
        ListNode * p=head;
        while(l1||l2) {
            if(!l1) {
                p->next=l2;
                l2=l2->next;
            } else if(!l2) {
                p->next=l1;
                l1=l1->next;
            } else if(l1->val<l2->val){
                p->next=l1;
                l1=l1->next;
            } else {
                p->next=l2;
                l2=l2->next;
            }
            p=p->next;
        }
        return head;
    }
};

剑指 Offer 26. 树的子结构*

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

3-(4-(1-2))-5
给定的树 B：

4-1-null
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：

0 <= 节点个数 <= 10000

通过次数41,506提交次数89,791

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 {
    //  93.81%  59.55%
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) {return false;}
        return fun(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
    bool fun(TreeNode* A, TreeNode* B) {
        if(!B) {return true;}
        if(!A) {return false;}
        return A->val == B->val && fun(A->left, B->left) && fun(A->right, B->right);
    }
};

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
  	//	递归
    //  100.00% 80.62%
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode * temp=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(temp);
        return root;
    }
};

剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

0 <= 节点个数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    //  递归
    //  93.14%  71.60%
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return fun(root->left, root->right);
    }
    //  判断两个树是否对称
    //  若都非空，对称需要值相同、1左和2右对称、1右和2左对称
    bool fun(TreeNode* &l, TreeNode* &r) {
        if(!l && !r) return true;
        if(!l || !r) return false;
        return l->val==r->val && fun(l->left, r->right) && fun(l->right, r->left);
    }
};

剑指 Offer 29. 顺时针打印矩阵*

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //  99.19%  81.60%
        vector<int> res;
        int len1=matrix.size();
        if(!len1) return res;
        int len2=matrix[0].size();
        if(!len2) return res;

        int n1=len1/2+len1%2, n2=len2/2+len2%2;
        //  一共要绕几个圈
        int c=n1<n2?n1:n2;
        //  判断最后一个圈长宽是否可能为1
        bool flag=(len1-2*c+2==1 || len2-2*c+2==1);
        for(int i=0;i<c;i++) {
            for(int j=i; j<len2-i; j++) res.push_back(matrix[i][j]);
            for(int j=i+1; j<len1-i; j++) res.push_back(matrix[j][len2-i-1]);
            if(i!=c-1 || !flag){
                //  如果最后一个长宽为1，则不执行后一半
                for(int j=len2-i-2; j>=i; j--) res.push_back(matrix[len1-i-1][j]);
                for(int j=len1-i-2; j>=i+1; j--) res.push_back(matrix[j][i]);
            }
        }
        return res;
    }
};

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); —> 返回 -3.
minStack.pop();
minStack.top(); —> 返回 0.
minStack.min(); —> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack {
public:
  	//	辅助栈
    //  85.39%  67.60%
    stack<int> s;
    stack<int> m;
    MinStack() {}
    
    void push(int x) {
        if(m.empty() || m.top()>=x) m.push(x);
        s.push(x);
    }
    
    void pop() {
        if(!s.empty()){
            if(s.top()==m.top()) m.pop();
            s.pop();
        }
    }
    
    int top() { return s.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();
 */
CATALOG
  1. 1. 剑指 Offer 21. 使奇数位于偶数前面
  2. 2. 剑指 Offer 22. 链表倒数第k个节点
  3. 3. 剑指 Offer 23. 链表环的入口节点
  4. 4. 剑指 Offer 24. 反转链表
  5. 5. 剑指 Offer 25. 合并两个排序的链表
  6. 6. 剑指 Offer 26. 树的子结构*
  7. 7. 剑指 Offer 27. 二叉树的镜像
  8. 8. 剑指 Offer 28. 对称的二叉树
  9. 9. 剑指 Offer 29. 顺时针打印矩阵*
  10. 10. 剑指 Offer 30. 包含min函数的栈
Total : 27
2020
2019
3D-Game-Programming&Design SYSU-Course AR/MR Software-Testing LeetCode 剑指Offer
3D-Game-Programming-Design Software-Testing Programming