随想录训练营第一天|| 704.二分查找、27.移除元素

********

方法一：左闭右闭

（不知道为什么喜欢写函数，也许不太擅长用while表示二分法）

int df(int l, int r, int* nums, int target) {
    if (l > r) {      //已经不合法了
        return -1;
    }
    //三个if正好对应三种大小情况
    
    //相等直接返回
    int mid = (l + r) / 2;
    if (nums[mid] == target) {
        return mid;
    }
      
    //不相等的情况
    if (nums[mid] > target) {
        return df(l, mid - 1, nums, target);
    }
    if (nums[mid] < target) {
        return df(mid + 1, r, nums, target);
    }
    return -1;
}
int search(int* nums, int numsSize, int target) {
    return df(0, numsSize-1, nums, target);//注意这里是 numsSize-1才算闭区间
}

方法二：左闭右开

（我还是喜欢左闭右闭）

int df(int l, int r, int* nums, int target) {

    if (l >= r) {  //左闭右开，[1）是不合法的
        return -1;
    }

    int mid = (l + r) / 2;
    if (nums[mid] == target) {
        return mid;
    }
    if (nums[mid] > target) {
        return df(l, mid, nums, target); //不需要mid-1，保持右端点不合法
    }
    if (nums[mid] < target) {
        return df(mid + 1, r, nums, target);
    }
    return -1;
}
int search(int* nums, int numsSize, int target) {
    return df(0, numsSize, nums, target); //注意这里是numsSize，不用-1，是开区间
}

（第一道题做完啦，写blog还挺好玩的，一开始紧张的感觉也没有了）

总结一下吧

之前学过一些二分法所以觉得还挺轻松，关键就是注意边界更新的问题(懒了，一会再写

27.移除元素

（long long years later......）

（卡在 27.移除元素了,用前后指针没写出来，总有特殊情况卡我，难受了，不想写了，该吃饭了。。。。。。先暴力一下平复心情）

（纪念一下错题，不能白写）

```int removeElement(int* nums, int numsSize, int val) {
    // 本以为要暴力，原来是双指针

    // 考虑下nums[n]的所有情况
    // 第一种 n==0,直接返回
    // 第二种 n==1，检查再返回
    // 第三种 n>=2，循环
    // 想合并三种情况，但是没想到好办法
    if (numsSize == 0)
        return 0;
    if (numsSize == 1) {
        if (nums[0] == val)
            return 0;
        else
            return 1;
    }
    if (numsSize == 2 && nums[0] == val && nums[1] == val)
        return 0;
    int head = 0, tail = numsSize - 1; // 设置头指针和尾指针
    while (head < tail) {             // 两指针相遇就代表移除完了
        while (nums[head] != val && head < tail)
            head++;
        while (nums[tail] == val && head < tail)
            tail--;
        if (head < tail && nums[head] == val) {
            numsSize--;
            int temp = nums[head];
            nums[head] = nums[tail];
            nums[tail] = temp;
        }
     
    }
    printf("%d\n", numsSize);
    return numsSize;
}

方法一：暴力

（哼哼哼...我暴力出来了）

（不过暴力怎么也有小陷阱，😭）

```int removeElement(int* nums, int numsSize, int val) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == val) {
            for (int j = i; j < numsSize-1; j++) {
                nums[j] = nums[j+1];
            }
            numsSize--;
            i--;      //这里要倒回去一下，避免两个val连在一起而误解
        }
    }
    return numsSize;
}

方法二：双指针

(哼哼，看了卡尔的视频，我会了！

（没想到原来这么简单）

int removeElement(int* nums, int numsSize, int val) {
    // 看了卡尔的视频，我觉得我会了
    int fast = 0, slow = 0;  //设置快慢指针，慢指针构造新数组下标，快指针在原数组寻找新数组的元素；
    for (; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

977.有序数组

方法一：暴力

（拿到题了，总之先暴力）

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 //英语不好，看不懂note，翻译之后读不懂中文，服了自己
int cmp(const void* a, const void* b) { 
    return (*(int*) a - *(int*) b); 
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;  //一开始忽视了返回长度，还以为没用呢，原来是个隐藏的return，怪不得总是空数组【NULL】
    for (int i = 0; i < numsSize; i++) {
        nums[i] = nums[i] * nums[i];
    }
    qsort (nums, numsSize, sizeof (int), cmp);
    return nums;
}

方法二：双指针

（先自己想了个奇奇怪怪没法通过的双指针，憋不出来看了卡尔，看完思路自己去写了写，跟卡尔写的形式不一样但是本质一样的）

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int l, r;
    l = 0, r = numsSize - 1;
    *returnSize = numsSize;
    int* a = (int*)malloc(sizeof(int) * numsSize);
    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[l] * nums[l] > nums[r] * nums[r]) {
            a[i] = nums[l] * nums[l];
            l++;
        } else {
            a[i] = nums[r] * nums[r];
            r--;
        }
    }
    return a;
}