LintCode 496 · Toy Factory.py

	"""
	Your object will be instantiated and called as such:
	ty = ToyFactory()
	toy = ty.getToy(type)
	toy.talk()
	"""
	# Simulation OOP
	class Toy:
	def talk(self):
	raise NotImplementedError('This method should have implemented.')
	class Dog(Toy):
	# Write your code here
	def talk(self):
	print("Wow")
	class Cat(Toy):
	# Write your code here
	def talk(self):
	print("Meow")
	class ToyFactory:
	# @param {string} Type a string
	# @return {Toy} Get object of the type
	def getToy(self, type):
	# Write your code here
	if type == 'Dog':
	return Dog()
	elif type == 'Cat':
	return Cat()
	else:
	return None

view raw LintCode 496 · Toy Factory.py hosted with ❤ by GitHub

LintCode 97 · Maximum Depth of Binary Tree.py

	"""
	Definition of TreeNode:
	class TreeNode:
	def __init__(self, val):
	self.val = val
	self.left, self.right = None, None
	"""
	# Approach #1 - DFS - T O(n), S O(h), with n being #OfNodes, h being the depth.
	class Solution:
	"""
	@param root: The root of binary tree.
	@return: An integer
	"""
	def maxDepth(self, root):
	# write your code here
	if root is None:
	return 0
	return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

view raw LintCode 97 · Maximum Depth of Binary Tree.py hosted with ❤ by GitHub

LintCode 1178 · Student Attendance Record I.py

	# Approach #1 - Simulation, String - T O(n), S O(1)
	class Solution:
	"""
	@param s: a string
	@return: whether the student could be rewarded according to his attendance record
	"""
	def checkRecord(self, s):
	# Write your code here
	# if As > 1 or consective Ls > 2, false, otherwise true
	countA, countL = 0, 0
	for ch in s:
	if ch == 'A':
	countA += 1
	if countA > 1:
	return False
	countL = 0
	elif ch == 'L':
	countL += 1
	if countL > 2:
	return False
	else:
	countL = 0
	return True

view raw LintCode 1178 · Student Attendance Record I.py hosted with ❤ by GitHub

LintCode 1 · A + B Problem.py

	class Solution:
	"""
	@param a: An integer
	@param b: An integer
	@return: The sum of a and b
	"""
	def aplusb(self, a, b):
	# write your code here
	return a + b

view raw LintCode 1 · A + B Problem.py hosted with ❤ by GitHub

LintCode 39 · Recover Rotated Sorted Array.java

	// Approach #1 - 3-way flipping - T O(n), S O(1)
	public class Solution {
	/**
	* @param nums: An integer array
	* @return: nothing
	*/
	public void recoverRotatedSortedArray(List<Integer> nums) {
	// handle corner cases
	if (nums == null || nums.size() == 0) {
	return;
	}
	int n = nums.size();
	int endingIndex = n - 1;
	for (int i = 0; i < n - 1; i++) {
	if (nums.get(i) > nums.get(i + 1)) {
	endingIndex = i;
	break;
	}
	}
	// reverse left
	reverse(nums, 0, endingIndex);
	// reverse right
	reverse(nums, endingIndex + 1, n - 1);
	// reverse the whole thing
	reverse(nums, 0, n - 1);
	return;
	}
	private void reverse(List<Integer> nums, int left, int right) {
	while (left < right) {
	Integer tmp = nums.get(left);
	nums.set(left, nums.get(right));
	nums.set(right, tmp);
	left++;
	right--;
	}
	}
	}

view raw LintCode 39 · Recover Rotated Sorted Array.java hosted with ❤ by GitHub

LintCode 423 · Valid Parentheses.java

	// Approach #1 - T O(n), S O(n), given that n is the length of the input string.
	// Error-prone: Character instead of Characters
	public class Solution {
	/**
	* @param s: A string
	* @return: whether the string is a valid parentheses
	*/
	public boolean isValidParentheses(String s) {
	// write your code here
	if (s == null || s.length() == 0) {
	return true;
	}
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i < s.length(); i++) {
	char letter = s.charAt(i);
	if (isOpening(letter)) {
	stack.push(letter);
	} else {
	if (stack.isEmpty()) {
	return false;
	} else if (isMatching(stack.peek(), letter)) {
	stack.pop();
	} else {
	return false;
	}
	}
	}
	if (!stack.isEmpty()) {
	return false;
	}
	return true;
	}
	private boolean isOpening(char ch) {
	return (ch == '(' || ch == '[' || ch == '{');
	}
	private boolean isMatching(char ch1, char ch2) {
	return (ch1 == '{' && ch2 == '}') || (ch1 == '(' && ch2 == ')') || (ch1 == '[' && ch2 == ']');
	}
	}

view raw LintCode 423 · Valid Parentheses.java hosted with ❤ by GitHub

LintCode 442 · Implement Trie (Prefix Tree).java

	// Approach #1 - Trie - Data Structure implementation.
	// T O(h) for all the 3 searching functions, given that h is the height of the tree.
	public class Trie {
	private TrieNode root;
	public Trie() {
	// do intialization if necessary
	root = new TrieNode();
	}
	/*
	* @param word: a word
	* @return: nothing
	*/
	public void insert(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	node.sons.put(letter, new TrieNode());
	}
	node = node.sons.get(letter);
	}
	node.word = word;
	node.isWord = true;
	}
	/*
	* @param word: A string
	* @return: if the word is in the trie.
	*/
	public boolean search(String word) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < word.length(); i++) {
	char letter = word.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return node.isWord;
	}
	/*
	* @param prefix: A string
	* @return: if there is any word in the trie that starts with the given prefix.
	*/
	public boolean startsWith(String prefix) {
	// write your code here
	TrieNode node = root;
	for (int i = 0; i < prefix.length(); i++) {
	char letter = prefix.charAt(i);
	if (!node.sons.containsKey(letter)) {
	return false;
	}
	node = node.sons.get(letter);
	}
	return true;
	}
	private class TrieNode {
	public String word;
	public boolean isWord;
	public Map<Character, TrieNode> sons;
	public TrieNode() {
	this.word = null;
	this.isWord = false;
	sons = new HashMap<>();
	}
	public TrieNode(String word, boolean isWord) {
	this.word = word;
	this.isWord = isWord;
	sons = new HashMap<>();
	}
	}
	}

view raw LintCode 442 · Implement Trie (Prefix Tree).java hosted with ❤ by GitHub

LintCode 1301 · Game of Life.java

	// T O(mn) S O(1), 2 passes - Simulation
	public class Solution {
	/**
	* @param board: the given board
	* @return: nothing
	*/
	public void gameOfLife(int[][] board) {
	// Write your code here
	if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
	return ;
	}
	// 1st pass:
	// Live to die : if (cnt < 2) setTo 2/TO_DIE（依然>=1）
	// Dead to live: if (cnt == 3) setTo -1/REBORN（依然<=0）
	int n = board.length, m = board[0].length;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int state = board[i][j];
	int livingCount = getLivingNeighborsCount(board, i, j, n, m);
	if (state == 1) {
	if (livingCount < 2 || livingCount > 3) {
	board[i][j] = TO_DIE;
	}
	} else {
	if (livingCount == 3) {
	board[i][j] = REBORN;
	}
	}
	}
	}
	// 2nd pass:
	// turn 2/ TO_DIE into 0
	// turn -1/ REBORN into 1
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int state = board[i][j];
	if (state == TO_DIE) {
	board[i][j] = 0;
	} else if (state == REBORN) {
	board[i][j] = 1;
	}
	}
	}
	}
	private final int TO_DIE = 2;
	private final int REBORN = -1;
	private final int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
	private final int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
	private int getLivingNeighborsCount(int[][] board, int i, int j, int n, int m) {
	int counter = 0;
	for (int k = 0; k < 8; k++) {
	int x = dx[k] + i;
	int y = dy[k] + j;
	if (!isValid(x, y, n, m)) {
	continue;
	}
	if (board[x][y] >= 1) {
	counter++;
	}
	}
	return counter;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return i >= 0 && i < n && j >= 0 && j < m;
	}
	}

view raw LintCode 1301 · Game of Life.java hosted with ❤ by GitHub

