Day 102, #174, Dungeon Game

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();
        vector<vector<int> > dp(m,vector<int>(n,0));
        dp[m - 1][n - 1] = max(0,-dungeon[m - 1][n - 1]);
        
        for (int i = n - 2; i >= 0; i--) {
            dp[m - 1][i] = max(dp[m - 1][i + 1] - dungeon[m - 1][i],0);
        }
        
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = max(dp[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--) {
                dp[i][j] = max(min(dp[i][j + 1],dp[i + 1][j]) - dungeon[i][j], 0);
            }
        }

        return dp[0][0] + 1;
    }
};

O(n) space

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(),n = dungeon[0].size();
        vector<int> dp(n + 1,INT_MAX);

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    dp[j] = max(-dungeon[i][j],0);
                    continue;
                }
                dp[j] = max(min(dp[j],dp[j + 1]) - dungeon[i][j],0);
            }
        }
        return dp[0] + 1;
    }
};

递归：
从此可以看出需要DP，
返回前，最大血量要跟0做个对比，避免返回负数
最后结果要加1，因为骑士的骑士生命不能为0

int minHealth(vector<vector<int>> &matrix,int i, int j) {
 if (i == matrix.size() || j == matrix[0].size()) return INT_MAX;
 if (i == matrix.size() - 1 && j == matrix[0].size() - 1) {
  return max(-matrix[i][j],0);
 }

 return max(min(minHealth(matrix,i + 1,j),minHealth(matrix,i,j + 1)) - matrix[i][j],0);
}

Day 101, ##, Reverse Words in a String II

Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
------------------------------------------------------

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(),s.end());
        int i = 0;
        while (i < s.length()) {
            int start = i;
            while (i < s.length() && s[i] != ' ') {
                i++;
            }
            
            reverse(s.begin() + start, s.begin() + i);
            i++;
        }
    }
};

Day 100, ##, Two Sum III - Data structure design, Factorial Trailing Zeroes

Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

------------------------------------------

class TwoSum {
public:
 void add(int number) {
     if (dic.find(number) == dic.end()) {
         dic[number] = 1;
     }else {
         dic[number]++;
     }
 }

 bool find(int value) {
     for (auto i = dic.begin(); i != dic.end(); i++) {
         if (dic.find(value - i->first) != dic.end()) {
             if (value == i->first * 2 && i->second == 1) {
                 continue;
             }
             return true;
         }
     }
     
     return false;
 }
private:
    unordered_map<int,int> dic;
};

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
----------------------------------------

class Solution {
public:
    int trailingZeroes(int n) {
        int rt = 0;
        while (n) {
            rt += n / 5;
            n /= 5;
        }
        return rt;
    }
};

Day 99, ##, Fraction to Recurring Decimal, Majority Element, Majority Number II

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

---------------------------------------------
Map 里面记录是某一个数的开始的index
reference
注意正负号跟溢出，casting long long
27行，先存map，再乘10

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string rt = "";
        
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            rt = "-";
        }
        
        long long dividend = abs((long long)numerator);
        long long divisor = abs((long long)denominator);
        rt += to_string(dividend / divisor);
        
        dividend %= divisor;
        if (dividend == 0) return rt;
        
        rt += '.';
        unordered_map<int,int> mapping;
        
        while (dividend != 0) {
            if (mapping.find(dividend) != mapping.end()) {
                rt.insert(mapping[dividend],"(");
                rt += ")";
                return rt;
            }
            mapping[dividend] = rt.size();
            dividend *= 10;
            rt += to_string(dividend / divisor);
            dividend %= divisor;
        }

        return rt;
    }
};

