leetcode 14天算法入门 C语言实现

文章目录

leetcode 14天算法入门 C语言实现

leetcode 14天算法入门 C语言实现

第一天二分查找

二分法讲解 : 把答案所在的区间逐渐缩小，直到区间内只有答案。

图解:

704. 二分查找

思路:二分思想,不用解释直接上手

代码:

int search(int* nums, int numsSize, int target){
int left=0;
int right=numsSize-1;
while(left<=right)
{
    int mid=(right-left)/2+left;
    if(nums[mid]==target)
    {
        return mid;
    }
    if(nums[mid]<target)
    {
        left=mid+1;
    }
    else
    {
        right=mid-1;
    }
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

278. 第一个错误的版本

思路:还是基本的二分思想,当mid是真时,说明mid处为真,则left=mid+1,如此不断缩小间距,当left>=right时left处指的一定是第一个错误版本(此处不在证明)

代码:

// 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;
       bool tmp=isBadVersion(mid);
       if(!tmp)
            {
            left=mid+1;
            }
        else
            {
            right=mid;
             }

     }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

35. 搜索插入位置

思路:*nums*[*p**o**s*−1]<*target*≤*nums*[*p**o**s*]只要需要理解这个概念就ok了

代码:

int searchInsert(int* nums, int numsSize, int target){
int left=0;
int right=numsSize-1;
int mid=0;
while(left<=right)
{
    mid=(right-left)/2+left;
    if(nums[mid]==target)
    {
        return mid;
    }
    if(nums[mid]>target)
    {
        right=mid-1;
    }
    else
    {
        left=mid+1;
    }
}
return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第二天双指针

双指针法讲解:双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

977. 有序数组的平方

思路:1.每个数都平方,平方后在排序,当然这就和双指针以及题目的非递减条件无关了.

2.最大的平方数一定出自左端或右端,所以使用双指针,一个左端一个右端,左右交替选最大平方值.

代码:

int mul(int a)
{
    return a*a;   
}

int* sortedSquares(int* nums, int numsSize, int* returnSize){
int left=0;
int right=numsSize-1;
*returnSize=numsSize;
int *answer=(int *)malloc(sizeof(int)*numsSize);
int loc=numsSize-1;
while(left<=right)
{
    if(mul(nums[left])>mul(nums[right]))
    {
        answer[loc]=mul(nums[left]);
        left++;
    }
    else
    {
        answer[loc]=mul(nums[right]);
        right--;
    }
    loc--;
}
return answer;
}
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

189. 轮转数组

思路:k的左边反转,k的右边反转,最后对于数组整体反转,即可以完成实现

代码:

void swap(int *a,int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

void exchange(int *nums,int left,int right)
{
    while(left<right)
    {
        swap(nums+left,nums+right);
        left++;
        right--;
    }
}


void rotate(int* nums, int numsSize, int k){
k=k%numsSize;
exchange(nums,0,numsSize-1-k);
exchange(nums,numsSize-k,numsSize-1);
exchange(nums,0,numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

第三天双指针

283. 移动零

思路:注释部分是我第一次写的,使用的两个指针来记录0和非0的位置,进行移动操作

非注释时对该代码的简化

代码:

void swap(int *a,int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void moveZeroes(int* nums, int numsSize){
// int numloc=0;
// int zeroloc=0;
// while(numloc
// {
//     while(zeroloc
//     {
//         zeroloc++;
//     }
//      if(zeroloc==numsSize)
//     {
//         break;
//     }
//     //numloc=zeroloc+1;
//     while(numloc
//     {
//         numloc++;
//     }
//     if(numloc>=numsSize||zeroloc>=numsSize)
//     {
//         break;
//     }
//     if(numloc>zeroloc)
//     swap(nums+zeroloc,nums+numloc);
//     //zeroloc++;
//     numloc++;
// }
int left = 0, right = 0;
    while (right < numsSize) {
        if (nums[right]) {
            swap(nums + left, nums + right);
            left++;
        }
        right++;
    }
}
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

167. 两数之和 II - 输入有序数组

思路:左指针,右指针,大于目标数,右指针左移.小于目标数,左指针右移.

代码:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
int left=0;
int right=numbersSize-1;
int *answer=(int *)malloc(sizeof(int)*2);
*returnSize=2;
while(1)
{
    if(numbers[left]+numbers[right]==target)
    {
        answer[0]=left+1;
        answer[1]=right+1;
        break;
    }
    else if(numbers[left]+numbers[right]<target)
    {
        left++;
    }
    else
    {
        right--;
    }
}
return answer;
}
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

第四天双指针

344. 反转字符串

思路:就左指针与右指针交换即可

代码:

void swap(char *a, char *b) {
    char t = *a;
    *a = *b, *b = t;
}
void reverseString(char* s, int sSize){

    int left=0,right=sSize-1;
    while(left<right)
    {
        swap(s + left, s + right);
        left++;
        right--;
    }
        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

557. 反转字符串中的单词 III

思路:难点就在于寻找每一个单词

代码:

void swap(char *a,char *b)
{
    char tmp=*a;
    *a=*b;
    *b=tmp;
}
void revers(char *arr,int begin,int end)
{
    while(begin<end)
    {
        swap(arr+begin,arr+end);
        begin++;
        end--;
    }
}
char * reverseWords(char * s){
int begin=0;
int last=0;
int len=strlen(s);
while(last<=len)
{
    while(s[begin]==' ')
    {
        begin++;
    }
    while(s[last]!=' '&&s[last]!='\0')
    {
        last++;
    }
    revers(s,begin,last-1);
    if(s[last]=='\0')
    {
        break;
    }
    begin=last+1;
    last+=1;
}
return s;
}
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

第五天双指针

876. 链表的中间结点

思路:一个快指针一次走两步(最后一次可能走一步,因为两个中间节点的第二个),一个慢指针一次走一步,当快指针的next=null时,此时慢指针指向中间节点.

代码:

struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow=head;
struct ListNode*fast=head;
while(fast->next&&fast->next->next)
{
    fast=fast->next->next;
    slow=slow->next;
}

if(fast->next)
{
    slow=slow->next;
}
return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

19. 删除链表的倒数第 N 个结点

思路:找到该节点,删除即可.

代码:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode*fast=head;
    struct ListNode*guard=(struct ListNode*)malloc(sizeof( struct ListNode));
    int i=1;
    struct ListNode* slow=guard;
    slow->next=head;
    while(fast->next)
    {
        if(i>=n)
        {
            slow=slow->next;
        }
        i++;
        fast=fast->next;
    }
        struct ListNode*tmp=slow->next;
        slow->next=tmp->next;
        head=guard->next; 
        free(tmp);
        free(guard);
    return head;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第六天滑动窗口

567. 字符串的排列

思路:采用滑动窗口,判断窗口中的数量是否与s1相同

代码:

bool check(int s1_arr[],int s2_arr[])
{
    for(int i=0;i<26;i++)
    {
        if(s1_arr[i]!=s2_arr[i])
        {
            return false;
        }
    }

    return true;
}

bool checkInclusion(char * s1, char * s2){
    int n=strlen(s1);
    int m=strlen(s2);
    if(n>m)
    {
        return false;
    }
    
    
    int s1_arr[26];
    int s2_arr[26];
    memset(s1_arr,0,sizeof(s1_arr));
    memset(s2_arr,0,sizeof(s2_arr));
    for(int i=0;i<n;i++)
    {
        s1_arr[*(s1+i)-'a']++;
    }
    for(int i=0;i<n;i++)
    {
        s2_arr[*(s2+i)-'a']++;
    }
    if(check(s1_arr,s2_arr))
    {
        return true;
    }
    for(int i=n;i<m;i++)
    {
        s2_arr[*(s2+i)-'a']++;
        s2_arr[*(s2+i-n)-'a']--;
        if(check(s1_arr,s2_arr))
        {
            return true;
        }
    }

    return false;

}
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

3. 无重复字符的最长子串

思路:计算窗口的最大值即可

代码:

int lengthOfLongestSubstring(char * s){
    int left=0;
    int right=0;
    int max=0;
    int len=strlen(s);
    int j=0,i=0;
    int same=0;
    
    //for(int i=0;i
    while(right<len)
    {
        if(left<right)
        {
            //判断是否重复
            same=0;
            for(j=left;j<right;j++)
            {
                if(s[j]==s[right])
                {
                    same=1;
                    break;
                }
            }
            if(same)
            left=j+1;
        }
        max=max>(right-left+1)?max:(right-left+1);
        right++;
    }
    return max;
}
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

第七天广度优先搜索 / 深度优先搜索

733. 图像渲染

思路:先修改最初的起点,再在修改起点上下左右的点,再然后再把四个点都作为起点,依次进行.

代码:

void dfs(int **image,int color,int curcolor,int row,int col,int sr,int sc)
{
    if(sr<row&&sr>=0&&sc<col&&sc>=0)
    {
     if(image[sr][sc]==curcolor)
     {
         image[sr][sc]=color;
         dfs(image,color,curcolor,row,col,sr-1,sc);
         dfs(image,color,curcolor,row,col,sr+1,sc);
         dfs(image,color,curcolor,row,col,sr,sc-1);
         dfs(image,color,curcolor,row,col,sr,sc+1);
         
     }   
    }
        return ;
}


int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes){
    int row =imageSize;
    int col=imageColSize[0];
    
    
    //行数
    *returnSize=row;
    //列数
    *returnColumnSizes=(int *)malloc(sizeof(int)*row);
    for(int i=0;i<row;i++)
    {
        (*returnColumnSizes)[i]=col;
    }

    int curcolor=image[sr][sc];
    if(curcolor!=color)
    {
        dfs(image,color,curcolor,row,col,sr,sc);
    }
 
    return image;
}
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

695. 岛屿的最大面积

思路:深度递归即可,每次遍历到1就修改为0.选出最大值即可

代码:

int dfs(int **grid,int gr,int gc,int row, int col)
{
    if(gr<row&&gr>=0&&gc<col&&gc>=0)
    {
        if(grid[gr][gc]==1)
        {
            grid[gr][gc]=0;
            int tmp1=dfs(grid,gr-1,gc,row,col);
            int tmp2=dfs(grid,gr+1,gc,row,col);
            int tmp3=dfs(grid,gr,gc-1,row,col);
            int tmp4=dfs(grid,gr,gc+1,row,col);
            return 1+tmp1+tmp2+tmp3+tmp4;
        }
        else
        {
            return 0;
        }
    }

    return 0;
}

int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    int max=0;
    int row=gridSize;
    int col=*gridColSize;
    for(int i=0;i<gridSize;i++)
    {
        for(int j=0;j<*gridColSize;j++)
        {
            if(grid[i][j]==1)
            {
                int tmp = dfs(grid,i,j,row,col);
                max=max>tmp?max:tmp;
            }
        }
    }
    return max;
}
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

第八天广度优先搜索 / 深度优先搜索

617. 合并二叉树

思路:遍历每一个节点即可.

代码:

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
     if(!root1&&!root2)
     {
         return NULL;
     }
     if(!root1)
     {
         return root2;
     }
     if(!root2)
     {
         return root1;
     }
     
     
    struct TreeNode* head=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    head->val=root1->val+root2->val;
    head->left= mergeTrees(root1->left,root2->left);
    head->right= mergeTrees(root1->right,root2->right);
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

116. 填充每个节点的下一个右侧节点指针

思路:根据图可以理解,最难的部分是判断5->6,使用 if(root->next&&root->right) root->right->next=root->next->left;即可解决.

代码:

// void connectTwoNode (struct Node* a, struct Node* b){
//     if (a == NULL || b == NULL) 
//     return;
//     a->next = b;
//     connectTwoNode(a->left,a->right);  //连接a子树的左右结点
//     connectTwoNode(b->left,b->right);  //连接b子树的左右结点
//     connectTwoNode(a->right,b->left);  //连接相邻子树的相邻结点
// }
struct Node* connect(struct Node* root) {
    if (root == NULL||root->left==NULL) 
    return root;
    root->left->next=root->right;
    if(root->next&&root->right)
    {
        root->right->next=root->next->left;
    }
    root->left=connect(root->left);
    root->right=connect(root->right);
    //connectTwoNode(root->left,root->right);
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第九天广度优先搜索 / 深度优先搜索

542. 01 矩阵

思路:这题代码写不出来参考https://leetcode.cn/problems/01-matrix/solution/54201ju-zhen-zhong-deng-cyu-yan-dfsjie-f-r8gt/

代码:

 #define MIN(a,b)(a<b?a:b)

int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes){
*returnSize=matSize;
int** ans=(int**)malloc(matSize*sizeof(int*));
(*returnColumnSizes)=(int*)malloc(sizeof(int*)*matSize);
//给returnC0lmunSizes分配空间，因为matrixSize代表行数，而ColumnSizes数组个数就是行数
memcpy(*returnColumnSizes,matColSize,matSize*sizeof(int));

//定义ans(返回数组)
for(int i=0;i<matSize;i++){
    ans[i]=(int*)calloc(matColSize[0],sizeof(int));
//i代表行，每行分配matrixColSize[i]这么多空间并初始化0，dp已经建立完毕
    for(int j=0;j<matColSize[i];j++){
        if(mat[i][j]!=0)
        ans[i][j]=9999;
//9999是最大的数，在测试用例中体现，需要返回9999
    }
    
}
//比较自己左边的上面的邻接元素，如果是0，就会因为自身和（0+1）比较而直接返回1不然则会根据对方带的数（代表了对方距离最近的0多远）和自身比较
for(int x=0;x<matSize;x++){
    for(int y=0;y<matColSize[0];y++){
        if(x-1>=0)
        ans[x][y]=MIN(ans[x][y],ans[x-1][y]+1);
        if(y-1>=0)
        ans[x][y]=MIN(ans[x][y],ans[x][y-1]+1);
    }
}
//第二次遍历比较自己下面和右边的邻接元素，同理，就可以得出自己上下左右最接近0的方位并确定那个数。
for(int x=matSize-1;x>=0;x--){
    for(int y=matColSize[x]-1;y>=0;y--){
        if(x+1<matSize)
        ans[x][y]=MIN(ans[x][y],ans[x+1][y]+1);
        if(y+1<matColSize[x])
        ans[x][y]=MIN(ans[x][y],ans[x][y+1]+1);
    }
}

return ans;
}

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

994. 腐烂的橘子

思路:这题代码也写不出, 参考https://leetcode.cn/problems/rotting-oranges/solution/by-nirvana-10-djc3/

代码:


#define MAX 100
// 判断给定行列号是否在grid中
bool IsInArea(int row, int col, int rowSize, int colSize)
{
    // printf("row = %d, col = %d\n", row, col);
    if (row >= 0 && row < rowSize && col >= 0 && col < colSize) {
        return true;
    }
    return false;
}

int orangesRotting(int** grid, int gridSize, int* gridColSize){
    // 申请一个与输入矩阵等大的矩阵辅助存储最小分钟数，初始化为-1，表示未腐烂
    int **dis = (int **)malloc(sizeof(int *) * gridSize);
    for (int i = 0; i < gridSize; i++) {
        dis[i] = (int *)malloc(sizeof(int) * gridColSize[i]);
        for (int j = 0; j < gridColSize[i]; j++) {
            dis[i][j] = -1;
        }
    }

    // 申请一个辅助队列
    int **q = (int **)malloc(sizeof(int *) * MAX);
    for (int i = 0; i < MAX; i++) {
        q[i] = (int *)malloc(sizeof(int) * 2);
    }
    int front = 0;
    int rear = 0;

    // 初始腐烂的橘子入队，顺便新鲜橘子完成计数
    int freshCnt = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[i]; j++) {
            if (grid[i][j] == 2) {
                q[rear][0] = i;
                q[rear][1] = j;
                rear++;
                // 已腐烂的橘子，腐烂时间为0
                dis[i][j] = 0;
            } else if (grid[i][j] == 1) {
                // 算出新鲜橘子总数
                freshCnt++;
            }
        }
    }

    // 广度优先搜索
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int ans = 0;
    while (front < rear) {
        // 逐个出队腐烂橘子，对它的上下左右方向考查
        int r = q[front][0];
        int c = q[front][1];
        front++;
        for (int i = 0; i < 4; i++) {
            int x = r + dir[i][0];
            int y = c + dir[i][1];
            // 如果这个方向上下标越界，或者橘子已经腐烂，或者是空单元格，无需考查，看下一个方向
            if (IsInArea(x, y, gridSize, gridColSize[0]) == false || dis[x][y] >= 0 || grid[x][y] == 0) {
                continue;
            }
            // 如果这个方向上是新鲜橘子，那么它将被传染腐烂
            dis[x][y] = dis[r][c] + 1;  // 记录在第几分钟被传染腐烂，即上一橘子被腐烂的时间+1
            // 记录当前分钟数，如果此时已全部腐烂，那么它就是最短时间
            ans = dis[x][y];
            // 将被腐烂的橘子入队，它将是下一轮的传染源
            q[rear][0] = x;
            q[rear][1] = y;
            rear++;
            // 剩余新鲜橘子数量减1
            freshCnt--;
            // 如果新鲜橘子都没了，说明已全被腐烂，无需再看下去了
            if (freshCnt == 0) {
                break;
            }
        }
    }

    // 释放辅助队列内存
    for (int i = 0; i < MAX; i++) {
        free(q[i]);
    }
    free(q);

    for (int i = 0; i < gridSize; i++) {
        free(dis[i]);
    }
    free(dis);    

    // 如果还剩下有新鲜橘子，表明不可能腐烂掉所有橘子，否则返回被腐烂时间
    if (freshCnt > 0) {
        return -1;
    } else {
        return ans;
    }
}


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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

第十天递归 / 回溯

21. 合并两个有序链表

思路:归并思想,每次取两个对比.排序

代码:

struct ListNode* mergeTwoLists1(struct ListNode* list1, struct ListNode* list2,struct ListNode*tmp)
{
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    if(list1->val<list2->val)
    {
        tmp=list1;
        tmp->next=mergeTwoLists1(list1->next,list2,tmp->next);
    }
    else
    {
        tmp=list2;
        tmp->next=mergeTwoLists1(list1,list2->next,tmp->next);
    }
    return tmp;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  struct ListNode*guard=(struct ListNode*)malloc(sizeof(struct ListNode));
  guard->next=NULL; 
  struct ListNode*tmp=guard;
  tmp->next=mergeTwoLists1(list1,list2,tmp->next);
  tmp=guard->next;
  free(guard);
  return tmp;
}
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

206. 反转链表

思路:每次进行一个尾插尾删即可.

代码:


struct ListNode* reverseList(struct ListNode* head){
struct ListNode*tmp=head,*tail;;
if(tmp==NULL||tmp->next==NULL)
{
    return head;
}
struct ListNode *guard=(struct ListNode *)malloc(sizeof(struct ListNode));
guard->next=NULL;
tail=guard->next;
while(tmp!=NULL)
{
tail=tmp;
tmp=tmp->next;
tail->next=guard->next;
guard->next=tail;
}
head=guard->next;
free(guard);
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第十一天递归 / 回溯

77. 组合

思路:参考官方 :https://leetcode.cn/problems/combinations/solution/zu-he-by-leetcode-solution/

代码:

int* temp;
int tempSize;

int** ans;
int ansSize;

void dfs(int cur, int n, int k) {
    // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
    if (tempSize + (n - cur + 1) < k) {
        return;
    }
    // 记录合法的答案
    if (tempSize == k) {
        int* tmp = malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++) {
            tmp[i] = temp[i];
        }
        ans[ansSize++] = tmp;
        return;
    }
    // 考虑选择当前位置
    temp[tempSize++] = cur;
    dfs(cur + 1, n, k);
    tempSize--;
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    temp = malloc(sizeof(int) * k);
    ans = malloc(sizeof(int*) * 10001);
    tempSize = ansSize = 0;
    dfs(1, n, k);
    *returnSize = ansSize;
    *returnColumnSizes = malloc(sizeof(int) * ansSize);
    for (int i = 0; i < ansSize; i++) {
        (*returnColumnSizes)[i] = k;
    }
    return ans;
}



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

784. 字母大小写全排列

思路:参考代码 https://leetcode.cn/problems/letter-case-permutation/solution/c-by-eeeugene-0i5o/

代码:


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** letterCasePermutation(char * s, int* returnSize){
    /*创建长度，开辟ret空间*/
    int len = strlen(s);
    char **ret = malloc(sizeof(char *)* pow(2,len));
    ret[0] = malloc(sizeof(char) * len + 1);
    /*将s复制进去，第一个肯定为答案*/
    strcpy(ret[0],s);
    int i,j,k;
    int size = 1;
    for(i = 0;i < len;i++){
        k = size;
        /*如果是字母的话*/
        if(isalpha(s[i])){
            /*k为行数，j用来控制移动到下行*/
            for(j = 0;j < k;j++){
                ret[k + j] = malloc(sizeof(char) * (len+1));
                /*基于j - j+k行，每次只改变一个字符*/
                strcpy(ret[j + k],ret[j]);  
                /*如果是小写，转换大写，反之小写*/
                ret[k + j][i] = (isupper(s[i]) != 0) ? s[i] + 32 : s[i] - 32;
                size++;
            }
        }
    }
    *returnSize = size;
    return ret;
}


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

46. 全排列

思路:参考代码:https://leetcode.cn/problems/permutations/solution/quan-pai-lie-cyu-yan-xiang-jie-chao-ji-x-pywy/

代码:

void swap(int * nums,int indexA,int indexB)
{
    int temp    = nums[indexA];
    nums[indexA]= nums[indexB];
    nums[indexB]= temp;
}

void prem(int* nums, int numsSize, int* returnSize, int** returnColumnSizes,int** returnNums,int offset)
{
    if(offset == numsSize)
    {
        //遍历到末尾了
        //申请returnNums
        returnNums[*returnSize] = (int *)malloc(sizeof(int ) * numsSize);
        //拷贝内容到returnNums
        memcpy(returnNums[*returnSize],nums,sizeof(int) * numsSize );
        //记录当前拷贝内容的长度
        (*returnColumnSizes)[*returnSize] = numsSize;
        *returnSize = *returnSize + 1;

    }
    else
    {

        //回溯算法的核心
        int i;
        for(i = offset; i < numsSize; i++)
        {
            swap(nums,i,offset);//i 和 offset 交换
            prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,offset+1);
            swap(nums,i,offset);//i 和 offset 交换
        }
    }
}


int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    //不重复的数字的全排序
    //组合次数为 n！= n *( n - 1) *( n - 2) ...... 2 * 1
    //这样的方法适合回溯的方法
    //取值范围1 <= nums.length <= 6  = 6 * 5 * 4 * 3 *2 * 1 = 720中可能
    int **returnNums = (int **)malloc(sizeof(int *) * 721);
    *returnColumnSizes= (int *)malloc(sizeof(int ) * 721);
    *returnSize = 0;
    prem(nums,numsSize,returnSize,returnColumnSizes,returnNums,0);
    return returnNums;

}



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