LintCode 1704 · Range Sum of BST.java

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	// Approach #1 - More Readable recursion
	public class Solution {
	/**
	* @param root: the root node
	* @param L: an integer
	* @param R: an integer
	* @return: the sum
	*/
	public int rangeSumBST(TreeNode root, int L, int R) {
	// write your code here.
	if (root == null || L > R) {
	return 0;
	}
	int ans = (L <= root.val && root.val <= R) ? root.val : 0;
	if (root.val > L) {
	ans += rangeSumBST(root.left, L, R);
	}
	if (root.val < R) {
	ans += rangeSumBST(root.right, L, R);
	}
	return ans;
	}
	}
	// Approach #2 - Tail recursion
	// public class Solution {
	// /**
	// * @param root: the root node
	// * @param L: an integer
	// * @param R: an integer
	// * @return: the sum
	// */
	// public int rangeSumBST(TreeNode root, int L, int R) {
	// // write your code here.
	// if (root == null || L > R) {
	// return 0;
	// }
	// return rangeSumBST(root.left, L, R) +
	// rangeSumBST(root.right, L, R) +
	// ((root.val >= L && root.val <= R) ? root.val : 0);
	// }
	// }

view raw LintCode 1704 · Range Sum of BST.java hosted with ❤ by GitHub

LintCode 912 · Best Meeting Point.java

	// Approach #1 - T O(n * m) + O(p) + O(p log p), with p being # of 1 points.
	public class Solution {
	/**
	* @param grid: a 2D grid
	* @return: the minimize travel distance
	*/
	public int minTotalDistance(int[][] grid) {
	// handle corner cases
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	// step #0 scan the grid (n * m). And fill the lists.
	List<Integer> listX = new LinkedList<>();
	List<Integer> listY = new LinkedList<>();
	int n = grid.length, m = grid[0].length;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (grid[i][j] == 1) {
	listX.add(i);
	listY.add(j);
	}
	}
	}
	// get the ManhattanDistances and sum them up.
	int minTotal = 0;
	minTotal += getMinimumManhattanDistance(listX);
	// System.out.println(minTotal);
	Collections.sort(listY);
	minTotal += getMinimumManhattanDistance(listY);
	// System.out.println(minTotal);
	return minTotal;
	}
	private int getMinimumManhattanDistance(List<Integer> list) {
	int sum = 0;
	int begin = 0, end = list.size() - 1;
	while (begin < end) {
	sum += list.get(end) - list.get(begin);
	begin++;
	end--;
	}
	return sum;
	}
	}
	// Approach #2 - T O(n * m) + O(p) + O(p log p), with p being # of 1 points.
	// public class Solution {
	// /**
	// * @param grid: a 2D grid
	// * @return: the minimize travel distance
	// */
	// public int minTotalDistance(int[][] grid) {
	// // handle corner cases
	// if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	// return 0;
	// }
	// // step #0 scan the grid (n * m).
	// List<Integer> listX = new LinkedList<>();
	// List<Integer> listY = new LinkedList<>();
	// for (int i = 0; i < grid.length; i++) {
	// for (int j = 0; j < grid[0].length; j++) {
	// if (grid[i][j] == 1) {
	// listX.add(i);
	// listY.add(j);
	// }
	// }
	// }
	// // step #1 find horizontal Median. O(n log n)
	// int minTotal = 0;
	// minTotal += getManhattanDistance(listX);
	// // step #2 find vertical Median. O(n log n)
	// Collections.sort(listY);
	// minTotal += getManhattanDistance(listY);
	// return minTotal;
	// }
	// private int getManhattanDistance(List<Integer> list) {
	// int sum = 0;
	// int median = getMedian(list);
	// for (int x : list) {
	// sum += Math.abs(x - median);
	// }
	// return sum;
	// }
	// private int getMedian(List<Integer> list) {
	// int size = list.size();
	// if (size % 2 == 1) {
	// return list.get(size / 2);
	// } else {
	// return (list.get(size / 2 - 1) + list.get(size / 2)) / 2;
	// }
	// }
	// }

view raw LintCode 912 · Best Meeting Point.java hosted with ❤ by GitHub

LintCode 1283 · Reverse String.java

	// Approach #1 - Converging Two Pointers - O(n) T O(n) S
	public class Solution {
	/**
	* @param s: a string
	* @return: return a string
	*/
	public String reverseString(String s) {
	// handle corner cases
	if (s == null || s.length() < 2) {
	return s;
	}
	int i = 0, j = s.length() - 1;
	char[] reversing = s.toCharArray();
	while(i < j) {
	char tmp = reversing[i];
	reversing[i] = reversing[j];
	reversing[j] = tmp;
	i++;
	j--;
	}
	return new String(reversing);
	}
	}

view raw LintCode 1283 · Reverse String.java hosted with ❤ by GitHub

LintCode 1794 · Count Duplicates.java

	// Approach #1 - O(n) T O(n) S - Just count,
	// and be careful it's not about 1st appearance, it's about the 2nd appear...; it's testing the data structure: list, map.
	public class Solution {
	/**
	* @param nums: a integer array
	* @return: return an integer denoting the number of non-unique(duplicate) values
	*/
	public List<Integer> countduplicates(List<Integer> nums) {
	// write your code here
	List<Integer> duplicates = new LinkedList<>();
	if (nums == null || nums.size() < 2) {
	return duplicates;
	}
	Map<Integer, Boolean> sawNumbers2AddedYet = new HashMap<>();
	for (int num : nums) {
	if (sawNumbers2AddedYet.containsKey(num)) {
	if (!sawNumbers2AddedYet.get(num)) {
	duplicates.add(num);
	sawNumbers2AddedYet.put(num, true);
	}
	} else {
	sawNumbers2AddedYet.put(num, false);
	}
	}
	return duplicates;
	}
	}

view raw LintCode 1794 · Count Duplicates.java hosted with ❤ by GitHub

LintCode 38 · Search a 2D Matrix II.java

	// Approach #1 - Divide-and-conquer algorithm - O(n + m) T O(1) S - just search from the corner. Every step you can easily eliminate a row and/ or col.
	public class Solution {
	/**
	* @param matrix: A list of lists of integers
	* @param target: An integer you want to search in matrix
	* @return: An integer indicate the total occurrence of target in the given matrix
	*/
	public int searchMatrix(int[][] matrix, int target) {
	// write your code here
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return 0;
	}
	int n = matrix.length, m = matrix[0].length;
	int i = n - 1, j = 0, counter = 0;
	while (isValid(i, j, n, m)) {
	if (matrix[i][j] == target) {
	counter++;
	i--;
	j++;
	} else if (matrix[i][j] < target) {
	j++;
	} else {
	i--;
	}
	}
	return counter;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return (i >= 0 && i < n && j >= 0 && j < m);
	}
	}
	// Approach #2 - O(n * log m) T O(1) S - you can binary search each row. Double the typing.
	public class Solution {
	/**
	* @param matrix: A list of lists of integers
	* @param target: An integer you want to search in matrix
	* @return: An integer indicate the total occurrence of target in the given matrix
	*/
	public int searchMatrix(int[][] matrix, int target) {
	// write your code here
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return 0;
	}
	int counter = 0;
	for (int[] row : matrix) {
	counter += binarySearch(row, target);
	}
	return counter;
	}
	private int binarySearch(int[] row, int target) {
	int n = row.length;
	int begin = 0, end = n - 1;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (row[mid] == target) {
	return 1;
	} else if (row[mid] < target) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	if (row[begin] == target) {
	return 1;
	}
	if (row[end] == target) {
	return 1;
	}
	return 0;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return (i >= 0 && i < n && j >= 0 && j < m);
	}
	}

view raw LintCode 38 · Search a 2D Matrix II.java hosted with ❤ by GitHub

