Premium Algo 100 - Array/String

Premium Algo 주제인 Array/String 이다.

---

Maximum Distance in Arrays
link: https://leetcode.com/problems/maximum-distance-in-arrays/

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int curr_min = arrays[0][0], curr_max = arrays[0].back(); 
        int max_dist = INT_MIN; 
        for(int i = 1; i < arrays.size(); i++){
            int next_min = arrays[i][0], next_max = arrays[i].back(); 
            max_dist = max(max_dist, max(abs(curr_max - next_min), abs(curr_min - next_max))); 
            curr_min = min(curr_min, next_min);
            curr_max = max(curr_max, next_max); 
        }
        
        return max_dist; 
    }
};

---

Wiggle Sort
link: https://leetcode.com/problems/wiggle-sort/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        for(int i = 0; i < nums.size()-1; i++){
            if((i % 2 == 0 && nums[i] > nums[i+1]) || (i % 2 == 1 && nums[i] < nums[i+1])){
                swap(nums[i], nums[i+1]); 
            }
        }
    }
};

---

Confusing Number
link: https://leetcode.com/problems/confusing-number/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    bool confusingNumber(int n) {
        map<char,char> hashMap = {{'0','0'}, {'1','1'}, {'6','9'}, {'8','8'}, {'9', '6'}}; 
        string compare = ""; 
        string strN = to_string(n); 

        for(int i = strN.length()-1; i >= 0; i--){
            if(hashMap.count(strN[i])){
                compare.push_back(hashMap[strN[i]]); 
            } else{
                return false; 
            }
        }

        return strN != compare; 
    }
};

---

Perform String Shifts
link: https://leetcode.com/problems/perform-string-shifts/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        for(vector<int>& v : shift){
            int dir = v[0], steps = v[1] % s.length(); 
            if(dir == 0){
                s = s.substr(steps) + s.substr(0,steps); 
            } else{
                s = s.substr(s.length() - steps) + s.substr(0, s.length() - steps); 
            }
        }

        return s; 
    }
};

One Edit Distnace
link: https://leetcode.com/problems/one-edit-distance/description/

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if(s.empty() && t.empty()) return false; 

        if(s.length() > t.length()){
            return isOneEditDistance(t,s); 
        }

        for(int i = 0; i < s.length(); i++){
            if(s[i] != t[i]){
                if(s.length() == t.length()){ //replace 
                    return s.substr(i+1) == t.substr(i+1); 
                } else if(t.length() > s.length()) { //insert 
                    return s.substr(i) == t.substr(i+1); 
                } 
            }
        }


        return (s.length() + 1 == t.length()); 
    }
};

Reverse Words in a String II
link: https://leetcode.com/problems/reverse-words-in-a-string-ii/description/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    void reverseWords(vector<char>& s) {
        reverse(s.begin(),s.end()); 
        int start = 0, end = 0; 
        bool flag = false; 
        while(end < s.size()){
            
            if(s[end] == ' '){
                flag = true; 
                int tmpStart = start;
                int tmpEnd = end - 1; 
                while(tmpStart < tmpEnd){
                    swap(s[tmpStart], s[tmpEnd]); 
                    tmpStart++;
                    tmpEnd--;
                }

                start = end + 1; 
            }


            end++; 
        }

        if(start > 0){
            int tmpStart = start;
            int tmpEnd = end - 1; 
            while(tmpStart < tmpEnd){
                swap(s[tmpStart], s[tmpEnd]); 
                tmpStart++;
                tmpEnd--;
            }
        } else{
            reverse(s.begin(), s.end()); 
        }
    }
};

#개선 된 코드 
class Solution {
public:
    void reverseWords(vector<char>& s) {
        int start = 0, end = 0; 
        reverse(s.begin(), s.end()); 

        while(start < s.size()){
            while(end < s.size() && s[end] != ' ') end++; 
            //cout << end << endl; 
            reverse(s.begin() + start, s.begin() + end); 

            end++; 
            start = end; 
        }

        
    }
};

Shortest Way to Form String
link: https://leetcode.com/problems/shortest-way-to-form-string/?envType=study-plan-v2&envId=premium-algo-100

class Solution {
public:
    int shortestWay(string source, string target) {
        int answer = 0; 
        int start = 0, end = 0; 
        bool flag = false; 
        while(end < target.length()){
            start = 0; //fixed 
            while(start < source.length()){
                if(source[start] == target[end]){
                    start++; //fixed 
                    end++; //fixed 
                    flag = true;  
                } else{
                    start++; 
                } 
            }

            if(!flag) return -1; 
            answer++; //fixed; 
            flag = false; 
        }


        return answer; 
    }
};

---

복습 필요한 문제

1. Maximum Distance in Arrays: 이건 문제를 읽고 조금 로직을 놓치면은 살짝 어려울수도 있는 문제라고 생각한다. 가장 마지막, 그리고 첫번 째 element 를 구하고 싶을 때는 .back(), .front() 메소드를 사용하자.

2. Perform String Shifts : 이런 유형은 원래라면은? 쉬운 문제인데 String 개념이 부족 해졌나.. 다시 한번 해봐야겠다. 단순한 Slicing + 이어 붙히기 로직이다.

3. One Edit Distance : 확실히 처음보다는 더 잘풀긴 했다. DELETE operation 이 좀 어렵게 느껴졌는데 그래도 로직만 생각할 줄 알면 풀 수 있을 것 같다. 다시 도전해보자.

4. Reverse Worlds in a String II : 훨씬 더 쉽게 풀 수 있는 문제인데 좀 이상하게 푼거 같다. 중첩 While 문 안에서 미리 조건대로 포인터들을 옮기고 안에서 미리 reverse 를 해준다면 추가적인 코드 없이 깔끔하게 할 수 있다.

5. Shortest Way to Form String : 분명 여러번 풀어보았는데도 헷갈려서 생각을 여러번 했다. 그래도 고민을 여러번 해본만큼 이번에는 답에 가장 근접하게 다가갔다. 다음 섹션을 풀기 전에 꼭 리뷰!