LeetCode——【第一周】

第一周

一、爬楼梯

问题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

代码实现:

/**
* 递归方法
* 时间复杂度:O(nlogn)   --（深度过大，超时！）
* 空间复杂度:O(1)
* 语言实现：C
**/

int climbStairs(int n){

if(n == 1){return 1;}

if(n == 2){return 2;}

return climbStairs(n-1) + climbStairs(n - 2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、两数之和

问题：

方法一：【暴力循环 ——两个for循环遍历】

时间复杂度：O（n**2）

空间复杂度：O（1）

方法二：【创建数组——空间换时间】

时间复杂度：O（n）

空间复杂度：O（n）

三、合并两个有序数组

问题：

方法一：【暴力排序】

将数组2放入数组1，然后直接排序即可

时间复杂度：O（n**2）

空间复杂度：O（1）

方法二：【双指针排序】

从头开始排序，如果p2小于p1，则插入，其他往后挪

时间复杂度：O（n+m）

空间复杂度：O（1）

方法三：【巧妙排序——从后面开始】

所有玩家都全力向前冲刺, 却不知道向后才是胜利之门。《头号玩家》

时间复杂度：O（n+m）

空间复杂度：O（1）

四、移动零

问题：

方法一：【暴力排序】

遍历数组 当等于0时，后面数组往前进1位，在最后添加0即可

时间复杂度：O（n**2）

空间复杂度：O（1）

方法二：【记录0排序—逆向思维】

遍历数组：当不等于0时，则去起始标志位，标志位递增

最后：总长-标志位 = 0的个数（末尾添加即可）

时间复杂度：O（2n）

空间复杂度：O（1）

方法三：【双指针】

创建一个标志位，开始遍历数组：如果不为零，进行交换，

标志位为数，原位置为0即可，然后标志位递增

时间复杂度：O（n）

空间复杂度：O（1）

/**
* 双指针方法
* 时间复杂度:O(n)
* 空间复杂度:O(1)
* 语言实现：C
**/
void moveZeroes(int* nums, int numsSize){
    
    if(numsSize<2){
        return;
    }
    int j = 0;
    // 遍历一遍
    for(int i=0; i<numsSize; i++){
        // 如果不等于0，则交换
        if(nums[i]!=0){
            int temp = nums[i];
            nums[i] = 0;
            nums[j] = temp;
            j++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

五、找到所有数组中消失的数字

问题：

方法一：

1.排序一遍

2.在遍历一遍，发现缺少的数组，并记录

3.返回结果

时间复杂度：O（n**2）

空间复杂度：O（1）

方法二：

1.创建一个【1，n】的数组

2.遍历原数组，去减轻创建的数组元素

3.新数组中，不为0的元素即为缺失的

时间复杂度：O（n）

空间复杂度：O（n）

方法三：

【重点：在原数组上进行数值操作，并进行标记，而且标记不会影响后续的判断】

1.遍历数组：将数先取模，获取原始数值，再将对应的原值当索引，将对应的位置上的数值+n

（注意：这不会影响对应位置上数值，+n相当于标记！）

2.再次遍历数组：（因为标记了的数值都会+n，那么没有标记的数值就会小于n）

将小于n的数值+1，记录即可！

因为，数组从1开始，所以在取模时，需要-1，而且后面判断不符合数值的时候，需要+1

六、合并两个有序链表

问题：

方法一：【非递归排序】

1.创建两个指针（head，tail）

2.比较大小，小的就往tail上挂

3.两边同时遍历，当遍历完一端，剩下的直接往tail上挂，最后返回head

时间复杂度：O（n）

空间复杂度：O（1）

方法二：【递归排序】

1.创建一个指针，进行比较，指针指向下一个节点（递归调用）

2.把下一个连接好后，函数再返回当前的指针地址

注意：相当于一直递归到到最后，从最后开始连接！

时间复杂度：O（nlogn）

空间复杂度：O（1）

/**
* 方法二：递归
* 时间复杂度：O（nlogn）
* 空间复杂度：O（1）
* 语言实现：C++
**/

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        if(list1 == NULL){
            return list2;
        }
        if(list2 == NULL){
            return list1;
        }       
        if(list1->val<=list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
        
    }
};
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

递归心得：（复制于LeeCode的大佬评论）

其实递归如果做的多了，真的挺简单的！

主要想清楚几点问题就行了：

1.这个问题的子问题是什么。

2.当前层要干什么事情。

3.递归出口。

想清楚这几点就好啦。 很多刚接触递归的同学习惯往深处想，就想想清楚下一层，下下层到底咋回事，千万别！

这样永远也想不清楚的，你只要把当前层的事情干好，边界条件找好，深层自然而然就是对的。千万别想那么深。

七、删除排序链表中的重复元素

问题：

方法一：双指针

1.遍历链表

2.如果不和之前相同，那么就连接！

时间复杂度:O(n)

空间复杂度:O(1)

方法二：递归

1.从最后开始【递归到最后】
2.比较当前节点和下一个节点的值

3.如果不相同就连接，并返回当前的节点；

​ 如果相同就返回下一个的节点

时间复杂度:O(nlogn)

空间复杂度:O(1)

递归注意事项：

1.找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return

2.想想应该返回什么值：应该返回的自然是已经去重的链表的头节点

3.每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head

/**
* 方法一：双指针
* 时间复杂度:O(n)
* 空间复杂度:O(1)
* 语言实现：C
**/

struct ListNode* deleteDuplicates(struct ListNode* head){


    // 创建一个连接的节点
    struct ListNode* tail;

    // 创建一个索引节点
    struct ListNode* flag;

    tail = head;
    flag = head;
    
    // 1.遍历链表   
    while(head){
        // 2.如果不和之前相同，那么就连接！
        if(tail->val != flag->val){
            tail->next = flag;
            tail = flag;
        }
        
        // 如果flag的next为空,则停止
        if(flag->next == NULL){
            // 如果这里的值和上一个相同
            if(tail->val == flag->val){
                tail->next = NULL;     // 将tail切断
                return head;
            }
            else{
                tail->next = flag;     // 将tail连接flag
                return head;
            }
        }
        
        // flag继续往下索引
        flag = flag->next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
* 方法二：递归
* 时间复杂度:O(nlogn)
* 空间复杂度:O(1)
* 语言实现：C
**/
struct ListNode* deleteDuplicates(struct ListNode* head){
    
    // 递归到最后
    if(head){
        
        struct ListNode* flag;

        if(head->next != NULL){
            // 接收下一个节点
            flag = deleteDuplicates(head->next);
        }else{
            // 如果是空节点就直接返回
            return head;
        }
        
        // 如果当前的值 与 下一个节点的值不相同，则连接起来，并返回当前节点
        if(head->val != flag->val ){
            head->next = flag;
            return head;
        }

        // 如果相同，则返回上一个节点
        else{
            return flag;
        }
    }
    
    // 返回head
    return head;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37