题目描述：

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

将数组排序之后从第一个元素开始相邻的元素为一组，将每一组中较小的值加起来就可以了。

题目描述：

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

  Input: [1000,100,10,2]
  Output: "1000/(100/10/2)"
  Explanation:
  1000/(100/10/2) = 1000/((100/10)/2) = 200
  However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
  since they don't influence the operation priority. So you should return "1000/(100/10/2)". 
  
  Other cases:
  1000/(100/10)/2 = 50
  1000/(100/(10/2)) = 50
  1000/100/10/2 = 0.5
  1000/100/(10/2) = 2

Note:

1. The length of the input array is [1, 10].
2. Elements in the given array will be in range [2, 1000].
3. There is only one optimal division for each test case.

这道题对一个连续除法加上括号，使得到的最终结果最大。像这样的算式：1000/(100/10)/2，如果去掉括号并且保证值不变的话就是：1000/100*10/2，所有的括号都可以打开最终变成一个没有括号的乘除混合的算式。

因此可以用穷举法穷举每一个运算符位置的可能性（*或/），从中选择结果最大的，然后用括号把乘法括起来，就可以得到结果。左括号的位置应该在前一个符号为/后一个符号为*的数字前，右括号的位置应该在前一个符号为*后一个符号为/的数字后（最后一个数字应该认为后面一个符号为/）。

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

class Solution {
    vector<int> ops;
    const int MULTIPLY = 0;
    const int DIVIDE = 1;
    double maxResult = 0;
public:
    string optimalDivision(vector<int>& nums) {
        if (nums.size() == 1) return to_string(nums[0]);
        vector<int> tmpOps(nums.size() - 1);
        int maxResult = INT_MIN;
        tmpOps[0] = DIVIDE;
        double tmpResult = (double)nums[0] / nums[1];
        findMaxResult(nums, 1, tmpOps, tmpResult);
        string ans = "";
        for (int i = 1; i < nums.size() - 1; i++) {
            if (ops[i - 1] == DIVIDE && ops[i] == MULTIPLY) {
                ans += ("(" + to_string(nums[i]));
            }
            else if (ops[i - 1] == MULTIPLY && ops[i] == DIVIDE) {
                ans += (to_string(nums[i]) + ")");
            }
            else {
                ans += to_string(nums[i]);
            }
            ans += "/";
        }
        ans = to_string(nums[0]) + "/" + ans;
        if (ops.back() == MULTIPLY) {
            ans += (to_string(nums.back()) + ")");
        }
        else {
            ans += to_string(nums.back());
        }
        
        return ans;
    }
    
    void findMaxResult (vector<int>& nums, int begin, vector<int> &tmpOps, const double &result) {
        if (begin == nums.size() - 1) {
            if (result > maxResult) {
                maxResult = result;
                ops = tmpOps;
                return;
            }
            else {
                return;
            }
        }
        tmpOps[begin] = DIVIDE;
        findMaxResult(nums, begin + 1, tmpOps, result / nums[begin + 1]);
        
        tmpOps[begin] = MULTIPLY;
        findMaxResult(nums, begin + 1, tmpOps, result * nums[begin + 1]);
    }
};

题目描述：

You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. ‘A’ : Absent.
2. ‘L’ : Late.
3. ‘P’ : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

题目很简单，就是扫一遍字符串就可以了，但是要注意一些边界情况。

GitHub Pages默认是启用SSL的，但是绑定了自己的域名之后证书就不匹配了。通过Cloudfare官方的免费服务^[1]就可以给博客启用SSL了（当然也就默认使用了他家的CDN）。终于可以跟国内无良ISP的劫持说再见了。

前段时间多说宣布准备关闭服务，之后偶然看到一个用GitHub Issues来做评论系统的项目：https://github.com/imsun/gitment，倒不是说对这个想法很感兴趣，而且因为它又激起了我转移到静态博客+GitHub Pages的念头。今天算是付诸行动了吧。

题目描述：

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

1 2 3

Input: "Let's take LeetCode contest" Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

这么简单的题真的会出现？

由于没有多余的空格，所以用双指针找到下一个空格，翻转当前位置与下一个空格之间的字符，设置左指针为下一个空格的位置+1.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    string reverseWords(string s) {
        int p1 = 0;
        while (p1 < s.length()) {
            int p2 = p1;
            while (p2 < s.length() && s[p2] != ' ') p2++;
            reverse(s.begin() + p1, s.begin() + p2);
            p1 = p2 + 1;
        }
        return s;
    }
};

题目描述：

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

1 2 3 4 5 6 7 8 9

Input: [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]] Output: 2 Explanation:

Note:

1. The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