LintCode 683 · Word Break III.java

	// Approach #1 DFS + MEMO O(n * 3) T O(n * n) S
	// Approach #2 DP O(n * 3) T O(n * n) S
	// With maxLength optimization it can be O(n * maxLength * maxLength).
	// Approach #1 DFS + MEMO O(n * 3) T O(n * n) S
	public class Solution {
	/**
	* @param s: A string
	* @param dict: A set of word
	* @return: the number of possible sentences.
	*/
	public int wordBreak3(String s, Set<String> dict) {
	// handle corner cases
	if (dict == null || dict.size() == 0 || s == null || s.length() == 0) {
	return 0;
	}
	// make it case insensitive
	Set<String> words = new HashSet<>();
	for (String word : dict) {
	words.add(word.toLowerCase());
	maxLength = Math.max(maxLength, word.length());
	}
	// prep for MEMO
	dp = new int[s.length()][s.length()];
	for (int[] row : dp) {
	Arrays.fill(row, -1);
	}
	// perform the MEMO search
	return dfs(words, s.toLowerCase(), 0, s.length() - 1);
	}
	private int maxLength;
	private int[][] dp;
	private int dfs(final Set<String> words, final String originalString, final int left, final int right) {
	if (left > right) {
	return 1;
	}
	if (dp[left][right] != -1) {
	return dp[left][right];
	}
	int counter = 0;
	for (int i = left; i <= right && (i - left < maxLength); i++) {
	String word = originalString.substring(left, i + 1);
	if (!words.contains(word)) {
	continue;
	}
	counter += dfs(words, originalString, i + 1, right);
	}
	dp[left][right] = counter;
	return dp[left][right];
	}
	}
	// Approach #2 DP O(n * 3) T O(n * n) S
	public class Solution {
	/**
	* @param s: A string
	* @param dict: A set of word
	* @return: the number of possible sentences.
	*/
	public int wordBreak3(String s, Set<String> dict) {
	// handle corner cases
	if (dict == null || dict.size() == 0 || s == null || s.length() == 0) {
	return 0;
	}
	// make words case insensitive
	Set<String> words = new HashSet<>();
	int maxLength = 0;
	for (String word : dict) {
	words.add(word.toLowerCase());
	maxLength = Math.max(maxLength, word.length());
	}
	// dp initialize
	String string2Break = s.toLowerCase();
	int stringLength = string2Break.length();
	int[][] dp = new int[stringLength][stringLength];
	for (int i = 0; i < stringLength; i++) {
	for (int j = i; j < stringLength && (j - i < maxLength); j++) {
	String sub = string2Break.substring(i, j + 1);
	if (words.contains(sub)) {
	dp[i][j] = 1;
	}
	}
	}
	// dp fill the rest with dual-for loop
	for (int i = 0; i < stringLength; i++) {
	for (int j = i; j < stringLength; j++) {
	for (int k = i; k < j; k++) {
	dp[i][j] += dp[i][k] * dp[k + 1][j];
	}
	}
	}
	return dp[0][stringLength - 1];
	}
	}

view raw LintCode 683 · Word Break III.java hosted with ❤ by GitHub

LintCode 927 · Reverse Words in a String II.java

	public class Solution {
	/**
	* @param str: a string
	* @return: return a string
	*/
	public char[] reverseWords(char[] str) {
	// handle corner cases
	if (str == null || str.length < 2) {
	return str;
	}
	// step #1 flip the whole thing
	reverse(str, 0, str.length - 1);
	// System.out.println(Arrays.toString(str));
	// step #2 flip each word
	int left = 0;
	for (int right = 0; right < str.length - 1; right++) {
	if (str[right] != ' ') {
	continue;
	}
	reverse(str, left, right - 1);
	left = right + 1;
	}
	// one last reverse
	reverse(str, left, str.length - 1);
	return str;
	}
	private void reverse(char[] str, int left, int right) {
	while (left < right) {
	char tmp = str[left];
	str[left] = str[right];
	str[right] = tmp;
	left++;
	right--;
	}
	}
	}

view raw LintCode 927 · Reverse Words in a String II.java hosted with ❤ by GitHub

LintCode 1186 · Encode and Decode TinyURL.java

	public class Solution {
	List<String> list = new ArrayList<>();
	public String encode(String longUrl) {
	// Encodes a URL to a shortened URL.
	list.add(longUrl);
	return String.valueOf(list.size() - 1);
	}
	public String decode(String shortUrl) {
	// Decodes a shortened URL to its original URL.
	int id = Integer.valueOf(shortUrl);
	return list.get(id);
	}
	}
	// Your Codec object will be instantiated and called as such:
	// Codec codec = new Codec();
	// codec.decode(codec.encode(url));

view raw LintCode 1186 · Encode and Decode TinyURL.java hosted with ❤ by GitHub

LintCode 165 · Merge Two Sorted Lists.java

	/**
	* Definition for ListNode
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param l1: ListNode l1 is the head of the linked list
	* @param l2: ListNode l2 is the head of the linked list
	* @return: ListNode head of linked list
	*/
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	// handle corner cases
	if (l1 == null) {
	return l2;
	}
	if (l2 == null) {
	return l1;
	}
	ListNode pre = new ListNode(-1);
	ListNode node = pre;
	ListNode left = l1;
	ListNode right = l2;
	while (left != null && right != null) {
	if (left.val < right.val) {
	node.next = new ListNode(left.val);
	left = left.next;
	} else {
	node.next = new ListNode(right.val);
	right = right.next;
	}
	node = node.next;
	}
	while (left != null) {
	node.next = new ListNode(left.val);
	left = left.next;
	node = node.next;
	}
	while (right != null) {
	node.next = new ListNode(right.val);
	right = right.next;
	node = node.next;
	}
	return pre.next;
	}
	}

view raw LintCode 165 · Merge Two Sorted Lists.java hosted with ❤ by GitHub

LintCode 167 · Add Two Numbers.java

	/**
	* Definition for ListNode
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	// Approach #1 - T O(max(n, m)) - S O(1)
	public class Solution {
	/**
	* @param l1: the first list
	* @param l2: the second list
	* @return: the sum list of l1 and l2
	*/
	public ListNode addLists(ListNode l1, ListNode l2) {
	// handle corner cases
	if (l1 == null) {
	return l2;
	}
	if (l2 == null) {
	return l1;
	}
	// create a new list for result
	ListNode dummyPreHead = new ListNode(-1);
	ListNode tail = dummyPreHead;
	ListNode left = l1;
	ListNode right = l2;
	int carry = 0;
	while (left != null || right != null) {
	int number = ((left == null) ? 0 : left.val) + ((right == null) ? 0 : right.val) + carry;
	carry = (number > 9) ? 1 : 0;
	number = (number > 9) ? number - 10 : number;
	tail.next = new ListNode(number);
	tail = tail.next;
	if (left != null) {
	left = left.next;
	}
	if (right != null) {
	right = right.next;
	}
	}
	if (carry > 0) {
	tail.next = new ListNode(carry);
	}
	return dummyPreHead.next;
	}
	}

view raw LintCode 167 · Add Two Numbers.java hosted with ❤ by GitHub

LintCode 1046 · Prime Number of Set Bits in Binary Representation.java

	public class Solution {
	/**
	* @param L: an integer
	* @param R: an integer
	* @return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation
	*/
	public int countPrimeSetBits(int L, int R) {
	// handle corner cases
	int counter = 0;
	for (int i = L; i <= R; i++) {
	if (isPrimeSetBits(i)) {
	counter++;
	}
	}
	return counter;
	}
	private boolean isPrimeSetBits(int i) {
	int counter = 0;
	while (i > 0) {
	if (i % 2 == 1) {
	counter++;
	}
	i /= 2;
	}
	return isPrime(counter);
	}
	private boolean isPrime(int number) {
	if (number < 2) {
	return false;
	}
	for (int i = 2; i <= Math.sqrt(number); i++) {
	if (number % i == 0) {
	return false;
	}
	}
	return true;
	}
	}

view raw LintCode 1046 · Prime Number of Set Bits in Binary Representation.java hosted with ❤ by GitHub

Algoexpert Run-Length Encoding.java

	import java.util.*;
	class Program {
	// O(n) T | O(n) S
	public String runLengthEncoding(String string) {
	// handle corner cases
	if (string == null || string.length() == 0) {
	return string;
	}
	int currentRunLength = 1;
	StringBuilder encodedStringCharacters = new StringBuilder();
	for (int i = 1; i < string.length(); i++) {
	char previousChar = string.charAt(i - 1);
	char currentChar = string.charAt(i);
	if ((currentChar != previousChar) || (currentRunLength == 9)) {
	encodedStringCharacters.append(currentRunLength);
	encodedStringCharacters.append(previousChar);
	currentRunLength = 1;
	} else {
	currentRunLength++;
	}
	}
	// handle the last run
	if (currentRunLength > 0) {
	encodedStringCharacters.append(currentRunLength);
	encodedStringCharacters.append(string.charAt(string.length() - 1));
	}
	return encodedStringCharacters.toString();
	}
	}

view raw Algoexpert Run-Length Encoding.java hosted with ❤ by GitHub

