241. Different Ways to Add Parentheses -------M！！！！

Q:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

A:          分而治之， 从每个+-* 拆开

class Solution {
public:
    vector<int> diffWaysToCompute(string input) { // assume no space
        bool foundOp = false;
        vector<int> res;
        for(int i =0;i<input.size();i++){
            if(!isdigit(input[i])){
                foundOp=true;
                auto L=diffWaysToCompute(input.substr(0,i));
                auto R=diffWaysToCompute(input.substr(i+1));
                for(auto s1 : L)
                    for(auto s2 : R)
                        res.push_back(cal(s1, s2, input[i]));
            }
        }
        if(not foundOp)
            res.push_back(stoi(input));
        return res;        
    }
private:
    int cal(int a, int b, char op){
        if(op=='+')
            return a+b;
        if(op=='-')
            return a-b;
        if(op=='*')
            return a*b;
        return 0; // wrong . should never hit
    }
};

Mistakes:

一开始，先split成一个个vector<string> 其实是没有必要的。 以后注意

几道面试题

1.（数组、规划）有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:  
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];


2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。

56.最长公共字串（算法、字符串）。

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，

则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，

2.n个骰子的点数。把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
打印出S的所有可能的值出现的概率。

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

Google 面试题：
一堆扑克牌，可以看到所有的牌，每次拿一张，手里有3张， 如何计算，最多需要多少才能凑够21点？
要求  O(n)的复杂度

170. Two Sum III - Data structure design ----E

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.

Example 1:

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

Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

A:
用HashMap, save with count

class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        M[number]++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        auto iter = M.begin();
        while(iter!=M.end()){
            int key = iter->first;
            int count = iter->second;
            if(key == value - key){
                if(count>1)
                    return true;
            }else{
                if(M.find(value - key) != M.end()){
                    return true;
                }
            }
            iter++;
        }
        return false;
    }
private:
    unordered_map<int,int> M; // value and its count
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

Mistakes:

1： 开始根本没有考虑重复的情况。
   上来就用了Set
 哎，就是自己SB， 没办法， 水平不够，  Tiger
是根本的人的问题，   再刷1000遍也没办法的，Tiger

艹

Two Sum II - Input array is sorted -E

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

A:
就是简单的two Pointer 方法

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size()-1;
        vector<int> res;
        while(left<right)
        {
            if(numbers[left]+numbers[right] == target){
                res.push_back(left+1);
                res.push_back(right+1);
                break;
            }else if(numbers[left]+numbers[right] < target){
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
};

332. Reconstruct Itinerary

Q:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets may form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

A:
***************Sol 1 ******graph--> topological sort ***************


****************Sol 2 **************Hash ***************
下面这个结果不对，你看看是哪里错了？

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> res = new LinkedList();
        Map<String, List<String> > map = new HashMap();
        for(int i =0;i<tickets.length; i++){
            String start = tickets[i][0];
            String end = tickets[i][1];
            if(map.containsKey(start)){
                List<String> list = map.get(start);
                int n = list.size();
                for(int j =0; j<= n;j++) // insert sort
                    if(j==n || list.get(j).compareTo(end)>0)
                        list.add(j,end);
            }else{
                List<String> list = new LinkedList();
                list.add(end);
                map.put(start,list);
            }
        }
        String start = "JFK";
        res.add(start);
        while( !map.isEmpty() ){
            List<String> list = map.get(start);
            String end = null;
            if(list.size() > 1){
                for(int i =0;i<list.size();i++){
                    if(isLoop(map,list.get(i),list.get(i) )){
                        end = list.remove(i);
                        break;
                    }
                }
            }else{
                end = list.get(0);
                map.remove(start);
            }
            res.add(end);
            start = end;
        }
        return res;
    }
    private boolean isLoop(Map<String,List<String>> map, String originalStart, String curStart ){
        if(map.get(curStart)==null)
            return false;
        for(String tmp : map.get(curStart)){
            if(tmp.equals(originalStart))
                return true;
            if( isLoop(map,originalStart, tmp) )
                return true;
        }
        return false;
    }
}

**************不能基于现在的状态去选择最好的，只能是dfs试错了***********最终代码如下***********




Mistakes:
1: 这里有一个情况没有考虑到：就是

         如果 路程有环的话，需要先找  可以转回来的，最低string **********

2：  但上面的也不对：
J --> AS
A-->JS
S-->A上面的这个就不能简单的用loop回来做选择。（因为 A-->S --A 是闭环的。但是J-->S就无法跑了。

Given an array of pairs, find all symmetric pairs in it

Two pairs (a, b) and (c, d) are said to be symmetric if c is equal to b and a is equal to d. For example (10, 20) and (20, 10) are symmetric. Given an array of pairs find all symmetric pairs in it.

It may be assumed that first elements of all pairs are distinct.

Example:

Input: arr[] = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}}
Output: Following pairs have symmetric pairs
        (30, 40)
        (5, 10)  

A Simple Solution is to go through every pair, and check every other pair for symmetric. This solution requires O(n2) time.

A Better Solution is to use sorting. Sort all pairs by first element. For every pair, do binary search for second element in the given array, i.e., check if second element of this pair exists as first element in array. If found, then compare first element of pair with second element. Time Complexity of this solution is O(nLogn).

An Efficient Solution is to use Hashing. First element of pair is used as key and second element is used as value. The idea is traverse all pairs one by one. For every pair, check if its second element is in hash table. If yes, then compare the first element with value of matched entry of hash table. If the value and the first element match, then we found symmetric pairs. Else, insert first element as key and second element as value.

Find four elements a, b, c and d in an array such that a+b = c+d

