<style>
.easy{
color:green;
}
.medium{
color:#eda35e;
}
.red{
color:red;
}
</style>
# String / Array
## :speech_balloon: 介紹
此為LeetCode 75的解題筆記與紀錄，裡面包含解題Code與想法

* 先備知識
* C++ program
* Dynamic Programming (只有一題用到)

* 文章分類 (針對初學者)
* 難度：★★★ ~ ★★★★

### Merge Strings Alternately <span class="easy">(esay)</span>
---

>You are given two strings word1 and word2.
>Merge the strings by adding letters in alternating order, starting with word1.
> If a string is longer than the other, append the additional letters onto the end of the merged string.
>

class Solution {
    public:
        string mergeAlternately(string word1, string word2) {
            string mergestr = "";
            int i  = 0;
            while(i < word1.length() || i < word2.length()){

                if(i < word1.length()){
                    mergestr += word1[i];
                }

                if(i < word2.length()){
                    mergestr += word2[i];
                }

                i++;
            }
            return mergestr;
        }
};

### Greatest Common Divisor of String <span class="easy">(esay)</span>
---
>For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

>Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.


:::success
**想法**
1. str1 + str2 = str2 + str1 則兩字串必有gcd (能夠用common string整除，不管左串接還是右串接必須相等否則無法整除)
2. 能夠整除的substring長度 必為 str1.length()和str2.length()之gcd

:::

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        return (str1 + str2 == str2 + str1)? str1.substr(0,gcd(size(str1),size(str2))):"";
    }
};

### Kids With the Greatest Number of Candies <span class="easy">(esay)</span>
---
>There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

>Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

>Note that multiple kids can have the greatest number of candies.

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        
        //find the maximum number
        int maximum = *max_element(candies.begin(),candies.end());    

        //give extraCandies
        vector<bool> result(candies.size(),1);
        for(int i = 0 ; i < candies.size() ; i++){
            if(candies[i]+extraCandies < maximum) result[i] = 0;            
        }
        return result;
    }
};

>[vector container](https://en.cppreference.com/w/cpp/container/vector)

### Can Place Flowers <span class="easy">(esay)</span>
---

>You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
>
>Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

:::success
**想法**
1. 每找到一個可種植空位n-=1
2. 可種植判斷條件為左邊為0右邊也為0
3. 合併特殊情況 i = 0(頭) or i = flowerbed.size-1(尾)
:::

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {     

        for(int i = 0 ; i < flowerbed.size(); i++){
            if(flowerbed[i] == 0 && (i==0 || flowerbed[i-1] == 0) && (i==flowerbed.size()-1 || flowerbed[i+1] == 0)){
                flowerbed[i] = 1;
                --n;
            }
            if(n <= 0)return 1;            
        }

        return 0;
    }
};

### Reverse Vowels of a String <span class="easy">(esay)</span>
---

>Given a string s, reverse only all the vowels in the string and return it.
>
>The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

class Solution {
public:
    bool isVowels(char ch){
        ch = tolower(ch);
        return ch == 'a' || ch == 'e'|| ch == 'i'|| ch == 'o'|| ch == 'u';
    }
    string reverseVowels(string s) {
        int left = 0;
        int right = s.size()-1;        
        while(left < right){            
            if(isVowels(s[left]) && isVowels(s[right])){
                swap(s[left],s[right]);
                left ++;
                right --;
            }
            else if(!isVowels(s[left])){
                left++;
            }
            else{
                right--;
            }
        }
        return s;
    }
};

### Reverse Words in a String <span class="medium">(medium)</span>
---
>Given an input string s, reverse the order of the words.
>
>A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
>
>Return a string of the words in reverse order concatenated by a single space.
>
>Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

:::success
**想法**
1. r_index 指向**單字的尾巴**，l_index 指向**單字的頭**，當l_index指向**空白**或**等於0**時，立即將此單字串接到result
2. 思考r_index與l_index各種情況所代表意義
3. 串接新單字時，會先添加空白再串接單字以達單字空格效果，最後再把第一個單字空白消除
:::

