LeetCode 75 - Prefix Sum + Hash Map

1~3 개월의 준비 기간을 가지고 풀기에 좋은 문제들을 가지고 있는 특징이 있다.
이번 내용은 Prefix Sum + Hash Map주제다.

---

Find the Highest Altitude
link : https://leetcode.com/problems/find-the-highest-altitude/description/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        vector<int> prefix(gain.size() + 1, 0); 
        for(int i = 1; i <= gain.size(); i++){
            prefix[i] = prefix[i-1] + gain[i-1]; 
        }

        

        return *max_element(prefix.begin(), prefix.end()); 
    }
};

---

Find Pivot Index
link: https://leetcode.com/problems/find-pivot-index/description/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> prefix(nums.size()+1, 0); 
        vector<int> suffix(nums.size()+1, 0); 

        for(int i = 1; i <= nums.size(); i++){
            prefix[i] = prefix[i-1] + nums[i-1]; 
        }

        for(int i = nums.size()-1; i >= 0; i--){
            suffix[i] = suffix[i+1] + nums[i];
        }  

        for(int i = 0; i < prefix.size()-1; i++){
            if(prefix[i] == suffix[i+1]) return i; 
        }

        return -1; 
    }
};

---

Find the Difference of Two Arrays
link : https://leetcode.com/problems/find-the-difference-of-two-arrays/description/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    vector<int> getElementsOnlyInFirstList(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> onlyInNums1;
        unordered_set<int> existsInNums2;
        for (int num : nums2) {
            existsInNums2.insert(num);
        }
        
        for (int num : nums1) {
            if (existsInNums2.find(num) == existsInNums2.end()) {
                onlyInNums1.insert(num);
            }
        }

        return vector<int> (onlyInNums1.begin(), onlyInNums1.end());
    }
    
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        return {getElementsOnlyInFirstList(nums1, nums2), getElementsOnlyInFirstList(nums2, nums1)};
    }
};

---

Unique Number of Occurences
link : https://leetcode.com/problems/unique-number-of-occurrences/description/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        map<int,int> hashMap; 
        set<int> hashSet; 
        for(int n : arr) hashMap[n]++; 


        for(auto& it : hashMap) hashSet.insert(it.second); 

        return  hashSet.size() == hashMap.size(); 
    }
};

---

Determine if Two Strings Are Close
link : https://leetcode.com/problems/determine-if-two-strings-are-close/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        if(word1.length() != word2.length()) return false; 

        vector<int> word1Map(26,0); 
        vector<int> word2Map(26,0); 

        for(int i = 0; i < word1.size(); i++){
            word1Map[word1[i] - 'a']++; 
            word2Map[word2[i] - 'a']++; 
        }

        for(int i = 0; i < word1Map.size(); i++){
            //if(word1Map[i] != word2Map[i]) return false; 
            if((word1Map[i] == 0 && word2Map[i] > 0) || (word2Map[i] == 0 && word1Map[i] > 0)){
                return false; 
            }
        } 

        sort(word1Map.begin(),word1Map.end()); 
        sort(word2Map.begin(),word2Map.end()); 


        return word1Map == word2Map; 
    }
};

---

Equal Row and Column Pairs
link: https://leetcode.com/problems/equal-row-and-column-pairs/description/?envType=study-plan-v2&envId=leetcode-75

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int answer = 0; 
        map<int, vector<int>> hashMap, hashMap2; 

        for(int i = 0; i < grid.size(); i++){
            vector<int> container; 
            vector<int> container2; 
            for(int j = 0; j < grid[i].size(); j++){
                container.push_back(grid[i][j]);
                container2.push_back(grid[j][i]); 
            }
            hashMap[i] = container; 
            hashMap2[i] = container2; 
        } 

        for(auto& it : hashMap){
            
            for(auto& it2 : hashMap2){
                if(it.second == it2.second){
                    answer++; 
                }
            }
        }


        return answer; 
    }
};

class Solution {
    public int equalPairs(int[][] grid) {
        int count = 0; 
        int n = grid.length; 

        Map<String, Integer> rowCounter = new HashMap<>(); 
        for(int[] row : grid){
            String rowString = Arrays.toString(row); 
            rowCounter.put(rowString, 1 + rowCounter.getOrDefault(rowString, 0)); 
        }

        for(int c = 0; c < n; c++){
            int[] colArray = new int[n]; 
            for(int r = 0; r < n; ++r){
                colArray[r] = grid[r][c]; 
            }

            count += rowCounter.getOrDefault(Arrays.toString(colArray), 0); 
        }

        return count;
    }
}

---

복습할 문제

1.Determine if Two Strings Are Close : 분명히 개념은 이제 잡혔지만 문제를 생각보다 유연하게 잘 못풀었던거 같다. 시간이 지나고 다시 한번 풀어봐야지.