Leetcode刷题笔记（简单）

1 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII，即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

实例：

1
2
3
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
1
2
3
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思想

2 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2
输入：nums = [3,3], target = 6
输出：[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
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j, first, second, mask = 0;
    int *array;
    array = (int *)malloc(2 * sizeof(int));
    for(i = 0; i < numsSize; i++) {
        first = *(nums + i);
        second = target - first;
        for(j = i + 1; j < numsSize; j++) {
            if(*(nums + j) != second) {
                continue;
            } else {
                mask = 1;
                break;
            }
        }
        if(mask == 1) {
            break;
        }
    }
    array[0] = i;
    array[1] = j;
    // 设置返回数组的大小
    *returnSize = 2;
    return array;
}
  • 时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
  • 空间复杂度：O(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
struct hashTable {
    int key; // 键：数组中的值
    int val; // 值：该值对应的下标
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) { // 找到
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        // 没有找到，则插入
        insert(nums[i], i);
    }
    // 没有找到
    *returnSize = 0;
    return NULL;
}

补充：C语言中的哈希表

uthash是C语言比较优秀的开源代码。它实现了常见的hash函数，例如插入、查找、删除等功能。它支持C语言的任意数据类型做为key值，无论是基本数据类型还是自定义的struct，但是不同类型的key其操作接口方式略有不同，而且它甚至可以采用多个值作为key。由于该代码采用宏的方式实现，所有的实现代码都在uthash.h文件中，因此只需要在自己的代码中包含"uthash.h"头文件即可。

  • 定义hash结构体
1
2
3
4
5
6
7
8
9
10
#include "uthash.h"
 
struct my_struct {
    int id; /* key */
    char name[10]; /* val */
    UT_hash_handle hh; /* makes this structure hashable hh不需要初始化。它可以命名为任何名称，但是我们一般都命名为hh */
};

/*声明哈希为NULL指针*/
struct my_struct *users = NULL;    /* important! initialize to NULL */
  • key的类型

uthash支持任意类型的key（键），包括整型、字符串、指针、结构体等。如果key类型不同，那么add和find函数有不同的接口，但是HASH_DELETE和HASH_SORT不区分key类型。结构体的一个或者多个成员构成键，结构体指针本身作为值。

  • 操作接口

操作接口根据key的类型分为int，string和ptr三种类型。这三种类型又可以分为添加（ADD），查找（FIND）和替换（REPLACE）三种操作方式。

对于删除（DEL），排序（SORT）和计数（COUNT），不分key的类型。

head为定义的结构体（例如users）。

macro arguments
HASH_ADD_INT (head, keyfield_name, item_ptr)
HASH_REPLACE_INT (head, keyfield_name, item_ptr, replaced_item_ptr)
HASH_FIND_INT (head, key_ptr, item_ptr)
HASH_ADD_STR (head, keyfield_name, item_ptr)
HASH_REPLACE_STR (head, keyfield_name, item_ptr, replaced_item_ptr)
HASH_FIND_STR (head, key_ptr, item_ptr)
HASH_ADD_PTR (head, keyfield_name, item_ptr)
HASH_REPLACE_PTR (head, keyfield_name, item_ptr, replaced_item_ptr)
HASH_FIND_PTR (head, key_ptr, item_ptr)
HASH_DEL (head, item_ptr)
HASH_SORT (head, cmp)
HASH_COUNT (head)
  • 添加
    • HASH_ADD_INT表示添加的键为int类型
    • HASH_ADD_STR表示添加的键为字符串类型
    • HASH_ADD_PTR表示添加的键为指针类型
    • HASH_ADD表示添加的键可以是任意类型

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct my_struct {
    int id; /* key */
    char name[10]; /* val */
    UT_hash_handle hh;
};

struct my_struct *users = NULL; 

void add_user(int user_id, char *name) {
    struct my_struct *s;
    /*重复性检查，当把两个相同key值的结构体添加到哈希表中时会报错*/
    HASH_FIND_INT(users, &user_id, s);
    /*只有在哈希中不存在ID的情况下，我们才创建该项目并将其添加。否则，我们只修改已经存在的结构。*/
    if (s == NULL) {
    	s = (struct my_struct *)malloc(sizeof *s);
    	s->id = user_id;
    	HASH_ADD_INT(users, id, s);  /* id: name of key field */
    }
    strcpy(s->name, name);
}

HASH_ADD_INT函数中，第一个参数users是哈希表，第二个参数id是键字段的名称。最后一个参数s是指向要添加的结构的指针。

  • 查找
1
2
3
4
5
6
struct my_struct *find_user(int user_id) {
    struct my_struct *s;
    s = (struct my_struct *)malloc(sizeof *s);
    HASH_FIND_INT(users, &user_id, s);  /* s: output pointer */
    return s;
}

