来刷题啊 2.23（qsort）

LeetCode

easy

633. Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

开始用的是取个 c = x + y，然后判x、y是不是平方数，但是 T 掉了。看 discuss 的做法过的。

【思路】
取一个小于 c 的平方数 a^2，看 c - a^2 是不是平方数。
因为平方数越到后面间隔越大，会比前面每次步长为 1 的做法快非常的多。

【代码】

bool judgeSquareSum(int c) {
    for(int i=0;i<=sqrt(c);i++) 
    {
        int t=sqrt(c-i*i);
        if(t*t==c-i*i) return true;
    }
    return false;
}

628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

【思路】
有可能有负数，所以并不能快乐地找三个最大的来乘。但是要不然就是三正，要不然就是两负一正。所以拿一个 pos 存正数，一个 neg 存负数，从大到小排序一下看是两负一正大还是三正大。
注意一下负数排序的时候其实是从小到大排序，被这个坑了个wa...

【代码】

int cmp1(const void* a, const void* b){
  return *(int*)b - *(int*)a ;
} 
int cmp2(const void* a, const void* b){
  return *(int*)a - *(int*)b;
} 
int maximumProduct(int* nums, int numsSize) {
    if(numsSize == 3) return nums[0]*nums[1]*nums[2];
    int pos[10001];
    int pLen = 0;
    int neg[10001];
    int nLen = 0;
    for(int i =0; i < numsSize; i++)
    {
        if(nums[i] >= 0) pos[pLen++] = nums[i];
        else neg[nLen++] = nums[i];
    }
    qsort(pos,pLen,sizeof(int),cmp1);
    qsort(neg,nLen,sizeof(int),cmp2);   
    int a = nLen>=2 ? neg[0]*neg[1]*pos[0] : 0;
    int b = pLen>=3 ? pos[0]*pos[1]*pos[2] : 0;
    return a > b ? a : b;
}

qsort的用法
（include < algorithm > ）

qsort(arr,len,sizeof(int),cmp);

和c++的sort不同的是，cmp函数一定要自己写，而且还长的贼丑，很烦。

1. 从小到大排序：

    int cmp(const void* a, const void* b){
      return *(int*)a - *(int*)b;
    } 

1. 从大到小排序：

    int cmp(const void* a, const void* b){
      return *(int*)b - *(int*)a ;
    } 

medium

672. Bulb Switcher II

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:

Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

Note: n and m both fit in range [0, 1000].

这是一道..花了一整个下午的..令人啜泣的题目....

【思路】
表面上看，4 种操作，每种都可能被做 ai 次（a1+a2+a3+a4=m），然而其实任意一种操作，做了偶数次就相当于没做，所以其实只有“做了”和“没做”的区别。
即便 n 再大，最终灯的状态仿佛可以取到 2^n 似的，但其实最多不会超过 2^4 = 16 种（事实上是 12，因为做 1 和做 2 3 效果一样），也就是说 m 太大是没有意义的。
所以..这是一道规律题...

用 4 位的二进制数表示某个操作有没有做：
考虑n = 3 时，(因为当 n >= 3 时才能保证 4 种操作单独做的效果是不一样的)
m = 0, (0000), ans = 1;
m = 1, 1+0, (0001 0010 0100 1000), ans = 4;
m = 2, 2+0 (0+0) || 1+1， (0000 0011 0101 1001 0110 1010 1100), ans = 7
m = 3, 3+0 (1+0) || 2+1 (0+1) || 1+1+1，(0001 0010 0100 1000 0111 1011 1101 1110), ans = 8
之后 m 再大也都是 8。

n = 4时，
m = 0, (0000), ans = 1;
m = 1, 1+0, (0001 0010 0100 1000), ans = 4;
m = 2, 2+0 (0+0) || 1+1， (0000 0011 0101 1001 0110 1010 1100), ans = 7
m = 3, 3+0 (1+0) || 2+1 (0+1) || 1+1+1，(0001 0010 0100 1000 0111 1011 1101 1110), ans = 8
m = 4, 4+0 (0+0) || 3+1(1+1) || 2+2(0+0) || 2+1+1(1+1) || 1+1+1+1, (m=2, 1111), ans = 8
之后也都是 8。

n = 5时，
m = 0, (0000), ans = 1;
m = 1, 1+0, (0001 0010 0100 1000), ans = 4;
m = 2, 2+0 (0+0) || 1+1， (0000 0011 0101 1001 0110 1010 1100), ans = 7
m = 3, 3+0 (1+0) || 2+1 (0+1) || 1+1+1，(0001 0010 0100 1000 0111 1011 1101 1110), ans = 8
m = 4, 4+0 (0+0) || 3+1(1+1) || 2+2(0+0) || 2+1+1(1+1) || 1+1+1+1, (m=2, 1111), ans = 8
m = 5, 5+0(1+0) || 4+1(0+1) || 3+2(1+0) || 3+1+1(1+1+1) || 2+2+1(0+0+1) || 2+1+1+1(0+1+1+1) || 1+1+1+1+1（不存在这种分配）, (m = 3) ans = 8;

也就是说只要 n > 3 ，但凡 m >= 3 就都是 8 。

（其实再想一想会发现，n > 3 和 n = 3 其实是一毛一样的...完全可以用 n = 3 的那三个灯泡代表 n > 3 时的某一类灯泡...）

然后再看
n = 1 时，显然只要 m > 0 都只有 2 种；
n = 2 时，当 m = 1 时为 3，m = 2 时为 4。

【代码】

 int flipLights(int n, int m) {
        if (m == 0 || n == 0) return 1;
        if (n == 1) return 2;
        if (n == 2) return m == 1? 3:4;
        if (m == 1) return 4;
        return m == 2? 7:8;
    }

discuss：https://leetcode.com/problems/bulb-switcher-ii/discuss/107271/C++-concise-code-O(1)
（显然他说的没我清楚...）