Given a list of words and two words word1 and word2, 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.

解法1：

思路就是维护两个指针，一个记录上一次出现的word1的位置，另一个记录word2的位置。每次发现一个新位置的时候计算一下当前的距离并且更新最短距离。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int iter1 = -1, iter2 = -1;
        int res = words.size();
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word1) {
                iter1 = i;
                if (iter2 != -1) {
                    res = std::min(res, iter1 - iter2);
                }
            } else if (words[i] == word2) {
                iter2 = i;
                if (iter1 != -1) {
                    res = std::min(res, iter2 - iter1);
                }
            }
        }
        return res;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        if (words.length < 2) {
            return 0;
        }
        int first = -1, second = -1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                first = i;
                if (second != -1) {
                    res = Math.min(res, Math.abs(second - first));
                }
            } else if (words[i].equals(word2)) {
                second = i;
                if (first != -1) {
                    res = Math.min(res, Math.abs(second - first));
                }
            }
        }
        return res;
    }
}

家里有两台台式机，一台干脆专门用来下data，配置了一下MySQL,从另一台电脑上成功连接，把大概的步骤记录一下。

• 打开 3306 端口
  ….MySQL的默认端口是3306,需要配置firewall来开放端口，如果是Windows机可以参考这篇文章。

• 建立远程连接的用户
  …. 添加用户

  1 2	CREATE USER 'myuser'@'localhost' IDENTIFIED BY 'mypass'; CREATE USER 'myuser'@'%' IDENTIFIED BY 'mypass';

  ….设定用户的权限

  1 2	GRANT ALL ON *.* TO 'myuser'@'localhost'; GRANT ALL ON *.* TO 'myuser'@'%';

• 连接

  1	mysql -u USERNAME -h HOST_IP -p

• 基本操作

  1 2 3 4 5 6

  // Show all databases show database; // Switch to a table use DATABASE_NAMME; // Show all tables show tables;

Reference：
http://stackoverflow.com/questions/16287559/mysql-adding-user-for-remote-access
http://stackoverflow.com/questions/15872543/access-remote-database-from-command-line

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

解法1：Recursion with O(N) time

Divide and Conquer, 递归的思路，空Node的depth为0，任意一个Node的depth为左面和右面的最大的depth+1, i.e. maxDepth(i) = Max(maxDepth(left), maxDepth(right)) + 1
注意C++中空值是NULL, java是null
C++

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

Java

1
2
3
4
5
6
7
8
9

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

解法2: Non-recursion

我们只需要修改一个非递归的树的遍历算法就可以了，这篇文章详细讲了思路

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解法1：O(N) time with O(1) space, N is the number of elements

运用XOR是一个抵消运算符，A XOR A 出来是一个0，所以对所有的数字做XOR之后重复的都消掉了，只剩下单独的一个。C++中vector的method是vector.size(),和java中array的array.length注意区分。

C++

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            result ^= nums[i];
        }
        return result;
    }
};

Java

1
2
3
4
5
6
7
8
9

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result ^= nums[i];
        }
        return result;
    }
}

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

解法1：Iteration

XOR是一个不带进位的加法运算，进位的信息可以通过AND（与运算）再左移获得。可以有Recursion和Iteration两种写法
C++

1
2
3
4
5
6
7
8
9
10
11
12

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int c = a ^ b;
            int carry = (a & b) << 1;
            a = c;
            b = carry;
        }
        return a;
    }
}

解法2：Recursion

C++

1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    public int getSum(int a, int b) {
      if (b == 0) {
        return a; // stop condition
      }
      int c = a ^ b;
      int carry = (a & b) << 1;
      return getSum(c, carry);
    }
}

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = “++++”, after one move, it may become one of the following states:

[
“–++”,
“+–+”,
“++–”
]
If there is no valid move, return an empty list [].

解法1：DP with O(N) time, N = number of characters

按顺序一个个查看是否连续的两个字符是’+’， 如果是则换，如果不是继续
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        vector<string> result;
        if (s.length() == 0) {
            return result;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                string temp = s.substr(0); // or just string temp = s;
                temp[i] = '-';
                temp[i + 1] = '-';
                result.push_back(temp);
            }
        }
        return result;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                StringBuffer temp = new StringBuffer(s);
                temp.setCharAt(i, '-');
                temp.setCharAt(i + 1, '-');
                result.add(temp.toString());
            }
        }
        return result;
    }
}

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

