碎碎念

碎碎念

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//qsort 要 #include <stdlib.h>
//sort 函数：
int cmp(const void *a, const void *b){
  return *(int *)a-*(int *)b;
}
//升序
qsort(nums, numsSize, sizeof(int), cmp);

//初始化
memset(void *ptr, int value, size_t num);
//ptr：要设置的内存起始地址
//value：要填充的字节值（只取低 8 位）
//num：要填充的字节数

1
abs(); //绝对值函数
1
map[128]={0} //数组初始化
1
2
#include <limits.h>
int max=INT_MAX
1
2
3
4
5
6
7
8
9
//求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

头文件记得总结

机试时记得审题孩子们，题目给的用例描述略微模糊，一不注意就坠机了

不要轻易修改题目传进来的参数，万一又被 const 坑了呢

考虑数字为 0 或者负数的情况

c语言位运算异或：a^b；

int *A=*(int **a);犯这种错误还是人类吗？

报错反思

  • 有没有错把索引当做值？

  • 判断相等有没有用双等于？

  • 大括号是否少了一半？

  • 结构体定义顺序？

  • 空指针？

  • 字符串记得最后要有‘\0’

  • 变量是否忘了初始化？

  • 别不舍得用大括号，改着改着成多行了，最后又忘了加。

  • 有些时候是要赋值字符，别搞成数字了，记得加单引号

  • long long 的 max 函数记得把返回值和参数也都写成 long long

字符串

  1. strcpy(s1, s2);
    复制字符串 s2 到字符串 s1。

  2. strcat(s1, s2);
    连接字符串 s2 到字符串 s1 的末尾。

  3. strlen(s1);
    返回字符串 s1 的长度。

  4. strcmp(s1, s2);
    如果 s1 和 s2 是相同的，则返回 0；如果 s1<s2 则返回小于 0；如果 s1>s2 则返回大于 0。

  5. strchr(s1, ch);
    返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置。

  6. strstr(s1, s2);
    返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置。

字符赋值\0要加单引号，字符串加双引号。

一、数组

1.移出元素

思路：快慢指针

1
2
3
4
5
6
7
8
9
10
int removeElement(int* nums, int numsSize, int val) {
    int slow=0;
    for(int i=0;i<numsSize;i++){
        if(nums[i]!=val){
            nums[slow]=nums[i];
            slow++;
        }
    }
    return slow;
}

2.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

思路：滑动窗口吧，自己写的，不赖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minSubArrayLen(int target, int* nums, int numsSize) {
    //左闭右开
    int left=0,right=0,sum=0,min=INT_MAX;
    while(left<numsSize){
        while(sum<target&&right<numsSize)
            sum+=nums[right++];
        if(sum>=target)
            min=min<=right-left?min:right-left;
        sum-=nums[left++];

    }
    if(min==INT_MAX)
        return 0;
    return min;
}

3.螺旋矩阵II

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

思路：好像写过一个类似的，反正有点像削平果，一直转就行了。

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
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    int top=0,down=n-1,left=0,right=n-1;
    int **result=malloc(sizeof(int *)*n);
    for(int j=0;j<n;j++)
        result[j]=malloc(sizeof(int)*n);

    int i=1;
    while(i<=n*n){
        //上
        for(int j=left;j<=right;j++){
            result[top][j]=i;
            i++;
        }
        top++;
        //右
        for(int j=top;j<=down;j++){
            result[j][right]=i;
            i++;
        }
        right--;
        //下
        for(int j=right;j>=left;j--){
            result[down][j]=i;
            i++;
        }
        down--;
        //左
        for(int j=down;j>=top;j--){
            result[j][left]=i;
            i++;
        }
        left++;
    }

    *returnSize=n;
    *returnColumnSizes=malloc(sizeof(int)*n);
    for(int j=0;j<n;j++)
        (*returnColumnSizes)[j]=n;
    return result;
}

二、字符串

1.反转字符串

1
2
3
4
5
6
7
8
void reverseString(char* s, int sSize) {
    char temp;
    for(int i=0;i<sSize/2;i++){
        temp=s[i];
        s[i]=s[sSize-1-i];
        s[sSize-1-i]=temp;
    }
}

2.反转字符串II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void reverse(char s[],int start,int end){
    int len=end-start+1;
    char temp;
    for(int i=0;i<len/2;i++){
        temp=s[start+i];
        s[start+i]=s[end-i];
        s[end-i]=temp;
    }
}
char* reverseStr(char* s, int k) {
    int len=strlen(s);
    int round=len/(2*k);
    int rest=len%(2*k);
    for(int i=0;i<round;i++)
        reverse(s,i*2*k,i*2*k+k-1);
    if(rest==0)
        return s;
    else if(rest>k)
        reverse(s,round*2*k,round*2*k+k-1);
    else
        reverse(s,round*2*k,len-1);
    return s;
}

3.翻转字符串里的单词

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

题解：好题，快慢指针去除多余空格，两次翻转得到结果。注意字符串终止符的处理。

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
//去除多余空格
int removeExtraSpaces(char s[]){
    int slow=0,len=strlen(s);
    for(int i=0;i<len;i++){
        if(s[i]!=' '){//遇到非空格就处理，即删除所有空格。
            if(slow!=0)//手动控制空格，给单词之间添加空格。
                s[slow++]=' ';
            while(i<len&&s[i]!=' ')
                s[slow++]=s[i++];
        }
    }
    s[slow] = '\0';//补上终止符
    return slow;
}

//反转字符串
void reverse(char s[], int start,int end){
    int len=end-start+1;
    char temp;
    for(int i=0;i<len/2;i++){
        temp=s[start+i];
        s[start+i]=s[end-i];
        s[end-i]=temp;
    }
}
char* reverseWords(char* s) {
    //记录新的len用于截断末尾的多余空格
    int len=removeExtraSpaces(s);
    printf("len=%d",len);
    char* result=malloc(sizeof(char)*len+1);//+1 放终止符
    for(int i=0;i<len;i++)
        result[i]=s[i];
    result[len]='\0';
    //整体翻转
    reverse(result,0,len-1);
    //单词翻转
    int start=0,end;
    for(int i=0;i<len;i++){
        if(result[i]==' '){
            end=i-1;
            reverse(result,start,end);
            start=i+1;
        }
    }
    reverse(result,start,len-1);
    return result;
}

4.重复的子字符串

题解：简单又不简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool repeatedSubstringPattern(char* s) {
    int len=strlen(s),flag=0;
    for(int i=0;i<len/2;i++){
        //整数倍才有可能符合条件
        if(len%(i+1)==0){
            int j=i+1;
            flag=0;
            while(j<len&&flag==0){
                if(s[j]!=s[j%(i+1)])//取余比较
                    flag=1;
                j++;
            }
            if(flag==0)
                return true;
        }
    }
    return false;
}

5.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。

  • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。

  • 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

题解1：记录一下自己手搓的暴力大法，虽然超时了，只通过113 / 128 个样例，但还是辛苦自己了。

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
bool equal(char* s, char* t){
    int lens=strlen(s);
    int lent=strlen(t);
    //长度不同直接返回false
    if(lens!=lent)
        return false;
    int hash1[26]={0};
    int hash2[26]={0};
    for(int i=0;i<lens;i++)
        hash1[s[i]-'a']++;
    for(int i=0;i<lent;i++)
        hash2[t[i]-'a']++;
    for(int i=0;i<26;i++){
        if(hash1[i]!=hash2[i])
            return false;
    }
    return true;
}
//判断是否全为true
bool over(bool *flag, int len){
    for(int i=0;i<len;i++){
        if(flag[i]==false)
            return false;
    }
    return true;
}

char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    char ***result=malloc(sizeof(char**)*strsSize);
    int resultTop=0;
    int pathTop;//记录一组的字符串数量
    int *length=malloc(sizeof(int)*strsSize);//记录每组的字符串数量
    bool *flag=malloc(sizeof(bool)*strsSize);
    for(int i=0;i<strsSize;i++)
        flag[i]=false;

    while(!over(flag,strsSize)){
        pathTop=0;
        //找到第一个还未处理的字符串index
        int index=0;
        while(flag[index])
            index++;
        result[resultTop]=malloc(sizeof(char*)*strsSize);
        char *temp=malloc(sizeof(char)*(strlen(strs[index])+1));
        strcpy(temp,strs[index]);
        result[resultTop][pathTop++]=temp;
        flag[index]=true;
        
        //把后续所有一样的全取出
        for(int i=index+1;i<strsSize;i++){
            //如果为true则没必要看了
            if(flag[i]==false&&equal(result[resultTop][0],strs[i])){
                char *temp=malloc(sizeof(char)*(strlen(strs[i])+1));
                strcpy(temp,strs[i]);
                result[resultTop][pathTop++]=temp;
                flag[i]=true;
            }
        }
        //长度存入并使resultTop++
        length[resultTop++]=pathTop;
    }

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];

    return result;
}

题解2：每个字符串排序后作为 key，再整体排序分组。看了遍答案，自己写一遍过。

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
typedef struct{
    char *str;
    char *key;
} node;

//排序字符
int cmpchar(const void* a, const void* b){
    return *(char*)a-*(char*)b;
}

//排序节点
int cmpnode(const void* a, const void* b){
    node* x=(node*)a;
    node* y=(node*)b;
    return strcmp(x->key,y->key);
}

//拷贝字符串
char* copystring(char *s){
    char *temp=malloc(sizeof(char)*(strlen(s)+1));
    strcpy(temp,s);
    return temp;
}

char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    node *nodes=malloc(sizeof(node)*strsSize);
    for(int i=0;i<strsSize;i++){
        nodes[i].str=copystring(strs[i]);
        nodes[i].key=copystring(strs[i]);
        //排序得到key
        qsort(nodes[i].key,strlen(nodes[i].key),sizeof(char),cmpchar);
    }
    //排序node节点
    qsort(nodes,strsSize,sizeof(node),cmpnode);

    char ***result=malloc(sizeof(char**)*strsSize);
    int resultTop=0;
    char **path=malloc(sizeof(char*)*strsSize);
    int pathTop;
    int *lens=malloc(sizeof(int)*strsSize);//记录每一组的长度

    int index=0;
    while(index<strsSize){
        pathTop=0;
        path[pathTop++]=copystring(nodes[index++].str);
        //如果下一个key相同，继续加入
        while(index<strsSize&&
            strcmp(nodes[index].key,nodes[index-1].key)==0){
                path[pathTop++]=copystring(nodes[index++].str);
        }
        //存储path
        char **temp=malloc(sizeof(char*)*pathTop);
        for(int i=0;i<pathTop;i++)
            temp[i]=path[i];
        result[resultTop]=temp;
        lens[resultTop++]=pathTop;
    }

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++){
        (*returnColumnSizes)[i]=lens[i];
    }
    return result;
}

.

二、回溯算法

核心思想：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

回溯算法模板：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

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
25
26
27
28
29
30
31
32
33
34
35
36
//全局变量
int *path;
int pathTop;
int **result;
int resultTop;
void backtracking(int n,int k,int start){
    if(pathTop==k){
        int *temp=malloc(sizeof(int)*k);
        for(int i=0;i<k;i++)
            temp[i]=path[i];
        result[resultTop++]=temp;
        return;
    }
    //j可以取到n
    for(int j=start;j<=n;j++){
        path[pathTop++]=j;
        backtracking(n,k,j+1);
        //进行回溯，将数组最上层结点弹出
        pathTop--;
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    result=malloc(sizeof(int *)*1000000);
    path=malloc(sizeof(int)*k);
    pathTop=0;
    resultTop=0;
	//从1开始
    backtracking(n,k,1);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*(*returnSize));
    for(int i=0;i<*returnSize;i++)
        (*returnColumnSizes)[i]=k;
    return result;
}

2.组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

题解：多维护一个sum变量，9是定死的。默写板子一遍过，芜湖~

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
int sum;
int *path;
int pathTop;
int **result;
int resultTop;

void backtracking(int n,int k,int start){
    if(pathTop==k){
        if(sum==n){
            int *temp=malloc(sizeof(int)*k);
            for(int i=0;i<k;i++)
                temp[i]=path[i];
            result[resultTop++]=temp;
        }
        return;
    }
    for(int i=start;i<=9;i++){
        path[pathTop++]=i;
        sum+=i;
        backtracking(n,k,i+1);
        pathTop--;
        sum-=i;
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
    result=malloc(sizeof(int*)*1000000);
    path=malloc(sizeof(int)*k);
    pathTop=0;
    resultTop=0;

    backtracking(n,k,1);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=k;

    return result;
}

3.电话号码的字母组合

题解：套板子，但好像又有点不一样。看一下c语言map是怎么写的。

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
char* path;
int pathTop;
char** result;
int resultTop;
char *letterMap[10]={
    "",//0
    "",//1
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
};

void backtracking(char *s,int index){
    int len=strlen(s);
    if(pathTop==len){
        char *temp=malloc(sizeof(char)*(len+1));
        for(int i=0;i<len;i++)
            temp[i]=path[i];
        temp[len]='\0';
        result[resultTop++]=temp;
        return;
    }

    int digit=s[index]-'0';//将字符转换为数字;

    for(int i=0;i<strlen(letterMap[digit]);i++){
        path[pathTop++]=letterMap[digit][i];
        backtracking(s,index+1);
        pathTop--;
    }

}
char** letterCombinations(char* digits, int* returnSize) {

    path=malloc(sizeof(char)*strlen(digits));
    result=malloc(sizeof(char*)*1000000);
    pathTop=0;
    resultTop=0;

    backtracking(digits,0);

    *returnSize=resultTop;
    return result;
}

4.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

题解：套板子一遍过，依旧需要使用start变量，不过 candidates 中的数字可以无限制重复被选取。

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
int *path;
int pathTop;
int **result;
int resultTop;
int sum;
int *length;//记录每一行的长度

void backtracking(int *candidates,int size,int target,int start){
    if(sum==target){
        int *temp=malloc(sizeof(int)*pathTop);
        for(int i=0;i<pathTop;i++)
            temp[i]=path[i];
        length[resultTop]=pathTop;
        result[resultTop++]=temp;
        return;
    }
    //剪枝
    if(sum>target){
        return;
    }
    for(int i=start;i<size;i++){
        path[pathTop++]=candidates[i];
        sum+=candidates[i];
        backtracking(candidates,size,target,i);
        pathTop--;
        sum-=candidates[i];
    }
}


int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*target);//最多target个数
    result=malloc(sizeof(int *)*1000000);
    length=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;
    sum=0;
    
    backtracking(candidates,candidatesSize,target,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];
    
    return result;
}

5.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

题解：相较于上一题，虽然candidates 中的每个数字只能使用一次，但是集和里面本身会有重复数字。要想办法去重。

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
int *path;
int pathTop;
int **result;
int resultTop;
int sum;
int *length;

