貪欲法(Greedy algorithm)で問題を解く

(2020-01-13)

貪欲法(Greedy algorithm)は問題を分割し、それぞれにおいて貪欲に最適な選択をしていくアルゴリズムの総称。 必ずしも最適解になるとは限らないが、うまくいけば簡潔に計算量を減らすことができる。

Best Time to Buy and Sell Stock II - LeetCode

配列で株価が与えられ、売買して得られる最大の利益を返す問題。

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 (i.e., buy one and sell one share of the stock multiple times).

Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

局所的な利益の最大化が単純に全体の利益の最大化になるので、上がるなら持ち続け、下がるなら売るのが最適。

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

Wiggle Subsequence - LeetCodeも同様に解ける。

Jump Game - LeetCode

最大配列の数字の分進めて、最初のindexから最後のindexに到達できるかを返す問題。

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

前から探索するといくつ進めばいいのか分からないので、 後ろから辿り、終わりまで到達できる地点を見つけたら、次はその地点まで到達できる地点を探すというのを繰り返し、先頭まで繋がるかどうかで判定する。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int pos = nums.size() - 1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (pos <= i + nums[i]) {
                pos = i;   
            }
        }
        return pos == 0;
    }
};

Jump Game II - LeetCode

Jump Gameの最短ジャンプ回数を返す版。

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

後ろから辿っていくのはJump Gameと同様だが、最短回数にするため、到達できる地点を見つけるたびにそれまでの地点に止まる必要があるかを確認する。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1) {
            return 0;
        }
        int pos = nums.size() - 1;
        deque<int> stops = {pos};
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (pos <= i + nums[i]) {
                stops.push_back(pos);
                pos = i;
                while(stops.size() >= 2) {
                    if (stops[stops.size() - 2] > i + nums[i]) {
                        break;
                    }
                    stops.pop_back();
                }
            }
        }
        return stops.size();
    }
};