第十二天动态规划

70. 爬楼梯

思路:爬一节楼梯方法数1 爬两节楼梯方法数2,爬3=爬1+爬2, 爬4=爬2+爬3;以此类推

代码:

int climbStairs(int n){
if(n==1)
{
    return 1;
}
if(n==2)
{
    return 2;
}

int a=1;
int b=2;
int sum=0;
while(n>2)
{
   sum=a+b;
   a=b;
   b=sum;
   n--;
}
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

120. 三角形最小路径和

思路:最小路径和,即每次选最小的值即可

举例:

每次选两个数中的最小值,加到上一行,依次进行,最顶层的数一定是最小数.

代码:

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){
    for(int i=0;i<triangleSize;i++)
    {
        triangleColSize[i]=i+1;
    }
    int *answer=(int *)malloc(sizeof(int)*triangleSize);
    for(int i=0;i<triangleSize;i++)
    {
        answer[i]=triangle[triangleSize-1][i];
    }
    for(int i=triangleSize-1-1;i>=0;i--)
    {
        for(int j=0;j<triangleColSize[i];j++)
        {
            answer[j]=answer[j]<answer[j+1]?triangle[i][j]+answer[j]:triangle[i][j]+answer[j+1];
        }
    }
    return answer[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第十三天位运算

231. 2 的幂

思路:如果是2的次方数,则2进制序列中一定只有一个1,判断1的个数即可.

代码:

bool isPowerOfTwo(int n){
    if(n<=0)
    {
        return false;
    }
        int count=0;
        while(n)
        {
            n=n&(n-1);
            count++;
        }
        if(count==1)
        {
            return true;
        }
        return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

191. 位1的个数

思路:特殊解法: n&(n-1)的次数即为1的个数.

代码:

int hammingWeight(uint32_t n) {
    int count=0;
    while(n)
    {
        n=n&(n-1);
        count++;
    }
    return count;
}
1
2
3
4
5
6
7
8
9

第十四天位运算

190. 颠倒二进制位

思路:分治思想,一次分为两部分进行倒置.

代码:

const uint32_t M1 = 0x55555555;  // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333;  // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f;  // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff;  // 00000000111111110000000011111111

uint32_t reverseBits(uint32_t n) {
    n = n >> 1 & M1 | (n & M1) << 1;
    n = n >> 2 & M2 | (n & M2) << 2;
    n = n >> 4 & M4 | (n & M4) << 4;
    n = n >> 8 & M8 | (n & M8) << 8;
    return n >> 16 | n << 16;
}
1
2
3
4
5
6
7
8
9
10
11
12

136. 只出现一次的数字

思路:两个相同的按位异或=0;

代码:

int singleNumber(int* nums, int numsSize){
    int a=nums[0];
    for(int j=1;j<numsSize;j++)
    {
        a=a^nums[j];
    }
    return a;
}
1
2
3
4
5
6
7
8

95041221e6.png)

思路:特殊解法: n&(n-1)的次数即为1的个数.

代码:

int hammingWeight(uint32_t n) {
    int count=0;
    while(n)
    {
        n=n&(n-1);
        count++;
    }
    return count;
}
1
2
3
4
5
6
7
8
9

第十四天位运算

190. 颠倒二进制位

思路:分治思想,一次分为两部分进行倒置.

代码:

const uint32_t M1 = 0x55555555;  // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333;  // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f;  // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff;  // 00000000111111110000000011111111

uint32_t reverseBits(uint32_t n) {
    n = n >> 1 & M1 | (n & M1) << 1;
    n = n >> 2 & M2 | (n & M2) << 2;
    n = n >> 4 & M4 | (n & M4) << 4;
    n = n >> 8 & M8 | (n & M8) << 8;
    return n >> 16 | n << 16;
}
1
2
3
4
5
6
7
8
9
10
11
12

136. 只出现一次的数字

思路:两个相同的按位异或=0;

代码:

int singleNumber(int* nums, int numsSize){
    int a=nums[0];
    for(int j=1;j<numsSize;j++)
    {
        a=a^nums[j];
    }
    return a;
}
1
2
3
4
5
6
7
8

第九天,第十天的代码没有写出来,等下一次补一篇博客思路与代码. 欢迎各位博主多多点评,希望各位大佬提出给优秀的建议或思路.

相关阅读:
MyCat主从数据库集群搭建
 font-spider 压缩字体使用
 Python | Leetcode Python题解之第51题N皇后
 泰勒展开式
 使用Consul建立docker集群
 SpringCloud学习笔记（一）
web前端面试题附答案003-说一下你都用过那些格式的图片
 JAVAEE框架技术之17之SSM综合案例角色管理
 坚持与努力的背后：从校园到职场，我选择奋斗
 Nmap端口服务之 CentOS7 关于启动Apache(httpd)服务、telnet服务、smtp服务、ftp服务、sftp服务
原文地址：https://blog.csdn.net/gemgod/article/details/126880593

leetcode 14天算法入门 C语言实现

文章目录