Code – 第158页

LeetCode 398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

题目大意：给一个整数数组，里面可能有重复元素。给一个target，随机返回一个数组元素等于target的元素下标～

分析：将所有等于target的元素的下标存储在index数组中，然后根据rand() % index.size()的值随机从index中取一个值返回～

class Solution {
private:
    vector<int> nums;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
    }
    
    int pick(int target) {
        vector<int> index;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == target)
                index.push_back(i);
        }
        return index[rand() % index.size()];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

class Solution {

private:

vector<int> nums;

public:

Solution(vector<int> nums) {

this->nums = nums;

}

int pick(int target) {

vector<int> index;

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

if(nums[i] == target)

index.push_back(i);

}

return index[rand() % index.size()];

}

};

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* int param_1 = obj.pick(target);

LeetCode 382. Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

题目大意：给一个单链表，返回一个随机结点的值，要求每一个结点都有同样的概率被选中～

分析：先求出链表的长度len，然后用rand() % len生成一个0～len-1之间的随机数cnt，然后从head开始遍历直到第cnt个结点，返回第cnt个结点的值～

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    ListNode* head;
    int len;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        this->head = head;
        len = 1;
        while(head->next != NULL) {
            head = head->next;
            len++;
        }
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int cnt = rand() % len;
        while(cnt--) {
            node = node->next;
        }
        return node->val;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

private:

ListNode* head;

int len;

public:

/** @param head The linked list's head.

Note that the head is guaranteed to be not null, so it contains at least one node. */

Solution(ListNode* head) {

this->head = head;

len = 1;

while(head->next != NULL) {

head = head->next;

len++;

}

/** Returns a random node's value. */

int getRandom() {

ListNode* node = head;

int cnt = rand() % len;

while(cnt--) {

node = node->next;

}

return node->val;

}

};

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(head);

* int param_1 = obj.getRandom();

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

}

};