题目描述:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这道题可以用一种我也不知道算不算动态规划的方法来解. 首先我们可以进行零次, 一次或者两次买入卖出操作, 零次或一次是之前的题目, 比较容易解决. 问题在于两次交易, 由于不能同时持有多个stock, 所以两次交易必须是前后发生的, 那么就可以用两个数组来分别记录[0,i]中获得能获得的最大收益和[i+1, n]中能获得的最大收益, 通过遍历i就可以得到前后两次交易的最大收益.

第一个数组通过遍历一次prices得到, 而第二个数组通过反向遍历一次prices得到.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

        int highest = prices.back();
        for(int i = n - 2; i >= 0; i--){
            highest = max(highest, prices[i]);
            profit2[i] = max(profit2[i + 1], highest - prices[i]);
        }

        int maxProfit = profit1.back();
        for(int i = 0; i < n - 1; i++){
            maxProfit = max(maxProfit, profit1[i] + profit2[i + 1]);
        }
        return maxProfit;
    }
};

而最后两个循环可以合并为一个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

        int highest = prices.back(), maxProfit = profit1.back();
        for(int i = n - 2; i >= 0; i--){
            highest = max(highest, prices[i]);
            profit2[i] = max(profit2[i + 1], highest - prices[i]);
            maxProfit = max(maxProfit, profit1[i] + profit2[i + 1]);
        }
        return maxProfit;
    }
};

题目描述:

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example: Given a / b = 2.0, b / c = 3.0.  queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .  return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is:

1 2 3 4 5

, where `equations.size() == values.size()`, and the values are positive. This represents the equations. Return `vector`. According to the example above:

equations = [ [“a”, “b”], [“b”, “c”] ], values = [2.0, 3.0], queries = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction. 这道题一看起来没啥思路, 但是看到tags里的Graph就一下子豁然开朗了. 其实每一个除法就是定义了有向图的一条边(实际上是来回两条)以及这条边的权值. 这样一来每一个查询就是判断给定的两个节点是否连通, 并且计算出路径上每条边的权值的乘积. 首先构建邻接矩阵或邻接表, 然后对每个查询使用DFS或者BFS来搜索是否有两点之间的通路, 并且计算乘积. 在计算过程中, 如果两个点是间接相连的, 实际上我们就可以直接在两点之间增加一条边, 权值为连接通路的权值乘积. 这样的话在剩下的查询中BFS中就可能更快地抵达目标节点. ```cpp class Solution { // 由于对于string的比较等操作很费时, 所以用一个map把string与int对应起来. unordered_map<string, int> nodes; public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { for(int i = 0; i < equations.size(); i++){ // 给每一个string分配一个下标 // 注意这里有个隐藏bug, 假如map/unordered_map对象m中不包含a, // 那么在使用m[a]时实际上是已经创建一个a的key和对应的value, 导致size加1 // 所以如果我们想让第n个加入的元素的value为n-1的话, // 需要赋值m.size() - 1而不是m.size() if(!nodes.count(equations[i].first)){ nodes[equations[i].first] = nodes.size() - 1; } if(!nodes.count(equations[i].second)){ nodes[equations[i].second] = nodes.size() - 1; } } vector<vector<double>> g(nodes.size(), vector<double>(nodes.size(), -1.0)); for(int i = 0; i < equations.size(); i++){ // 构建邻接矩阵 g[getNode(equations[i].first)][getNode(equations[i].second)] = values[i]; g[getNode(equations[i].second)][getNode(equations[i].first)] = 1 / values[i]; } vector<double> ret(queries.size()); for(int i = 0; i < queries.size(); i++){ string a = queries[i].first, b = queries[i].second; if(!nodes.count(a) || !nodes.count(b)){ // 如果出现了不存在的节点 ret[i] = -1.0; } else{ // 使用BFS来搜索路径 ret[i] = BFS(g, getNode(a), getNode(b)); } } return ret; } int getNode(string s){ return nodes[s]; } double BFS(vector<vector<double>> &g, int a, int b){ // 如果是同一个节点就直接返回 if(a == b) return 1.0; int n = g.size(); vector<int> visited(n, 0); // 用于保存是否访问过节点 queue<int> q; // BFS队列, 保存节点下标 queue<double> v; // 用于保存从a到BFS队列中相应的节点的路径乘积 q.push(a); visited[a] = 1; v.push(1.0); while(!q.empty()){ int node = q.front(); double value = v.front(); for(int i = 0; i < n; i++){ if(visited[i] || g[node][i] == -1.0) continue; // 节点i已经访问过或者没有边到达i visited[i] = 1; q.push(i); double len = value * g[node][i]; // 从a到i的路径权值乘积 // 添加新的边 g[a][i] = len; g[i][a] = 1 / len; if(i == b){ // 抵达b点 return len; } v.push(len); } q.pop(); v.pop(); } return -1.0; } };

题目描述:

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note: The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

1 2 3 4 5 6 7 8

int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums); // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning. solution.pick(3); // pick(1) should return 0. Since in the array only nums[0] is equal to 1. solution.pick(1);

这道题的内存要求相当严, 对我来说比较容易想到的方法都超内存了. 最后还是看tag才知道要用一种叫作reservoir sampling 水塘抽样(https://en.wikipedia.org/wiki/Reservoir_sampling)的算法来做.

这个算法可以用于从n个数据(n很大且未知)中随机抽取k个样本, 具体思路如下(下标从0开始):

1. 首先取取数组a前k个元素放入结果r中
2. 对于第i个元素(n>i>=k), 取一个随机数j(0<=j<i), 如果j<k, 那么就把r[j]换成a[i].

至于等概率的具体证明可以看wiki. 具体到这道题, 就是k=1的情况, 我们只需要在r中保存一个元素, 并且同时记录已经遍历到第几个target即可…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    vector<int> n;
public:
    Solution(vector<int> nums) {
        n = nums;
        srand((unsigned int)time(NULL));
    }
    
    int pick(int target) {
        int retIndex, totalTarget = 1;
        for(int i = 0; i < n.size(); i++){
            if(n[i] != target) continue;
            if(totalTarget == 1){
                retIndex = i;
            }
            else{
                if(rand() % totalTarget == 0){
                    retIndex = i;
                }
            }
            totalTarget++;
        }
        return retIndex;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

题目描述:

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

1 2 3 4 5 6 7 8

Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1

Example 2:

1 2 3 4 5 6 7 8 9 10

Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1

我一开始想用动态规划, 但是这个题的测试数据有INT_MAX这么大, 根本开不了这么大的数组, 所以不行. 说明这道题有一些小窍门. 仔细想想, n为偶数是直接除以2没有什么问题, 问题在于奇数时有两种情况, (n+1)/2与(n-1)/2恰好是相邻的两个数, 一个奇数一个偶数, 对于其中的偶数还是直接除以2, 但是奇数就要多一步加1或减1, 所以在选择加1还是减1时应该选择的是除以2后还是偶数的那一个.

这道题因为数据是指数下降的, 所以最多迭代几十次, 递归与循环的性能差距不大, 用递归更好理解一点.

当n等于INT_MAX时, 再加1会导致溢出, 所以下次递归选择次数相同的INT_MAX-1.

还有一个问题在于n等于3时的情况, (n+1)与(n-1)/2分别是4和2, 按照先前的规则应该选择4, 但实际上应该选择2, 我对于这种情况单独处理.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
	int integerReplacement(int n) {
	    if(n == 1) return 0;
	    else if(n == 2) return 1;
	    else if(n == 4 || n == 3) return 2;
	    else if(n % 2 == 0) return integerReplacement(n / 2) + 1;
	    else if(n == INT_MAX) return integerReplacement(n - 1);
	    else{
	        return integerReplacement(((n - 1) / 2) % 2 ? (n + 1) : (n - 1)) + 1;
	    }
	}
};

问题描述:

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note: n is guaranteed to be less than 105.

Example:

1 2 3 4 5 6 7 8

A = [4, 3, 2, 6] F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

按照题目要求的步骤来计算一个数组的每个元素与下标乘积的和, 然后每次循环右移一位, 找出所有的和中的最大值. 不需要在每次右移后都计算一次数组的和, 只要把上一次得到的结果减去最后一项(n-1) * Bk[n-1]再加上所有元素的和(不乘下标)再减去Bk[n-1]即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int sum = 0, stepSum = 0, maxSum = INT_MIN, n = A.size();
        for(int i = 0; i < n; i++){
            sum += A[i];
            stepSum += (i * A[i]);
        }
        maxSum = stepSum;
        for(int i = 1; i < n; i++){
            stepSum = stepSum - A[n - i] * (n - 1) + sum - A[n - i];
            maxSum = max(maxSum, stepSum);
        }
        return maxSum;
    }
};

题目描述:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这道题与上一题相比不同点在于可以多次买入卖出股票但是不能同时持有多份股票, 所以整个的操作流程必须是"买入-卖出-买入-卖出…-买入-卖出". 考虑一个简单的情况:

1,4,2,10

显然有两种策略, 分别的利润为(4-1)+(10-2)=11和10-1=9, 应选择第一种. 而另一种情况:

1,2,4,10

两种策略的利润为(2-1)+(10-4)=8和10-1=9, 此时应该选择第二种. 对于一般情况来说:

a1,a2,a3...,ap,...,aq,...,an

如果在a1买入ap卖出然后再aq买入an卖出的话, 利润为(an-aq)+(ap-a1), 如果在a1买入an卖出的话, 利润为an-a1, 两者之差为(an-a1)-[(an-aq)+(ap-a1)]=aq-ap, 所以如果ap>aq, 那么应该选择前者, 反之选择后者. 从编程策略上来说就应该是搜索一个从低价位开始的递增序列, 在不能再保持递增的时候就是应该卖出的时候.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

题目描述:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

1 2 3 4 5

Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

1 2 3 4

Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0.

这道题我一开始看错了题意. 它的意思是只允许一次买入卖出操作或者没有操作, 所以只要找到相差最大的两个价格并且低价在高价之前就可以了. 从前往后遍历一次数组, 记录到目前为止的最低价格, 然后再记录一个差额的最大值就可以了. 时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目描述：

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

1 2 3 4 5 6

[ [2], [3,4], [6,5,7], [4,1,8,3] >]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

比较简单的动态规划题, 每次需要的数据就是上一行到达每个位置的最小路径和. 只要比较左上方与右上方的两个和然后选择较小的一个就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        vector<int> lastRow, rowSum;
        lastRow = triangle[0];
        for(int i = 1; i < triangle.size(); i++){
            rowSum.resize(triangle[i].size());
            rowSum[0] = lastRow[0] + triangle[i][0];
            for(int j = 1; j < triangle[i].size() - 1; j++){
                rowSum[j] = min(lastRow[j - 1], lastRow[j]) + triangle[i][j];
            }
            rowSum.back() = lastRow.back() + triangle[i].back();
            lastRow = rowSum;
        }
        int ret = INT_MAX;
        for(int i = 0; i < lastRow.size(); i++){
            ret = min(lastRow[i], ret);
        }
        return ret;
    }
};

题目描述:

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

与上一题类似, 只不过现在是要求某一行的结果. 每计算一行只需要上一行的数据, 所以只需要保存一行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret = {1};
        vector<int> last = {1};
        for(int i = 1; i <= rowIndex; i++){
            ret.clear();
            ret.push_back(last[0]);
            auto j = last.begin() + 1;
            for(; j != last.end(); j++){
                ret.push_back(*j + *(j - 1));
            }
            ret.push_back(*(j - 1));
            last = ret;
        }
        
        return ret;
    }
};

题目描述:

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5, Return

1 2 3 4 5 6 7

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Pascal三角形就是每一行除了开头和结尾的数是1, 其他数都等于它的左上方与右上方的数之和.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result(numRows, vector<int>());

        for(int i = 0; i < numRows; i++){
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i) result[i].push_back(1);
                else{
                    result[i].push_back(result[i - 1][j - 1] + result[i - 1][j]);
                }
            }
        }
        return result;
    }
};