day7

61.扑克牌中的顺子

思路:先将牌排序，然后将牌分为两部分：0和非0。遍历非0部分，遇到非顺子的情况，消耗掉一个0，并自加1。最后看看非0部分能否遍历完毕。

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int zero=-1;//指向最后一个零元素,不存在的话为-1
        int k,n=nums.size();
        for(k=0;nums[k]==0&&k<nums.size();k++){//nums[k]==0一定要写在前面
        }
        if(k) zero+=k;
        
        int i=0,j=zero+1;
        while(j<nums.size()-1){
            if(nums[j+1]-nums[j]==1){
                j++;
            }
            else{
                if(i<=zero){
                    I++;
                    //nums[j+1]--;不可以这样写,这样会影响到j+2 对 j+1的判断
                    nums[j]++;
                }
                else{
                    break;
                }
            }
        }
        if(j==n-1 || j==n || j==nums.size()-1) return true;
        else return false;
    }
};

课本的思路更加清晰：
首先把数组排序；其次统计数组中0的个数；最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之，则不连续。但需要注意：如果数组中的非0数字重复出现，则该数组不是连续的。也就是说，如果牌中有对子，则不可能是顺子。

课本说，sort函数为o(nlogn)，还不够快。由于扑克牌的值出现在0~13之间，我们可以定义一个长度为14的哈希表，这样在O(n)时间就能完成排序。通常我们认为不同级别的时间复杂度只有当n足够大时才有意义。由于本题中数组的长度是固定的，只有5张牌，那么O(n)和O(nlogn)不会有多少区别，我们可以选用简洁易懂的方法来实现算法。

HASH排序原理：
将Value值作为下标，存放在一个conut数组里面。以count数组对应下标的值为计重复次数。遍历count数组。对有值的进行打印下标。完成排序。整体的时间复杂度取决于数组最大数字

测试了好多次代码才通过

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int zero=0,blank=0;//0的数目和空缺数
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]==0){
                zero++;
            } 
            else if(nums[i]==nums[i+1]){
                return false;
            }
            else{
                blank+=nums[i+1]-nums[i]-1;//+=!
            }
        }
        if(blank<=zero||blank==0) return true;//不是blank==zero
        else return false;
    }
};

课本的写法

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int zero=0,gap=0;
        for(int i=0;nums[i]==0&&i<nums.size();i++){
            zero++;
        }
        for(int i=zero;i<nums.size()-1;i++){
            if(nums[i]==nums[i+1]){
                return false;
            }
            gap+=nums[i+1]-nums[i]-1;
        }
        if(gap<=zero) return true;//不是blank==zero
        else return false;
    }
};

思路2:关键点在于max-min<5

https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/bu-ke-pai-zhong-de-shun-zi-pai-xu-fang-shi-he-bu-p/

未实现

62.圆圈中最后剩下的数字(重点)

思路1:环形链表模拟圆圈
题目中有一个数字圆圈，很自然的想法就是用个数据结构来模拟这个圆圈。
在常用的数据结构中，很容易的想到环形链表。可以创建一个共有n个结点的环形链表，然后每次都从这个链表中删除第m个结点。
一开始个人的思路是用数组，但数组不适合频繁的删除操作啊。

如果面试官要求不可以使用标准模版库里的数据容器来模拟环形链表，那么我们可以自己实现一个链表。若没有要求可以使用模版库中的std::list(双向链表)来模拟一个环形链表。由于list并不是一个环形结构，因此每当迭代器扫描到链表末尾时，要记得把迭代器移到链表的头部。这样就相当于按照顺序在一个圆圈里遍历了。

虽然超时了，但是这个思路要会。

class Solution {
public:
    int lastRemaining(int n, int m) {
        list<int> cir;
        for(int i=0;i<n;i++){
            cir.push_back(i);
        }
        list<int>::iterator cur=cir.begin();
        while(cir.size()>1){
            for(int i=1;i<m;i++){
                cur++;
                if(cur==cir.end()) cur=cir.begin();
            }
            list<int>::iterator next=++cur;
            if(next==cir.end()) next=cir.begin();
            --cur;
            cir.erase(cur);
            cur=next;
        }
        return cir.back();
    }
};

自己写的代码，原本想利用求余来节约时间，可是忽略了余数的结果范围是0～cir.size()-1;当余数为0时，应该令其等于cir.size();
否则你后续的while(--temp_m) 根本无法退出循环，即使修改成while(--temp_m>0)也是不对的，虽然可以退出循环，但是也是不正确的。