在上述代码中，第一个参数users是哈希表，第二个参数是user_id的地址（一定要传递地址）。最后s是输出变量。当可以在哈希表中找到相应键值时，s返回给定键的结构，当找不到时s返回NULL。

3 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

1
2
3
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
1
2
3
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
1
2
输入：digits = [0]
输出：[1]

注意：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

代码示例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
61
62
63
64
65
66
67
68
69
70
71
72
#include "utstack.h"

typedef struct item {
    int val;
    struct item *next;
}item;

item *stack1 = NULL;
item *stack2 = NULL;

int* plusOne(int* digits, int digitsSize, int* returnSize){
    int i;
    // 进位标志
    int mask = 0;
    // 是否是末尾数
    int last = 1;
    // stack2栈的大小
    int count;
    item *count_tmp;
    // 出栈的数值
    int top;
    for(i = 0; i < digitsSize; i++) {
        item *tmp = (item *)malloc(sizeof(item));
        tmp -> val = *(digits + i);
        STACK_PUSH(stack1, tmp);
    }
    // stack1出栈，末尾数加1并入栈
    while(!STACK_EMPTY(stack1)) {
        item *tmp = (item *)malloc(sizeof(item));
        STACK_POP(stack1, tmp);
        top = tmp -> val;
        if(last) { // 末尾数
            top += 1;
            item *tmp = (item *)malloc(sizeof(item));
            mask = (top == 10) ? 1 : 0;
            tmp -> val = (top == 10) ? 0 : top;
            STACK_PUSH(stack2, tmp);
            last = 0; // 末尾处理后将last置为0
        } else { // 不是末尾数
            if(mask) { // 有进位
                top += 1;
                item *tmp = (item *)malloc(sizeof(item));
                mask = (top == 10) ? 1 : 0;
                tmp -> val = (top == 10) ? 0 : top;
                STACK_PUSH(stack2, tmp);
            } else { // 没有进位
                item *tmp = (item *)malloc(sizeof(item));
                tmp -> val = top;
                STACK_PUSH(stack2, tmp);
            }
        }
    }
    // 结束循环时，如果进位标志还为1，则再入栈1
    if(mask) {
        item *tmp = (item *)malloc(sizeof(item));
        tmp -> val = 1;
        STACK_PUSH(stack2, tmp);
    }
    STACK_COUNT(stack2, count_tmp, count);
    *returnSize = count;
    int *array = (int *)malloc(count * sizeof(int));
    i = 0;
    // stack2出栈
    while(!STACK_EMPTY(stack2)) {
        item *tmp = (item *)malloc(sizeof(item));
        STACK_POP(stack2, tmp);
        top = tmp -> val;
        array[i] = top;
        i++;
    }
    return array;
}

代码示例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int* plusOne(int* digits, int digitsSize, int* returnSize){
    for(int i = digitsSize - 1; i >= 0; --i){
        digits[i] = digits[i] + 1;//最后元素+1判断是不是10
        //如果当前元素不为10，直接返回数组
        if(digits[i] != 10){
            *returnSize = digitsSize;
            return digits;
        }
        //第一个元素不为10，后面元素均为10的情况
        if(digits[i] == 10)
            digits[i] = 0;
    }
    //元素全为9开辟新数组
    int* ans = malloc(sizeof(int) * (digitsSize + 1));
    memset(ans, 0, sizeof(int) * (digitsSize + 1));//全部置0
    ans[0] = 1;
    *returnSize = digitsSize + 1;
    return ans;
}

memset函数

1
void memset(void *s, char ch, unsigned n);

函数功能：将s为首地址的一片连续的n个字节内存单元都赋值为ch

4 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

直接合并后排序

1
2
3
4
5
6
7
8
9
10
int cmp(int* a, int* b) {
    return *a - *b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = 0; i != n; ++i) {
        nums1[m + i] = nums2[i];
    }
    qsort(nums1, nums1Size, sizeof(int), cmp);
}

qsort函数：使用快速排序例程进行排序，这个函数是根据二分法写的，其时间复杂度为n*log(n)

1
2
#include<stdlib.h>
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *))
  • base：待排序数组首地址（可直接输入待排序数组名，或是指向数组的指针）
  • nelem：数组中待排序元素数量（可以用sizeof来求）
  • width：各元素的占用空间大小（可以用sizeof(arr[0])来求）
  • fcmp：指向函数的指针

qsort需要我们自己创建一个比较函数，基本都是这个函数：

1
2
3
4
int cmp(const void* a, const void* b) {
	return *a - *b; // 从小到大排
    // return *b - *a; 从大到小排
}

双指针

将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。

为两个数组分别设置一个指针 p_1 与 p_2 来作为队列的头部指针。代码实现如下：