In Java, updated on Feb-13th-2019

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        StringBuilder sb = new StringBuilder();
        
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            sb.append("-");
        }
        
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        
        sb.append(num / den);
        num %= den;
        if (num == 0) return sb.toString();
        sb.append(".");
        
        Map<Long, Integer> map = new HashMap<>();
        map.put(num, sb.length());
        
        while (num > 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                sb.insert(map.get(num),"(");
                sb.append(")");
                return sb.toString();
            }
            
            map.put(num, sb.length());
        }
        
        return sb.toString();
    }
}

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
-----------------------------------------------------
fact: we are given an array with a majority element in it.
每次都丢掉2个不同数，majority最后肯定会被留下来

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int count = 1;
        int countElem = num[0];
        
        for (int i = 1; i < num.size(); i++) {
            if (count == 0) {
                countElem = num[i];
                count++;
                continue;
            }
            if (countElem == num[i]) {
                count++;
            }else {
                count--;
            }
            
        }
        
        return countElem;
    }
};

Majority Number II 

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.
Find it.

Note

There is only one majority number in the array

Example

For [1, 2, 1, 2, 1, 3, 3] return 1

-------------------------------------
每次都丢掉3个不同的数，最后超过1/3的肯定会被留下来
最后还要重新对留下来的2个数重新计数，因为超1/3的数可能会被过度消耗
举例：1，1，1，1，2，2，3，3，4，4，4

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number occurs more than 1/3.
     */
    int majorityNumber(vector<int> nums) {
        // write your code here
        int count_1 = 1, count_2 = 0;
        int cand_1 = nums[0], cand_2;
        
        for (int i = 1; i < nums.size(); i++) {
            if (count_1 == 0 && cand_2 != nums[i]) {
                count_1 = 1;
                cand_1 = nums[i];
                continue;
            }
            if (count_2 == 0 && cand_1 != nums[i]) {
                count_2 = 1;
                cand_2 = nums[i];
                continue;
            }
            
            if (nums[i] != cand_1 && nums[i] != cand_2) {
                count_1--;
                count_2--;
            }
            
            if (nums[i] == cand_1) {
                count_1++;
            }
            if (nums[i] == cand_2) {
                count_2++;
            }
        }
        
        count_1 = 0;
        count_2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == cand_1) count_1++;
            if (nums[i] == cand_2) count_2++;
        }
        
        if (count_1 > count_2) {
            return cand_1;
        }else {
            return cand_2;
        }
    }
};

Day 98, ##, Maximum Gap

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
------------------------------------------------------------------------------
reference 
use n - 1 buckets
注意 bucketSize用double

class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2) return 0;
        int min_val = num[0];
        int max_val = num[0];
        for (int i = 1; i < num.size(); i++) {
            min_val = min(num[i],min_val);
            max_val = max(num[i],max_val);
        }
        
        double bucketSize = (max_val - min_val) * 1.0 / (num.size() - 1);
        vector<int> maxBucket(num.size() - 1, -1);
        vector<int> minBucket(num.size() - 1, INT_MAX);
        for (int i = 0; i < num.size(); i++) {
            if (num[i] == min_val || num[i] == max_val) continue;
            int bucket = (int)((num[i] - min_val) / bucketSize);
            maxBucket[bucket] = max(num[i],maxBucket[bucket]);
            minBucket[bucket] = min(num[i],minBucket[bucket]);
        }
        
        int maxGap = INT_MIN;
        int preMax = min_val;
        for (int i = 0; i < num.size() - 1; i++) {
            if (maxBucket[i] == -1) continue;
            maxGap = max(maxGap,minBucket[i] - preMax);
            preMax = maxBucket[i];
        }
        maxGap = max(maxGap,max_val - preMax);
        return maxGap;
    }
};

Update Feb-18-2015
radix sort

class Solution {
public:
    int maximumGap(vector<int> &num) {
        if (num.size() < 2) return 0;
        vector<int> one;
        vector<int> zero;
        
        for (int i = 0; i < 32; i++) {
            int mask = 1 << i;
            for (int j = 0; j < num.size(); j++) {
                if (num[j] & mask) {
                    one.push_back(num[j]);
                }else {
                    zero.push_back(num[j]);
                }
            }
            
            zero.insert(zero.end(),one.begin(),one.end());
            num =zero;
            one.clear();
            zero.clear();
        }
        
        int maxGap = 0;
        for (int i = 1; i < num.size(); i++) {
            maxGap = max(num[i] - num[i - 1],maxGap);
        }
        
        return maxGap;
    }
};

