LeetCode weekly contest 158

1221. Split a String in Balanced Strings

Understand the definition of balanced, and you will find that we only need to find positions where the counts of L and R are equal.

Time complexity: O(N),
Space complexity: O(1).

impl Solution {
    pub fn balanced_string_split(s: String) -> i32 {
        let mut ans = 0;
        let mut l = 0;
        let mut r = 0;
        for c in s.chars() {
            match c {
                'L' => { l += 1},
                'R' => { r += 1},
                _ => (),
            }
            if l == r {
                ans += 1;
            }
        }
        ans
    }
}

1222. Queens That Can Attack the King

Although understanding the problem is slightly more complicated, the algorithm is actually very direct: search outward from the King, rather than starting from the queens.

Time complexity: O(queens.len() + chessboard.len()),
space complexity: O(queens.len()).

pub fn queens_attackthe_king(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
    let mut qs: HashSet<(i32, i32)> = HashSet::new();
    for queen in queens.iter() {
        qs.insert((queen[0], queen[1]));
    }
    let mut ans: Vec<Vec<i32>> = Vec::new();
    let direction = vec![
        (0, 1),
        (1, 1),
        (1, 0),
        (1, -1),
        (0, -1),
        (-1, -1),
        (-1, 0),
        (-1, 1),
    ];
    let k = (king[0], king[1]);
    for (x, y) in direction.iter() {
        let mut target: (i32, i32) = k;
        loop {
            target.0 += x;
            target.1 += y;
            if target.0 >= 0 && target.0 < 8 && target.1 >= 0 && target.1 < 8 {
                if qs.contains(&target) {
                    ans.push(vec![target.0, target.1]);
                    break;
                }
            } else {
                break;
            }
        }
    }
    ans
}

1223. Dice Roll Simulation

DFS with memoization.

By analyzing the maximum possible size of the memo, we can know:
Time complexity: O(6 * N ^ 2),
space complexity: O(6 * N ^ 2).

use std::collections::HashMap;

impl Solution {
    const MOD_NUMBER: i32 = 1000000007;

    pub fn answer(
        mut memo: &mut HashMap<(i32, usize, i32), i32>,
        roll_max: &Vec<i32>,
        n: i32,
        previous_number: usize,
        previous_consecutive: i32,
    ) -> i32 {
        if n == 0 {
            return 1;
        }
        match memo.get(&(n, previous_number, previous_consecutive)) {
            Some(value) => {
                return *value;
            }
            None => {
                let mut ans = 0;
                for i in 0..6 {
                    if i == previous_number {
                        if previous_consecutive == roll_max[previous_number] {
                            continue;
                        } else {
                            ans = (ans
                                + Solution::answer(&mut memo, &roll_max, n - 1, i, previous_consecutive + 1))
                                % Solution::MOD_NUMBER;
                        }
                    } else {
                        ans = (ans + Solution::answer(&mut memo, &roll_max, n - 1, i, 1)) % Solution::MOD_NUMBER;
                    }
                }
                memo.insert((n, previous_number, previous_consecutive), ans);
                return ans;
            }
        }
    }
    pub fn die_simulator(n: i32, roll_max: Vec<i32>) -> i32 {
        let mut memo: HashMap<(i32, usize, i32), i32> = HashMap::new();
        Solution::answer(&mut memo, &roll_max, n, 0, 0)
    }
}

1224. Maximum Equal Frequency

First clarify the meaning of an array prefix of nums, namely a prefix array.
Then, seeing the bolded exactly one, we know that there are two possible valid prefix arrays:

• The count of the number with the highest occurrence count minus 1 equals the occurrence count of all other numbers.
• One number has occurrence count 1, and all other numbers have the same occurrence count.
  Finally, looking at the data size 10^5, we can basically determine that an O(N * log N) or O(N) algorithm is required.

The algorithm is almost obvious. It is natural to think of using a hash table to record the occurrence count of each distinct number, and using a TreeSet to store the occurrence counts, so that occurrence counts can be updated quickly. Then one pass is enough.

Time complexity: O(N log N),
space complexity: O(N).

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        unordered_map<int, int> count;
        multiset<int> order;
        int ans = 0;
        for (int x = 0; x < nums.size(); ++x) {
            int i = nums[x];
            if (count[i] != 0) {
                auto it = order.find(count[i]);
                order.erase(it);
            }
            ++count[i];
            order.insert(count[i]);
            // detemiate
            auto it1 = order.begin();
            auto it2 = order.end();
            --it2;
            int n = order.size() - 1;
            int length = x + 1;
            if (it1 == it2) {
                ans = x + 1;
            } else {
                if ((*it2) == (*it1) + 1) {
                    if ( (*it2) * 1 + (*it1) * (n) == length) {
                        ans = x + 1;
                    }
                }
                if (*it1 == 1) {
                    if (*it2 * n == length - 1) {
                        ans = x + 1;
                    }
                }
            }
        }
        return ans;
    }
};