void backtracking(int *candidates, int size, int target, int start){
    if(sum==target){
        int *temp=malloc(sizeof(int)*pathTop);
        for(int i=0;i<pathTop;i++)
            temp[i]=path[i];
        length[resultTop]=pathTop;
        result[resultTop++]=temp;
        return;
    }
    if(sum>target)
        return;
    for(int i=start;i<size;i++){
        //去重核心步骤
        if(i>start&&candidates[i]==candidates[i-1])
            continue;
        path[pathTop++]=candidates[i];
        sum+=candidates[i];
        
        backtracking(candidates,size,target,i+1);
        sum-=candidates[i];
        pathTop--;
    }
}

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

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*target);
    result=malloc(sizeof(int *)*1000000);
    pathTop=0;
    resultTop=0;
    sum=0;
    length=malloc(sizeof(int)*1000000);
    //排序，便于去重
    qsort(candidates,candidatesSize,sizeof(int),cmp);

    backtracking(candidates, candidatesSize, target,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];

    return result;
}

6.分割回文串

题解：吐了。三重指针处理字符串，太难了，屈服了，对着答案敲了。记得回来重新写一遍。

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
char **path;
char ***result;
int pathTop;
int resultTop;
int *length;//记录每一种分割方式分割为几个字符串

//将path中的字符串全部复制到result中
void copy(){
    char **temp=malloc(sizeof(char **)*pathTop);
    for(int i=0;i<pathTop;i++)
        temp[i]=path[i];
    result[resultTop]=temp;
    length[resultTop++]=pathTop;
}

//判断是否是回文串
bool isHW(char *s, int start, int end){
    while(start<=end){
        if(s[start++]!=s[end--])
            return false;
    }
    return true;
}

//切割从start到end的子字符串
char *cutString(char * s, int start,int end){
    char *temp=malloc(sizeof(char)*(end-start+2));
    for(int i=0;i<end-start+1;i++)
        temp[i]=s[start+i];
    temp[end-start+1]='\0';
    return temp;
}

void backtracking(char *s,int start){
    int len=strlen(s);
    if(start>=len){
        //将path复制到result中去
        copy();
        return;
    }

    for(int i=start;i<len;i++){
        //是回文就剪下来，否则就跳过
        if(isHW(s,start,i))
            path[pathTop++]=cutString(s,start,i);
        else
            continue;

        backtracking(s,i+1);

        pathTop--;
    }
}

char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
    int len=strlen(s);
    path=malloc(sizeof(char*)*len);
    result=malloc(sizeof(char**)*1000000);
    length=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;

    backtracking(s,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];
    return result;
}

7.复原IP地址

题解：哎呦，难死我了，憋出来上一道题，结果这题还是这么费劲。不过处理点号的思路不错。

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
char **result;
int resultTop;
int segment[3];

//判断是否有效
bool valid(char *s, int start,int end){
    //首个数字为零，无效
    if(end>start&&s[start]=='0'||end-start>2)
        return false;
    //最后一段如果没有字符，也无效
    if(start>end)
        return false;
    //不在0-255范围无效
    int sum=0;
    for(int i=start;i<=end;i++)
        sum=sum*10+(s[i]-'0');
    if(sum>=0&&sum<=255)
        return true;
    return false;
}

void backing(char *s, int start, int dotNum){
    int len=strlen(s);
    if(dotNum>=3){
        //如果最后一段有效
        if(valid(s,start,len-1)){
            char *temp=malloc(sizeof(char)*(len+4));
            int index=0;
            //对'.'的处理，很巧妙
            int num=0;//记录处理的是第几个'.'
            for(int i=0;i<len;i++){
                temp[index++]=s[i];
                if(num<3&&i==segment[num]){
                    temp[index++]='.';
                    num++;
                }
            }
            temp[len+3]='\0';
            result[resultTop++]=temp;
        }
        return;
    }

    for(int i=start;i<len&&i<start+3;i++){
        if(valid(s,start,i)){
            segment[dotNum]=i;
            backing(s,i+1,dotNum+1);
        }
    }
}

char** restoreIpAddresses(char* s, int* returnSize) {
    result=malloc(sizeof(char*)*1000000);
    resultTop=0;
    backing(s,0,0);
    *returnSize=resultTop;
    return result;
}

8.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

题解：好难好难，想不到。看了答案发现是要收集遍历树上的所有节点，所以改变一下收集的位置就行了。哎哎哎。

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
int *path;
int pathTop;
int **result;
int resultTop;
int *length;

void backing(int *nums, int numsSize,int start){
    //收集结果
    int *temp=malloc(sizeof(int)*pathTop);
    for(int i=0;i<pathTop;i++)
        temp[i]=path[i];
    length[resultTop]=pathTop;
    result[resultTop++]=temp;
    //终止条件
    if(start>=numsSize){
        return;
    }

    for(int i=start;i<numsSize;i++){
        path[pathTop++]=nums[i];
        backing(nums,numsSize,i+1);
        pathTop--;
    }
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*numsSize);
    result=malloc(sizeof(int*)*1000000);
    length=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;
    
    backing(nums,numsSize,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];
    return result;
}

9.子集II

题解：多了个去重，直接秒了。

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
int *path;
int **result;
int *length;
int pathTop;
int resultTop;

void backing(int *nums, int len, int start){
    //记录每个节点
    int *temp=malloc(sizeof(int)*len);
    for(int i=0;i<pathTop;i++)
        temp[i]=path[i];
    length[resultTop]=pathTop;
    result[resultTop++]=temp;

    if(start>=len)
        return;

    for(int i=start;i<len;i++){
        //去重
        if(i>start&&nums[i]==nums[i-1])
            continue;    
        path[pathTop++]=nums[i];
        backing(nums,len,i+1);
        pathTop--;
    }
}

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

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*numsSize);
    result=malloc(sizeof(int*)*1000000);
    length=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;
    qsort(nums,numsSize,sizeof(int),cmp);
    backing(nums,numsSize,0);
    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];
    return result;
}

10.非递减子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

  • 输入: [4, 6, 7, 7]

  • 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  • 给定数组的长度不会超过15。

  • 数组中的整数范围是 [-100,100]。

  • 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

题解：因为无法排序，所以需要借助used数组进行去重。注意这里的used数组只负责遍历树的一层。

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
int *path;
int **result;
int *length;
int pathTop;
int resultTop;

//判断是否符合条件
bool valid(int *nums,int len){
    if(len<2)
        return false;
    for(int i=1;i<len;i++){
        if(nums[i]<nums[i-1])
            return false;
    }
    return true;
}

//寻找used数组中是否存在某个数字
bool find(int *nums, int len, int k){
    for(int i=0;i<len;i++){
        if(nums[i]==k)
            return true;
    }
    return false;
}

void backing(int *nums, int len, int start){
    if(valid(path,pathTop)){
        int *temp=malloc(sizeof(int)*pathTop);
        for(int i=0;i<pathTop;i++)
            temp[i]=path[i];
        length[resultTop]=pathTop;
        result[resultTop++]=temp;
    }

    if(start>=len)
        return;
    
    //记录元素是否使用过
    int *used=malloc(sizeof(int)*len);
    int usedTop=0;

    for(int i=start;i<len;i++){
        //如果已经使用过，则跳过
        if(find(used,usedTop,nums[i]))
            continue;
        used[usedTop++]=nums[i];
        path[pathTop++]=nums[i];
        backing(nums,len,i+1);
        pathTop--;
    }
}
int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*numsSize);
    result=malloc(sizeof(int*)*1000000);
    length=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;

    backing(nums,numsSize,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=length[i];
    return result;
}

11.全排列

题解：简简单单去个重，不过这里的used数组和上一题不一样。

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
int *path;
int **result;
int pathTop;
int resultTop;
bool *used;

void backing(int *nums, int len){
    if(pathTop==len){
        int *temp=malloc(sizeof(int)*len);
        for(int i=0;i<len;i++)
            temp[i]=path[i];
        result[resultTop++]=temp;
        return;
    }

    for(int i=0;i<len;i++){
        if(used[i])
            continue;
        used[i]=1;
        path[pathTop++]=nums[i];
        backing(nums,len);
        used[i]=0;
        pathTop--;
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*numsSize);
    result=malloc(sizeof(int*)*1000000);
    pathTop=0;
    resultTop=0;
    used=malloc(sizeof(bool)*numsSize);
    for(int i=0;i<numsSize;i++)
        used[i]=0;

    backing(nums,numsSize);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=numsSize;
    return result;
}

12.全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

题解：依旧去重，但是没想出来。

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
int *path;
int **result;
int pathTop;
int resultTop;
bool *used;

void backing(int *nums, int len){
    if(pathTop>=len){
        int *temp=malloc(sizeof(int)*len);
        for(int i=0;i<len;i++)
            temp[i]=path[i];
        result[resultTop++]=temp;
        return;
    }
    for(int i=0;i<len;i++){
        if(used[i])
            continue;
        //去重方案，好好看，好好学
        if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)
            continue;
        used[i]=1;
        path[pathTop++]=nums[i];
        backing(nums,len);
        used[i]=0;
        pathTop--;
    }
}

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

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*numsSize);
    result=malloc(sizeof(int*)*1000000);
    pathTop=0;
    resultTop=0;
    used=malloc(sizeof(bool)*numsSize);
    for(int i=0;i<numsSize;i++)
        used[i]=0;
    qsort(nums,numsSize,sizeof(int),cmp);

    backing(nums,numsSize);

    *returnSize=resultTop;
    (*returnColumnSizes)=malloc(sizeof(int*)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=numsSize;
    return result;
}

13.N皇后

题解：复杂度爆炸，有时间优化一下。

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
char **map;
char ***result;
int resultTop;
int num_Q;

//判断是否符合条件
bool valid(char **map, int x, int y,int n){
    bool isQ;
    //检查行
    for(int i=0;i<y;i++){
        if(map[x][i]=='Q')
            return false;
    }
    //检查列
    for(int i=0;i<x;i++){
        if(map[i][y]=='Q')
            return false;
    }
    //检查左上角（想想为什么只要检查一个方向）
    for(int i=x,j=y;i>=0&&j>=0;i--,j--){
        if(map[i][j]=='Q')
            return false;
    }
    //检查右上角
    for(int i=x,j=y;i>=0&&j<n;i--,j++){
        if(map[i][j]=='Q')
            return false;
    }
    return true;
}

void backing(int n,int satrt){
    if(num_Q>=n){
        char **temp=malloc(sizeof(char*)*n);
        for(int i=0;i<n;i++){
            temp[i]=malloc(sizeof(char)*(n+1));
            for(int j=0;j<n;j++)
                temp[i][j]=map[i][j];
            temp[i][n]='\0';
        }
        result[resultTop++]=temp;
        return;
    }
    for(int i=satrt;i<n*n;i++){
        if(!valid(map,i/n,i%n,n))
            continue;
        map[i/n][i%n]='Q';
        num_Q++;
        backing(n,i+1);
        map[i/n][i%n]='.';
        num_Q--;
    }
}   

char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    num_Q=0;
    map=malloc(sizeof(char*)*n);
    for(int i=0;i<n;i++){
        map[i]=malloc(sizeof(char)*(n+1));
        for(int j=0;j<n;j++)
            map[i][j]='.';
        map[i][n] = '\0';
    }
    result=malloc(sizeof(char**)*1000000);
    resultTop=0;

    backing(n,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=n;
    return result;
}

14.字母大小写全排列

给定一个字符串 s ，通过将字符串 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
40
char** result;
int resultTop;

void back(char *s, int len, int start){
    printf("start=%d,len=%d\n",start,len);
    if(start>=len){
        char* temp=malloc(sizeof(char)*(len+1));
        for(int i=0;i<len;i++)
            temp[i]=s[i];
        temp[len]='\0';
        result[resultTop++]=temp;
        return;
    }
        
    if(s[start]>='0'&&s[start]<='9'){
        //数字也要记得继续向下调用
        back(s,len,start+1);
    }
    else if(s[start]>='A'&&s[start]<='Z'){
        back(s,len,start+1);
        s[start]=s[start]-'A'+'a'; 
        back(s,len,start+1);
    }
    else{
        //以小写和大写两种方式向下递归
        back(s,len,start+1);
        s[start]=s[start]-'a'+'A';
        back(s,len,start+1);       
    }
}

char** letterCasePermutation(char* s, int* returnSize) {
    result=malloc(sizeof(char*)*1000000);
    resultTop=0;
    int len=strlen(s);
    back(s,len,0);
    *returnSize=resultTop;
    printf("resultTop=%d",resultTop);
    return result;
}

15.等积子集的划分方案

给你一个整数数组 nums，其中包含的正整数 互不相同 ，另给你一个整数 target。

请判断是否可以将 nums 分成两个 非空、互不相交 的 子集 ，并且每个元素必须 恰好 属于 一个 子集，使得这两个子集中元素的乘积都等于 target。

如果存在这样的划分，返回 true；否则，返回 false。

子集 是数组中元素的一个选择集合。

题解：对于每一个元素，无非是分到子集1还是子集2的区别。

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
long long product1;//子集1的乘积
long long product2;//子集2的乘积
int flag;

void back(int* nums,int numsSize,long long target,int start){
    //如果已经找到有效的情况，则不需要继续查找了
    if(flag)
        return;
    //超过target可以直接停止了
    if(product1>target||product2>target)
        return;
    if(start==numsSize){
        if(product1==target&&product2==target){
            flag=true;
        }
        return;
    }
    //分给子集1
    product1*=nums[start];
    back(nums,numsSize,target,start+1);
    product1/=nums[start];
    //分给子集2
    product2*=nums[start];
    back(nums,numsSize,target,start+1);
    product2/=nums[start];
}

bool checkEqualPartitions(int* nums, int numsSize, long long target) {
    product1=1;
    product2=1;
    flag=0;
    back(nums,numsSize,target,0);
    return flag;
}

16.统计按位或能得到最大值的子集数目

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。

如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。

题解：依旧二进制枚举，记得恢复现场。

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
int max;
int counter;
int temp;

void back(int* nums,int numsSize,int start){
    if(start==numsSize){
        if(temp>max){
            max=temp;
            counter=1;
        }
        else if(temp==max){
            counter++;
        }
        return;
    }
    back(nums,numsSize,start+1);
    int old = temp;
    temp=temp|nums[start];
    back(nums,numsSize,start+1);
    temp=old;//恢复现场
}

int countMaxOrSubsets(int* nums, int numsSize) {
    max=0;
    counter=0;
    temp=0;
    back(nums,numsSize,0);
    return counter;
}

三、贪心算法

1.摆动序列

题解：直接看上坡下坡变了几次，很巧妙的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int wiggleMaxLength(int* nums, int numsSize) {
    if(numsSize==0)
        return 0;
    //flag记录上坡还是下坡
    int counter=1,flag=0;
    for(int i=1;i<numsSize;i++){
        if(nums[i]==nums[i-1])
            continue;
        else if(nums[i-1]<nums[i]){
            if(flag<=0){
                counter++;
                flag=1;
            }
        }
        else if(nums[i-1]>nums[i]){
            if(flag>=0){
                counter++;
                flag=-1;
            }
        }
    }
    return counter;
}

2.加油站问题

