liuchuo – 第166页

LeetCode 441. Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

分析：直接用公式一行代码就能解决

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)((sqrt(8 * (long)n + 1) - 1)/ 2);
    }
};

class Solution {

public:

int arrangeCoins(int n) {

return (int)((sqrt(8 * (long)n + 1) - 1)/ 2);

}

};

LeetCode 447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

分析：map(m[i] = j)用来存储点与点之间距离（其实是距离的平方，不影响结果）为i的个数j。对于某一点，距离它为i的个数若为j个，则能够构成的i，j，k这样的组数是j * (j – 1)个。每次累计得到的总结果即为所求～

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int cnt = 0;
        for(int i = 0; i < points.size(); i++) {
            map<int, int> m;
            int x1 = points[i].first, y1 = points[i].second;
            for(int j = 0; j < points.size(); j++) {
                if(j == i) continue;
                int x2 = points[j].first, y2 = points[j].second;
                int dis = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
                m[dis]++;
            }
            for(auto it = m.begin(); it != m.end(); it++) {
                cnt += it->second * (it->second - 1);
            }
        }
        return cnt;
    }
};

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

int cnt = 0;

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

map<int, int> m;

int x1 = points[i].first, y1 = points[i].second;

for(int j = 0; j < points.size(); j++) {

if(j == i) continue;

int x2 = points[j].first, y2 = points[j].second;

int dis = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);

m[dis]++;

}

for(auto it = m.begin(); it != m.end(); it++) {

cnt += it->second * (it->second - 1);

}

return cnt;

}

};

LeetCode 448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

分析：hash[i]用来标记i是否在nums数组中出现过。然后将没有出现过的放入result数组中，返回result数组～～～

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        vector<bool> hash(nums.size() + 1, false);
        for(int i = 0; i < nums.size(); i++) {
            hash[nums[i]] = true;
        }
        for(int i = 1; i < hash.size(); i++) {
            if(hash[i] == false)
                result.push_back(i);
        }
        return result;
    }
};

class Solution {

public:

vector<int> findDisappearedNumbers(vector<int>& nums) {

vector<int> result;

vector<bool> hash(nums.size() + 1, false);

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

hash[nums[i]] = true;

}

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

if(hash[i] == false)

result.push_back(i);

}

return result;

}

};

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;

}

};

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

}

};