if (num[j] & mask) 判断的是0或者是非0，而不是1或0
radix sort, 10-base
REF

class Solution {
public:
    int getMax(vector<int> &nums) {
        int maxNum = 0;
        for (int i = 0; i < nums.size(); i++) {
            maxNum = max(nums[i],maxNum);
        }
        return maxNum;
    }

    void countSort(vector<int>& nums, int m) {
        vector<int> count(10,0);
        for (int i = 0; i < nums.size(); i++) {
            count[(nums[i] / m) % 10]++;
        }
        
        // calculate start point for each key
        int total = 0;
        for (int i = 0; i < 10; i++) {
            int oldCount = count[i];
            count[i] = total;
            total += oldCount;
        }
        
        // sort
        vector<int> rt(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            rt[count[(nums[i] / m) % 10]] = nums[i];
            count[(nums[i] / m) % 10]++;
        }
        
        nums = rt;
    }

    int maximumGap(vector<int>& nums) {
        int maxNumber = getMax(nums);
        for (int m = 1; m <= maxNumber; m *= 10) {
            countSort(nums,m);
        }
        
        int maxGap = 0;
        for (int i = 1; i < nums.size(); i++) {
            maxGap = max(maxGap,nums[i] - nums[i - 1]);
        }
        
        return maxGap;
    }
};

Day 97, ##, Largest Number, Compare Version Numbers

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

class Solution {
public:
    static bool cmp(string s1,string s2) {
        return (s1 + s2) < (s2 + s1);
    }
    
    string largestNumber(vector<int> &num) {
        vector<string> strings(num.size());
        for (int i = 0; i < num.size(); i++) {
            strings[i] = to_string(num[i]);
        }
        
        sort(strings.begin(),strings.end(),cmp);
        if (strings.back() == "0") {
            return "0";
        }
        
        string rt = "";
        for (int i = strings.size() - 1; i >= 0; i--) {
            rt += strings[i]; 
        }
        
        return rt;
    }
};

Compare Version Numbers

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

----------------------------------------------------------

class Solution {
public:
    int getNextSubString(string &str, int &i) {
        int rt = 0;
        while (i < str.length() && str[i] != '.') {
            rt = rt * 10 + (str[i] - '0');
            i++;
        }
        
        i++;
        return rt;
    }

    int compareVersion(string version1, string version2) {
        int itr1 = 0, itr2 = 0;
        while (itr1 < version1.length() || itr2 < version2.length()) {
            int s1 = getNextSubString(version1,itr1);
            int s2 = getNextSubString(version2,itr2);

            if (s1 > s2) return 1;
            if (s1 < s2) return -1;
        }
        return 0;
    }
};

Day 96, ##, Topological Sorting

Topological Sorting 

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A-->B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Note

You can assume that there is at least one topological order in the graph.

Example

For graph as follow:

The topological order can be:
[0, 1, 2, 3, 4, 5]
or
[0, 2, 3, 1, 5, 4]
or
....

Challenge

Can you do it in both BFS and DFS?

----------------------------------------------------------------------------
 DFS

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
     
    void dfs(DirectedGraphNode * node, vector<DirectedGraphNode*> &rt,unordered_set<DirectedGraphNode*> &visit) {
        visit.insert(node);
        for (int i = 0; i < node->neighbors.size(); i++) {
            if (visit.find(node->neighbors[i]) == visit.end()) {
                dfs(node->neighbors[i], rt, visit);
            }
        }
        
        rt.push_back(node);
    }
     
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        vector<DirectedGraphNode*> rt;
        unordered_set<DirectedGraphNode*> visit;
        
        for (int i = 0; i < graph.size(); i++) {
            if (visit.find(graph[i]) == visit.end()) {
                dfs(graph[i],rt,visit);
            }
        }
        
        reverse(rt.begin(),rt.end());
        return rt;
    }
};