Algoexpert Caesar Cipher Encryptor.java

	import java.util.*;
	class Program {
	// O(n) T | O(n) S
	public static String caesarCypherEncryptor(String str, int key) {
	// handle corner cases
	if (str == null || str.length() == 0) {
	return str;
	}
	int n = str.length();
	char[] encoded = new char[n];
	for (int i = 0; i < n; i++) {
	encoded[i] = getNewChar(str.charAt(i), key);
	}
	return new String(encoded);
	}
	private static char getNewChar(char oldChar, int key) {
	return (char)('a' + (oldChar - 'a' + key) % 26);
	}
	}

view raw Algoexpert Caesar%20Cipher%20Encryptor.java hosted with ❤ by GitHub

Algoexpert Palindrome Check.java

	import java.util.*;
	class Program {
	public static boolean isPalindrome(String str) {
	// handle corner cases
	if (str == null || str.length() < 2) {
	return true;
	}
	int begin = 0; int end = str.length() - 1;
	while (begin < end) {
	if (str.charAt(begin) != str.charAt(end)) {
	return false;
	}
	begin++;
	end--;
	}
	return true;
	}
	}

view raw Algoexpert Palindrome%20Check.java hosted with ❤ by GitHub

LintCode 1449 · Loud and Rich.java

	// Approach #1 - DFS + Memoization - Build Graph w/ adjacency list.
	// T O(n + edges + n * edges) = T O(n * edges), given that n is the length of quiet (# of people). h is the parent edges of the graph (worse case h = n).
	public class Solution {
	/**
	* @param richer: the richer array
	* @param quiet: the quiet array
	* @return: the answer
	*/
	public int[] loudAndRich(int[][] richer, int[] quiet) {
	// handle corner cases
	if (quiet == null || quiet.length == 0) {
	return quiet;
	}
	if (richer == null || richer.length == 0) {
	answer = new int[quiet.length];
	for (int i = 0; i < quiet.length; i++) {
	answer[i] = i;
	}
	return answer;
	}
	int n = quiet.length;
	answer = new int[n];
	Arrays.fill(answer, -1);
	// step #1 build graph - with adjacency list. T O(n + edges)
	List<Integer>[] graph = new ArrayList[n];
	// fill the list. T O(n)
	for (int person = 0; person < n; person++) {
	graph[person] = new ArrayList<>();
	}
	// add the edges into the adjacency list. T O(edges)
	for (int[] edge : richer) {
	graph[edge[1]].add(edge[0]);
	}
	// Step #2 foreach person, find the (dfs direct/ in-direct) smallest quiet. T O(n * h)
	for (int person = 0; person < n; person++) {
	answer[person] = dfs(graph, quiet, person);
	}
	return answer;
	}
	private int[] answer;
	private int dfs(List<Integer>[] graph, int[] quiet, int person) {
	// find the (dfs direct/ in-direct) max quiet
	if (answer[person] != -1) {
	return answer[person];
	}
	// init with himself
	answer[person] = person;
	// search for quieter (from the richer persons)
	for (int richer : graph[person]) { // foreach richer, find quieter
	int quietest = dfs(graph, quiet, richer);
	if (quiet[quietest] < quiet[answer[person]]) {
	answer[person] = quietest;
	}
	}
	return answer[person];
	}
	}

view raw LintCode 1449 · Loud and Rich.java hosted with ❤ by GitHub

LintCode 1652 · Interval XOR II.java

	/**
	* Definition of Interval:
	* public classs Interval {
	* int start, end;
	* Interval(int start, int end) {
	* this.start = start;
	* this.end = end;
	* }
	* }
	*/
	public class Solution {
	/**
	* @param A:
	* @param query:
	* @return: nothing
	*/
	public List<Integer> intervalXOR(int[] A, List<Interval> query) {
	// handle corner cases
	if (A == null || A.length == 0 || query == null || query.size() == 0) {
	return new LinkedList<>();
	}
	int n = A.length;
	int m = query.size();
	List<Integer> result = new LinkedList<>();
	for (Interval interval : query) {
	int tmp = 0;
	for (int i = interval.start; i <= interval.start + interval.end - 1; i++) {
	tmp ^= A[i];
	}
	result.add(tmp);
	}
	return result;
	}
	}

view raw LintCode 1652 · Interval XOR II.java hosted with ❤ by GitHub

LintCode 797 · Reach a Number.java

	// Approach #1 - Math - T O(sqrt(target))
	public class Solution {
	/**
	* @param target: the destination
	* @return: the minimum number of steps
	*/
	public int reachNumber(int target) {
	// Write your code here
	target = Math.abs(target);
	int position = 0, step = 1;
	while (position < target) {
	position += step;
	step++;
	}
	step--;
	if (position == target) {
	return step;
	}
	// remember if the diff is even, it is achievable with same steps, just flip the 2, or 4, or other something that you already have.
	int diff = position - target;
	if (diff % 2 == 0) {
	return step;
	} else if ((step + 1) % 2 == 1) {
	// if the diff is odd, and the next step is odd, then the next step will make it even.
	return step + 1;
	} else {
	// if the diff is odd, and the next step is even, then the next of the next will make it even.
	return step + 2;
	}
	}
	}

view raw LintCode 797 · Reach a Number.java hosted with ❤ by GitHub

LintCode 242 · Convert Binary Tree to Linked Lists by Depth.java

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	// Approach #1 - T O(#OfNodes) - do a BFS w/ levels. Then just simulate and fill the LinkedList.
	public class Solution {
	/**
	* @param root the root of binary tree
	* @return a lists of linked list
	*/
	public List<ListNode> binaryTreeToLists(TreeNode root) {
	// handle corner cases
	if (root == null) {
	return new LinkedList<>();
	}
	result = new LinkedList<>();
	bfs(root);
	return result;
	}
	private List<ListNode> result;
	private void bfs(TreeNode root) {
	Queue<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	ListNode dummyPreHead = new ListNode(-1);
	ListNode current = dummyPreHead;
	while (size-- > 0) {
	TreeNode node = queue.poll();
	current.next = new ListNode(node.val);
	current = current.next;
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	result.add(dummyPreHead.next);
	}
	}
	}

view raw LintCode 242 · Convert Binary Tree to Linked Lists by Depth.java hosted with ❤ by GitHub

LintCode 69 · Binary Tree Level Order Traversal.java

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	// Approach #1 - BFS - T O(#OfNodes).
	public class Solution {
	/**
	* @param root: A Tree
	* @return: Level order a list of lists of integer
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
	// write your code here
	if (root == null) {
	return new LinkedList<>();
	}
	result = new LinkedList<>();
	bfs(root);
	return result;
	}
	private List<List<Integer>> result;
	private void bfs(TreeNode root) {
	Queue<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	result.add(new LinkedList<>());
	while (size-- > 0) {
	TreeNode node = queue.poll();
	result.get(result.size() - 1).add(node.val);
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	}
	}
	}

view raw LintCode 69 · Binary Tree Level Order Traversal.java hosted with ❤ by GitHub

LintCode 1691 · Best Time to Buy and Sell Stock V.java

	// Appproach #1 - T O(n log n).
	public class Solution {
	/**
	* @param A: the array A
	* @return: return the maximum profit
	*/
	public int getAns(int[] A) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int profit = 0;
	Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1 - o2);
	for (int a : A) {
	if (!pq.isEmpty() && pq.peek() < a) {
	// greedy: found business proposition
	profit += a - pq.poll();
	// correctness: in case you will find even better business proposition
	pq.offer(a);
	}
	pq.offer(a);
	}
	return profit;
	}
	}

view raw LintCode 1691 · Best Time to Buy and Sell Stock V.java hosted with ❤ by GitHub

LintCode 363 · Trapping Rain Water.java

	public class Solution {
	/**
	* @param heights: a list of integers
	* @return: a integer
	*/
	public int trapRainWater(int[] heights) {
	// handle corner cases
	if (heights == null || heights.length == 0) {
	return 0;
	}
	int n = heights.length;
	// 1st pass - prefixMax - O(n)
	int[] prefixMax = new int[n];
	prefixMax[0] = 0;
	for (int i = 1; i < n; i++) {
	prefixMax[i] = Math.max(heights[i - 1], prefixMax[i - 1]);
	}
	// 2nd pass - postfixMax - O(n)
	int[] postfixMax = new int[n];
	postfixMax[n - 1] = 0;
	for (int i = n - 2; i >= 0; i--) {
	postfixMax[i] = Math.max(heights[i + 1], postfixMax[i + 1]);
	}
	// 3rd pass - get each water and sum - O(n)
	int sum = 0;
	for (int i = 1; i < n - 1; i++) {
	int currentHeight = heights[i];
	int boundaryMin = Math.min(prefixMax[i], postfixMax[i]);
	sum += (boundaryMin > currentHeight) ? boundaryMin - currentHeight : 0;
	}
	return sum;
	}
	}

