Coding Part
1. Find the longest continuous sequence
use a stack to hold the current character and a variable to hold the largest number of appearance up till now. Compare and empty the stack if the current length is larger. Push into the stack if the current length is equal to the maxLen
/*
韩国小哥面的，和地里面经一样就是那个找连续最长字符
input1: thiisiisgoodd
output1: i i o d.1point3acres
input2: thiiisiisgoodd
output2: i
input3: this
output3: t h i s
顺序输出出现连续次数最多的每个字符。
*/
import java.util.Stack;
public class Solution {
public static void main(String[] args){
String test = "this";
String res = findtheLongest(test);
System.out.println(res);
}
public static String findtheLongest(String s){
if(s == null || s.length() == 0)return "";
char[] arr = s.toCharArray();
int i = 0;
int n = arr.length;
int maxLen = Integer.MIN_VALUE;
Stack<Character> stack = new Stack<Character>();
while(i < n)
{
char cur = arr[i];
int r = i + 1;
while(r < n && arr[r] == cur){
r++;
}
int len = r - i;
if(maxLen < len){
empty(stack);
maxLen = len;
stack.push(cur);
}
else if(maxLen == len){
stack.push(cur);
}
//update
i = r;
}
StringBuilder bd = new StringBuilder();
for(Character c : stack){
bd.append(c);
}
return bd.toString();
}
public static void empty(Stack<Character> stack){
while(!stack.isEmpty()){
stack.pop();
}
}
}
2. Largest Number
第一题就是leetcode原题 Largest Number 只是换成了return一个arr而已 我是改写compareTo再quick sort arr实现的
557. Reverse Words in a String III
input : drawbridge is the best
output: egdirbward si eht tseb
Find the Maximum Length
/**Given an n*n array. Each element is a 0 or 1 and each row is sorted in descending order (1s followed by 0s).
1 1 0 0 0
1 1 1 0 0
1 1 1 1 0
1 0 0 0 0
1 1 0 0 0
Find the maximum sum that you will get by adding the elements of a row.
Output for the above example is 4.
A naive Solution would be to scan and calculate each rows number of 1s which costs
O(N2) To speed up we can use binary search to search for the last 1 in each row
but still gives NlogN time cost
A improved Alg: scan for the last "1" position of first row and check the second
row at the corresponding position, if it's "1" go on and update the right most 1
index if not then skip this row. In general the idx are only go through the number
of colomns once, so it's a O(N) running time
**/
public class solution {
public static void main(String[] args){
int[] test = {1,1,1,0,0};
int[][] board = {{1,1,0,0,0},{1,1,1,0,0},{1,1,1,1,0},{1,0,0,0,0},{1,1,0,0,0}};
System.out.println(binarySearch(test,0,4));
System.out.println(maxSum(board));
}
public static int maxSum(int[][] board){
int res = -1;
int m = board.length;
int n = board[0].length;
int idx = binarySearch(board[0],0,n - 1);
for(int i = 1;i < m;i++){
if(board[i][idx] == 1){
idx = binarySearch(board[i],idx,n - 1);
res = Math.max(res, idx + 1);
}
}
return res;
}
//return the last 1 index
public static int binarySearch(int[] array,int start,int end){
while(start < end){
int mid = start + (end - start)/2;
int val = array[mid];
if(val == 1){
start = mid + 1;
}
else{
end = mid - 1;
}
}
return start - 1;
}
}
160. Intersection of Two Linked Lists
56. Merge Intervals
Find the Closest Number in a Sorted Array
/** Given a sorted array of 1000 numbers,write code to find the closest number
* to the given input k. In case of a tie any one of them is fine. Array is static but multiple k’s need to be looked up.
* @author Christina
* O(LogN) using binary search since the array is already sorted
*/
public class ClosestValue {
public static void main(String[] args){
int[] test = {1,4,9,11,12,40,55};
System.out.println(closest(test,50));
}
//return the closest value to K in the given sorted array
public static int closest(int[] arr,int k){
int start = 0;
int end = arr.length - 1;
while(start + 1 < end){
int mid = start + (end - start)/2;
int val = arr[mid];
if(k > val){
start = mid;
}
else if(val == k)return arr[mid];
else{
end = mid;
}
}
int v1 = Math.abs(arr[start] - k);
int v2 = Math.abs(arr[end] - k);
if(v1 < v2)return arr[start];
else return arr[end];
}
}
Binary tree inorder traversal
import java.util.*;
public class BST {
public int val;
public BST left;
public BST right;
public BST(int val){
this.val = val;
this.left = null;
this.right = null;
}
private List<Integer> inorderTraverse(){
List<Integer> res = new ArrayList<Integer>();
helper(this,res);
return res;
}
private void helper(BST node,List<Integer> res){
if(node == null)return;
helper(node.left,res);
res.add(node.val);
helper(node.right,res);
}
@Override
public String toString(){
StringBuilder bd = new StringBuilder();
List<Integer> list = inorderTraverse();
for(Integer i: list){
bd.append(i);
}
return bd.toString();
}
}
Merge Two Balanced BST Tree
You are given two balanced binary search trees e.g., AVL or Red Black Tree. Write a function that merges the two given balanced BSTs into a balanced binary search tree. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time.
I. generate the sorted traversal of two tree, merge the sorted array and rebuild the tree from the sorted array. Every Time select the middle element as the TreeNode
public TreeNode merge(TreeNode first,TreeNode second){
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
inOrder(first,list1);
inOrder(second,list2);
int[] arr = mergeList(list1,list2);
return buildTree(arr,0,arr.length - 1);
}
public inOrder(TreeNode root,List<Integer> res){
Stack<TreeNode> stack = new Stack();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
res.add(p.val);
p = p.right;
}
return res;
}
public int[] mergeList(List<Integer> list1,List<Integer> list2){
int[] res = new int[list1.size() + list2.size()];
int i = 0;
int j = 0;
int idx = 0;
while(i < list1.size() && j < list2.size()){
if(list1.get(i) < list2.get(j)){
arr[idx++] = list1.get(i++);
}
else{
arr[idx++] = list.get(j++);
}
}
while(i < list1.size()){
arr[idx++] = list1.get(i++);
}
while(j < list2.size()){
arr[idx++] = list2.get(j++);
}
return res;
}
//build a balanced bst from a sorted array
public TreeNode buildTree(int[] arr,int left,int right){
if(left > right)return null;
int mid = left + (right - left)/2;
TreeNode root = new TreeNode(mid);
root.left = buildTree(arr,0,mid - 1);
root.right = buildTree(arr,mid + 1,right);
return root;
}
II Insert the node one by one