leetcode biweekly-contest-83

发布于 2022-07-25  857 次阅读


Best Poker Hand

You are given an integer array ranks and a character array suits. You have 5 cards where the ith card has a rank of ranks[i] and a suit of suits[i].

The following are the types of poker hands you can make from best to worst:

  1. "Flush": Five cards of the same suit.
  2. "Three of a Kind": Three cards of the same rank.
  3. "Pair": Two cards of the same rank.
  4. "High Card": Any single card.

Return a string representing the best type of poker hand you can make with the given cards.

Note that the return values are case-sensitive.

Example 1:

Input: ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
Output: "Flush"
Explanation: The hand with all the cards consists of 5 cards with the same suit, so we have a "Flush".

直接按顺序模拟一下

class Solution {
public:
    string bestHand(vector<int> &ranks, vector<char> &suits) {
        bool a = false;
        for (auto &n: suits) {
            if (n != suits[0]) {
                a = 1;
                break;
            }
        }
        if (!a) {
            return "Flush";
        }
        map<int, int> m;
        int ma = 0;
        for (auto &n: ranks) {
            m[n]++;
            ma = max(ma, m[n]);
        }
        if (ma >= 3) {
            return "Three of a Kind";
        }
        if (ma == 2) {
            return "Pair";
        }
        return "High Card";
    }
};

Number of Zero-Filled Subarrays

2348. Number of Zero-Filled Subarrays

  • User Accepted: 10283
  • User Tried: 11095
  • Total Accepted: 10547
  • Total Submissions: 19823
  • Difficulty: Medium

Given an integer array nums, return the number of subarrays filled with 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation: 
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.

题目很短,有多少个全是0的子数组,先看最长的然后。。就算贡献度,1到长度求和

$c_i=\frac{(l_i+1)*l_i}{2}$

class Solution {
public:
    long long zeroFilledSubarray(vector<int> &nums) {
        int now = 0;
        long long ans=0;
        for (auto &n: nums) {
            if (n == 0) {
                now++;
            } else {
                ans += (1ll + now) * now / 2ll;
                now = 0;
            }
        }
        ans += (1ll + now) * now / 2ll;
        return ans;
    }
};

Design a Number Container System

Design a number container system that can do the following:

  • Insert or Replace a number at the given index in the system.
  • Return the smallest index for the given number in the system.

Implement the NumberContainers class:

  • NumberContainers() Initializes the number container system.
  • void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
  • int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. 
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

应该是个map和set的模拟吧,不太难。

class NumberContainers {
public:
    map<int, int> m;
    map<int, set<int>> as;

    NumberContainers() {

    }

    void change(int index, int number) {
        if (m.count(index)) {
            as[m[index]].erase(index);
        }
        as[number].insert(index);
        m[index] = number;
    }

    int find(int number) {
        if (as[number].size() == 0) {
            return -1;
        }
        return *as[number].begin();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */

Shortest Impossible Sequence of Rolls

You are given an integer array rolls of length n and an integer k. You roll a k sided dice numbered from 1 to k, n times, where the result of the ith roll is rolls[i].

Return the length of the shortest sequence of rolls that cannot be taken from rolls.

A sequence of rolls of length len is the result of rolling a k sided dice len times.

Note that the sequence taken does not have to be consecutive as long as it is in order.

Example 1:

Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
Output: 3
Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
Every sequence of rolls of length 2, [1, 1], [1, 2], ..., [4, 4], can be taken from rolls.
The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
Note that there are other sequences that cannot be taken from rolls.

没看懂,但是看用例发现了,就是能组成一组1-k了就ans++

class Solution {
public:
    int shortestSequence(vector<int> &rolls, int k) {
        set<int> f;
        int ans = 1;
        for (auto &n: rolls) {
            f.insert(n);
            if (f.size() == k) {
                ans++;
                f.clear();
            }
        }
        return ans;
    }
};

绝对不是恋爱脑!