Longest Increasing Subsequence
先从 O(n^2) 的 DP 做法说起。先从这个开做，是因为 O(n^2) 做法的普适性高，而且可以无视维度，易于扩展到各种变形与 follow-up 上。
需要返回具体 LIS sequence 的时候，加一个新 array，记录 parent index 一路追踪就可以了~ 和 Largest Divisible Subset 一样。
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
int max=0;
for(int i=0;i<len;i++){
dp[i] = 1;
for(int j=i-1;j>=0;j--){
if(nums[j]<nums[i] && dp[i]<dp[j]+1)
dp[i] = dp[j]+1;
}
max = Math.max(max, dp[i]);
}
return max;
}
这个问题的 follow up 也很有意思，返回一条最长的 subsequence，还有返回所有的 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?
A O(n^2) solution is, do Longest Common Subsequence between original array and sorted one, the LCS would be the LIS.
This is also "Online Algorithm" which we keep taking streams of input data one at a time.
For improvement, the key is take advantage of the "Increasing Sequence"
Terminating condition for "Search insert position" is important and needs to be accurate.
Arrays.binarySearch() This method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1).
public int lengthOfLIS(int[] nums) {
int[] dp = new int [nums.length];
int len = 0;
for(int num : nums){
int i = Arrays.binarySearch(dp, 0, len, num); //key point : search range[0,len]; search array: dp
if(i<0)
i = -(i+1);
dp[i] = num;
if(i==len) len++;
}
return len;
}
Find Permutation
先上一个错误思路，根据升降序原则得出［0，－1，－2，－1，0，－1，0］这个表格。再根据表格填数，得到［5，2，1，3，6，4，7］这里犯了一个错误是－1不一定需要比0小，非相邻元素不要包含此规定。正解为［3，2，1，4，6，5］
public class Solution {
public int[] findPermutation(String s) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
char[] arr = s.toCharArray();
int[] ans = new int[arr.length+1];
int pre = 0; int min = 0; int max = 0;
for(char c : arr){
map.put(pre, map.getOrDefault(pre,0)+1);
if(c=='D') pre--;
else pre++;
min = Math.min(min, pre);
max = Math.max(max, pre);
}
map.put(pre, map.getOrDefault(pre,0)+1);
int[] start = new int[max-min+1];
int idx = 0; int count = 1;
for(int i=min;i<=max;i++){
if(map.containsKey(i)){
start[idx] = count;
count+=map.get(i);
}
idx++;
}
idx = 0;
ans[0] = start[idx-min]; start[idx-min]++;
for(int i=1;i<ans.length;i++){
char c = s.charAt(i-1);
if(c=='D') idx--;
else idx++;
System.out.println(idx);
System.out.println(min);
ans[i] = start[idx-min];
start[idx-min]++;
}
return ans;
}
}
看了论坛上的答案后，理解了本题本质上就是wigle sort，只不过将连续的‘I’和‘D’看成一个整体。
正确 的打开方式是建立一个升序数组，对连续的‘D’部分reverse。
public class Solution {
public int[] findPermutation(String s) {
int[] ans = new int[s.length()+1];
for(int i=0;i<ans.length;i++) ans[i] = i+1;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='D'){
int low = i;
while(i<s.length() && s.charAt(i)=='D') i++;
int high = i;
i--;
reverse(ans, low, high);
}
}
return ans;
}
public void reverse(int[] ans, int low, int high){
while(low<high){
int tmp = ans[low];
ans[low] = ans [high];
ans[high] = tmp;
low++;high--;
}
}
}
Next Greater Element I
public class Solution {
public int[] nextGreaterElement(int[] findNums, int[] nums) {
if(findNums==null || findNums.length==0) return new int[0];
Stack<Integer> stack = new Stack<Integer>(); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int n=nums.length;
int[] ans = new int[n]; Arrays.fill(ans, Integer.MIN_VALUE);
for(int i=n-1;i>=0;i--){
map.put(nums[i], i);
if(i==n-1) {ans[i]=-1;stack.push(nums[i]);}
else{
while(!stack.isEmpty()&&stack.peek()<=nums[i]) stack.pop();
if(stack.isEmpty()) ans[i] = -1;
else ans[i] = stack.peek();
stack.push(nums[i]);
}
}
//System.out.println(Arrays.toString(ans));
int[] rtn = new int[findNums.length];
for(int i=0;i<rtn.length;i++){
rtn[i] = ans[map.get(findNums[i])];
}
return rtn;
}
}
Next Greater Element II
要求是circular的，先将数组元素逆序压入栈，保证0号元素在栈顶。然后从后往前遍历，返回最大值。
本质就是将extend部分的数组压入栈中。然后处理。
这道题于Count of Smaller Numbers After Self的区别在于count这道题要统计个数，难度要大一些。
public class Solution {
public int[] nextGreaterElements(int[] nums) {
if(nums==null||nums.length==0) return new int[0];
int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, Integer.MIN_VALUE);
Stack<Integer> stack = new Stack<Integer>();
for(int i=n-1;i>=0;i--){
stack.push(nums[i]);
}
for(int i=n-1;i>=0;i--){
while(!stack.isEmpty() && stack.peek()<=nums[i]) stack.pop();
if(stack.isEmpty()) ans[i] = -1;
else ans[i] = stack.peek();
stack.push(nums[i]);
}
return ans;
}
}
Count of Smaller Numbers After Self
非常好的一道题，用BST直接构造。每个node count存duplicate，leftCount存遇到过的数字。
1(0, 1)
\
6(3, 1)
/
2(0, 2)
\
3(0, 1)
class TreeNode{
int val;
int count = 0;
int leftCount = 0;
int rightCount = 0;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
count=1;
}
}
public class Solution {
public int insertNode(TreeNode root, int val){
int rtn = 0;
while(root!=null){
if(root.val>val){
root.leftCount++;
if(root.left==null){
TreeNode node = new TreeNode(val);
root.left = node;
return rtn;
}
root = root.left;
}
else if (root.val==val){
root.count++;
rtn += root.leftCount;
return rtn;
}
else{
rtn += root.count + root.leftCount;
if(root.right==null){
TreeNode node = new TreeNode(val);
root.right = node;
return rtn;
}
root = root.right;
}
}
return rtn;
}
public List<Integer> countSmaller(int[] nums) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(nums.length<1) return result;
TreeNode root = new TreeNode(nums[nums.length-1]);
result.add(0);
for(int i=nums.length-2;i>=0;i--){
int rtn = insertNode(root, nums[i]);
result.add(0, rtn);
}
return result;
}
Next Greater Element III
next permutation