class Solution {
public:
    string reverseWords(string s) {
        int r_index = s.size()-1;
        int l_index = r_index;
        string result = "";
        // 從尾巴搜尋單字
        while(r_index >= 0){
            // s[r_index] 為空格時代表還沒指向新的單字尾
            if(s[r_index] == ' '){
                r_index--;
            }
            // 找到新的單字，開始調整l_index位置並找到單字的頭
            else if(l_index >= r_index){
                l_index = r_index-1;
            }
            // l_index指向空白或-1代表找到單字的頭可以串接了
            else if(l_index == -1 || s[l_index]==' '){
                result += ' ';
                for(int i = l_index+1 ; i <= r_index;i++){
                    result += s[i];
                }
                r_index = l_index;
            }
            else{
                l_index--;
            }

        }
        result.erase(0,1);
        return result;
    }
};

### Product of Array Except Self <span class="medium">(medium)</span>
---

>Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
>
>The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
>
>You must write an algorithm that runs in O(n) time and without using the division operation.

:::success
想法
1. 因題目要求不可使用除法且時間複雜度為O(n)，要做到如此乘法結果不可一直重複計算否則為O(n^2)
2. 必須要利用之前計算結果以此節省計算次數，觀察可否可利用Dynamic Programming解
3. 觀察並撰寫轉換式，發現左邊乘法會隨著i遞增會與i-1結果相關，且右乘法j-1會與j結果相關，故分開處理
:::

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {   
        int num = nums.size();     
        vector<int> result(nums.size()); 
        result[0] = 1; 
        //compute left Product
        for(int i = 1 ; i < num; i++){
            result[i] = result[i-1] * nums[i-1];
        }

        //compute right Product
        int right = 1;
        for(int j = num-1 ; j >= 0; j--){
            result[j] *= right;
            right *= nums[j];
        }
        return result;
    }
};

### Increasing Triplet Subsequence <span class="medium">(medium)</span>
---
>Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

:::success
想法
1. 初始a跟b是無限大，如果出現比a小就將a換為該數字，若比a大且比b小就將b紀錄為該數字
2. 搜尋過一次陣列用a、b紀錄陣列元素是否有a < b < c條件存在，不用紀錄c的原因是如果出現c就為true，所以不用額外紀錄

:::

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {  
        int a,b; 
        a = INT_MAX;
        b = INT_MAX;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] <= a){
                a = nums[i]; 
            }
            else if(nums[i] <= b){
                b = nums[i];
            }
            else{
                return true;
            }
        }
        return false;

    }
};

### String Compression <span class="medium">(medium)</span>
>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.

:::success
想法
1.因題目是看input的chars評分，要邊改chars邊走訪chars，所以為了區分原始資料與新的資料，故利用利用current_index紀錄當前壓縮新的vector之index位置
2.利用i遍歷整個vector，直到vector.end()
3.當count == 1 時代表為新的character加入到當前current_index並向右移一格
4.如果走訪時遇到character與上一個不同，此時要結算count(之前character出現次數)，並將count重新設為0

:::

class Solution {
public:  
    int compress(vector<char>& chars) {
        int current_index = 0;
        for(int i = 1 , count = 1 ; i <= chars.size(); i++, count++){
            //甚麼時候要加入數字
            //1.當目前字元與上一個字元不同時
            //2.到了vector尾巴沒有下一個字元
            //i == chars.size()放前面的原因是成立時就不會執行右邊判斷，就不會超出index範圍
            if(i == chars.size() ||chars[i] != chars[i-1]){
                //當字元不一樣時，先將之前的字元放入chars並結算出現次數
                chars[current_index++] = chars[i-1];
                if(count > 1){
                    for(char c : to_string(count)){
                        chars[current_index++] = c;
                    }
                }
                //設0的原因是等下count會++，所以count = 1(目前新字元個數)
                count = 0;                
            }
        }
        return current_index;
    }
};

###### tags: `LeetCode 75` `Algorithm`