力扣(LeetCode)刷题，简单+中等题(第33期)目录第1题：Z 字形变换第2题：删除字符串中的所有相邻重复项第3题：基本计算器 II第4题：螺旋矩阵第5题：螺旋矩阵 II第6题：盛最多水的容器第7题：删除有序数组中的重复项 II第8题：搜索旋转排序数组 II第9题：平方数之和第10题：最接近的三数之和

54 阅读 0 评论 36 点赞

我是靠谱客的博主虚心帽子，最近开发中收集的这篇文章主要介绍力扣(LeetCode)刷题，简单+中等题(第33期)目录第1题：Z 字形变换第2题：删除字符串中的所有相邻重复项第3题：基本计算器 II第4题：螺旋矩阵第5题：螺旋矩阵 II第6题：盛最多水的容器第7题：删除有序数组中的重复项 II第8题：搜索旋转排序数组 II第9题：平方数之和第10题：最接近的三数之和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

第1题：Z 字形变换

试题要求如下：

解题思路：

回答（C语言）：

char * convert(char * s, int numRows){
    int n = strlen(s);
    if (numRows == 1) return s;
    char* res = (char*)malloc(sizeof(char) * (n + 1));
    int k = 0;

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < n; j++) {
            if (j % (2 * numRows - 2) == i || 
            j % (2 * numRows - 2) == 2 * numRows - 2 - i) {
                res[k++] = s[j];
            }
        }
    }
    
    res[k] = '';
    return res;
}

运行效率如下所示：

第2题：删除字符串中的所有相邻重复项

试题要求如下：

回答（C语言）：

char* removeDuplicates(char* S) {
    int n = strlen(S);
    char* stk = malloc(sizeof(char) * (n + 1));
    int retSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (retSize > 0 && stk[retSize - 1] == S[i]) {
            retSize--;
        } else {
            stk[retSize++] = S[i];
        }
    }

    stk[retSize] = '';
    return stk;
}

运行效率如下所示：

第3题：基本计算器 II

试题要求如下：

回答（C语言）：

int calculate(char* s) {
    int n = strlen(s);
    int stk[n], top = 0;
    char preSign = '+';
    int num = 0;

    for (int i = 0; i < n; ++i) {
        if (isdigit(s[i])) {
            num = num * 10 + (int)(s[i] - '0');
        }

        if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
            switch (preSign) {
                case '+':
                    stk[top++] = num;
                    break;
                case '-':
                    stk[top++] = -num;
                    break;
                case '*':
                    stk[top - 1] *= num;
                    break;
                default:
                    stk[top - 1] /= num;
            }
            preSign = s[i];
            num = 0;
        }
    }

    int ret = 0;
    for (int i = 0; i < top; i++) {
        ret += stk[i];
    }

    return ret;
}

运行效率如下所示：

第4题：螺旋矩阵

试题要求如下：

解题思路：

可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }

    int rows = matrixSize, columns = matrixColSize[0];
    int total = rows * columns;
    int* order = malloc(sizeof(int) * total);
    *returnSize = 0;

    int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
    while (left <= right && top <= bottom) {
        for (int column = left; column <= right; column++) {
            order[(*returnSize)++] = matrix[top][column];
        }
        for (int row = top + 1; row <= bottom; row++) {
            order[(*returnSize)++] = matrix[row][right];
        }
        if (left < right && top < bottom) {
            for (int column = right - 1; column > left; column--) {
                order[(*returnSize)++] = matrix[bottom][column];
            }
            for (int row = bottom; row > top; row--) {
                order[(*returnSize)++] = matrix[row][left];
            }
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    
    return order;
}

运行效率如下所示：

第5题：螺旋矩阵 II

试题要求如下：

回答（C语言）：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    int i;
    int up    = 0;
    int down  = n - 1;
    int left  = 0;
    int right = n - 1;
    int idx   = 1;
    int **res          = (int**)malloc(sizeof(int*) * n);
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    *returnSize        = n;

    /* 输出n*n矩阵 */
    for (i = 0; i < n; i++) {
        res[i] = (int*)malloc(sizeof(int) * n);
        (*returnColumnSizes)[i] = n;
    }

    while (up <= down && left <= right) {
        for (i = left; i <= right; i++) { /* 上 */
            res[up][i] = idx++;
        }
        up++;
        for (i = up; i <= down; i++) {    /* 右 */
            res[i][right] = idx++;
        }
        right--;
        for (i = right; i >= left && up <= down; i--) { /* 下 */
            res[down][i] = idx++;
        }
        down--;
        for (i = down; i >= up && left <= down; i--) { /* 左 */
            res[i][left] = idx++;
        }
        left++;
    }
    
    return res;
}

运行效率如下所示：

第6题：盛最多水的容器

试题要求如下：

解题思路：

采用双指针思路：因为所求区间是类似于窗口的区间，在一直变化，只是取其中最大的一个；可以从两端往中间移动，一次移动中，最小的边与窗口区间组成的面积为本条边所组成的最大容积。

回答（C语言）：

#define MAXSIZE 30000
int stack[MAXSIZE] = {0};

int maxArea(int* height, int heightSize){
    int ret = 0;
    int left = 0;
    int right = heightSize - 1;
    int temp = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            temp = height[left] * (right - left);
            left++;
        } else {
            temp = height[right] * (right - left);
            right--;
        }
        ret = ret > temp ? ret : temp;
    }

    return ret;
}

运行效率如下所示：

第7题：删除有序数组中的重复项 II

试题要求如下：

回答（C语言）：

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize <= 2) {
        return numsSize;
    }
    int slow = 2, fast = 2;
    while (fast < numsSize) {
        if (nums[slow - 2] != nums[fast]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

运行效率如下所示：

第8题：搜索旋转排序数组 II

试题要求如下：

解题思路：

回答（C语言）：

bool search(int* nums, int numsSize, int target) {
    if (numsSize == 0) {
        return false;
    }
    if (numsSize == 1) {
        return nums[0] == target;
    }
    int l = 0, r = numsSize - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
            ++l;
            --r;
        } else if (nums[l] <= nums[mid]) {
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[numsSize - 1]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return false;
}

运行效率如下所示：

第9题：平方数之和

试题要求如下：

解题思路：

回答（C语言）：

bool judgeSquareSum(int c) {
    long left = 0;
    long right = (int)sqrt(c);

    while (left <= right) {
        long sum = left * left + right * right;
        
        if (sum == c) {
            return true;
        } else if (sum > c) {
            right--;
        } else {
            left++;
        }
    }

    return false;
}

运行效率如下所示：

第10题：最接近的三数之和

试题要求如下：

解题思路：

1、先快速排序，再用双指针找三数之和

2、用一个变量gap记录 sum和target的距离（即差的绝对值）, ret记录此时的返回值

3、若有sum = target，直接返回sum。否则所有循环结束后返回ret

回答（C语言）：

int comp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
    int ret, gap = 0x7fffffff;   // gap 记录距离并初始化为最大值，ret 记录此时返回值
    qsort(nums, numsSize, sizeof(int), comp);

    for (int i = 0; i < numsSize - 2; i++) {
        int left = i + 1;
        int right = numsSize - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (abs(sum - target) < gap) {    //如果距离更短，则更新 gap 和 ret
                gap = abs(sum - target);
                ret = sum;
            }
            
            if (sum > target) right--;        //移动左右指针
            else if (sum < target) left++;
            else return sum;
        }
    }

    return ret;
}

运行效率如下所示：