gif1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = 0, p2 = 0;
    int sorted[m + n];
    int cur;
    while (p1 < m || p2 < n) {
        if (p1 == m) {
            cur = nums2[p2++];
        } else if (p2 == n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (int i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
}

5 买卖股票的最佳时机

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

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

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

示例：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(int* prices, int pricesSize){
    int i, j, max = 0;
    int cur;
    for(i = 0; i < pricesSize - 1; i++) {
        cur = prices[i];
        for(j = i + 1; j < pricesSize; j++) {
            if((prices[j] - cur) > max) {
                max = prices[j] - cur;
            }
        }
    }
    return max;
}

一次遍历

假设给定的数组为：[7, 1, 5, 3, 6, 4]（注意这组数[2,5,1,3]）

如果我们在图表上绘制给定数组中的数字，我们将会得到：

image-20230104112529588

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(int* prices, int pricesSize){
    int i;
    int max = 0;
    int min = INT_MAX;
    for(i = 0; i < pricesSize; i++) {
        if(prices[i] < min) {
            min = prices[i]; // 更新最小值
        } else if ((prices[i] - min) > max) {
            max = prices[i] - min; // 更新最大值
        }
    }
    return max;
}

单调栈

单调栈：栈中元素以单增或单减的关系排列。在这里维护一个单增的栈。

算法：

  • 在 prices 数组的末尾加上一个 哨兵（也就是一个很小的元素，这里设为 0）
  • 假如栈空或者入栈元素大于栈顶元素，直接入栈（单增栈）
  • 假如入栈元素小于栈顶元素则循环弹栈，直到入栈元素大于栈顶元素或者栈空
  • 在每次弹出的时候，我们拿他与买入的值(也就是栈底)做差，维护一个最大值。

以时间序列[7, 1, 5, 3, 6, 4]为例，灰色的为扫描过的。

第一步，栈空，扫描的是 77，我们直接入栈。

image-20230104115256607

第二步，入栈元素为 1，他比栈顶元素小，为了维护这个单调栈，我们把7弹出，又因为他即是栈底又是栈顶所以不需要更新我们的最大值，又因为弹出之后为空，我们将1直接入栈我们直接入栈。

image-20230104115330582

第三步，入栈元素为 5，他比栈顶元素大，我们直接入栈

image-20230104115343248

第四步，入栈元素为 3，他比栈顶元素 5 小，我们直接弹栈，并拿他（5）减去栈底元素1

image-20230104115447486

第五步，入栈元素为 6 ，比栈顶元素3大，入栈。

image-20230104115533364

第六步，入栈元素为 4，比栈顶元素 6小，根据我们刚刚的理论，在遇上 4 之后，6的最高利润已经确定了，因为无论后面遇上怎么样的升值，在 4 的时候购买的利润显然更高 所以我们弹出 6，并与栈底(也就是我们买入的价值)做差，并与我们之前维护的最大值进行比较，然后更新。

image-20230104115606776

第七步，现在 哨兵的作用就非常清楚啦，假如没有哨兵，我们单调栈中还有残留的元素没有进行判断(比如 prices 数组单调增的情况下，不加哨兵会出现 max=0 的情况)，因此 哨兵的作用就是确保单调栈中的每个元素都被进行判定。因此最后的图像应该是这样：

image-20230104115627881

单调栈的作用是：用O(n) 的时间得知所有位置两边第一个比他大(或小)的数的位置。

6 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

1
2
3
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。
1
2
3
输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为4。
1
2
3
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为6的“joyboy”。
  • 1 <= s.length <= 104
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

正向遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLastWord(char * s){
    int len = strlen(s);
    int res = 0, tmp = 0;
    int flag = 1;
    int i;
    for(i = 0; i < len; i++) {
        if(s[i] != ' ') {
            tmp++;
            flag = 1;
        } else if(flag) {
            flag = 0;
            res = tmp;
            tmp = 0;
        }
    }
    return flag ? tmp : res;
}

反向遍历

题目要求得到字符串中最后一个单词的长度，可以反向遍历字符串，寻找最后一个单词并计算其长度。

由于字符串中至少存在一个单词，因此字符串中一定有字母。首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。

从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLastWord(char * s){
    int len = strlen(s);
    int res = 0, flag = 0;
    int i;
    for (i = len - 1; i != -1; i--) {
        if(s[i] == ' ') {
            if(flag == 0) {
                continue;
            } else {
                return res;
            }
        } else {
            flag = 1;
            res+=1;
        }
    }
    return res;
}

7 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

双指针法

image-20230105115001655

1
2
3
4
5
6
7
8
9
10
11
void swap(char *a, char *b) {
    char t = *a;
    *a = *b;
    *b = t;
}

void reverseString(char *s, int sSize) {
    for (int left = 0, right = sSize - 1; left < right; ++left, --right) {
        swap(s + left, s + right);
    }
}

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reverseString(char* s, int sSize){
    int i;
    if(sSize == 1) {
        return ;
    } else {
        int mid = sSize / 2;
        for(i = 0; i < mid; i++) {
            char tmp;
            tmp = s[i];
            s[i] = s[sSize-i-1];
            s[sSize-i-1] = tmp;
        }
    }
}

8 数组中的重复数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

1
2 <= n <= 100000

哈希表

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
struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

int insert(int ikey, int ival) {
    struct hashTable* tmp = find(ikey);
    if(tmp != NULL) {
        return -1;
    } else {
        tmp = (struct hashTable*)malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
        return 0;
    }
    return -1;
}

int findRepeatNumber(int* nums, int numsSize){
    // 在函数中初始化全局变量
    hashtable = NULL;
    int i;
    struct hashTable* tmp;
    for(i = 0; i < numsSize; i++) {
        if(insert(nums[i], i) == -1){
            return nums[i];
        }
    }
    return 0;   
}

注意：执行代码返回结果正确，但提交解答却出错的原因：

对于全局变量，leetcode对后面的测试用例会接着使用前面的全局变量。如果在全局变量声明处初始化的话，会造成错误：

1
2
3
4
5
6
struct hashTable* hashtable = NULL;

// ..
int findRepeatNumber(int* nums, int numsSize){
    // ...
}

解决办法是：在函数中初始化全局变量。这样对所有的测试用例，每次执行该函数时，都会初始化全局变量，这样保证全局变量从新开始。

9 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"
1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[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
char * longestCommonPrefix(char ** strs, int strsSize){
    int i, j, count = 0;
    if(strlen(strs[0]) == 0) {
        return "";
    }
    // 第i个位置
    for(i = 0; i < strlen(strs[0]); i++) {
        char c = strs[0][i];
        // 第j个字符串
        for(j = 1; j < strsSize; j++) {
            if(i >= strlen(strs[j])) {
                goto label;
            } else if (c == strs[j][i]) {
                continue;
            } else {
                goto label;
            }
        }
        count += 1;
    }
label:
    strs[0][count] = '\0';
    return strs[0];
}

或者动态分配一个count+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
char * longestCommonPrefix(char ** strs, int strsSize){
    int i, j, count = 0;
    if(strlen(strs[0]) == 0) {
        return "";
    }
    // 第i个位置
    for(i = 0; i < strlen(strs[0]); i++) {
        char c = strs[0][i];
        // 第j个字符串
        for(j = 1; j < strsSize; j++) {
            if(i >= strlen(strs[j])) {
                goto label;
            } else if (c == strs[j][i]) {
                continue;
            } else {
                goto label;
            }
        }
        count += 1;
    }
    // 变量声明放在label之前
    char* res;
label:
    res = (char *)malloc((count+1) * sizeof(char));
    for(i = 0; i < count; i++) {
        res[i] = strs[0][i];
    }
    // 将最后一个位置的字符置为空字符，表示字符串
    res[count] = '\0';
    return res;
}

注意不能这样写：

1
2
label:
    char* res = (char *)malloc((count+1) * sizeof(char));

报错：

1
a label can only be part of a statement and a declaration is not a statement

原因：label之后进行变量的声明而导致的错误。

解决：label后的所有变量的声明放在label之前，或者用大括号将label之后的部分包裹起来。

例如：

1
2
3
4
5
6
7
8
9
10
11
// ...
label:{
        char* res = (char *)malloc((count+1) * sizeof(char));
        for(i = 0; i < count; i++) {
            res[i] = strs[0][i];
        }
        res[count] = '\0';
        return res;
}
// 默认返回，注意不能返回res，因为上面的res只在label代码块中可见
return "";

10 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成%20

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

限制：

1
0 <= s 的长度 <= 10000

代码示例

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
char* replaceSpace(char* s){
    int i;
    int count = 0;
    // 计算空格的个数
    for(i = 0; i < strlen(s); i++) {
        if(s[i] == ' ') {
            count+=1;
        }
    }
    // 替换后的字符串长度，注意留一个位置存储空字符
    int size = count*3-count+strlen(s)+1;
    char* res = (char *)malloc(size * sizeof(char));
    int j = 0;
    for(i = 0; i < strlen(s); i++) {
        if(s[i] == ' ') {
            res[j] = '%';
            res[j+1] = '2';
            res[j+2] = '0';
            j+=3;
        } else {
            res[j] = s[i];
            j+=1;
        }
    }
    // 最后一个位置设置为空字符
    res[size-1] = '\0'; 
    return res;
}

11 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例：

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

代码示例——二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int search(int* nums, int numsSize, int target){
    // 左边界和右边界
    int left = 0, right = numsSize - 1;
    // 循环条件：左边界在右边界左边
    while(left <= right) {
        int mid = (right - left) / 2 + left;
        int num = nums[mid];
        if(num == target) {
            return mid;
        } else if (num > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

注意，二分法只适用于有序元素的查找。

细节：

求中间的位置时，可以使用：

1
int mid = (left + right) / 2;

但是数组很大的话，相加后可能导致整数溢出，因此做了恒等变形，现将两个整数相减，再相加，防止int越界：

1
int mid = (right - left) / 2 + left;

12 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例：

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

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

方法1——排序

在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cmp(const void* _a, const void* _b) {
    int a = *(int*)_a, b = *(int*)_b;
    return a - b;
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

方法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
typedef struct hashtable {
    int key;
    int val;
    UT_hash_handle hh;
} hashtable;

hashtable* table;

bool containsDuplicate(int* nums, int numsSize){
    table = NULL;
    int i;
    for(i = 0; i < numsSize; i++) {
        hashtable* tmp;
        HASH_FIND_INT(table, &nums[i], tmp);
        if(tmp == NULL) {
            tmp = (hashtable*) malloc(sizeof(hashtable));
            tmp->key = nums[i];
            tmp->val = i;
            HASH_ADD_INT(table, key, tmp);
        } else {
            return true;
        }
    }
    return false;
}

13 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例：

1
2
输入: s = "anagram", t = "nagaram"
输出: true
1
2
输入: s = "rat", t = "car"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • 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
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
typedef struct hashtable {
    // 字符
    int key;
    // 字符出现的次数
    int count;
    UT_hash_handle hh;
} hashtable;

hashtable * table;

hashtable* find(int ikey) {
    hashtable* tmp;
    HASH_FIND_INT(table, &ikey, tmp);
    return tmp;
}

bool isAnagram(char * s, char * t){
    table = NULL;
    int s_len = strlen(s);
    int t_len = strlen(t);
    // 两个字符串长度不等，直接返回false
    if(s_len != t_len) {
        return false;
    }
    // 将s字符串添加进哈希表
    int i;
    for(i = 0; i < s_len; i++) {
        hashtable* item = find((int)s[i]);
        if(item == NULL) {
            item = (hashtable*)malloc(sizeof(hashtable));
            item->key = (int)s[i];
            item->count = 1;
            HASH_ADD_INT(table, key, item);
        } else {
            item->count = item->count + 1;
        }
    }
    int count_old;
    // 遍历t字符串
    for(i = 0; i < t_len; i++) {
        hashtable* item = find((int)t[i]);
        if(item == NULL) {
            // 没找到返回false
            return false;
        } else {
            count_old = item->count;
            if(count_old == 1) { // 只有一个字符，则从表中删除
                HASH_DEL(table, item);
            } else { // 否则减1个计数
                item->count = item->count - 1;
            }
        }
    }
    return true;
}

注意：不要返回函数终止时不再存在的内存单元的指针或引用

  • 不要返回局部变量的地址
1
2
3
4
5
6
int* func() {
    int tmp = 1; // 局部变量
    return &tmp; // 局部变量的地址
}

int * ptr = func(); // ptr指向被释放的内存地址，error！

image-20230108165854450

  • tmp变量是局部变量，它的内存会被释放，但它所保存的地址不会被释放
1
2
3
4
5
6
7
hashtable* find(int ikey) {
    hashtable* tmp;
    HASH_FIND_INT(table, &ikey, tmp);
    return tmp;
}

hashtable* item = find((int)s[i]);

image-20230108170556926

14 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

img

示例：

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
1
2
输入：head = [], val = 1
输出：[]
1
2
输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

方法——迭代法

用 temp 表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：

1
temp.next = temp.next.next

如果 temp 的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 temp 移动到下一个节点即可。

当 temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 val 的节点都被删除。

具体实现方面，由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令dummyHead.next=head ，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* temp = dummyHead;
    while (temp->next != NULL) {
        if (temp->next->val == val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return dummyHead->next;
}

我的代码

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
struct ListNode* removeElements(struct ListNode* head, int val){
    // 当前节点
    struct ListNode* cur = head;
    while((head != NULL) && (head->val == val)) {
        head = head->next;
        free(cur);
        cur = head;
    }
    if(head == NULL) { // 为空
        return head;
    }
    // 不为空，说明当前节点不等于val
    struct ListNode* pre = head;
    cur = cur->next;
    while(cur != NULL) {
        if(cur->val == val) {
            cur = cur->next;
            free(pre->next);
            pre->next = cur;
        } else {
            pre = pre->next;
            cur = cur->next;
        }
    }
    return head;
}

15 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

方法1——数组保存节点值

思路：先遍历链表，用数组保存各个节点值和总节点数，再次遍历链表，用数组倒序的对应值替换对应节点的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct ListNode* reverseList(struct ListNode* head){
    int val[5000];
    int i = 0;
    struct ListNode* cur = head;
    while(cur != NULL) {
        val[i] = cur->val;
        i+=1;
        cur = cur->next;
    }
    int right = i;
    i = 0;
    cur = head;
    while(cur != NULL) {
        cur->val = val[right-i-1];
        i+=1;
        cur = cur->next;
    }
    return head;
}

方法2——迭代法（原地修改链表）

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1
2
3
4
5
6
7
8
9
10
11
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

16 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct hashtable {
    int key;
    int val;
    UT_hash_handle hh;
} hashtable;

hashtable * table;

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    table = NULL;
    // 设置暂时的数组代大小
    int tmpSize = (nums1Size >= nums2Size) ? nums2Size : nums1Size;
    int* res = (int *)malloc(tmpSize * sizeof(int));
    int i;
    for(i = 0; i < nums1Size; i++) {
        hashtable* item;
        HASH_FIND_INT(table, &nums1[i], item);
        if(item == NULL) {
            item = (hashtable*)malloc(sizeof(hashtable));
            item->key = nums1[i];
            item->val = i;
            HASH_ADD_INT(table, key, item);
        }
    }
    int count = 0; // 交集的个数
    for(i = 0; i < nums2Size; i++) {
        hashtable* item;
        HASH_FIND_INT(table, &nums2[i], item);
        if(item != NULL) {
            res[count] = item->key;
            count+=1;
            HASH_DEL(table, item);
        }
    }
    // 设置返回的大小
    *returnSize = count;
    return res;
}

17 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

实例：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

平方后排序

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

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int i;
    int* res = (int*)malloc(numsSize * sizeof(int));
    for(i = 0; i < numsSize; i++) {
        res[i] = nums[i] * nums[i];
    }
    qsort(res, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return res;
}

双指针

image-20230110094012867

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
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int negative = -1;
    // 找到负数和非负数的分界点
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] < 0) {
            negative = i;
        } else {
            break;
        }
    }
    int* ans = malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    int i = negative, j = negative + 1;
    // 左右指针都溢出则循环结束
    while (i >= 0 || j < numsSize) {
        if (i < 0) { // 左指针溢出，则右指针的数全部加入
            ans[(*returnSize)++] = nums[j] * nums[j];
            ++j;
        } else if (j == numsSize) { // 与上面相反
            ans[(*returnSize)++] = nums[i] * nums[i];
            --i;
        } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
            ans[(*returnSize)++] = nums[i] * nums[i];
            --i;
        } else {
            ans[(*returnSize)++] = nums[j] * nums[j];
            ++j;
        }
    }
    return ans;
}

18 两个数组的交集②

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
1
2
3
4
5
6
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){

}

19 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false
1
2
输入：ransomNote = "aa", magazine = "ab"
输出：false
1
2
输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote 和 magazine 由小写英文字母组成

哈希表

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
typedef struct hashtable {
    int key;
    int count;
    UT_hash_handle hh;
}hashtable;

hashtable * table;

hashtable* find(int ikey) {
    hashtable* tmp;
    HASH_FIND_INT(table, &ikey, tmp);
    return tmp;
}

bool canConstruct(char * ransomNote, char * magazine){
    table = NULL;
    int i;
    for(i = 0; i < strlen(magazine); i++) {
        hashtable* item = find((int)magazine[i]);
        if(item == NULL) {
            item = (hashtable*)malloc(sizeof(hashtable));
            item->key = (int)magazine[i];
            item->count = 1;
            HASH_ADD_INT(table, key, item);
        } else {
            (item->count)+=1;
        }
    }
    int count_now;
    for(i = 0; i< strlen(ransomNote); i++) {
        hashtable* item = find((int)ransomNote[i]);
        if(item == NULL) {
            return false;
        } else {
            count_now = item->count;
            if(count_now == 1) {
                HASH_DEL(table, item);
            } else {
                (item->count)-=1;
            }
        }
    }
    return true;
}

思路和13有效的字母异位词相同

20 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例：

1
2
3
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
1
2
3
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
1
2
3
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
1
2
3
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

方法1——哈希表

首先遍历数组 nums，将数组中的每个元素加入哈希集合，然后依次检查从 0 到 n 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1)，因此总时间复杂度是 O(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
typedef struct hashtable {
    int key;
    int val;
    UT_hash_handle hh;
} hashtable;

hashtable* table;

int missingNumber(int* nums, int numsSize){
    table = NULL;
    int i;
    for(i = 0; i < numsSize; i++) {
        hashtable* item = (hashtable*)malloc(sizeof(hashtable));
        item->key = nums[i];
        item->val = i;
        HASH_ADD_INT(table, key, item);
    }
    for(i = 0; i < numsSize+1; i++) {
        hashtable* item;
        HASH_FIND_INT(table, &i, item);
        if(item == NULL) {
            return i;
        }
    }
    return 0;
}

方法2——数学

将从 0 到 n 的全部整数之和记为 total，根据高斯求和公式，有：

将数组 nums 的元素之和记为 arrSum，则 arrSum 比 total 少了丢失的一个数字，因此丢失的数字即为 total 与 arrSum 之差。

1
2
3
4
5
6
7
8
int missingNumber(int* nums, int numsSize){
    int total = n * (n + 1) / 2;
    int arrSum = 0;
    for (int i = 0; i < n; i++) {
        arrSum += nums[i];
    }
    return total - arrSum;
}

21 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例：

1
2
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
1
2
输入: numRows = 1
输出: [[1]]

提示:

  • 1 <= numRows <= 30

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    int** res = (int**)malloc(numRows * sizeof(int*));
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));
    int i;
    for(i = 0; i < numRows; i++) {
        int j;
        returnColumnSizes[0][i] = i + 1;
        int* item = (int*)malloc((i + 1) * sizeof(int));
        item[0] = 1;
        item[i] = 1;
        for(j = 1; j < i; j++) {
            item[j] = res[i-1][j-1] + res[i-1][j];
        }
        res[i] = item;
    }
    *returnSize = numRows;
    return res;
}
  • 注意点1：

