Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int M = dungeon.size();
        int N = dungeon[0].size();
        
        dungeon[M-1][N-1] = max(-dungeon[M-1][N-1], 0);
        
        for(int j = N-2; j >= 0; j--) 
           dungeon[M-1][j] = max(dungeon[M-1][j+1] - dungeon[M-1][j], 0);
        
        for(int i = M-2; i >= 0; i--) 
           dungeon[i][N-1] = max(dungeon[i+1][N-1] - dungeon[i][N-1], 0); 
        
        for(int i = M-2; i >=0; i--)
          for(int j = N-2; j >= 0; j--) 
             dungeon[i][j] = max(min(dungeon[i+1][j], dungeon[i][j+1]) - dungeon[i][j], 0); 
        
        return dungeon[0][0] + 1 ;
    }
};

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

bool myCompare (string i, string j) 
{ 
    return (i+j) > (j+i); 
}

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> tmp;
        bool allZero = true;
        for(int i : num) {
           allZero = allZero && i == 0;
           tmp.push_back(to_string(i));
        }
        
        if (allZero) return "0";
        
        sort(tmp.begin(), tmp.end(), myCompare);
        string output = "";
        
        for(string s : tmp)
           output+=s;
           
        return output;
    }
};

CanIWin

This was discussed at http://www.mitbbs.com/article_t/JobHunting/32861097.html

In "the 100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. 

What if we change the game so that players cannot re-use integers? 

For example, if two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100. This problem is to write a program that determines which player would win with ideal play. 

Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)", 
which returns true if the first player to move can force a win with optimal play. 

发信人: sirzen (会飞的鸭子), 信区: JobHunting
标  题: Re: 问一道L家的题
发信站: BBS 未名空间站 (Sun Jan  4 21:59:55 2015, 美东)

如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。

如果不可以重复选数字, there is a solution from http://blog.csdn.net/lsdtc1225/article/details/40342473:  
  public boolean canIWin(int max, int target) {
        List<Integer> candidates = new ArrayList<Integer>();
        for (int i = 1; i <= max; i++){
            candidates.add(i);
        }
        return helper(candidates, target);
    }

    public boolean helper(List<Integer> candidates, int target){
        if (candidates.get(candidates.size()-1) >= target){
            return true;
        }
        for (int i = 0; i < candidates.size(); i++){
            int removed = candidates.remove(i);
            if (!helper(candidates, target-removed)){
                candidates.add(i, removed);
                return true;
            }
            candidates.add(i, removed);
        }
        return false;
    }

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

    * The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.  

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

// Refer to : http://en.wikipedia.org/wiki/Longest_increasing_subsequence

class Solution {
    int insert(vector<int> &A, int lastIndex, int target) {
        int i = 0, j = lastIndex;
        while(i <= j) {
            int m = (i+j)/2;
            if (A[m] > target) 
               j = m - 1;
            else 
               i = m + 1;
        }
        A[i] = target;
        return i;
    }
public:
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> nums) {
        int n = nums.size();
        if (n < 2) return n;
        
        vector<int> M(n, 0);
        int longest = 0;
        M[0] = nums[0];
        
        for(int i =1; i < n; i++) 
            longest = max(longest, insert(M, longest, nums[i]));
        
        return longest+1;
    }
};

Reverse Linked List

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

ListNode *reverse(ListNode *head) {
        if (!head) return head;
        
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode *p = &dummy;
        while(head->next) {
            ListNode *T = head->next;
            head->next = T->next;
            T->next = p->next;
            p->next = T; 
        }
        
        return dummy.next;
    }

 ListNode *reverse(ListNode *head) {
        ListNode *prev = NULL;
        while(head) {
            ListNode* T = head->next;
            head->next = prev;
            prev = head;
            head = T;
        }
        
        return prev;
    }

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

class Solution {
    TreeNode *sortedListToBST(ListNode *&head, int start, int end)
    {
        if (start > end) return NULL;
        int m = (start + end)/2;
        
        TreeNode *left = sortedListToBST(head, start, m-1);
        TreeNode *root = new TreeNode(head->val);
        root->left = left;
        head = head->next;
        root->right = sortedListToBST(head, m+1, end);
        return root;   
    }
        
public:
   
