174. Dungeon Game ------hard ~~~~~~~~~~

The demons had captured the princess 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 was initially positioned in the top-left room and must fight his way through 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 (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

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

Return the knight's minimum initial health so that he can rescue the princess.

Note that 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.

 

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

 

Constraints:

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

A:

就是简单的2D  , 但是，这里要        backward calculating

每个A[i][j] 表示的是这个位置需要多少engergy进来。但是由于前面的位置不允许出来的engergy<=0    ---------》 A[i][j] >= 1

比较tricky的是: 要注意每次出去的生命值不能 <= 0    , aka, 每个位置剩余的生命必须 > 0


直接在dungeon[][]上面改，没有用额外的空间. 记录该点 entering的最少的要求

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        int rightNeed = 0, downNeed = 0;
        // use dungeon in place, to mark the min possible
        // entering_life for [i][j] so it can safely go right&down
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1 ; j >=0 ; j--) {
                rightNeed = (j == n-1) ? 1 : dungeon[i][j+1];
                downNeed = (i == m-1)? 1 : dungeon[i+1][j];
                // entering_life = (at least 1)  
                // entering_life + cur_value >= max( right_left_life ,  down_left_life) 
                dungeon[i][j] = max(1,  min( rightNeed, downNeed) - dungeon[i][j] );
            }
        }
        return dungeon[0][0];
    }
};

上面的是有问题的。 在于如果没有右边或者左边的时候，我们就不能往那边走

下面是修改后的代码

class Solution {

public:

int calculateMinimumHP(vector<vector<int>>& dungeon) {

int m = dungeon.size(), n = dungeon[0].size();

int rightNeed = 0, downNeed = 0;

// use dungeon in place, to mark the min possible

// entering_life for [i][j] so it can safely go right&down

for (int i = m - 1; i >= 0; i--) {

for (int j = n - 1; j >= 0; j--) {

if (i == m - 1 && j == n - 1) {

dungeon[i][j] = max(1, 1 - dungeon[i][j]);

} else {

rightNeed = (j == n - 1) ? INT_MAX : dungeon[i][j + 1]; // INT_MAX for no-go

downNeed = (i == m - 1) ? INT_MAX : dungeon[i + 1][j];

// entering_life = (at least 1)

// entering_life + cur_value >= max( right_left_life ,

// down_left_life)

dungeon[i][j] =

max(1, min(rightNeed, downNeed) - dungeon[i][j]);

}

}

}

return dungeon[0][0];

}

};

因此最右下角的点，需要单独处理

Mistakes:
1: 一开始A[i][j]的定义不清楚。
2： 忘了检查A[i][j] >0

157. Read N Characters Given Read4 -----E

Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

 

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

    Parameter:  char[] buf4
    Returns:    int

Note: buf4[] is destination not source, the results from read4 will be copied to buf4[]

Below is a high level example of how read4 works:

File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf4 = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf = "", fp points to end of file

 

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

    Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

 

Example 1:

Input: file = "abc", n = 4
Output: 3
Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.

Example 2:

Input: file = "abcde", n = 5
Output: 5
Explanation: After calling your read method, buf should contain "abcde". We read a total of 5 characters from the file, so return 5.

Example 3:

Input: file = "abcdABCD1234", n = 12
Output: 12
Explanation: After calling your read method, buf should contain "abcdABCD1234". We read a total of 12 characters from the file, so return 12.

Example 4:

Input: file = "leetcode", n = 5
Output: 5
Explanation: After calling your read method, buf should contain "leetc". We read a total of 5 characters from the file, so return 5.

 

Note:

• Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
• The read function will only be called once for each test case.
• You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.

A:
就是简单的每次计数，对比

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char *buf4);
 */

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        int count = 0;
        char* buf4 = new char[4];
        while(count < n){// if need more to read
            int c = read4(buf4);
            if(c==0){
                break;
            }
            for(int i=0;i<c;i++){
                *(buf+count) = *(buf4+i);
                count++;
                if(count>=n)
                    break;
            }
        }        
        return count;
    }
};

NOTE:

char* buf4 = new char[4];

写成   char (*buf4)[4];   会导致 调用read4(buf4)出错

Number of 1 Bits

Q:
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

A:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res++;
            n = n&(n-1);
        }
        return res;
    }
}
 

//

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i =0;i<32;i++){
            if( ( n & (1<<i) ) != 0)
                count++;
        }
        return count;
    }
}

Mistakes:

1: 开始都转换成long类型。来处理负值。但那样是不对的。

153. Find Minimum in Rotated Sorted Array

Q:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.

A:  

*************分别找两边最小的，然后取最小的。

public class Solution {
    public int findMin(int[] num) {
        return findMin(num,0,num.length-1);
    }
    private int findMin(int[] num, int left, int right){
        if(left==right || num[right]>num[left])
            return num[left];
        int mid = (left+right)/2;
        int l = findMin(num,left,mid-1);
        int r = findMin(num,mid+1,right);
        return Math.min(num[mid], Math.min(l,r));
    }
}

