CUFMH2Blog

LeetCode - 剑指Offer - Part7

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

朝辞白帝彩云间，千里江陵一日还。

剑指 Offer 61. 扑克牌中的顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        //  0为赖子牌，判断赖子牌够不够，有没有重复即可
        //  100.00% 71.15%
        sort(nums.begin(), nums.end());
        int c=0, need=0;
        while(!nums[c]) c++;
        for (int i=c+1;i<nums.size();i++) {
            if(nums[i]==nums[i-1])  return false;
            need+=nums[i]-nums[i-1]-1;
        }
        return c>=need;
    }
};

剑指 Offer 62. 圆圈中最后剩下的数字*

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lastRemaining(int n, int m) {
        //  约瑟夫环问题
        //  反推
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
};
//  参考链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //  95.61%  99.07%
        int len=prices.size();
        if(len<=1)    return 0;
        int ans=0,min=prices[0];
        for(int i=0;i<len;i++) {
            if(min > prices[i]) min=prices[i];
            else if(ans<prices[i]-min)  ans=prices[i]-min;
        }
        return ans;
    }
};

剑指 Offer 64. 求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6
示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qiu-12n-lcof

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int sumNums(int n) {
        //  逻辑符 - 短路原理
        //  100.00% 43.98%
        n && (n += sumNums(n-1));
        return n;
    }
};

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

提示：

a, b 均可能是负数或 0
结果不会溢出 32 位整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    /*
    网友题解：
    ^ 亦或 ----相当于 无进位的求和， 想象10进制下的模拟情况：（如:19+1=20；无进位求和就是10，而非20；因为它不管进位情况）
    & 与 ----相当于求每位的进位数， 先看定义：1&1=1；1&0=0；0&0=0；即都为1的时候才为1，正好可以模拟进位数的情况,还是想象10进制下模拟情况：（9+1=10，如果是用&的思路来处理，则9+1得到的进位数为1，而不是10，所以要用<<1向左再移动一位，这样就变为10了）；
    这样公式就是：（a^b) ^ ((a&b)<<1) 即：每次无进位求 + 每次得到的进位数--------我们需要不断重复这个过程，直到进位数为0为止；
    */
    int add(int a, int b) {
        while(b!=0){
            int tmp=a^b;
            b=((unsigned int)(a&b)<<1);
            a=tmp;
        }
        return a;
    }
};

剑指 Offer 66. 构建乘积数组*

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

所有元素乘积之和不会溢出 32 位整数
a.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-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<int> constructArr(vector<int>& a) {
        //  暴力-超时
        //  对称算法-结果为左边乘右边，先选好每一位左边的积，再逆向计算右边
        //  41.94%  78.09%
        int len=a.size();
        vector<int> b(len,1);
        int left=1,right=1;
        for(int i=0;i<len;i++) {
            b[i]=left;
            left=left*a[i];
        }
        for(int i=len-1;i>=0;i--)
        {
            b[i]=b[i]*right;
            right=right*a[i];
        }
        return b;
    }
};

剑指 Offer 67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42”
输出: 42
示例 2:

输入: “ -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:

输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。
示例 4:

输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:

输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−2^31) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    //  79.10%  75.27%
public:
    int strToInt(string str) {
        long ans=0;
        bool flag=false;
        int index=0;
        while(str[index]==' ')  index++;
        if(!isdigit(str[index])&&str[index]!='+'&&str[index]!='-')  return 0;
        if(str[index]=='+') index++;
        else if (str[index]=='-') {
            flag=true;
            index++;
        }
        while(isdigit(str[index])) {
            ans=ans*10+str[index++]-'0';
            if(!flag && ans>INT_MAX)    return INT_MAX;
            else if(flag && -ans<INT_MIN)   return INT_MIN;
        }
        return flag?-ans:ans;
    }
};

剑指 Offer 68 - I. 二叉树的最近公共祖先*

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //  递归
        //  44.14%  80.21%
        if(root->val>p->val && root->val>q->val)
            return lowestCommonAncestor(root->left,p,q);
        if(root->val<p->val && root->val<q->val)
            return lowestCommonAncestor(root->right,p,q); 
        return root;
    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //  递归
        //  73.82%  66.74%
        if(!root)   return nullptr;
        if(root==p || root==q)  return root;
        TreeNode * t1=lowestCommonAncestor(root->left,p,q);
        TreeNode * t2=lowestCommonAncestor(root->right,p,q);
        if(t1 && t2)    return root;
        if(t1)  return t1;
        if(t2)  return t2;
        return nullptr;
    }
};
CATALOG
  1. 1. 剑指 Offer 61. 扑克牌中的顺子
  2. 2. 剑指 Offer 62. 圆圈中最后剩下的数字*
  3. 3. 剑指 Offer 63. 股票的最大利润
  4. 4. 剑指 Offer 64. 求1+2+…+n
  5. 5. 剑指 Offer 65. 不用加减乘除做加法
  6. 6. 剑指 Offer 66. 构建乘积数组*
  7. 7. 剑指 Offer 67. 把字符串转换成整数
  8. 8. 剑指 Offer 68 - I. 二叉树的最近公共祖先*
Total : 27
2020
2019
3D-Game-Programming&Design SYSU-Course AR/MR Software-Testing LeetCode 剑指Offer
3D-Game-Programming-Design Software-Testing Programming