[leetcode 1680] CONCATENATION OF CONSECUTIVE BINARY NUMBERS

Problem: 

輸入一數字n，將1到n的binary concatenate在一起後，輸出最後的數字。由於數字太大，所以取10^9+7的餘數。

Example 1:

Input: n = 1
Output: 1
Explanation: "1"  

Example 2:

Input: n = 3
Output: 27
Explanation: "11011"

Example 3:

Input: n = 12
Output: 505379714
Explanation:  "1101110010111011110001001101010111100".

Programming Language: C++

Execution time: 256 ms

Solution:

先將數字reverse，再串起來

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

class Solution { public: int concatenatedBinary(int n) { const int modulo = 1000000007; long long int result = 0; for(int num = 1;num <= n;num++){ int count = 0; int binary = num, reverse_binary = 0; while(binary){ reverse_binary = (reverse_binary << 1) | (binary & 0x01); binary >>= 1; count++; } while(count--){ result = (result << 1) | (reverse_binary & 0x01); reverse_binary >>= 1; } result %= modulo; } return result; } };

[leetcode 1679] MAX NUMBER OF K-SUM PAIRS

Problem: 

輸入一陣列nums和一數字k，找出總共有幾對數字的總和為k。

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: 
[1,4], [2,3]

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: 
[1,4,3]

Programming Language: C++

Execution time: 584 ms

Solution:

先用hash table判斷是否找得到k – num，如果可以總和等於k的次數加一，如果不行，則計數該數字出現的次數，

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

class Solution { public: int maxOperations(vector<int>& nums, int k) { int count = 0; map<int, int> count_map; for(int num : nums){ int remain = k - num; if(count_map.find(remain) != count_map.end() && count_map[remain]){ count_map[remain]--; count++; }else{ count_map[num]++; } } return count; } };

[leetcode 1678] GOAL PARSER INTERPRETATION

GOAL PARSER INTERPRETATION

Problem: 

輸入一字串，依照下列規則取代出現過的字串:

(al) => al

() => o

G => G

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"

Programming Language: C++

Execution time: 4 ms

Solution:

由於輸入字串只會出現有效的字串，使用look ahead去判斷每一個字串。

class Solution {
public:
    string interpret(string command) {
        string result;
        for(int idx = 0;idx < command.size();idx++){
            if(idx + 1 < command.size() && command[idx] == '(' && command[idx + 1] == ')'){ // () => o
                result += "o";
                idx++;
            }else if(idx + 3 < command.size() && command[idx] == '(' && command[idx + 1] == 'a'){ // (al) => al
                result += "al";
                idx += 3;
            }else { //G
                result += command[idx];
            }
        }    
        return result;
    }
};

[leetcode 1582] Special Positions in a Binary Matrix

Problem: 

給定一個二維二元矩陣(只有0或1)，找到row方向和column方向皆只有自己一個1的位置，統計出現這樣special pattern的次數並回傳。

Example 1:

Input: mat = [[1,0,0],
              [0,0,1],
              [1,0,0]]
Output: 1
Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],
              [0,1,0],
              [0,0,1]]
Output: 3
Explanation: (0,0), (1,1) and (2,2) are special positions. 

Example 3:

Input: mat = [[0,0,0,1],
              [1,0,0,0],
              [0,1,1,0],
              [0,0,0,0]]
Output: 2

Example 4:

Input: mat = [[0,0,0,0,0],
              [1,0,0,0,0],
              [0,1,0,0,0],
              [0,0,1,0,0],
              [0,0,0,1,1]]
Output: 3

Programming Language: C++

Execution time: 40 ms

Solution:

1.先統計row、column方向的1數量 (row histogram和column histogram)

2.找出column為1的位置

3.以row方向為1的row進行搜尋，找到同時column和row方向皆為1的位置。由於一個row只會出現1次special pattern，所以找到就break for loop

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        vector<int> row_count(mat.size(), 0);
        vector<int> col_count(mat[0].size(), 0);
        
        for(int row = 0;row < mat.size();row++){
            for(int col = 0;col < mat[row].size();col++){
                row_count[row] += mat[row][col];
                col_count[col] += mat[row][col];
            }
        }
        
        vector<int> one_col_count;
        for(int col = 0;col < col_count.size();col++){
            if(col_count[col] == 1) one_col_count.push_back(col);
        }
        
        int special_count = 0;
        for(int row = 0;row < mat.size();row++){
            if(row_count[row] == 1){
                for(int index : one_col_count){
                    if(mat[row][index] == 1){
                        special_count++;
                        break;
                    }
                }
            }
        }
        
        return special_count;
    }
};