view raw LintCode 363 · Trapping Rain Water.java hosted with ❤ by GitHub

LintCode 1479 · Can Reach The Endpoint.java

	public class Solution {
	/**
	* @param map: the map
	* @return: can you reach the endpoint
	*/
	public boolean reachEndpoint(int[][] map) {
	// Write your code here
	if (map == null || map.length == 0 || map[0] == null || map[0].length == 0 ) {
	return true;
	}
	if (map[0][0] == 0) {
	return false;
	}
	return bfs(map);
	}
	int[] dx = new int[]{1, -1, 0, 0};
	int[] dy = new int[]{0, 0, 1, -1};
	private boolean bfs(int[][] map) {
	int n = map.length;
	int m = map[0].length;
	Queue<Integer> queue = new ArrayDeque<>();
	Set<Integer> visited = new HashSet<>();
	queue.add(0);
	visited.add(0);
	while (!queue.isEmpty()) {
	int codedIndex = queue.poll();
	int i = codedIndex / m;
	int j = codedIndex % m;
	for (int k = 0; k < 4; k++) {
	int x = i + dx[k];
	int y = j + dy[k];
	if (!isValid(x, y, n, m) || map[x][y] == 0 || visited.contains(x * m + y)) {
	continue;
	}
	if (map[x][y] == 9) {
	return true;
	}
	queue.add(x * m + y);
	visited.add(x * m + y);
	}
	}
	return true;
	}
	private boolean isValid(int i,int j,int n,int m) {
	return i >= 0 && i < n && j >= 0 && j < m;
	}
	}

view raw LintCode 1479 · Can Reach The Endpoint.java hosted with ❤ by GitHub

LintCode 1678 · Train compartment problem.java

	public class Solution {
	/**
	* @param arr: the arr
	* @return: the number of train carriages in this transfer station with the largest number of train carriages
	*/
	public int trainCompartmentProblem(int[] arr) {
	// Handle corner cases
	if (arr == null || arr.length == 0) {
	return 0;
	}
	int maxCount = 0;
	int n = arr.length, j = 0;
	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i < n; i++) {
	if (i + 1 == arr[j]) {
	// bypass directly???
	j++;
	} else {
	stack.push(i + 1);
	maxCount = Math.max(maxCount, stack.size());
	}
	while (j < n && !stack.isEmpty() && stack.peek() == arr[j]) {
	stack.pop();
	j++;
	}
	}
	if (j == n) {
	// done all pop
	return maxCount;
	} else {
	return -1;
	}
	}
	}

view raw LintCode 1678 · Train compartment problem.java hosted with ❤ by GitHub

LintCode 1673 · Save Money.java

	public class Solution {
	/**
	* @param operations: the type of information
	* @param name: the name of user
	* @param w: the money need to save or take
	* @return: output the remaining money of the user.if the operation is illegal,output -1
	*/
	public int[] getAns(int[] operations, String[] names, int[] amounts) {
	// Write your code here
	if (operations == null || operations.length == 0) {
	return new int[0];
	}
	int n = operations.length;
	int[] result = new int[n];
	Map<String, Integer> name2Balance = new HashMap<>();
	for (int i = 0; i < n; i++) {
	int op = operations[i];
	String name = names[i];
	int amount = amounts[i];
	if (op == 0) {
	int balance = name2Balance.getOrDefault(name, 0) + amount;
	name2Balance.put(name, balance);
	result[i] = balance;
	} else {
	if (name2Balance.getOrDefault(name, 0) >= amount) {
	int balance = name2Balance.getOrDefault(name, 0) - amount;
	name2Balance.put(name, balance);
	result[i] = balance;
	} else {
	result[i] = -1;
	}
	}
	}
	return result;
	}
	}

view raw LintCode 1673 · Save Money.java hosted with ❤ by GitHub

LintCode 1883 · Top K Frequently Mentioned Keywords.java

	public class Solution {
	/**
	* @param K: a integer
	* @param keywords: a list of string
	* @param reviews: a list of string
	* @return: return the top k keywords list
	*/
	public List<String> TopkKeywords(int K, String[] keywords, String[] reviews) {
	// write your code here
	if (keywords == null) {
	return new ArrayList<>(0);
	}
	Set<String> keys = new HashSet<>();
	for (String keyword : keywords) {
	keys.add(keyword);
	}
	Map<String, Integer> word2Counts = new HashMap<>();
	Map<String, Integer> keys2Counts = new HashMap<>();
	for (String review : reviews) {
	Set<String> tmpSet = new HashSet<>();
	String[] words = review.split("\\P{Alpha}+");
	for (String word : words) {
	tmpSet.add(word.toLowerCase());
	}
	// for each review, if a keyword is hit, ++
	for (String uniqueWord : tmpSet) {
	if (keys.contains(uniqueWord)) {
	keys2Counts.put(uniqueWord, keys2Counts.getOrDefault(uniqueWord, 0) + 1);
	}
	}
	}
	Queue<KeyWithFrequency> queue = new PriorityQueue<>(K, new MyComparator());
	for (Map.Entry<String, Integer> entry : keys2Counts.entrySet()) {
	queue.add(new KeyWithFrequency(entry.getKey(), entry.getValue()));
	if (queue.size() > K) {
	queue.poll();
	}
	}
	// System.out.println("queue=" + queue);
	LinkedList<String> result = new LinkedList<>();
	while(!queue.isEmpty()) {
	result.addFirst(queue.poll().key);
	}
	return result;
	}
	private class MyComparator implements Comparator<KeyWithFrequency>{
	@Override
	public int compare(KeyWithFrequency o1, KeyWithFrequency o2) {
	int result = o1.frequency - o2.frequency;
	if (result == 0) {
	result = o2.key.compareTo(o1.key);
	}
	return result;
	}
	}
	private class KeyWithFrequency {
	String key;
	int frequency;
	KeyWithFrequency(String key, int frequency) {
	this.key = key;
	this.frequency = frequency;
	}
	@Override
	public String toString() {
	return "key=" + key + "; frequency=" + frequency;
	}
	}
	}

view raw LintCode 1883 · Top K Frequently Mentioned Keywords.java hosted with ❤ by GitHub

LintCode 40 · Implement Queue by Two Stacks.java

	public class MyQueue {
	Stack<Integer> stack = new Stack<>();
	Stack<Integer> stack2 = new Stack<>();
	public MyQueue() {
	// do intialization if necessary
	stack = new Stack<>();
	stack2 = new Stack<>();
	}
	/*
	* @param element: An integer
	* @return: nothing
	*/
	public void push(int element) {
	// write your code here
	stack.push(element);
	}
	/*
	* @return: An integer
	*/
	public int pop() {
	// write your code here
	if (stack2.isEmpty()) {
	while (!stack.isEmpty()) {
	stack2.push(stack.pop());
	}
	}
	return stack2.pop();
	}
	/*
	* @return: An integer
	*/
	public int top() {
	// write your code here
	if (stack2.isEmpty()) {
	while (!stack.isEmpty()) {
	stack2.push(stack.pop());
	}
	}
	return stack2.peek();
	}
	}

view raw LintCode 40 · Implement Queue by Two Stacks.java hosted with ❤ by GitHub

LintCode 229 · Stack Sorting.java

	public class Solution {
	/*
	* @param stk: an integer stack
	* @return: void
	*/
	public void stackSorting(Stack<Integer> stk) {
	// write your code here
	if (stk == null || stk.size() < 2) {
	return ;
	}
	// fill the holderStack in reverse order
	Stack<Integer> holderStack = new Stack<>();
	while (!stk.isEmpty()) {
	Integer latest = stk.pop();
	if (holderStack.isEmpty()) {
	holderStack.push(latest);
	} else {
	while (!holderStack.isEmpty() && holderStack.peek() < latest) {
	stk.push(holderStack.pop());
	}
	holderStack.push(latest);
	}
	}
	// fill the original stack in regular order.
	while (!holderStack.isEmpty()) {
	stk.push(holderStack.pop());
	}
	return ;
	}
	}

view raw LintCode 229 · Stack Sorting.java hosted with ❤ by GitHub

