来刷题啊 2.24

LeetCode

今天一整天都在快乐地刷签到题划水- -...

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1

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

Example 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

【思路】
本来一眼的想法就是 sort 一下遍历，但是题目要求是线性复杂度。所以拿一个 bool 数组来存是否存在这个数就好了。

【代码】

int missingNumber(int* nums, int numsSize) {
    bool arr[numsSize+1];
    memset(arr,0,sizeof(arr));
    for(int i = 0; i < numsSize; i++)
        arr[nums[i]] = 1;
    for(int i = 0; i <= numsSize; i++)
        if(arr[i] == 0) return i;
    return 0;
}

【改进思路】
哇，我是真没想到还有这种操作。空间复杂度是O(1)。
思路是把 0~n 的和求出来，然后拿去一个个减掉 nums 数组里的数，减完剩下的那个就是丢失的数。

int missingNumber(int* nums, int numsSize) {
    int sum = numsSize*(numsSize+1)/2;
    for(int i = 0; i < numsSize; i++) sum -= nums[i];
    return sum;
}

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

【思路】
题目是说数组里面每个元素都出现了两次，除了有一个是只出现了一次，找到这个数字。
用异或已经是老套路了。

【代码】

int singleNumber(int* nums, int numsSize) {
    int a = 0;
    for(int i = 0; i < numsSize; i++) a ^= nums[i];
    return a;
}

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

两个排好序的数组，将 nums2 合并到 nums1 里面去，成为一整个排序好的数组。

【思路】
从头到位一个个去比对，哪个小把哪个拿出来放到一个新数组，最后在放回 nums1 里去。

【代码】

void merge(int* nums1, int m, int* nums2, int n) {
    int arr[m+n];
    memset(arr,0,sizeof(arr));
    int p1 = 0, p2 = 0;
    for(int i = 0; i < m+n; i++)
    {
        if(p1 == m) 
        {
            while(p2 < n) arr[i++] = nums2[p2++];
            break;
        }
        if(p2 == n)
        {
            while(p1 < m) arr[i++] = nums1[p1++];
            break;
        } 
        if(nums1[p1] < nums2[p2]) arr[i] = nums1[p1++];
        else arr[i] = nums2[p2++];
    }
    for(int i = 0; i < m+n; i++) nums1[i] = arr[i];
}

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

判断一个数是不是 2 的幂次。

【思路】
二进制数上只有 1 个位是 1。
要注意一下特判非正数的情况，因为用补码表示负数会有一堆前导 1 ，就会超时。

【代码】

bool isPowerOfTwo(int n) {
    if(n <= 0) return false;
    int cnt = 0;
    while(n)
    {
        if(n&1 == 1) cnt++;
        n >>= 1;
    }
    if(cnt == 1) return true;
    else return false;
}

【看到一个思路】
也是位运算，算是利用 2 的幂次的特殊性质吧。代码更短但是运行效率没有上面高哈哈哈，不过挺巧妙的，是用 n&(n-1) == 0 来判。
因为所有 2 的 n 次方的数的二进制都是一开始一个 1 ，后面全是 0， 1000xxxx（一堆0）这样的，那这样一个数-1 之后，就是 0111xxxx（一堆1），相与为 0。
（这时候的特殊情况是 0 ，也会被判为 true ，所以还是保留特判）

bool isPowerOfTwo(int n) {
    if(n <= 0) return false;
    if((n & (n-1)) == 0) return true;
    return false;
}

练习 手写快速排序

嘤嘤嘤，手动表白UP主正月点灯笼qvq

//把小于支点的数扔到支点的左边，大于的扔到右边；返回支点位置 
int partition(int arr[], int L, int R)
{
    int pivot = arr[R]; //选择最后一个数字做支点 
    int j = L;
    for(int i = L; i <= R; i++)
    {
        if(arr[i] < pivot)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            j++;
        }
    }
    //交换最终j和支点位置数 
    int tmp = arr[R];
    arr[R] = arr[j];
    arr[j] = tmp;
    return j; 
}
void quicksort(int arr[], int L, int R) 
{
    if(L < R)
    {
        int M = partition(arr,L,R);
        quicksort(arr,L,M-1);
        quicksort(arr,M+1,R);
    }
}