Binary Tree Longest Consecutive Sequence

Q:

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections.

Note: The path does not need to go through the root.

For example,

   4
  / \
 1   3
    / \
   2   5

Longest consecutive sequence path is 2-3-4, so return 3.

   5
  / \
 2   3
    / \
   2   4
  / \
 3   1

Longest consecutive sequence path is 1-2-3-4, so return 4.
A:

Mistakes:

309. Best Time to Buy and Sell Stock with Cooldown ---M !!!!!!!!!!!!!!!!!!!!!!!!!

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 (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

A:

每当新添加一个的时候，如果不动，就是dp[end-1] 否则就往前找买的那一天。

再加上前前的dp值

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

vector<int> dp(n, 0);

// only when we sell on the new day (i_th), we have profit

for (int end = 1; end < n; end++) {

dp[end] = dp[end - 1]; // we can: do nothing, so, dp[i] = 0

// profit only increase if we sell on the end day.

for (int start = 0; start < end; start++) {

auto profit = prices[end] - prices[start];

if (profit > 0) {

dp[end] = max(

dp[end], profit + (start - 2 >= 0 ? dp[start - 2] : 0));

}

}

}

return dp[n - 1];

}

};

---------------状态转移  。  只不过，我们之前的都是2个状态，现在是3个了-----------------

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int lastBuy = INT_MIN/2, lastCool = 0, lastSell = 0; // status-wise maximum profit 
        for(int v : prices)
        {
            int newBuy = max(lastCool - v, lastBuy);// either use previous buy, and buy this time
            int newCool = max(lastCool, lastSell);
            int newSell = lastBuy + v;
            
            lastSell = newSell;
            lastCool = newCool;
            lastBuy = newBuy;
        }
        return max(lastSell, lastCool);
    }
};

--------------利用状态图------------------------

// Author: Huahua
// Running time: 12 ms
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sold = 0;
        int rest = 0;
        int hold = INT_MIN;
        for (const int price : prices) {
            int prev_sold = sold;
            sold = hold + price;
            hold = max(hold, rest - price);
            rest = max(rest, prev_sold);
        }
        return max(rest, sold);
    }
};

Mistakes:

Best Meeting Point

Q:

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel
distance of 2+2+2=6 is minimal. So return 6.

A:

就是单独的计算横纵坐标的中间位置啊？注意，这里是median, 不是middle

public int minTotalDistance(int[][] grid) {
        if(grid==null || grid.length==0|| grid[0].length==0)
            return 0;
        int m = grid.length, n = grid[0].length;
        List<Integer> X = new LinkedList<Integer>();
        List<Integer> Y = new LinkedList<Integer>();
        double sumX=0, sumY =0;
        for(int i =0;i< m;i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 1){
                    X.add(i);
                    Y.add(j);
                    sumX += i;
                    sumY += j;
                }
            }
        }
        int medianX = X.get(X.size()/2);
        Collections.sort(Y);
        int medianY = Y.get(Y.size()/2);
        int res = 0;
        for(Integer x : X)
            res += Math.abs( x - medianX );
        for(Integer y : Y)
            res += Math.abs( y - medianY);
        return res;
    }

Mistakes:

269. Alien Dictionary --------H

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 

Explanation: The order is invalid, so return "".

Note:

• You may assume all letters are in lowercase.
• If the order is invalid, return an empty string.
• There may be multiple valid order of letters, return any one of them is fine.

A:

topological sort

比较tricky的地方，toplogical sort的时候， 如果找到的是GRAY node, 则返回 false.

class Solution {
public:
    string alienOrder(vector<string>& words) {
        int n = words.size();
        // toplogical sort
        unordered_map<char, int> colors;// WHITE, GRAY, BLACK
        for(int i =0;i<n;i++){
            for(char ch : words[i])
                colors[ch] = WHITE;// not visited
        }
        // build edges
        unordered_map<char, vector<char>> edges;
        for(int i =0;i<n-1;i++){
            string s1 = words[i];
            string s2 = words[i+1];
            int n1 = s1.length(), n2 = s2.length();
            for(int j = 0;j< min(n1,n2); j++){
                char c1 = s1[j];
                char c2 = s2[j];
                if(c1 != c2){
                    edges[c1].push_back(c2);
                    break;
                }else if(n1 > n2 && j == n2-1){// s1=="ab", s2 = "a"-->false; as "b" canot go before ""
                    return "";
                }
            }
        }
        string res= "";       
        for(auto it : colors){ // dfs 
            if(it.second==WHITE){
                if( dfs_visit(it.first, colors, edges, res))//if found circular
                    return "";
            }
        }
        return res;
    }
private:
    enum COLOR { WHITE=0, GRAY, BLACK};
    bool dfs_visit(char ch,   unordered_map<char, int> & colors, unordered_map<char, vector<char>> &edges, string &res){
        colors[ch] = GRAY;
        for(char nextCh : edges[ch]){
            if(colors[nextCh]==GRAY){
                return true;   // find circular 
            }else if(colors[nextCh] == WHITE){
                if(dfs_visit(nextCh, colors, edges, res)){
                    return true;  // find circular 
                }
            }
        }
        colors[ch] = BLACK;
        res = string(1,ch)+res;
        return false;
    }
};

Mistakes:

为了处理["abc", "ab"]  ，返回应该是 "";       因为“b“ 不能在”“ 前面。

259. 3Sum Smaller ------------M

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Follow up: Could you solve it in O(n2) runtime?

 

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

 

Constraints:

• n == nums.length
• 0 <= n <= 300
• -100 <= nums[i] <= 100
• -100 <= target <= 100

A:
思路很直观，就是 two pointer techniques
内层要计算的时候， 每次考虑的是： 前一个固定，一共有多少个合适的。

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int res = 0;
        for(int i =0;i<n-2;i++){
            int k = n-1; // increase k would get smaller
            for(int j = i+1;j<k;j++ ){
                while(k > j && nums[i] + nums[j] + nums[k] >= target){ //k is strictly decreasing
                    k--;
                }
                res += k-j;
            }
        }
        return res;
    }
};

Mistakes:

275. H-Index II ------------M ~~~这次的比较简洁，以前写的太啰嗦

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:

• This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
• Could you solve it in logarithmic time complexity?

A:
很直观，就是二分查找

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int start = 0, end = n-1;
        while(start <=end){
            int mid = (start+end)/2;
            if(citations[mid]>=n - mid){
                end = mid -1;
            }else{
                start = mid+1;
            }
        }
        return n - start;
    }
};

Mistakes:

274. H-Index ----------M

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

A:
就是sort后，

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        sort(citations.begin(), citations.end(), greater<int>());
        for(int i =0;i< n;i++)
            if(citations[i]<i+1)
                return i;
        return n;
    }
};