int** returnColumnSizes的形式为一个二维数组，形如：

1
2
3
4
5
6
7
[[1, 2, 3, 4, 5]] // if numRows = 5
// 数字对应为：
returnColumnSizes[0][0]
returnColumnSizes[0][1]
returnColumnSizes[0][2]
returnColumnSizes[0][3]
returnColumnSizes[0][4]

但题中说明对*columnSizes进行分配内存，则：

1
2
3
*returnColumnSizes = (int*)malloc(numRows * sizeof(int));
// 不要写成：
**returnColumnSizes = (int*)malloc(numRows * sizeof(int*));
  • 注意点2：

进入for循环时，首先进行赋值，再进行条件判断，如果成立，则进入循环体，否则跳出循环。

22 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

示例：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
1
2
输入：n = 2
输出：false

提示：

  • 1 <= n <= 2^31 - 1

方法1——哈希表

可能有3种情况：

  1. 最终会得到 1。
  2. 最终会进入循环。
  3. 值会越来越大，最后接近无穷大。

例如7：

fig1

例如116：

fig2

对于第三种情况，可以考虑每一位数的最大数字的下一位数是多少。

Digits Largest Next
1 9 81
2 99 162
3 999 243
4 9999 324
13 9999999999999 1053

对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

因此，使用哈希表来存储出现过的数字，如果在哈希表中已经出现，说明有循环，否则直到遇到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
typedef struct hashtable {
    int key;
    int val;
    UT_hash_handle hh;
}hashtable;

