Scott
BAN USERI was a SDET of Oracle OBIEE Team and I am looking for a new SDET/STE opportunity .
the idea for this one is binary search to find low bound (row) and upper bound (col) for the
2-d array
private int getlength(String target){
int count = 0 ;
for (char c : target.toCharArray()) {
if (c != ' ') {
count++;
}
}
return count ;
}
public void createSquare (String target){
int len = getlength(target) ;
if (len == 0) {
return ;
}
long low = 1 , high = len ;
while (low + 1 < high) {
long mid = low + (high - low) / 2 ;
if (mid * mid < len ) {
low = mid ;
} else{
high = mid ;
}
}
char [][] ch = null ;
int row = 0 , col = 0 ;
if (high * high == len) {
row = (int) high ;
col = (int) high ;
ch = new char[row][col];
} else if (low * low == len) {
row = (int) low ;
col = (int) low ;
ch = new char[(int)row][(int)col];
} else{
row = (int) low ;
col = (int) high ;
ch = new char[(int)row][(int)col];
}
createMatrix (ch, target);
display (ch);
}
private void createMatrix (char [][] matrix, String word){
int row = matrix.length , col = matrix[0].length;
int i = 0 , j = 0 , p = 0;
while (i < row) {
j = 0 ;
while (p < word.length() && j < col) {
if (word.charAt(p) != ' ') {
matrix[i][j++] = word.charAt(p) ;
}
p++;
}
i++;
}
}
private void display (char [][] matrix){
int row = matrix.length , col = matrix[0].length;
for (int i = 0 ; i < row ; ++i) {
for (int j = 0 ; j < col ; ++j) {
if (matrix[i][j] != '\u0000') {
System.out.print(matrix[i][j]);
}
}
System.out.println();
}
}
public String longestConsecutiveString(String target){
int tail = 0 , max = 0 ;
String rst = "" ;
for (int i = 1 ; i < target.length() ; ++i) {
if (target.charAt(i) - target.charAt(i -1) != 1) {
if (i - tail > max) {
max = i - tail ;
rst = target.substring(tail, i) ;
}
tail = i ;
}
}
return rst ;
}
- Scott March 04, 2015dp solution
public int match (String target, String source){
int [][] f = new int[target.length() + 1][source.length() + 1] ;
for (int i = 0 ; i <= source.length() ; ++i) {
f[0][i] = 1;
}
f[0][0] = 1;
for (int i = 1 ; i <= target.length() ; ++i) {
for (int j = 1 ; j <= source.length() ; ++j) {
if (target.charAt(i - 1) == source.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + f[i][j - 1] ;
} else{
f[i][j] = f[i][j - 1] ;
}
}
}
return f[target.length()][source.length()] ;
}
- Scott March 04, 2015public String compress(String target){
char [] chs = target.toCharArray() ;
int tail = 0 , j = 0 ;
for (int i = 1 ; i <= chs.length ; ++i) {
if (i == chs.length || chs[j] != chs[i]) {
chs[tail++] = chs[j] ;
if (i - j > 1) {
if (i - j < 10) {
chs[tail] = (char)((i - j) + '0');
tail++;
} else{
char [] digits = String.valueOf(i - j).toCharArray() ;
for (char c : digits) {
chs[tail++] = c ;
}
}
}
j = i ;
}
}
return new String(chs, 0, tail) ;
}
- Scott March 04, 2015backtrack
public boolean checkPattern (String target, String pattern){
HashMap<Character, List<String>> map = new HashMap<> ();
HashMap<Character, Integer> compare = new HashMap<> ();
for (char c : pattern.toCharArray()) {
int count = compare.containsKey(c) ? compare.get(c) + 1 : 1 ;
compare.put(c, count);
}
return helper (target, pattern, 0 , 0, map, compare);
}
private boolean helper (String target , String pattern , int j , int index, HashMap<Character,List<String>> map, HashMap<Character,Integer> compare){
if (j == pattern.length() - 1) {
char p = pattern.charAt(j) ;
String word = target.substring(index, target.length()) ;
boolean f = false ;
if (!map.containsKey(p)) {
List<String> set = new ArrayList<> ();
set.add(word) ;
map.put(p, set);
f = checkResult (compare, map, pattern) ;
map.remove(p);
} else{
String pre = map.get(p).get(0) ;
if (word.equals(pre)) {
map.get(p).add(word);
}
f = checkResult (compare, map, pattern) ;
}
return f ;
}
if (j == pattern.length()) return false ;
boolean flag = false ;
char p = pattern.charAt(j) ;
for (int i = index ; i < target.length() ; ++i) {
String word = target.substring(index, i + 1) ;
if (!map.containsKey(p)) {
List<String> set = new ArrayList<> ();
set.add(word);
map.put(p, set) ;
flag = helper (target, pattern, j + 1, i + 1 ,map ,compare);
map.remove(p) ;
} else{
String pre = map.get(p).get(0) ;
if (word.equals(pre)) {
map.get(p).add(word) ;
flag = helper (target, pattern, j + 1, i + 1, map, compare);
}
}
if (flag) {
return flag ;
}
}
return flag ;
}
private boolean checkResult (HashMap<Character,Integer> compare, HashMap<Character, List<String>> cache, String pattern){
for (char c : pattern.toCharArray()) {
if (compare.get(c) != cache.get(c).size()) {
return false ;
}
}
return true ;
}
sliding window
public String lengthOfLongestSubstring(String s) {
int max = 0 ;
int tail = 0 ;
String candidate = "";
HashMap<Character, Integer> map = new HashMap<> ();
for (int i = 0 ; i < s.length() ; ++i) {
if (!map.containsKey(s.charAt(i))) {
map.put(s.charAt(i), 1) ;
} else{
map.put(s.charAt(i), map.get(s.charAt(i)) + 1) ;
while (map.get(s.charAt(i)) != 1) {
map.put(s.charAt(tail), map.get(s.charAt(tail)) - 1) ;
tail++;
}
}
if (max < i - tail + 1) {
max = i - tail + 1 ;
candidate = s.substring(tail, i + 1) ;
}
}
return candidate ;
}
- Scott March 02, 2015public boolean isPalindrome(String s) {
int i = 0 , j = s.length() - 1 ;
while (i <= j) {
while (i <= j && !Character.isLetterOrDigit(s.charAt(i))){
i++;
}
while (i <= j && !Character.isLetterOrDigit(s.charAt(j))){
j--;
}
if (i <= j && Character.toLowerCase(s.charAt(i)) !=
Character.toLowerCase(s.charAt(j))) {
return false ;
}
i++;
j--;
}
return true ;
}
- Scott February 26, 2015we could have mutiple longest increasing sequences
if the the requirement is to find all of them , the solution should be a dfs the time complexity is 2^n
if we only need to find one of them ,dp is enough
what we need to do is to use another array to track , the array will save the index right before the current index
after done ,we iterate the array and get the longest string
public String getLongestStr (int[] nums){
if (nums == null || nums.length == 0) {
return "" ;
}
int max = Integer.MIN_VALUE ;
int [] dp = new int [nums.length] ;
int [] track = new int [nums.length] ;
Arrays.fill(track, -1);
int start = 0 ;
Arrays.fill(dp, 1);
for (int i = 1 ; i < nums.length ; ++i) {
for (int j = 0 ; j < i ; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1 ;
track[i] = j;
}
}
if (dp[i] > max) {
max = dp[i] ;
track[i] = j ;
start = i ;
}
}
}
StringBuilder rst = new StringBuilder ();
int index = start ;
rst.append(nums[start]) ;
while (track[index] != -1) {
index = track[index];
rst.append(nums[index]) ;
}
rst.reverse() ;
return rst.toString();
}
- Scott February 24, 2015we could have mutiple longest increasing sequences
if the the requirement is to find all oof them , the solution should be a dfs the time complexity is 2^n
if we only need to find one of them ,dp is enough
what we need to do is to use another array to track , the array will save the index right before the current index
after done ,we iterate the array and get the longest string
public String getLongestStr (int[] nums){
if (nums == null || nums.length == 0) {
return "" ;
}
int max = Integer.MIN_VALUE ;
int [] dp = new int [nums.length] ;
int [] track = new int [nums.length] ;
Arrays.fill(track, -1);
int start = 0 ;
Arrays.fill(dp, 1);
for (int i = 1 ; i < nums.length ; ++i) {
for (int j = 0 ; j < i ; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1 ;
track[i] = j;
}
}
if (dp[i] > max) {
max = dp[i] ;
track[i] = j ;
start = i ;
}
}
}
StringBuilder rst = new StringBuilder ();
int index = start ;
rst.append(nums[start]) ;
while (track[index] != -1) {
index = track[index];
rst.append(nums[index]) ;
}
rst.reverse() ;
return rst.toString();
}
- Scott February 24, 2015public void convert (long num ,int steps){
if (num > 10) {
long digit = num % 10 ;
convert (num / 10 , steps + 1) ;
System.out.print(digit);
if (steps != 0 && steps % 3 == 0) {
System.out.print(',');
}
} else{
System.out.print(num) ;
if (steps % 3 == 0) {
System.out.print(',');
}
}
}
- Scott February 19, 2015inorder traversal
iterate
public TreeNode convert (TreeNode root){
TreeNode curr = root ;
Stack<TreeNode> stack = new Stack<> ();
TreeNode dummyNode = new TreeNode (1);
TreeNode pre = null ;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr) ;
curr = curr.left ;
} else {
//access the middle node
TreeNode t = stack.pop() ;
if (pre == null) {
if (dummyNode.next == null) {
dummyNode.next = t ;
}
pre = t ;
} else{
pre.next = t;
t.prv = pre ;
pre = t ;
}
curr = t.right ;
}
}
return dummyNode.next ;
}
recursive
TreeNode pre = null ;
TreeNode head = null ;
public void convert_recursive (TreeNode root){
if (root == null) return ;
convert_recursive (root.left);
if (pre == null) {
if (head == null) head = root ;
pre = root ;
} else {
pre.next = root ;
root.prv = pre ;
pre = root ;
}
convert_recursive (root.right);
}
- Scott February 05, 2015public int findNumberOfWays (int n, double m){
int ways = 0 ;
int k = (int)Math.sqrt(n) ;
for (double i = 1 , j = k ; i < j ;) {
if (Math.pow(i, 2) + Math.pow(j, 2) == n) {
ways++;
i++;
j--;
} else if (Math.pow(i, 2) + Math.pow(j, 2) > n) {
j-- ;
} else {
i++ ;
}
}
return ways ;
}
- Scott February 05, 2015public List<String> findLongestWord (String [] wrds , char [] chars ){
int maxLen = 0 ;
HashMap <Character, Integer> dict = new HashMap<> ();
HashMap <Integer, List<String> > rst = new HashMap<> ();
for (char ch : chars) {
int c = dict.containsKey(ch) ? dict.get(ch) + 1 : 1 ;
dict.put(ch, c) ;
}
HashMap <Character, Integer> runtime = new HashMap<> ();
for (String w : wrds) {
int count = 0 ;
for (char c : w.toCharArray()) {
if (!dict.containsKey(c)) break ;
int curr = runtime.containsKey(c) ? runtime.get(c) + 1 : 1 ;
if (curr > dict.get(c)) break ;
count++;
if (count == w.length()) {
maxLen = Math.max(maxLen, count) ;
if (!rst.containsKey(count)) {
List<String> list = new ArrayList<> ();
list.add(w) ;
rst.put(count, list) ;
} else{
rst.get(count).add(w) ;
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;
}
- Scott February 05, 2015public List<String> findLongestWord (String [] wrds , char [] chars ){
int maxLen = 0 ;
HashMap <Character, Integer> dict = new HashMap<> ();
HashMap <Integer, List<String> > rst = new HashMap<> ();
for (char ch : chars) {
int c = dict.containsKey(ch) ? dict.get(ch) + 1 : 1 ;
dict.put(ch, c) ;
}
HashMap <Character, Integer> runtime = new HashMap<> ();
for (String w : wrds) {
int count = 0 ;
for (char c : w.toCharArray()) {
if (!dict.containsKey(c)) break ;
int curr = runtime.containsKey(c) ? runtime.get(c) + 1 : 1 ;
if (curr > dict.get(c)) break ;
count++;
if (count == w.length()) {
maxLen = Math.max(maxLen, count) ;
if (!rst.containsKey(count)) {
List<String> list = new ArrayList<> ();
list.add(w) ;
rst.put(count, list) ;
} else{
rst.get(count).add(w) ;
}
}
runtime.put(c, curr) ;
}
runtime.clear();
}
return maxLen == 0 ? new ArrayList<String>() : rst.get(maxLen) ;
}
public String getLongestConsecutiveChar (String s){
int tail = 0 , maxLen = 0;
String result = "";
for (int i = 1 ; i < s.length() ; ++i) {
if (s.charAt(i) != s.charAt( i -1)) {
if (i - tail > maxLen) {
maxLen = i - tail;
result = s.substring(tail, i) ;
}
tail = i ;
}
}
if (s.length() - tail > maxLen) {
result = s.substring(tail, s.length()) ;
}
return result ;
}
- Scott February 04, 2015public String findMin (String s, HashSet<Character> set){
int len = set.size() , count = 0 , tail = 0 , minLen = Integer.MAX_VALUE;
String result = "" ;
HashMap<Character, Integer> map = new HashMap<> ();
for (int i = 0 ; i < s.length() ; ++i) {
char ch = s.charAt(i) ;
if (set.contains(ch)) {
int c = map.containsKey(ch) ? map.get(ch) + 1 : 1 ;
if (c == 1) count++;
map.put(ch, c) ;
}
while (count == len) {
if (set.contains(s.charAt(tail))) {
int v = map.get(s.charAt(tail));
if (v - 1 == 0) {
count--;
}
map.put(s.charAt(tail), v - 1) ;
}
if (i - tail + 1 < minLen) {
minLen = i - tail + 1 ;
result = s.substring(tail, i + 1) ;
}
tail++;
}
}
return result;
}
- Scott February 04, 2015my dp solution
public int find_dp (int n){
if (n == 0) return 1 ;
int [] dp = new int [n + 1] ;
double bound = Math.sqrt(n) ;
dp[0] = 0 ;
for (int i = 1 ; i <= n ; ++i) {
dp[i] = Integer.MAX_VALUE ;
for (int j = 1 ; j <= bound ; ++j) {
if (i >= Math.pow(j, 2)) {
dp[i] = dp[i - (int)Math.pow(j, 2)] + 1 < dp[i] ? dp[i - (int)Math.pow(j, 2)] + 1 : dp[i] ;
}
}
}
return dp[n] ;
}
my recursive method
public int find (double d, int count){
if (d == 0) return count ;
if (d < 0) return 0 ; ;
int min = Integer.MAX_VALUE;
for (int i = 1 ; i <= Math.sqrt(d) ;++i) {
if (d >= Math.pow(i, 2)) {
int c = find (d - Math.pow(i, 2), count + 1);
min = Math.min(c, min) ;
}
}
return min ;
}
- Scott January 29, 2015public String removeOneString (String text , String find , String r) {
Stack <Character> stack = new Stack<Character> ();
char [] chs = text.toCharArray() ;
char [] replace = r.toCharArray() ;
int count = 0 ;
StringBuilder sb = new StringBuilder ();
for (int i = 0 ; i < chs.length ; ++i) {
if (stack.isEmpty()) {
stack.push(chs[i]) ;
continue ;
}
sb.append(stack.peek()) ;
sb.append(chs[i]) ;
if (find.equals(sb.toString())) {
stack.pop() ;
count++;
} else {
int p = 0;
while (p < count) {
for (char c : replace ) {
stack.push(c) ;
}
p++;
}
count = 0 ;
stack.push(chs[i]) ;
}
sb.setLength(0) ;
}
while (!stack.isEmpty()) {
sb.append(stack.pop()) ;
}
return sb.reverse().toString() ;
}
- Scott June 09, 2014public String removeSpace (String text){
char [] chs = text.toCharArray() ;
int i = 0 ;
int j = i ;
boolean head = false ;
boolean isSpace = false ;
for (i = 0 ; i < chs.length ; ++i) {
if (!head && chs[i] == ' ') {
continue ;
}
head = true ;
if (chs[i] != ' ') {
chs[j++] = chs[i] ;
isSpace = false ;
} else {
if (!isSpace) {
chs[j++] = chs[i] ;
}
isSpace = true ;
}
}
return new String(chs, 0 , j) ;
}
- Scott June 09, 2014public int removeSub(String target, HashSet <String> set) {
if (target.length() == 0) {
return 0 ;
}
Stack<Character> stack = new Stack<Character>();
char [] chs = target.toCharArray() ;
for (int i = 0 ; i < chs.length ; ++i) {
if (stack.isEmpty()) {
stack.push(chs[i]);
continue;
}
StringBuilder sub = new StringBuilder ();
sub.append(stack.peek()) ;
sub.append(chs[i]) ;
if (set.contains(sub.toString())) {
stack.pop() ;
} else {
stack.push(chs[i]) ;
}
sub.setLength(0) ;
}
return stack.size() ;
}
- Scott June 08, 2014public static int getLength(String word, char [] chs){
int [] map = new int [26];
int count = 0;
char [] chars = word.toCharArray() ;
for (int i = 0 ; i < chars.length ; ++i){
map[chars[i] - 'a']++;
}
for (char c: chs){
if (map[c - 'a'] != 0){
map[c - 'a'] -- ;
count++ ;
}
}
return count ;
}
use the above method to get length for all words ,then sorted or using a binary heap
public static void multiply(List<Integer> listA, List<Integer> listB){
List<Integer> a = null ;
List<Integer> b = null ;
if (listA.size() >= listB.size()){
a = listA ;
b = listB ;
}else{
a = listB ;
b = listA ;
}
int carrier = 0;
for (int i = a.size() - 1 ; i >= 0 ; --i){
for (int j = b.size() - 1 ; j >= 0 ; --j){
carrier = 0 ;
int product = b.get(j) * a.get(i) ;
a.set(i, product % 10 + carrier);
carrier = product / 10 ;
}
}
if (carrier > 0){
a.add(0, carrier) ;
}
for (Integer i : a){
System.out.print(i);
}
System.out.println();
}
- Scott May 06, 2014public void merge(LinkedList<List<Integer>> queue){
while (queue.size() >= 2){
List <Integer> listA = queue.pop() ;
List <Integer> listB = queue.pop() ;
List<Integer> tmp = new LinkedList<Integer>();
int i = 0 ;
int j = 0 ;
while (i < listA.size() && j < listB.size()){
if (listA.get(i) <= listB.get(j)){
tmp.add(listA.get(i++)) ;
}else{
tmp.add(listB.get(j++)) ;
}
}
while (i < listA.size()){
tmp.add(listA.get(i++)) ;
}
while (j < listB.size()){
tmp.add(listB.get(j++)) ;
}
queue.push(tmp);
}
}
- Scott May 06, 2014public static void findMaxNumOfOne(int [][] matrix){
int [][] dp = new int[matrix.length][matrix[0].length] ;
dp [0][0] = matrix[0][0] == 1 ? 1 : 0;
int max_h = -1 ;
int max_d = -1 ;
for (int i = 0 ; i < matrix.length ; ++i){
for (int j = 1 ; j < matrix[0].length ; ++j){
//horizon
if ( matrix[i][j] != 0 && dp [i][j] < matrix[i][j] + dp [i][j-1]) {
dp [i][j] = matrix[i][j] + dp [i][j-1];
max_h = Math.max(max_h, dp [i][j]);
}
}
}
int [][] dp1 = new int[matrix.length][matrix[0].length] ;
dp1 [0][0] = matrix[0][0] == 1 ? 1 : 0;
for (int i = 0 ; i < matrix.length ; ++i){
for (int j = 1 ; j < matrix[0].length ; ++j){
//down
if ( i+1 < matrix.length && matrix[i+1][j-1] != 0 && dp1 [i+1][j-1] < matrix[i+1][j-1] + dp1 [i][j-1] ){
dp1 [i+1][j-1] = matrix[i+1][j-1] + dp1 [i][j-1];
max_d = Math.max(max_d, dp1 [i+1][j-1]);
}
}
}
max_h = Math.max(max_h, max_d) ;
for (int i = 0 ; i < max_h ; ++i ){
System.out.print(1 + " ");
}
}
- Scott May 06, 2014public static void removeDuplicate(String exp){
int end = exp.length() - 1 ;
char [] chs = exp.toCharArray() ;
Stack<Character> stack = new Stack<Character>();
for (int i = 0 ; i <= end ; ++i){
if (chs[i] == '('){
if (!stack.isEmpty() && stack.peek() == '('){
System.out.println("find " + stack.peek() + chs[end--]);
stack.pop();
}
}
stack.push(chs[i]);
}
for (Character c : stack){
System.out.print(c);
}
}
- Scott May 03, 2014class FirstCommonAncestorImp implements FirstCommonAncestor {
@Override
public Node commonAncestor(Node nodeOne, Node nodeTwo) {
Stack<Node> nodeOneStack = new Stack<Node>();
Stack<Node> nodeTwoStack = new Stack<Node>();
getNodes(nodeOne,nodeOneStack);
getNodes(nodeOne,nodeTwoStack);
Node commonAncestor = null ;
while (!nodeOneStack.isEmpty() && !nodeTwoStack.isEmpty()){
Node one = nodeOneStack.pop();
Node two = nodeTwoStack.pop();
if (one == two){
commonAncestor = one ;
}
}
return commonAncestor;
}
public void getNodes(Node node, Stack<Node> stack){
if (!node.isRoot()){
stack.push(node);
getNodes(node.parent, stack);
}else{
stack.push(node);
}
}
}
- Scott May 01, 2014public static void findCommonElements(int [] a , int [] b){
// each containing 8 bits integer
boolean [] flag = new boolean [256] ;
for (int i = 0 ; i <= a.length ; ++i){
flag [a[i]] = true ;
}
for (int i = 0 ; i < b.length ; ++i){
if (flag[b[i]]){
System.out.println("common elements is " + b[i]);
}
}
}
- Scott April 29, 2014dp
public static void findMaxSeq(int [] seq){
int [] dp = new int [seq.length] ;
dp [0] = seq [0] ;
int max = Integer.MIN_VALUE ;
int end = -1 ;
int start = -1 ;
for (int i = 1 ; i < seq.length ; ++i){
if (seq[i] + dp[i-1] <= 0 ){
dp [i] = seq[i] ;
}else{
dp [i] = seq[i] + dp[i-1] ;
}
if (dp[i] > max){
max = dp [i];
end = i;
}
}
end = dp [0] > max ? 0 : end;
for (int i = 0 ; i < dp.length ; ++i){
if (dp[i] >= 0){
start = i ;
break;
}
}
System.out.println("from " + start + " to " + end);
}
- Scott April 28, 2014public static boolean OneEditApart(String s1, String s2){
return editDisance(s1, s2) == 1 ;
}
public static int editDisance(String s1, String s2){
int [] [] dp = new int [s1.length() + 1] [s2.length() + 1] ;
for (int i = 0 ; i <= s1.length() ; ++i){
dp [i][0] = i;
}
for (int j = 0 ; j <= s2.length(); ++j ){
dp [0][j] = j;
}
for (int i = 1 ; i <= s1.length() ; ++i){
for (int j = 1 ; j <= s2.length() ; ++j){
// replacement
int replace = dp[i-1][j-1] + (s1.charAt(i -1 ) == s2.charAt(j - 1)? 0 : 1);
// remove
int remove = dp [i-1][j] + 1 ;
// insert
int insert = dp [i][j-1] + 1 ;
int min = Math.min(replace, remove) ;
min = Math.min(insert, min);
dp[i][j] = min ;
}
}
return dp[s1.length()][s2.length()];
}
recursive solution
public static void removeString_rec(char [] chs , int len ,int current, int next){
if (chs.length == next){
if (len == 0){
System.out.println(-1);
} else {
for (int i = 0 ; i < len ; ++i){
System.out.print(chs[i]);
}
}
} else {
if (chs [current] == chs [next]){
len -= 2;
if (current != 0){
current-- ;
}
} else{
current++ ;
chs[current] = chs [next] ;
}
removeString_rec(chs, len, current, next + 1);
}
}
- Scott April 09, 2014recursive solution
public static void removeString_rec(char [] chs , int len ,int current, int next){
if (chs.length == next){
if (len == 0){
System.out.println(-1);
} else {
for (int i = 0 ; i < len ; ++i){
System.out.print(chs[i]);
}
}
} else {
if (chs [current] == chs [next]){
len -= 2;
if (current != 0){
current-- ;
}
} else{
current++ ;
chs[current] = chs [next] ;
}
removeString_rec(chs, len, current, next + 1);
}
}
- Scott April 09, 2014public static void removeString(String input){
Stack<Character> stack = new Stack<Character>() ;
for (int i = 0 ; i < input.length() ;++i){
if (!stack.isEmpty()){
if (input.charAt(i) == stack.peek()){
stack.pop();
}else{
stack.push(input.charAt(i));
}
}else{
stack.push(input.charAt(i));
}
}
if (stack.isEmpty()){
System.out.println (-1) ;
}else{
Iterator<Character> it = stack.iterator() ;
while (it.hasNext()){
System.out.print(it.next());
}
}
System.out.println();
}
- Scott April 08, 2014public int [] product(int [] input){
int [] dp = new int [input.length] ;
int [] front = new int [input.length] ;
int [] rear = new int [input.length] ;
front [0] = 1 ;
rear [rear.length - 1] = 1;
for (int i = 1 ; i < front.length ; ++i){
front [i] = front [i - 1] * input [i - 1] ;
}
for (int i = rear.length - 2; i >= 0 ; --i){
rear [i] = rear[i + 1] * input [ i + 1] ;
}
for (int i = 0 ; i < input.length ; ++i){
dp [i] = front [i] * rear [i];
}
return dp;
}
- Scott April 03, 2014public int [] product(int [] input){
int [] dp = new int [input.length] ;
int [] front = new int [input.length] ;
int [] rear = new int [input.length] ;
front [0] = 1 ;
rear [rear.length - 1] = 1;
for (int i = 1 ; i < front.length ; ++i){
front [i] = front [i - 1] * input [i - 1] ;
}
for (int i = rear.length - 2; i >= 0 ; --i){
rear [i] = rear[i + 1] * input [ i + 1] ;
}
for (int i = 0 ; i < input.length ; ++i){
dp [i] = front [i] * rear [i];
}
return dp;
}
public static char find(char [] chs , char target){
int left = 0;
int right = chs.length - 1;
while(left<=right){
int mid = (left+right)/2;
if (chs[mid] == target){
if (mid<chs.length - 1){
return chs[mid+1];
}else{
return chs[0];
}
} else if (target > chs[mid]){
left = mid+1;
}else{
right = mid -1 ;
}
}
return left == 0? chs[0]:left==chs.length? chs[left-1]:chs[left];
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
public class TreeBuilder {
HashMap<Integer,Node> vertexMap = new HashMap<Integer,Node>();
static class Node {
int value ;
int scratch;
Node left;
Node right;
List<Edge> adj;
public Node (int value){
this.value = value;
adj= new LinkedList<Edge>();
}
}
static class Edge{
Node node ;
public Edge(Node node ){
this.node = node;
}
}
private Node getVertex(int name){
Node v= vertexMap.get(name);
if (v == null){
v = new Node(name);
vertexMap.put(name, v);
}
return v;
}
public void addEdge(int sourceName, int destName){
Node v=getVertex(sourceName);
Node w=getVertex(destName);
v.adj.add(new Edge(w));
}
public void build(){
for (Node node : vertexMap.values()){
for (Edge edge : node.adj){
edge.node.scratch++;
}
}
Node root = null;
for (Node node : vertexMap.values()){
if (node.scratch==0){
root = node;
break;
}
}
if (root==null){
throw new NoSuchElementException("cannot find the root node");
}
Queue <Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()){
Node current = queue.poll();
for (Edge e : current.adj){
if (current.left==null){
current.left = e.node;
} else if (current.right==null){
current.right = e.node;
}
queue.add(e.node);
}
}
}
public static void main(String []args){
int [][] nodes = {{2,4},
{1,2},
{3,6},
{1,3},
{2,5}
};
TreeBuilder tb = new TreeBuilder();
for (int i = 0;i<nodes.length ;++i){
for (int j = 0;j<1 ;++j){
tb.addEdge(nodes[i][j],nodes[i][j+1]);
}
}
tb.build();
}
}
- Scott February 02, 2014public String replace(String txt){
int sp= 0;
char [] chs = txt.toCharArray();
for (int i =0 ;i<chs.length ;++i){
if (chs[i] ==' '){
sp++;
}
}
char [] n_ch = new char [txt.length()+sp*2];
int j =0;
for (int i = 0 ;i<chs.length ;++i){
if (chs[i]==' '){
n_ch[j] = '%';
n_ch[j+1] = '2';
n_ch[j+2] = '0';
j+=3;
}else{
n_ch[j++] = chs [i] ;
}
}
return new String(n_ch);
}
RepNelson Perez, Software Engineer
can you please explain why the heap size is m ? m == array.size ?
- Scott March 06, 2015