题解：从0开始累加前缀和，如果到i处和为负数，说明从0到i都不能作为起点，把start设置到i+1重新计算前缀和。只需遍历一遍数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int *res=malloc(gasSize*sizeof(int));
    for(int i=0;i<gasSize;i++)
        res[i]=gas[i]-cost[i];
    int total=0;
    for(int i=0;i<gasSize;i++)
        total+=res[i];
    //总前缀和小于0，说明不可能绕一圈
    if(total<0)
        return -1;    
    int start=0,sum=0;
    for(int i=0;i<gasSize;i++){
        sum+=res[i];
            if(sum<0){
                start=i+1;
                if(start==gasSize)
                    return -1;
                sum=0;
            }
    }
    return start;
}

为什么最后能确定是start呢？因为start到末尾是正，又因为前面验证了total为正，所以绕一圈的过程中不会出现负数的情况

3.分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。

  • 相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

题解：初始一人一个，从左到右检索一次，从右到左检索一次。代码简单，但思路感觉不好想啊。

1
2
3
4
5
6
7
8
for(int i=1;i<ratingsSize;i++){
    if(ratings[i]>ratings[i-1])
        candy[i]=candy[i-1]+1;
}
for(int i=ratingsSize-2;i>=0;i--){
    if(ratings[i]>ratings[i+1])
        candy[i]=candy[i+1]+1>candy[i]?candy[i+1]+1:candy[i];
}

4.柠檬水找零

五块，十块，二十块买水。

题解：easy，注意一下20块有两种找零方式就行。

5.根据身高重建队列

题解：看了一下提示还是很好想思路的，高个子的别把矮个子的当人就行了。就是哥们真看不懂c语言的二维指针啊，怎么玩的这玩意？

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
int cmp(const void* _a, const void* _b) {
    int *a = *(int**)_a, *b = *(int**)_b;
    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
    int **result=malloc(peopleSize*sizeof(int*));
    *returnSize=peopleSize;
    *returnColumnSizes=malloc(sizeof(int)*peopleSize);
    //初始化
    memset(*returnColumnSizes, 0, sizeof(int) * peopleSize);
    //排序
    qsort(people,peopleSize,sizeof(int *),cmp);
    int rank;
    for(int i=0;i<peopleSize;i++){
        rank=people[i][1];
        for(int j=0;j<peopleSize;j++){
            if((*returnColumnSizes)[j]==0&&rank==0){
                result[j]=malloc(sizeof(int)*2);
                result[j][0]=people[i][0];
                result[j][1]=people[i][1];
                (*returnColumnSizes)[j]=2;
                break;
            }
            else if((*returnColumnSizes)[j]==0&&rank!=0)
                rank--;
        }
    }
    return result;
}

6.用最少数量的箭引爆气球

题解：依旧对二维数组排序，会了板子之后就轻车熟路了。但是每加入一个气球就要重新维护一下end变量可能比较难想到。

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
int cmp(const void* a,const void* b){
    int *A=*(int **)a;
    int *B=*(int **)b;
    // return A[0]==B[0]?A[1]-B[1]:A[0]-B[0];
    //防止溢出
    if(A[0]==B[0]){
        if(A[1]>B[1])
            return 1;
        else if(A[1]<B[1])
            return -1;
        else
            return 0;
    }else{
        if(A[0]>B[0])
            return 1;
        else if(A[0]<B[0])
            return -1;
        else
            return 0;
    }
}
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    qsort(points,pointsSize,sizeof(int *),cmp);
    int end,index=0,rest=pointsSize,time=0;
    while(rest>0){
        end=points[index][1];
        while(index<pointsSize&&points[index][0]<=end){
            //加入新气球时候要重新维护end
            if(points[index][1]<end)
                end=points[index][1];
            index++;
            rest--;
        }
        time++;
    }
    return time;
}

7.无重叠区间

题解：上来忍不住先排个序先，然后思路类似上题，但是更新end还是比较难想。

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
int cmp(const void* a,const void* b){
    int *A=*(int **)a;
    int *B=*(int **)b;
    if(A[0]==B[0])
        return A[1]-B[1];
    return A[0]-B[0];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
    qsort(intervals,intervalsSize,sizeof(int *),cmp);
    int end=intervals[0][1],counter=0;
    for(int i=1;i<intervalsSize;i++){
        if(intervals[i][0]<end){
            counter++;
            //更新end为更小的那个
            if(end>intervals[i][1])
                end=intervals[i][1];
        }
        else{
            end=intervals[i][1];
        }

    }
    return counter;
}

8.划分字母区间

把字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

题解：关键是想要记录每个字母最后出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int* partitionLabels(char* s, int* returnSize) {
    //last记录每个字母最后出现的位置
    int last[128]={0},len=strlen(s);
    for(int i=0;i<len;i++)
        last[s[i]]=i;
    int start=0,end=0;
    int *result=malloc(sizeof(int)*len);
    *returnSize=0;
    //这里要用start做循环条件，之前用end死循环了
    while(start<len){
        end=last[s[start]];
        for(int i=start;i<=end;i++){
            if(end<last[s[i]])
                end=last[s[i]];
        }
        result[(*returnSize)++]=end-start+1;
        start=end+1;
    }
    return result;
}

9.合并区间

题解：做过前面几道题后思路很容易想到，但是二维数组的空间申请和赋值是真难处理啊，绕不过来了。

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
int cmp(const void *a,const void *b){
    int *A=*(int **)a;
    int *B=*(int **)b;
    if(A[0]==B[0])
        return A[1]-B[1];
    return A[0]-B[0];
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    qsort(intervals,intervalsSize,sizeof(int *),cmp);

    int **result=malloc(sizeof(int *)*intervalsSize);
    *returnSize=0;

    int start=intervals[0][0],end=intervals[0][1];
    for(int i=1;i<intervalsSize;i++){
        if(intervals[i][0]<=end){
            end=end>=intervals[i][1]?end:intervals[i][1];
        }
        else{
            result[*returnSize]=malloc(sizeof(int)*2);
            result[*returnSize][0]=start;
            result[*returnSize][1]=end;
            (*returnSize)++;
            start=intervals[i][0]; 
            end=intervals[i][1];
        }
    }
    //补上最后一个区间
    result[*returnSize]=malloc(sizeof(int)*2);
    result[*returnSize][0]=start;
    result[*returnSize][1]=end;
    (*returnSize)++;

    *returnColumnSizes=malloc(sizeof(int)*(*returnSize));
    for(int i=0;i<*returnSize;i++)
        (*returnColumnSizes)[i]=2;

    return result;
}

10.单调递增的数字

题解：从高位向低位检索半天想不明白，从低位向高位检索直接秒了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int monotoneIncreasingDigits(int n) {
    if(n<10)
        return n;
    int num=n,index=0;
    int *digits=malloc(sizeof(int)*10);
    while(num!=0){
        digits[index]=num%10;
        num=num/10;
        index++;
    }
    //从后向前遍历(从个位遍历到第二高位)
    for(int i=0;i<index-1;i++){
        if(digits[i]<digits[i+1]){
            digits[i+1]--;
            for(int j=0;j<=i;j++)
                digits[j]=9;
        }
    }
    num=0;
    for(int i=index-1;i>=0;i--){
        num=num*10+digits[i];
    }
    return num;
}

11.最长数对链

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。 现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。 找出并返回能够形成的 最长数对链的长度 。 你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

题解：这个和前面的合并区间不一样。贪心思路是每次选取右端点最小的数对，因此排序时只比较右端点即可。可以想一下为什么第一个数对一定会被选取。如果想从第 1 个数对开始遍历，也可以给 end 赋一个极小的初值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int cmp(const void* a, const void* b){
    int *A=*(int **)a,*B=*(int **)b;
    return A[1]-B[1];
}

int max(int a, int b){
    return a>=b?a:b;
}

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) {
    qsort(pairs,pairsSize,sizeof(int*),cmp);
    int end=pairs[0][1];
    int counter=1;
    for(int i=1;i<pairsSize;i++){
        if(pairs[i][0]>end){
            counter++;
            end=pairs[i][1];
        }
    }
    return counter;
}

四、动态规划

1.斐波那契数（非递归写法）

1
2
3
4
5
6
7
8
9
10
int fib(int n) {
    if(n<2)
        return n;
    int *dp=malloc(sizeof(int)*(n+1));
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++)
        dp[i]=dp[i-1]+dp[i-2];
    return dp[n];
}

2.不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

题解：想想怎么初始化。

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
//感觉官方题解给的初始化方案更简单
//vector<vector<int>> dp(m, vector<int>(n, 0));
//for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
//for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
    int m=obstacleGridSize,n=obstacleGridColSize[0];
    int **dp=malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++)
        dp[i]=malloc(sizeof(int)*n);
    for(int i=0;i<m;i++)
        dp[i][0]=0;
    for(int i=1;i<n;i++)
        dp[0][i]=0; 
    int i=0;//别贪那一下从1开始，如果(0,0)点也有障碍物会报错
    while(i<m&&obstacleGrid[i][0]==0)
        dp[i++][0]=1;
    i=0;
    while(i<n&&obstacleGrid[0][i]==0)
        dp[0][i++]=1;
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(obstacleGrid[i][j]==0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            else
                dp[i][j]=0;
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            printf("%d\t",dp[i][j]);
        }
        printf("\n");
    }
    return dp[m-1][n-1];
}

2.整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。返回可以获得的最大乘积。

题解：难点在于思考应该拆分为两个数还是三个数还是更多，以及怎么用代码的形式实现。j*(i-j)表示拆分成两个数，j*dp[i-1]表示拆分成三个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int max(int a,int b){
    return a>=b?a:b;
}
int integerBreak(int n) {
    if(n<2)
        return 0;
    int *dp=malloc(sizeof(int)*(n+1));
    dp[0]=0;
    dp[1]=0;
    dp[2]=1;
    for(int i=3;i<=n;i++){
        int MAX=0;
        for(int j=1;j<i;j++)
            MAX=max(max(j*(i-j),j*dp[i-j]),MAX);
        dp[i]=MAX;
    }
    return dp[n];
}

3.不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

题解：别被搜索数吓到，这是用来降低难度的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numTrees(int n) {
    if(n<3)
        return n;
    int *dp=malloc(sizeof(int)*(n+1));
    dp[0]=1;//用于递归计算
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=n;i++){
        dp[i]=0;
        for(int j=0;j<i;j++)
            dp[i]+=dp[j]*dp[i-j-1];
    }
    return dp[n];
}

3.经典01背包问题

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
#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, bagweight;
    scanf("%d %d", &n, &bagweight);

    int *weight = (int *)malloc(n * sizeof(int));
    int *value = (int *)malloc(n * sizeof(int));

    for (int i = 0; i < n; ++i) {
        scanf("%d", &weight[i]);
    }
    for (int j = 0; j < n; ++j) {
        scanf("%d", &value[j]);
    }

    int **dp = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; ++i) {
        dp[i] = (int *)malloc((bagweight + 1) * sizeof(int));
        for (int j = 0; j <= bagweight; ++j) {
            dp[i][j] = 0;
        }
    }

    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }
//行表示物品，列表示背包容量
//dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= bagweight; j++) {
            if (j < weight[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);//核心递推公式
            }
        }
    }

    printf("%d\n", dp[n - 1][bagweight]);

    for (int i = 0; i < n; ++i) {
        free(dp[i]);
    }
    free(dp);
    free(weight);
    free(value);

    return 0;
}

滚动数组：采用一维数组实现，但是遍历背包时要倒序遍历。

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
// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取 M 和 N
    int M, N;
    cin >> M >> N;

    vector<int> costs(M);
    vector<int> values(M);

    for (int i = 0; i < M; i++) {
        cin >> costs[i];
    }
    for (int j = 0; j < M; j++) {
        cin >> values[j];
    }

    // 创建一个动态规划数组dp，初始值为0
    vector<int> dp(N + 1, 0);

    // 外层循环遍历每个类型的研究材料
    for (int i = 0; i < M; ++i) {
        // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
        for (int j = N; j >= costs[i]; --j) {
            // 考虑当前研究材料选择和不选择的情况，选择最大值
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }

    // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值
    cout << dp[N] << endl;

    return 0;
}

4.分割等和子集

题解：本质是能否把容量为half的背包装满。

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
int max(int a,int b){
    if(a>=b)
        return a;
    return b;
}

bool canPartition(int* nums, int numsSize) {
    int half=0;
    for(int i=0;i<numsSize;i++)
        half+=nums[i];
    //奇数直接返回false
    if(half%2==1)
        return false;
    half=half/2;

    int *dp=malloc(sizeof(int)*(half+1));
    for(int j=0;j<=half;j++)
        dp[j]=0;
    for(int i=0;i<numsSize;i++){
        for(int j=half;j>=nums[i];j--)
            dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
    }
    if(dp[half]==half)
        return true;
    return false;
}

5.最后一块石头的重量II

题解：看了眼答案才知道，两块石头之间互相湮灭，只需要把石头分成重量差距最小的两份就行了，然后处理思路和上题一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int max(int a,int b){
    if(a>=b)
        return a;
    return b;
}

int lastStoneWeightII(int* stones, int stonesSize) {
    int sum=0,half;
    for(int i=0;i<stonesSize;i++)
        sum+=stones[i];
    half=sum/2;

    int *dp=malloc(sizeof(int)*(half+1));
    for(int j=0;j<=half;j++)
        dp[j]=0;
    for(int i=0;i<stonesSize;i++){
        for(int j=half;j>=stones[i];j--){
            dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
        }
    }
    return sum-dp[half]*2;
}

6.目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//求2的n次方
int pow_2(int n){
    int result=1;
    for(int i=0;i<n;i++)
        result*=2;
    return result;
}