LintCode 608 · Two Sum II - Input array is sorted.java

	public class Solution {
	/**
	* @param nums: an array of Integer
	* @param target: target = nums[index1] + nums[index2]
	* @return: [index1 + 1, index2 + 1] (index1 < index2)
	*/
	public int[] twoSum(int[] nums, int target) {
	// two pointers, O(n)/ Opposite Direction Two Pointers/ Alternatively you can solve with Hash Table.
	// handle corner cases
	if (nums == null || nums.length < 2) {
	return new int[]{0, 0};
	}
	// two pointers
	int left = 0, right = nums.length - 1;
	while (left + 1 < right) {
	if (nums[left] + nums[right] == target) {
	return new int[]{left + 1, right + 1};
	}
	if (nums[left] + nums[right] < target) {
	left++;
	} else {
	right--;
	}
	}
	if (nums[left] + nums[right] == target) {
	return new int[]{left + 1, right + 1};
	}
	// the returns are NOT 0-based。
	return new int[]{0, 0};
	}
	}

view raw LintCode 608 · Two Sum II - Input array is sorted.java hosted with ❤ by GitHub

LintCode 1676 · Skip Stones.java

	public class Solution {
	/**
	* @param n: The total number of stones.
	* @param m: The total number of stones you can remove.
	* @param target: The distance from the end to the starting point.
	* @param d: The array that the distance from the i rock to the starting point is d[i].
	* @return: Return the maximum value of the shortest jump distance.
	*/
	public int getDistance(int n, int m, int target, List<Integer> d) {
	// handle corner cases
	if (m >= n) {
	return target;
	}
	// binarySearch on the result space.
	int begin = 0, end = target;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (numberOfRemovals(n, mid, target, d) <= m) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	// System.out.println("begin=" + begin + "; end=" + end);
	if (numberOfRemovals(n, end, target, d) <= m) {
	return end;
	}
	if (numberOfRemovals(n, begin, target, d) <= m) {
	return begin;
	}
	return target;
	}
	private int numberOfRemovals(int n, int minDistanceRequired, int target, List<Integer> D) {
	// calculating the numberOfRemovals, if we were to achieve that minDistanceRequired.
	int removalCounter = 0;
	int lastLocation = 0;
	for (int currentLocation : D) {
	if (currentLocation - lastLocation < minDistanceRequired) {
	removalCounter++;
	} else {
	lastLocation = currentLocation;
	}
	}
	// System.out.println("removalCounter=" + removalCounter + "; minDistanceRequired=" + minDistanceRequired);
	return removalCounter;
	}
	}

view raw LintCode 1676 · Skip Stones.java hosted with ❤ by GitHub

LintCode 1671 · play game.java

	public class Solution {
	/**
	* @param A:
	* @return: nothing
	*/
	public long playGames(int[] A) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return 0;
	}
	long begin = 0, end = A.length;
	// find the begin and end for the binarySearch
	for (int a : A) {
	if (begin < a) {
	begin = a;
	}
	end += a;
	}
	// binarySearch on the solution space
	while (begin + 1 < end) {
	long mid = (end - begin) / 2 + begin;
	if (isValid(A, mid)) {
	end = mid;
	} else {
	begin = mid;
	}
	}
	if (isValid(A, begin)) {
	return begin;
	} else {
	return end;
	}
	}
	private boolean isValid(int[] A, long games) {
	return getRoundsOfJudges(A, games) >= games;
	}
	private long getRoundsOfJudges(int[] A, long games) {
	long sum = 0;
	for (int a : A) {
	sum += (games - a);
	}
	return sum;
	}
	}

view raw LintCode 1671 · play game.java hosted with ❤ by GitHub

LintCode 61 · Search for a Range.java

	public class Solution {
	/**
	* @param A: an integer sorted array
	* @param target: an integer to be inserted
	* @return: a list of length 2, [index1, index2]
	*/
	public int[] searchRange(int[] A, int target) {
	// binarySearch O(n logn) + fan out search O(n)
	// handle corner cases
	Arrays.sort(A);
	// perform a routine binarySearch
	int result = binarySearch(A, target);
	if (result == -1) {
	// if target not existed, return [-1, -1] as instructed.
	return new int[]{-1, -1};
	} else {
	// if target is located, fan out and search for the left& right limit.
	int begin = result;
	int end = result;
	while (begin > 0) {
	if (A[begin - 1] != target) {
	break;
	}
	begin--;
	}
	while (end < A.length - 1) {
	if (A[end + 1] != target) {
	break;
	}
	end++;
	}
	return new int[]{begin, end};
	}
	}
	private int binarySearch(int[] A, int target) {
	if (A == null || A.length == 0) {
	return -1;
	}
	int n = A.length;
	int begin = 0, end = A.length - 1;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (A[mid] == target) {
	return mid;
	}
	if (A[mid] < target) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	if (A[begin] == target) {
	return begin;
	}
	if (A[end] == target) {
	return end;
	}
	return -1;
	}
	}

view raw LintCode 61 · Search for a Range.java hosted with ❤ by GitHub

LintCode 62 · Search in Rotated Sorted Array.java

	public class Solution {
	/**
	* @param A: an integer rotated sorted array
	* @param target: an integer to be searched
	* @return: an integer
	*/
	public int search(int[] nums, int target) {
	// Binary Search, regardless of smoke screen, Time: O(n logn), just draw a picture, be patient and turn on your analytical mode.
	// handle corner cases.
	if (nums == null || nums.length == 0) {
	return -1;
	}
	int n = nums.length;
	int begin = 0, end = n - 1;
	while (begin + 1 < end) {
	// avoid integer overflow
	int mid = (end - begin) / 2 + begin;
	// found the answer
	if (nums[mid] == target) {
	return mid;
	}
	// avoid duplications
	if (nums[mid] == nums[begin]) {
	begin++;
	continue;
	}
	// Case-by-case discussion
	if (nums[mid] > nums[begin]) {
	if (target >= nums[begin] && target <= nums[mid]) {
	end = mid;
	} else {
	begin = mid;
	}
	} else {
	if (target >= nums[mid] && target <= nums[end]) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	}
	// handle the rest.
	if (nums[begin] == target) {
	return begin;
	}
	if (nums[end] == target) {
	return end;
	}
	return -1;
	}
	}

view raw LintCode 62 · Search in Rotated Sorted Array.java hosted with ❤ by GitHub

LintCode 461 · Kth Smallest Numbers in Unsorted Array.java

	public class Solution {
	/**
	* @param k: An integer
	* @param nums: An integer array
	* @return: kth smallest element
	*/
	public int kthSmallest(int k, int[] nums) {
	// write your code here
	if (nums == null) {
	return -1;
	}
	return quickSelect(k, nums, 0, nums.length - 1);
	}
	private int quickSelect(int k, int[] nums, int begin, int end) {
	if (begin == end) {
	return nums[begin];
	}
	int left = begin, right = end;
	int pivot = nums[(left + right) / 2];
	while (left <= right) {
	while (left <= right && nums[left] < pivot) {
	left++;
	}
	while (left <= right && nums[right] > pivot) {
	right--;
	}
	if (left <= right) {
	int tmp = nums[left];
	nums[left] = nums[right];
	nums[right] = tmp;
	left++;
	right--;
	}
	}
	if (begin + k - 1 <= right) {
	return quickSelect(k, nums, begin, right);
	}
	if (begin + k - 1 >= left) {
	return quickSelect(k - left + begin, nums, left, end);
	}
	return nums[right + 1];
	}
	}

view raw LintCode 461 · Kth Smallest Numbers in Unsorted Array.java hosted with ❤ by GitHub

LintCode 5 · Kth Largest Element.java

	public class Solution {
	/**
	* @param k: An integer
	* @param nums: An array
	* @return: the Kth largest element
	*/
	public int kthLargestElement(int k, int[] nums) {
	// write your code here
	return quickSelect(k, nums, 0, nums.length - 1);
	}
	private int quickSelect(int k, int[] nums, int left, int right) {
	if (left > right) {
	return -1;
	}
	int i = left, j = right;
	int pivot = nums[(left + right) / 2];
	while (i <= j) {
	while (i <= j && nums[i] > pivot) {
	i++;
	}
	while (i <= j && nums[j] < pivot) {
	j--;
	}
	if (i <= j) {
	int tmp = nums[i];
	nums[i] = nums[j];
	nums[j] = tmp;
	i++;
	j--;
	}
	}
	if (left + k - 1 <= j) {
	return quickSelect(k, nums, left, j);
	}
	if (left + k - 1 >= i) {
	return quickSelect(k + left - i, nums, i, right);
	}
	return nums[j + 1];
	}
	}

view raw LintCode 5 · Kth Largest Element.java hosted with ❤ by GitHub

LintCode 143 · Sort Colors II.java

	public class Solution {
	/**
	* @param colors: A list of integer
	* @param k: An integer
	* @return: nothing
	*/
	public void sortColors2(int[] colors, int k) {
	// write your code here
	if (colors == null || colors.length == 0) {
	return;
	}
	// first round, count the occurance of each color.
	int n = colors.length;
	int[] counts = new int[k + 1];
	for (int color : colors) {
	counts[color]++;
	}
	// 2nd round, fill the colors array according to the calculated occurances.
	int i = 0;
	for (int color = 1; color <= k; color++) {
	int count = counts[color];
	while (count-- > 0) {
	colors[i++] = color;
	}
	}
	return;
	}
	}

view raw LintCode 143 · Sort Colors II.java hosted with ❤ by GitHub

LintCode 751 · John's business.java

	public class Solution {
	/**
	* @param A: The prices [i]
	* @param k:
	* @return: The ans array
	*/
	public int[] business(int[] A, int k) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return new int[0];
	}
	int n = A.length;
	int[] profit = new int[n];
	Queue<Integer> minHeap = new PriorityQueue<>();
	// init the first 0..k-1 prices into the minHeap
	for (int i = 0; i < k; i++) {
	minHeap.add(A[i]);
	}
	// core logic - keep sliding the window,
	// update the minHeap by removing the left most outdated, and adding the right most new addition.
	// then always take the current price, the A[i], and subtract that to the minHeap.peek(),
	// otherwise if it's not profitable, just use zero. indicating that you don't take that deal for a loss.
	for (int i = 0; i < n; i++) {
	if (i - k - 1 >= 0) {
	minHeap.remove(A[i - k - 1]);
	}
	if (i + k < n) {
	minHeap.add(A[i + k]);
	}
	profit[i] = Math.max(0, A[i] - minHeap.peek());
	// System.out.println("minHeap = " + minHeap);
	}
	return profit;
	}
	}

