C practice

solution.c

// Online C compiler to run C program online
#include <stdio.h>
#include <stdbool.h>
/* 給一個int a[20]已排序的陣列，請寫一個function(a, size)能印出0~500的數字，
   且不包含a陣列內的元素，請用最少的時間和空間複雜度完成 */
void solution1(int a[], int size) {
    int cur = 0;
    while (cur < size && *(a + cur) < 0)
        cur += 1;
    for (int i = 0; i <= 500; i += 1) {
        if (i != *(a + cur)) printf("%d ", i);
        while (cur < size && i == *(a + cur))
            cur += 1;
    }
}
/*給一個int a[20]已排序的陣列，請寫一個function(a, size, b) 能依照參數b(b = 0~4)別印出該區間的數字，
  且不包含a陣列內的元素，例如 b =0, 印出0~99 b = 1, 印出100~199 */
 void solution2(int a[], int size, int b) {
    b *= 100;
    int cur = 0;
    while (cur < size && *(a + cur) < b)
        cur += 1;
    for (int i = b; i < b + 100; i += 1) {
        if (i != *(a + cur)) printf("%d ", i);
        while (cur < size && i == *(a + cur))
            cur += 1;
    }
}

int binarySearch(int nums[], int target, int size) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
bool isTheSame(unsigned short num) {
    unsigned short same[4];
    same[0] = num & 0x000F;
    same[1] = (num & 0x00F0) >> 4;
    same[2] = (num & 0x0F00) >> 8;
    same[3] = (num & 0xF000) >> 12;
    return (same[0] == same[1]) && (same[1] == same[2]) && (same[2] == same[3]);
}

unsigned int MSB(unsigned int n){
    if (n == 0) return 0;
    unsigned int ans = 1;
    while (n != 1){
        n >>= 1;
        ans <<= 1;
    }
    return ans;
}
int gcd(int a, int b){
    // while (b) {
    //     int r = a % b;
    //     a = b, b = r;
    // }
    // return a;
    return b == 0 ? a: gcd(b, a%b);
}
void stringReverse(char* st, int size) {
    size -= 1;
    for (int i = 0; i < size / 2; i += 1) {
        char tmp = *(st + size - i - 1);
        *(st + size - i - 1) = *(st + i), *(st + i) = tmp;
    }
    printf("%s\n", st);
}

int partition(int nums[], int l, int r) {
    int i = l, p = nums[r];
    int tmp;
    for(int j = l; j < r; j += 1) {
        if (nums[j] <= p) {
            tmp = nums[j];
            nums[j] = nums[i], nums[i] = tmp;
            i += 1;
        }
    }
    nums[r] = nums[i], nums[i] = p;
    return i;
}
void quickSort(int nums[], int l, int r) {
    if (l < r) {
        int p = partition(nums, l, r);
        quickSort(nums, l, p - 1);
        quickSort(nums, p + 1, r);
    }
    
}
int main() {
    // Write C code here
    int nums1[] = {1,2,3,4,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,9,25,25,26,26,27,28,26,80,252,300};
    // solution1(nums, sizeof(nums1) / sizeof(int));
    int nums2[] = {1,2,3,4,5,6,6,9,50,101,111,115,118,119,120,120,120,124,152,198,199,199,199,199};
    // solution2(nums2, sizeof(nums2) / sizeof(int), 1);
    // printf("%d\n", binarySearch(nums1, 300, sizeof(nums1)/sizeof(int)));
    // printf("%d\n", isTheSame(0xaaad));
    // printf("%d\n", MSB(0x10000000));
    // printf("%d\n", gcd(27,18));
    char st[] = "hello";
    // stringReverse(st, sizeof(st)/sizeof(char));
    int nums3[] = {9,8,8,8,5,5,5,2,2,2,1,1,0,1,1,5,5,9,9,-9,-9,-9-8};
    int size = sizeof(nums3) / sizeof(int);
    quickSort(nums3, 0, size - 1);
    for (int i = 0; i < size; i += 1)
        printf("%d ", nums3[i]);
    return 0;
}