LeetCode OJ – 第24页

LeetCode 481. Magical String

A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules:

The string S is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string S itself.

The first few elements of string S is the following: S = “1221121221221121122……”

If we group the consecutive ‘1’s and ‘2’s in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 ……

and the occurrences of ‘1’s or ‘2’s in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ……

You can see that the occurrence sequence above is the S itself.

Given an integer N as input, return the number of ‘1’s in the first N number in the magical string S.

Note: N will not exceed 100,000.

Example 1:
Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is “12211” and it contains three 1’s, so return 3.

分析：直接按照这个字符串的构造方法还原这个字符串s：首先初始化s = “122”,让index指向下标为2处，开始根据index指向的字符在s后面添加字符串，如果指向的是2就添加2个，如果指向的是1就添加一个，具体添加什么字符以当前s的末尾一位的字符是1还是2为准，如果s当前最后一个字符是1就添加2，反之添加1～还原好了之后用count直接计算字符串从begin()到n长度处一共有多少个’1’字符～～

class Solution {
public:
    int magicalString(int n) {
        string s = "122";
        int index = 2;
        while(s.length() < n) {
            int cnt = s[index] - '0';
            char c = (s.back() == '1' ? '2' : '1');
            string temp(cnt, c);
            s += temp;
            index++;
        }
        return count(s.begin(), s.begin() + n, '1');
    }
};

class Solution {

public:

int magicalString(int n) {

string s = "122";

int index = 2;

while(s.length() < n) {

int cnt = s[index] - '0';

char c = (s.back() == '1' ? '2' : '1');

string temp(cnt, c);

s += temp;

index++;

}

return count(s.begin(), s.begin() + n, '1');

}

};

LeetCode 462. Minimum Moves to Equal Array Elements II

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example:

Input:
[1,2,3]

Output:
2

Explanation:
Only two moves are needed (remember each move increments or decrements one element):

[1,2,3] => [2,2,3] => [2,2,2]

题目大意：给一个非空整数数组，每次可以将数组中一个元素+1或者-1，求最少需要多少次这样的操作，才能使数组中所有的数都想等～

分析：让所有数都等于那个第n/2 + 1大的数字～首先用nth_element(nums.begin(), nums.begin() + n / 2, nums.end());将第n/2 + 1大的数字放到最中间，然后取得它的值为mid，最后遍历数组，累加所有元素与mid的差的绝对值即为所求～

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int result = 0, n = nums.size();
        nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
        int mid = *(nums.begin() + n / 2);
        for(int i = 0; i < n; i++)
            result += abs(nums[i] - mid);
        return result;
    }
};

class Solution {

public:

int minMoves2(vector<int>& nums) {

int result = 0, n = nums.size();

nth_element(nums.begin(), nums.begin() + n / 2, nums.end());

int mid = *(nums.begin() + n / 2);

for(int i = 0; i < n; i++)

result += abs(nums[i] - mid);

return result;

}

};

LeetCode 492. Construct the Rectangle

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1. The area of the rectangular web page you designed must equal to the given target area.

2. The width W should not be larger than the length L, which means L >= W.

