CUFMH2Blog

LeetCode - 剑指Offer - Part6

LeetCode 剑指Offer
Word count: 4.1k Reading time: 20 min
2020-09-11 calculating Share

晴空一鹤排云上，便引诗情到碧霄。

剑指 Offer 51. 数组中的逆序对**

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-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
class Solution {
public:
    //  归并排序
    //  94.99%  80.52%
    int reversePairs(vector<int>& nums) {
        int len=nums.size();
        if(len<=1) return 0;
        vector<int> temp(len);
        return mergesort(nums, temp, 0, len-1);
    }

    int mergesort(vector<int>& nums, vector<int>& temp, int l, int r) {
        if(l==r)    return 0;
        int mid=l+(r-l)/2;
        int ans1=mergesort(nums,temp,l,mid);
        int ans2=mergesort(nums,temp,mid+1,r);
        if(nums[mid]<=nums[mid+1])  return ans1+ans2;
        int ans3=merge(nums,temp,l,r);
        return ans1+ans2+ans3;
    }

    int merge(vector<int>& nums, vector<int>& temp, int l, int r) {
        int mid=l+(r-l)/2;
        for(int i=l;i<=r;i++) temp[i]=nums[i];
        int p1=l, p2=mid+1, ans=0;
        for(int i=l;i<=r;i++) {
            if(p1==mid+1)   nums[i]=temp[p2++];
            else if(p2==r+1 || temp[p1]<=temp[p2])    nums[i]=temp[p1++];
            else {
                nums[i]=temp[p2++];
                ans+=(mid-p1+1);
            }
        }
        return ans;
    }
};

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-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
27
28
29
30
31
32
/**
 * 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) {
        //  交替双指针，找链表相交节点
        //  92.32%  14.18%
        ListNode * a=headA;
        ListNode * b=headB;
        if(!a || !b)    return nullptr;
        while(a!=b) {
            if(!a->next && !b->next)  return nullptr;
            else if(!a->next){
                a=headB;
                b=b->next;
            } else if(!b->next){
                a=a->next;
                b=headA;
            } else {
                a=a->next;
                b=b->next;
            }
        }
        return a;
    }
};

剑指 Offer 53. 在排序数组中查找数字

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //  排序数组中找出现次数 - 直接二分
        //  89.28%  64.10%
        return helper(nums, target, 0, nums.size()-1);
    }

    int helper(vector<int>& nums, int target, int l, int r){
        int mid=l+(r-l)/2;
        if(l>r) return 0;
        if(nums[r]<target)  return 0;
        if(nums[l]>target)  return 0;
        if(nums[l]==target && nums[r]==target)  return r-l+1;
        return helper(nums,target,l,mid)+helper(nums,target,mid+1,r);
    }
};

0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //  无序可以考虑异或，有序直接二分
        //  74.49%  97.16%
        return helper(nums,0,nums.size()-1);  
    }

    int helper(vector<int>& nums, int l, int r){
        if(l>r) return 0;
        if(l==r){
            if(nums[l]==r)   return nums[l]+1;
            return nums[l]-1;
        }
        int mid=l+(r-l)/2;
        if(nums[mid]==mid)  return helper(nums,mid+1,r);
        else return helper(nums,l,mid);
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

限制：

1 ≤ k ≤ 二叉搜索树元素个数

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
/**
 * 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:
    int num=0,ans=0,t=0;
    int kthLargest(TreeNode* root, int k) {
        //  反向中序遍历，得到从大到小的排列，截止到k就停止
        //  96.90%  74.84%
        t=k;
        helper(root);
        return ans;
    }
    void helper(TreeNode* root) {
        if(root->right) helper(root->right);
        if(num==t)  return;
        num++;
        if(num==t) {
            ans=root->val;
            return;
        }
        if(root->left) helper(root->left);
        if(num==t)  return;
    }
};

剑指 Offer 55. 二叉树的深度和平衡二叉树

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

提示：

节点总数 <= 10000

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

1
2
3
4
5
6
7
8
9
class Solution {
public:
    //  递归
    //  82.83%  38.07%
    int maxDepth(TreeNode* root) {
        if(!root)   return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    //  80.08%  35.49%
    bool isBalanced(TreeNode* root) {
        return !root ? true : 
        abs(maxDepth(root->left)-maxDepth(root->right)) <= 1 
        && isBalanced(root->left) && isBalanced(root->right);
    }
    int maxDepth(TreeNode* root) {
        return !root ? 0 : max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

剑指 Offer 56. 数组中数字出现的次数*

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-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
class Solution {
public:
    //  异或
    //  全体异或
    //      因为一个数异或本身=0，0^a=a，所以结果实为所求两数的异或
    //  分组异或
    //      这两个数不同所以异或结果不为0，取其中为1的一位
    //      根据这一位为0为1把全体划分为两组
    //      分组异或，各得到所求两数
    //  96.43%  87.50%
    vector<int> singleNumbers(vector<int>& nums) {
        int len=nums.size();
        vector<int> ans;
        int a=0,b=0,c=0,d=0;
        for(int i=0;i<len;i++)    a^=nums[i];
        d=a&(-a);   //  比如a100->d100、a110->d10
        for(int i=0;i<len;i++) {
            if(nums[i]&d)  b^=nums[i];
            else c^=nums[i];
        }
        ans.push_back(b);
        ans.push_back(c);
        return ans;
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4
示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    //  位运算
    //  数a出现k次，说明a的二进制每一位上有1的数在数组中也出现k次
    //  数b出现1次，说明a的二进制每一位上有1的数在数组中也出现1次
    //  对全部数每一位分别求和，如果为3倍数则说明b该位=0，否则=1
    //  41.99%  80.49%
    int singleNumber(vector<int>& nums) {
        int ans=0;
        for(int i=0;i<32;i++) {
            int sum=0;
            for(int j:nums) if(j&(1<<i))    sum++;
            if(sum%3)    ans|=(1<<i);
        }
        return ans;
    }
};

剑指 Offer 57. 和为s的两数/序列

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //  由于递增，直接两端双指针
        //  如果无序，使用set或者map(带索引)
        //  61.67%  73.68%
        int l=0,r=nums.size()-1;
        while(l<r) {
            int t=nums[l]+nums[r]-target;
            if(!t)  return vector<int>{nums[l],nums[r]};
            else if(t>0)    r--;
            else    l++;
        }
        return vector<int>{0,0};
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        //  找规律
        //  66.61%  65.55%
        vector<vector<int>> ans;
        //  (target-sum(i))/(i+1) ~ (target-sum(i))/(i+1)+i
        for(int i=1;target>0;i++) {
            target-=i;
            if(target>0 && !(target%(i+1))) {
                vector<int> temp;
                for(int j=0;j<i+1;j++) {
                    temp.push_back(target/(i+1)+j);
                }
                ans.push_back(temp);
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

剑指 Offer 58 . 翻转单词/字符串

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”
示例 2：

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-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
class Solution {
public:
    string reverseWords(string s) {
        //  双指针
        //  86.70%  81.20%
        string ans="";
        int r,l=s.size()-1;
        while(l>=0 && s[l]==' ') {
            l--;
        }
        r=l;
        while(r>=0) {
            while(l>=0 && s[l]!=' ') {
                l--;
            }
            ans+=s.substr(l+1,r-l);
            while(l>=0 && s[l]==' ') {
                l--;
            }
            if(l>=0) ans+=" ";
            else    break;
            r=l;
        }
        return ans;
    }
};

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例 2：

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制：

1 <= k < s.length <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof

1
2
3
4
5
6
7
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        //  52.96%  39.62%
        return s.substr(n)+s.substr(0,n);
    }
};

剑指 Offer 59. 滑动窗口/队列的最大值**

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-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
class Solution {
    class MyQueue {
    private:
        deque<int> data;
    public:
        void push(int n) {
            while (!data.empty() && data.back() < n)    data.pop_back();
            data.push_back(n);
        }
        
        int max() { return data.front(); }
        
        void pop(int n) {
            if (!data.empty() && data.front() == n) data.pop_front();
        }
    };
public:
    //  单调队列（双端队列）
    //  O(n)复杂度
    //  57.73%  81.74%
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue window;
        vector<int> res;
        int len=nums.size();
        for (int i = 0; i < len; i++) {
            if (i < k - 1)  window.push(nums[i]);
            else {
                window.push(nums[i]);
                res.push_back(window.max());
                window.pop(nums[i-k+1]);
            }
        }
        return res;
    }
};

剑指 Offer 59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-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
class MaxQueue {
    //  36.28%  43.33%
public:
    deque<int> q1;
    deque<int> q2;  //  单调队列
    MaxQueue() {}
    
    int max_value() {
        if(q2.empty())  return -1;
        return q2.front();
    }
    
    void push_back(int value) {
        q1.push_back(value);
        while(!q2.empty() && q2.back()<value)   q2.pop_back();
        q2.push_back(value);
    }
    
    int pop_front() {
        if(q1.empty())  return -1;
        int t=q1.front();
        q1.pop_front();
        if(q2.front()==t) q2.pop_front();
        return t;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

剑指 Offer 60. n个骰子的点数*

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：

1 <= n <= 11

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-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<double> twoSum(int n) {
        //  dp
        //  次数=dp[n][sum]=dp[n−1][sum−1]+...+dp[n−1][sum−6]
        //  总数=6^n
        //  100.00% 32.61%
        vector<double> ans;
        vector<double> dp(6*n+1, 0);   //  对齐, 滚动数组
        for(int i=1;i<=6;i++)   dp[i]=1;
        for(int i=2;i<=n;i++) {
            for(int j=6*i;j>=i;j--) {
                dp[j]=0;
                for(int k=1;k<=6;k++)   if(j-k>=i-1)    dp[j]+=dp[j-k];
            }
        }
        for(int i=n;i<=6*n;i++) ans.push_back(dp[i]*pow(1.0/6,n));
        return ans;
    }
};
CATALOG
  1. 1. 剑指 Offer 51. 数组中的逆序对**
  2. 2. 剑指 Offer 52. 两个链表的第一个公共节点
  3. 3. 剑指 Offer 53. 在排序数组中查找数字
  4. 4. 剑指 Offer 54. 二叉搜索树的第k大节点
  5. 5. 剑指 Offer 55. 二叉树的深度和平衡二叉树
  6. 6. 剑指 Offer 56. 数组中数字出现的次数*
  7. 7. 剑指 Offer 57. 和为s的两数/序列
  8. 8. 剑指 Offer 58 . 翻转单词/字符串
  9. 9. 剑指 Offer 59. 滑动窗口/队列的最大值**
  10. 10. 剑指 Offer 60. n个骰子的点数*
Total : 27
2020
2019
3D-Game-Programming&Design SYSU-Course AR/MR Software-Testing LeetCode 剑指Offer
3D-Game-Programming-Design Software-Testing Programming