hashtable* table;

// 获取下一个数
int getNext(int n) {
    int res = 0;
    int temp;
    while(n != 0) {
        temp = n % 10;
        res = res + temp * temp;
        n = n /10;
    }
    return res;
}

bool isHappy(int n){
    table = NULL;
    hashtable* item = (hashtable*)malloc(sizeof(hashtable));
    item->key = n;
    item->val = n;
    HASH_ADD_INT(table, key, item);
    while((n = getNext(n)) != 1) {
        hashtable* temp;
        HASH_FIND_INT(table, &n, temp);
        if(temp == NULL) {
            temp = (hashtable*)malloc(sizeof(hashtable));
            temp->key = n;
            temp->val = n;
            HASH_ADD_INT(table, key, temp);
        } else {
            return false;
        }
    }
    return true;
}

方法2——快慢指针

快慢指针是检测是否有环的常用算法。

在算法的每一步中，慢速在链表中前进 1 个节点，快跑者前进 2 个节点（对 getNext(n) 函数的嵌套调用）。

如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。

如果 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
// 获取下一个数
int getNext(int n) {
    int res = 0;
    int temp;
    while(n != 0) {
        temp = n % 10;
        res += temp * temp;
        n = n /10;
    }
    return res;
}

bool isHappy(int n){
    // 慢指针
    int slow = n;
    // 快指针
    int fast = n;
    while(1) {
        // 慢指针移动一步
        slow = getNext(slow);
        // 快指针移动两步
        fast = getNext(getNext(fast));
        if(fast == 1) {
            return true;
        } else if(slow == fast) {
            return false;
        }
    }
    // 默认返回
    return false;
}