class Solution {
public:
    int lastRemaining(int n, int m) {
        list<int> cir;
        for(int i=0;i<n;i++){
            cir.push_back(i);
        }
        list<int>::iterator cur=cir.begin();
        while(cir.size()>1){
            int temp_m=m%cir.size();
            if(temp_m==0) temp_m=cir.size();//!
            while(--temp_m){//0如果减1 变成-1 负数一直剪也不会变成0呀.。
            //while(--temp_m>0){
                cur++;
                if(cur==cir.end()) cur=cir.begin();
            }
            list<int>::iterator next=++cur;
            if(next==cir.end()) next=cir.begin();
            --cur;
            cir.erase(cur);
            cur=next;
        }
        return cir.back();
    }
};

ps:list的迭代器erase问题
https://www.cnblogs.com/litifeng/p/12960622.html

一开始的思路是数组，但是写不出来代码，写得很复杂，还用什么迭代器，都晕了，看看别人的，好好领悟一下

class Solution{
public:
    //n个数字，每次删除第m个数字
    int lastRemaining(int n, int m){
        if (n < 1 || m < 1) return -1;
        //使用vector来模拟一个环形链表
        vector<int> num(n);
        for(int i = 0; i < n; i++) num[i] = i;

        int temp = 0;
        while(num.size() > 1){
            int count = temp + m - 1;//从数组开头删除下一个节点需要的总步数
            int size = num.size();//数组大小
            int mv = count % size;//实际从数组开头需走的步数
            temp = mv;
            num.erase(num.begin() + mv); //删除元素
        }
        return num[0];
    }
};

思路2:
课本p302-303
没有实现没有仔细去想
下面应该都是思路2
https://blog.csdn.net/u011500062/article/details/72855826
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-by-lee/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/

63.股票的最大利润

思路：
买入价越低越好，卖出价越高越好。

自己的思路：遍历两次。先从后往前遍历，建立max_n数组，表示i之后的最大卖出价。
第二次从头遍历，求每一个买入价和卖出价的差，找出最大值。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<1) return 0;
        vector<int> max_p(prices.size());
        int max=-1;//价格不会为负数
        for(int i=prices.size()-1;i>=0;i--){
            if(prices[i]>max){
                max=prices[i];
            }
            max_p[i]=max;
        }
        int ans=0;
        int min=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min) min=prices[i];
            if(max_p[i]-min>ans) ans=max_p[i]-min;
        }
        return ans;
    }
};

优化：实际上并不需要遍历两次，也不需建立数组。
定义函数diff(i)为当卖出价为数组中第i个数字时可能获得的最大利润。
显然，当卖出价固定时，买入价越低获得的利润越大。也就是说，如果在扫描到数组中的第i个数字时，只要我们能记住之前的i-1个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润!!!
代码中变量min保存了数组前i-1个数字的最小值，也就是之前股票的最低价。只遍历一次，时间复杂度o(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        int min_price=prices[0],max_profit=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min_price){
                min_price=prices[i];
            }
            int cur_profit=prices[i]-min_price;
            if(cur_profit>max_profit){
                max_profit=cur_profit;
            }
        }
        return max_profit;
    }
};

64.求1+2+...+n(重点)

不会写
通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确限制for和while的使用，循环已经不能再用了。同样，递归函数也需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了
因此我们手里能用的工具很少，列举出来发现只有加减法、赋值、位运算符以及逻辑运算符。

递归(没有想到)：f(n)=n+f(n-1)

class Solution {
public:
    int sumNums(int n) {
        if(n==1) return 1;
        return n+sumNums(n-1);
    }
};

但是这道题：不能用for循环;不能用if运算.
如何解决：
for用递归实现，这很好理解
if用逻辑运算符的计算特性来解决。即&&的短路特性。

A && function() 如果A是True，返回的是function 如果A是false，function都不会被执行到就下一句了。
因此我们把递归入口放在function处，那么A表达式就可以起到if的作用，function递归起到for的作用
为了让n能及时停止（数量够的时候，要输出false），我们只能把终点设置成0，因此我们递归中要倒数。

class Solution {
public:
    int sumNums(int n) {
        n && (n += sumNums(n-1));
        return n;
    }
};

时间复杂度：O(n)递归函数递归n 次，每次递归中计算时间复杂度为 O(1)，因此总时间复杂度为 O(n)。
空间复杂度：O(n)。递归函数的空间复杂度取决于递归调用栈的深度，这里递归函数调用栈深度为 O(n)，因此空间复杂度为 O(n)。

