Thursday, December 31, 2015

324. Wiggle Sort II

Q:
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
A:

排序,然后分配即可 不行的。 第一个例子就通不过





Mistakes:





Wednesday, December 30, 2015

266. Palindrome Permutation ----------E

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true
A:

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> M;
        for(auto c : s)
            M[c]++;
        int oddCount = 0;
        for(auto iter = M.begin(); iter!= M.end(); iter++){
            if(iter->second %2)
                oddCount++;
        }
        return oddCount<=1;
    }
};

Mistakes:





265. Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
             Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. 

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

A:
DP
每次记录之前一行,最小的value和index,以及 secondMinimum value;

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n==0)
            return 0;
        int k = costs[0].size();
        int minVal = 0, minIndex=0;
        int min2Val = 0; // no need to record its index
        for(auto & cost : costs){
            int newMinVal = INT_MAX-1, newMinIndex=0;
            int newMin2Val = INT_MAX;
            for(int i =0;i<k;i++){
                cost[i] += (i != minIndex ? minVal : min2Val);
                if(cost[i] < newMin2Val){
                    newMin2Val = cost[i];
                }
                if(cost[i] < newMinVal){
                    newMin2Val = newMinVal;
                    newMinVal = cost[i];
                    newMinIndex = i;
                }
            }
            minVal = newMinVal;
            minIndex = newMinIndex;
            min2Val = newMin2Val;
        }
        return minVal;
    }
};

不用单独把 第0行单独计算(只需要把minValue = 0 即可)

Mistakes:






261. Graph Valid Tree ------------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 check whether these edges make up a valid tree.

Example 1:

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

Example 2:

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

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:
首先,# of edges = # of nodes - 1        (还是必要的,否则可能是个有环联通图)
然后: 检查是否从一个点可以发现其余所有的node

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if(edges.size() !=n-1)
            return false;
        unordered_map<int,vector<int>> M;
        for(auto &edge : edges){
            M[edge[0]].push_back(edge[1]);
            M[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(n,false);
        dfs(0, M, visited);// pick any node, and 
        for(auto v:visited)
            if(not v) // if some nodes are not visited
                return false;
        return true;
    }
private:
    void dfs(int seed, unordered_map<int,vector<int>> &M,vector<bool> &visited){
        if(visited[seed])// if already visted at this place
            return;
        visited[seed]=true;
        for(auto v : M[seed])
            dfs(v,M, visited);
    }
};
Mistakes:
1: 要把双向的edges都放到Map里面




Tuesday, December 29, 2015

256. Paint House ---------E

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.
A:
DP

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n==0)
            return 0;
        for(int i =1;i<n;i++){
            costs[i][0] += min( costs[i-1][1], costs[i-1][2]);
            costs[i][1] += min( costs[i-1][0], costs[i-1][2]);
            costs[i][2] += min( costs[i-1][0], costs[i-1][1]);
        }
        return min(costs[n-1][0], min(costs[n-1][1], costs[n-1][2] ));
    }
};


255. Verify Preorder Sequence in Binary Search Tree ----------M !!!!!~~~~~~

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up:
Could you do it using only constant space complexity?

A:

每次找到小于的, 然后分开查询

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        return helper(preorder, 0, preorder.size()-1);
    }
private:
    bool helper(vector<int>& preorder, int start, int end){
        if(start >= end) // just one value
            return true;
        int val = preorder[start];
        int mid = start+1; // mid point to first position either go-beyond, or with bigger value 
        while(mid<=end && preorder[mid] < val){
            mid++;
        }
        for(int i = mid; i<=end;i++){
            if(preorder[i] < val )
                return false;
        }
        return helper(preorder, start+1,mid-1) && helper(preorder, mid, end);
    }
};
上面这个方法,说都通过了,可是有点儿慢。   修改下,加上范围. 这样,可以省掉上面的for循环
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        return helper(preorder, 0, preorder.size()-1, INT_MIN, INT_MAX);
    }
