LeetCode 530. Minimum Absolute Difference in BST

Mar 4, 2017

题目描述：

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.

一个只包含非负元素的二叉搜索树中找到两个元素之间的最小差的绝对值。因为是二叉搜索树所以用中序遍历就可以得到一个有序序列，最小的差值一定是出现在相邻的元素中，只比较相邻元素的差值即可。

/**
 * 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 {
    int ans = INT_MAX;
    int prevVal = -1;
public:
    int getMinimumDifference(TreeNode* root) {
        inOrder(root);
        return ans;
    }
    
    void inOrder (TreeNode *node) {
        if (!node) return ;
        inOrder(node->left);
        if(prevVal >= 0) ans = min (ans, node->val - prevVal);
        prevVal = node->val;
        inOrder(node->right);
    }
};

LeetCode 529. Minesweeper

Mar 3, 2017

题目描述：

Let’s play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.

If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.

If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.

Return the board when no more squares will be revealed.

Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:
Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:
Note:

The range of the input matrix’s height and width is [1,50].

The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.

The input board won’t be a stage when game is over (some mines have been revealed).

For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

扫雷游戏，根据题目要求做相应的处理就可以了。

class Solution {
    int totalRow, totalCol;
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        totalRow = board.size();
        totalCol = board[0].size();
        char cur = board[click[0]][click[1]];
        switch (cur) {
            case 'M':
                updateM(board, click[0], click[1]);
                break;
            case 'E':
                updateE(board, click[0], click[1]);
                break;
        }
        return board;
    }
    
    void updateM (vector<vector<char>>& board, int row, int col) {
        board[row][col] = 'X';
    }
    
    void updateE (vector<vector<char>>& board, int row, int col) {
        if (row < 0 || col < 0 || row >= totalRow || col >= totalCol || board[row][col] != 'E') return;
        int mine = adjacentMine(board, row, col);
        if (mine) {
            board[row][col] = mine + '0';
        }
        else {
            board[row][col] = 'B';
            updateE(board, row - 1, col - 1);
            updateE(board, row - 1, col);
            updateE(board, row - 1, col + 1);
            updateE(board, row, col + 1);
            updateE(board, row + 1, col + 1);
            updateE(board, row + 1, col);
            updateE(board, row + 1, col - 1);
            updateE(board, row, col - 1);
        }
    }
    
    int adjacentMine (vector<vector<char>>& board, int row, int col) {
        int cnt = 0;
        if (row - 1 >= 0 && col - 1 >= 0 && board[row - 1][col - 1] == 'M')                cnt++;
        if (row - 1 >= 0 && board[row - 1][col] == 'M')                                    cnt++;
        if (row - 1 >= 0 && col + 1 < totalCol && board[row - 1][col + 1] == 'M')          cnt++;
        if (col + 1 < totalCol && board[row][col + 1] == 'M')                              cnt++;
        if (row + 1 < totalRow && col + 1 < totalCol && board[row + 1][col + 1] == 'M')    cnt++;
        if (row + 1 < totalRow && board[row + 1][col] == 'M')                              cnt++;
        if (row + 1 < totalRow && col - 1 >= 0 && board[row + 1][col - 1] == 'M')          cnt++;
        if (col - 1 >= 0 && board[row][col - 1] == 'M')                                    cnt++;
        
        return cnt;
    }
};

LeetCode 526. Beautiful Arrangement

Mar 3, 2017

题目描述：

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

The number at the ith position is divisible by i.

i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:

N is a positive integer and will not exceed 15.

因为数据规模比较小，可以先确定对于每一个位置可以选择数值有哪些，然后再用回溯法穷举。

class Solution {
    vector<vector<int>> possibleValue;
    int ans = 0;
public:
    int countArrangement(int N) {
        setPossibleValue(N);
        vector<int> visited(N, 0);
        tryValue(0, visited);
        return ans;
    }
    
    void tryValue (int index, vector<int> &visited) {
        if (index == visited.size()) {
            ans++;
            return;
        }
        for (int i = 0; i < possibleValue[index].size(); i++) {
            if (!visited[possibleValue[index][i]]) {
                visited[possibleValue[index][i]] = 1;
                tryValue(index + 1, visited);
                visited[possibleValue[index][i]] = 0;
            }
        }
    }
    
    void setPossibleValue (int N) {
        for (int i = 1; i <= N; i++) {
            vector<int> val;
            for (int j = 1; j <= N; j++) {
                if (i % j == 0 || j % i == 0) {
                    val.push_back(j - 1);
                }
            }

            possibleValue.push_back(val);
        }
    }
};

LeetCode 525. Contiguous Array

Mar 3, 2017

题目描述：

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
1
2
3
4
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
1
2
3
4
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

这道题一看上去我想到了贪心orDP的方向，但是可以用哈希表来解决。思考的关键在于连续子数组中含有相同数目的0和1会具有什么样的特征，另外一点要考虑的是数据规模。数据规模达到50000，说明解法是小于O(n^2)的，而通过对数组一次遍历可以得到的结果有从数组开始到某一个下标为止所包含的0和1的个数。

如果一个连续子数组[i:j]中的0和1数目相等，那么子数组[0:i]和[0:j]中的0的个数与1的个数之差是相等的。因此对于每一个差值记录最小的下标，当再次出现这个差值时，两个下标之间的子数组就含有相同的0和1.

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> diff;
        int cnt[2] = {0, 0};
        int ans = 0;
        diff[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums[i]]++;
            int t = cnt[0] - cnt[1];
            if (diff.count(t)) {
                ans = max(ans, i - diff[t]);
            }
            else {
                diff[t] = i;
            }
        }
        return ans;
    }
};

LeetCode 524. Longest Word in Dictionary through Deleting

Mar 1, 2017

题目描述：

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:
1
2
3
4
5
6
Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"
Example 2:
1
2
3
4
5
6
Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"
Note:

All the strings in the input will only contain lower-case letters.

The size of the dictionary won’t exceed 1,000.

The length of all the strings in the input won’t exceed 1,000.

用双指针来判断一个单词可不可以从另一个单词通过删除字母的来。依次判断，选出最长的。如果有多个最长的，就保留字典序较小的。当遍历到一个单词时，可以进行一定的剪枝。

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        string ans;
        for (auto word : d) {
            int wordLen = word.length(), ansLen = ans.length();
            if (wordLen <= s.length() && wordLen >= ansLen && match(s, word)) {
                if (wordLen > ansLen) ans = word;
                else if (wordLen == ansLen) {
                    ans = min(ans, word);
                }
            }
        }
        return ans;
    }
    
    bool match(string s, string w) {
        int si = 0, wi = 0;
        while (si < s.length() && wi < w.length()) {
            if (s[si] == w[wi]) {
                wi++;
                si++;
            }
            else {
                si++;
            }
        }
        return wi == w.length();
    }
};

LeetCode 520. Detect Capital

Mar 1, 2017

题目描述：

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.

All letters in this word are not capitals, like “leetcode”.

Only the first letter in this word is capital if it has more than one letter, like “Google”.

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:
1
2
3
Input: "USA"
Output: True
Example 2:
1
2
3
Input: "FlaG"
Output: False
Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

遍历一遍字符串，记录大写字母的出现次数与首字母是否大写，然后根据题目要求返回结果就可以了。

class Solution {
public:
    bool detectCapitalUse(string word) {
        if (word.empty()) return true;
        int capitalNum = 0;
        int firstCapital = isupper(word[0]);
        
        for (auto c : word) {
            if (isupper(c)) capitalNum++;
        }
        
        return (capitalNum == 0 || capitalNum == word.length() || (firstCapital && capitalNum == 1));
    }
};

LeetCode 515. Find Largest Value in Each Tree Row

Feb 21, 2017

题目描述：

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

我使用BFS来遍历二叉树，这样可以保证一行的节点是连续出现的。对于每一行维护一个当前搜索到的最大值，当遇到下一行时说明这一行已经搜索完了，保存结果。

/**
 * 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 {
    vector<int> ans;
public:
    vector<int> largestValues(TreeNode* root) {
        if (root == nullptr) return ans;
        BFS(root);
        return ans;
    }
    
    void BFS(TreeNode *root) {
        queue<TreeNode*> nodeQueue;
        queue<int>       depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);
        
        int maxDepth = 0;
        int maxInDepth = root->val;
        while (!nodeQueue.empty()) {
            TreeNode *node = nodeQueue.front();
            nodeQueue.pop();
            int depth = depthQueue.front();
            depthQueue.pop();
            if (maxDepth < depth) {
                maxDepth = depth;
                ans.push_back(maxInDepth);
                maxInDepth = node->val;
            }
            else {
                maxInDepth = max(maxInDepth, node->val);
            }
            
            if (node->left) {
                nodeQueue.push(node->left);
                depthQueue.push(depth + 1);
            }
            if (node->right) {
                nodeQueue.push(node->right);
                depthQueue.push(depth + 1);
            }
        }
        ans.push_back(maxInDepth); // Last row
    }
};

LeetCode 513. Find Bottom Left Tree Value

Feb 21, 2017

题目描述：

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:
1
2
3
4
5
6
7
8
9
Input:

    2
   / \
  1   3

Output:
1
**Example 2: **
1
2
3
4
5
6
7
8
9
10
11
12
13
Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.

用DFS/BFS遍历一遍二叉树，要保证左子树比右子树先遍历到，这样没出现一个更深的节点就一定是该深度的最左边的节点。

/**
 * 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) {
        return BFS(root);
    }
    
    int BFS(TreeNode *root) {
        queue<TreeNode*> nodeQueue;
        queue<int>       depthQueue; // Store the corresponding depth
        nodeQueue.push(root);
        depthQueue.push(0);
        
        int maxDepth = -1;
        int leftBottomVal;
        while (!nodeQueue.empty()) {
            TreeNode *node = nodeQueue.front();
            nodeQueue.pop();
            int depth = depthQueue.front();
            depthQueue.pop();
            if (maxDepth < depth) {
                maxDepth = depth;
                leftBottomVal = node->val;
            }
            if (node->left) {
                nodeQueue.push(node->left);
                depthQueue.push(depth + 1);
            }
            if (node->right) {
                nodeQueue.push(node->right);
                depthQueue.push(depth + 1);
            }
        }
        return leftBottomVal;
    }
};

LeetCode 508. Most Frequent Subtree Sum

Feb 21, 2017

题目描述：

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1 Input:
1
2
3
4
  5
 /  \
2   -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2 Input:
1
2
3
4
  5
 /  \
2   -5
return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

用递归来计算每个节点的subtree sum，然后用哈希表保存每个sum的出现次数。

/**
 * 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 {
    unordered_map<int, int> sumFreq;
    int maxSumFreq = INT_MIN;
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        DFS_sum(root);
        vector<int> ans;
        for (auto i : sumFreq) {
            if (i.second == maxSumFreq) 
                ans.push_back(i.first);
        }
        return ans;
    }
    
    int DFS_sum(TreeNode *node) {
        if (node == nullptr) {
            return 0;
        }
        int sum = DFS_sum(node->left) + DFS_sum(node->right) + node->val;
        maxSumFreq = max(maxSumFreq, ++sumFreq[sum]);
        return sum;
    }
};

LeetCode 498. Diagonal Traverse

Feb 19, 2017

题目描述：

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:
1
2
3
4
5
6
7
8
9
10
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:
Note:

The total number of elements of the given matrix will not exceed 10,000.

这道题就是按照题目要求的顺序遍历这个矩阵就可以了。首先有两个方向，对于每个方向在到达矩阵边缘的时候又有两种处理方式，分情况来处理就可以了。值得注意的是矩阵的右上角与左下角。他们的处理方式分别与矩阵的右边缘和下边缘相同，要注意安排判断横纵坐标的顺序以免越界。

class Solution {
    enum DIRECTION {
        DownLeft = 0,
        UpRight = 1
    };
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        int row = matrix.size();
        if (row == 0) return vector<int>();
        int col = matrix[0].size();
        if (col == 0) return vector<int>();
        
        vector<int> ans;
        
        DIRECTION direction = UpRight;
        
        int x = 0, y = 0;
        while (x != row - 1 || y != col - 1) {
            ans.push_back(matrix[x][y]);
            if (direction == UpRight) {
                if (y == col - 1) {
                    x++;
                    direction = DownLeft;
                }
                else if (x == 0) {
                    y++;
                    direction = DownLeft;
                }
                else {
                    x--;
                    y++;
                }
            }
            else {
                if (x == row - 1) {
                    y++;
                    direction = UpRight;
                }
                else if (y == 0) {
                    x++;
                    direction = UpRight;
                }
                else {
                    x++;
                    y--;
                }
            }
        }
        ans.push_back(matrix[row - 1][col - 1]);
        
        return ans;
    }
};