liuchuo – 第167页

LeetCode 283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        for(int i = 0; i < len - 1; i++) {
            if(nums[i] == 0) {
                for(int j = i + 1; j < len; j++) {
                    if(nums[j] != 0) {
                        swap(nums[i], nums[j]);
                        break;
                    }
                }
            }
        }
    }
};

class Solution {

public:

void moveZeroes(vector<int>& nums) {

int len = nums.size();

for(int i = 0; i < len - 1; i++) {

if(nums[i] == 0) {

for(int j = i + 1; j < len; j++) {

if(nums[j] != 0) {

swap(nums[i], nums[j]);

break;

}

};

LeetCode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

class Solution {
public:
    int addDigits(int num) {
        return num - (num - 1) / 9 * 9;
    }
};

class Solution {

public:

int addDigits(int num) {

return num - (num - 1) / 9 * 9;

}

};

LeetCode 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

class Solution {

public:

int minimumTotal(vector<vector<int>>& triangle) {

for(int i = triangle.size() - 2; i >= 0; i--) {

for(int j = 0; j <= i; j++) {

triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);

}

return triangle[0][0];

}

};

LeetCode 485. Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

分析：设立cnt数组，表示在nums[i]处当前连续的1的值，maxn取其最大的值，在遇到nums[i] == 0的时候更新maxn的值。最后还要更新一下防止最后一个是1.

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        vector<int> cnt(nums.size());
        int maxn = 0;
        cnt[0] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == 0) {
                cnt[i] = 0;
                maxn = max(maxn, cnt[i-1]);
            } else {
                cnt[i] = cnt[i-1] + 1;
            }
        }
        maxn = max(maxn, cnt[nums.size() - 1]);
        return maxn;
    }
};

class Solution {

public:

int findMaxConsecutiveOnes(vector<int>& nums) {

vector<int> cnt(nums.size());

int maxn = 0;

cnt[0] = nums[0];

for(int i = 1; i < nums.size(); i++) {

if(nums[i] == 0) {

cnt[i] = 0;

maxn = max(maxn, cnt[i-1]);

} else {

cnt[i] = cnt[i-1] + 1;

}

maxn = max(maxn, cnt[nums.size() - 1]);

return maxn;

}

};

LeetCode 257. Binary Tree Paths

257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

/**
 * 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:
    void dfs(vector<string> &v, TreeNode *node, string s) {
        if(node->left == NULL && node->right == NULL) {
            v.push_back(s);
            return ;
        }
        if(node->left != NULL) {
            dfs(v, node->left, s + "->" + to_string(node->left->val));
        }
        if(node->right != NULL) {
            dfs(v, node->right, s + "->" + to_string(node->right->val));
        }
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> v;
        if(root == NULL) {
            return v;
        }
        dfs(v, root, to_string(root->val));
        return v;
    }
};

/**

* 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:

void dfs(vector<string> &v, TreeNode *node, string s) {

if(node->left == NULL && node->right == NULL) {

v.push_back(s);

return ;

}

if(node->left != NULL) {

dfs(v, node->left, s + "->" + to_string(node->left->val));

}

if(node->right != NULL) {

dfs(v, node->right, s + "->" + to_string(node->right->val));

}

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> v;

if(root == NULL) {

return v;

}

dfs(v, root, to_string(root->val));

return v;

}

};

LeetCode 475. Heaters

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:
Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters‘ warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

题目大意：给出房子的坐标和供暖器的坐标，求供暖器的最小供热半径是多少才能满足让所有房子都暖和。

分析：先将houses和heaters排序，计算每一个house左右的供暖器的距离最小的那个值，然后将所有的这些最小值中取最大的值。
因为houses和heaters都是排序好的，所以heater[j]与houses[i]的距离应该越来越小，如果突然间变大了，说明不是最小值了，就break掉。这样就能得知最小值。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int startindex = 0, maxn = 0;
        for(int i = 0; i < houses.size(); i++) {
            int tempmin = INT_MAX;
            for(int j = startindex; j < heaters.size(); j++) {
                if(abs(heaters[j] - houses[i]) <= tempmin) {
                    tempmin = abs(heaters[j] - houses[i]);
                    startindex = j;
                } else {
                    break;
                }
            }
            maxn = max(maxn, tempmin);
        }
        return maxn;
    }
};

class Solution {

public:

int findRadius(vector<int>& houses, vector<int>& heaters) {

sort(houses.begin(), houses.end());

sort(heaters.begin(), heaters.end());

int startindex = 0, maxn = 0;

for(int i = 0; i < houses.size(); i++) {

int tempmin = INT_MAX;

for(int j = startindex; j < heaters.size(); j++) {

if(abs(heaters[j] - houses[i]) <= tempmin) {

tempmin = abs(heaters[j] - houses[i]);

startindex = j;

} else {

break;

}

maxn = max(maxn, tempmin);

}

return maxn;

}

};