Appreciate life and record it

Leetcode

 1337  3    
Leetcode

Leetcode

emacs leecode-client

目前已经有大佬写出了emacs的leecode插件，还有什么理由不好好学习呢？

安装步骤

M-x package-install leetcode

使用

M-x leetcode 发现会装很多的python依赖

leetcode题目

two sum（两数之和） 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

  /**
   ,** code from leetcode -- two sum **
  1. Two Sum

  Easy    likes: 25351    dislikes: 823    solve it    link

  Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to
  target.

  You may assume that each input would have exactly one solution, and you may not use the same element twice.

  You can return the answer in any order.


  Example 1:


  Input: nums = [2,7,11,15], target = 9
  Output: [0,1]
  Output: Because nums[0] + nums[1] == 9, we return [0, 1].

  Example 2:


  Input: nums = [3,2,4], target = 6
  Output: [1,2]

  Example 3:


  Input: nums = [3,3], target = 6
  Output: [0,1]

   ,**/

  #include <stdio.h>
  #include <stdlib.h>

  int query(int *nums, int numsSize, int num) {
    for(int i=0;i<numsSize;i++) {
      if (num == nums[i]) {
        return i;
        break;
      }
    }
    return 0;
  }
  int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int*)malloc(sizeof(int)*3);
    for(int i=0;i<numsSize;i++) {
      int delta = target - nums[i];
      int deltaIndex = query(nums, numsSize, delta);
      if (deltaIndex > 0) {
        ret[0] = i;
        ret[1] = deltaIndex;
        break;
      }
    }
    returnSize = ret;

    return returnSize;
  }
  int main() {
    int nums[10] = {1,2,3,4,6};
    int numsSize = sizeof(nums) / sizeof(int);
    int returnSize[10] = {0};
    twoSum(nums, numsSize,6,returnSize);
    printf("[%d, %d]", returnSize[0],returnSize[1]);
    return 0;
  }

暂时还有点问题 TODO:fix

1 3[0 0]

旋转矩阵

https://leetcode-cn.com/leetbook/read/array-and-string/clpgd/

旋转矩阵我观察起来，是多组4个值交换，然后控制交换的次数，如何按顺序循环

再分析交换的次数其实就是有几个环，简单看下

3x3的时候只有1个环+1个中心

4x4的时候有两个环

5x5的时候有两个环+1个中心

6x6的时候有三个环

7x7的时候有3个环加1个中心

所以cols/2就是环数，也就是循环的数量

循环的终止条件是啥呢？

3x3的时候是从00,01,(02不用)，

4x4的时候是从00,01,02,3(不用), 11,12(不用)

你可能已经发现了

循环外层遍历环

循环开始的时候是依次从(ii,)一直到边界

还有一个就是矩阵的x,y对应关系，以一个4*4矩阵来说 a[0][0],a[0][1],a[0][2],a[0][3],

a[1][0],a[1][1],a[1][2],a[1][3],

a[2][0],a[2][1],a[2][2],a[2][3],

a[3][0],a[3][1],a[3][2],a[3][3]

大致可以得到旋转对应的下标 a[i][j] a[j][4-1-i],行就是上一个的列，列就是index和行的差值 a[4-1-i][4-1-j],和旁边的比，同一个道理 a[4-1-j][i],套用行就是上一个的列

知道上述了我们开始编码哈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

  /**
     This is a problem from leetcode called rotate matrix at https://leetcode-cn.com/leetbook/read/array-and-string/clpgd/. And now this C solution is from liuliancao
     at 20211016..
  ,**/
  void rotateNumbers(int *a, int *b, int *c, int *d) {
    int tmp = *a;
    ,*a = *d;
    ,*d = *c;
    ,*c = *b;
    ,*b = tmp;
  }

  void rotate(int **matrix, int matrixSize, int* matrixColSize) {
    for(int i=0;i<matrixSize/2;i++) {
      for(int j=i;j<*matrixColSize-i-1;j++) {
        rotateNumbers(&matrix[i][j],&matrix[j][*matrixColSize-i-1],&matrix[*matrixColSize-i-1][*matrixColSize-j-1],&matrix[*matrixColSize-1-j][i]);
      }
    }
  }
  int main() {
    int matrixColSize = 3;
    int matrixSize = 3;
    int *matrix[3];
    int p[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    matrix[0] = p[0];
    matrix[1] = p[1];
    matrix[2] = p[2];
    rotate(matrix,matrixSize,&matrixColSize);
    for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
        printf("matrix[%d][%d]: %d\n",i,j, matrix[i][j]);
      }
    }

    int *matrix1[4];
    matrixColSize = 4;
    int p1[4][4] = {{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
    matrix1[0] = p1[0];
    matrix1[1] = p1[1];
    matrix1[2] = p1[2];
    matrix1[3] = p1[3];
    rotate(matrix1,4,&matrixColSize);
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
        printf("matrix1[%d][%d]: %d\n",i,j, matrix1[i][j]);
      }
    }
    return 0;
  }
