题目

原题在此

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor’s advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:
Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:
Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:
Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

• n == candyType.length
• 2 <= n <= 104
• n is even.
• $-10^5$ <= candyType[i] <= $10^5$

解析

首先会想到用set来做, 但题目只要求返回最大值即可所以可以用bitset替代以节省时间和空间. candyType[i]可能的值为 $-10^5$ 到 $10^5$ 一共有200001个数, 储存状态时加上偏移量100000即可.

代码

c++

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        bitset<200001> b;
        int n = candyType.size() / 2;
        for(int i : candyType)
            b[i + 100000] = 1;
        int cnt = b.count();
        return min(n, cnt);
    }
};

题目

原题在此

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:
Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

• Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
• It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
• The total number of FreqStack.push calls will not exceed 10000 in a single test case.
• The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

解析

设计数据结构的题, 选对基本数据结构是关键. 要pop频率最高的元素, 就要统计每个元素出现频率. 用map<element, freq>是个思路; 其次在元素频率相同时, pop最近一次push的元素, 将相同freq的元素放入同一个stack即可 => map<freq, stack<element>>. 类成员变量里定义一个maxFreq, 在出退栈时更新.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class FreqStack {
public:
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> m;
    int maxfreq = 0;
    FreqStack() {}

    // ++i will increment the value of i, and then return the incremented value.
    // i++ will increment the value of i, but return the original value that i held before being incremented.
    void push(int x) {
        maxfreq = max(maxfreq, ++freq[x]);
        m[freq[x]].push(x);
    }

    int pop() {
        int x = m[maxfreq].top();
        m[maxfreq].pop();
        if (!m[freq[x]--].size()) maxfreq--;
        return x;
    }
};

题目

原题在此

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note:

• Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [$−23^1$, $23^1$]. For this problem, assume that your function returns $23^1$ − 1 when the division result overflows.

Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Example 3:
Input: dividend = 0, divisor = 1
Output: 0

Example 4:
Input: dividend = 1, divisor = 1
Output: 1

Constraints:

• $−23^1$ <= dividend, divisor <= $23^1$ - 1
• divisor != 0

解析

题目假设机器只能存32位的整数, 所以不能用long, edge case只好用if处理掉.
直观思路就是在N(numerator, dividend)的绝对值大于0时, 减去尽可能多个的D(denominator, divisor)的绝对值. 并记录减了多少个. 此方法在N非常大或(且)D非常小时会很慢.
虽然不让用乘除操作但是可以用左右位移替代, 每次尝试减去尽可能多个的D.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    // f(N, D) -> (Q, R)
    int divide(int N, int D) {
        if(N == INT_MIN && D == -1) return INT_MAX;
        if(N == INT_MIN && D ==  1) return INT_MIN;
        unsigned int n = abs(N), d = abs(D), q = 0;
        
        for(int i = 31; i >= 0; i--) {
            // subtract (d << i) from n if n still >= 0, add the quotient to q.
            if((n >> i) >= d) {
                n -= (d << i);
                q += (1 << i);
            }
        }
        return (N > 0) == (D > 0) ? q : -q;
    }
};

题目

原题在此
Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed is a permutation of popped.
• pushed and popped have distinct values.

解析

模拟栈的操作, 将pushed依次入栈, 并在每次入栈后尝试pop尽可能多的元素. 最后若popped完全遍历则是合法的.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        auto it = popped.begin();
        for(int i : pushed) {
            s.push(i);
            while(!s.empty() && *it == s.top()) {
                it++;
                s.pop();
            }
        }
        return it == popped.end();
    }
};

题目

原题在此
Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.

Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:
Input: nums = [1,2,3,4]
Output: 0

Example 3:
Input: nums = [1]
Output: 0

Constraints:

• 1 <= nums.length <= $10^4$
• $-10^5$ <= nums[i] <= $10^5$

Follow up: Can you solve it in O(n) time complexity?

解析

1. 从左侧开始向右找到第一次值变小的点, 记做left;
2. 从右侧开始想做找到第一次值变大的点, 记做right;
3. 在[left:right]区间内找到最大值和最小值, 记做min,max; (中间的这一坨里面可能会有比[begin:left]区间里的值小的或比[right:end]区间里大的.)
4. 在[:left]区间内找到min的上界, 既从begin起至left内第一个比min大的位置;
5. 在[right:]区间内找到max的下界, 既从right起至end内第一个大于等于max的位置;
6. 比较上下界的距离.
   这些std函数都是$O(N)$的所以整体复杂度也是$O(N)$.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right && nums[left] <= nums[left + 1]) left++;
        while(right > left && nums[right - 1] <= nums[right]) right--;
        auto [min_it, max_it] = minmax_element(nums.begin() + left, nums.begin() + right + 1);
        auto left_cut = upper_bound(nums.begin(), nums.begin() + left, *min_it);
        auto right_cut = lower_bound(nums.begin() + right, nums.end(), *max_it);
        return distance(left_cut, right_cut);
    }
};

