Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/plus-one-linked-list/

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if (head == NULL) return head;
        
        ListNode* cur = new ListNode(0);
        ListNode* ret = cur;
        cur->next = head;
        
        while(cur->next) {
            stack<ListNode*> st;
            st.push(cur); //The digit before the leading 9
            while(cur->next && cur->next->val == 9) {
                cur = cur->next;
                st.push(cur);
            }
            if(cur->next == NULL) {
                //The last digit is 9
                while(st.size() > 1) {
                    ListNode* item = st.top();
                    st.pop();
                    item->val = 0;
                }
                st.top()->val += 1;
                return ret->val ? ret : ret->next;
            }
            //Find the next 9
            while(cur->next && cur->next->val != 9) cur = cur->next;
        }
        //The last digit is not 9
        cur->val += 1;
        return ret->next;
    }
};

Posted on

Description

Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.

If the list is empty (i.e., given node is null), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* inserted = new Node(insertVal, NULL);
        if (head == NULL) return inserted;
        
        Node* cur = head;
            
        if(insertVal < cur->val) {
            while(cur->next != head && 
              cur->next->val >= cur->val && cur->val > insertVal) cur = cur->next;
            while(cur->next->val < insertVal) cur = cur->next;
        }else if(insertVal > cur->val){
            while(cur->next != head && cur->val <= cur->next->val 
              && cur->next->val < insertVal) cur = cur->next;
        }
        
        inserted->next = cur->next;
        cur->next = inserted;
        return head;
    }
};

Posted on

Description

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

1
2
3
4
Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int p1 = -1;
        int p2 = -1;
        int ret = INT_MAX;
        for (int i = 0; i < words.size(); ++i) {
            if(words[i] != word1 && words[i] != word2) continue;
            if(words[i] == word1) p1 = i;
            if(words[i] == word2) p2 = i;
            if (p1 != -1 && p2 != -1) ret = min(ret, abs(p1 - p2));
        }
        return ret;
    }
};

Posted on

Description

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example:

1
2
3
4
5
Input: nums = [-2,0,1,3], and target = 2
Output: 2 
Explanation: Because there are two triplets which sums are less than 2:
             [-2,0,1]
             [-2,0,3]

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
class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if (nums.size() < 3) return 0;
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = 0; i < nums.size() - 2; ++i) {
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum >= target) {
                    --right;
                }else {
                    count += (right - left);
                    ++left;
                    
                }
                
            }
            
        }
        return count;
    }
};

Posted on

Description

Numbers can be regarded as product of its factors. For example,

1
2
8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Example 1:

1
2
Input: 1
Output: []

Example 2:

1
2
Input: 37
Output:[]

Example 3:

1
2
3
4
5
6
7
Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

1
2
3
4
5
6
7
8
9
10
Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

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
class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ret;
        set<int> st;
        if (n == 1) return ret;
        for (int i = 2; i <= n / 2; ++i) {
            if (st.find(i) != st.end()) continue;
            if (n % i == 0) {
                st.insert(i); st.insert(n/i);
            }
        }
        vector<int> current;
        helper(ret, st.begin(), st, n, current);
        
        return ret;
    }
    
    void helper(vector<vector<int>>& ret, 
                set<int>::iterator iter, 
                set<int>& st, int product, 
                vector<int>& current) {
        if (product == 1) {
            ret.push_back(current);
            return;
        }
        while(iter != st.end()) {
            int count = 0;
            int power = *iter;
            while(true) {
                if(product % power != 0) break;
                count += 1;
                current.push_back(*iter);
                auto nextIter = next(iter, 1);
                cout << *iter << *nextIter;
                helper(ret, nextIter, st, product/power, current); 
                power *= *iter;
            }
            while(count > 0) {
                current.pop_back();
                --count;
            }
            ++iter;
        }
        return;
    }
};

Beat 100% 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
class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ret;
        set<int> st;
        if (n == 1) return ret;
        for (int i = 2; i <= sqrt(n); ++i) {
            if (st.find(i) != st.end()) continue;
            if (n % i == 0) {
                st.insert(i); st.insert(n/i);
            }
        }
        vector<int> current;
        helper(ret, st.begin(), st, n, current);
        
        return ret;
    }
    
    void helper(vector<vector<int>>& ret, 
                set<int>::iterator iter, 
                set<int>& st, int product, 
                vector<int>& current) {
        if (product == 1) {
            ret.push_back(current);
            return;
        }
        while(iter != st.end()) {
            int count = 0;
            int power = *iter;
            while(true) {
                if(product % power != 0) break;
                count += 1;
                current.push_back(*iter);
                auto nextIter = next(iter, 1);
                helper(ret, nextIter, st, product/power, current); 
                power *= *iter;
            }
            while(count > 0) {
                current.pop_back();
                --count;
            }
            ++iter;
        }
        return;
    }
};

3 4 5