//x为正，sum-x的为负。x-(sum-x)=target,故x=(sum+target)/2;
int findTargetSumWays(int* nums, int numsSize, int target) {
    int sum=0;
    for(int i=0;i<numsSize;i++)
        sum+=nums[i];
    //结果是奇数，直接返回false
    if((sum+target)%2)
        return false;
    
    //如果是负数也直接返回false
    if(sum+target<0)
        return false;

    int x=(sum+target)/2;

    //dp[numsSize-1][x];初始化
    int **dp=malloc(sizeof(int*)*numsSize);
    for(int i=0;i<numsSize;i++){
        dp[i]=malloc(sizeof(int)*(x+1));
        for(int j=0;j<=x;j++)
            dp[i][j]=0;
    }

    //赋值dp[0][j],只放物品0，想要填满必须刚好容量等于物品0的价值；
    if(nums[0]<=x)  //防止溢出
        dp[0][nums[0]]=1;

    //赋值dp[i][0],填满容量为0的背包有一种方式，什么都不放（暂不考虑物品价值为0的情况）
    // for(int i=0;i<numsSize;i++)
    //     dp[i][0]=1;

    //如果考虑0的情况那就是取不取0，几个0就是2的几次方。
    int counter_0=0;
    for(int i=0;i<numsSize;i++){
        if(nums[i]==0)
            counter_0++;
        dp[i][0]=pow_2(counter_0);
    }

    for(int i=1;i<numsSize;i++){
        for(int j=0;j<=x;j++){
            //如果能装下物品i
            if(j>=nums[i]){
                dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j];
            }
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[numsSize-1][x];
}

7.一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 ：

  • 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

  • 输出：4

  • 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

题解：依旧是背包问题，但是三维数组。物品的价值都为1（因为只计算个数），而背包的容量有两个维度，分别是 m，n。因此 dp 数组是三维的，可以利用滚动数组压缩到二维，但记得对背包容量进行遍历的时候要倒序遍历！！！

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
int max(int a,int b){
    return a>=b?a:b;
}

int findMaxForm(char** strs, int strsSize, int m, int n) {
    //记录每个字符串中0和1的数量
    int **nums=malloc(sizeof(int*)*2);
    nums[0]=malloc(sizeof(int)*strsSize);
    nums[1]=malloc(sizeof(int)*strsSize);
    for(int i=0;i<2;i++)
        for(int j=0;j<strsSize;j++)
            nums[i][j]=0;

    for(int i=0;i<strsSize;i++){
        int len=strlen(strs[i]);
        for(int j=0;j<len;j++){
            if(strs[i][j]=='0')
                nums[0][i]++;
            else if(strs[i][j]=='1')
                nums[1][i]++;
        }
    }

    //初始化dp数组
    int **dp=malloc(sizeof(int*)*(m+1));
    for(int j=0;j<=m;j++){
        dp[j]=malloc(sizeof(int)*(n+1));
        for(int k=0;k<=n;k++)
            dp[j][k]=0;
    }

    //推导公式:dp[i][j][k]=max(dp[i-1][j-nums[0][i]][k-nums[1][i]]+1,dp[i-1][j][k])
    //压缩成二维：dp[j][k]=max(dp[j-nums[0][i]][k-nums[1][i]]+1,dp[j][k])
    //注意公式中的+1不要忘了，放入i后长度会加1。
    //压缩后遍历背包容量且从后向前遍历！
    for(int i=0;i<strsSize;i++){
        for(int j=m;j>=nums[0][i];j--){
            for(int k=n;k>=nums[1][i];k--){
                dp[j][k]=max(dp[j-nums[0][i]][k-nums[1][i]]+1,dp[j][k]);
            }
        }
    }
    return dp[m][n];
}

8.完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。在完全背包中，物品是可以放无限个，所以 即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放 物品0 和 物品1 的最大价值即：dp[1][1]， 而不是 dp[0][1]

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

初始化：

  • 背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0，故全部初始化为 0。

  • 当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。 当j >= weight[0]时，dp[0][j] 如果能放下weight[0]的话，就一直装，每一种物品有无限个。

代码如下：

1
2
3
4
5
6
7
for (int i = 1; i < weight.size(); i++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[i][0] = 0;
}

// 正序遍历，如果能放下就一直装物品0
for (int j = weight[0]; j <= bagWeight; j++)
    dp[0][j] = dp[0][j - weight[0]] + value[0];

9.零钱兑换II

题解：关键是递推公式，另外注意amount为 0 的时候，有一种组合方案，不能初始化为零。

1
2
3
4
5
//递推公式（分为能不能放下coins[]
if(j>=coins[i])
	dp[i][j]=dp[i][j-coins[i]]+dp[i-1][j];
else
	dp[i][j]=dp[i-1][j];
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
int change(int amount, int* coins, int coinsSize) {
    int **dp=malloc(sizeof(int*)*coinsSize);
    for(int i=0;i<coinsSize;i++){
        dp[i]=malloc(sizeof(long long)*(amount+1));
        for(int j=0;j<=amount;j++)
            dp[i][j]=0;
    }
    //初始化dp[0][i];
    int i=coins[0];
    while(i<=amount){
        dp[0][i]=1;
        i+=coins[0];
    }
    //amount为0时，有一种方案。
    for(int i=0;i<coinsSize;i++)
        dp[i][0]=1;

    //推导公式
    for(int i=1;i<coinsSize;i++){
        for(int j=0;j<=amount;j++){
            if(j>=coins[i])
                dp[i][j]=dp[i][j-coins[i]]+dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[coinsSize-1][amount];
}

10.组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

  • nums = [1, 2, 3]

  • target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

题解：不要想成二维背包，很难理解，想象成爬楼梯就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
int combinationSum4(int* nums, int numsSize, int target) {
    unsigned long long *dp=malloc(sizeof(unsigned long long)*(target+1));
    for(int i=1;i<=target;i++)
        dp[i]=0;
    dp[0]=1;
    for(int i=1;i<=target;i++){
        for(int j=0;j<numsSize;j++){
            if(i>=nums[j])
                dp[i]+=dp[i-nums[j]];
        }
    }
    return dp[target];
}

先遍历背包后遍历物品得到的是排列数 ；先遍历物品后遍历背包得到的是组合数。

11.零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//取最小值，但是-1不行(右边的b是因为被加1了)
int min(int a,int b){
    if(a==-1&&b!=0)
        return b;
    else if(a!=-1&&b==0)
        return a;
    else if(a==-1&&b==0)
        return -1;
    else
        return a<=b?a:b;
}

int coinChange(int* coins, int coinsSize, int amount) {
    if(amount==0)
        return 0;

    int **dp=malloc(sizeof(int*)*coinsSize);
    for(int i=0;i<coinsSize;i++){
        dp[i]=malloc(sizeof(int)*(amount+1));
        for(int j=0;j<=amount;j++)
            dp[i][j]=-1;
    }

    for(int i=0;i<=amount;i++){
        if(i%coins[0]==0)
            dp[0][i]=i/coins[0];
    }

    for(int i=1;i<coinsSize;i++){
        for(int j=0;j<=amount;j++){
            if(j>=coins[i])
                dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1);
            else
                dp[i][j]=dp[i-1][j];
        }
    }

    return dp[coinsSize-1][amount];
}

12.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题解：和上一题一样。

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
int min(int a,int b){
    return a<=b?a:b;
}
//因为1也是平方数，所以没有表示不了的情况。
int numSquares(int n) {
    //自己创建平方数的数组
    int *coins=malloc(sizeof(int)*100);
    int coinsSize=0;
    while((coinsSize+1)*(coinsSize+1)<=n){
        coins[coinsSize++]=(coinsSize+1)*(coinsSize+1);
    }

    int **dp=malloc(sizeof(int*)*coinsSize);
    for(int i=0;i<coinsSize;i++){
        dp[i]=malloc(sizeof(int)*(n+1));
        for(int j=0;j<=n;j++)
            dp[i][j]=0;
    }

    for(int j=0;j<=n;j++)
        dp[0][j]=j;

    for(int i=1;i<coinsSize;i++){
        for(int j=0;j<=n;j++){
            if(j>=coins[i])
                dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1);
            else
                dp[i][j]=dp[i-1][j];
        }
    }

    return dp[coinsSize-1][n];
}

13.单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

  • 输入: s = "leetcode", wordDict = ["leet", "code"]

  • 输出: true

  • 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

  • 输入: s = "applepenapple", wordDict = ["apple", "pen"]

  • 输出: true

  • 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。

  • 注意你可以重复使用字典中的单词。

题解：二维背包害人不浅啊。。。以后排列问题直接写一维。话说你能一眼看出来是排列吗？

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
bool equal(char *s, int start, int end, char *t){
    //对其颗粒度
    start--;
    end--;
    int lenT=strlen(t);
    if(end-start+1!=lenT)
        return false;
    for(int i=0;i<lenT;i++){
        if(s[start+i]!=t[i])
            return false;
    }
    return true;
}

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int len=strlen(s);
    bool *dp=malloc(sizeof(bool)*(len+1));
    for(int i=1;i<=len;i++)
        dp[i]=0;
    //字符串长度为0时可以表示
    dp[0]=1;
    //先遍历背包容量，再遍历字符串
    for(int i=0;i<=len;i++){
        for(int j=0;j<wordDictSize;j++){
            //如果存在字符串能弥补新的一段空缺
            int len_j=strlen(wordDict[j]);
            if(i>=len_j
                &&dp[i-len_j]==1
                &&equal(s,i-len_j+1,i,wordDict[j])){
                    dp[i]=1;
                    break;
                }
        }
    }
    return dp[len];
}

14.多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

题解：每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

15.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

题解：简单的 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int max(int a,int b){
    return a>=b?a:b;
}
int rob(int* nums, int numsSize) {
    if(numsSize==0)
        return 0;
    if(numsSize==1)
        return nums[0];

    int *dp=malloc(sizeof(int)*(numsSize+1));
    for(int i=2;i<=numsSize;i++)
        dp[i]=0;
    dp[0]=0;
    dp[1]=nums[0];
    for(int i=2;i<=numsSize;i++){
        dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);
    }
    return dp[numsSize];
}

16.打家劫舍 II

所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。

题解：对于一个合法方案，不可能同时抢第 0 间和第 n-1 间。因此最优解一定是属于下面两类之一：

  • 情况 1：不抢最后一间 n-1

  • 情况 2：不抢第一间 0

因为任意一个合法方案，必然满足：要么没选 0，要么没选 n-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
25
26
27
28
29
int max(int a,int b){
    return a>=b?a:b;
}
int rob(int* nums, int numsSize) {
    if(numsSize==1)
        return nums[0];
    if(numsSize==2)
        return max(nums[0],nums[1]);
    
    //先计算0到n-2的情况
    int *dp1=malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++)
        dp1[i]=0;
    dp1[0]=0;
    dp1[1]=nums[0];
    for(int i=2;i<numsSize;i++)
        dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i-1]);
    
    //再计算1到n-1的情况
    int *dp2=malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++)
        dp2[i]=0;
    dp2[0]=0;
    dp2[1]=nums[1];
    for(int i=2;i<numsSize;i++)
        dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i]);
    
    return max(dp1[numsSize-1],dp2[numsSize-1]);
}

17.打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

题解：遍历一下树就行，但是dp[2]来表示可不可以偷当前节点的思路是怎么想到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int max(int a,int b){
    return a>=b?a:b;
}

int *robTree(struct TreeNode* root){
    int *dp=malloc(sizeof(int)*2);
    //0表示不偷当前节点，1表示可以偷（注意是可以不是一定）
    dp[0]=0;
    dp[1]=0;
    if(root==NULL)
        return dp;
    int *left=robTree(root->left);
    int *right=robTree(root->right);
    dp[0]=left[1]+right[1];
    dp[1]=max(dp[0],left[0]+right[0]+root->val);
    return dp;
}

int rob(struct TreeNode* root) {
    int *dp=robTree(root);
    return max(dp[0],dp[1]);
}

18.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

题解：不管了，还是贪心的方法比较好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int min(int a,int b){
    return a<=b?a:b;
}
int max(int a,int b){
    return a>=b?a:b;
}
int maxProfit(int* prices, int pricesSize) {
    int low=INT_MAX,result=0;
    for(int i=0;i<pricesSize;i++){
        low=min(low,prices[i]);
        result=max(result,prices[i]-low);
    }
    return result;
}

19.买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

题解：状态转换方式很有意思。其实也不难理解，但是自己想是真想不到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int max(int a, int b){
    return a>=b?a:b;
}
int maxProfit(int* prices, int pricesSize) {
    int buy1=-prices[0],sell1=0;
    int buy2=-prices[0],sell2=0;
    for(int i=1;i<pricesSize;i++){
        //当天买入，或已经买入
        buy1=max(-prices[i],buy1);
        //当天卖出，或已经卖出
        sell1=max(buy1+prices[i],sell1);
        //当天买入，或已经买入
        buy2=max(sell1-prices[i],buy2);
        //当天卖出，或已经卖出
        sell2=max(buy2+prices[i],sell2);
    }
    return sell2;
}

20.买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

题解：和上题思路一样，直接定义一个数组来存储状态（真是压压又缩缩啊）。

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
int max(int a, int b){
    return a>=b?a:b;
}
int maxProfit(int k, int* prices, int pricesSize) {
    //记录第i次买入卖出共2k种状态
    int *state=malloc(sizeof(int)*k*2);
    int len=k*2;
    //初始化
    for(int i=0;i<len;i++){
        if(i%2==0)
            state[i]=-prices[0];
        if(i%2==1)
            state[i]=0;
    }
    for(int i=1;i<pricesSize;i++){
        for(int j=0;j<len;j++){
            //当天买入或已经买入
            if(j%2==0){
                if(j==0)
                    state[j]=max(-prices[i],state[j]);
                else
                    state[j]=max(state[j-1]-prices[i],state[j]);
            }
            //当天卖出或已经卖出
            else
                state[j]=max(state[j-1]+prices[i],state[j]);
        }
    }
    return state[len-1];
}

21.最佳买卖股票时机含冷冻期

题解：好复杂的状态转换。。。你才是真正的 hard 吧？

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
int max(int a, int b){
    return a>=b?a:b;
}
int maxProfit(int* prices, int pricesSize) {
    int **state=malloc(sizeof(int*)*pricesSize);
    for(int i=0;i<pricesSize;i++)
        state[i]=malloc(sizeof(int)*4);
    //四种状态:持有股票，今天卖出，冷冻期，卖出状态。
    //思考为什么要单独把今天卖出和卖出状态分来，
    //因为冷冻期的前一天一定是今天卖出
    state[0][0]=-prices[0];
    state[0][1]=0;
    state[0][2]=0;
    state[0][3]=0;
    for(int i=1;i<pricesSize;i++){
        //持有股票状态，今天买或已经买入
        //今天买有两种状态，前一天是冷冻期或者是卖出状态
        state[i][0]=max(max(state[i-1][2]-prices[i],state[i-1][3]-prices[i]),state[i-1][0]);
        //今天卖出,昨天一定是持有股票状态
        state[i][1]=state[i-1][0]+prices[i];
        //冷冻期的前一天一定是今天卖出
        state[i][2]=state[i-1][1];
        //卖出状态,前一天是冷冻期，或前一天就是卖出状态
        state[i][3]=max(state[i-1][2],state[i-1][3]);
    }
    
    int Max=0;
    for(int i=1;i<4;i++){
        Max=max(Max,state[pricesSize-1][i]);
    }
    return Max;
}

22.买卖股票的最佳时机含手续费

题解：持有股票和未持有股票两种状态。卖出时多减个手续费就行。state[0][1]不能赋值成-fee。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int max(int a,int b){
    return a>=b?a:b;
}
int maxProfit(int* prices, int pricesSize, int fee) {
    int **state=malloc(sizeof(int*)*pricesSize);
    for(int i=0;i<pricesSize;i++)
        state[i]=malloc(sizeof(int)*2);
    state[0][0]=-prices[0];
    state[0][1]=0;
    for(int i=1;i<pricesSize;i++){
        //今天买或已经买了
        state[i][0]=max(state[i-1][1]-prices[i],state[i-1][0]);
        //今天卖或已经卖了
        state[i][1]=max(state[i-1][0]+prices[i]-fee,state[i-1][1]);
    }
    return state[pricesSize-1][1];
}

23.最长递增子序列

