• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

7天前 8次浏览

# 第1题：Z 字形变换

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题：删除字符串中的所有相邻重复项

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

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题：螺旋矩阵

/**
* 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

/**
* 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题：盛最多水的容器

#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

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

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题：平方数之和

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

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;
}