剑指offer 62与63


剑指offer62与63

1.面试题62. 圆圈中最后剩下的数字

有一篇比较好的约瑟夫环讲解文章:

https://blog.csdn.net/u011500062/article/details/72855826

class Solution {
public:
    int lastRemaining(int n, int m) {
        int res = 0;
        for(int i=2;i<=n;i++) {
            res = (res+m) % i;
        }
        return res;
    }
};

2.面试题63. 股票的最大利润

method1:维护一个最小值。

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

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录