2020-03-07 刷题4 设计，数学
384 打乱数组
标签：洗牌算法，数组
本题看得我一脸懵bo，后来看了评论区才知道是要用洗牌算法，也就是保证shuffle过后，每个元素出现在每个位置的概率是相同的，也就是1/n。
1）最naive的做法是，开辟一片空间来存放shuffle后的数组，每次随机从剩下未就位的元素中取出一个元素放好，然后删除刚取出的元素。这种做法的时间复杂度是O(n^2)，因为数组删除元素代价是O(n)，空间复杂度是O(n).
证明：每个元素出现在第k个位置的概率是
n-1/n * n-2/n-1 * ... 1/n-k+1 = 1/n,也就是前k-1轮没有取到它，第k轮取到它的概率。
2）第二种做法是，假设从末尾数k个元素已经就位，每次从前n-k个元素中随机选一个与第n-k个元素交换位置。因为原地操作，所以这种做法的空间复杂度是O(1)，且由于每次交换都是常数时间，时间复杂度也是O(n)。不过这种做法需要提前知道数组的长度。
证明：
洗牌后，每个元素出现在第n-1个位置的概率是：1/n，也就是第一轮就被选中，出现在n-2的概率是：n-1/n * 1/n-1，即第一轮没选中第二轮选中，其他位置也可以类似推出。
代码：
class Solution {
public:
Solution(vector<int>& nums) {
Elements = nums;
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return Elements;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
vector<int> vShuffle = Elements;
for(int i = Elements.size() - 1; i > 0; i--){
int idx = rand() % (i + 1);
if(idx != i)
swap(vShuffle[i], vShuffle[idx]);
}
return vShuffle;;
}
private: vector<int> Elements;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* vector<int> param_1 = obj->reset();
* vector<int> param_2 = obj->shuffle();
*/
这里我犯了个错误，因为要从0到i中随机选一个数，所以应该是rand() % (i+1)，开始写成了rand() % i，这样的话，i是无论如何也出不来的。
3）第三种方法适用于长度未知的数组，从左向右扫描数组，到第i个位置的时候，随机将其与前i个元素中的一个交换（包括它自己）。
证明：
对于第i-1个元素，其出现在前i个位置上任意一个的概率都是1/i * i/i+1 * ...n-1/n=1/n，即后面的n-i次每次交换都没有选到它。
出现在i后位置k-1的概率是：1/k * k/k+1 * ...* n-1/n =1/n.
204 计算质数
标签：质数，数学
最朴实的办法就是依次判断2到n-1之间的每个数i是不是质数，判断的时候，依次对于每个比i小的数，看能否被i整除。
解法1:
优化1: 将用于测试整除的除数上界改为sqrt(n)，判断每个数是不是质数就可以从O(n)降到O(n^1/2).
优化2: 质数一般都出现在6的倍数左右，比如5和7，比如17和19. 很好证明，6x-3, 6x-2, 6x-1, 6x, 6x+1, 6x+2, 这一轮数中，除了6x-1和6x+1，其他的肯定都不是质数。所以，可以将循环的步长设为6，每次判断6x-1和6x+1就可以。这样复杂度降低到原来的1/3.
代码：
class Solution {
public:
bool check_prime(int n){
for(int i = 2; i * i <= n; i++){
if(n % i == 0) return false;
}
return true;
}
int countPrimes(int n) {
int cnt = 0;
for(int i = 2; i <= 4 && i < n; i++){
if(check_prime(i)) cnt++;
}
for(int i = 5; i < n; i += 6){
if(check_prime(i)) cnt++;
if(i+2 < n)
if(check_prime(i+2)) cnt++;
}
return cnt;
}
};
我就说这个运行时间不靠谱，同一份代码我两次跑差了二百多毫秒。
解法2
更快的做法是可以搞一个数组，每扫描到一个数时，就把它的倍数都改为false；当然这样有重复操作的嫌疑，比如扫描到2的时候就会把6置为false了，但是到3的时候，又搞了一遍。比较好的做法就是从这个数的平方开始，哇真的很机智啊，运行时间一下降了好多。这样的复杂度是O(nloglogn).
class Solution {
public:
int countPrimes(int n) {
int cnt = 0;
bool *is_prime = new bool[n];
for(int i = 0; i < n; i++) *(is_prime+i) = true;
for(int i = 2; i < n; i++){
if(*(is_prime+i)){
cnt++;
for(int j = i; j < ceil(float(n) / i); j++) *(is_prime+j*i) = false;
}
}
return cnt;
}
};
326 3的幂
这个题是真的搞笑，不过也很机智。循环或者递归是很好做，但是由于输入就是32位整数，这个范围内最大的3的幂就是3^19, 又因为3是质数，所以能整除3^19的一定是3的幂。一行搞定。。。。
class Solution {
public:
bool isPowerOfThree(int n) {
return (n > 0 && (1162261467 % n == 0));
}
};
13 罗马数字转整数
这个题目比较难处理的就是，小的数字可能出现在大的之前。我开始写了很多条件判读，后来发现除了给定的六种情况，小数字是不会出现在大数字之前的，所以直接比较前后的数字就可以了。发现出现特殊情况，就减去两倍的小数字。
class Solution {
public:
int romanToInt(string s) {
map<char, int> m = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int sum = 0;
for(int i = 0; i < s.size(); i++){
sum = sum + m[s[i]];
if(i > 0){
if(m[s[i-1]] < m[s[i]]) sum = sum - 2 * m[s[i-1]];
}
}
return sum;
}
};
