Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

Brutal Force O(n^3)

Prefix Sum: O(n^2)

Naive Hash Table: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int ret = 0;
        int sum = 0;
        int size = nums.size();
        if (size == 0) return 0;
        unordered_map<int, vector<int>> mapping; ///Mapping the sum to [0,..index]
        vector<int> dp(size + 1, -1);
        for (int i = 0; i < size; ++i) {
            dp[i] = sum;
            sum += nums[i];
            mapping[dp[i]].push_back(i);
        }
        dp[size] = sum;
        sum += nums[size];
        mapping[dp[size]].push_back(size); 
        
        for (int j = 0; j < size + 1; ++j) {
            if (mapping.count(dp[j] - k)) {
                for (auto& item : mapping[dp[j] - k])
                    ret = max(ret, j - item);
            }
        }
        
        return ret;
    }
};

Hash Table: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int ret = 0;
        int sum = 0;
        int size = nums.size();
        if (size == 0) return 0;
        unordered_map<int, int> mapping; ///Mapping the sum to [0,..index]
        vector<int> dp(size + 1, -1);
        dp[0] = 0;
        mapping[0] = 0;
        for (int i = 1; i <= size; ++i) {
            sum += nums[i - 1];
            dp[i] = sum;
            if (mapping.count(dp[i]) == 0) mapping[dp[i]] = i;
        }
        
        for (int j = 0; j < size + 1; ++j) {
            if (mapping.count(dp[j] - k)) {
                ret = max(ret, j - mapping[dp[j] - k]);
            }
        }
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/kill-process/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
        unordered_map<int, vector<int>> ppidMap;

        for (int index = 0; index < pid.size(); ++index) {
            ppidMap[ppid[index]].push_back(pid[index]);
        }
        
        queue<int> que;
        que.push(kill);
        vector<int> ret;
        ret.push_back(kill);
        while (!que.empty()) {
            int t = que.front();
            que.pop();
            if (ppidMap.count(t) == 0) continue;
            vector<int>& vec = ppidMap[t];
            for (auto& item : vec) {
                que.push(item);
                ret.push_back(item);
            }
        }
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/max-increase-to-keep-city-skyline/description/

Solution

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 maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        vector<int> rowArray(grid.size(), -1);
        vector<int> columnArray(grid[0].size(), -1);
        
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                rowArray[i] = max(rowArray[i], grid[i][j]);
                columnArray[j] = max(columnArray[j], grid[i][j]);
            }
        }
        
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                ret += (min(rowArray[i], columnArray[j]) - grid[i][j]);
            }
        }
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/next-closest-time/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    string nextClosestTime(string time) {
        string ret = time;
        set<int> digits;
        digits.insert(time[0] - '0');
        digits.insert(time[1] - '0');
        digits.insert(time[3] - '0');
        digits.insert(time[4] - '0');
        
        int index = 4;
        //Process Minute
        auto next = digits.lower_bound(time[index] - '0');
        if (*next == time[index] - '0') ++next;
        cout << *next << endl;
        if (next != digits.end()) {
            ret[index] = *next + '0';
            return ret;
        }
        
        ret[index] = *(digits.begin()) + '0';
        
        --index;
        next = digits.lower_bound(time[index] - '0');
        if (*next == time[index] - '0') ++next;
        if (next != digits.end() && *next <= 5) {
            ret[index] = *next + '0';
            return ret;
        }
        ret[index] = *(digits.begin()) + '0';
        
        index -= 2;
        
        
        //Process Hour
        next = digits.lower_bound(time[index] - '0');
        if (*next == time[index] - '0') ++next;
        int bound = (time[0] - '0') == 2 ? 3 : 9;
        if (next != digits.end() && *next <= bound) {
            ret[index] = *next + '0';
            return ret;
        }
        ret[index] = *(digits.begin()) + '0';
        --index;
        
        next = digits.lower_bound(time[index] - '0');
        if (*next == time[index] - '0') ++next;
        if (next != digits.end() && *next <= 2) {
            ret[index] = *next + '0';
            return ret;
        }
        
        ret[index] = *(digits.begin()) + '0';
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/find-leaves-of-binary-tree/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> ret;
        helper(root, ret);
        return ret;
    }
    
    int helper(TreeNode* root, vector<vector<int>>& ret) {
        if (root == NULL) return -1;
        int height = max(helper(root->left, ret), 
                            helper(root->right, ret)) + 1;
        
        if (ret.size() <= height) ret.resize(height + 1);
        ret[height].push_back(root->val);
        return height;
    }
};

