# 未分類主題

# 171. Excel Sheet Column Number
## Question (Easy)
Given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

Example 1:

Input: columnTitle = "A"
Output: 1
Example 2:

Input: columnTitle = "AB"
Output: 28
Example 3:

Input: columnTitle = "ZY"
Output: 701

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].
## Solution (C++)

class Solution {
public:
    int titleToNumber(string columnTitle) {
        //基本上就是26禁制
        int sum = 0;
        long long int temp = 1;
        for(int i=columnTitle.length()-1; i>=0; i--){
            sum+=((columnTitle[i]-'A'+1)*temp);
            temp*=26;
        }
        return sum;
    }
};

## Notes:
* 基本上這題就是26進位轉10進位而已
---

# 168. Excel Sheet Column Title
## Question (Easy)
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

Example 1:

Input: columnNumber = 1
Output: "A"
Example 2:

Input: columnNumber = 28
Output: "AB"
Example 3:

Input: columnNumber = 701
Output: "ZY"
## Solution (C++)

class Solution {
public:
    string convertToTitle(int columnNumber) {
        map<int, char> mapping;
        for(int i=1; i<=26; i++)
            mapping[i] = char(int('A')+i-1);
        string ans = "";
        while(columnNumber!=0){
            ans = mapping[1+((columnNumber-1)%26)] + ans;
            columnNumber = (columnNumber-1) / 26;
        }
        return ans;
    }
};

## Notes:
* 10進位轉26進位
* 只是要注意沒有0的概念

---
# 2909. Minimum Sum of Mountain Triplets II
## Question (Medium)
You are given a 0-indexed array nums of integers.

A triplet of indices (i, j, k) is a mountain if:

i < j < k
nums[i] < nums[j] and nums[k] < nums[j]
Return the minimum possible sum of a mountain triplet of nums. If no such triplet exists, return -1.

Example 1:

Input: nums = [8,6,1,5,3]
Output: 9
Explanation: Triplet (2, 3, 4) is a mountain triplet of sum 9 since:
- 2 < 3 < 4
- nums[2] < nums[3] and nums[4] < nums[3]
And the sum of this triplet is nums[2] + nums[3] + nums[4] = 9. It can be shown that there are no mountain triplets with a sum of less than 9.
Example 2:

Input: nums = [5,4,8,7,10,2]
Output: 13
Explanation: Triplet (1, 3, 5) is a mountain triplet of sum 13 since:
- 1 < 3 < 5
- nums[1] < nums[3] and nums[5] < nums[3]
And the sum of this triplet is nums[1] + nums[3] + nums[5] = 13. It can be shown that there are no mountain triplets with a sum of less than 13.
Example 3:

Input: nums = [6,5,4,3,4,5]
Output: -1
Explanation: It can be shown that there are no mountain triplets in nums.
## Solution (C++)

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int* left = new int[nums.size()]{};
        int* right = new int[nums.size()]{};
        int min_left = 1000000000;
        int min_right = 1000000000;
        for(int i=0; i<nums.size(); i++){
            left[i] = min_left;
            if(nums[i]<min_left){
                min_left = nums[i];
            }
        }
        for(int i=nums.size()-1; i>=0; i--){
            right[i] = min_right;
            if(nums[i]<min_right){
                min_right = nums[i];
            }
        }
        int minima = INT_MAX;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > left[i] && nums[i] > right[i]){
                int temp = nums[i] + left[i] + right[i];
                if(temp<minima)
                    minima = temp;
            }
        }
        return (minima == INT_MAX)?-1:minima;
    }
};

## Notes:
* 新建兩個array，分別記錄index i 左邊、右邊的最小值
* O(N)去找出minimun sum

---
# 443. String Compression
## Question
Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group's length is 1, append the character to s.
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
## Solution