*****************上面的还是太慢，  看这个*********

public class Solution {
    public int findMin(int[] nums) {
        return helper(nums,0, nums.length-1);
    }
    private int helper(int[] nums, int start, int end){
        if(nums[start] <= nums[end])
            return nums[start];
        int mid = (start+end)/2;
        if(start==mid)
            return nums[end];
        return nums[start]<nums[mid]?helper(nums, mid+1, end) : helper(nums,start, mid);
    }
}
 

158. Read N Characters Given Read4 II - Call multiple times --------H

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

 

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

    Parameter:  char[] buf4
    Returns:    int

Note: buf4[] is destination not source, the results from read4 will be copied to buf4[]

Below is a high level example of how read4 works:

File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf = "", fp points to end of file

 

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

    Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

 

Example 1:

File file("abc");
Solution sol;
// Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.
sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1.
sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Example 2:

File file("abc");
Solution sol;
sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

 

Note:

• Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
• The read function may be called multiple times.
• Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
• You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
• It is guaranteed that in a given test case the same buffer buf is called by read.

A： 
这个题目tricky 的地方在于：  以前遗留下来的 buffer ，可能这次还读取不完。

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char *buf4);
 */

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    int read(char *buf, int n) {
        int count = 0;
        while(count < n){
            // first read up the values in buf4
            for(; iStart<preCount && count < n;iStart++){
                *(buf+count++) = *(buf4+iStart);
            }
            if(count>=n){
                break;
            }
            // read another round of buf
            if(iStart >= preCount){
                preCount = read4(buf4);
                iStart = 0;
            }
            if(preCount==0)
                break; // if no data readin anymore
        }
        return count;
    }
private:
    char * buf4 = new char[4];
    int preCount = 0;
    int iStart = 0; // position that we can start to read new char    
};

错误：

忘了检查if(preCount==0)

190. Reverse Bits (easy)

Q:

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

A:
思路1： 每个bit 单独操作。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i =0;i<32;i++)
        {
            int mask = 1<<i;
            if(n & mask)            
                res |= (1<<(31-i));  // i_th bit will go to 31-i bit
        }
        return res;
    }
};

Mistakes:
我草，就是上面的 写成了   i<31 浪费了好久阿好久。 日他娘的

159. Longest Substring with At Most Two Distinct Characters ----M

Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

A:

****************第一遍*****************************
记录了两个char 来计算。 这里tricky的一点就是，如果新加入了第三个char , 在 i 位置，那么i-1

位置就是 另外一个char。  倒退回去就知道最新长度了

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int n = s.length();
        if(n<=2)
            return n;
        // sliding window        
        int pre = -1;
        char c1 = s[0], c2 = c1;
        int res = 0;
        for(int i = 0;i<s.length();i++){
            char ch = s[i];
            if(ch != c1 && ch != c2){
                c2 = ch;
                c1 = s[i-1];
                pre = i-2;
                while(pre>=0 && s[pre]==c1){
                    --pre;
                }
            }
            res = max(res, i - pre);
        }
        return res;
    }
};

*******用Map  来计数****************

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int res = 0, pre = -1;
        Map<Character,Integer> map = new HashMap();
        for(int i =0;i< s.length(); i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                map.put(ch,1+map.get(ch));
            }else{
                while(map.size() >= 2){
                    char tmp = s.charAt(++pre);
                    map.put(tmp,map.get(tmp)-1);
                    if(map.get(tmp)==0)
                        map.remove(tmp);
                }
                map.put(ch,1);
            }
            res = Math.max(res, i-pre);
        }
        return res;
    }
}

161. One Edit Distance ---------M

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

• Insert exactly one character into s to get t.
• Delete exactly one character from s to get t.
• Replace exactly one character of s with a different character to get t.

 

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

 

Constraints:

• 0 <= s.length <= 104
• 0 <= t.length <= 104
• s and t consist of lower-case letters, upper-case letters and/or digits.

A:


*************递归*****************

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n1 = s.length();
        int n2 = t.length();
        if(n1 > n2)
            return isOneEditDistance(t,s);
        if(n1==0){
            return n2==1;
        }
        if(s[0]==t[0]){
            return isOneEditDistance(s.substr(1), t.substr(1));
        }else{ // not equal
            if(n1==n2) // replace on first
                return s.substr(1) == t.substr(1);
            else // remove the first of longer
                return s == t.substr(1);
        }
    }
};

不用递归，  直接用两个指针， 这样快一些。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int n1 = s.length();
        int n2 = t.length();
        if(n1 > n2)
            return isOneEditDistance(t,s);
        if(n1+1<n2)
            return false;        
        for(int is = 0; is<n1;is++){
            if( s[is] != t[is]){
                if(n1==n2)
                    return s.substr(is+1) == t.substr(is+1);
                else
                    return s.substr(is) == t.substr(is+1);
            }
        }
        return n1+1==n2;// for case s="ab"  t="abc"
    }
};