[leetcode 1551] Minimum Operations to Make Array Equal

Problem: 

給定一個n，會產生一個奇數陣列，並對陣列進行操作，每次操作可以選擇兩個陣列元素，對一個元素進行+1，對一個元素進行-1。試問需經過多少次運算，陣列的數字才全部一樣。

Example 1:

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5] 

Example 2:

Input: n = 6
Output: 9

Programming Language: C++

Execution time: 0 ms

Solution:

由於n除2的數字一定位於陣列的中間

而且一定是將0和n-1位置的數字進行操作

1和n-2、2和n-3、以此類推…

可以發現，其需要的次數剛好為n – 1, n – 3, n – 5, …, 1

所以只須求該數列的和，即為答案

class Solution {
public:
    int minOperations(int n) {
        // 1, 3, 5, 7, 9, 11
        // 5 + 3 + 1
        return (1 + (n - 1)) * n / 4;
    }
};

 

[leetcode 1550] Three Consecutive Odds

Problem: 

判斷一個陣列有沒有連續三個奇數。

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: 沒有連續三個奇數

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] 是連續三個奇數

Programming Language: C++

Execution time: 16 ms

Solution:

用一個計數器實做。

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        int odd_cnt = 0;
        
        for(int element : arr){
            odd_cnt = (element & 0x01) ? odd_cnt + 1 : 0;
            if(odd_cnt >= 3){ return true; }
        }
        
        return false;
    }
};

 

[leetcode 1493] Longest Subarray of 1’s After Deleting One Element

Problem: 

輸入一個只包含0和1數字的陣列，判斷陣列在刪除一個數字之後，最多可以連續幾個1。

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: 刪除0

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: 刪除第二個零後，有連續5個1

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: 如果全部都是1，則至少需刪除一個數字

Example 4:

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

Example 5:

Input: nums = [0,0,0]
Output: 0

Programming Language: C++

Execution time: 88 ms

Solution:

使用四個變數，分別去紀錄:

prev_one_cnt: 前一次1的數量

one_cnt: 現在1的數量

prev_zero_cnt: 前一次0的數量

zero_cnt: 現在0的數量

 

出現0:

如果遇到1個0，則紀錄prev_one_cnt

如果遇到1個以上的0，則把prev_one_cnt歸零

 

出現1:

看到第一個1，如果曾經出現過零，則記錄prev_zero_cnt，zero_cnt歸零

如果prev_zero_cnt==1，則判斷one_cnt+prev_one_cnt有沒有大於max_one_cnt

如果prev_one_cnt==0，則只判斷one_cnt有沒有大於max_one_cnt

 

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int prev_one_cnt = 0, one_cnt = 0;
        int prev_zero_cnt = 0, zero_cnt = 0;
        int max_one_cnt = 0;
        for(int num : nums){
            if(num == 0){ 
                zero_cnt++;
                if(zero_cnt == 1){
                    prev_one_cnt = one_cnt;
                    one_cnt = 0;
                }else{
                    prev_one_cnt = 0;
                }
            }else{
                if(zero_cnt){
                    prev_zero_cnt = zero_cnt;
                    zero_cnt = 0;
                }
                one_cnt++;
                if(prev_zero_cnt == 1 && max_one_cnt < prev_one_cnt + one_cnt) max_one_cnt = prev_one_cnt + one_cnt;
                else if(max_one_cnt < one_cnt) max_one_cnt = one_cnt;
            }
        }
        
        return prev_zero_cnt == 0 && zero_cnt == 0 ? max_one_cnt - 1 : max_one_cnt;
    }
};

 

[leetcode 1481] Least Number of Unique Integers after K Removals

Problem: 

輸入一個陣列和k，判斷移除k個數字之後，最少可以剩下幾個不重複的數字。

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: 移除1個4

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: 移除2、4和兩個1的其中一個，或是三個3的其中一個

Programming Language: C++

Execution time: 520 ms

Solution:

Greedy

1.統計每個數字的出現次數

2.對次數做排序

3.先從最少次數的數字先移除

4.”總共有幾個數字”減去”移除的數量”，即剩下數字的數量

class Solution {
public:
    
    static bool cmp(pair<int, int> &p1, pair<int, int> &p2){
        return p1.second < p2.second;
    }
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        int unique_cnt = 0, sum = 0;
        map<int, int> h;
        
        for(int num : arr) h[num]++;
        
        vector<pair<int, int>> nums(h.begin(), h.end());
        sort(nums.begin(), nums.end(), cmp);
        