题解：这个 dp 数组的含义感觉不好想。

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
int lengthOfLIS(int* nums, int numsSize) {
    int *dp=malloc(sizeof(int)*numsSize);
    //dp[i]表示以nums[i]为最大值的最长序列长度。
    // for(int i=0;i<numsSize;i++){
    //     if(nums[0]==nums[i])
    //         dp[i]=1;
    //     else
    //         dp[i]=0;
    // }
    //好像不用初始化这么麻烦也行，反正max会矫正的。
    dp[0]=1;
    for(int i=;i<numsSize;i++)
            dp[i]=0;

    int max;
    for(int i=0;i<numsSize;i++){
        max=0;
        for(int j=0;j<numsSize;j++){
            if(nums[i]>nums[j])
                max=max>=dp[j]?max:dp[j];
        }
        dp[i]=max+1;
    }
    max=0;
    for(int i=0;i<numsSize;i++)
        max=max>=dp[i]?max:dp[i];
    return max;
}

24.最长连续递增序列

题解：这也是动态规划的思想吗？

1
2
3
4
5
6
7
8
9
10
11
12
int findLengthOfLCIS(int* nums, int numsSize) {
    int counter=1,max=1;
    for(int i=1;i<numsSize;i++){
        if(nums[i]>nums[i-1]){
            counter++;
            max=max>=counter?max:counter;
        }
        else
            counter=1;
    }
    return max;
}

25.最长重复子数组

题解：也是自己写出来了，感觉借助了上一题的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int counter=0,max=0;
    //i表示从nums的第i个数开始比较，j表示nums2的下标
    //nums2的最后一个数字对准nums1的第一个字符开始比较、移动
    for(int i=-nums2Size+1;i<nums1Size;i++){
        counter=0;//记得归零
        for(int j=0;j<nums2Size;j++){
            if(j+i>=nums1Size)
                break;
            else if(j+i<0)
                continue;
            else if(nums2[j]==nums1[j+i]){
                counter++;
                max=max>=counter?max:counter;
            }
            else    
                counter=0;
        }
    }
    return max;
}

26.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

题解：推导公式想不出来。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int max(int a, int b){
    return a>=b?a:b;
}
int longestCommonSubsequence(char* text1, char* text2) {
    int len1=strlen(text1);
    int len2=strlen(text2);
    int **dp=malloc(sizeof(int*)*(len1+1));
    for(int i=0;i<=len1;i++){
        dp[i]=malloc(sizeof(int)*(len2+1));
        for(int j=0;j<=len2;j++)
            dp[i][j]=0;
    }
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            //如果text1的第i个和text2的第j个的字符相同
            if(text1[i-1]==text2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

        }
    }
    return dp[len1][len2];
}

27.不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

  • nums1[i] == nums2[j]

  • 且绘制的直线不与任何其他连线（非水平线）相交。

题解：果然和上一题代码一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int max(int a, int b){
    return a>=b?a:b;
}
int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int **dp=malloc(sizeof(int*)*(nums1Size+1));
    for(int i=0;i<=nums1Size;i++){
        dp[i]=malloc(sizeof(int)*(nums2Size+1));
        for(int j=0;j<=nums2Size;j++)
            dp[i][j]=0;
    }
    for(int i=1;i<=nums1Size;i++){
        for(int j=1;j<=nums2Size;j++){
            //如果nums1的第i个数和nums2的第j个数相同
            if(nums1[i-1]==nums2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    return dp[nums1Size][nums2Size];
}

28.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

题解：easy题，直接双指针了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isSubsequence(char* s, char* t) {
    int lens=strlen(s);
    int lent=strlen(t);
    if(lens>lent)
        return false;
    int i=0,j=0;
    while(i<lens&&j<lent){
        if(s[i]==t[j])
            i++;
        j++;
    }
    if(i==lens)
        return true;
    return false;
}

29.不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

题解：即使看了答案递推公式也很难理解。

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
int numDistinct(char* s, char* t) {
    int lens=strlen(s);
    int lent=strlen(t);
    int **dp=malloc(sizeof(int*)*(lens+1));
    for(int i=0;i<=lens;i++){
        dp[i]=malloc(sizeof(int)*(lent+1));
        for(int j=0;j<=lent;j++)
            dp[i][j]=0;
    }
    //任意长度的t中都有一中空串（或者说把t删成空串只有一种方法）
    for(int i=0;i<=lens;i++)
        dp[i][0]=1;
    //s中t出现的次数
    for(int i=1;i<=lens;i++){
        for(int j=1;j<=lent;j++){
            //如果s中的第i个字符与t中的第j个字符相同
            if(s[i-1]==t[j-1])
                //分为第i个字符直接作为结尾和第i个字符不直接作为结尾两种情况:
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            //如果不同，则考虑把第i个字符删除的情况（不用这个字符做匹配）
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[lens][lent];
}

30.两个字符串的删除操作

题解：注意一下初始化的内容。这题也可以转换成前面那道最长公共子序列来求。

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
int min(int a, int b){
    return a<=b?a:b;
}
int minDistance(char* word1, char* word2) {
    int len1=strlen(word1);
    int len2=strlen(word2);
    int **dp=malloc(sizeof(int*)*(len1+1));
    for(int i=0;i<=len1;i++)
        dp[i]=malloc(sizeof(int)*(len2+1));
    //初始化
    for(int i=0;i<=len1;i++)
        dp[i][0]=i;
    for(int j=0;j<=len2;j++)
        dp[0][j]=j;

    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(word1[i-1]==word2[j-1])
                dp[i][j]=dp[i-1][j-1];
            //不相同时有三种情况，删word1，删word2，都删
            else
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1])+1,dp[i-1][j-1]+2);
        }
    }
    return dp[len1][len2];
}

31.编辑距离

题解：和上题类似。增删意义相同，而替换的意义在于可以把两步操作压缩为一步。

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
int min(int a,int b,int c){
    return (a<=b?a:b)<=c?(a<=b?a:b):c;
}
int minDistance(char* word1, char* word2) {
    int len1=strlen(word1);
    int len2=strlen(word2);
    int **dp=malloc(sizeof(int*)*(len1+1));
    for(int i=0;i<=len1;i++)
        dp[i]=malloc(sizeof(int)*(len2+1));
    for(int i=0;i<=len1;i++)
        dp[i][0]=i;
    for(int j=0;j<=len2;j++)
        dp[0][j]=j;

    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(word1[i-1]==word2[j-1])
                dp[i][j]=dp[i-1][j-1];
            //因为可以修改字符，所以不需要两个都删
            else
                dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;
        }
    }
    return dp[len1][len2];
}

32.回文子串

题解：借助回文串的特点来定义 dp 的含义以及递推公式，再观察公式的递推方向判断出要从左下角向右上角遍历。

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
int countSubstrings(char* s) {
    int len=strlen(s);
    bool **dp=malloc(sizeof(bool*)*len);
    for(int i=0;i<len;i++){
        dp[i]=malloc(sizeof(bool)*len);
        for(int j=0;j<len;j++)
                dp[i][j]=false;
    }
    //dp[i][j]表示下标i到下标j的字符串
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){
            if(s[i]!=s[j])
                dp[i][j]=false;
            else{
                //长度为1，肯定是
                if(i==j)
                    dp[i][j]=true;
                //长度为2，也是
                else if(i+1==j)
                    dp[i][j]=true;
                //长度为3以以上，看内圈
                else
                    dp[i][j]=dp[i+1][j-1];
            }
        }
    }
    int counter=0;
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){
            if(dp[i][j])
                counter++;
        }
    }
    return counter;
}

33.最长回文子序列

给你一个字符串 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
int max(int a,int b){
    return a>=b?a:b;
}
int longestPalindromeSubseq(char* s) {
    int len=strlen(s);
    int **dp=malloc(sizeof(int*)*len);
    for(int i=0;i<len;i++){
        dp[i]=malloc(sizeof(int)*len);
        for(int j=0;j<len;j++)
            dp[i][j]=0;
    }
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){
            //去掉左边的或右边的
            if(s[i]!=s[j])
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            else{
                //长度为1，则一定是且最大长度为1
                if(i==j)
                    dp[i][j]=1;
                //长度为2，且两个字符相同
                else if(i+1==j)
                    dp[i][j]=2;
                //长度大于等于3，且两个字符相同，直接内部加2
                else
                    dp[i][j]=dp[i+1][j-1]+2;
            }
        }
    }
    return dp[0][len-1];
}

34.乘积最大子数组

题解：存储以每个位置为结尾的最大数组乘积和最小数组乘积。

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
int max(int a, int b, int c){
    a=a>=b?a:b;
    return a>=c?a:c;
}
int min(int a, int b, int c){
    a=a<=b?a:b;
    return a<=c?a:c;
}

int maxProduct(int* nums, int numsSize) {
    int *maxs=malloc(sizeof(int)*numsSize);
    int *mins=malloc(sizeof(int)*numsSize);
    maxs[0]=nums[0];
    mins[0]=nums[0];
    int result=maxs[0];
    for(int i=1;i<numsSize;i++){
        /* 关键逻辑：每个位置有三种可能
           1. 从当前元素重新开始（比如遇到0后）
           2. 前一个最大乘积 * 当前元素
           3. 前一个最小乘积 * 当前元素（负负得正的情况）*/
        maxs[i]=max(nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]);
        mins[i]=min(nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]);
        if(maxs[i]>result)
            result=maxs[i];
    }
    return result;
}

35.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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
int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
int longestConsecutive(int* nums, int numsSize) {
    if(numsSize==0)
        return 0;
    qsort(nums,numsSize,sizeof(int),cmp);
    int* dp=malloc(sizeof(int)*numsSize);
    dp[0]=1;
    int max=1;
    for(int i=1;i<numsSize;i++){
        //刚好比上一个数大1
        if(nums[i]-nums[i-1]==1)
            dp[i]=dp[i-1]+1;
        //相同则忽略
        else if(nums[i]==nums[i-1])
            dp[i]=dp[i-1];
        else
            dp[i]=1;

        if(dp[i]>max)
            max=dp[i];        
    }
    return max;
}

36.最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

题解：怎么感觉自己把 dp 都写成屎山了...

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
char* longestPalindrome(char* s) {
    int len=strlen(s);
    if(len==1)
        return s;
    bool **dp=malloc(sizeof(bool*)*len);
    for(int i=0;i<len;i++){
        dp[i]=malloc(sizeof(bool)*len);
        for(int j=0;j<len;j++){
            if(i==j)
                dp[i][j]=1;
            else
                dp[i][j]=0;
        }
    }
    for(int i=len-1;i>=0;i--){
        for(int j=i+1;j<len;j++){
            if(s[i]!=s[j])
                dp[i][j]=0;
            //长度为2，相同，则是回文
            else if(s[i]==s[j]&&i+1==j)
                dp[i][j]=1;
            else
                dp[i][j]=dp[i+1][j-1];
        }
    }

    int max=1,start=0;//记录最长回文长度和起点
    for(int i=len-1;i>=0;i--){
        for(int j=i+1;j<len;j++){
            if(dp[i][j]==1&&j-i+1>max){
                max=j-i+1;
                start=i;
            }
        }
    }
    char *result=malloc(sizeof(char)*(max+1));
    for(int i=0;i<max;i++)
        result[i]=s[start+i];
    result[max]='\0';

    return result;
}

37.统计放置房子的方式数

一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

题解：只算一侧，结果平方即可。

1
2
3
4
5
6
7
8
9
10
11
# define MOD 1000000007
int countHousePlacements(int n) {
    //dp只记录一侧的房子摆列种类。结果平方即可
    int *dp=malloc(sizeof(int)*(n+1));
    dp[0]=1;
    dp[1]=2;
    for(int i=2;i<=n;i++)
        dp[i]=(dp[i-1]+dp[i-2])%MOD;
    int result=(long long)dp[n]*(long long)dp[n]%MOD;
    return result;
}

38.删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

题解：可以转换为打家劫舍问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int max(int a, int b){
    return a>=b?a:b;
}
int deleteAndEarn(int* nums, int numsSize) {
    int new_nums[10001]={0};
    for(int i=0;i<numsSize;i++){
        new_nums[nums[i]]+=nums[i];
    }

    int dp[10001]={0};
    dp[0]=new_nums[0];
    dp[1]=max(new_nums[0],new_nums[1]);
    for(int i=2;i<10001;i++){
        dp[i]=max(dp[i-1],dp[i-2]+new_nums[i]);
    }
    return dp[10000];
}

39.执行操作可获得的最大总奖励 I

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

  • 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。

  • 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

题解：奇怪的 dp。关键是要注意到，如果选择大小为 k 的物品，则总价值可能是 k 到 2k-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
25
26
int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
int maxTotalReward(int* rewardValues, int rewardValuesSize) {
    qsort(rewardValues,rewardValuesSize,sizeof(int),cmp);
    //假设最大值为m，则总奖励最多只能是2m-1。
    int n=2*rewardValues[rewardValuesSize-1]-1;
    //dp[k]表示总奖励能否到达K
    bool *dp=malloc(sizeof(bool)*(n+1));
    for(int i=1;i<=n;i++)
        dp[i]=0;
    dp[0]=1;
    for(int i=0;i<rewardValuesSize;i++){
        //注意循环限制条件
        for(int j=rewardValues[i];j<=n&&j<2*rewardValues[i];j++){
            if(dp[j]||dp[j-rewardValues[i]])
                dp[j]=1;
        }
    }
    
    for(int i=n;i>=0;i--){
        if(dp[i])
            return i;
    }
    return 0;
}

40.超级饮料的最大强化能量

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

题解：状态机简单题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long long max(long long a,long long b){
    return a>=b?a:b;
}
long long maxEnergyBoost(int* energyDrinkA, int energyDrinkASize, int* energyDrinkB, int energyDrinkBSize) {
    int n=energyDrinkASize;
    long long **state=malloc(sizeof(long long*)*n);
    for(int i=0;i<n;i++){
        //饮用a，切换，引用b三种状态
        state[i]=malloc(sizeof(long long)*3);
    }
    state[0][0]=energyDrinkA[0];
    state[0][1]=0;
    state[0][2]=energyDrinkB[0];
    for(int i=1;i<n;i++){
        state[i][0]=max(state[i-1][0],state[i-1][1])+energyDrinkA[i];
        state[i][1]=max(state[i-1][0],state[i-1][2]);
        state[i][2]=max(state[i-1][2],state[i-1][1])+energyDrinkB[i];
    }
    long long result=max(max(state[n-1][0],state[n-1][1]),state[n-1][2]);
    return result;
}

41.选择建筑的方案数

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中： s[i] = '0' 表示第 i 栋建筑是一栋办公楼， s[i] = '1' 表示第 i 栋建筑是一间餐厅。 作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。 比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。 请你返回可以选择 3 栋建筑的 有效方案数 。

题解1：暴力回溯，记得回退的时候 flag 也要还原。

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
long long counter;//方案数
int num;//选择的数字数量
void back(char *s,int len,int start,char flag){
    if(num==3){
        counter++;
        printf("到达%d\n",start);
        return;
    }
    for(int i=start;i<len;i++){
        //字符与上个选取的不同才行
        if(flag!=s[i]){
            num++;
            char oldflag=flag;
            flag=s[i];
            back(s,len,i+1,flag);
            num--;
            flag=oldflag;//flag也要还原
        }
    }
}
long long numberOfWays(char* s) {
    counter=0;
    num=0;
    int len=strlen(s);
    back(s,len,0,'x');
    return counter;
}