Q：

Given an array of distinct integers, find if there are two pairs (a, b) and (c, d) such that a+b = c+d, and a, b, c and d are distinct elements. If there are multiple answers, then print any of them.

Example:

Input:   {3, 4, 7, 1, 2, 9, 8}
Output:  (3, 8) and (4, 7)
Explanation: 3+8 = 4+7

Input:   {3, 4, 7, 1, 12, 9};
Output:  (4, 12) and (7, 9)
Explanation: 4+12 = 7+9

Input:  {65, 30, 7, 90, 1, 9, 8};
Output:  No pairs found

Expected Time Complexity: O(n2)

A:

1：  sort--> two pointer 

2: hashing each possible sum

Check if an array can be divided into pairs whose sum is divisible by k

Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.

Examples:

Input: arr[] = {9, 7, 5, 3}, k = 6
Output: True
We can divide array into (9, 3) and (7, 5).
Sum of both of these pairs is a multiple of 6.

Input: arr[] = {92, 75, 65, 48, 45, 35}, k = 10
Output: True
We can divide array into (92, 48), (75, 65) and 
(45, 35). Sum of all these pairs is a multiple of 10.

Input: arr[] = {91, 74, 66, 48}, k = 10
Output: False

A:

Use Hashing to 0 to k-1. and # of i == # k-1-i.  并且 if k %2 = 0, # k/2 can also be divided by 2

317. Shortest Distance from All Buildings

Q:

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

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

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

A:



Mistakes:

307. Range Sum Query - Mutable ----------M

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

 

Constraints:

• The array is only modifiable by the update function.
• You may assume the number of calls to update and sumRange function is distributed evenly.
• 0 <= i <= j <= nums.length - 1

A:

class NumArray {
public:
    NumArray(vector<int>& nums) {
        V = nums;
        for(int i =1;i<V.size();i++)
            V[i] += V[i-1];
    }
    
    void update(int i, int val) {
        int diff = val -  (V[i] - (i==0? 0 : V[i-1]));
        for(;i<V.size(); i++){
            V[i] += diff;
        }
    }
    
    int sumRange(int i, int j) {
        return V[j] - (i==0? 0:V[i-1]);
    }
private:
    vector<int> V;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

Mistakes：

L 323. Number of Connected Components in an Undirected Graph ---M

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

A:

典型的图遍历，  dfs

public class Solution {
    public int countComponents(int n, int[][] edges) {
        int res = 0;
        boolean A[] = new boolean[n];
        Map<Integer, List<Integer>> map  = new HashMap();
        for(int i =0;i<n;i++)
            map.put(i,new LinkedList());
        for(int i =0;i<edges.length;i++){
            map.get(edges[i][0]).add(edges[i][1]);
            map.get(edges[i][1]).add(edges[i][0]);
        }
        for(int i =0;i<n;i++){
            if(A[i] == false){
                A[i] = true;
                res++;
                dfs(i,map, A);
            }
        }
        return res;
    }
    private void dfs(int root, Map<Integer, List<Integer>> map, boolean[] A){
        List<Integer> list = map.get(root);
        for(Integer cur : list){
            if(A[cur]==false){
                A[cur] = true;
                dfs(cur, map,A);
            }
        }
    }
}
 

Mistakes:

325. Maximum Size Subarray Sum Equals k ----M ~~~~·

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4 
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2 
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Follow Up:
Can you do it in O(n) time?

A:

先求accumulate sum,并放到HashMap里，记住，相同的sum，只存最前面的那个。
然后 查看 已有的值里面，是否含有 total - k  。  (Note: total == 0 一开始就放进去)

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> M; // only save the first appearance
        M[0] = -1;
        int total = 0;
        int maxLen = 0;
        for(int i =0; i<n; i++){
            total += nums[i];
            if(M.find(total - k) != M.end()){
                maxLen = max(maxLen, i- M[total-k]);
            }
            if(M.find(total) == M.end()){
                M[total] = i;
            }
        }
        return maxLen;
    }
};

*****************上面是O(n^2).  如果要O(n)。 少了一个量级************这时候，就需要考虑Hashing *********（如果减少的是Log（n）级别，就可以考虑binary search, tree 等************


Mistakes:
1: 

295. Find Median from Data Stream --- H

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

 

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

 

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

A:
 就是左边一个max heap，  右边一个 min Heap。
这里，要学的是，如何用 Collections.reverseOrder();

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {        
    }
    
    void addNum(int num) {
        // blindly added into the left
        leftMaxHeap.push(num);
        if(leftMaxHeap.size() > 1+ rightMinHeap.size() ){
            int tmp = leftMaxHeap.top();
            leftMaxHeap.pop();
            rightMinHeap.push(tmp);
        }
        if(not rightMinHeap.empty() && leftMaxHeap.top() > rightMinHeap.top() ){
            int bigger = leftMaxHeap.top();
            leftMaxHeap.pop();
            
            int smaller = rightMinHeap.top();
            rightMinHeap.pop();
            
            rightMinHeap.push(bigger);
            leftMaxHeap.push(smaller);
        }
    }
    
    double findMedian() {
        if(leftMaxHeap.size() > rightMinHeap.size()){
            return leftMaxHeap.top();
        }else{
            return (leftMaxHeap.top()  + rightMinHeap.top() )/2.0;            
        }
    }
private:
    priority_queue<int, vector<int>> leftMaxHeap;
    priority_queue<int, vector<int>,greater<int>> rightMinHeap;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

Mistakes:

Amzaon面试中遇到了。

结果我没有检查

        if(not rightMinHeap.empty() && leftMaxHeap.top() > rightMinHeap.top() ){