Posted on

Description

https://leetcode.com/problems/pour-water/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int V, int K) {
        vector<int> ret = heights;
        if (K < 0 || K >= heights.size() ) return heights;
        for (int i = 0; i < V; ++i) {
            //Check left
            int index = K - 1;
            int minIndex = -1;
            while(index >= 0 && ret[index] <= ret[index + 1]) {
                if (ret[index] < ret[index + 1]) minIndex = index;
                --index;
            }
            if (minIndex != - 1) {
                ++ret[minIndex];
                continue;
            }
            
            //Check right
            index = K + 1;
            minIndex = -1;
            while(index < ret.size() && ret[index] <= ret[index - 1]) {
                if (ret[index] < ret[index - 1]) minIndex = index;
                ++index;
            }
            if (minIndex != -1) {
                ++ret[minIndex];
                continue;
            }
            //Stay here
            ++ret[K];
        }
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/flatten-2d-vector/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Vector2D {
private:
    vector<vector<int>> vec;
    vector<vector<int>>::iterator rowIter;
    vector<int>::iterator columnIter;
public:
    Vector2D(vector<vector<int>>& vec2d) {
        vec = vec2d;
        rowIter = vec.begin();
        while (rowIter != vec.end() && rowIter->size() == 0) ++rowIter;
        if (rowIter != vec.end()) columnIter = rowIter->begin();
    }

    int next() {
        int ret = *columnIter;
        ++columnIter;
        if (columnIter == rowIter->end()) {
            ++rowIter;
            while (rowIter != vec.end() && rowIter->size() == 0) ++rowIter;
            if (rowIter != vec.end()) columnIter = rowIter->begin();
        }
        return ret;
    }

    bool hasNext() {
        if (rowIter == vec.end()) return false;
        return true;
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i(vec2d);
 * while (i.hasNext()) cout << i.next();
 */

Posted on

Description

https://leetcode.com/problems/island-perimeter/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int height = grid.size();
        if (height == 0) return 0;
        
        int width = grid[0].size();
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 0) continue;
                for (int k = 0; k < 4; ++k) {
                    int newX = dir[k][0] + i;
                    int newY = dir[k][1] + j;
                    if (newX < 0 || newX >= height 
                        || newY < 0 || newY >= width 
                            || grid[newX][newY] == 0) {
                        ret += 1;
                    }
                }
            }
        }
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/two-sum-iii-data-structure-design/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TwoSum {
public:
    unordered_map<int, int> counter;
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        counter[number] += 1;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for (auto& item : counter) {
            int left = item.first;
            int right = value - left;
            if (left == right && item.second >= 2) return true;
            if (left != right && counter.count(right) != 0) return true;
            
        }
        
        return false;
    }
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * bool param_2 = obj.find(value);
 */

Posted on

Description

https://leetcode.com/problems/shortest-word-distance-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class WordDistance {
private:
    unordered_map<string, vector<int>> dic;
public:
    WordDistance(vector<string> words) {
        for (int i = 0; i < words.size(); ++i) {
            dic[words[i]].push_back(i); 
        }
    }
    
    int shortest(string word1, string word2) {
        int ret = INT_MAX;
        for (auto item1 : dic[word1]) {
            for (auto item2 : dic[word2]) {
                ret = min(abs(item1 - item2), ret);
            }
        }
        return ret;
    }
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */