liuchuo – 第159页

【C++】n_element的用法

n_element函数定义在头文件#include <algorithm>里面，用法是：

n_element(v.begin(), v.begin() + k, v.end());

表示假设v排序后v[k]应该存储的值为v[k]，则n_element函数的作用就是让v[k]这个值放在v[k]处，且让v[k]左边的数都小于v[k]，v[k]右边的数都大于v[k]。但是不保证他们是有序的。（即v[k]处存放的是第k+1大的数，并且左边数都比他小右边数字都比他大，比如假设k = 1，表示将v[1]处设置为第2大的数）

也可以自定义添加cmp函数，表示方法为：

n_element(v.begin(), v.begin() + k, v.end(), cmp);

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
    nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    cout << "The median is " << v[v.size()/2] << '\n';
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

nth_element(v.begin(), v.begin() + v.size()/2, v.end());

cout << "The median is " << v[v.size()/2] << '\n';

}

输出为：

The median is 5

【发现两个好玩的句子】怠穿糙费孬渡茬杀长辑、法互瘁就诓脚搭协但茅

怠穿糙费孬渡茬杀长辑

法互瘁就诓脚搭协但茅

这两个句子是在搜索百度or谷歌的时候发现的

经常无端出现在正常的句子中间

好像是什么奇怪的乱码或者编码问题导致的～

啦啦啦好好玩～

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;

}

};