HHR的小站
享受代码带来的快乐吧
首页
您正在查看:HHR 发布的文章

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int ans = 0, min = prices[0];
        for (int price:prices) {
            ans = max(ans, price - min);
            if (price < min) min = price;
        }
        return ans;
    }
};

到某天为止的最大盈利=max(前一天为止的最大盈利,如果今天卖出的最大盈利)
注意没有任何交易日的特殊情况

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

2020-02-06 |HHR

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3 
输出: 3 
解释: 有三种方法可以爬到楼顶。 
1.  1 阶 + 1 阶 + 1 阶 
2.  1 阶 + 2 阶 
3.  2 阶 + 1 阶 

class Solution {
public:
    int climbStairs(int n) {
        vector<int> ans;
        ans.push_back(1);
        ans.push_back(2);
        for (int x = 2; x < n; x++) {
            ans.push_back(ans[x - 1] + ans[x - 2]);
        }
        return ans[n-1];
    }
};

到每一阶的方法数是前两阶方法数之和

https://leetcode-cn.com/problems/climbing-stairs/

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int sum = 0, max = nums[0];
        for (int num:nums) {
            if (sum < 0) sum = 0;
            sum += num;
            if (sum > max) max = sum;
        }
        return max;
    }
};

假设你是一个选择性遗忘的赌徒,数组表示你这几天来赢钱或者输钱,
你用sum来表示这几天来的输赢,
用ans来存储你手里赢到的最多的钱,
如果昨天你手上还是输钱(sum < 0),你忘记它,明天继续赌钱; 如果你手上是赢钱(sum > 0), 你记得,你继续赌钱;
你记得你手气最好的时候
作者:acnesu
链接:https://leetcode-cn.com/problems/maximum-subarray/solution/jia-she-ni-shi-yi-ge-du-tu-by-acnesu/
来源:力扣(LeetCode)

https://leetcode-cn.com/problems/maximum-subarray/

在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为011替换为10

给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始)

例子:

输入: N = 1, K = 1
输出: 0
输入: N = 2, K = 1
输出: 0
输入: N = 2, K = 2
输出: 1
输入: N = 4, K = 5
输出: 1
解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N != 1)
            return ((kthGrammar(N - 1, (K + 1) / 2)) + K % 2 + 1) % 2;
        return 0;
    }
};

https://leetcode-cn.com/problems/k-th-symbol-in-grammar/

2020-02-05 |HHR

给定两个正整数 x 和 y,如果某一整数等于 x^i + y^j,其中整数 i >= 0 且 j >= 0,那么我们认为该整数是一个强整数。

返回值小于或等于 bound 的所有强整数组成的列表。

你可以按任何顺序返回答案。在你的回答中,每个值最多出现一次。

示例 1:

输入:x = 2, y = 3, bound = 10
输出:[2,3,4,5,7,9,10]
解释: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

示例 2:

输入:x = 3, y = 5, bound = 15 
输出:[2,4,6,8,10,14] 

提示:

  • 1 <= x <= 100
  • 1 <= y <= 100
  • 0 <= bound <= 10^6

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        set<int> num;
        if (x != 1 && y != 1) {
            for (int i = 0; i <= log(bound) / log(x); i++) {
                for (int j = 0; j <= log(bound - pow(x, i) / log(y)); j++) {
                    if (bound >= pow(x, i) + pow(y, j))
                        num.insert(pow(x, i) + pow(y, j));
                }
            }
        } else if (x == 1 && y == 1) {
            if (bound >= 2)
                num.insert(2);
        } else if (x == 1) {
            for (int j = 0; j <= log(bound - 1) / log(y); j++) {
                num.insert(pow(y, j) + 1);
            }
        } else {
            for (int i = 0; i <= log(bound - 1) / log(x); i++) {
                num.insert(pow(x, i) + 1);
            }
        }
        vector<int> ans;
        ans.assign(num.begin(), num.end());
        return ans;
    }
};

https://leetcode-cn.com/problems/powerful-integers/