LeetCode 135. Candy

Sep 28, 2016

题目描述:

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

分糖果的问题, 有两条规则:

每个孩子必须至少有一个糖果.
如果rating比相邻的孩子高, 那么也必须有更多的糖果. 也就是说相等的rating是没有要求的, 跟小于一样.

我所采用的思路是一种类似双指针的方法:

扫描一遍ratings, 找到所有小于等于相邻元素的元素的rating, 这些rating是可以直接设为1的.
在上一步的到的数组中每两个相邻的rating中间找到rating的最大值
比较这个最大值与相邻的两个最小rating的距离, 使用等差数列来算出所需要的总rating值.

对于最后一步为什么可以使用等差数列, 因为对于两个candy值为1的孩子中间的孩子, 按照索引顺序的话他们各自的candy值是先增后减的趋势, 为了保证总得candy最小每次增加或减少1是唯一方法, 是两个等差数列. 但是由于最大rating的孩子与两边candy为1的孩子的距离不同, 这两个数列也不同. 比如对于以下的ratings

[6,8,9,10,2,1]

对应的最小candy值应为:

[1,2,3,4,2,1]

左边数列是一个从左边的candy为1的孩子到rating最大的孩子共4个, 而右边则是到2就结束了. 把输入数据颠倒一下:

[1,2,10,9,8,6]

对应的结果应为:

[1,2,4,3,2,1]

数列的形式也颠倒了, 所以要根据rating最大的孩子到左右两边的距离来分别求和.

还有一些其他问题:

关于最左边与最右边的值, 因为他们只有一边有邻居, 所以不能像中间的节点一样计算. 我的方法是在前后各插入一个INT_MIN, 这样就可以把两端节点当作中间节点来处理了. 最后再从结果中减去.
rating的最大值有多个. 这种情况只有一种可能, 就是两个连续的最大rating值(从我的方法来说, 其他情况都是不可能的), 由于相等的两个值没有大小要求, 因此也应该分别计算.

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if(n < 2) return 1;
        
        vector<int> oneIndex;
        oneIndex.push_back(-1);
        if(ratings[0] <= ratings[1]) oneIndex.push_back(0);
        for(int i = 1; i < n - 1; i++){
            if(ratings[i] <= ratings[i - 1] && ratings[i] <= ratings[i + 1]) 
                oneIndex.push_back(i);
        }
        if(ratings[n - 1] <= ratings[n - 2]) oneIndex.push_back(n - 1);
        
        oneIndex.push_back(n);
        
        int ans = oneIndex.size() - 2, i = 0;
        while(i < oneIndex.size()){
            while(i < oneIndex.size() - 1 && oneIndex[i + 1] == oneIndex[i] + 1) i++; // 跳过连续的相等值
            if(i == oneIndex.size() - 1) break;
            int left = oneIndex[i], right = oneIndex[i + 1];
            int maxRating = INT_MIN, maxIndex;
            for(int j = left + 1; j < right; j++){ // 找出最大rating值
                if(ratings[j] >= maxRating){
                    maxRating = ratings[j];
                    maxIndex = j;
                }
            }
            if((ratings[maxIndex - 1] == ratings[maxIndex] && maxIndex - 1 != left)){
                // 有两个最大rating值
                ans += (2 + maxIndex - left) * (maxIndex - left - 1) / 2;
                ans += (right - maxIndex) * (3 + right - maxIndex) / 2;
            }
            else if(right - maxIndex < maxIndex - left){
                // 距左边较远
                ans += (3 + maxIndex - left) * (maxIndex - left) / 2;
                ans += (right - maxIndex - 1) * (2 + right - maxIndex) / 2;
            }
            else{ // 距右边较远
                ans += (2 + maxIndex - left) * (maxIndex - left - 1) / 2;
                ans += (right - maxIndex) * (3 + right - maxIndex) / 2;
            }
            i++;
        }
        return ans;
    }
};

LeetCode 406. Queue Reconstruction by Height

Sep 26, 2016

题目描述:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example
1
2
3
4
5
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

输入数据中的k表示这个人之前有几个大于等于自己的h的人. 比较容易想到对于h最小的人来说, 他的k值就是他在最终队列中的位置, 因为排在他前面的所有人都是大于等于他的h的. 如果去掉h最小的人, 此时h次小的人就成为了最小的, 他在队列中的位置就是从开头数起, 跳过已经确定位置的h更小的人的第k个位置. 这样不断重复就可以确定最终的序列.