就是简单的分情况讨论

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int n1 = s.length(), n2 = t.length();
        if( n1< n2)
            return n1+1 == n2 && delOneStep(t,s);
        else if(n1 == n2)
            return changeOneStep(s,t);
        else return n1-1 == n2 && delOneStep(s,t);
    }
    private boolean changeOneStep(String s, String t){
        int nDif = 0;
        for(int i =0;i<s.length();i++){
            if(s.charAt(i) != t.charAt(i))
                nDif++;
        }
        return nDif==1;
    }
    private boolean delOneStep(String sLong, String sShort){
        int dif = 0;
        for(int i = 0;i<sShort.length();i++){
            if(sShort.charAt(i)!=sLong.charAt(i+dif)){
                if(dif!=0)
                    return false;
                i--;
                dif=1;
            }
        }
        return true;
    }
}

Mistakes:

162. Find Peak Element -M

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

A:
------------------------check left part, if works,  then stop, Otherwise, check right side ---------

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 1 or nums[0]>nums[1])
            return 0;
        if(nums[n-1] > nums[n-2])
            return n-1;
        return helper(nums, 0,n-1);
    }
private:
    int helper(vector<int>& nums, int start, int end)// start/end is valid, no need to check peak element
    {   
        if(start+1 > end-1)
            return -1;
        int mid = start + (end-start)/2;
        if(nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1])
            return mid;
        int leftRes = helper(nums, start, mid);
        if(leftRes>=0)
            return leftRes;
        return helper(nums,mid, end);
    }
};

Mistakes:

163. Missing Ranges ----M

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

• "a->b" if a != b
• "a" if a == b

 

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Example 2:

Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".

Example 3:

Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Explanation: The only missing range is [-3,-1], which becomes "-3->-1".

Example 4:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Example 5:

Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]

 

Constraints:

• -109 <= lower <= upper <= 109
• 0 <= nums.length <= 100
• lower <= nums[i] <= upper
• All the values of nums are unique.

A:
每看一个数字，表示之前的都处理完了。 trick： 把upper+1  放到最后

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        int pre = lower-1;
        nums.push_back(upper+1);
        vector<string> res;
        for(auto end : nums){
            if(end != pre+1){
                res.push_back(getStr(pre+1, end-1));
            }
            pre = end;
        }
        nums.pop_back();// pop the newly added upper+1
        return res;
    }
private:
    string getStr(int a , int b){
        if(a==b){
            return to_string(a);
        }else{
            return to_string(a)+"->"+to_string(b);
        }
    }
};

Maximum Gap

Q:



A:





Mistakes:

179. Largest Number ----- Medium !!!!!!!

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

 

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

A:

就是简单的两个int 按照string的方式对比。---------核心是如果前边相等，则取其substring，继续比较
因此自己写了一个 comparator method  (不能用通常的struct. 因为需要递归调用）

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        priority_queue<string, vector<string>, decltype(compare)*> queue(
            compare);
        for (auto a : nums)
            queue.push(to_string(a));
        string res;
        while (!queue.empty()) {
            auto top = queue.top();
            if (!(top[0] == '0' && res == ""))
                res += top;
            queue.pop();
        }
        return res == "" ? "0" : res;
    }
private:
    static bool compare(const string& a, const string& b) {
        if (a == b) {
            return true;
        }
        if (a.size() >= b.size()) {
            for (int i = 0; i < b.size(); i++) {
                if (a[i] == b[i]) {
                    continue;
                } else {
                    return a[i] < b[i];
                }
            }
            return compare(a.substr(b.size()), b);
        } else {
            return !compare(b, a);
        }
    }
};

------第二遍 。 关于comparator ，有更好的比较方法-------------------

class Solution {

public:

string largestNumber(vector<int>& nums) {

vector<string> V;

for (auto val : nums)

V.push_back(to_string(val));

sort(V.begin(), V.end(), [](const string& a, const string& b) {

return a + b < b + a; // in ascending order, since we pop from back

});

string res = "";

while (!V.empty()) {

auto s = V.back();

V.pop_back();

if (!(res == "" && s == "0"))

res += s;

}

return res == "" ? "0" : res;

}

};

Mistakes:
1 :  第一遍的时候， compare函数一开始没有没有注意，因为我们要的是max Heap， 因此要按照 a < b . 默认是max_heap

2：compare函数中，如果s1,s2 之前的都相同。那么要对比的是取下来的和 另外一个短的全部。

3:  In C++, "abb" < "abbc" evaluates to true.  Since, empty is less than anything

3：  输入是 0, 0 , 输出应该是0.  因此这里要检查最后结果的首位。(又错了，哎）



Learned:

In C++, to sort an array in reverse order, we do not need write our own Comparator (though we could)

See this page: https://www.geeksforgeeks.org/comparator-in-cpp/

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int main() {

std::vector<int> nums{3, 4, 1, 8};

sort(nums.rbegin(), nums.rend()); // optimization: try big numbers first

for (auto a : nums) {

cout << a << " ";

}

return 0;

}

Will print : 8 4 3 1