请假一天

今天嗯赶了一天 project，大概是来不及写题了，请假一天。

3 月 19 日 每日一题

题目：167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

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

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

思路

这道题可以说是 15. 3Sum 的弱化版，思路很简单（竟然是道 medium），双指针移动，找到 total = target 时 return。

代码

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

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        int left = 0;
        int right = int(numbers.size()) - 1;
        while(left < right){
            int total = numbers[left] + numbers[right];
            if(total < target)
                left++;
            else if(total > target)
                right--;
            else if(total == target){
                res.push_back(left + 1);
                res.push_back(right + 1);
                break;
            }
        }
        return res;
    }
};

3 月 18 日 每日一题

题目：Prefix Replacement

Prefixes are words that can be followed by other letters to form a longer word — let’s call this final, combined word the successor. For example, the prefix “an” followed by the word “other” forms the word “another.” Here, “an” is the prefix and “another” is the successor.
Given a dictionary consisting of many prefixes and a sentence, you need to replace all the successors in the sentence with the prefix forming it. If a successor has many prefixes that can form it, replace it with the prefix with the shortest length.
The input will only have lower-case letters. Return the new sentence in a vector of strings.

1
2
3

Example:
Prefixes: ["cat", "bat", "rat"]
Sentence: ["the", "cattle", "was", "rattled", "by", "the", "battery"] Output: ["the", "cat", "was", "rat", "by", "the", "bat"]

mplementation: Your solution must run in O(PM + NM^2) time, where P represents the number of prefixes in the prefix vector, N represents the number of words in the sentence vector, and M represents the length of the longest string in the sentence vector.

思路

今天这道题来自 281lab 的 handwritten problem。 基本思路是利用 set 存储 prefix。遍历每一个 word 的每一个 character，如果可以在 set 里找到对应 prefix 则 push，prefix，否则 push 原本的 word。

代码

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

vector<string> replace_words(const vector<string>& prefixes,
                             const vector<string>& sentence) {
  // TODO
    unordered_set<string> pref;
    vector<string> res;
    for(auto prefix: prefixes){
        pref.insert(prefix);
    }
    for(auto word: sentence){
        bool isInsert = true;
        string temp = "";
        for(auto character: word){
            temp += character;
            if(pref.count(temp)){
                res.push_back(temp);
                isInsert = false;
                break;
            }
        }
        if(isInsert)
            res.push_back(word);
    }
  return res;
}

3 月 17 日 每日一题

题目：146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.

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

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

思路

这道题出现的时间很合适，刚好 370 讲到 Cache。
本题的思路是使用一个 list 存储 key/value pairs，通过对 pair 位置的调整，以实现 front 为 most recently used，back 为 least recently used。
为了达到 O（1）的 search，我们还需要用一个 hashmap 存储指向每一个 pair 的 iterator，并以 pair 的 key 作为 hashmap 的 key。
实现时通过 splice 将一个 node 移动到 list 的 front。put 可以分为三种情况：exit， not exit && full 和 not exit & not full。顺便 map 的 erase 既可以使用 iterator，也可以直接用 key。

代码

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

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
public:
    LRUCache(int capacity):capacity{capacity} {}

    int get(int key) {
        if(cacheMap.find(key) == cacheMap.end())
            return -1;
        //move to the front
        cache.splice(cache.begin(), cache, cacheMap.find(key)->second);
        return cacheMap.find(key)->second->second;
    }

    void put(int key, int value) {
        pair<int, int> temp{key, value};
        if(cacheMap.find(key) != cacheMap.end()){
            cacheMap[key]->second = value;
            //move to the front
            cache.splice(cache.begin(), cache, cacheMap.find(key)->second);
            return;
        }
        else if(cacheMap.size() == capacity){
            //delete least recently
            cacheMap.erase(cache.back().first);
            cache.pop_back();
        }
        //add
        cache.push_front(temp);
        cacheMap[key] = cache.begin();
    }
};

3 月 16 日 每日一题

题目：953. Verifying an Alien Dictionary

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

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

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

思路

本题使用 hashmap 记录每一个字母的相对大小，之后使用嵌套的 for 循环将 word 的每一个字符修改成字符的相对大小。最后使用 is_sorted 函数判断顺序即可。
时间复杂度 O(ns)

代码

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

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> orders;
        for(int i = 0; i < order.length(); i++){
            orders[order[i] - 'a'] = i;
        }
        for(auto &word: words){
            for(auto &c: word){
                c = orders[c - 'a'];
            }
        }
        return is_sorted(words.begin(), words.end());
    }
};

BTW，今天晚上看到一个很有意思的视频。

3 月 15 日 每日一题

题目：380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.

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

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

思路

本题使用 hashmap 记录每一个 val 在 vector 的 index，以达到 O(1)的 search。 O(1) remove 通过将 val 位置和 vector 末尾值的位置调换再 pop 实现，需要注意的是 swap 之前需要先更新 hashmap 内 vector 末尾值的 index。getRomdom 通过 rand()%nums.size()实现。

代码

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

class RandomizedSet {
public:
    RandomizedSet() {}

    bool insert(int val) {
        if(indexs.find(val) != indexs.end())
            return false;
        nums.push_back(val);
        indexs[val] = int(nums.size() - 1);
        return true;
    }