        for(pair<int, int> p : nums){
            //cout << p.first << ", " << p.second << endl;
            sum += p.second; 
            if(sum > k){
                break;
            }
            unique_cnt++;
        }
        
        return h.size() - unique_cnt;
    }
};

 

[leetcode 1363] Largest Multiple of Three

Problem: 

給定一個陣列，陣列包含0到9的任意數量的數字，試從數字當中找出一個最大的數字組合，且需被3整除。

Programming Language: C++

Execution time: 16 ms

Solution:

1.統計每個數字出現次數digit_cnt、計算數字總和sum、把每個數字取三的餘數，並放到長度為3的陣列remain。

2.如果數字總和sum的餘數為零，那麼直接以現有數字由大到小的排序結果回傳

3.如果數字總和sum的餘數不等於零，那麼則把造成該餘數的數字移除，舉例來說:

若sum餘數為1，則把所有餘數等於1的數字移除，如1、4、7

若sum餘數為2，則把所有餘數等於2的數字移除，如2、5、8

如果想要移除1，但找不到餘數為1的數字，那麼移除餘數為2的最小兩個數字

如果想要移除2，但找不到餘數為2的數字，那麼移除餘數為1的最小兩個數字

class Solution {
public:
    
    void findTwoMin(vector<int> &nums, int *firstMin, int *secondMin){
        *firstMin = INT_MAX;
        *secondMin = INT_MAX;
        for(int idx = 0;idx < nums.size();idx++){
            if(nums[idx] < *firstMin){
                *secondMin = *firstMin;
                *firstMin = nums[idx];
            }else if(nums[idx] < *secondMin){
                *secondMin = nums[idx];
            }
        }
    }
    
    int findMin(vector<int> &nums){
        int min_num = nums[0];
        for(int idx = 1;idx < nums.size();idx++){
            if(min_num > nums[idx]) min_num = nums[idx];
        }
        return min_num;
    }
    
    string largestMultipleOfThree(vector<int>& digits) {
        int digit_cnt[10] = {0};
        vector<vector<int>> remain(3, vector<int>());
        int sum = 0;
        for(int digit : digits){
            remain[digit % 3].push_back(digit);
            sum += digit;
            digit_cnt[digit]++;
        }
        if(sum == 0){ return "0"; }
        int remainder = (sum % 3);
        if(remainder != 0){
            int firstMin, secondMin;
            if(remain[remainder].size() != 0){
                firstMin = findMin(remain[remainder]);
            }else{
                findTwoMin(remain[3 - remainder], &firstMin, &secondMin);
                digit_cnt[secondMin]--;
            }
            digit_cnt[firstMin]--;
        }
        
        //construct string
        string res;
        for(int idx = 9;idx >= 0;idx--){
            while(digit_cnt[idx] != 0){
                res += (char)(idx + '0');
                digit_cnt[idx]--;
            }
        }
        
        return res;
    }
};

 

[leetcode 893] Groups of Special-Equivalent Strings

Problem: 

輸入字串陣列，判斷這些字串可以分成幾個group。

哪些字串視為同個group?

每個字串可以透過在奇數位置上字元任意數量的移動，或偶數位置上字元任意數量的移動後，字串相同的字串視為同個group。

Example 1:

Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
Explanation: 
可以分成三個group
["abcd", "cdab", "cbad"], ["xyzz", "zzxy"], ["zzyx"].  

Example 2:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3

Programming Language: C++

Execution time: 12 ms

Solution:

1.先將所有字串在奇數位置、偶數位置上進行排序

2.再判斷該字串是否有出現過，有的話則不插入集合set

沒有的話則插入集合set，意即群組數量加一

class Solution {
public:
    
    void sort(string &str){
        int even_table[26] = {0};
        int odd_table[26] = {0};
        int idx, odd, even;
        for(idx = 0;idx < str.size();idx++){
            if(idx & 0x01){
                odd_table[str[idx] - 'a']++;
            }else{
                even_table[str[idx] - 'a']++;
            }
        }
        odd = 0; even = 0;
        for(idx = 0;idx < str.size();idx++){
            if(idx & 0x01){
                while(odd < 26 && odd_table[odd] == 0) odd++;
                str[idx] = 'a' + odd;
                odd_table[odd]--;
            }else{
                while(even < 26 && even_table[even] == 0) even++;
                str[idx] = 'a' + even;
                even_table[even]--;
            }
        }
        
    }
    
    int numSpecialEquivGroups(vector<string>& A) {
        set<string> words;
        
        for(string str : A){
            sort(str);
            if(words.find(str) == words.end()){
                words.insert(str);
            }
        }
        
        return words.size();
    }
};