题解2：状态机，记录不同前缀。

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
long long numberOfWays(char* s) {
    int len=strlen(s);
    long long result=0;
    long long** state=malloc(sizeof(long long*)*1000000);
    for(int i=0;i<len;i++)
        //四种状态(前缀)，0、1、01、10
        state[i]=malloc(sizeof(long long)*4);
    //初始化第一层
    if(s[0]=='0'){
        state[0][0]=1;
        state[0][1]=0;
    }
    else{
        state[0][0]=0;
        state[0][1]=1;        
    }
        state[0][2]=0;
        state[0][3]=0;

    for(int i=1;i<len;i++){
        if(s[i]=='0'){
            result+=state[i-1][2];

            state[i][0]=state[i-1][0]+1;
            state[i][1]=state[i-1][1];
            state[i][2]=state[i-1][2];
            state[i][3]=state[i-1][3]+state[i-1][1];
        }
        else{
            result+=state[i-1][3];

            state[i][0]=state[i-1][0];
            state[i][1]=state[i-1][1]+1;
            state[i][2]=state[i-1][2]+state[i-1][0];
            state[i][3]=state[i-1][3];            
        }
    }
    return result;
}

题解3：时间复杂度最低的答案，抄一份。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long long numberOfWays(char* s) {
    long long count0 = 0, count1 = 0;
    long long count01 = 0, count10 = 0;
    long long count010 = 0, count101 = 0;
    int i = 0;
    
    while (s[i] != '\0') {
        if (s[i] == '0') {
            count010 += count01;
            count10 += count1;
            count0++;
        } else {
            count101 += count10;
            count01 += count0;
            count1++;
        }
        i++;
    }
    
    return count010 + count101;
}

42.一个小组的最大实力值

题解：自己写了一堆 if else 灵神的代码太优雅了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
long long max(long long a, long long b){
    return a>=b?a:b;
}
long long min(long long a,long long b){
    return a<=b?a:b;
}
long long maxStrength(int* nums, int numsSize) {
    long long *maxdp=malloc(sizeof(long long)*numsSize);
    long long *mindp=malloc(sizeof(long long)*numsSize);
    maxdp[0]=nums[0];
    mindp[0]=nums[0];
    //四种情况，最小值同理
    // 不选，max 不变。
    // x 单独一个数组成子序列。
    // max⋅x。如果 x 是正数，这可能得到最大乘积。
    // max⋅x。如果 x 是负数，这可能得到最小乘积。
    for(int i=1;i<numsSize;i++){
        maxdp[i]=max(max(maxdp[i-1],nums[i]),max(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]));
        mindp[i]=min(min(mindp[i-1],nums[i]),min(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]));
    }
    return maxdp[numsSize-1];
}

43.乘积为正数的最长子数组长度

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

题解：真的很绕，但这种 dp 方式也很巧妙。每次检索到 0，长度直接清零。如果新加入的是正数，不影响符号，直接加一。但最长负数要额外判断一下前面的是否是 0，因为如果是 0，那么新加入的数就不可能形成负数数组，不能计算为0+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
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
int getMaxLen(int* nums, int numsSize) {
    int **dp=malloc(sizeof(int*)*2);
    dp[0]=malloc(sizeof(int)*numsSize);//记录以i为结尾的最大正积数长度
    dp[1]=malloc(sizeof(int)*numsSize);//记录以i为结尾的最大负积数长度
    if(nums[0]==0){
        dp[0][0]=0;
        dp[1][0]=0;
    }else if(nums[0]>0){
        dp[0][0]=1;
        dp[1][0]=0;        
    }else{
        dp[0][0]=0;
        dp[1][0]=1;            
    }

    for(int i=1;i<numsSize;i++){
        if(nums[i]==0){
            dp[0][i]=0;
            dp[1][i]=0;            
        }
        //nums[i]为正数时，前面的值乘以nums[i]不会改变符号
        else if(nums[i]>0){
            dp[0][i]=dp[0][i-1]+1;

            //前一个长度为0时,加上nums[i]，形成的负数长度依旧为0，因此要特殊判断
            if(dp[1][i-1]==0)
                dp[1][i]=0;
            else    
                dp[1][i]=dp[1][i-1]+1;
        }
        //如果是负数，前面的值乘以nums[i]改变符号
        else{
            //前一个长度为0时,加上nums[i]，形成的正数长度依旧为0，因此要特殊判断
            if(dp[1][i-1]==0)
                dp[0][i]=0;
            else
                dp[0][i]=dp[1][i-1]+1;

            dp[1][i]=dp[0][i-1]+1;
        }
    }

    int max=dp[0][0];
    for(int i=1;i<numsSize;i++){
        if(dp[0][i]>=max)
            max=dp[0][i];
    }
    
    return max;
}

44.访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

  • 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。

  • 对于你访问的位置 i ，你可以获得分数 nums[i] 。

  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

题解：同时维护两个数组分别表示以奇数结尾的最大值和以偶数结尾的最大值。题目要求必须选取nums[0]，导致在odd[0]和even[0]的赋值上犯了难。后面看了答案发现可以给不符合的那一项赋一个非常小的值，使其在比较的过程中必定不会被选取，太神奇了。

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
//判断是否是奇数
bool isodd(int a){
    if(a%2==1)
        return true;
    return false;
}

long long max(long long a, long long b){
    return a>=b?a:b;
}

long long maxScore(int* nums, int numsSize, int x) {
    //扫描到i时，选取的最后一个值为奇数的最大情况
    long long* odd=malloc(sizeof(long long)*numsSize);
    //扫描到i时，选取的最后一个值为偶数的最大情况
    long long* even=malloc(sizeof(long long)*numsSize);
    if(isodd(nums[0])){
        odd[0]=nums[0];
        even[0]=-1000000;
    }else{
        odd[0]=-1000000;
        even[0]=nums[0];        
    }
    for(int i=1;i<numsSize;i++){
        //如果是奇数
        if(isodd(nums[i])){
            odd[i]=max(odd[i-1]+nums[i],even[i-1]+nums[i]-x);
            even[i]=even[i-1];
        }
        //如果是偶数
        else{
            odd[i]=odd[i-1];
            even[i]=max(odd[i-1]+nums[i]-x,even[i-1]+nums[i]);
        }
    }
    return max(odd[numsSize-1],even[numsSize-1]);
}

45.插入一个字母的最大子序列数

给你一个由大写英文字母组成的字符串 s。

你可以在字符串的 任意 位置（包括字符串的开头或结尾）最多插入一个 大写英文字母。

返回在 最多插入一个字母 后，字符串中可以形成的 "LCT" 子序列的 最大 数量。

子序列 是从另一个字符串中删除某些字符（可以不删除）且不改变剩余字符顺序后得到的一个 非空 字符串。

题解：记录不同的前缀后缀数量，比较在前面差入 L，在中间插入 C，在末尾插入 L 三种情况的最大值。最后返回时记得加上字符串本身就存在的 LCT 数量。

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
long long max(long long a, long long b){
    return a>=b?a:b;
}

long long numOfSubsequences(char* s) {
    int len=strlen(s);
    long long *preL=malloc(sizeof(long long)*len);
    long long *preLC=malloc(sizeof(long long)*len);
    //LCT前缀后缀意义等价，记录一个即可
    long long *preLCT=malloc(sizeof(long long)*len);
    long long *sufT=malloc(sizeof(long long)*len);
    long long *sufCT=malloc(sizeof(long long)*len);
    //计算前缀
    preL[0]=0;
    preLC[0]=0;
    preLCT[0]=0;
    if(s[0]=='L')
        preL[0]++;

    for(int i=1;i<len;i++){
        if(s[i]=='L'){
            preL[i]=preL[i-1]+1;
            preLC[i]=preLC[i-1];
            preLCT[i]=preLCT[i-1];
        }
        else if(s[i]=='C'){
            preL[i]=preL[i-1];
            preLC[i]=preLC[i-1]+preL[i-1];
            preLCT[i]=preLCT[i-1];
        }
        else if(s[i]=='T'){
            preL[i]=preL[i-1];
            preLC[i]=preLC[i-1];   
            preLCT[i]=preLCT[i-1]+preLC[i-1];         
        }
        else{
            preL[i]=preL[i-1];
            preLC[i]=preLC[i-1];
            preLCT[i]=preLCT[i-1];
        }
    }
    //计算后缀
    sufT[len-1]=0;
    sufCT[len-1]=0;
    if(s[len-1]=='T')
        sufT[len-1]++;
    for(int i=len-2;i>=0;i--){
        if(s[i]=='T'){
            sufT[i]=sufT[i+1]+1;
            sufCT[i]=sufCT[i+1];
        }
        else if(s[i]=='C'){
            sufT[i]=sufT[i+1];
            sufCT[i]=sufCT[i+1]+sufT[i+1];
        }
        else{
            sufT[i]=sufT[i+1];
            sufCT[i]=sufCT[i+1];
        }
    }
    long long result=0;
    //假设插入L
    result=max(result,sufCT[0]);
    //假设插入T
    result=max(result,preLC[len-1]);
    //假设在中间插入C
    for(int i=0;i<len-1;i++){
        result=max(result,preL[i]*sufT[i+1]);
    }

    return result+preLCT[len-1];//加上原本就有的LCT数量
}

五、图论

1.所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出从节点 0 到节点 n-1 的所有路径并输出（不要求按特定顺序）graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

题解：这 dfs 不就是前面练的回溯吗，还没忘哈哈哈。

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
int *path;
int pathTop;
int **result;
int resultTop;
int *len;

void dfs(int **graph,int graphSize,int *graphColSize,int start){
    //到达终点
    if(start==graphSize-1){
        int *temp=malloc(sizeof(int)*pathTop);
        for(int i=0;i<pathTop;i++)
            temp[i]=path[i];
        len[resultTop]=pathTop;
        result[resultTop++]=temp;
        return;
    }
    for(int i=0;i<graphColSize[start];i++){
        path[pathTop++]=graph[start][i];
        dfs(graph,graphSize,graphColSize,graph[start][i]);
        pathTop--;
    }
}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
    path=malloc(sizeof(int)*graphSize);
    result=malloc(sizeof(int*)*1000000);
    len=malloc(sizeof(int)*1000000);
    pathTop=0;
    resultTop=0;
    //首先加入起点0;
    path[pathTop++]=0;

    dfs(graph,graphSize,graphColSize,0);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++)
        (*returnColumnSizes)[i]=len[i];
    return result;
}

2.岛屿数量

题解：深度遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs(char **grid, int dep, int len, int i,int j){
    if(i<0||i>=dep||j<0||j>=len||grid[i][j]!='1')
        return;
    grid[i][j]='0';
    dfs(grid,dep,len,i-1,j);//上
    dfs(grid,dep,len,i,j+1);//右
    dfs(grid,dep,len,i+1,j);//下
    dfs(grid,dep,len,i,j-1);//左
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int dep=gridSize;
    int len=gridColSize[0];
    int counter=0;
    for(int i=0;i<dep;i++){
        for(int j=0;j<len;j++){
            if(grid[i][j]=='1'){
                counter++;
                dfs(grid,dep,len,i,j);
            }
        }
    }
    return counter;
}

3.岛屿的最大面积

题解：这几个 mid 题纯白给啊。

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
int counter;

void dfs(int** grid, int dep, int wid, int i, int j){
    if(i<0||i>=dep||j<0||j>=wid||grid[i][j]!=1)
        return;
    counter++;
    grid[i][j]=0;
    dfs(grid,dep,wid,i-1,j);//上
    dfs(grid,dep,wid,i,j+1);//右
    dfs(grid,dep,wid,i+1,j);//下
    dfs(grid,dep,wid,i,j-1);//左
}

int max(int a, int b){
    return a>=b?a:b;
}

int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize) {
    int Max=0,dep=gridSize,wid=gridColSize[0];
    for(int i=0;i<dep;i++){
        for(int j=0;j<wid;j++){
            if(grid[i][j]==1){
                counter=0;
                dfs(grid,dep,wid,i,j);
                Max=max(Max,counter);
            }
        }
    }
    return Max;
}

4.总价值可以被 K 整除的岛屿数目

题解：大晚上的就别敲代码了，不是这错就是那错的。

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
int value;

void dfs(int** grid, int dep, int wid, int i, int j){
    if(i<0||i>=dep||j<0||j>=wid||grid[i][j]==0)
        return;
    value+=grid[i][j];
    grid[i][j]=0;
    dfs(grid,dep,wid,i-1,j);//上
    dfs(grid,dep,wid,i,j+1);//右
    dfs(grid,dep,wid,i+1,j);//下
    dfs(grid,dep,wid,i,j-1);//左
}

int countIslands(int** grid, int gridSize, int* gridColSize, int k) {
    int counter=0,dep=gridSize,wid=gridColSize[0];
    for(int i=0;i<dep;i++){
        for(int j=0;j<wid;j++){
            if(grid[i][j]!=0){
                value=0;
                dfs(grid,dep,wid,i,j);
                if(value%k==0)
                    counter++;
            }
        }
    }
    return counter;
}

5.主题空间

线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 grid，字符串中仅包含 "0"～"5" 这 6 个字符。地图上每一个字符代表面积为 1 的区域，其中 "0" 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。

假如整个 grid 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 0。

题解：做个标记，顺手的事情。第一遍写的时候，修改grid[i][j]='6'又把它作为参数传递了下去，被自己蠢哭。

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
int max;
int place;//记录单个区域的面积
bool flag;

void dfs(char **grid, int m, int n, int i, int j, char num){
    //如果是走廊，则不合题意，进行标记
    if(i<0||i>=m||j<0||j>=n||grid[i][j]=='0'){
        flag=false;
        return;
    }
    //与之前的数字不同，直接返回
    if(grid[i][j]!=num)
        return;

    place++;
    grid[i][j]='6';
    dfs(grid,m,n,i-1,j,num);
    dfs(grid,m,n,i,j+1,num);
    dfs(grid,m,n,i+1,j,num);
    dfs(grid,m,n,i,j-1,num);
}

int largestArea(char** grid, int gridSize){
    int max=0,m=gridSize,n=strlen(grid[0]);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]!='0'&&grid[i][j]!='6'){
                place=0;
                flag=true;
                dfs(grid,m,n,i,j,grid[i][j]);
                if(flag)
                    max=max>=place?max:place;
            }
        }
    }
    return max;
}

6.岛屿的周长

题解：在终止条件处做文章就行了。

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
int sum;

void dfs(int **grid, int m, int n, int i, int j){
    if(i<0||i>=m||j<0||j>=n||grid[i][j]==0){
        sum++;
        return;
    }
    if(grid[i][j]==2)
        return;
    grid[i][j]=2;//这里不能标记成0，不然会重复计数
    dfs(grid,m,n,i-1,j);
    dfs(grid,m,n,i,j+1);
    dfs(grid,m,n,i+1,j);
    dfs(grid,m,n,i,j-1);
}

int islandPerimeter(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    sum=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                dfs(grid,m,n,i,j);
                break;
            }
        }
    }
    return sum;
}