但是从开头数起, 跳过已经确定位置的h更小的人的第k个位置是需要遍历数组的, 效率不高, 所以我用一个deque来保存还没有被占用的位置, 当一个位置确定之后就从其中删除, 这样对于之后的人来说, 用k作为索引从deque中取得的位置就是最终的位置. 但是这会造成一个问题, 就是h相同的人如果排在前面的已经确定了位置, 那么排在后面的人会由于已经删除一个位置而偏后一位, 解决方法是排序的时候就把h相同的人中k较大的排在前面.

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        sort(people.begin(), people.end(), [&](pair<int, int> &a, pair<int, int> &b){
            if(a.first == b.first){
                return a.second > b.second;
            }
            return a.first < b.first;
        });
        int sz = people.size();
        vector<pair<int, int>> ans(sz);
        deque<int> indexes(sz);
        for(int i = 0; i < sz; i++) indexes[i] = i;
        for(int i = 0; i < sz; i++){
            int index = people[i].second;
            ans[indexes[index]] = people[i];
            indexes.erase(indexes.begin() + index);
        }
        return ans;
    }
};

LeetCode 405. Convert a Number to Hexadecimal

Sep 26, 2016

题目描述:

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.

The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.

The given number is guaranteed to fit within the range of a 32-bit signed integer.

You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:
1
2
3
4
5
6
Input:
26

Output:
"1a"
Example 2:
1
2
3
4
5
Input:
-1

Output:
"ffffffff"

由于传入的数据是int型, 所以其实负数就已经是用补码来表示了. 因此只要每次取四位二进制位出来然后把它们转换为16进制即可.

class Solution {
public:
    string toHex(int num) {
        int n = num;
        string hex;
        for(int i = 0; i < 8; i++){
            hex.push_back(toCharHex(n & 0xf));
            n >>= 4;
        }
        while(hex.size() > 1 && hex.back() == '0') hex.pop_back();
        reverse(hex.begin(), hex.end());
        return hex;
    }
    
    char toCharHex(int num){
        if(num < 10){
            return num + '0';
        }
        else{
            return num - 10 + 'a';
        }
    }
};

LeetCode 404. Sum of Left Leaves

Sep 26, 2016

题目描述:

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

用DFS找出所有左叶子节点再求和即可.

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

LeetCode 134. Gas Station

Sep 25, 2016

题目描述:

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

环路上分布着n个加油站, 输入数据是每个加油站可以加多少油和到下一个加油站耗费多少油, 要求找出能不能走完这个环.

首先要证明一个情况: 如果从a点出发无法抵达c点(c之前的一点可以到达), 那么从a到c之间的任何一点b出发都是无法到达c点的. 这是因为从a出发到b的时候最坏的情况是正好没有油, 所以从b点继续的时候油是>=在b点加的油的, 而如果一开始就从b出发, 油就等于在b加的油, 是不可能比从a出发开的远的.

因此可以在O(n)的时间复杂度内解决. 从第一个点开始, 搜索能到达的最远的点, 如果不能走完一圈, 那么这之间的点就不用再试了, 可以直接从最远点的下一个点开始尝试.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int newStart, i = 0;
        while(true){
            if(impl(gas, cost, i, newStart)){
                return i;
            }
            else if(newStart >= gas.size()){
                break;
            }
            else{
                i = newStart;
            }
        }
        return -1;
    }
    
    bool impl(vector<int> &gas, vector<int> &cost, int start, int &newStart){
        int carGas = 0;
        for(int i = start; i < start + gas.size(); i++){
            int index = i % gas.size();
            carGas += gas[index];
            carGas -= cost[index];
            if(carGas < 0) {
                newStart = i + 1;
                return false;
            }
        }
        return true;
    }
};

LeetCode 133. Clone Graph

Sep 25, 2016

题目描述:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

**OJ’s undirected graph serialization:**Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.The graph has a total of three nodes, and therefore contains three parts as separated by #.First node is labeled as 0. Connect node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following:
1
2
3
4
5
6
   1
  / \
 /   \
0 --- 2
     / \
     \_/

