本週題目

1. Subarray Sum Equals K
2. Bitwise AND of Numbers Range
3. LRU Cache
4. Jump Game
5. Longest Common Subsequence
6. Maximal Square
7. First Unique Number

Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2

Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Hint #1
Will Brute force work here? Try to optimize it.

Hint #2
Can we optimize it by using some extra space?

Hint #3
What about storing sum frequencies in a hash table? Will it be useful?

Hint #4
sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1. Can we use this property to optimize it.

Solution 1

• 直接暴力法竟然過了！
  • 在每個位置上遍歷不同長度的子數列，若子數列總和為 k 則累加。

class Solution {
   public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                ans += (sum == k);
            }
        }

        return ans;
    }
};

Solution 2

• 題目提示希望我們使用 hash table。

1. 建一個 hashmap 紀錄各總和出現的次數。
2. 根據 Hint #4，我們利用 sum(i,j)=sum(0,j)-sum(0,i) 的特性 -> 子數列和為 sum - k 若存在，則必存在和為 k 的子數列。
3. 因此我們累加 sum - k 出現的次數，總和第一次出現 k 的狀況利用初始化總和為 0 出現一次 => hmap[0] = 1 解決。

class Solution {
   public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hmap;
        hmap[0]++;

        int sum = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            ans += hmap[sum - k];
            hmap[sum]++;
        }

        return ans;
    }
};

</br>

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:
Input: [5,7]
Output: 4

Example 2:
Input: [0,1]
Output: 0

Solution 1 (Time Limit Exceeded)

• 暴力解失敗。

class Solution {
   public:
    int rangeBitwiseAnd(int m, int n) {
        int ans = m, i = m + 1;
        while (i <= n)
            ans &= i++;

        return ans;
    }
};

Solution 2

1. 觀察一下 bitwise AND 在連續整數下的特性，將數轉為二進制來看，因為連續整數每次加 1，會自 LSB (Least Significant Bit) 不斷進位，凡是有出現過 0 的位置其 bitwise AND 的結果就一定是 0 -> 同理就是取 MSB (Most Significant Bit) 相同的 bit 數，其餘為 0。
   從 Example 1 觀察：
   -- 10'd5 = 2'b101, 10'd6 = 2'b110, 10'd7 = 2'b111 -> 2'b100 = 10'd4
2. 於是，我們將邊界的兩個數不斷的右移一個位元（或除以 2）直到兩數相等為止（一樣的MSB），並紀錄右移的位數。
3. 最後，將較小的數再左移回去即為所求。

class Solution {
   public:
    int rangeBitwiseAnd(int m, int n) {
        int cnt = 0;
        while (m != n) {
            m >>= 1;  // m /= 2;
            n >>= 1;  // n /= 2;
            cnt++;
        }

        return m << cnt;
    }
};

Solution 3

1. 我們將 n 和 n-1 做 bitwise AND，一路做到 n <= m。
2. n 和 n-1 做 bitwise AND，其實就是把 n 最右邊位置（LSB）的 1 給丟掉，舉幾個例子：
   ex. 10'd3 = 2'b011, 10'd2 = 2'b010 -> 2'b010 = 10'd2，n: 3 -> 2。
   ex. 10'd2 = 2'b010, 10'd1 = 2'b001 -> 2'b000 = 10'd0，n: 2 -> 0。
   ex. 10'd4 = 2'b100, 10'd3 = 2'b011 -> 2'b000 = 10'd0，n: 4 -> 0。
3. 注意這做法和 Solution 1 暴力解是不同的，一路做 bitwise AND，並不會遍歷整個區間內所有的數，收斂的速度會比暴力解快上不少。

class Solution {
   public:
    int rangeBitwiseAnd(int m, int n) {
        while (n > m)
            n &= n--;

        return n;
    }
};

