leetcode 22-03-25

发表于 更新于 分类于 阅读次数： 本文字数： 342 阅读时长 ≈ 1 分钟

今日份 leetcode

  • 1572. 矩阵对角线元素的和
  • 977. 有序数组的平方
  • 278. 第一个错误的版本

1572. 矩阵对角线元素的和

解题思路

存在交点时交点只被计算一次

代码

1
2
3
4
5
6
7
8
// C
int diagonalSum(int** mat, int matSize, int* matColSize){
    int sum = 0;
    for(int i = 0; i < matSize; i++){
        sum += i == matSize - i - 1 ? mat[i][i] : mat[i][i] + mat[i][matSize - i - 1];
    }
    return sum;
}

977. 有序数组的平方

解题思路

每个元素乘以自己然后再排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// C
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp (void * a, void * b){
    return *(int *) a - *(int *) b;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    for (int i = 0; i < numsSize ; i++){
        nums[i] *= nums[i]; 
    }
    qsort(nums,numsSize,sizeof(int),cmp);
    *returnSize = numsSize;
    return nums;
}

278. 第一个错误的版本

本来打算直接找的，不过果不其然超时了，所以用二分

1
2
3
4
5
6
7
8
9
10
11
12
// C
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n) {
    for (int i = 0; i <= n; i++){
        if(isBadVersion(i)){
            return i;
        }
    }
    return 1;
}

解题思路

因为只要错了一个版本后面的都会错，所以只要两边缩直到剩下一个，要注意的是 right 不用 -1 ，因为它本身可能就是第一个错误

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while(left < right){
        int mid = (right - left) / 2 + left;
        if (isBadVersion(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}