private:
    bool helper(vector<int>& preorder, int start, int end, int lower, int upper){
        if(start > end) // just one value
            return true;
        int val = preorder[start];
        if(val <=lower || val >= upper)
            return false;
        if(start == end)
            return true;
        int mid = start+1; // mid point to first position either go-beyond, or with bigger value 
        while(mid<=end && preorder[mid] < val){
            if(preorder[mid]<=lower)
                return false;
            mid++;
        }
        return helper(preorder, start+1,mid-1, lower, val) && helper(preorder, mid, end, val, upper);
    }
};
这次通过了, 可是,只是faster than 5.65% 
观察得知,我们还是有了个while 循环,考虑去掉。  用stack 来表示。

This problem is very interesting. Recursive approach is very straightforward, though solution is likely of O(nlogn)/O(logn) time/space complexity (avg), or O(N^2)/O(N) worst case.


The key to optimize is to recall how iterative(non-recursive)

pre-order traversal works, then follow the same idea to "reconstruct" BST from preorder sequence, during which we need a stack to keep track of node path from root. The trick here is to use input preorder sequence to simulate the stack in-place. For verification purpose, we need to maintain a "lower bound" variable: when we visit a node that is the right child of its parent, the parent's value must be lower bound of all subsequent values.

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> st;
        int lower_bound = INT_MIN;
        for(int i = 0;i< preorder.size();i++){
            int v = preorder[i];
            if(v <= lower_bound) // check that it's in the range
                return false;
            
            if(st.empty() || v < st.top()){
                st.push(v);
            }else{
                lower_bound = st.top();
                st.pop();
                i--;     // this is the KEY, step back so we can check with grandparent 
            }
        }
        return true;
    }
};


Mistakes:




254. Factor Combinations --------M ~!!!~~


Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

  A:
递归。 ---不是很必须用memorization, 因为每次的startFactor/minFactor不同。

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        auto res = helper(2, n);
        if (not res.empty())
            res.pop_back(); // pop out {n},  
        return res;
    }
private:
    vector<vector<int>> helper(int startFactor, int n) {
        vector<vector<int>> res;
        for (int i = startFactor; i <= n; i++) {
            if (n % i == 0) {
                if (i == n) {
                    res.push_back(vector<int>{n}); // this would need to be deleted
                }
                else {
                    auto lessAll = helper(i, n / i);
                    for (auto& line : lessAll) {
                        line.insert(line.begin(), i);
                        res.push_back(line);
                    }
                }
            }
        }
        return res;
    }
};


Mistakes:
1: 为了代码缩减,因此直接在helper()中的for  loop中 i <= n
   因此,需要删掉最后一个 32   的<32)>. 因此需要在主函数中删掉最后一个。





253. Meeting Rooms II ----------M !!!!!!!~~~~~~~~!!!!!!!!

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

A:

 核心点,就是先排序(先start,再end),再每次找一个room,尽量多的排meeting

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            if(a[0]==b[0])
                return a[1]<b[1];
            return a[0] < b[0];
        });
        // each round, add a table, then arrange the max possible conference on it
        int res = 0;        
        while(not intervals.empty()){
            vector<int> pre = intervals[0];
            res++;
            vector<vector<int>> nextRound;
            for(int i =1;i<intervals.size();i++){
                auto cur = intervals[i];
                if(cur[0] >= pre[1]){
                    pre = cur;
                }else{
                    nextRound.push_back(cur);
                }
            }
            intervals = nextRound;
        }
        return res;
    }
};

Mistakes:
竟然直接pass了, ╮(╯▽╰)╭





252. Meeting Rooms -------E

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Example 1:

Input: [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: [[7,10],[2,4]]
Output: true

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

A :
Use Lambda function  to sort the vector
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            if(a[0]==b[0])
                return a[1]<b[1];
            return a[0] < b[0];
        });
        for(int i =1; i < intervals.size(); i++){
            if(intervals[i][0] < intervals[i-1][1])
                return false;
        }
        return true;
    }
};



