backup

https://leetcode.com/problems/solve-the-equation/description/



https://leetcode.com/problems/find-duplicate-subtrees/description/

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
      
          
           
           2,4,#
           
           
           
           
           
           
(1),2,4,#


"#" :1
"4,#":1  =>     list.add(currNode) 
"2,4,#":1


https://leetcode.com/problems/encode-and-decode-tinyurl/description/

below is the tiny url solution in java, also this is the similar method in industry. In industry, most of shorten url service is by database, one auto increasing long number as primary key. whenever a long url need to be shorten, append to the database, and return the primary key number. (the database is very easy to distribute to multiple machine like HBase, or even you can use the raw file system to store data and improve performance by shard and replica).
Note, it's meaningless to promise the same long url to be shorten as the same short url. if you do the promise and use something like hash to check existing, the benefit is must less than the cost.
Note: if you want the shorted url contains '0-9a-zA-Z' instead of '0-9', then you need to use 62 number system, not 10 number system(decimal) to convert the primary key number. like 123->'123' in decimal, 123->'1Z' in 62 number system (or '0001Z' for align).


public class Codec {
    List<String> urls = new ArrayList<String>();
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        urls.add(longUrl);
        return String.valueOf(urls.size()-1);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        int index = Integer.valueOf(shortUrl);
        return (index<urls.size())?urls.get(index):"";
    }
}


https://leetcode.com/problems/super-washing-machines/description/


[0,0,11,5].



[-4,-4,-1,    1].
[0,-8,7,1]



https://leetcode.com/problems/find-the-derangement-of-an-array/description/

public class Solution {
    public int findDerangement(int n) {
        Integer[] memo = new Integer[n + 1];
        return find(n, memo);
    }
    public int find(int n, Integer[] memo) {
        if (n == 0)
            return 1;
        if (n == 1)
            return 0;
        if (memo[n] != null)
            return memo[n];
        memo[n] = (int)(((n - 1L) * (find(n - 1, memo) + find(n - 2, memo))) % 1000000007);
        return memo[n];
    }
}

        if (n<2) return 0;
        long f[]=new long[n+1];
        f[1]=0;f[2]=1;
        for (int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])*(i-1)%1000000007;
        return (int)f[n];


n^2

https://leetcode.com/problems/set-mismatch/description/
1 2 2 4

sum = n*(n+1)/2 = 10
10-1=9
9-2=7
7-2=5  (2)
5-4=1

1+2 = 3

We can save the space used in the last approach, if we can somehow, include the information regarding the duplicacy of an element or absence of an element in the numsnums array. Let's see how this can be done.

We know that all the elements in the given numsnums array are positive, and lie in the range 11 to nn only. Thus, we can pick up each element ii from numsnums. For every number ii picked up, we can invert the element at the index \left|i\right|∣i∣. By doing so, if one of the elements jj occurs twice, when this number is encountered the second time, the element nums[\left|i\right|]nums[∣i∣] will be found to be negative. Thus, while doing the inversions, we can check if a number found is already negative, to find the duplicate number.

After the inversions have been done, if all the elements in numsnums are present correctly, the resultant numsnums array will have all the elements as negative now. But, if one of the numbers, jj is missing, the element at the j^{th}j
​th
​​  index will be positive. This can be used to determine the missing number.


public class Solution {
    public int[] findErrorNums(int[] nums) {
        int dup = -1, missing = 1;
        for (int n: nums) {
            if (nums[Math.abs(n) - 1] < 0)
                dup = Math.abs(n);
            else
                nums[Math.abs(n) - 1] *= -1;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > 0)
                missing = i + 1;
        }
        return new int[]{dup, missing};
    }
}

4 4 1 3

-4 4 -1 -3  dup = 4




1  3  3  4

-1    -3 -4    dup = 3
















https://leetcode.com/problems/shopping-offers/description/
https://discuss.leetcode.com/topic/95200/simple-java-recursive-solution

[2,5]
[[1,0,5],[1,2,10]]
[39,39]
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        Map<List<Integer>, Integer> dp = new HashMap<>();
        List<Integer> allZero = new ArrayList<>();
        for(int i=0;i<needs.size();i++) {
            allZero.add(0);
        }
        dp.put(allZero, 0);
        return dfs(needs, price, special, dp);
    }
    private int dfs(List<Integer> needs, List<Integer> price, List<List<Integer>> special, Map<List<Integer>, Integer> dp) {
        if(dp.containsKey(needs)) return dp.get(needs);
        int res = Integer.MAX_VALUE;
        for(List<Integer> s : special) {
            List<Integer> needsCopy = new ArrayList<>(needs);
            boolean valid = true;
            for(int i=0;i<needs.size();i++) {
                needsCopy.set(i, needsCopy.get(i) - s.get(i));
                if(needsCopy.get(i) < 0) {
                    valid = false;
                    break;
                }
            }
            if(valid) {
                res = Math.min(res, s.get(needs.size()) + dfs(needsCopy, price, special, dp));
            }
        }
        //What if we do not use specials? specials can be deceiving,
        //perhaps buying using regular prices is cheaper.
        int noSpecial = 0;
            for(int i=0;i<needs.size();i++) {
                noSpecial += needs.get(i) * price.get(i);
            }
        res = Math.min(res, noSpecial);    

        dp.put(needs, res);
        return res;
    }
}
    
    