</br>

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:
LRUCache cache = new LRUCache( 2 / capacity / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Solution

• Follow up: time complexity = O(1)。

1. 顯然又是一題要用 hashmap 解決的問題，但這邊不一樣的是，我們在 hashmap 中保存 key 以及其對應的 list::iterator。
2. 接著建一個 list 保存 key-value 指令，並維持最常用的指令放在 list 的最前面（operationList.begin()）。
3. 先考慮 put 的實現：
   -- 若 key 已經存在，先將這個 key 對應到的 key-value 指令從 list 中移除。
   -- 若 cache 已滿，找出在 list 最後面（operationList.rbegin()）的 key，從 hashmap 中移除，並移除 list 最後面的指令（pop_back()）。注意這裡指向 list 最後面的是 rbegin 而不是 end，end 是指向最後一個元素的下一個位置。
   -- 最後把新增的 key-value 指令放在 list 的最前面（push_front(make_pair(key, value))），並加入 hashmap 中。
4. get 的實現就直覺多了：
   -- 檢查 hashmap，如果 key 不存在 => 回傳 -1。
   -- 存在的話我們利用 list 的 splice() 函數，把 key 對應到的 key-value 指令放到 list 的最前面（operationList.begin()），並回傳對應的 value。

• 這題學到了兩個新東西：
  • list 的 splice() 函數
  • iterator

class LRUCache {
   private:
    int cap;
    list<pair<int, int>> operationList;
    unordered_map<int, list<pair<int, int>>::iterator> hmap;

   public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        if (!hmap.count(key)) return -1;

        auto operation = hmap.find(key)->second;
        operationList.splice(operationList.begin(), operationList, operation);
        return operation->second;
    }

    void put(int key, int value) {
        if (hmap.count(key))
            operationList.erase(hmap.find(key)->second);

        if (operationList.size() == cap) {
            int keyLRU = operationList.rbegin()->first;
            hmap.erase(keyLRU);
            operationList.pop_back();
        }

        operationList.push_front(make_pair(key, value));
        hmap[key] = operationList.begin();
    }
};

</br>

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

Solution 1

• 貪婪演算法 Greedy algorithm 的做法：

1. 因為數值代表你可以跳的最遠距離，我們最後一步是可以跳超過的。
2. 使用貪婪演算法，算出每一個可以抵達的位置最遠可以跳的距離：
   • 用一個變數 maxJump 代表目前跳力，初始為 0。
   • 接著檢查每個位置，如果可以抵達，則將跳力更新。
   • 最後檢查最終跳力是否可以抵達或超過最後一個位置。

class Solution {
   public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();

        int maxJump = 0;
        for (int i = 0; i < n; i++) {
            if (i <= maxJump)
                maxJump = max(nums[i] + i, maxJump);
        }

        return (maxJump >= n - 1);
    }
};

Solution 2

• Solution 1 加入判斷若當前跳力可以抵達或超過最後一個位置，則回傳 true。

class Solution {
   public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();

        int maxJump = 0;
        for (int i = 0; i < n; i++) {
            if (maxJump >= n - 1)
                return true;
            if (i <= maxJump)
                maxJump = max(nums[i] + i, maxJump);
        }

        return (maxJump >= n - 1);
    }
};

Solution 3

• 動態規劃 DP (Dynamic Programming) 的做法：

1. 我們紀錄每個位置的剩餘跳力，一路更新。更新的規則為，每個位置的剩餘跳力等於前一個位置的剩餘跳力或新跳力的較大值減 1。
2. 因為在前一位置有可能原本剩餘的跳力較大或獲得新的跳力補給，所以更新成較大值；而每次往前一步就會消耗掉一格跳力，所以減 1。
3. 一旦在某個位置上的剩餘跳力為負值，表示無法抵達該位置 => 回傳 false。
4. 若能夠完成遍歷數列，表示在最後一個位置上的剩餘跳力仍然大於等於 0，可以抵達 => 回傳 true。

class Solution {
   public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }

        return true;
    }
};

</br>

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

Hint #1
Try dynamic programming. DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j].

Hint #2
DP[i][j] = DP[i - 1][j - 1] + 1 , if text1[i] == text2[j] DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) , otherwise

Solution

• 根據 Hint #1 使用動態規劃 DP (Dynamic Programming) 的做法：

1. 經典的二維動態規劃題型，建立一個二維陣列 dp[i][j]，用來紀錄到目前位置兩字串的最長共同長度。
2. 我們必須初始化邊界的條件，因為 dp[i][0] 和 dp[0][j] 都代表其中一個字串為空，因此需要初始為 0。這也造成到位置 (i, j) 時其實是將兩字串的最長共同長度紀錄在 dp[i+1][j+1]。
   • 若兩個字母相同，則更新為左上方的值加 1，將最長共同長度加 1。
   • 若兩個字母不同，則取上面和左邊的較大值，以維持最長共同長度。

• 從 Example 1 的 DP table 觀察：
  | | i | 0 | 1 | 2 | 3 | 4 | 5 |
  | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
  | j | | a | b | c | d | e | |
  | 0 | a | 0 | 0 | 0 | 0 | 0 | 0 |
  | 1 | c | 0 | 1 | 1 | 1 | 1 | 1 |
  | 2 | e | 0 | 1 | 1 | 2 | 2 | 2 |
  | 3 | | 0 | 1 | 1 | 2 | 2 | 3 |