    bool remove(int val) {
        if(indexs.find(val) == indexs.end())
            return false;
        indexs[nums[nums.size() - 1]] = indexs[val];
        swap(nums[indexs[val]], nums[nums.size() - 1]);
        nums.pop_back();
        indexs.erase(val);
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];
    }
private:
    unordered_map<int,int> indexs;
    vector<int> nums;
};

3 月 14 日 每日一题

题目：3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

本题使用 sliding Window 的解法，设 left 和 right，用 hashmap 记录字母出现频率。向右移动 right，如果当前字母出现次数不为 0，代表该 no repeating substring 已经到终点，此时右移 left，并减一 map 中的频率，直到 counts[right]频率为 0，则新的 no repeating substring 开始。
时间复杂度为 O(n)，空间复杂度 O(1)。

代码

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0){
            return 0;
        }
        unordered_map<char, int>counts;
        int left = 0;
        int right = 1;
        int res = 1;
        counts[s[left]]++;
        while(right < s.length()){
            int temp = right - left;
            while(counts[s[right]] >= 1){
                counts[s[left]]--;
                left++;
                temp--;
            }
            while(right < s.length() && counts[s[right]] == 0){
                counts[s[right]]++;
                right++;
                temp++;
            }
            res = max(temp,res);
        }
        return res;
    }
};

3 月 13 日 每日一题

题目：266. Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

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

Example 1:

Input: "code"
Output: false
Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

思路

本题考虑两种情况，length 为奇数和 length 为偶数，若为偶数所有字母都出现偶数次，若为奇数，只有一个字母出现奇数次。利用 hashmap 记录字母出现频率。

代码

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

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int>counts;
        size_t size = s.length();
        int num = 0;
        for(auto c:s){
            counts[c]++;
        }
        for(auto count:counts){
            if(count.second % 2 == 1){
                num++;
            }
        }
        return num == 0 || (num == 1 && size % 2 == 1);
    }
};

3 月 12 日 每日一题

题目：13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and 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.

eg:

1
2
3

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

思路

使用 hashmap 模拟字典，从前向后遍历 string （除最后一位），如果当前的 vlue 比下一 value 下，说明为 IV 等特殊形式，此时减去此 value，否则加上此 value，for 循环结束后加上最后一个值。

代码

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

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman = { { 'I' , 1 },
                                   { 'V' , 5 },
                                   { 'X' , 10 },
                                   { 'L' , 50 },
                                   { 'C' , 100 },
                                   { 'D' , 500 },
                                   { 'M' , 1000 } };
        int res = 0;
        for(int i = 0; i < s.length() - 1; i++){
            if(roman[s[i]] < roman[s[i + 1]])
                res -= roman[s[i]];
            else
                res += roman[s[i]];
        }
        res += roman[s.back()];
        return res;
    }
};

3 月 11 日 每日一题

题目：209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

eg:

1
2
3
4
5
6
7
8
9

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

思路

Sliding Window

本题最快且最容易理解的写法是使用 sliding window。
建立双指针 left 和 right，移动 right 对 total 进行累加。如果 total 大于等于 target，则触发内部 while 循环，调整 res 之后移动 left, total 减去 left 指向的 value。继续移动 right，直到 right 遍历整个数组。时间复杂度为 O(n)。

Binary Search

使用 Binary Search 写法很有趣。
首先新建数组 total[i]，total 数组为升序。

$total[0] = 0$
$total[i] = nums[0] + nums[1] + … nums[i-1]$

对于每一个 i，利用 Binary Search 找到第一个 j ，满足 j < i 并且 total[j] > total[i] - target。并且易得 total[j - 1] <= total[i] - target

$total[j] > total[i] - target$
则 $nums[0] + nums[1] + nums[j - 1] > nums[0] + nums[1] + nums[i - 1] - target$

$total[j - 1] <= total[i] - target$
则 $nums[0] + nums[1] + … + nums[j - 2] <= nums[0] + nums[1] + … + nums[i - 1] - target$

化简后可得
$target > nums[j] + … +nums[i - 1]$
$target <= nums[j - 1] + … nums[i - 1]$

这意味着对于当前的 i - 1，j - 1 到 i - 1 是最短的满足要求的 subarray。再遍历所有可能的 i 之后，就能找到最短的 subarray。
时间复杂度为 O(nlogn) for * binary search
今天一题顶两题，算是补上了昨天的…

代码

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
36

//sliding window
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = nums.size() + 1;
        int total = 0;
        int left = 0;
        for(int right = 0; right < nums.size(); right++){
            total += nums[right];
            while(total >= target){
                res = min(res, right - left + 1);
                total -= nums[left];
                left++;
            }
        }
            return (res == (nums.size() + 1)) ? 0 : res;
    }
};

//Binary Search
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int res = size + 1;
        vector<int> sums (size + 1, 0);
        for(int i = 1; i < size + 1; i++){
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for(int i = size; i > 0 && sums[i] >= target; i--){
            int j = upper_bound(sums.begin(), sums.end(), sums[i] - target) - sums.begin();
            res = min(res, i - j + 1);
        }
        return (res == (nums.size() + 1)) ? 0 : res;
    }
};