LeetCode刷题日记第三天
【摘要】 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)