3. The difference between length L and width W should be as small as possible.
You need to output the length L and the width W of the web page you designed in sequence.
Example:
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3, [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
Note:
The given area won’t exceed 10,000,000 and is a positive integer
The web page’s width and length you designed must be positive integers.

题目大意：给定area，求长和宽，使得长方形面积等于area，要求长>=宽并且长和宽之间的大小差距尽可能小～～

分析：先令长l和宽w等于sqrt(area), 如果长x宽得到的面积不等于area，稍微调整l和w的大小：如果面积小了，将长+1；如果面积大了，将宽-1。直到最后l * w == area为止～

class Solution {
public:
    vector<int> constructRectangle(int area) {
        vector<int> result(2, 0);
        int l = sqrt(area), w = sqrt(area);
        while(l * w != area) {
            if(l * w < area)
                l++;
            else
                w--;
        }
        result[0] = l;
        result[1] = w;
        return result;
    }
};

class Solution {

public:

vector<int> constructRectangle(int area) {

vector<int> result(2, 0);

int l = sqrt(area), w = sqrt(area);

while(l * w != area) {

if(l * w < area)

l++;

else

w--;

}

result[0] = l;

result[1] = w;

return result;

}

};

LeetCode 419. Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.
Example:
X..X
…X
…X
In the above board there are 2 battleships.
Invalid Example:
…X
XXXX
…X
This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

题目大意：给一张地图，战列舰用X表示，空地用.表示，战列舰只可能横着或者竖着一条，而且两条战列舰之间肯定有空地，计算战列舰的个数～

分析：其实只需要数战列舰的头部有几个就行了，因为战列舰要么横着要么竖着，它的头部肯定满足以下条件：1.它的上方是空地（或者边界） 2.它的左方是空地（或者边界）
这样遍历一遍地图上所有的点，如果当前点是X而且满足上面所述的两个条件，就将战列舰个数+1～～～

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int result = 0;
        if(board.size() == 0) return 0;
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[0].size(); j++) {
                if(board[i][j] == 'X' && (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.'))
                    result++;
            }
        }
        return result;
    }
};

class Solution {

public:

int countBattleships(vector<vector<char>>& board) {

int result = 0;

if(board.size() == 0) return 0;

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

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

if(board[i][j] == 'X' && (i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.'))

result++;

}

return result;

}

};

LeetCode 406. Queue Reconstruction by Height

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

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

题目大意：给一组序列(h, k), h表示身高，k表示在当前人的前面有k个人比他高，求满足这样的排队序列～

分析：先将所有人按照身高h排序，如果他们的身高h相同就按照k从小到大排序～接下来就可以构建result数组了，从排序好的序列第一个数开始一直遍历到最后一个，依次把它插入到result数组的第k位，因为对于当前这个人，他说了比他高的人是k个，而整个数组按照身高排序了，所以前面的所有人都是比他高的，排他的队伍的时候只需要排到第k位就能满足他前面比他高的人是k个～这样将所有人都插入后得到的result即为所求队伍的顺序～～

class Solution {
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> result;
        if(people.size() == 0)
            return result;
        auto cmp = [](pair<int, int> p1, pair<int, int> p2) {
            if(p1.first == p2.first)
                return p1.second < p2.second;
            else
                return p1.first > p2.first;
        };
        sort(people.begin(), people.end(), cmp);
        for(auto it : people) {
            result.insert(result.begin() + it.second, it);
        }
        return result;
    }
};

class Solution {

public:

vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {

vector<pair<int, int>> result;

if(people.size() == 0)

return result;

auto cmp = [](pair<int, int> p1, pair<int, int> p2) {

if(p1.first == p2.first)

return p1.second < p2.second;

else

return p1.first > p2.first;

};

sort(people.begin(), people.end(), cmp);

for(auto it : people) {

result.insert(result.begin() + it.second, it);

}

return result;

}

};

LeetCode 413. Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.
Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

题目大意：求一个数组中能构成至少连续三个数的等差数列的个数

分析：有一个规律是：
连续3个数构成等差数列，能组成的等差数列个数是1
连续4个数构成等差数列，能组成的等差数列个数是3（1+2）
连续5个数构成等差数列，能组成的等差数列个数是6（1+2+3）
……
所以每次当有三个构成等差数列的时候，cnt = 1，之后每连续增加一个数满足与之前的数构成等差数列，就令cnt++，并且将结果加到最终的result里面～

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int cnt = 0, result = 0;
        for(int i = 2; i < A.size(); i++) {
            if(A[i-1] - A[i-2] == A[i] - A[i-1]) {
                cnt++;
                result += cnt;
            } else {
                cnt = 0;
            }
        }
        return result;
    }
};

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int cnt = 0, result = 0;

for(int i = 2; i < A.size(); i++) {

if(A[i-1] - A[i-2] == A[i] - A[i-1]) {

cnt++;

result += cnt;

} else {

cnt = 0;

}

return result;

}

};