虽然行数与每一行的砖块数都可能达到10000，但是总的砖块数最大只有20000，又因为总的砖块间缝隙的数量一定小于砖块总数，所以可以用Hash表来记录每一个出现缝隙的位置一共出现了几次缝隙，出现缝隙次数最多的位置就是穿过砖块数最少的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        if (wall.empty()) return 0;
        int row = wall.size();
        unordered_map<int, int> occurTimes;
        int width;
        for (int i = 0; i < row; i++) {
            int sum = 0;
            for (auto j : wall[i]) {
                sum += j;
                occurTimes[sum]++;
            }
            width = sum;
        }
        occurTimes[width] = 0;
        int maxOccur = 0;
        for (auto &i : occurTimes) {
            maxOccur = max(maxOccur, i.second);
        }
        return row - maxOccur;
    }
};

题目描述：

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

1 2 3 4 5 6 7 8

Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2 Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. The 2nd student himself is in a friend circle. So return 2.

Example 2:

1 2 3 4 5 6 7 8

Input: [[1,1,0], [1,1,1], [0,1,1]] Output: 1 Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

比较典型的并查集题目，也可以使用广度优先搜索来解决。

话说朋友圈就直接翻译成Friend Circle?

并查集：

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

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int num = M.size();
        vector<int> uf(num);
        for (int i = 0; i < num; i++) uf[i] = i;
        for (int i = 0; i < num; i++) {
            for (int j = i + 1; j < num; j++) {
                if (!M[i][j]) continue;
                if (uf[i] == i && uf[j] == j) {
                    uf[j] = i;
                }
                else if (uf[i] == i) {
                    int h = j;
                    while (uf[h] != h) h = uf[h];
                    uf[i] = h;
                }
                else if (uf[j] == j) {
                    int h = i;
                    while (uf[h] != h) h = uf[h];
                    uf[j] = h;
                }
                else {
                    int h1 = j, h2 = i;
                    while (uf[h1] != h1) h1 = uf[h1];
                    while (uf[h2] != h2) h2 = uf[h2];
                    uf[h2] = h1;
                }
            }
        }
        int circleNum = 0;
        for (int i = 0; i < num; i++) {
            if (uf[i] == i) circleNum++;
        }
        return circleNum;
    }
};

BFS：每发现一个未标记的人，则通过广度优先搜索找出他所在的朋友圈的所有人并全部标记为访问过，朋友圈数量+1s。

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

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        vector<int> visited(M.size(), 0);
        int friendCircleNum = 0;
        for (int i = 0; i < M.size(); i++) {
            if (!visited[i]) {
                setMatrix(M, visited, i);
                ++friendCircleNum;
            }
        }
        return friendCircleNum;
    }
    
    void setMatrix(vector<vector<int>>& M, vector<int>& visited, int x) {
        queue<int> q;
        q.push(x);
        visited[x] = 1;
        while(!q.empty()) {
            int p = q.front();
            q.pop();
            for (int i = 0; i < M.size(); i++) {
                if (M[p][i] && !visited[i]) {
                    visited[i] = 1;
                    q.push(i);
                }
            }
        }
    }
};

题目描述：

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

      1
     / \
    2   3
   / \     
  4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

这道题可以采用分治法，对于一颗树来说，任意两个节点之间的最长路径从大的方面来说存在两种情况：

• 路径经过根节点，则最长路径为左子数的最大深度与右子树的最大深度之和
• 路径不经过根节点，又有两种情况：
  • 最长路径为左子树的最长路径
  • 最长路径为右子树的最长路径

所以就可以通过递归求出根节点的这三个长度取最大值就是整棵树的最长路径。

计算子树的深度可以和计算子树的最长路径结合到一起。

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

/**
 * 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 diameterOfBinaryTree(TreeNode* root) {
        int maxDepth = 0;
        return diameterOfBinaryTreeImpl(root, maxDepth);
    }
    
    int diameterOfBinaryTreeImpl(TreeNode* node, int &maxDepth) {
        if (!node) return 0;
        int leftMaxDepth = 0, rightMaxDepth = 0;
        int leftAns = diameterOfBinaryTreeImpl(node->left, leftMaxDepth);
        int rightAns = diameterOfBinaryTreeImpl(node->right, rightMaxDepth);
        maxDepth = max(leftMaxDepth, rightMaxDepth) + 1;
        return max(leftMaxDepth + rightMaxDepth, max(leftAns, rightAns));
    }
};

题目描述：

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

1 2 3 4 5 6 7 8 9

Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13

转换一颗二叉搜索树，使其每一个节点都变为原来的值+所有比它大的节点的值的和。

这道题只要从大往小遍历BST就可以了，也就是DFS先右后左，记录已经遍历过的节点的值的和，每遍历到一个新节点就把节点值加上这个和。

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

/**
 * 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:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        DFS(root, sum);
        return root;
    }
    
    void DFS(TreeNode *node, int &sum) {
        if (!node) return;
        DFS(node->right, sum);
        int v = node->val;
        node->val += sum;
        sum += v;
        DFS(node->left, sum);
    }
};