Code – 第166页

【C++】C++中substr的用法

substr有2种用法：
假设：string s = “0123456789”;

string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789”

string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = “567”

LeetCode 463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Answer: 16

分析：如果彼此不相连，那么一个1就应该有4条边；考虑相连的情况，为了避免重复计算，只取每个为1的坐标的左边和上边：
如果当前点为1而且它上面也为1，他们彼此相连导致双方都失去1条边，也就是2条边；同理如果当前点为1它左边也为1，他们彼此相连导致双方都失去1条边，也就是2条边。不考虑第一行没有上一行和第一列没有左边的情况，则可以遍历每一个格子得到cnt

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int cnt = 0;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if(grid[i][j] == 1) {
                    cnt += 4;
                    if(i != 0 && grid[i-1][j] == 1)
                        cnt -= 2;
                    if(j != 0 && grid[i][j-1] == 1)
                        cnt -= 2;
                }
            }
        }
        return cnt;
    }
};

class Solution {

public:

int islandPerimeter(vector<vector<int>>& grid) {

int cnt = 0;

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

for(int j = 0; j < grid[i].size(); j++) {

if(grid[i][j] == 1) {

cnt += 4;

if(i != 0 && grid[i-1][j] == 1)

cnt -= 2;

if(j != 0 && grid[i][j-1] == 1)

cnt -= 2;

}

return cnt;

}

};

LeetCode 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

分析：mask – 1为和num二进制位等长的所有位数为1的数，与num取^可以得到和num相反的数字。

class Solution {
public:
    int findComplement(int num) {
        int temp = num, mask = 1;
        while(temp != 0) {
            temp = temp >> 1;
            mask = mask << 1;
        }
        return num ^ (mask - 1);
    }
};

class Solution {

public:

int findComplement(int num) {

int temp = num, mask = 1;

while(temp != 0) {

temp = temp >> 1;

mask = mask << 1;

}

return num ^ (mask - 1);

}

};

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];

}

};