4/29剑指offer

1.圆圈中最后剩下的数字
0,1,...,n-1这n个数字排成一个圆圈，从0开始，每次删除圆圈里第m个数字。求出这个圆圈里剩下的最后一个数字。
思路一：用环形链表模拟圆圈:创建一个一共有n个节点的环形链表，然后每次在这个链表中删除的第m个节点。

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1||m<1) return -1;
        list<int> numbers;
        for(int i=0;i<n;i++)
        {
            numbers.push_back(i);
        }
        list<int>::iterator current=numbers.begin();//迭代器
        while(numbers.size()>1)
        {
            for(int i=1;i<m;i++)
            {
                ++current;
                if(current==numbers.end())
                {
                    current=numbers.begin();//形成一个环
                }
            }
            list<int>::iterator next=++current;
            if(next==numbers.end())
            {
                next=numbers.begin();//迭代到尾部时，调到头部
            }
            --current;
            numbers.erase(current);//删除第m个元素
            current=next;//开始新的循环
        }
        return *(current);
    }
};

思路二：数学方法

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<1||m<1)
            return -1;
        int last=0;
        for(int i=2;i<=n;i++)
        {
            last=(last+m)%i;//公式
        }
        return last;
    }
};

2.股票的最大利润
（1）假如把某股票的价格按照时间先后顺序存储在数组中，买卖该股票一次可能获得的最大利润是多少。
思路：定义一个min用来记录股票的最低价，再定义一个cur和max来比较每次迭代获益的最大值。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len<2) return 0;
        int min=prices[0];
        int res=prices[1]-min;
        for(int i=2;i<len;i++)
        {
            if(prices[i-1]<min)
            {
                min=prices[i-1];//记录i之前最小的股票
            }
            int cur=prices[i]-min;
            res=max(res,cur);
        }
        return max(res,0);
    }
};

(2)给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
思路：依次遍历，相邻做比较，算小利润相加即等于总利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len<2) return 0;
        int max=0;
        for(int i=1;i<len;i++)
        {
            if(prices[i]-prices[i-1]>0)
            {
                max+=prices[i]-prices[i-1];//从头开始依次遍历，只要后者大于前者，就买卖一次，多次差和相加等于连续总差和
            }
        }
        return max;       
    }
};

3.求1-n的和，不能使用乘除法，循环，条件、选择语句。
思路一：利用递归与布尔值。

class Solution {
public:
    int Sum_Solution(int n) {
        int sum=n;
        bool t=(n>0)&&(sum+=Sum_Solution(n-1));
        return sum;
    }
};

思路二：利用构造函数求解

class Temp
{
    public:
           Temp(){++N;Sum+=N;}
    static void Reset(){N=0,Sum=0};
    static unsigned int GetSum(){return Sum};
    private:
    static unsigned int N;
    static unsigned int Sum;
};
unsigned int Temp::N=0;
unsigned int Temp::Sum=0;
unsigned int Sum_solution2(unsigned int n)
{
    Temp::Reset();
    Temp*a=new Temp[n];//调用n次构造函数
    delete []a;
    a=nullptr;
    return Temp::GetSum();
}