class Solution {
public:
    int compress(vector<char>& chars) {
        int count = 1;
        for(int i=1; i<chars.size();){
            if(chars[i] == chars[i-1]){
                count++;
                chars.erase(chars.begin()+i, chars.begin()+i+1);
            }
            else{
                if(count>1){
                    string count_str = to_string(count);
                    for(int j=0; j<count_str.length(); j++)
                        chars.insert(chars.begin()+i+j, count_str[j]);
                    i = i+count_str.length()+1;
                }
                else
                    i = i+1;
                count = 1;
            }
        }
        if(count>1){
            string count_str = to_string(count);
            for(int j=0; j<count_str.length(); j++)
                chars.insert(chars.end(), count_str[j]);
        }
        return chars.size();
    }
};

## Notes
* 逐一遍歷chars vector，若遇到不重複的，就插入目前累積的count。
* 這題就單純麻煩而已。

---
# 1503. Last Moment Before All Ants Fall Out of a Plank
## Question (Medium)
We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank immediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right, return the moment when the last ant(s) fall out of the plank

## Solution (C++)

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        //start at 10:32
        int max_left = INT_MIN;
        int min_right = INT_MAX;
        for(int l: left){
            max_left = max(l, max_left);
        }
        for(int r: right){
            min_right = min(r, min_right);
        }
        return max(max_left, n-min_right);
    }
};

## Notes
* 核心觀念:兩隻螞蟻碰撞時，各自的方向會改變，但可以想像成是兩隻螞蟻身分互換繼續走。
* EX: ant1: 1(需要往右走n-1步)，ant2: 2(需要往左走2步)。兩隻在1.5的時候相遇
* 轉變為在T=0.5時，ant1: 1.5(需要往左走1.5步)，ant2: 1.5(需要往左走n-1.5)
* 題目問最後一隻螞蟻是在幾秒的時候掉落的，所以我們只要找行走距離最長的那隻螞蟻即可，這隻螞蟻是誰並不重要。

---
# 1921. Eliminate Maximum Number of Monsters
## Question (Medium)
You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the ith monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the ith monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge. The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.
Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.
Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.
## Solution

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        /*
            (1) 利用dist、speed去算出到達城市的時間
            (2) 直接將time做sort 
            (3) 根據題目對weapone的限制，可以得到第i-th monster的抵達時間至少要>i mins才有可以能摧毀。
            (4) EX: 若第2隻怪獸的預計到達時間是1.5，那weapon就有足夠的時間充能。反之若為0.5，則無法摧毀。
            (5) Line 18~ Line25為核心部分，若沒用此方法很容易TLE
        */
        int n = dist.size();
        int count = 1; 
        vector<double> time(n);
        for(int i=0; i<n; i++){
            time[i] = double(dist[i])/double(speed[i]);
        }
        sort(time.begin(), time.end());
        for(int i=1; i<time.size(); i++){
            if(time[i]>i){
                count++;
            }
            else{
                return count;
            }
        }
        return (count>=n)?n:count;
    }
};

---

# 1877. Minimize Maximum Pair Sum in Array
## Question (Medium)
The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.
Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.
Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.
Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

## Solution (C++)

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = INT_MIN;
        int count = nums.size()/2;
        int left = 0, right = nums.size()-1;
        while(count--){
            res = max(res, (nums[left]+nums[right]));
            left++;
            right--;
        }
        return res;
    }
};

## Notes:
1. 先sort array。
2. 因為我們要得到minimized maximum pair sum，
3. 用two pointer解。left指向最小，right指向最大。

---

# 1980. Find Unique Binary String
## Question (Medium)
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

## Solution (C++)

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        // https://zh.wikipedia.org/zh-tw/%E5%B0%8D%E8%A7%92%E8%AB%96%E8%AD%89%E6%B3%95
        int n = nums.size();
        string ans = "";
        for(int i=0; i<nums.size(); i++){
            int temp = (nums[i][i] - '0');
            if(temp==0)
                ans+="1";
            else
                ans+="0";
        }
        return ans;
    }
};