      TreeNode *sortedListToBST(ListNode *head) {
        int count = 0;
        ListNode *p = head;
        while(p) {
            count++;
            p = p->next;
        }
        
        return sortedListToBST(head, 0, count-1);
    }
};

 TreeNode *sortedListToBST(ListNode *head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        
        ListNode *p = head;
        ListNode *pp = head->next;
        
        while(pp->next && pp->next->next) {
            p = p->next;
            pp = pp->next->next;
        }
        
        pp = p->next;
        p->next = NULL;
        TreeNode *root = new TreeNode(pp->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(pp->next);
        return root;
    }

子数组的最大差

Copied from: http://www.ninechapter.com/problem/31/

问题详情 

给定一个数组，求两个不相交的并且是连续的子数组A和B（位置连续），满足|sum(A) - sum(B)|最大（和之差的绝对值）。例如[2, -1, -2, 1, -4, 2, 8]，可以得到A=[-1, -2, 1, -4], B=[2, 8]，最大差为16。

解答 

答：

预处理每个位置往左/右的最大/最小子数组，然后再枚举划分位置，求得所有MaxLeft[i] - MinRight[i+1]和MaxRight[i+1] - MinLeft[i]中的最大值，即为答案。预处理O(n)，枚举划分位置O(n)，整体O(n)。

面试官角度：

在《九章算法面试题12 最大子区间/子矩阵》中，我们介绍了在O(n)时间内求得最大子数组(子区间)的方法，在这个题目中，实际上是通过枚举划分位置（AB两个数组中间的间隔）来将求两个数组之差最大的问题变为了求某个数组最大/最小子数组的问题。最小子数组只需要将每个数取相反数则可用最大子数组的方法来求得。

仔细考虑本题，实际上A数组和B数组一定是相邻数组，因为假设A和B之间存在一段数字，假设和为C，如果C>0则可以加入A和B中较大的一边让差变得更大，如果C<0，则加入较小的一边也可以让差变得更大，如果C=0，加入A或者B都不会影响结果。因此，只需要计算每个位置开始往左取到的最大/最小小连续和与往右取到的最大/最小连续和，即可得到答案。

Minimum Sum of Manhattan Distance

Shamelessly copied from:http://www.fgdsb.com/2015/01/02/minimum-manhattan-distance/

已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短并求出这个最短距离。

因为是曼哈顿距离，所以可以把x轴和y轴分离开来计算。

1. 针对x坐标对所有点排序。
2. 求一个数组，每个元素为对应点到其他所有点的在x轴上的距离和。
   这一步需要O(n)的算法，具体思路是，记录两个数组，left和right:
   left[i] = x[1] + x[2] + ... + x[i-1]
right[i] = x[i+1] + x[i+2] ... + x[n]
   然后对每个点
   sum[i] = x[i] * i - left[i] + right[i] - (n - 1 - i) * x[i]
3. 针对y坐标重复1和2的计算。
4. 求得每个点在x和y上的1D曼哈顿距离和之后，可以遍历所有点，直接找出最小值。

算法复杂度即为sort的复杂度,O(nlogn)

一个参考解答，同时也说了Follow up: 九章算法

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

map<pair<int,int>,int> mht_sum(const vector<Point>& pts, bool get_x) { int n = (int)pts.size(); vector<int> left(n), right(n); int sum = 0; for(int i = 0; i < n; ++i) { left[i] = sum; sum += get_x ? pts[i].x : pts[i].y; } sum = 0; for(int i = n - 1; i >= 0; --i) { right[i] = sum; sum += get_x ? pts[i].x : pts[i].y; } map<pair<int,int>,int> ret; for(int i = 0; i < n; ++i) { int p = get_x ? pts[i].x : pts[i].y; ret[{pts[i].x,pts[i].y}] = p * i - left[i] + right[i] - (n-1-i) * p; } return ret; } int min_mht_dis(vector<Point> pts) { sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){ return p0.x < p1.x; }); auto x_sums = mht_sum(pts, true); sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){ return p0.y < p1.y; }); auto y_sums = mht_sum(pts, false); int ret = INT_MAX; for(int i = 0; i < pts.size(); ++i) { ret = min(ret, x_sums[{pts[i].x,pts[i].y}] + y_sums[{pts[i].x,pts[i].y}]); } return ret; }

Check the original question at MITBBS

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
public:
    int searchInsert(vector<int> &A, int target) {
        int l = 0, r = A.size()-1;
        while(l <= r) {
            int m = (l+r)/2;
            if (A[m] < target)
               l = m + 1;
            else 
               r = m - 1;
        }
        return l;
    }
};

Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

          20

       /        \

    8           22

  /     \

4       12

class Solution {
    void pushLeft(stack<TreeNode *> &st, TreeNode *root, int k1) {
        while(root) {
            st.push(root);
            if (root->val < k1) break;
            
            root = root->left;
        }
    }
public:
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        stack<TreeNode *> st;
        vector<int> output;
        
        pushLeft(st, root, k1);
        
        while(st.size() > 0) {
            TreeNode *t = st.top();
            st.pop();
            
            if (t->val >= k1 && t->val <= k2)
                output.push_back(t->val);
            
            if (t->val <= k2) 
               pushLeft(st, t->right, k1);
        }
        
        return output;
    }
};

Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What is rotated array:

    - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

class Solution {
    void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    void reverse(vector<int> &num, int i, int j) {
        while(i < j) {
           swap(num, i, j);        
           i++;
           j--;
        }
    }
     
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int i = findMinPoint(nums);
        if (i == 0) return;
        reverse(nums, 0, i-1);
        reverse(nums, i, nums.size()-1);
        reverse(nums, 0, nums.size()-1);
    }
};

class Solution {
     void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int k = findMinPoint(nums);
        if (k == 0) return;
        
        int n = nums.size();
        int i = 0;
        int L = n;
        while(k > 0) {
            while(i+k <n) {
               swap(nums, i, i+k);
               i++;
            }
            
            int t = k;
            k = L%k? k - L%k : 0;
            L = t;
        }
    }
};