思路2:巧用sizeof做乘法，>>做除法
定义一个二维数组再获取数组的size，达到n*(n+1)的目的，然后位运算就是n(n+1)/2

class Solution {
public:
    int sumNums(int n) {
        bool arr[n][n+1];
        return sizeof(arr)>>1;
    }
};

思路3 .4.5.6:利用构造函数/虚函数/函数指针/模版类型求解
课本p307-310
由于不熟悉这些知识，不太看得明白

67.把字符串转变为整数

(重点res=res*10+str[i]-'0',不必按照思维从低位算起)

原始思路：常规的思路，逐步解决，具体如步骤1、2、3。
但是22% 5%..

class Solution {
public:
    int strToInt(string str) {
        if(str.empty()) return 0;//空字符串
        //1 去除开头的空格
        int i=0;
        while(i<str.size()&&str[i]==' '){
            i++;
        }
        if(i==str.size()) return 0;//全为空格
        if(str[i]!='+' && str[i]!='-' && str[i]<'0' && str[i]>'9'){
            return 0;
        }
        //2 判断正负
        bool positive=true;
        if(str[i]=='+') i++;
        else if(str[i]=='-'){
            i++;
            positive=false;
        }
        //3 处理数字并返回结果
        if(i==str.size()) return 0;//只有正负号
        //去除开头的无意义0
        while(i<str.size()&&str[i]=='0'){
            i++;
        }
        if(i==str.size()) return 0;//全是0

        stack<int> num;
        while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
            num.push(str[i]-'0');
            i++;
        }
        long n=0,ten=1;
        while(!num.empty()){
            n+=num.top()*ten;
            num.pop();
            ten*=10;
            //如果不去除开头的无意义0，虽然n没有超过INT_MAX，不会break，但是ten*=10这里会不断累乘，导致溢出 程序崩溃
            //"  0000000000012345678"
            if(n>INT_MAX) break;
            if(ten>10000000000) break;
            //"20000000000000000000"
            //n一直没有超过INT_MAX，不会break，但是ten*=10这里不断累乘，导致溢出 程序崩溃。而且开头没有无意义的0
        }
        if(!positive) n=-n;

        if(n>INT_MAX || (!num.empty()&&positive)){
            return INT_MAX;
        }
        else if(n<INT_MIN || (!num.empty()&&!positive)){
            return INT_MIN;
        }
        else{
            return (int)n;
        }
    }
};

自己的代码因为没有使用正确的思想将string转为int导致复杂。
改成：res=res*10+str[i]-'0';
几乎双百

class Solution {
public:
    int strToInt(string str) {
        if(str.empty()) return 0;//空字符串
        //1 去除开头的空格
        int i=0;
        while(i<str.size()&&str[i]==' '){
            i++;
        }
        if(i==str.size()) return 0;//全为空格
        if(str[i]!='+' && str[i]!='-' && str[i]<'0' && str[i]>'9'){
            return 0;
        }
        //2 判断正负
        bool positive=true;
        if(str[i]=='+') i++;
        else if(str[i]=='-'){
            i++;
            positive=false;
        }
        //3 处理数字并返回结果
        if(i==str.size()) return 0;//只有正负号
        long res=0;
        while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
            res=res*10+str[i]-'0';
            i++;
            if(res>INT_MAX) break;
        }
        if(!positive) res=-res;
        if(res>INT_MAX){
            return INT_MAX;
        }
        else if(res<INT_MIN){
            return INT_MIN;
        }
        else{
            return (int)res;
        }
    }
};

但是好像不能够使用long..因为题目说环境是32位的.
下次再看吧.
https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solution/mian-shi-ti-67-ba-zi-fu-chuan-zhuan-huan-cheng-z-4/

68- I. 二叉搜索树的最近公共祖先

思路1：注意是BST，所以分别保存两个节点的父节点到数组，最后从数组尾部开始遍历，寻找第一个相同节点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> phead,qhead;
        TreeNode* temp=root;
        //保存p的父亲节点
        while(temp!=p){
            if(temp->val>p->val){
                temp=temp->left;
            }
            else if(temp->val<p->val){
                temp=temp->right;
            }
            else{
                temp=p;
            }
            phead.push_back(temp);
        }
        //保存q的父亲节点
        temp=root;
        while(temp!=q){
            if(temp->val>q->val){
                temp=temp->left;
            }
            else if(temp->val<q->val){
                temp=temp->right;
            }
            else{
                temp=q;
            }
            qhead.push_back(temp);
        }
        //从尾部开始找第一个相同的元素
        for(int i=phead.size()-1;i>=0;i--){
            for(int j=qhead.size()-1;j>=0;j--){
                if(phead[i]==qhead[j]){
                    return phead[i];
                }
            }
        }
        return root;
    }
};