题目

原题在此

Given a balanced parentheses string S, compute the score of the string based on the following rule:

• () has score 1
• AB has score A + B, where A and B are balanced parentheses strings.
• (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:
Input: "()"
Output: 1

Example 2:
Input: "(())"
Output: 2

Example 3:
Input: "()()"
Output: 2

Example 4:
Input: "(()(()))"
Output: 6

Note:

• S is a balanced parentheses string, containing only ( and ).
• 2 <= S.length <= 50

解析

用stack记录字符串,是'('就入栈一个0; 是')'时, 若栈顶为0, 则说明此时括号内还没有数字, 将栈顶元素修改为1; 若不是0,则说明括号内以有元素, 此时应乘二. 累加求和.
当然也可以直接用解释型语言, 替换字符串, 调用表达式.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> stk;
        stk.push(0);
        int tmp;
        for(char c : S) {
            if(c == '(') {
                stk.push(0);
            } else {
                tmp = stk.top();
                stk.pop();
                stk.top() += tmp ? (tmp * 2) : 1;
            }
            
        }
        return stk.top();
    }
};

py

1
2

def scoreOfParentheses(self, S):
    return eval(S.replace(')(', ')+(').replace('()', '1').replace(')', ')*2'))

题目

原题在此

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m<= 300
• -109 <= matix[i][j] <= 109
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• $-10^9$ <= target <= $10^9$

解析

利用题中提到的矩阵每行每列都递增的特性, 从左下或右上开始,一次排除一行或一列即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
         int i = 0;
         int j = matrix[0].size() - 1;

         while(i < matrix.size() && j >= 0) {
             if(matrix[i][j] == target) return true;
             if(matrix[i][j] < target)  i++;
             else                       j--;
         }
         return false;
    }
};

题目

原题在此

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Example 2:

Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"

Constraints:

• 1 <= s.length<= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s and dictionary[i] consist of lowercase English letters.

解析

根据题意, 将字典按照先长度后字典序的规则排序, 然后逐一比对s中是否包含字典元素的子序列即可.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#pragma GCC optimize("Ofast")
static auto speedup = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:    
    string findLongestWord(string s, vector<string>& d) {
        auto cmp = [](string &a, string &b) {
            if(a.length() != b.length())
                return a.length() > b.length();
            return a < b;
        };
        sort(d.begin(), d.end(), cmp);
        
        for(auto word : d) {
            if(contains(s, word))
                return word;
        }
        return "";
    }

private:
    inline bool contains(string &s, string &t) {
        int n = s.length(), m = t.length();
        int i = 0 , j = 0;
        while(i < n and j < m)
            if(s[i] == t[j]) i++ , j++;
            else i++;
        return j == m;
    }
};

题目

原题在此

On a broken calculator that has a number showing on its display, we can perform two operations:

• Double: Multiply the number on the display by 2, or;
• Decrement: Subtract 1 from the number on the display.
  Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:
Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:
Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:
Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

• 1 <= X <= $10^9$
• 1 <= Y <= $10^9$

解析

X变Y等价于通过加法和除法使Y变X. 贪心地执行除法操作, 能整除2就除, 不能就加一, 直到Y比X小的时候, 此时在补上 X - Y个加一操作即可.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int brokenCalc(int X, int Y) {
        int res = 0;
        while (Y > X) {
            res++;
            Y = Y & 1 ? Y + 1 : Y >> 1;
        }

        return res + X - Y;
    }
};

题目

原题在此
Roman numerals are represented by seven different symbols: "I, V, X, L, C, D, M".

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.
  Given a roman numeral, convert it to an integer.

Example 1:
Input: s = “III”
Output: 3
Example 2:
Input: s = “IV”
Output: 4
Example 3:
Input: s = “IX”
Output: 9
Example 4:
Input: s = “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

解析

根据题意, 当一个值小的字母出现在值大的字母左侧时, 应该减去它的值; 否则就是累加.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> mp = { { 'I' , 1 }, { 'V' , 5 }, { 'X' , 10 }, { 'L' , 50 }, { 'C' , 100 }, { 'D' , 500 }, { 'M' , 1000 } };

       int sum = mp[s.back()];
       for (int i = s.length() - 2; i >= 0; --i) {
           if (mp[s[i]] < mp[s[i + 1]]) sum -= mp[s[i]];
           else sum += mp[s[i]];
       }
       return sum;
    }
};