7.迷宫中离入口最近的出口

题解：明明思路看着很简单，但第一次写 BFS 还是要比想的麻烦啊。

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
int dir[4][2]={0,1,1,0,0,-1,-1,0};//表示四个方向

int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {
    int front=0,rear=0,step=0;
    //每个字符最多入队一次
    int **queue=malloc(sizeof(int*)*mazeSize*mazeColSize[0]);
    for(int i=0;i<mazeSize*mazeColSize[0];i++)
        queue[i]=malloc(sizeof(int)*2);
    
    //标记数组
    bool **flag=malloc(sizeof(bool*)*mazeSize);
    for(int i=0;i<mazeSize;i++){
        flag[i]=malloc(sizeof(bool)*mazeColSize[0]);
        for(int j=0;j<mazeColSize[0];j++)
            flag[i][j]=false;
    }
    //起点入栈
    queue[rear][0]=entrance[0];
    queue[rear][1]=entrance[1];
    rear++;

    flag[entrance[0]][entrance[1]]=true;

    while(front<rear){
        step++;
        //记录目前队列中元素数量
        int size=rear-front;
        for(int s=0;s<size;s++){
            //出队
            int x=queue[front][0],y=queue[front][1];
            front++;

            //寻找四个方向
            for(int i=0;i<4;i++){
                int nextx=x+dir[i][0];
                int nexty=y+dir[i][1];
                //越界了，跳过继续
                if(nextx<0||nextx>=mazeSize||nexty<0||nexty>=mazeColSize[0])
                    continue;

                //如果找到出口，则停止
                if(!flag[nextx][nexty]&&maze[nextx][nexty]=='.'
                    &&(nextx==0||nextx==mazeSize-1||nexty==0||nexty==mazeColSize[0]-1))
                    return step;

                //如果未访问且是空格，则标记并入队列
                if(!flag[nextx][nexty]&&maze[nextx][nexty]=='.'){
                    flag[nextx][nexty]=true;
                    queue[rear][0]=nextx;
                    queue[rear][1]=nexty;
                    rear++;
                }
            }
        }
    }
    return -1;
}

8.二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

  • 路径途经的所有单元格的值都是 0 。

  • 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

题解：答案上面用结构体数组来表示队列好像比二维数组方便诶。

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
//八个方向
int dir[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};

int shortestPathBinaryMatrix(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    //如果起点或终点本身就是障碍，返回-1;
    if(grid[0][0]==1||grid[m-1][n-1]==1)
        return -1;
    //如果只有一个格子，且不是障碍，返回1
    if(m==1&&n==1)
        return 1;

    int front=0,rear=0,step=0;
    int **queue=malloc(sizeof(int*)*m*n);
    for(int i=0;i<m*n;i++){
        queue[i]=malloc(sizeof(int)*2);
    }

    bool **flag=malloc(sizeof(bool*)*m);
    for(int i=0;i<m;i++){
        flag[i]=malloc(sizeof(bool)*n);
        for(int j=0;j<n;j++)
            flag[i][j]=false;
    }
    
    //起点入队
    queue[rear][0]=0;
    queue[rear][1]=0;
    rear++;
    flag[0][0]=true;//标记为已经访问
    
    while(front<rear){
        step++;//步数加一
        int size=rear-front;
        for(int i=0;i<size;i++){
            //出队
            int x=queue[front][0],y=queue[front][1];
            front++;

            //八个方向旋转
            for(int j=0;j<8;j++){
                int nextx=x+dir[j][0];
                int nexty=y+dir[j][1];
                //如果越界，或者是障碍，直接跳过
                if(nextx<0||nextx>=m||nexty<0||nexty>=n||grid[nextx][nexty]==1)
                    continue;
                //找到最终点
                else if(nextx==m-1&&nexty==n-1)
                    return step+1;//题目要求的是途径的总格数
                //未标记的可探索点
                else if(!flag[nextx][nexty]&&grid[nextx][nexty]==0){
                    //标记并入队
                    flag[nextx][nexty]=1;
                    queue[rear][0]=nextx;
                    queue[rear][1]=nexty;
                    rear++;
                }
            }
        }
    }
    return -1;
}

9.腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；

  • 值 1 代表新鲜橘子；

  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -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
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
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    //只有一个格子的情况
    if(m*n==1){
        if(grid[0][0]==0)
            return 0;
        else if(grid[0][0]==1)
            return -1;
        else if(grid[0][0]==2)
            return 0;
    }
    //使用队列存储腐烂的橘子
    int *qx=malloc(sizeof(int)*m*n);
    int *qy=malloc(sizeof(int)*m*n);
    int front=0,rear=0;
    int good=0;//新鲜橘子数量
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1)
                good++;
            //坏橘子入队
            else if(grid[i][j]==2){
                qx[rear]=i;
                qy[rear++]=j; 
            }
        }
    }
    //如果没有新鲜橘子
    if(good==0)
        return 0;

    int time;//记录时间
    while(front!=rear){
        time++;//时间加一
        int len=rear-front;
        for(int i=0;i<len;i++){
            //出队
            int x=qx[front];
            int y=qy[front++];
            //四个方向寻找
            for(int j=0;j<4;j++){
                int nx=x+dir[j][0];
                int ny=y+dir[j][1];
                //找到新鲜橘子进行处理
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1){
                    //入队
                    qx[rear]=nx;
                    qy[rear++]=ny;
                    //腐烂
                    grid[nx][ny]=2;
                    good--;
                }
            }
        }
    }
    if(good!=0)
        return -1;
    return time-1;//最后一轮没有橘子腐烂
}

10.地图中的最高点

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

  • 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。

  • 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度：

  • 每个格子的高度都必须是非负的。

  • 如果一个格子是 水域 ，那么它的高度必须为 0 。

  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子（也就是说它们有一条公共边） 。

找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。

题解：多源BFS，想了半天发现思路想错了。

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
int dir[4][2]={0,1,1,0,0,-1,-1,0};

int min(int a,int b){
    return a<=b?a:b;
}

int** highestPeak(int** isWater, int isWaterSize, int* isWaterColSize, int* returnSize, int** returnColumnSizes) {
    int m=isWaterSize, n=isWaterColSize[0];
    int **result=malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++){
        result[i]=malloc(sizeof(int)*n);
        for(int j=0;j<n;j++)
            result[i][j]=-1;//避免重复，全都初始化为-1;
    }

    //入栈
    int *qx=malloc(sizeof(int)*m*n);
    int *qy=malloc(sizeof(int)*m*n);
    int front=0,rear=0;

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(isWater[i][j]){
                result[i][j]=0;//水高度为0;
                qx[rear]=i;
                qy[rear++]=j;
            }
        }
    }

    while(front<rear){
        int size=rear-front;
        for(int i=0;i<size;i++){
            //出队
            int x=qx[front];
            int y=qy[front++];
            
            for(int j=0;j<4;j++){
                int nx=x+dir[j][0];
                int ny=y+dir[j][1];
                //只需判断是否等于-1即可，因为水域已经全部变成0了
                //判断是否为-1还可确保该节点未访问
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&result[nx][ny]==-1){
                    result[nx][ny]=result[x][y]+1;
                    //入队
                    qx[rear]=nx;
                    qy[rear++]=ny;
                }
            }
        }
    }

    *returnSize=m;
    *returnColumnSizes=malloc(sizeof(int)*m);
    for(int i=0;i<m;i++)
        (*returnColumnSizes)[i]=n;

    return result;
}

11.边界着色

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。

如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：

  • 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻

  • 在网格的边界上（第一行/列或最后一行/列）

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色。

并返回最终的网格 grid 。

题解：一个 DFS 被你写成啥了都。

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
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int *pathx;
int *pathy;
int top;

void dfs(int **grid, int m, int n, int i, int j, int num, int color, bool **visited){
    
    visited[i][j]=true;
    int isborder=false;
    for(int k=0;k<4;k++){
        int x=i+dir[k][0];
        int y=j+dir[k][1];
        if(x<0||x>=m||y<0||y>=n||grid[x][y]!=num){
            isborder=true;
        }else if(!visited[x][y])
            dfs(grid,m,n,x,y,num,color,visited);
    }
    if(isborder){
        pathx[top]=i;
        pathy[top++]=j;
    }
}
int** colorBorder(int** grid, int gridSize, int* gridColSize, int row, int col, int color, int* returnSize, int** returnColumnSizes) {
    int m=gridSize,n=gridColSize[0];
    *returnSize=m;
    *returnColumnSizes=malloc(sizeof(int)*m);
    for(int i=0;i<m;i++)
        (*returnColumnSizes)[i]=n;
    top=0;
    pathx=malloc(sizeof(int)*m*n);
    pathy=malloc(sizeof(int)*m*n);

    //记录是否被访问
    bool **visited=malloc(sizeof(bool*)*m);
    for(int i=0;i<m;i++){
        visited[i]=malloc(sizeof(bool)*n);
        for(int j=0;j<n;j++)
            visited[i][j]=false;
    }

    dfs(grid,m,n,row,col,grid[row][col],color,visited);

    for(int i=0;i<top;i++){
        grid[pathx[i]][pathy[i]]=color;
    }
    return grid;
}

12.飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

题解：把与边界相连的陆地全部清除，然后统计剩余陆地数量。

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
int dirx[4]={1,0,-1,0};
int diry[4]={0,1,0,-1};

void dfs(int **grid, int m, int n, int i, int j){
    if(i<0||i>=m||j<0||j>=n||grid[i][j]==0)
        return;
    grid[i][j]=0;
    for(int k=0;k<4;k++){
        int x=i+dirx[k];
        int y=j+diry[k];
        dfs(grid,m,n,x,y);
    }
}

int numEnclaves(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    //清除与边界相联的岛屿
    for(int i=0;i<m;i++){
        dfs(grid,m,n,i,0);
        dfs(grid,m,n,i,n-1);
    }
    for(int j=1;j<n-1;j++){
        dfs(grid,m,n,0,j);
        dfs(grid,m,n,m-1,j);
    }
    int counter=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1)
                counter++;
        }
    }
    return counter;
}

13.矩阵中移动的最大次数

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

  • 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 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
25
26
27
28
29
30
31
32
33
34
35
36
37
int dir[3][2]={-1,1,0,1,1,1};

int max(int a, int b){
    return a>=b?a:b;
}

int dfs(int** grid, int m, int n, int i, int j, int **dp){
    //不为-1，说明被计算过
    if(dp[i][j]!=-1)
        return dp[i][j];
    int max_step=0;
    for(int k=0;k<3;k++){
        int x=i+dir[k][0];
        int y=j+dir[k][1];
        if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]>grid[i][j]){
            max_step=max(max_step,dfs(grid,m,n,x,y,dp)+1);
        }
    }
    dp[i][j]=max_step;
    return max_step;
}
int maxMoves(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    int **dp=malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++){
        dp[i]=malloc(sizeof(int)*n);
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }
    int result=0;
    for(int i=0;i<m;i++){
        dfs(grid,m,n,i,0,dp);
        result=max(result,dp[i][0]);
        
    }
    return result;
}

14.统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

题解：被水围住的才是封闭岛屿，dfs 的时候要标记一下是否撞到边界。

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
int dir[4][2]={0,1,1,0,0,-1,-1,0};
bool flag;//标记是否撞到边界

void dfs(int **grid, int m, int n, int i, int j){
    if(i<0||i>=m||j<0||j>=n){
        flag=1;
        return;
    }
    else if(grid[i][j]==1)
        return;

    grid[i][j]=1;//变成水
    for(int k=0;k<4;k++){
        int x=i+dir[k][0];
        int y=j+dir[k][1];
        dfs(grid,m,n,x,y);
    }
}
int closedIsland(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    int counter=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==0){
                flag=0;
                dfs(grid,m,n,i,j);
                if(flag==0)
                    counter++;
            }
        }
    }
    return counter;
}

15.统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

题解：看着复杂。实则只要对比下图一对应的位置是否全为陆地就行了。

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
int flag;
void dfs(int** grid1, int** grid2, int m, int n, int i, int j){
    if(i<0||i>=m||j<0||j>=n||grid2[i][j]==0)
        return;
    //如果岛屿1对应的位置有水，则说明不合题意
    if(grid1[i][j]==0)
        flag=false;
    grid2[i][j]=0;
    dfs(grid1,grid2,m,n,i,j+1);
    dfs(grid1,grid2,m,n,i+1,j);
    dfs(grid1,grid2,m,n,i,j-1);
    dfs(grid1,grid2,m,n,i-1,j);
}

int countSubIslands(int** grid1, int grid1Size, int* grid1ColSize, int** grid2, int grid2Size, int* grid2ColSize) {
    int m=grid1Size,n=grid1ColSize[0];
    int counter=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid2[i][j]==1){
                flag=true;
                dfs(grid1,grid2,m,n,i,j);
                if(flag)
                    counter++;
            }
        }
    }
    return counter;
}

科软真题

1.位1的个数

题解：就这你给我扯什么位运算？

1
2
3
4
5
6
7
8
9
int hammingWeight(int n) {
    int counter=0;
    while(n!=0){
        if(n%2)
            counter++;
        n/=2;
    }
    return counter;
}

2.七进制数

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

题解：加上终止符，记得处理负数和 0 的情况。

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
char* convertToBase7(int num) {
    char *result=malloc(sizeof(char)*10000);
    int index=0;
    bool flag=0;
    if(num==0){
        result[0]='0';
        result[1]='\0';
        return result;
    }
    if(num<0){
        num=-num;
        flag=1;
    }
    while(num!=0){
        result[index++]='0'+num%7;
        num=num/7;
    }
    //负数则补上负号
    if(flag)
        result[index++]='-';
    //反转字符串
    for(int i=0;i<index/2;i++){
        char temp=result[i];
        result[i]=result[index-i-1];
        result[index-i-1]=temp;
    }
    result[index]='\0';
    return result;
}

3.数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。 答案字符串中的所有字母都应该是小写字符，并且除了 0 本身之外，答案中不应该有任何前置零。

题解：unsigned 神力，直接解决了补码的问题。

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
char* toHex(int num) {
    char *result=malloc(sizeof(char)*9);
    int index=0;
    if(num==0){
        result[0]='0';
        result[1]='\0';
        return result;
    }
    unsigned int x=num;
    while(x!=0){
        if(x%16<10)
            result[index++]='0'+x%16;
        else
            result[index++]='a'+x%16-10;
        x=x/16;
    }
    //翻转字符串
    for(int i=0;i<index/2;i++){
        char temp=result[i];
        result[i]=result[index-i-1];
        result[index-i-1]=temp;
    }
    result[index]='\0';
    return result;
}

4.单调数列

题解：这题好像比我想的有意思。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isMonotonic(int* nums, int numsSize) {
    if(numsSize<=2)
        return true;
    //两个标记，一个表示有递增，一个表示有递减
    bool flag[2]={0,0};
    for(int i=1;i<numsSize;i++){
        if(nums[i]>nums[i-1])
            flag[0]=1;
        else if(nums[i]<nums[i-1])
            flag[1]=1; 
        //判断是否同时出现两种类型  
        if(flag[0]&&flag[1])
            return false;             
    }
    return true;
}