public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    int result = Integer.MAX_VALUE;
    //apply each offer to the needs, and recurse
    for(int i = 0; i < special.size(); i++) {
        List<Integer> offer = special.get(i);
        boolean invalidOffer = false;
        for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
            int remain = needs.get(j) - offer.get(j);
            needs.set(j, remain);
            if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
        }
        if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
            result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(offer.size() - 1));
        }
        for(int j = 0; j < needs.size(); j++) { // reset the needs
            int remain = needs.get(j) + offer.get(j);
            needs.set(j, remain);
        }
    }
    // choose b/w offer and non offer
    int nonOfferPrice = 0;
    for(int i = 0; i < needs.size(); i++) {
        nonOfferPrice += price.get(i) * needs.get(i);
    }
    return Math.min(result, nonOfferPrice);
}



DP => 路径问题 
        最小最大  
        minmax

public int solution(String input) {
     int n = input.length;
     int[][] dp = new int[n][n];
 
    for(int k=1; k < n; k++) {
       for (int i = 0, j = k; i < n && j < n; i++, j++) {
           if (input.charAt(i) == input.charAt(j)) {     /////(aa)a   
                 dp[i][j] = dp[i + 1][j - 1];               //dp[0][1] = dp[0+1][1-1]  dp[1][0] 
              }else {
                 dp[i][j] = Math.min(Math.min(dp[i+1][j-1], dp[i+1, j]), dp[i, j-1]) + 1;
              }
       }
    }
    return dp[0][j];
    

\\\
 \\\
  \\\






    0 1 2 3 4       (str)in  =>  saast
  0 0 1 1 2 2       (sts)(0-2)
  1 0 0 1 1 2       
  2 0 0 0 1 1
  3 0 0 0 0 1 
  4 0 0 0 0 0
  
  
  >>>>>>>>>
    (0,4) => (1,3) => (2,2)
    (2,2) => (1,3) => (0,4)
     dp[i+1, j]
    s(tri)n 
    st(r)in
    

  
   
   
                   saast   i= 0, j=2
                   dp[i+1][j-1]
                   
                   => palindrome string
    0 1 2 3 4       
  0 0 1 1 0 1  
  1 0 0 0 1 2 
  2 0 0 0 1 1
  3 0 0 0 0 1 
  4 0 0 0 0 0




[['E', 'E', 'E', 'E', 'E'],
 ['E4', 'E5', 'M', 'E', 'E'],
 ['E1', '1', 'E6', 'E', 'E'],
 ['E'<<, 'E3', 'E7', 'E', 'E']]

http://codeforces.com/blog/entry/47344

Given string s, find minimum number of operations to convert it into Palindromic string. Operations are: 1) Insert a new character anywhere into the string (including its beginning and end). 2) Remove a single character. 3) Replace a single character by another character.

You can use dynamic programming approach to solve this problem. dp[i, j] — minimum number of operations to convert substring s[i..j] into palindrome. Below is the transitions:
Obviously, dp[i, j] = 0 if i >= j
And in general dp[i, j] is minimum of:
dp[i+1, j-1] if s[i] == s[j]
dp[i+1][j-1] + 1 # replace character s[i] to s[j] OR s[j] to s[i]
dp[i+1, j] + 1 # remove i-th character OR insert a new character right after j-th position
dp[i, j-1] + 1 # remove j-th character OR insert a new character right before i-th position

http://codeforces.com/blog/entry/47344

1)a b a
2) a b c d b => a (b c d) a
4) a b b a d  =>  d a b b a d
   d (a b b a )d



i - j 
i+1 -- j: bcde
i -- j-1: abcd
bcde -> a bcde a
        (a)bcde
abcde

abcd 2
abba






Elizabeth 

Check out our engineering team: https://www.thumbtack.com/team/engineering

Elizabeth Swaney
eswaney@thumbtack.com


Ryan Sheehan | Technical Recruiter | Alexa Experience & Devices
E: ryanshee@amazon.com | P: 914.231.6070 | M: 845-649-7411
Work hard. Have fun. Make history.
Description: Macintosh HD:Users:alishaaz 1:Documents:Photos:Logos :Alexa Logos:Alexa_logo_horizontal:Horizontal_RGB_PNG:Amazon_Alexa_Horizontal_RGB_Dark-Color.png





Imagine you have a special keyboard with the following keys:

Key 1: (A): Prints one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:
Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A
Example 2:
Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:



// A recursive function that returns the optimal length string 
// for N keystrokes
int findoptimal(int N)
{
    // The optimal string length is N when N is smaller than 7
    if (N <= 6)
        return N;
 
    // Initialize result
    int max = 0;
 
    // TRY ALL POSSIBLE BREAK-POINTS
    // For any keystroke N, we need to loop from N-3 keystrokes
    // back to 1 keystroke to find a breakpoint 'b' after which we
    // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way.
    int b;
    for (b=N-3; b>=1; b--)
    {
            // If the breakpoint is s at b'th keystroke then
            // the optimal string would have length
            // (n-b-1)*screen[b-1];
            int curr = (N-b-1)*findoptimal(b); => (i-j-1)*dp[j]
            if (curr > max)
                max = curr;
     }
     return max;
}

public int maxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i - 3; j++)
                dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
        }
        return dp[n];
    }



observation : copy first and paste all the way










http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/


n = 5

public int recurse(int n,int[] dp) {
   
    if (n < 3)  
        return n;
    
    for(int i=2; i < n / 2; i++) {
        if (n % i == 0)
        return recurse(n/i) + n / i;
    }    
    
    dp[n] = ....
    
    
    
    
    
    for(int i=2; i < n; i++) {
        for (int j = i / 2; j > 1; j--) {
            if (i % j == 0) dp[i] = dp[j] + i / j;
        }
    }
}

  (1)   (3)
6 => 3 => 1  = 4





a[i][j] = 第i个人抄前j个书
b[k][l] ＝ L本书  交给 k 跟抄袭



f[k][i] = min{max{f[k-1][j], A[j] +…+A[i-1]}}

k ＝ k个人
最短多少时间抄袭前i本书