2022-11-22

字数统计: 3k字 | 阅读时长: 14分

剑指offer-4

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

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

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector <double> dp(6, 1.0 / 6.0);
        for(int i = 2; i <= n; i++) {
            vector <double> tmp(5 * i + 1, 0);  //i个骰子一共有5 * i + 1中方式
            for(int j = 0; j < dp.size(); j++) {
                for(int k = 0; k < 6; k++) {
                    tmp[j + k] = tmp[j + k] + dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
};

剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode）

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

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

    //  n-1约瑟夫环的索引index(n-1)        删除一个数后的n约瑟夫环索引index(n)
    //                0           --->                     m%n
    //                1           --->                     (m+1)%n
    //                2           --->                     (m+2)%n
    //               ...                                  ...
    //                n-2         --->                     (m+n-2)%n
    //  由以上得出递推式：index(n-1)  --->      index(n) = (m+index(n-1))%n
    // 也就是说，现在的环索引为0的对应原来的索引为3的，换句话说，旧环的索引3跑到新环的索引0位置上了。
class Solution {
public:
    int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
};

剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode）

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

动态规划的思想，分别记录买入的最小值dp[i][0]和利润最大值dp[i][1]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if(size == 0) {
            return 0;
        }
        int result = 0;
        vector <vector <int>> dp(size, vector <int> (2));
        dp[0][0] = -prices[0]; //代表第一天买入
        dp[0][1] = 0;   //代表第一天卖出
        for(int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(-prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[size - 1][1];
    }
};

剑指 Offer 64. 求1+2+…+n - 力扣（LeetCode）

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

常规方法，使用while

class Solution {
public:
    int sumNums(int n) {
        int sum = 0;
        while(n) {
            sum += n;
            n--;
        }
        return sum;
    }
};

递归的算法，&&实现类似if的效果，如果不满足n > 1就退出递归。

class Solution {
public:
    int result = 0;
    int sumNums(int n) {
        bool x = n > 1 && sumNums(n - 1) > 0;   // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归
        result = result + n;
        return result;
    }
};

剑指 Offer 65. 不用加减乘除做加法 - 力扣（LeetCode）

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

class Solution {
public:
    int add(int a, int b) {
        if(b == 0) { //没有进位了就直接返回
            return a;
        }
        return add(a ^ b, (a & b & 0x7fffffff) << 1);   //&代表按位与后左移一位, ^代表异或。 a ^ b表示不包含进位的结果，a & b << 1代表进位, & 0x7fffffff代表强制将负数的最高位清零，这样才能左移
    }
};

剑指 Offer 66. 构建乘积数组 - 力扣（LeetCode）

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

因为不能用除法，把数组分成上三角和下三角两个部分，在将两部分乘起来就是最终的结果。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int size = a.size();
        if(size == 0) return {};
        vector <int> b(size, 1);
        b[0] = 1;
        int tmp = 1;
        for(int i = 1; i < size; i++) {	//计算下三角
            b[i] = b[i - 1] * a[i - 1];
        }
        for(int i = size - 2; i >= 0; i--) {	//计算上三角
            tmp = tmp * a[i + 1];
            b[i] = b[i] * tmp;
        }
        return b;
    }
};

剑指 Offer 67. 把字符串转换成整数 - 力扣（LeetCode）

class Solution {
public:
    int strToInt(string s) {
        long long int result = 0;
        int tmp = 0;
        bool neg = false;
        int count = 0;
        int start;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ' ') {	//去掉开始的空格
                continue;
            }
            else {	//移动下标
                start = i;
                break;
            }
        }
        if(s[start] == '-') {	//判断符号
            neg = true;
            start = start + 1;
        }
        else if(s[start] == '+') {
            neg = false;
            start = start + 1;
        }
        else {
            neg = false;
        }
        for(int i = start; i < s.size(); i++) {
            if(s[start] > '9' || s[start] < '0') {
                result = 0;
                break;
            }
            if(s[i] >= '0' && s[i] <= '9') {
                tmp = s[i] - '0';
                if(neg == true) {
                    tmp = -tmp;
                }
                result = result * 10 + tmp;
                if(result > pow(2, 31) - 1) {
                    result = pow(2, 31) - 1;
                }
                if(result < -pow(2, 31)) {
                    result = -pow(2, 31);
                }
            }
            else break;
        }
        return result;
    }
};

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

