LeetCode OJ – 第31页

LeetCode 459. Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: “abab”

Output: True

Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba”

Output: False
Example 3:
Input: “abcabcabcabc”

Output: True

Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)

分析：设字串长度为len，字符串长度为slen，len从1开始一直到slen / 2遍历，如果slen % len != 0肯定当前len不符合，直接continue；否则将每一个长度为len的字串取出到sub2，比较与sub1是否相等，如果所有的都相等说明满足条件，return true，如果到最后循环结束后依旧没有找到这样一个len满足条件，则return false

class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        int slen = str.length();
        for(int len = 1; len <= slen / 2; len++) {
            if(slen % len != 0)
                continue;
            string sub1 = str.substr(0, len);
            int flag = 0;
            for(int i = len; i < slen; i += len) {
                string sub2 = str.substr(i, len);
                if(sub1 != sub2) {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
                return true;
        }
        return false;
    }
};

class Solution {

public:

bool repeatedSubstringPattern(string str) {

int slen = str.length();

for(int len = 1; len <= slen / 2; len++) {

if(slen % len != 0)

continue;

string sub1 = str.substr(0, len);

int flag = 0;

for(int i = len; i < slen; i += len) {

string sub2 = str.substr(i, len);

if(sub1 != sub2) {

flag = 1;

break;

}

if(flag == 0)

return true;

}

return false;

}

};

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

}

};