class Solution {
   public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[text1.size()][text2.size()];
    }
};

</br>

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

Solution 1

• 暴力解，遍歷所有可能為正方形的情形。

1. 從最大有可能的正方形找起，判斷是否為都是 1 的正方形，方法是透過尋找正方形內是否含有 0 來檢查。
2. 同個面積在不同位置上的正方形檢查完後，找面積比較小的情形。
3. 若找到想要的正方形，回傳面積，都沒找到則回傳 0。

class Solution {
   public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (!matrix.size()) return 0;

        int n = min(matrix.size(), matrix[0].size());
        while (n > 0) {
            for (int x = 0; x <= matrix[0].size() - n; x++) {
                for (int y = 0; y <= matrix.size() - n; y++) {
                    if (squareCheck(matrix, x, y, n))
                        return n * n;
                }
            }

            n--;
        }

        return 0;
    }

    bool squareCheck(vector<vector<char>>& matrix, int x, int y, int length) {
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (matrix[y + j][x + i] == '0')
                    return false;
            }
        }

        return true;
    }
};

Solution 2

• 動態規劃 DP (Dynamic Programming) 的做法：

1. 二維動態規劃題型，建立一個二維陣列 dp[row][col]，表示到目前位置所能形成之最大有效正方形的邊長。
2. 先初始化邊界值，因為邊界形成的正方形邊長不可能超過 1，所以其實就是原本 2D binary matrix 的值。
3. 接著尋找規則，因為必須左上、上面、左邊以及自身都是 1 才能形成有效正方形，所以我們在自身為 1 時，更新為左上、上面、左邊三者的最小值。
4. 需另外用一個變數來紀錄全域性的正方形邊長最大值，最後回傳這個邊長的平方即為所求。

• 從 Example 的 DP table 觀察：
  | | i | 0 | 1 | 2 | 3 | 4 |
  | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
  | j | | | | | | |
  | 0 | | 1 | 0 | 1 | 0 | 0 |
  | 1 | | 1 | 0 | 1 | 1 | 1 |
  | 2 | | 1 | 1 | 1 | 2 | 1 |
  | 3 | | 1 | 0 | 0 | 1 | 0 |

class Solution {
   public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        int maxLength = 0;

        vector<vector<int>> dp(rows, vector<int>(cols));
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (!row || !col)
                    dp[row][col] = (matrix[row][col] == '1') ? 1 : 0;
                else if (matrix[row][col] == '1')
                    dp[row][col] = min(dp[row - 1][col - 1], min(dp[row][col - 1], dp[row - 1][col])) + 1;

                maxLength = max(maxLength, dp[row][col]);
            }
        }

        return maxLength * maxLength;
    }
};

</br>

First Unique Number