使用DFS或者BFS来进行复制就可以了. 有一个要注意的问题就是在新的图中, 连接到已经遍历过的节点的边也要连接到新的图中的节点, 所以不仅要记录原图中节点有没有访问过, 也要记录对应的新的图中的节点. 由于输入数据中节点是用编号来区分的, 因此我用一个map来把节点编号与节点指针对应起来记录访问过的节点, 这样就可以同时记录新的图的节点与原图访问过的节点了(原图用节点编号, 新的图用节点指针).

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return node;
        UndirectedGraphNode *re = new UndirectedGraphNode(node->label);
        queue<UndirectedGraphNode*> BFS, reBFS;
        unordered_map<int, UndirectedGraphNode*> visited;
        BFS.push(node);
        reBFS.push(re);
        visited[re->label] = re;
        while(!BFS.empty()){
            UndirectedGraphNode *p = BFS.front(), *r = reBFS.front();
            for(int i = 0; i < p->neighbors.size(); i++){
                UndirectedGraphNode *next = p->neighbors[i];
                if(visited.count(next->label)){
                    r->neighbors.push_back(visited[next->label]);
                    continue;
                }
                else{
                    UndirectedGraphNode *reNext = new UndirectedGraphNode(next->label);
                    r->neighbors.push_back(reNext);
                    BFS.push(next);
                    reBFS.push(reNext);
                    visited[reNext->label] = reNext;
                }
            }
            BFS.pop();
            reBFS.pop();
        }
        return re;
    }
};

LeetCode 132. Palindrome Partitioning II

Sep 24, 2016

题目描述:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

这道题可以用两次DP来解, 第一个二维数组palindrome[i][j]表示s从i到j的子串是不是回文串, 第二个数组dp[i]保存从0到i的子串有几种分割方法. 对于dp[i]来说, 它有几种分割方法取决于以s[i]为结尾的回文串有多少个. 由于使用普通的遍历比较方法来判断所有的回文串是一个三重循环, 而用DP+从中间向两边比较的方法可以用双重循环解决. 所以总的复杂度是O(n²).

class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        vector<int> dp(len + 1);
        vector<vector<int>> palindrome(len, vector<int>(len, 0));
        for(int i = 0; i < len - 1; i++){
            palindrome[i][i] = 1;
            if(s[i] == s[i + 1]) palindrome[i][i + 1] = 1;
        }
        palindrome[len - 1][len - 1] = 1;
        for(int l = 2; l < len; l++){
            for(int i = 0; i + l < len; i++){
                if(s[i] == s[i + l]) palindrome[i][i + l] = palindrome[i + 1][i + l - 1];
            }
        }
      
        dp[0] = dp[1] = 0;
        for(int i = 2; i <= len; i++){
            if(palindrome[0][i - 1]) dp[i] = 0;
            else{
                int minCut = INT_MAX;
                for(int j = i - 1; j > 0 && minCut > 1; j--){
                    if(palindrome[j][i - 1]){
                        minCut = min(minCut, dp[j] + 1);
                    }
                }
                dp[i] = minCut;
            }
        }
        return dp[len];
    }
};

其实可以把第二个循环的内容也放到第一个循环中去. 为了按行列的顺序来访问数组, 我把palindrome[i][j]的含义改为从j到i的字串是否为回文串.

class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        if(len < 2) return 0;
        vector<int> dp(len);
        vector<vector<int>> palindrome(len, vector<int>(len, 0));
        for(int i = 0; i < len - 1; i++){
            palindrome[i][i] = 1;
            if(s[i] == s[i + 1]) palindrome[i + 1][i] = 1;
        }
        palindrome[len - 1][len - 1] = 1;
        dp[0] = 0;
        dp[1] = palindrome[1][0] ? 0 : 1;
        for(int i = 2; i < len; i++){
            int minCut = dp[i - 1] + 1;
            if(palindrome[i][i - 1]){
                minCut = min(dp[i - 2] + 1, minCut);
            }
            for(int j = i - 2; j >= 0; j--){
                if(s[j] == s[i]) palindrome[i][j] = palindrome[i - 1][j + 1];
                if(j > 0 && palindrome[i][j]){
                    minCut = min(minCut, dp[j - 1] + 1);
                }
            }
            dp[i] = palindrome[i][0] ? 0 : minCut;
        }
        return dp[len - 1];
    }
};

LeetCode 131. Palindrome Partitioning

