#300 Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

O(n^2)

based on longest common subsequence

转化为最长公共子序列问题。先将数组排序(升序)，然后寻找与原数组的最长公共子序列。该子序列即为最长递增子序列。

e.g.
[10, 9, 2, 5, 3, 7, 101, 18]
[2, 3, 5, 7, 9, 10, 18, 101]

• Reverse Words in a String
• Longest Common SubSequence

Reverse Words in a String

Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.

之前有遇到这个题目，现在看到别人家的simple solution之后，发现用暴力解题的我真是太low了。
利用正则表达式，直接调用String类自带的工具–split()方法。

split() – “将字符串从正则表达式匹配的地方切开。”
–《Thinking in Java》

在这题中，就可以使用该方法，将String字符串从根据空格切割成String数组，每个元素就是一个单词(貌似不用考虑标点？)。
最后倒序输出就可以了。

括号匹配

#20 Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

借用栈来实现。若是合法的括号，左右括号必然是对称的。遍历字符串，遇到左括号即压入栈内；遇到右括号则与栈顶元素匹配，若匹配则弹出，否则返回false。
需要注意到一些特殊情况，比如：”(“ “)”这样的。若到了最后，栈中仍有括号，说明不合法；在弹栈前要确认栈内不为空。

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

public boolean isValid(String s) {
       Stack<Character> stack = new Stack<Character>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (c == '(' || c == '[' || c == '{') {
               stack.push(c);
           }
           else {
               if (stack.isEmpty())
                   return false;
               char pre = stack.pop();
               if ((c == ')' && pre == '(') || (c == ']' && pre == '[') || (c == '}' || pre == '{'))
                   continue;
               else
                   return false;
           }
       }
       return stack.isEmpty();
   }

#51 N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
   "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
   "Q...",
  "...Q",
  ".Q.."]
]

感觉题目说的不清不楚的，至少我看完上面的题目描述，我不知道我应该做什么。
将n个皇后棋子布置在一个n*n的棋盘上，使两个皇后之间无法互相攻击，及每一行，每一列，每一斜线上都只有唯一一个棋子存在(注意有两条斜线)。
以行作为回溯单位

Group Anagrams

#49 Group Anagrams

Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:
[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note:
For the return value, each inner list’s elements must follow the lexicographic order.
All inputs will be in lower-case.

思路：先将各个单词排序，排序后的字符串相同的单词即是anagrams。
具体实现需要用到容器HashMap，以键值对的形式保存排序后字符串相同的所有单词。key就是排序后字符串，value就是原本的单词组成的list。
e.g. (“abc”, [“abc”, “acb”, “bac”])

• 遍历string数组，得到当前单词的顺序字符串，然后在HashMap中查找。
• 若HashMap中已存在该key，则将该单词插入到对应的list中。
• 若不存在，则新插入键值对。
  最后将Map中的list放入需要返回的表中。
  注意，因为题中要求list中的元素是有序的，所以要在最开始的时候将单词数组排序，以保证插入的顺序。
  阅读全文 »