> You have a queue of integers, you need to retrieve the first unique integer in the queue.
> 
> Implement the FirstUnique class:
> 
>     FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
>     int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
>     void add(int value) insert value to the queue.
> 
> Example 1:
> Input: 
> ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
> [[[2,3,5]],[],[5],[],[2],[],[3],[]]
> Output: 
> [null,2,null,2,null,3,null,-1]
> Explanation: 
> FirstUnique firstUnique = new FirstUnique([2,3,5]);
> firstUnique.showFirstUnique(); // return 2
> firstUnique.add(5);            // the queue is now [2,3,5,5]
> firstUnique.showFirstUnique(); // return 2
> firstUnique.add(2);            // the queue is now [2,3,5,5,2]
> firstUnique.showFirstUnique(); // return 3
> firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
> firstUnique.showFirstUnique(); // return -1
> 
> Example 2:
> Input: 
> ["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
> [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
> Output: 
> [null,-1,null,null,null,null,null,17]
> Explanation: 
> FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
> firstUnique.showFirstUnique(); // return -1
> firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
> firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
> firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
> firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
> firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
> firstUnique.showFirstUnique(); // return 17
> 
> Example 3:
> Input: 
> ["FirstUnique","showFirstUnique","add","showFirstUnique"]
> [[[809]],[],[809],[]]
> Output: 
> [null,809,null,-1]
> Explanation: 
> FirstUnique firstUnique = new FirstUnique([809]);
> firstUnique.showFirstUnique(); // return 809
> firstUnique.add(809);          // the queue is now [809,809]
> firstUnique.showFirstUnique(); // return -1
> 
> Constraints:
>     1 <= nums.length <= 10^5
>     1 <= nums[i] <= 10^8
>     1 <= value <= 10^8
>     At most 50000 calls will be made to showFirstUnique and add.
> 
> Hint #1  
> Use doubly Linked list with hashmap of pointers to linked list nodes. add unique number to the linked list. When add is called check if the added number is unique then it have to be added to the linked list and if it is repeated remove it from the linked list if exists. When showFirstUnique is called retrieve the head of the linked list.
> 
> Hint #2  
> Use queue and check that first element of the queue is always unique.
> 
> Hint #3  
> Use set or heap to make running time of each function O(logn).

Solution 1 (Time Limit Exceeded)

• 暴力解失敗。

class FirstUnique {
   private:
    vector<int> vec;
    unordered_map<int, int> hmap;

   public:
    FirstUnique(vector<int>& nums) {
        vec = nums;
        for (int i : nums) {
            hmap[i]++;
        }
    }

    int showFirstUnique() {
        for (auto i : vec) {
            if (hmap[i] == 1)
                return i;
        }
        return -1;
    }

    void add(int value) {
        vec.push_back(value);
        hmap[value]++;
    }
};

Solution 2

{% note danger %}
後來發現這個解法是錯的，不知道為什麼 OJ 能過＠＠
ex: [[[2,3,5]],[3],[2],[]] 出來的結果會是 -1，但應該是 5。
{% endnote %}

1. 建一個 hashmap，紀錄每個數字出現過的次數。
2. 建一個 list，依序存入還沒出現過的數字。這樣在找 First Unique Number 的時候只要去檢查 list 的開頭即可。

• FirstUnique(int[] nums)：初始化 FirstUnique 時，若數字未曾出現過，則從後面推進 list 中。若出現過且在 list 的最前面，將它從 list 中移出。 -> 只要有出現過應該都要從 list 中移出。
• int showFirstUnique()：檢查 list 最前面的數，若只出現過一次，回傳這個數，否則回傳 -1。
• void add(int value)：和初始化的做法相同。

class FirstUnique {
   private:
    list<int> l;
    unordered_map<int, int> hmap;

   public:
    FirstUnique(vector<int>& nums) {
        for (int i : nums) {
            if (!hmap[i])
                l.push_back(i);
            else if (l.front() == i)
                l.pop_front();

            hmap[i]++;
        }
    }

    int showFirstUnique() {
        int firstUnique = l.front();
        if (hmap[firstUnique] == 1)
            return firstUnique;
        else
            return -1;
    }

    void add(int value) {
        if (l.front() == value)
            l.pop_front();
        else if (!hmap[value])
            l.push_back(value);

        hmap[value]++;
    }
};

Solution 3

{% note warning %}
未進行 OJ 驗證。
{% endnote %}

1. 用 set 紀錄數字是否出現過。
2. 用 list 依序存下 Unique Number。
3. 用 hashmap 紀錄 Unique Number 在 list 中的位置。

• FirstUnique(int[] nums)：依序呼叫 add(int value) 函數。
• int showFirstUnique()：檢查 list 是否為空，空則回傳 -1，否則回傳 list 最前面的數。
• void add(int value)：檢查數字是否已經出現過，出現過的話從 list 和 hashmap 中刪除。若沒出現過，將數字存入 set，從後面推進 list，並將其在 list 中的位置紀錄在 hashmap 中。

class FirstUnique {
   private:
    unordered_set<int> set;
    list<int> l;
    unordered_map<int, list<int>::iterator> hmap;

   public:
    FirstUnique(vector<int>& nums) {
        for (int num : nums) {
            add(num);
        }
    }

    int showFirstUnique() {
        return (l.empty()) ? -1 : l.front();
    }

    void add(int value) {
        if (set.find(value) != set.end()) {
            auto map_iter = hmap.find(value);
            if (map_iter != hmap.end()) {
                list<int>::iterator list_iter = hmap[value];
                l.erase(list_iter);
                hmap.erase(map_iter);  // map.erase(value);
            }
        } else {
            set.insert(value);
            l.push_back(value);
            hmap[value] = --l.end();  // prev(l.end());
        }
    }
};

</br>

• Source code: george16886@GitHub
  • [x] Programming language: C++
  • [x] Environment: ubuntu 16.04
  • [x] Tool: Visual Studio Code
• Category: 30-Day LeetCoding Challenge
• Original post @george16886's blog