## Notes:

---
## 3039. Apply Operations to Make String Empty

class Solution {
public:
    string lastNonEmptyString(string s) {
        map<char, int> record;
        string ans = "";
        int max_count = INT_MIN;
        for(int i=0; i<s.length(); i++){
            record[s[i]]++;
            if(record[s[i]] > max_count)
                max_count = record[s[i]];
        }
        for(int i=s.length()-1; i>=0; i--){
            if(record[s[i]]!=max_count || record[s[i]]==0)
                continue; 
            ans = s[i] + ans;
            record[s[i]] = 0;
        }
        return ans;
    }
};

### Notes:
1. 先計算出freq最高的chars，小於最高freq的都可以直接忽略
2. 最後由後面iterate回去即可找出答案

---

## 3038. Maximum Number of Operations With the Same Score I

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int score = 0;
        int pre_score = 0;
        int ans = 0;
        for(int i=0; i<nums.size()-1; i+=2){
            score = nums[i] + nums[i+1];
            if(score!=pre_score && i!=0){
                break;
            }
            pre_score = score;
            ans++;
        }
        return ans;
    }
};

### Notes:
1. 這題沒必要直接去刪除nums這個array來模擬題目的要求
2. 只要判斷nums[i] + nums[i+1]是否跟前一次iteration一樣即可
---
## 3070. Count Submatrices with Top-Left Element and Sum Less Than k

class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int r = grid.size(), c = grid[0].size();
        vector<vector<int>> pre_sum(r, vector<int>(c, 0));
        int count = 0, sum = 0;
        for(int i=0; i<r; i++){
            sum = 0;
            for(int j=0; j<c; j++){
                sum+=grid[i][j];
                pre_sum[i][j] = sum;    
            }
        }
        sum = 0;
        for(int j=0; j<c; j++){
            sum = 0;
            for(int i=0; i<r; i++){
                sum+=pre_sum[i][j];
                if(sum<=k)
                    count++;
            }
        }
        return count;
    }
};

### Notes:
1. 只要先建立一個nxn的array，arr[i][j]表示sum(arr[i][0]+...arr[i][j])
2. 有了這個2d array，我們就只需要O(NxN)的時間複雜度來判斷這個submatrix是否符合條件

## 3014. Minimum Number of Pushes to Type Word I

class Solution {
public:
    int minimumPushes(string word) {
        int str_length = word.length();
        int ans = 0;
        for(int i=1; i<=str_length/8; i++){
            ans = ans + i*8;
        }
        ans = ans + (1 + int(str_length / 8)) * (str_length % 8);
        return ans;
    }
};

### Notes:
1. 因為這個string的字元不會重複，所以只需要計算str_length/8和str_length%8做計算即可
2. 有O(1)的解法但是我懶

---
## 3016. Minimum Number of Pushes to Type Word II

class Solution {
public:
    int minimumPushes(string word) {
        map<char, int> counting;
        map<char, int> value;
        priority_queue<pair<int, char>> pq;
        for(int i=0; i<word.length(); i++){
            counting[word[i]]++;
        }
        for(auto it=counting.begin(); it!=counting.end(); it++){
            pq.push(make_pair(it->second, it->first));
        }
        int char_num = pq.size();
        for(int i=0; i<char_num; i++){
            pair<int, char> temp = pq.top();
            pq.pop();
            value[temp.second] = int(i/8) + 1;
        }
        int ans = 0;
        for(int i=0; i<word.size(); i++){
            ans+=value[word[i]];
        }
        return ans;
    }
};

### Notes:
1. 跟 3014. Minimum Number of Pushes to Type Word I，只不過input string裡面會有重複的character
2. 我們要統計每個character的freqency，因為出現越多次，就要讓**他按的次數最少**，最終結果才會是minimun。
3. 用priority queue，每次都pop出freq最高的character，並判斷這個character需要按幾次 (line 17)