Sep 23, 2016

问题描述:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return
1
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]

使用回溯法遍历每一种可能的情况.

class Solution {
    vector<vector<string>> ans;
public:
    vector<vector<string>> partition(string s) {
        vector<string> path;
        partitionImpl(s, 0, s.size(), path);
        return ans;
    }
    
    void partitionImpl(string &s, int start, int end, vector<string> &path){
        if(end <= start){
            return;
        }
        if(isPalindrome(s, start, end)){
            path.push_back(s.substr(start, end - start));
            ans.push_back(path);
            path.pop_back();
        }
        for(int i = start + 1; i <= end; i++){
            if(!isPalindrome(s, start, i)) continue;
            path.push_back(s.substr(start, i - start));
            partitionImpl(s, i, end, path);
            path.pop_back();
        }
    }
    
    bool isPalindrome(string &s, int start, int end){
        if(end - start <= 1) return true;
        for(int i = 0; i < (end - start) / 2; i++){
            if(s[start + i] != s[end - i - 1]) return false;
        }
        return true;
    }
};

LeetCode 130. Surrounded Regions

Sep 23, 2016

题目描述:

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
1
2
3
4
5
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
1
2
3
4
X X X X
X X X X
X X X X
X O X X

这道题可以使用并查集或者BFS的方法. 基本思想都是把没有接触边缘的元素归为一类, 然后设置为X. 我使用BFS的方法, 由于查找所有没有接触边缘的区块要遍历整个二维数组, 而查找与边缘有接触的区块只要遍历四条边, 所以我选择找出与边缘有接触的O组成的区块, 把它们使用另一种符号标记(比如T), 然后再遍历整个数组, 把O变为X, T变为O即可得到最终的结果.

class Solution {
    int row, col;
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty()) return;
        row = board.size();
        col = board[0].size();
        for(int i = 0; i < col; i++){
            if(board[0][i] == 'O') BFS(board, 0, i);
        }
        for(int i = 1; i < row - 1; i++){
            if(board[i][0] == 'O') BFS(board, i, 0);
            if(board[i][col - 1] == 'O') BFS(board, i, col - 1);
        }
        for(int i = 0; i < col; i++){
            if(board[row - 1][i] == 'O') BFS(board, row - 1, i);
        }
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == 'T') board[i][j] = 'O';
            }
        }
    }
    
    void BFS(vector<vector<char>> &b, int x, int y){
        queue<pair<int, int>> q;
        q.push(pair<int, int>(x, y));
        b[x][y] = 'T';
        while(!q.empty()){
            int cx = q.front().first, cy = q.front().second;
            if(cx > 0 && b[cx - 1][cy] == 'O'){
                b[cx - 1][cy] = 'T';
                q.push(pair<int, int>(cx - 1, cy));
            }
            if(cy > 0 && b[cx][cy - 1] == 'O'){
                b[cx][cy - 1] = 'T';
                q.push(pair<int, int>(cx, cy - 1));
            }
            if(cx < row - 1 && b[cx + 1][cy] == 'O'){
                b[cx + 1][cy] = 'T';
                q.push(pair<int, int>(cx + 1, cy));
            }
            if(cy < col - 1 && b[cx][cy + 1] == 'O'){
                b[cx][cy + 1] = 'T';
                q.push(pair<int, int>(cx, cy + 1));
            }
            q.pop();
        }
    }
};

LeetCode 129. Sum Root to Leaf Numbers

Sep 22, 2016

题目描述:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,
1
2
3
4
  1
 / \
2   3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

简单的DFS获取所有从根节点到叶子节点的路径的问题.

/**
 * 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 sumNumbers(TreeNode* root) {
        if(!root) return 0;
        vector<int> sums;
        string path;
        getPath(root, path, sums);
        int sum = 0;
        for(int i = 0; i < sums.size(); i++){
            sum += sums[i];
        }
        return sum;
    }
    
    void getPath(TreeNode* root, string &path, vector<int> &sums){
        if(!root->left && !root->right){
            path.push_back(root->val + '0');
            sums.push_back(stoi(path));
            path.pop_back();
            return;
        }
        path.push_back(root->val + '0');
        if(root->left){
            getPath(root->left, path, sums);
        }
        if(root->right){
            getPath(root->right, path, sums);
        }
        path.pop_back();
    }
};