递归法：判断节点的值和p，q比较，如果在p，q之间说明此节点就是祖先，否则就会找根节点的左孩子或者右孩子。

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val > p->val && root->val > q->val)
        return lowestCommonAncestor(root->left, p, q);
        else if(root->val < p->val && root->val < q->val)
        return lowestCommonAncestor(root->right, p, q);
        else return root; 
    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

注意这一题是二叉树，上一题是二叉搜索树。

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return root;
        if(root == p || root == q) return root;//处理根节点
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL)   return root;	//说明root的左孩子和右孩子各有一个指定节点，那么root就是最近公共祖先
        else if(left == NULL && right != NULL)   return right;	//只有右孩子有，说明一个指定节点是右孩子，另一个是右孩子的孩子。所以祖先就是右孩子
        else if(left != NULL && right == NULL)   return left;
        else return NULL;
    }
};

面试题13. 机器人的运动范围 - 力扣（LeetCode）

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

根据题目描述可以知道是用深度优先或者广度优先算法来解决问题。

深度优先算法思路如下：注意要加上visited数组作为标记确定哪些位置已经访问过了，否则可能会出现重复访问的情况。

//注意要对遍历过的进行标记，否则会有重复输出
class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector <vector <bool>> visited(m, vector <bool> (n, false));
        return dfs(0, 0, 0, 0, m, n, k, visited);
    }
    int dfs(int i, int j, int sumi, int sumj, int m, int n, int k, vector <vector <bool>> &visited) {
        if(i >= m || j >= n || sumi + sumj > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0? sumi + 1 : sumi - 8, sumj, m, n, k, visited) + dfs(i, j + 1, sumi, (j + 1) % 10 != 0? sumj + 1 : sumj - 8, m, n, k, visited);
    }
};

面试题45. 把数组排成最小的数 - 力扣（LeetCode）

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

class Solution {
public:
    static bool compare(string& x, string& y) {   //放在类里面，则要在函数前加static，因为类成员函数、变量不是static的话，会有一个默认的this指针参数，这样的话函数指针就和普通的函数指针类型不一样了，加了static的就没有this指针，相当于和类外的普通函数一样,如果想当普通函数用，就要加static
        return x + y < y + x;   //x + y < y + x,说明x应该排在y的前面，比如102
    }
    string minNumber(vector<int>& nums) {
        vector <string> tmps;
        for(auto num : nums) {
            tmps.push_back(to_string(num));
        }
        sort(tmps.begin(), tmps.end(), compare);
        string result;
        for(auto tmp : tmps) {
            result = result + tmp;
        }
        return result;
    }
};

面试题59 - II. 队列的最大值 - 力扣（LeetCode）

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

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

实际上还是单调队列的思想，用一个maxque从front到back存储从大到小的数据。

class MaxQueue {
public:
    queue <int> que;
    deque <int> maxdeq; //从front到back递减
    MaxQueue() {

    }
    
    int max_value() {
        if(!maxdeq.empty()) {
           return maxdeq.front(); 
        }
        else {
            return -1;
        }
    }
    
    void push_back(int value) {
        que.push(value);
        while(!maxdeq.empty() && value > maxdeq.back()) {
            maxdeq.pop_back();
        }
        maxdeq.push_back(value);
    }
    
    int pop_front() {
        if(que.empty()) {
            return -1;
        } 
        int val = que.front();
        if(val == maxdeq.front()) {
            maxdeq.pop_front();
        }
        que.pop();
        return val;
    }
};

/**
 * 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();
 */

面试题61. 扑克牌中的顺子 - 力扣（LeetCode）

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

其实就是不管0，不重复而且最大和最小的差值小于5即可构成顺子。

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int maxcount = 0;
        int mincount = 14;
        set <int> mset;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) {
                continue;
            }
            if(mset.count(nums[i]) != 0) {
                return false;
            }
            maxcount = max(nums[i], maxcount);
            mincount = min(nums[i], mincount);
            mset.insert(nums[i]);
        }
        return maxcount - mincount < 5;
    }
};