matrix[0][0]: 7
matrix[0][1]: 4
matrix[0][2]: 1
matrix[1][0]: 8
matrix[1][1]: 5
matrix[1][2]: 2
matrix[2][0]: 9
matrix[2][1]: 6
matrix[2][2]: 3
matrix1[0][0]: 15
matrix1[0][1]: 13
matrix1[0][2]: 2
matrix1[0][3]: 5
matrix1[1][0]: 14
matrix1[1][1]: 3
matrix1[1][2]: 4
matrix1[1][3]: 1
matrix1[2][0]: 12
matrix1[2][1]: 6
matrix1[2][2]: 8
matrix1[2][3]: 9
matrix1[3][0]: 16
matrix1[3][1]: 7
matrix1[3][2]: 10
matrix1[3][3]: 11

零矩阵

https://leetcode-cn.com/leetbook/read/array-and-string/ciekh/

想了下还是用最low的办法按照位置标记，其实按行按列标记会更好一点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

  /**
     The most bad algorithms of the zero matrix by liuliancao at 20211017..
  ,**/
  #include <stdio.h>
  #include <stdlib.h>

  void setZero(int **matrix, int matrixSize, int *matrixColSize,int x, int y){
    for(int i=0;i<matrixSize;i++){
      for(int j=0;j<*matrixColSize;j++){
        if(i==x || j==y){
          matrix[i][j] = 0;
        }
      }
    }
  }
  void zeroMatrix(int **matrix, int matrixSize, int *matrixColSize) {

    int **tmp;
    tmp = (int**)malloc(sizeof(int*)*matrixSize);
    for(int i=0;i<matrixSize;i++){
      tmp[i] = (int*)malloc(sizeof(int*)*(*matrixColSize));
    }

    for(int i=0;i<matrixSize;i++){
      for(int j=0;j<*matrixColSize;j++){
        if(matrix[i][j] == 0){
          tmp[i][j] = 0;
        } else {
          tmp[i][j] = 1;
        }
      }
    }
    for(int i=0;i<matrixSize;i++){
      for(int j=0;j<*matrixColSize;j++){
        if(tmp[i][j]==0){
          setZero(matrix, matrixSize, matrixColSize, i, j);
        }
      }
    }
  }
  int main() {
    int matrixColSize = 3;
    int *matrix[3],p3[3][3]={{1,1,1},{1,0,1},{1,1,1}};
    matrix[0] = p3[0];
    matrix[1] = p3[1];
    matrix[2] = p3[2];
    for(int i=0;i<3;i++){
      printf("%d %d %d\n",matrix[i][0],matrix[i][1],matrix[i][2]);
    }

    zeroMatrix(matrix, 3, &matrixColSize);
    for(int i=0;i<3;i++){
      printf("%d %d %d\n",matrix[i][0],matrix[i][1],matrix[i][2]);
    }

    matrixColSize = 4;
    int *matrix1[3],p4[3][4]={{0,1,2,0},{3,4,5,2},{1,3,1,5}};
    matrix1[0] = p4[0];
    matrix1[1] = p4[1];
    matrix1[2] = p4[2];
    for(int i=0;i<3;i++){
      printf("%d %d %d %d\n",matrix1[i][0],matrix1[i][1],matrix1[i][2],matrix1[i][3]);
    }

    zeroMatrix(matrix1, 3, &matrixColSize);
    for(int i=0;i<3;i++){
      printf("%d %d %d %d\n",matrix1[i][0],matrix1[i][1],matrix1[i][2],matrix1[i][3]);
    }

    return 0;
  }
1 1 1
1 0 1
1 1 1
1 0 1
0 0 0
1 0 1
0 1 2 0
3 4 5 2
1 3 1 5
0 0 0 0
0 4 5 0
0 3 1 0

参考文档