LeetCode——【第一周】

梦里梦外; 2024-04-07 13:22 72阅读 0赞

## 第一周 ##

### 一、爬楼梯 ###

> **问题：**
> 
> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
> 
> 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？  
> ![在这里插入图片描述][f443ea0fab434c72a135cf32f1bd2ecd.png_pic_center]

> **代码实现:**
> 
>     /**
>     * 递归方法
>     * 时间复杂度: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);
>     }

### 二、两数之和 ###

> **问题：**
> 
> ![在这里插入图片描述][0d95121b98ed4d78a5111f645ed4b47f.png_pic_center]

> **方法一：【暴力循环 ——两个for循环遍历】**
> 
> 时间复杂度：O（n\*\*2）
> 
> 空间复杂度：O（1）

> **方法二：【创建数组——空间换时间】**
> 
> 时间复杂度：O（n）
> 
> 空间复杂度：O（n）

![在这里插入图片描述][7bd2d2556df1411c8614664b32e19384.png_pic_center]

### 三、合并两个有序数组 ###

> **问题：**  
> ![在这里插入图片描述][8b1acdcfe1d4404f8b53f0c05c442c3a.png_pic_center]

> **方法一：【暴力排序】**
> 
> 将数组2放入数组1，然后直接排序即可
> 
> 时间复杂度：O（n\*\*2）
> 
> 空间复杂度：O（1）

> **方法二：【双指针排序】**
> 
> 从头开始排序，如果p2小于p1，则插入，其他往后挪
> 
> 时间复杂度：O（n+m）
> 
> 空间复杂度：O（1）

> **方法三：【巧妙排序——从后面开始】**
> 
> 所有玩家都全力向前冲刺, 却不知道向后才是胜利之门。*《**头号玩家**》*
> 
> 时间复杂度：O（n+m）
> 
> 空间复杂度：O（1）

### 四、移动零 ###

> **问题：**
> 
> ![在这里插入图片描述][a2187ccf20164d8d9c0ac0becf0382c0.png_pic_center]

> **方法一：【暴力排序】**
> 
> 遍历数组 当等于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++;
            }
        }
    }

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

> **问题：**  
> ![在这里插入图片描述][5f671454b9ef4eedaa7f19fbddc11fea.png_pic_center]

> **方法一：**
> 
> 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**

### 六、合并两个有序链表 ###

> **问题：**
> 
> ![在这里插入图片描述][d13663f3551046ed93c0d3163386c489.png_pic_center]

> **方法一：【非递归排序】**
> 
> 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;
            }
            
        }
    };

> **递归心得：（复制于LeeCode的大佬评论）**
> 
> 其实递归如果做的多了，真的挺简单的！
> 
> 主要想清楚几点问题就行了：
> 
> > **1.这个问题的子问题是什么。**
> > 
> > **2.当前层要干什么事情。**
> > 
> > **3.递归出口。**
> 
> 想清楚这几点就好啦。 很多刚接触递归的同学习惯往深处想，就想想清楚下一层，下下层到底咋回事，千万别！
> 
> 这样永远也想不清楚的，你只要把当前层的事情干好，边界条件找好，深层自然而然就是对的。千万别想那么深。

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

> **问题：**
> 
> ![在这里插入图片描述][543714be2a074ff39cd22951cc868ba6.png_pic_center]

> **方法一：双指针**
> 
> 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;
    }

/**
    * 方法二：递归
    * 时间复杂度: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;
        
    }

[f443ea0fab434c72a135cf32f1bd2ecd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4bbd4208efa84adabe5401333c6255a5.png
[0d95121b98ed4d78a5111f645ed4b47f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4bc268fee3d4412eb1fd9bd0ca184b5c.png
[7bd2d2556df1411c8614664b32e19384.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/212c5e4a630a446590f2e13d070fcc97.png
[8b1acdcfe1d4404f8b53f0c05c442c3a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4237863df53c4859a4b68b862cd5cd6b.png
[a2187ccf20164d8d9c0ac0becf0382c0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/dbcb224e51f049fd83224f0e19eb551b.png
[5f671454b9ef4eedaa7f19fbddc11fea.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b52598d7e0524fd2a7360142368a6221.png
[d13663f3551046ed93c0d3163386c489.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/763b29c100f94b5e97c9fd420895fec3.png
[543714be2a074ff39cd22951cc868ba6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2b7d4abf8ae04300a57113f7fa65b1d4.png