Chapter 26 Greedy

贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的.

26.1 649. Dota2 Senate

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

1. Ban one senator's right:
A senator can make another senator lose all his rights in this and all the following rounds.
2. Announce the victory:
If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

Example 1:

Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
And the second senator can't exercise any rights any more since his right has been banned. 
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in the round 1. 
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

这道题一看很像Josephus Problem. 基本数据结构是循环链表,但是C++里面没有循环链表,只能用另外的办法.

At the first glance, the problem is very much like Josephus Problem, where the basic data structure is cicular linked list. But there is no circular list in C++, we have to use something else.

例子: DRRDRD => DxRDRD

之后两种情况,如果R bans the D before himself, then R will lose; but if R bans D after himself, R will win. This is a greedy problem. The optimal rule is: you always ban the closest opponent after yourself.

谁输谁赢了位置和数量都有关,比如DDRRR, 虽然R多,但是结果是D赢.

26.1.1 Algo 1: Two Queue

string predictPartyVictory(string senate) {
    queue<int> q1, q2;
    int n = senate.length();
    for(int i = 0; i<n; i++)
        (senate[i] == 'R')?q1.push(i):q2.push(i);
    while(!q1.empty() && !q2.empty()){
        int r_index = q1.front(), d_index = q2.front();
        q1.pop(), q2.pop();
        (r_index < d_index)?q1.push(r_index + n):q2.push(d_index + n);
    }
    return q2.empty() ? "Radiant" : "Dire";
}

26.1.2 Algo 2:

DDRRR => DDR => D => D

注意这里count是全局变量,起到了代替circular linked list的作用.

string predictPartyVictory(string senate) {
    int count = 0, len = 0;
    // When the length of senate doesnot decrease, the game is over.
    while (senate.size() != len) {
        string s;
        len = senate.size();
        for (int i = 0; i < len; i++) {
            if (senate[i] == 'R') 
                if (count++ >= 0) s += 'R';
            else if (senate[i] == 'D') 
                if (count-- <= 0) s += 'D';
        }  
        senate=s;
    }
    return (senate[0] == 'R')?"Radiant":"Dire";
}

2016(1-3月) 码农类硕士实习 Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生
报一个FB两轮店面面经.
第一轮:
1.判断有效回文串
2.decode ways
3.number of islands
其中第一题稍微改得复杂了些,第三题要求返回个数

第二轮:
给定一堆interval(如果我们管这个list叫IntervalList), 和一个target interval
我们的目标是去merge这些interval,让merge的结果能够cover这个target interval, 求这种merge所需的原interval的最少个数是多少
有点抽象,举个栗子.
IntervalList: [-1, 9] [ 1, 10] [ 0, 3] [ 9, 10] [ 3, 14] [ 2, 9] [10, 16]
target interval: [ 2, 15]
在这个栗子中,我们发现要想cover[2,15]有好几种方法,比如:
[-1, 9] + [ 9, 10] + [10, 16] 或者 [ 1, 10] + [10, 16]
我们要的是merge个数最少的方法,所以这里应该返回2
http://www.1point3acres.com/bbs/thread-224128-1-1.html

greedy.先把所有intervals按start排序,然后遍历.首先我们要从那些start小于等于target.start的intervals中选end最大的那个,假设我们用A来表示那个选出来的interval.如果A.end小于target.end,我们就得继续遍历,从那些start小于等于A.end的intervals中选end最大的那个.最终返回所选的interval个数.时间复杂度是O(nlogn) due to the sorting.隐约觉得很像jump game II.

2015(10-12月) 码农类硕士全职 Google - 内推 - Onsite |Otherfresh grad应届毕业生
刚刚结束onsite…趁还记得
第一轮,国人大哥.
首先是安卓手机那种九个点的锁屏,找所有可能的序列.followup是限制长度怎么改.
然后给线段数组,求最多选多少个互相不overlap的线段,问怎么证明贪心是对的,然后code.
最后是给先增后减的数组,问怎么search一个target.讲完没时间code了.
第二轮,给一个pattern（可能会有最多一个*号)的字典,问怎么判断输入单词是不是在字典里.Trie从头写了一白板…followup怎么优化..
第三轮,国人妹子带shadow.
leetcode那个找循环小数的题.
然后是merge interval,稍微更改是连续的也merge,比如[1, 2]和[3, 4].
这一轮写得bug略多…两位面试官各种提示..不知是好是坏…
最后,先写了个array变BST,followup是改成iterate,然后又写了个模拟栈的版本.
第二题是怎么在二叉树里随机一个数（等概率),提示说可以增加node的data..比如..size..
求RP,求offer啊..
BTW,可以自己点名认识的人做lunch interviewer真是不错啊=,=. http://www.1point3acres.com/bbs/thread-143674-1-1.html

26.2 55. 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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

https://leetcode.com/problems/jump-game/
http://bangbingsyb.blogspot.com/2014/11/leetcode-jump-game-i-ii.html
http://www.cnblogs.com/zichi/p/4808025.html (BIT)

DFS:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int L=nums.size();
        return dfs(nums, 0, L);
    }
    bool dfs(vector<int>& nums, int i, int L){
        if(i+nums[i]>=L-1) return true;
        int step=1;
        while(step<=nums[i]){
            if (dfs(nums,i+step,L)) return true;
            step++;
        }
        return false;
    }
};

Greedy:

class Solution {
    public boolean canJump(int[] nums) {
        int mx=0;
        for(int i=0;i<nums.length;++i){
            if(i>mx) return false;
            mx=Math.max(i+nums[i],mx);
            if(mx>=nums.length-1) return true;
        }
        return false;
    }
}

26.3 45. Jump Game II

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.

For example: Given array A = [2,3,1,1,4]

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.)

Note: You can assume that you can always reach the last index.

http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html
http://blog.sina.com.cn/s/blog_6a0e04380102v5ag.html

/*
 * We use "last" to keep track of the maximum distance that has been reached
 * by using the minimum steps "ret", whereas "curr" is the maximum distance
 * that can be reached by using "ret+1" steps. Thus,
 * curr = max(i+A[i]) where 0 <= i <= last.
 */
class Solution {
public:
    int jump(int A[], int n) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }

        return ret;
    }
};

这个算法的思想主要是,扫描数组（废话…),以确定当前最远能覆盖的节点,放入curr.然后继续扫描,直到当前的路程超过了上一次算出的覆盖范围,那么更新覆盖范围,同时更新条数,因为我们是经过了多一跳才能继续前进的.

形象地说,这个是在争取每跳最远的greedy.