2022/7/19

The finger of the sword Offer 61. Shunzi in playing cards

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // Sort 

        int joker = 0;
        for(auto &x : nums) {
            if(x == 0) joker++;
            else break;
        }

        if(joker >= 4) return true; //4 More than two big and small Wang directly become shunzi 

        for(int i = joker + 1;i < 5;i++) {
            int diff = nums[i] - nums[i - 1];
            if(diff == 0) return false; // The difference between before and after is 0, return false
            else if(diff == 1) continue;
            else {  // Use size Wang to offset the difference 
                joker -= (diff - 1);
                if(joker < 0) return false;
            }
        }
        return true;
    }
};

The finger of the sword Offer 62. The last number in the circle

Joseph Ring problem

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;
    }
};

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> res(a.size(), 1);
        for(int i = 1;i < a.size();i++) {   // Traversing from front to back , Calculation a[i] Product of previous 
            res[i] = res[i - 1] * a[i - 1];
        }

        int s = 1;
        for(int j = a.size() - 1;j >= 0;j--) {  // Calculation a[i] Product after 
            res[j] *= s;
            s *= a[j];
        }
        return res;
    }
};

The original intention of the topic is to find the first val stay p and q The node between .

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        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;        
    }
};

/**
 * 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 || 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;
        else return left == NULL ? right : left;
    }
};

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;
        for(auto &x : arr) heap.push(x);
        vector<int> res;
        for(int i = 0;i < k;i++) {
            res.push_back(heap.top());
            heap.pop();
        }
        return res;
    }
};