5.最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。

题解：我真是甜菜，把它和有序的数组比较一下看看哪里不一样不就行了吗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

int findUnsortedSubarray(int* nums, int numsSize) {
    int *temp=malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++)
        temp[i]=nums[i];
    qsort(temp,numsSize,sizeof(int),cmp);
    //记录第一个和最后一个和原数组不同的数字的下标
    int left=0,right=numsSize-1;
    while(left<numsSize&&nums[left]==temp[left])
        left++;
    //如果全都一样，说明有序
    if(left==numsSize)
        return 0;
    while(right>=0&&nums[right]==temp[right])
        right--;
    return right-left+1;
}

6.最大交换

题解：本来是直接对 num 进行修改的，导致 num 变成了 0，然后直接返回 num 时输出结果一直为 0。找半天不知道哪错了... 这件事告诉我们不要随便修改传进来的参数，不然自己也会忘的。

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
int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}
int maximumSwap(int num) {
    if(num==0)
        return 0;
    int *nums=malloc(sizeof(int)*9);
    int size=0, numx=num;
    while(numx!=0){
        nums[size++]=numx%10;
        numx=numx/10;
    }
    //重新复制一个，进行排序后与原数组进行比较
    int *temp=malloc(sizeof(int)*size);
    for(int i=0;i<size;i++)
        temp[i]=nums[i];
    qsort(temp,size,sizeof(int),cmp);
    //找到那个最大的需要交换的数字
    int right=size-1, left=0;
    while(right>=0&&nums[right]==temp[right])
        right--;
    //未找到说明不需要交换
    if(right<=0)
        return num;
    //从原数组最左边找到相同的值
    while(left<size&&nums[left]!=temp[right])
        left++;
    //寻找完毕，开始交换
    int x=nums[left];
    nums[left]=nums[right];
    nums[right]=x;

    //把nums拼回去
    int result=0;
    for(int i=size-1;i>=0;i--)
        result=result*10+nums[i];

    return result;
}

7.反转字符串中的元音字母

题解：我没招了，测试用例里面怎么什么字符都有，被迫开个 flag 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char* reverseVowels(char* s) {
    int len=strlen(s),top=0;
    char* temp=malloc(sizeof(char)*len);
    bool *flag=malloc(sizeof(bool)*len);
    for(int i=0;i<len;i++)
        flag[i]=false;
    for(int i=0;i<len;i++){
        if(s[i]=='a'||s[i]=='o'||s[i]=='e'||s[i]=='i'||s[i]=='u'
            ||s[i]=='A'||s[i]=='O'||s[i]=='E'||s[i]=='I'||s[i]=='U'){
                temp[top++]=s[i];
                flag[i]=true;//作为标记
            }
    }
    for(int i=0;i<len;i++){
        if(flag[i])
            s[i]=temp[--top];
    }
    return s;
}

8.让字符串成为回文串的最少插入次数

题解：诶，hard 题我怎么一遍过啊，真的假的？

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
int min(int a, int b){
    return a<=b?a:b;
}
int minInsertions(char* s) {
    int len=strlen(s);
    int **dp=malloc(sizeof(int*)*len);
    for(int i=0;i<len;i++){
        dp[i]=malloc(sizeof(int)*len);
        for(int j=0;j<len;j++)
            dp[i][j]=0;
    }
    for(int i=len-2;i>=0;i--){
        //从i+1开始，如果等于i，只有单个字符，一定是回文串
        for(int j=i+1;j<len;j++){
            //如果前后相同
            if(s[i]==s[j]){
                //如果长度只有2或3，一定是回文
                if(j==i+1&&j==i+2)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i+1][j-1];
            }
            //如果不同,插入一个字符
            else
                dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
        }
    }
    return dp[0][len-1];
}

9.字符串中第二大的数字

题解：记得把字符转换成数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int secondHighest(char* s) {
    int max[2]={-1,-1},len=strlen(s),k;
    for(int i=0;i<len;i++){
        //把字符转换成数字
        k=s[i]-'0';
        if(k>=0&&k<=9){
            if(k>max[0]){
                max[1]=max[0];
                max[0]=k;
            }
            else if(k<max[0]&&k>max[1])
                max[1]=k;
        }
    }
    return max[1];
}

10.找出数组的最大公约数

题解：捡捡蛋蛋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int min(int a,int b){
    return a<=b?a:b;
}
int max(int a,int b){
    return a>=b?a:b;
}
int findGCD(int* nums, int numsSize) {
    int Min=nums[0],Max=nums[0];
    for(int i=1;i<numsSize;i++){
        Min=min(Min,nums[i]);
        Max=max(Max,nums[i]);
    }
    int result=Min;
    while(Max%result!=0||Min%result!=0)
        result--;
    return result;
}

11.划分数字的方案数

你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。

请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

题解：先回溯暴力大法，虽然超时了（优化了一下，不会超时了，但数字还是会溢出，不过拿一部分够了）。

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
int counter;
unsigned long long *path;
int top;

void backing(char* num, int len, int start){
    //成功到达最后
    if(start>=len){
        counter++;
        return;
    }
    for(int i=start;i<len;i++){
        //如果有前导0，直接回退
        if(num[start]=='0')
            return;
    
        //计算出切割出的数字大小并存入
        unsigned long long sum=0;
        for(int j=start;j<=i;j++){
            sum=sum*10+(num[j]-'0');
        }

        //如果比上一个数小，则计算下一个
        if(top>0&&sum<path[top-1])
            continue;
        //符合条件，则存入数组
        path[top++]=sum;
        //进入下一层
        backing(num,len,i+1);
        //回退
        top--;
    }
}

int numberOfCombinations(char* num) {
    int len=strlen(num);
    path=malloc(sizeof(unsigned long long)*len);
    top=0;
    counter=0;
    backing(num,len,0);
    return counter;
}

题解：动态规划。

1

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

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//左闭右开
void reverse(char *s,int start,int end){
    int time=(end-start+1)/2;
    for(int i=0;i<time;i++){
        char temp=s[start+i];
        s[start+i]=s[end-1-i];
        s[end-1-i]=temp;
    }
}
char* reverseWords(char* s) {
    int start=0,end=0,len=strlen(s);
    while(start<len){
        for(int i=start;i<=len;i++){
            if(s[i]==' '||s[i]=='\0'){
                end=i;
                break;
            }
        }
        reverse(s,start,end);
        start=end+1;
    }
    return s;
}

13.Excel 表列序号

题解：今年也多来点 easy 好吗？

1
2
3
4
5
6
7
int titleToNumber(char* columnTitle) {
    int sum=0,len=strlen(columnTitle);
    for(int i=0;i<len;i++){
        sum=sum*26+(columnTitle[i]-'A'+1);
    }
    return sum;
}

14.Excel 表列名称

题解：不对，这好像不是单纯的26进制... 斯，0 真是个伟大的数字...

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
char* convertToTitle(int columnNumber) {
    char *result=malloc(sizeof(char)*9);
    int top=0;
    while(columnNumber>=1){
        if(columnNumber%26==0){
            result[top++]='Z';
            columnNumber=columnNumber/26-1;
        }
        else{
            result[top++]='A'+columnNumber%26-1;
            columnNumber=columnNumber/26;
        }
    }
    result[top]='\0';
    //反转字符串
    int left=0,right=top-1;
    while(left<right){
        char temp=result[left];
        result[left]=result[right];
        result[right]=temp;
        left++;
        right--;
    }
    return result;
}

15.黄金矿工

题解：叽里咕噜说什么呢，直接全局变量加回溯。

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
int max;
int value;
bool **flag;

void dfs(int** grid, int m, int n, int i,int j){
    if(i<0||i>=m||j<0||j>=n||grid[i][j]==0||flag[i][j])
        return;
    
    value+=grid[i][j];
    flag[i][j]=1;
    max=max>=value?max:value;

    dfs(grid,m,n,i,j+1);//右
    dfs(grid,m,n,i+1,j);//下
    dfs(grid,m,n,i,j-1);//左
    dfs(grid,m,n,i-1,j);//上
    value-=grid[i][j];
    flag[i][j]=0;
}

int getMaximumGold(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize;
    int n=gridColSize[0];
    value=0;
    max=0;
    flag=malloc(sizeof(bool*)*m);
    for(int i=0;i<m;i++){
        flag[i]=malloc(sizeof(bool)*n);
        for(int j=0;j<n;j++)
            flag[i][j]=false;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]!=0)
                dfs(grid,m,n,i,j);
        }
    }
    return max;
}

16.不同路径 III

题解：依旧回溯法深度遍历。

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
int counter;
int step;
bool **flag;

void dfs(int** grid, int m, int n, int i, int j, int num_0){
    if(i<0||i>=m||j<0||j>=n||flag[i][j]||grid[i][j]==-1){
        return;
    }
    //到达终点
    if(grid[i][j]==2){
        //如果走过所有的空白点
        printf("step=%d\n",step);
        if(step==num_0+1)
            counter++;
        return;
    }
    //步数加一
    step++;
    flag[i][j]=true;

    dfs(grid,m,n,i,j+1,num_0);
    dfs(grid,m,n,i+1,j,num_0);
    dfs(grid,m,n,i,j-1,num_0);
    dfs(grid,m,n,i-1,j,num_0);
    //回退
    step--;
    flag[i][j]=false;
}

int uniquePathsIII(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize, n=gridColSize[0];

    flag=malloc(sizeof(bool*)*m);
    for(int i=0;i<m;i++){
        flag[i]=malloc(sizeof(bool)*n);
        for(int j=0;j<n;j++)
            flag[i][j]=false;
    }
    
    counter=0;
    step=0;

    //寻找起点并记录空白格数量
    int num_0=0,x=0,y=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                x=i;
                y=j;
            }
            else if(grid[i][j]==0)
                num_0++;
        }
    }
    dfs(grid,m,n,x,y,num_0);
    return counter;
}

17.最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

题解：DP 又快又简单啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int min(int a, int b){
    return a<=b?a:b;
}

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int m=gridSize,n=gridColSize[0];
    int **dp=malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++){
        dp[i]=malloc(sizeof(int)*n);
    }
    dp[0][0]=grid[0][0];
    for(int i=1;i<m;i++)
        dp[i][0]=dp[i-1][0]+grid[i][0];
    for(int j=1;j<n;j++)
        dp[0][j]=dp[0][j-1]+grid[0][j];

    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

18.矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

题解：暴力回溯法，因为题目要求数字递增，所以不需要额外记录节点是否访问过，但还是会超时。

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
int max;
int len;

void dfs(int **matrix, int m, int n, int i, int j, int pre){
    if(i<0||i>=m||j<0||j>=n||matrix[i][j]<=pre){
        if(max<len)
            max=len;
        return;
    }
    len++;
    dfs(matrix,m,n,i,j+1,matrix[i][j]);
    dfs(matrix,m,n,i+1,j,matrix[i][j]);
    dfs(matrix,m,n,i,j-1,matrix[i][j]);
    dfs(matrix,m,n,i-1,j,matrix[i][j]);
    len--;
}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    int m=matrixSize,n=matrixColSize[0];
    max=0;
    len=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            dfs(matrix,m,n,i,j,-1);
        }
    }
    return max;
}

题解：记忆化搜索。起初 for 循环遍历四个方向时，依旧使用了 i 变量，导致参数传进来的 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
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int dfs(int **matrix, int m, int n, int i, int j, int **dp){
    //如果不是-1，说明这个点已经被计算过最长路径
    if(dp[i][j]!=-1)
        return dp[i][j];
    //确保自身这一步被算上
    int maxlen=1;
    //别再用变量i了，用k吧
    for(int k=0;k<4;k++){
        int x=i+dir[k][0];
        int y=j+dir[k][1];
        //找到四个方向最长的
        if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]){
            int len=1+dfs(matrix,m,n,x,y,dp);
            if(len>maxlen)
                maxlen=len;
        }
    }
    dp[i][j]=maxlen;
    return maxlen;
}

int longestIncreasingPath(int** matrix, int matrixSize, int* matrixColSize) {
    int m=matrixSize,n=matrixColSize[0];
    int **dp=malloc(sizeof(int*)*m);
    for(int i=0;i<m;i++){
        dp[i]=malloc(sizeof(int)*n);
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }

    int maxlen=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            int len=dfs(matrix,m,n,i,j,dp);
            if(len>maxlen)
                maxlen=len;
        }
    }
    return maxlen;
}

模拟考试

2.特殊子序列

小问有一个长度为 n 的字符串 s，字符串中只包含大写字母 A、B、C。一个子序列是指从 s 中按顺序取出若干个字符（可以不连续，但保持原有顺序）组成的序列，且如果两个子序列在原字符串中的下标集合不同，则认为它们是不同的子序列。 现在，小问想知道，有多少种取法得到的子序列满足以下所有条件：

  • 子序列的长度至少为 3 。

  • 子序列的第一个字符是 A。

  • 子序列的最后一个字符是 C。

  • 除第一个和最后一个字符外，子序列中的其他字符全都是 B。

由于答案可能很大，请将答案对 10^9 + 7 取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MOD 1000000007;

int solve(int n, char s[]) {
    //定义三种状态
    long long a=0,ab=0,abc=0;
    for(int i=0;i<n;i++){
        if(s[i]=='A')
            a++;
        else if(s[i]=='B')
            //前面的ab串可以选择加或不加这个B,因此有2ab种
            ab=ab*2+a;
        else
            abc = (abc + ab) % MOD;
    }
    return (int)abc;
}

113.路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

  • 树中节点总数在范围 [0, 5000] 内

  • -1000 <= Node.val <= 1000

  • -1000 <= targetSum <= 1000

题解：二叉树的回溯？自己写出来了，还行，注意节点的值可能是负数。就是不知道会不会考树。

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
int **result;
int resultTop;
int *path;
int pathTop;
int *lens;
int sum;

void search(struct TreeNode* root,int target){
    //处理本节点
    sum+=root->val;
    //加入路径
    path[pathTop++]=root->val;
    //如果是叶子节点
    if(root->left==NULL&&root->right==NULL){
        //符合条件，存入最终结果
        if(target==sum){
            int *temp=malloc(sizeof(int)*pathTop);
            for(int i=0;i<pathTop;i++)
                temp[i]=path[i];
            result[resultTop]=temp;
            lens[resultTop++]=pathTop;
        }
        //回退
        pathTop--;
        sum-=root->val;
        return;
    }
    if(root->left!=NULL){
        search(root->left,target);
    }
    if(root->right!=NULL){
        search(root->right,target);
    }
    //回退
    pathTop--;
    sum-=root->val;
}

int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes) {
    result=malloc(sizeof(int*)*5000);
    resultTop=0;
    path=malloc(sizeof(int)*5000);
    pathTop=0;
    lens=malloc(sizeof(int)*5000); 
    sum=0;

    if(root==NULL)
        return result;

    search(root,targetSum);

    *returnSize=resultTop;
    *returnColumnSizes=malloc(sizeof(int)*resultTop);
    for(int i=0;i<resultTop;i++){
        (*returnColumnSizes)[i]=lens[i];
    }
    return result;
}