Posted on

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
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<int>> graph(N + 1, vector<int>(N + 1, 100000));
        for (auto& time : times)
            graph[time[0]][time[1]] = time[2];
        
        vector<bool> visited(N+1, false);
        visited[K] = true;
        int ret = -100000;
        int count = 0;
        while(count < N - 1) {
            int minLens = 100000;
            int minIndex = -1;
            for (int i = 1; i <= N; ++i) {
                if (visited[i]) continue;
                if (graph[K][i] < minLens) {
                    minLens = graph[K][i];
                    minIndex = i;
                }
            }
            if (minLens == 100000) return -1;
            visited[minIndex] = true;
            ret = max(ret, minLens);
            //update
            for (int i = 1; i < graph[K].size(); ++i) {
                if (visited[i]) continue;
                int minium = min(graph[K][i], minLens + graph[minIndex][i]);
                graph[K][i] = minium;
            }
            ++count;
        }
        
        return ret;
    }
};

Posted on

Description

https://leetcode.com/problems/01-matrix/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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rowSize = matrix.size();
        if (rowSize == 0) return matrix;
        int columnSize = matrix[0].size();
        
        vector<vector<int>> ret(rowSize, vector<int>(columnSize));
        
        for (int i = 0; i < rowSize; ++i) {
            for (int j = 0; j < columnSize; ++j) {
                ret[i][j] = findShortestPath(matrix, i, j, rowSize, columnSize);
            }
        }
        return ret;
    }
    
    int findShortestPath(vector<vector<int>>& matrix, int i, int j, int rowSize, int columnSize) {
        if (matrix[i][j] == 0) return 0; 
        queue<pair<int, pair<int, int>>> q;
        vector<pair<int, int>> directions = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        q.push(make_pair(1, make_pair(i, j)));
        while (!q.empty()) {
            int depth = q.front().first;
            int curRow = q.front().second.first;
            int curCol = q.front().second.second;
            q.pop();
            for (auto& item : directions) {
                int newRow = curRow + item.first;
                int newColumn = curCol + item.second;
                if (newRow < 0 || newRow >= rowSize || 
                     newColumn < 0 || newColumn >= columnSize) continue;
                if (matrix[newRow][newColumn] == 0) return depth;
                else {
                    q.push(make_pair(depth + 1, make_pair(newRow, newColumn)));
                }
            }
        }
        return -1;// Invaid 
    }
};

Posted on

Description

https://leetcode.com/problems/minesweeper/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
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
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int rowSize = board.size();
        int columnSize = board[0].size();
        int row = click[0]; 
        int column = click[1];
        vector<vector<bool>> visited(rowSize, vector<bool>(columnSize, false));
        if (board[row][column] == 'M') {
            board[row][column] = 'X';
            return board;
        }
        vector<pair<int, int>> directions = {
            {-1,-1}, {1, 1}, 
            {1, 0}, {-1, 0}, 
            {0, -1}, {0, 1},
            {-1, 1}, {1, -1}
        };
        
        helper(board, row, column, directions, 
                        rowSize, columnSize, visited);
        return board;
    }
    
    void helper(vector<vector<char>>& board, int curRow, 
            int curColumn, vector<pair<int, int>>& directions,
                int rowSize, int columnSize, vector<vector<bool>>& visited) {
        if (visited[curRow][curColumn]) return;
        visited[curRow][curColumn] = true;
        if (board[curRow][curColumn] == 'M') {
            board[curRow][curColumn] == 'X';
            return;
        }
        int count = 0;
        vector<pair<int, int>> adjacents;
        for (auto& item : directions) {
            int newRow = item.first + curRow;
            int newColumn = item.second + curColumn;
            if (newRow < 0 || newRow >= rowSize || 
                newColumn < 0 || newColumn > columnSize) continue;
            if(board[newRow][newColumn] == 'M' || board[newRow][newColumn] == 'X') {
                count += 1;
            }
            if(board[newRow][newColumn] == 'E' && !visited[newRow][newColumn]) {
                adjacents.push_back(make_pair(newRow, newColumn));
            }
        }
        if (count == 0) {
            for (auto& item : adjacents) {
                helper(board, item.first, item.second, 
                       directions, rowSize, columnSize, visited);   
            }
        }
        board[curRow][curColumn] = count ? count + '0' : 'B';
    }
};

Posted on

Description

https://leetcode.com/problems/find-bottom-left-tree-value/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
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:
    int findBottomLeftValue(TreeNode* root) {
        map<int, int> depthMapping;
        int depth = 0;
        helper(root, depthMapping, depth);
        return depthMapping.rbegin()->second;
    }
    
    void helper(TreeNode* root, map<int, int>& depthMapping, int depth) {
        if (root == NULL) return;
        helper(root->left, depthMapping, depth + 1);
        auto iter = depthMapping.find(depth);
        if(iter == depthMapping.end()) depthMapping[depth] = root->val;
        helper(root->right, depthMapping, depth + 1);
        return;
    }
};

Posted on

Description

https://leetcode.com/problems/same-tree/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if ((p && !q)||(!p && q)) return false;
        if (!p && !q) return true;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};