标准思路：其实并不需要这么复杂。利用bst的性质：位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大。我们只需从树的根结点开始和输入的两个结点进行比较。如果当前结点的值比两个结点的值都大，那么最低的共同父结点一定是在当前结点的左子树中，于是下一步遍历当前结点的左子结点；如果当前结点的值比两个结点的值都小，那么最低的共同父结点一定是在当前结点的右子树中，于是下一步遍历当前结点的右子结点。这样在树中从上到下找到第一个在输入结点的值之间的结点，就是最低的公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL;
        if (root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);
        if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;//不满足两个if则找到了，直接返回
    }
};

时间复杂度 O(N) ：其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）。
空间复杂度 O(N) ：最差情况下，即树退化为链表时，递归深度达到树的层数 N 。

思路2:迭代解法
将上述思想转为迭代
迭代

1.循环搜索：当节点 root 为空时跳出；
当 p,q 都在 root 的右子树中，则遍历至 root.right ；
否则，当 p,q 都在 root 的左子树中，则遍历至 root.left ；
否则，说明找到了最近公共祖先，跳出。

返回值：最近公共祖先 root 。

复杂度分析：
时间复杂度 O(N) ：其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）。
空间复杂度 O(1) ：使用常数大小的额外空间。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root!=NULL){
            if(root->val < p->val && root->val < q->val) // p,q 都在 root 的右子树中
                root = root->right; // 遍历至右子节点
            else if(root->val > p->val && root->val > q->val) // p,q 都在 root 的左子树中
                root = root->left; // 遍历至左子节点
            else break;
        }
        return root;
    }
};

68 - II. 二叉树的最近公共祖先

思路：dfs遍历每一条路径并临时保存，如果发现该路径中有所求节点p or q，就保存下来，找到两条路径之后便退出。
48% 10%

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path,phead,qhead;
        dfs(root,p,q,path,phead,qhead);
        //从尾部开始找第一个相同的元素
        for(int i=phead.size()-1;i>=0;i--){
            for(int j=qhead.size()-1;j>=0;j--){
                if(phead[i]==qhead[j]){
                    return phead[i];
                }
            }
        }
        return root;
    }
    void dfs(TreeNode* root, TreeNode* p, TreeNode* q,vector<TreeNode*> &path,vector<TreeNode*> &phead,vector<TreeNode*> &qhead){
        if(root==NULL|| (!phead.empty()&&!qhead.empty()) ){//如果两条路径都找到便不需要再遍历了
            return;
        }
        path.push_back(root);
        if(root->val==q->val){
            qhead=path;
        }
        else if(root->val==p->val){
            phead=path;
        }
        dfs(root->left,p,q,path,phead,qhead);
        dfs(root->right,p,q,path,phead,qhead);
        path.pop_back();
    }
};

其实获得两条路径之后，并不需要从尾部开始找，从头也可以，这样都不用写两层循环了呀，更快。
75% 10%

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path,phead,qhead;
        dfs(root,p,q,path,phead,qhead);
        
        //从头开始找
        TreeNode* res=root;
        for(int i=0,j=0;i<phead.size()&&j<qhead.size();i++,j++){
            if(phead[i]==qhead[j]){
                res=phead[i];
            }
        }
        return res;
    }
    void dfs(TreeNode* root, TreeNode* p, TreeNode* q,vector<TreeNode*> &path,vector<TreeNode*> &phead,vector<TreeNode*> &qhead){
        if(root==NULL|| (!phead.empty()&&!qhead.empty()) ){//如果两条路径都找到便不需要再遍历了
            return;
        }
        path.push_back(root);
        if(root->val==q->val){
            qhead=path;
        }
        else if(root->val==p->val){
            phead=path;
        }
        dfs(root->left,p,q,path,phead,qhead);
        dfs(root->right,p,q,path,phead,qhead);
        path.pop_back();
    }
};

另一种思路，递归，不用存路径。
没太看明白。。
https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/
这个也是这种做法

//如果是一般的二叉树
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;
        //如果根节点就是p或者q，返回根节点
        if(root == p || root == q)
            return root;
        //分别去左右子树里面找
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left && right)//p，q各在一边，说明当前的根就是最近共同祖先 
            return root;
        else if(left)//说明p，q都在左子树
            return left;
        else if(right)//说明p，q都在右子树
            return right;
        else
            return NULL;
        
    }
};

一周刷完剑指offer(7)