Use min_heap to extract next earliest start time.
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return true;
        priority_queue<vector<int>, vector<vector<int>>, comparator> minHeap;
        for(auto & tmp : intervals){
            minHeap.push(tmp);
        }
        auto pre = minHeap.top();
        minHeap.pop();
        while(not minHeap.empty()){
            auto cur = minHeap.top();
            minHeap.pop();
            if(pre[1] > cur[0])
                return false;
            pre = cur;
        }
        return true;
    }
private:
    struct comparator{
        bool operator()(vector<int> a, vector<int> b){
            if(a[0]==b[0]){
                return a[1] > b[1];
            }else{
                return a[0] > b[0];
            }
        }
        
    };
};



NOTE:
Lambda 和 comparator的 比较方式是相反的。  !~~~~~~~~~~




L 251. Flatten 2D Vector ----------M

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext.

 

Example:

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // return 1
iterator.next(); // return 2
iterator.next(); // return 3
iterator.hasNext(); // return true
iterator.hasNext(); // return true
iterator.next(); // return 4
iterator.hasNext(); // return false

 

Notes:

  1. Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases. Please see here for more details.
  2. You may assume that next() call will always be valid, that is, there will be at least a next element in the 2d vector when next() is called.

 

Follow up:

As an added challenge, try to code it using only iterators in C++ or iterators in Java.


    A:
    关键点是:可能包含是empty list    

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& v) {
            val = v;
            m = v.size();
            n = 0;
            if(m != 0)
                n = v[0].size();
            i = 0;
            j = 0;
        }
        
        int next() {
            int res =  val[i][j];
            ++j; // simply update, since hasNext would be called
            return res;
        }
        
        bool hasNext() {        
            while(i<m && j==n){
                i++;
                if(i==m){
                    return false;
                }
                j = 0;
                n = val[i].size();;
            }
            return true;
        }
    private:
        vector<vector<int>> val;
        int i,j;
        int m,n;
    };
    
    /**
     * Your Vector2D object will be instantiated and called as such:
     * Vector2D* obj = new Vector2D(v);
     * int param_1 = obj->next();
     * bool param_2 = obj->hasNext();
     */


    Mistakes:
    1:     允许  有空的list存在。
    above code works on windows, and ubuntu, but failed on Leetcode. Seems not my fault


    250. Count Univalue Subtrees ---M

    Given the root of a binary tree, return the number of uni-value subtrees.

    A uni-value subtree means all nodes of the subtree have the same value.

     

    Example 1:

    Input: root = [5,1,5,5,5,null,5]
    Output: 4
    

    Example 2:

    Input: root = []
    Output: 0
    

    Example 3:

    Input: root = [5,5,5,5,5,null,5]
    Output: 6
    

     

    Constraints:

    • The numbrt of the node in the tree will be in the range [0, 1000].
    • -1000 <= Node.val <= 1000
    A:
    递归

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        int countUnivalSubtrees(TreeNode* root) {
            int res = 0;
            helper(root, res);
            return res;
        }
    private:
        bool helper(TreeNode* root, int & res){ // return whether root is univalue
            if(not root)
                return true;
            bool isLeft = helper(root->left, res);
            bool isRight = helper(root->right, res);
            if(isLeft && isRight && ( !root->left || root->val == root->left->val )
              && ( !root->right || root->val == root->right->val )){
                res++;
                return true;
            }
            return false;
        }
    };



    Mistakes:






    249. Group Shifted Strings --------M

    Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
    "abc" -> "bcd" -> ... -> "xyz"
    Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
    For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
    Return:
    [
      ["abc","bcd","xyz"],
      ["az","ba"],
      ["acef"],
      ["a","z"]
    ]
    Note: For the return value, each inner list's elements must follow the lexicographic order.

    A:

    class Solution {
    public:
        vector<vector<string>> groupStrings(vector<string>& strings) {
            unordered_map<string, vector<string>> M;
            for(auto &s:strings){ // represent each string with their char difference
                string tmp="";
                for(int i =1;i<s.length();i++){
                    tmp+= to_string( (26 + s[i]-s[i-1]) %26);
                }
                M[tmp].push_back(s);
            }
            vector<vector<string>> res;
            auto iter = M.begin();
            while(iter!= M.end()){
                res.push_back(iter->second);
                iter++;
            }
            return res;
        }
    };

    1:  一个整数 -1 % 26,  的结果为 -1  , 因此计算新的char的时候, 得加上26

    一开始犯了糊涂,  az,  za 的difference 的结果是不一样的。

    247. Strobogrammatic Number II --------M

    A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

    Find all strobogrammatic numbers that are of length = n.

    Example:

    Input:  n = 2
    Output: ["11","69","88","96"]
    
    A:
    递归
    一开始是允许0开始的,最后再删掉。
    class Solution {
    public:
        vector<string> findStrobogrammatic(int n) {
            vector<string> res;
            if(n<=0){
                return res;
            }
            for(auto s: helper(n)){
                if(s.length()== 1 || s[0] !='0'){// remove number starting with 0
                    res.push_back(s);
                }
            }
            return res;
        }
    private:
        vector<string> helper(int n ){        
            if(n==1){
                return vector<string>{"0","1","8"};
            }
            if(n==2){
                return vector<string>{"11","69","88","96","00"};
            }else{
                vector<string> res;
                for(auto ss : helper(n-2)){
                    res.push_back("0"+ss+"0");
                    res.push_back("1"+ss+"1");
                    res.push_back("8"+ss+"8");
                    res.push_back("6"+ss+"9");
                    res.push_back("9"+ss+"6");
                }
                return res;
            }
        }
    };


    但会造成多用了时间, 因此,多加了个N参数,来标记是否是最外层。
    可是结果反而慢了,好奇怪



    Mistakes:

    1: 记得不能以0 开头,但是忘记了, n ==1 的时候, "0"也是可以的。




    Monday, December 28, 2015

    246. Strobogrammatic Number ---------E

    A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

    Write a function to determine if a number is strobogrammatic. The number is represented as a string.

     

    Example 1:

    Input: num = "69"
    Output: true
    

    Example 2:

    Input: num = "88"
    Output: true
    

    Example 3:

    Input: num = "962"
    Output: false
    

    Example 4:

    Input: num = "1"
    Output: true
    
    A:

    **************  用 Hashing ***************
    class Solution {
    public:
        bool isStrobogrammatic(string num) {
            unordered_map<char,char> M={{'1','1'}, {'0','0'}, {'8','8'},{'6','9'},{'9','6'}};
            string res="";
            for(char ch:num){
                if(M.find(ch) == M.end())
                    return false;
                res= M[ch]+res;
            }
            return res == num;
        }
    };

    *************  忘记先检查  char  是否在map中 ***********



    245. Shortest Word Distance III ----M

    Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

    word1 and word2 may be the same and they represent two individual words in the list.

    Example:
    Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

    Input: word1 = “makes”, word2 = “coding”
    Output: 1
    
    Input: word1 = "makes", word2 = "makes"
    Output: 3
    

    Note:
    You may assume word1 and word2 are both in the list.

    A:

    ************  第二遍**************************
    与II的唯一区别,就是增加了  if (a==b) continue  这一句

    class Solution {
    public:
        int shortestWordDistance(vector<string>& words, string word1, string word2) {
            vector<int> V1;
            vector<int> V2;
            for(int i = 0;i<words.size();i++){
                if(words[i] == word1){
                    V1.push_back(i);
                }
                if(words[i] == word2){
                    V2.push_back(i);
                }
            }
            int res = INT_MAX;
            for(int i1=0, i2=0;i1<V1.size();i1++){
                int a = V1[i1];
                int b = V2[i2];
                if(a==b)
                    continue;
                res = min(res, abs(a-b));
                if(a>b){
                    // increase b
                    if(i2+1<V2.size()){
                        i2++;
                        i1--;
                    }
                }
            }
            return res;
        }
    };


    *************笨办法, 从低到高,计算每一个可能的步长并对比**********
    public class Solution {
        public int shortestWordDistance(String[] words, String word1, String word2) {
            for(int step = 1; step<words.length;step++){
                for(int i =0;i + step < words.length; i++){
                    boolean bln1=words[i].equals(word1) && words[i+step].equals(word2);
                    boolean bln2=words[i].equals(word2) && words[i+step].equals(word1);
                    if(bln1 || bln2)
                        return step;
                }
            }
            return -1;
        }
    }
    


    *******  更快速 ***********但只是一遍的****************
    每次跟随检验, 利用的特性是:  每次往前一个新的string,我们只记录最近发现的word1 ,和 word2.

    public class Solution {
        public int shortestWordDistance(String[] words, String word1, String word2) {
            int i1= -1, i2 = -1, res = Integer.MAX_VALUE;
            boolean isSame = word1.equals(word2);
            for(int i =0;i<words.length; i++){
                String str = words[i];
                if(str.equals(word1)){
                    if(i2 >= 0)
                        res = Math.min(res, i-i2);
                    i1 = i;
                }
                if(str.equals(word2)){
                    if(i1 >= 0 && ! isSame )
                        res = Math.min(res, i-i1);
                    i2 = i;
                }
            }
            return res;
        }
    }
    




    244. Shortest Word Distance II ---------M

    Q:
    This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be calledrepeatedly many times with different parameters. How would you optimize it?
    Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
    For example,
    Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
    Given word1 = “coding”word2 = “practice”, return 3.
    Given word1 = "makes"word2 = "coding", return 1.
    Note:
    You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.


    A:
    就是保持2个list,然后对比
    这里唯一需要注意的是:每次根据 index的值,来update 前进哪个index

    class WordDistance {
    public:
        WordDistance(vector<string>& words) {
            for(int i =0;i<words.size();i++){
                M[words[i]].push_back(i);
            }
        }
        
        int shortest(string word1, string word2) {
            vector<int> &V1 = M[word1];
            vector<int> &V2 = M[word2];
            int res = INT_MAX;
            for(int i1 = 0, i2=0;i1<V1.size();i1++){
                int a = V1[i1];
                int b = V2[i2];
                res = min(res, abs(a-b));
                if(a>b){
                    if(i2+1<V2.size()){
                        i2++;
                        i1--;
                    }
                }
            }
            return res;
        }
    private:
        unordered_map<string, vector<int>> M;
    };
    
    /**
     * Your WordDistance object will be instantiated and called as such:
     * WordDistance* obj = new WordDistance(words);
     * int param_1 = obj->shortest(word1,word2);
     */

    Mistakes:



    243. Shortest Word Distance ----E

    Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

    Example:
    Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

    Input: word1 = “coding”, word2 = “practice”
    Output: 3
    
    Input: word1 = "makes", word2 = "coding"
    Output: 1
    

    Note:
    You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

    A:
    把位置记录到2个list里,然后逐个对比即可

    class Solution {
    public:
        int shortestDistance(vector<string>& words, string word1, string word2) {
            vector<int> V1;
            vector<int> V2;
            for(int i =0;i<words.size();i++){
                string ss = words[i];
                if(ss==word1){
                    V1.push_back(i);
                }else if(ss==word2){
                    V2.push_back(i);
                }
            }
            int res = INT_MAX;
            int i2 = 0;
            for(int i1 = 0;i1<V1.size();i1++){
                int a = V1[i1];
                int b = V2[i2];
                res = min(res, abs(a-b));
                if(a>b){
                    if(i2+1<V2.size()){
                        i2++;
                        i1--;
                    }
                }
            }
            return res;
        }
    };


    就是挨个数,根据距离从小到大
    ************但是这样,两层循环, 太慢,***********

    public class Solution {
        public int shortestDistance(String[] words, String word1, String word2) {
            int i1=-1,i2=-1;
            for(int len = 1;len<words.length;len++){
                for(int i =0;i+len<words.length;i++){
                    boolean bln1 = words[i].equals(word1) && words[i+len].equals(word2);
                    boolean bln2 = words[i].equals(word2) && words[i+len].equals(word1);
                    if(bln1 || bln2)
                        return len;
                }
            }
            return -1;
        }
    }
    





    Mistakes:
    1: 没有注意shortest