LeetCode刷题日记第三天

举报
开心星人 发表于 2022/10/15 09:04:31 2022/10/15
【摘要】 1、主站第七十题假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?首先先进行简单的分析,当你想要到达第n阶楼梯的时候,你可以从第n-1走一步到达,也可以从第n-2走两步到达。(在第n-2的时候不可以走两次一步到达,因为你走一步就会到n-1,就会和第一种情况重复了)。所以a(n)=a(n-1)+a(n-2)//法一:无脑递归,但...

1、
主站第七十题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
首先先进行简单的分析,当你想要到达第n阶楼梯的时候,你可以从第n-1走一步到达,也可以从第n-2走两步到达。(在第n-2的时候不可以走两次一步到达,因为你走一步就会到n-1,就会和第一种情况重复了)。所以a(n)=a(n-1)+a(n-2)

//法一:无脑递归,但是会超时,因为进行太多重复的运算了
class Solution {
public:
    int climbStairs(int n) {
        if(n==0||n==1){ //注意这里递归的出口,因为a(2)=a(1)+a(0)=2 ,所以a(0)等于1
            return 1;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

其实这题就几乎是等价于斐波那契数列

//法二
class Solution {
public:
    int climbStairs(int n) {
        int p,q,j; //就相当于三个格子
        p=1;  //第一格目前是a[0]
        q=1;   //第二格目前是a[1] 
        for(int i=0;i<n-1;i++){ //循环次数,比如n是2,我只需要一次就可以得出结果,n是3就需要两次,所以循环n-1次
            j=p+q;  //让第三格等于前两格相加
            p=q;   //三个格子整体向左移动一格,第三格又空出来了
            q=j;
        }
        return j;
    }
};


2、
主站第十九题
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
如果不管进阶,可直接先遍历一遍链表,得到链表的长度,再重新表里,找到要删除的结点即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
	//定义连个指针,让两个指针的距离相差n,这样当high指针的下一个是空结点,那么low的下一个结点即为要删除的结点
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * low=head;
        ListNode * high=head;
        for(int i=0;i<n;i++){
            high=high->next;
        }
        if(high==nullptr){
        //这里需要注意下,必须要判断一下,否则high是空结点,那么high->next会报错。
        //如果high是空结点,就证明倒数第n个结点就是第一个结点
            return head->next;
        }
        while(high->next!=nullptr){
            high=high->next;
            low=low->next;
        }
        low->next=low->next->next;
        return head;
    }
};


3、
主站第四十一题
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
终于知道这题为啥是困难了,看起来简单,实则有有很多需要去考虑

不知道咋回事,这个样例没过,找半天也没找出,明儿继续de吧。因为有没通过,所以先不注释了!>_<

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        set<int>snums;
        for(int i=0;i<nums.size();i++){{
            snums.insert(nums.at(i));
        }}
        int flag=1;
        if(nums.at(nums.size()-1)<=0){
            return 1;
        }
        for(set<int>::iterator i=snums.begin();i!=snums.end();i++)
        {
           if(*i>0){
               if(flag!=*i){
                   return flag;
               }
               if(i!=--snums.end()){
                   flag++;
               } 
           }
        }
        return ++flag;
    }
};
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。