view raw LintCode 751 · John's business.java hosted with ❤ by GitHub

LeetCode 760 · Binary Tree Right Side View.java

	// There is a little improvement from regular BFS,
	// This question needs to read the last one, and the queue does not support it.
	// But ArrayDeque itself does support it, so you only need to use the Deque interface, and you can play as you like.
	public class Solution {
	/**
	* @param root: the root of the given tree
	* @return: the values of the nodes you can see ordered from top to bottom
	*/
	public List<Integer> rightSideView(TreeNode root) {
	// write your code here
	if (root == null) {
	return new LinkedList<>();
	}
	return bfs(root);
	}
	private List<Integer> bfs(TreeNode root) {
	List<Integer> list = new LinkedList<>();
	Deque<TreeNode> queue = new ArrayDeque<>();
	queue.add(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	list.add(queue.peekLast().val);
	while (size-- > 0) {
	TreeNode node = queue.poll();
	if (node.left != null) {
	queue.add(node.left);
	}
	if (node.right != null) {
	queue.add(node.right);
	}
	}
	}
	return list;
	}
	}

view raw LeetCode 760 · Binary Tree Right Side View.java hosted with ❤ by GitHub

LintCode 1563 · Shortest path to the destination.java

	// Pure BFS:
	// The algorithm is mainly to master the variant with the number of layers.
	// There are some error-prone points in implementation:
	// Note 1: When not found, return -1;
	// Note 2: When found, return to level directly.
	// Note 3: The starting value of level is 1. It means that the first step has already gone, and the queue I just entered, that is to say, all the queues have passed.
	// Note 4: When you encounter something that works, here is a trick to omit the visited array: Mark the road directly on the original image and it will not work.
	public class Solution {
	/**
	* @param targetMap:
	* @return: nothing
	*/
	public int shortestPath(int[][] grid) {
	// write your code here
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	int m = grid.length, n = grid[0].length;
	int level = bfsWithLevel(0, 0, grid, m, n);
	return level;
	}
	private int bfsWithLevel(int i, int j, int[][] grid, int m, int n) {
	Queue<int[]> queue = new ArrayDeque<>();
	// Set<int[]> visited = new HashSet<>();
	queue.add(new int[]{i, j});
	// visited.add(new int[]{i, j});
	int[] dx = new int[]{1, -1, 0, 0};
	int[] dy = new int[]{0, 0, 1, -1};
	int level = 1;
	while (!queue.isEmpty()) {
	int size = queue.size();
	while (size-- > 0) {
	int[] coordinate = queue.poll();
	for (int k = 0; k < 4; k++) {
	int x = coordinate[0] + dx[k];
	int y = coordinate[1] + dy[k];
	if (!isValid(x, y, m, n) || grid[x][y] == 1) {
	continue;
	}
	if (grid[x][y] == 2) {
	return level;
	}
	queue.add(new int[]{x, y});
	grid[x][y] = 1;
	// visited.add(new int[]{x, y});
	}
	}
	level++;
	}
	return -1;
	}
	private boolean isValid(int x, int y, int m, int n) {
	return (x >= 0 && x < m && y >= 0 && y < n);
	}
	}

view raw LintCode 1563 · Shortest path to the destination.java hosted with ❤ by GitHub

LintCode 1360 · Symmetric Tree.java

Binary Search:
note that: "Check the left.left equal to the right.right."

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	// Approach #1 - Recursion - T O(#OfNodes).
	public class Solution {
	/**
	* @param root: root of the given tree
	* @return: whether it is a mirror of itself
	*/
	public boolean isSymmetric(TreeNode root) {
	// Write your code here
	if (root == null) {
	return true;
	}
	return isSymmetric(root.left, root.right);
	}
	private boolean isSymmetric(TreeNode left, TreeNode right) {
	if (left == null && right == null) {
	return true;
	}
	if (left == null || right == null) {
	return false;
	}
	return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
	}
	}

view raw 1360 · Symmetric Tree.java hosted with ❤ by GitHub

LintCode 437 · Copy Books.java

Binary Search:
note that: "This one is tricky."

	public class Solution {
	/**
	* @param pages: an array of integers
	* @param k: An integer
	* @return: an integer
	*/
	public int copyBooks(int[] pages, int k) {
	// write your code here
	if (pages == null || pages.length == 0) {
	return 0;
	}
	int begin = 0;
	int end = getSum(pages);
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (k >= getNumberOfCopiers(pages, mid)) {
	end = mid;
	} else {
	begin = mid;
	}
	}
	if (k >= getNumberOfCopiers(pages, begin)) {
	return begin;
	}
	if (k >= getNumberOfCopiers(pages, end)) {
	return end;
	}
	return Integer.MAX_VALUE;
	}
	private int getNumberOfCopiers(int[] pages, int timeLimit) {
	int copiers = 0;
	int alreadyCopied = timeLimit;
	for (int page : pages) {
	if (page > timeLimit) {
	return Integer.MAX_VALUE;
	}
	if (alreadyCopied + page > timeLimit) {
	copiers++;
	alreadyCopied = 0;
	}
	alreadyCopied += page;
	}
	return copiers;
	}
	private int getSum(int[] pages) {
	int sum = 0;
	for (int page : pages) {
	sum += page;
	}
	return sum;
	}
	}

view raw 437 · Copy Books.java hosted with ❤ by GitHub

LintCode 127 · Topological Sorting.java

Topological Sorting:
note that: "BFS with indegree."

	/**
	* Definition for Directed graph.
	* class DirectedGraphNode {
	* int label;
	* List<DirectedGraphNode> neighbors;
	* DirectedGraphNode(int x) {
	* label = x;
	* neighbors = new ArrayList<DirectedGraphNode>();
	* }
	* }
	*/
	public class Solution {
	/**
	* @param graph: A list of Directed graph node
	* @return: Any topological order for the given graph.
	*/
	public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
	// write your code here
	ArrayList<DirectedGraphNode> orders = new ArrayList<>();
	if (graph == null || graph.size() == 0) {
	return orders;
	}
	Map<DirectedGraphNode, Integer> indegree = new HashMap<>();
	for (DirectedGraphNode node : graph) {
	for (DirectedGraphNode neighbor : node.neighbors) {
	if (indegree.containsKey(neighbor)) {
	indegree.put(neighbor, indegree.get(neighbor) + 1);
	} else {
	indegree.put(neighbor, 1);
	}
	}
	}
	Queue<DirectedGraphNode> queue = new ArrayDeque<>();
	for (DirectedGraphNode node : graph) {
	if (!indegree.containsKey(node)) {
	queue.add(node);
	}
	}
	while (!queue.isEmpty()) {
	DirectedGraphNode node = queue.poll();
	orders.add(node);
	for (DirectedGraphNode neighbor : node.neighbors) {
	if (indegree.containsKey(neighbor)) {
	indegree.put(neighbor, indegree.get(neighbor) - 1);
	if (indegree.get(neighbor) == 0) {
	queue.add(neighbor);
	indegree.remove(neighbor);
	}
	}
	}
	}
	return orders;
	}
	}

