/*
* Author: Yang Pei
* Problem: Check K Sum
*
* Note:
* Given an array of non-negative numbers, check if we could use exactly K elements
* in the array (each element could only be used once) to get a target sum, we assume
* that the given target and k is valide.
*
* Solution:
* Using dp to solve the problem, dp[i][j] means if we could obtain sum i using j
* elements, then dp[i][j] |= dp[i-A[k]][j-1].
*/
import java.util.*;
public class CheckKSum {
public static boolean kSum(int[] num, int target, int k) {
int n = num.length;
boolean[][] dp = new boolean[target+1][k+1];
dp[0][0] = true;
for(int i = 0; i < n; i++) {
for(int j = target; j >= num[i]; j--) {
for(int p = 1; p <= k; p++) {
dp[j][p] |= dp[j-num[i]][p-1];
}
}
}
return dp[target][k];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
int[] num = new int[n];
for(int i = 0; i < n; i++) {
num[i] = scan.nextInt();
}
int target = scan.nextInt();
int k = scan.nextInt();
System.out.println(kSum(num, target, k));
}
scan.close();
}
}
2015年1月7日星期三
Check K Sum
2015年1月6日星期二
BST to Double Linked List
/*
* Author: Yang Pei
* Problem: BST to Double Linked List
* Source: http://www.careercup.com/question?id=4863668900593664
*
* Note:
* Given a BST, convert this BST into a double linked list that is sorted and
* returns the head of the list. Do it in place with space complexity O(1).
*
* Solution:
* Use recursive method or use morris iterate.
*/
public class BSTtoDoubleLinkedList {
public static TreeNode BSTtoDLL(TreeNode root) {
if(root == null)
return null;
TreeNode pre = BSTtoDLL(root.left);
TreeNode next = BSTtoDLL(root.right);
if(pre == null) {
root.left = null;
root.right = next;
if(next != null)
next.left = root;
return root;
}
else {
TreeNode temp = pre;
while(temp.right != null)
temp = temp.right;
temp.right = root;
root.left = temp;
root.right = next;
if(next != null)
next.left = root;
return pre;
}
}
public static TreeNode BSTtoDLL1(TreeNode root) {
if(root == null)
return null;
TreeNode cur = root, tmp = null, pre = null;
while(cur != null) {
if(cur.left == null) {
cur.left = pre;
if(pre != null)
pre.right = cur;
pre = cur;
cur = cur.right;
}
else {
tmp = cur.left;
while(tmp.right != null && tmp.right != cur)
tmp = tmp.right;
if(tmp.right == null) {
tmp.right = cur;
cur = cur.left;
}
else {
cur.left = pre;
if(pre != null)
pre.right = cur;
pre = cur;
cur = cur.right;
}
}
}
while(root.left != null)
root = root.left;
return root;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
root.left.left = new TreeNode(0);
root.right = new TreeNode(4);
root.right.left = new TreeNode(3);
root.right.right = new TreeNode(5);
root.right.right.right = new TreeNode(6);
root = BSTtoDLL1(root);
TreeNode pre = null;
while(root != null) {
System.out.print(root.val + " ");
pre = root;
root = root.right;
}
System.out.println("");
while(pre != null) {
System.out.print(pre.val + " ");
pre = pre.left;
}
}
}
Move Zeros Down
/*
* Author: Yang Pei
* Problem: Move Zeros Down
*
* Note:
* Given a binary tree, move the zeros to the bottom, so that if a node's value is 0,
* any of its descendant are 0s.
* For example:
* 1
* / \
* 0 0
* / \ \
* 2 0 3
* could be changed to
* 1
* / \
* 2 3
* / \ \
* 0 0 0
*
* Solution:
* Use level traversal and then assign from back of the list to front, if we find
* a node that is not 0 and we still have 0 to assign, record the value and change
* the node to 0, otherwise all 0 have assigned, when we meet a node that is 0,
* assign a recorded value to it.
* Use preorder traversal, when a node is 0, try to find if there is a lowest descendent
* that is not 0, reutrn the node and change the value.
*/
import java.util.*;
public class MoveZerosDown {
public static void moveDown(TreeNode root) {
if(root == null)
return;
List<TreeNode> list = new ArrayList<TreeNode>();
int count = 0;
Queue<TreeNode> qu = new LinkedList<TreeNode>();
TreeNode dummy = new TreeNode(0);
qu.add(root); qu.add(dummy);
while(qu.size() != 0) {
TreeNode temp = qu.remove();
if(temp == dummy) {
if(qu.size() != 0)
qu.add(dummy);
}
else {
count = count + ((temp.val == 0) ? 1 : 0);
list.add(temp);
if(temp.left != null)
qu.add(temp.left);
if(temp.right != null)
qu.add(temp.right);
}
}
Stack<Integer> stack = new Stack<Integer>();
for(int i = list.size() - 1; i >= 0; i--) {
TreeNode temp = list.get(i);
if(count > 0) {
if(temp.val != 0) {
stack.push(temp.val);
temp.val = 0;
}
count--;
}
else {
if(temp.val == 0 && stack.size() > 0)
temp.val = stack.pop();
}
}
}
public static void moveDown1(TreeNode root) {
if(root == null)
return;
if(root.val == 0) {
TreeNode left = findNonZero(root.left);
TreeNode right = findNonZero(root.right);
if(left != null) {
root.val = left.val;
left.val = 0;
}
else if(right != null) {
root.val = right.val;
right.val = 0;
}
}
moveDown1(root.left);
moveDown1(root.right);
}
private static TreeNode findNonZero(TreeNode root) {
if(root == null)
return null;
TreeNode left = findNonZero(root.left);
TreeNode right = findNonZero(root.right);
if(left != null)
return left;
else if(right != null)
return right;
if(root.val != 0)
return root;
return null;
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
node1.left = new TreeNode(0);
node1.right = new TreeNode(0);
node1.left.left = new TreeNode(3);
node1.left.left.left = new TreeNode(0);
node1.left.right = new TreeNode(0);
node1.right.right = new TreeNode(5);
node1.left.right.left = new TreeNode(4);
node1.left.right.right = new TreeNode(0);
PrintBST.printBST(node1);
moveDown1(node1);
System.out.println("");
PrintBST.printBST(node1);
}
}
Reverse List String
/*
* Author: Yang Pei
* Problem: Reverse List String
*
* Note:
* Given a string represent by a list, each node in the list contains a character,
* A word is separated by space. Reverse each word in the list.
* For example
* 'h'->'e'->'l'->'l'->'o'->' '->'w'->'o'->'r'->'l'->'d' would be changed to
* 'o'->'l'->'l'->'e'->'h'->' '->'d'->'l'->'r'->'o'->'w'
*
* Solution:
* Two pointers. Be careful: there might be multiple spaces between two words. And there
* might be leading and tailing spaces. And there might contains no space and there might
* be all space.
*
* Define of the ListNodeC
* {
* char val;
* ListNodeC next;
* public ListNodeC(char ch) {
* this.val = ch;
* this.next = null;
* }
* }
*/
public class ReverseListString {
public static ListNodeC reverse(ListNodeC head) {
if(head == null)
return head;
ListNodeC dummy = new ListNodeC(' ');
dummy.next = head;
ListNodeC pointer1 = dummy, pointer2 = dummy;
while(pointer1.next != null) {
while(pointer2.next != null && pointer2.next.val == ' ')
pointer2 = pointer2.next;
if(pointer2.next == null)
break;
pointer1 = pointer2;
// pay attention here, otherwise would have infinite loop
pointer2 = pointer2.next;
while(pointer2.next != null && pointer2.next.val != ' ') {
ListNodeC temp = pointer2.next;
pointer2.next = temp.next;
temp.next = pointer1.next;
pointer1.next = temp;
}
pointer1 = pointer2;
}
return dummy.next;
}
public static void main(String[] args) {
String str = " a ba c ";
ListNodeC dummy = new ListNodeC(' ');
ListNodeC temp = dummy;
for(int i = 0; i < str.length(); i++) {
ListNodeC node = new ListNodeC(str.charAt(i));
temp.next = node;
temp = temp.next;
}
temp = dummy.next;
while(temp != null) {
System.out.print(temp.val);
temp = temp.next;
}
System.out.println("");
temp = reverse(dummy.next);
while(temp != null) {
System.out.print(temp.val);
temp = temp.next;
}
System.out.println("");
}
}
2015年1月4日星期日
[Leetcode] Binary Search Tree Iterator
The solution is also available here:https://gist.github.com/pyemma/bbe39014f436f2a5aa5b
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
if(root != null)
pushleft(root);
}
private void pushleft(TreeNode root) {
while(root != null) {
stack.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode temp = stack.pop();
if(temp.right != null)
pushleft(temp.right);
return temp.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
2015年1月3日星期六
[Leetcode] Excel Sheet Column Title
The solution is also available here:https://gist.github.com/pyemma/93a32e641b90288867ae
/*
* Author: Yang Pei
* Problem: Excel Sheet Column Title
* Source: https://oj.leetcode.com/problems/excel-sheet-column-title/
*
* Note:
* Given a positive integer, return its corresponding column title as appear in an Excel sheet.
* For example:
* 1 -> A
* 2 -> B
* 3 -> C
* ...
* 26 -> Z
* 27 -> AA
* 28 -> AB
* Solution:
* Recursive method or iterative method.
*/
public class ExcelSheetColumnTitle {
public String convertToTitle(int n) {
if(n == 0)
return "";
return convertToTitle((n-1)/26) + (char)((n-1)%26 + 'A');
}
public String convertToTitle1(int n) {
StringBuilder sb = new StringBuilder();
while(n > 0) {
sb.append((char)((n - 1) % 26 + 'A'));
n = (n - 1) / 26;
}
sb = sb.reverse();
return sb.toString();
}
}
[Leetcode] Compare Version Numbers
The solution is also available here:https://gist.github.com/pyemma/0d6f6368fdcfcb73451d
/*
* Author: Yang Pei
* Problem: Compare Version Numbers
* Source: https://oj.leetcode.com/problems/compare-version-numbers/
*
* Note:
* Compare two version numbers version1 and version1.
* If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
*
* You may assume that the version strings are non-empty and contain only digits and the . character.
* The . character does not represent a decimal point and is used to separate number sequences.
* For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
*
* Here is an example of version numbers ordering:
* 0.1 < 1.1 < 1.2 < 13.37
*
* Solution:
* Split the version according to the ".", then compare each number. Pay attention to
* leading zeros. If each version number is within the Integer, we could use Integer.paresInt
* instead of writing a function to compare.
*
* Corner case: 1.0 and 1, 1.0.1 and 1. In this case, we need to check the array with
* more split to see if each number is 0 or not.
*/
public class CompareVersionNumbers {
public static int compareVersion(String version1, String version2) {
String[] strs1 = version1.split("\\.");
String[] strs2 = version2.split("\\.");
for(int i = 0; i < Math.min(strs1.length, strs2.length); i++) {
if(compare(strs1[i], strs2[i]) != 0)
return compare(strs1[i], strs2[i]);
}
if(strs1.length < strs2.length) {
for(int i = strs1.length; i < strs2.length; i++) {
if(compare("0", strs2[i]) < 0)
return -1;
}
return 0;
}
else if(strs1.length > strs2.length) {
for(int i = strs2.length; i < strs1.length; i++) {
if(compare(strs1[i], "0") > 0)
return 1;
}
return 0;
}
else
return 0;
}
private static int compare(String num1, String num2) {
int ind1 = 0;
while(ind1 < num1.length() && num1.charAt(ind1) == '0')
ind1++;
int ind2 = 0;
while(ind2 < num2.length() && num2.charAt(ind2) == '0')
ind2++;
num1 = num1.substring(ind1);
num2 = num2.substring(ind2);
if(num1.length() < num2.length())
return -1;
else if(num1.length() > num2.length())
return 1;
else {
for(int i = 0; i < num1.length(); i++) {
if(num1.charAt(i) < num2.charAt(i))
return -1;
else if(num1.charAt(i) > num2.charAt(i))
return 1;
}
return 0;
}
}
public static void main(String[] args) {
String version1 = "1.0.1";
String version2 = "1";
System.out.println(compareVersion(version1, version2));
}
}
订阅：
博文 (Atom)