蓝桥杯程序设计备赛（2024.1.14）

33. 搜索旋转排序数组https://leetcode.cn/problems/search-in-rotated-sorted-array/

? ? ? ? 这个题目的描述很长，请耐心读完。你会发现中间那一大段对解题好像没有什么用。这个题目化简起来就是给你一个nums数组，然后需要你去找一下这个nums数组里面有没有target这个数字，如果有就返回target在nums里面的下标，如果没有就返回-1。

? ? ? ? 读完题目就有思路了，超级快。对nums这个数组进行遍历，比较每个元素跟target的大小，如果一样就return下标，如果没有一样的，那就return-1。

????????提醒一下哦，下标是从0开始的。题目的这个nums数组的长度为numsSize，那么nums这个数组的下表就是从0到numsSize-1。

int search(int* nums, int numsSize, int target) {
    for(int i =0;i<numsSize;i++){
        if(nums[i] == target)return i;
    }    
    return -1;
}

81. 搜索旋转排序数组 IIhttps://leetcode.cn/problems/search-in-rotated-sorted-array-ii/????????这题跟上面那题很像，先自己写写看，看一下你能不能理解这种题目的解题方法。

153. 寻找旋转排序数组中的最小值https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

? ? ? ? 这题也有两种方法能解。

? ? ? ? 一、挨个遍历找出最小值

? ? ? ? 第1个跟第二2个比，如果第1个小，那么就拿第1个跟第3个比，如果第3个小，就拿第3跟跟第4个比。这个思路的还是需要我们来遍历数组。

int findMin(int* nums, int numsSize) {
    int min = nums[0];
    for(int i = 1;i<numsSize;i++){
        if(min>nums[i])min = nums[i];
    }
    return min;
}

? ? ? ? ? 二、排个顺序

? ? ? ? 题目中说了，数组nums里面的元素值互不相同，所以说我们可以给他来个升序排列。这个具体怎么排列的后面到排列的时候再说，我先把代码给出来。升序排列之后的最小值就是数组里面的第一个数。

int cmp(const void*a,const void*b){
    int val1 = *(int*) a;
    int val2 = *(int*) b;
    return val1>val2?1:-1;
}

int findMin(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int),cmp);
    return nums[0];
    }

509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/

? ? ? ? 这个的话，还是遍历。涉及到递归，可以自行了解。

? ? ? ? 我们要先申请一个足够大的数组，因为n的最大值是30，也就是下标的最大值是30.所以需要申请31个。然后再给下标是0和1的赋值，最后按照计算规则进行遍历计算。

int fib(int n){
    int f[31];
    f[0] = 0;
    f[1] = 1;
    for(int i = 2;i<=n;i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

70. 爬楼梯https://leetcode.cn/problems/climbing-stairs/????????这题也是斐波那契数列。

int climbStairs(int n) {
    int f[46];
    f[1] = 1;
    f[2] = 2;
    for(int i = 3;i<=n;i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

1137. 第 N 个泰波那契数https://leetcode.cn/problems/n-th-tribonacci-number/

int tribonacci(int n){
    int f[38];
    f[0] = 0;
    f[1] = f[2] = 1;
    for(int i = 3;i<=n;i++){
        f[i] = f[i-1]+f[i-2]+f[i-3];
    }
    return f[n];
}

2006. 差的绝对值为 K 的数对数目https://leetcode.cn/problems/count-number-of-pairs-with-absolute-difference-k/

第一个数字跟第一个数字后面的数字去做差，然后对差利用abs函数来绝对值，再去判断跟k是不是一样的，一样的就cnt加1，cnt代表满足题目意思的对数。

int countKDifference(int* nums, int numsSize, int k) {
    int cnt = 0;
    for(int i = 0;i<numsSize;i++){
        for(int j = i+1;j<numsSize;j++){
            if(abs(nums[j]-nums[i]) == k){
                cnt++;
            }
        }
    }
    return cnt;
}

int game(int* guess, int guessSize, int* answer, int answerSize){
    int cnt= 0;
    for(int i = 0 ;i<guessSize;i++){
       if(guess[i] == answer[i]) cnt++;
    }
    return cnt;
}

int minCount(int* coins, int coinsSize){
    int sum = 0;
    for(int i = 0;i<coinsSize;i++){
        sum += coins[i]%2==0?coins[i]/2:(coins[i]+1)/2;
    }
    return sum;
}

int peakIndexInMountainArray(int* arr, int arrSize){
    int n = arr[0];
    int j;
    for(int i = 1; i<arrSize ; i++){
        if(n<arr[i]) {
            n=arr[i];
            j = i;
            if (n>arr[i+1]) break;
        }
    }
    return j;
}