view raw 127 · Topological Sorting.java hosted with ❤ by GitHub

LintCode 801 · Backpack X.java

Backpack with Value array:
note that: "And the number of these merchandises can be considered as infinite."
function:
dp[i] |= dp[i - nums[j] * k]; (when you take that ith item)
or
dp[i] = false; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the money you have
	* @return: the minimum money you have to give
	*/
	public int backPackX(int target) {
	// write your code here
	if (target == 0) {
	return 0;
	}
	boolean[] dp = new boolean[target + 1];
	// dp: init
	dp[0] = true;
	// dp: states + functions
	int maximum = Integer.MIN_VALUE;
	int[] nums = new int[]{150, 250, 350};
	for (int i = 1; i <= target; i++) {
	for (int j = 0; j <= 2; j++) {
	int k = 1;
	while (i >= nums[j] * k) {
	dp[i] |= dp[i - nums[j] * k];
	k++;
	}
	}
	if (dp[i]) {
	maximum = i;
	}
	}
	// dp: answer
	return target - maximum;
	}
	}

view raw 801 · Backpack X.java hosted with ❤ by GitHub

LintCode 799 · Backpack VIII.java

Backpack with Value array:
note that: "Each item has different values and quantities."
function:
dp[i][j] |= dp[i - 1][j - A[i - 1] * k]; (when you take that ith item)
or
dp[i][j] = dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the value from 1 - n
	* @param value: the value of coins
	* @param amount: the number of coins
	* @return: how many different value
	*/
	public int backPackVIII(int m, int[] A, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	boolean[][] dp = new boolean[n+1][m+1];
	dp[0][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = false;
	}
	// dp: functions
	int counter = 0;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	for (int k = 1; k <= K[i - 1] && j - A[i - 1] * k >= 0; k++) {
	dp[i][j] |= dp[i - 1][j - A[i - 1] * k];
	}
	if (i == n && dp[i][j]) {
	counter++;
	}
	}
	}
	// for (int i = 0; i <= n; i++) {
	// System.out.println("Arrays.toString(dp[i]) = " + Arrays.toString(dp[i]));
	// }
	// dp: answer
	return counter;
	}
	}

view raw 799 · Backpack VIII.java hosted with ❤ by GitHub

LintCode 798 · Backpack VII.java

Backpack with Value array:
note that: "Given the weight, price and quantity constrains."
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]); (when you take that ith item)
or
dp[i][j] = dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the money of you
	* @param prices: the price of rice[i]
	* @param weight: the weight of rice[i]
	* @param amounts: the amount of rice[i]
	* @return: the maximum weight
	*/
	public int backPackVII(int m, int[] A, int[] V, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]);
	k++;
	if (K[i - 1] < k) {
	break;
	}
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 798 · Backpack VII.java hosted with ❤ by GitHub

LintCode 564 · Combination Sum IV.java

Backpack with Value array:
note that: "A number in the array can be used multiple times in the combination."
function:
dp[i] += dp[i - nums[j - 1]]; (when you take that ith item)
or
dp[i] = 0; (when you don't take that ith item)

	public class Solution {
	/**
	* @param nums: an integer array and all positive numbers, no duplicates
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackVI(int[] nums, int target) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int n = nums.length;
	int[] dp = new int[target + 1];
	// dp: init
	dp[0] = 1;
	// dp: states + functions
	for (int i = 1; i <= target; i++) {
	for (int j = 1; j <= n; j++) {
	if (i >= nums[j - 1]) {
	dp[i] += dp[i - nums[j - 1]];
	}
	}
	}
	// dp: answer
	return dp[target];
	}
	}

view raw 564 · Combination Sum IV.java hosted with ❤ by GitHub

LintCode 563 · Backpack V.java

Backpack with Value array:
note that: "Each item may only be used once"
function:
dp[i][j] += dp[i - 1][j - nums[i - 1]]; (when you take that ith item)
or
dp[i][j] += dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param nums: an integer array and all positive numbers
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackV(int[] nums, int target) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int n = nums.length;
	int[][] dp = new int[n + 1][target + 1];
	// dp: init
	dp[0][0] = 1;
	for (int j = 1; j <= target; j++) {
	dp[0][j] = 0;
	}
	// dp: states + functions
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 1;
	for (int j = 1; j <= target; j++) {
	dp[i][j] = dp[i - 1][j];
	if (nums[i-1] <= j) {
	dp[i][j] += dp[i - 1][j - nums[i - 1]];
	}
	}
	}
	// dp: answer
	return dp[n][target];
	}
	}

view raw 563 · Backpack V.java hosted with ❤ by GitHub

LintCode 562 · Backpack IV.java

Backpack with Value array:
note that: "Each item may be chosen unlimited number of times"
function:
dp[i][j] += dp[i - 1][j - A[i - 1] * k]; (when you take that ith item)
or
dp[i][j] += dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param nums: an integer array and all positive numbers, no duplicates
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackIV(int[] A, int m) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 1;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 1;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] += dp[i - 1][j - A[i - 1] * k];
	k++;
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 562 · Backpack IV.java hosted with ❤ by GitHub

LintCode 440 · Backpack III.java

Backpack with Value array:
note that now you can take k times, or "infinite times"
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]); (when you take that ith item)
or
dp[i][j] += dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param A: an integer array
	* @param V: an integer array
	* @param m: An integer
	* @return: an array
	*/
	public int backPackIII(int[] A, int[] V, int m) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]);
	k++;
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 440 · Backpack III.java hosted with ❤ by GitHub

LintCode 125 · Backpack II.java

Backpack with Value array:
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1]] + V[i - 1], dp[i - 1][j]); (when you take that ith item)
or
dp[i][j] += dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param m: An integer m denotes the size of a backpack
	* @param A: Given n items with size A[i]
	* @param V: Given n items with value V[i]
	* @return: The maximum value
	*/
	public int backPackII(int m, int[] A, int[] V) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	if (j - A[i-1] >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1]] + V[i - 1], dp[i - 1][j]);
	} else {
	dp[i][j] += dp[i - 1][j];
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 125 · Backpack II.java hosted with ❤ by GitHub

LintCode 92 · Backpack

Classic backpack:
function:
dp[i][j] = dp[i - 1][j];
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i-1]] (if it can fit that ith item, aka: j - A[i-1] >= 0)

	public class Solution {
	/**
	* @param m: An integer m denotes the size of a backpack
	* @param A: Given n items with size A[i]
	* @return: The maximum size
	*/
	public int backPack(int m, int[] A) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	boolean[][] dp = new boolean[n+1][m+1];
	dp[0][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = false;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	if (j - A[i-1] >= 0 && dp[i - 1][j - A[i-1]]) {
	dp[i][j] = true;
	} else {
	dp[i][j] = dp[i - 1][j];
	}
	if (i == n && dp[i][j]) {
	maximumJ = j;
	}
	}
	}
	// dp: answer
	return maximumJ;
	}
	}

view raw LintCode92 · Backpack.java hosted with ❤ by GitHub

LintCode 76 · Longest Increasing Subsequence

The dp: function is
dp[i] = Math.max(dp[i], dp[l] + 1);

	public class Solution {
	/**
	* @param nums: An integer array
	* @return: The length of LIS (longest increasing subsequence)
	*/
	public int longestIncreasingSubsequence(int[] nums) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int max = 0;
	int n = nums.length;
	int[] dp = new int[n];
	Arrays.fill(dp, 1);
	for (int i = 0; i < n; i++) {
	for (int l = 0; l < i; l++) {
	if (nums[i] > nums[l]) {
	dp[i] = Math.max(dp[i], dp[l] + 1);
	}
	}
	max = Math.max(max, dp[i]);
	}
	System.out.println("Arrays.toString(dp) = " + Arrays.toString(dp));
	return max;
	}
	}

view raw LintCode76 · Longest Increasing Subsequence.java hosted with ❤ by GitHub