23 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串abcdefg和数字2，该函数将返回左旋转两位得到的结果cdefgab。

示例：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"
1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

  • 1 <= k < s.length <= 10000

方法1——申请新的数组空间存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char* reverseLeftWords(char* s, int n){
    int i;
    char * head = (char*)malloc(n * sizeof(char));
    // 将要翻转的前n个字符存储起来
    for(i = 0; i < n; i++) {
        head[i] = s[i];
    }
    // 将s中后strlen(s)-n个字符向前移动
    for(i = 0; i < strlen(s) - n; i++) {
        s[i] = s[i + n];
    }
    int j;
    // 将s中最后n个位置用临时数组中的值顺序替代
    for(i = strlen(s) - n, j = 0; i < strlen(s); i++, j++) {
        s[i] = head[j];
    }
    return s;
}

方法2——原地翻转

算法步骤如下：

  1. 反转前 n 个字符
  2. 反转 n 到末尾的字符
  3. 反转整个字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char* reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start++] = s[end];
        s[end--] = temp;
    }
    return s;
}
char* reverseLeftWords(char* s, int n){
    int len = strlen(s);
    //反转前 n 个字符
    s = reverse(s, 0, n - 1);
    //反转 k 到末尾的字符
    s = reverse(s, n, len - 1);
    //反转整个字符串
    s = reverse(s, 0, len - 1);
    return s;
}