For example,
“code” -> False, “aab” -> True, “carerac” -> True.

解法1：DP with O(N) time, N = number of characters

Palindrome分为even和odd两种情况，在even的时候，一定是每一个字母都出现偶数次。在odd的时候，有且仅有一个字母可出现奇数次。那么就可以统计每一个字母出现的次数，如果出现奇数次的字母的个数大于1，那么一定不能组成一个Palindrome，反之则可以。统计的时候需要一个HashMap来记录每一个字母的个数。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    bool canPermutePalindrome(string s) {
        map<char, int> hmap;
        for (int i = 0; i < s.length(); i++) {
            if (hmap.count(s[i]) == 0) {
                // not exist
                hmap.insert(std::pair<char, int>(s[i], 1));
            } else {
                hmap[s[i]]++;
            }
        }
        // Iterate over map keys
        map<char, int>::iterator iter = hmap.begin();
        map<char, int>::iterator iter_end = hmap.end();
        int odd = 0;
        while (iter != iter_end) {
            if (iter->second % 2 != 0) {
                odd++;
            }
            ++iter;
        }
        return odd < 2;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        int size = s.length();
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < size; i++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            } else {
                map.put(s.charAt(i), 1);
            }
        }
        // Check for odd number
        int odd = 0;
        for (Character ch : map.keySet()) {
            if (map.get(ch) % 2 != 0) {
                odd++;
            }
        }
        return odd < 2;
    }
}

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

解法1：DP with O(N) time, N is the number of input, Runtime Error

思路就是去试几个不同的数，找出规律。自然的首先想到的是DP的算法，比如输入4，那么无论如何不能达到。如果是5，那么只要1可以，那么5就可以。似乎只需要看前面差4个数的结果。x[i] = x[i - 4]，但是当数据变大的时候会出现Runtime error。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool canWinNim(int n) {
      if (n <= 0) {
          return false;
      }
      if (n <= 3) {
          return true;
      }
      bool x[n + 1];
      x[0] = false; x[1] = true; x[2] = true; x[3] = true;
      for (int i = 4; i <= n; i++) {
          x[i] = x[i - 4];
      }
      return x[n];
    }
}

解法2：O(1) Time with Math

1,2,3 可以，4 false， 5，6，7 true, 8 false. 得出的结论是能除4的就不能赢。
C++

1
2
3
4
5
6

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

解法1：O(1) Computation and O(N) space

需要考虑每次计算运用上次的结果，由于平均值是Sum / Size, 如果维护average的值的话不方便重复利用已经计算过的值，所以我们可以考虑维护一个当前的Sum. 最后需要计算average的时候就把sum除以当前的数字个数。

数据结构： 考虑使用queue, 用到的操作是queue.front(), queue.pop() 和queue.push(item)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//C++
  class MovingAverage {
  private:
      queue<int> data;
      int sum;
      int msize;
  public:
      MovingAverage(int size) {
          msize = size;
          sum = 0;
      }
      double next(int val) {
          if (data.size() == msize) {
              sum -= data.front();
              data.pop();
          }
          data.push(val);
          sum += val;
          return (double)sum / data.size();      
      }
  };

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]], return 10. (four 1’s at depth 2, one 2 at depth 1)

Example 2:
Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27)

解法1：Recursion with O(N) time, N is number of total elements

看到Nested，从构造上来说和递归的思路很一致。想到递归时每一次调用递归函数需要记录下当前的level。
整体的思路是对每一个element, 如果是Integer的话，当前的结果应该是数值 * level, 然后继续，如果是Nested List，那么level + 1, 然后继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return depthSumHelper(nestedList, 1);
    }
    int depthSumHelper(vector<NestedInteger>& nestedList, int depth) {
        int sum = 0;
        for (int i = 0; i < nestedList.size(); i++) {
            if (nestedList[i].isInteger()) {
                sum += nestedList[i].getInteger() * depth;
            } else {
                sum += depthSumHelper(nestedList[i].getList(), depth + 1);
            }
        }
        return sum;
    }
};