力扣(LeetCode)刷题，简单+中等题(第33期)
力扣(LeetCode)刷题，简单+中等题(第33期)
不脱发的程序猿
发布于 2021-05-08 11:37:21
发布于 2021-05-08 11:37:21
文章被收录于专栏：AIoT技术交流、分享
力扣(LeetCode)定期刷题，每期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] = '\0';
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] = '\0';
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;
}运行效率如下所示：
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/04/29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
容器服务
腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
腾讯云开发者