24 字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例：

1
2
输入: s = "leetcode"
输出: 0
1
2
输入: s = "loveleetcode"
输出: 2
1
2
输入: s = "aabb"
输出: -1

提示:

  • 1 <= s.length <= 105
  • s 只包含小写字母

方法1——哈希表

在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 -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
typedef struct hashtable {
    int key;
    int val[2]; // index, count
    UT_hash_handle hh;
}hashtable;

hashtable* table;

hashtable* find(int ikey) {
    hashtable* tmp;
    HASH_FIND_INT(table, &ikey, tmp);
    return tmp;
}

int firstUniqChar(char * s){
    table = NULL;
    int i;
    for(i = 0; i < strlen(s); i++) {
        hashtable* item = find(s[i]);
        if(item == NULL) {
            item = (hashtable*)malloc(sizeof(hashtable));
            item->key = (int)s[i];
            item->val[0] = i;
            item->val[1] = 1;
            HASH_ADD_INT(table, key, item);
        } else {
            item->val[1] += 1;
        }
    }
    for(i = 0; i < strlen(s); i++) {
        hashtable* item = find(s[i]);
        if(item->val[1] == 1) {
            return item->val[0];
        }
    }
    return -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
int firstUniqChar(char * s){
    // 题目中说明只出现小写字母，为26个
    int* arr = (int*)malloc(26 * sizeof(int));
    int i;
    int index;
    // 初始化为-1，表示一次都没有出现过
    for(i = 0; i < 26; i++) {
        arr[i] = -1;
    }
    for(i = 0; i < strlen(s); i++) {
        index = (int)(s[i] - 'a');
        if(arr[index] == -1) {
            // 没有重复出现时，赋值为所在下标
            arr[index] = i;
        } else {
            // -2表示重复出现
            arr[index] = -2;
        }
    }
    for(i = 0; i < strlen(s); i++) {
        index = (int)(s[i] - 'a');
        if(arr[index] >= 0) {
            return i;
        }
    }
    return -1;
}

25 下一个更大元素①

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

image-20230114104626674

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

方法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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct hashtable {
    int key;
    int next;
    UT_hash_handle hh;
}hashtable;

hashtable* table;

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    table = NULL;
    int* res = (int*)malloc(nums1Size * sizeof(int));
    *returnSize = nums1Size;
    int i;
    int j;
    int flag;
    for(i = 0; i < nums2Size; i++) {
        flag = 0;
        int cur = nums2[i];
        hashtable* item = (hashtable*)malloc(sizeof(hashtable));
        // 从cur的位置向后找比他大的第一个数
        for(j = i; j < nums2Size; j++) {
            if(cur < nums2[j]) {
                item->key = cur;
                item->next = nums2[j];
                HASH_ADD_INT(table, key, item);
                flag = 1;
                break;
            }
        }
        if(flag == 0) {
            item->key = cur;
            item->next = -1;
            HASH_ADD_INT(table, key, item);
        }
    }
    for(i = 0; i < nums1Size; i++) {
        int cur = nums1[i];
        hashtable* item;
        HASH_FIND_INT(table, &cur, item);
        res[i] = item->next;
    }
    return res;
}

方法2——哈希表+单调栈

问题在于，如何更高效地计算 nums2 中每个元素右边的第一个更大的值；第一种解法采用的是双层for循环，本种解法采用单调栈。

栈中元素要么是递增，要么是递减，此处采用单减栈。

对于栈中的元素，栈下面的元素在原数组的右边，因此是栈上面的元素（数组左边）的下一个更大元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};

26 最大连续1的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例：

1
2
3
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
1
2
输入：nums = [1,0,1,1,0,1]
输出：2

提示：

  • 1 <= nums.length <= 105
  • nums[i] 不是 0 就是 1.

一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findMaxConsecutiveOnes(int* nums, int numsSize){
    int i;
    int max = 0;
    int tmp = 0;
    for(i = 0; i < numsSize; i++) {
        int cur = nums[i];
        if(cur == 1) {
            tmp += 1;
        } else {
            if(tmp > max) {
                max = tmp;
                tmp = 0;
            } else {
                tmp = 0;
            }
        }
    }
    // 如果最后一位不是0，还需要判断tmp和max的大小
    return tmp > max ? tmp : max;
}

27 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

代码示例

1