LeetCode刷题日记第三天

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;
    }
};