# k Sum II

#### k Sum II

Given n unique integers, number k (1<=k<=n)  and target. Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k=2, target=5, [1,4] and [2,3] are possible solutions

Solutions: DFS

Time Complexity?

```    public ArrayList < ArrayList < Integer >> kSumII(int A[], int k, int target) {
ArrayList < ArrayList < Integer >> result = new ArrayList < > ();
if (A == null) {
return result;
}
kSumIIHelper(new ArrayList < Integer > (), 0, A, k, target, result);
return result;
}

public void kSumIIHelper(ArrayList < Integer > curr, int index, int A[], int k,
int target, ArrayList < ArrayList < Integer >> result) {
if (curr.size() == k) {
if (target == 0) {
result.add(new ArrayList < > (curr));
}
return;
}
for (int i = index; i < A.length; i++) {
curr.add(A[i]);
kSumIIHelper(curr, i + 1, A, k, target - A[i], result);
curr.remove(curr.size() - 1);
}
}```

Share

# Linked List Cycle I & II

#### Linked List Cycle I 问有没有环

Given a linked list, determine if it has a cycle in it.

Challenge

Follow up:
Can you solve it without using extra space?

Example

Given -21->10->4->5, tail connects to node index 1, return true

```public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}```

#### Linked List Cycle II 问环的入口

Given a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

Example

Given -21->10->4->5, tail connects to node index 1，返回10

Challenge

Follow up:
Can you solve it without using extra space?

Solution: 当在找环的过程中slow和fast相遇后，第一题直接return true就行了，这题需要找到环的入口。从slow.next到环的入口的距离等于从head到环的入口的距离。

```public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null && slow != fast) {
slow = slow.next;
fast = fast.next.next;
}
if (fast == null || fast.next == null) {
return null;
}
ListNode runner = head;
while (runner != slow.next) {
runner = runner.next;
slow = slow.next;
}
return runner;
}```

# Reorder List

Reorder List

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Solution: O(n) time and O(1) extra space

Steps:

1. find middle of linked list

2. reverse from mid.next to end as right list

3. Merge left list(from head to mid) and right list(end to mid.next)

```public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode mid = findMiddle(head);
ListNode right = mid.next;
right = reverse(right);
mid.next = null;
ListNode left = head;
ListNode dummyHead = new ListNode(0);
ListNode runner = dummyHead;
int count = 0;
while (left != null && right != null) {
if (count % 2 == 0) {
runner.next = left;
left = left.next;
} else {
runner.next = right;
right = right.next;
}
count++;
runner = runner.next;
}
if (left != null) {
runner.next = left;
} else {
runner.next = right;
}
head = dummyHead.next;
}

public ListNode reverse(ListNode head) {
ListNode runner = head;
ListNode prev = null;
while (runner != null) {
ListNode tmp = runner.next;
runner.next = prev;
prev = runner;
runner = tmp;
}
return prev;
}

public ListNode findMiddle(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}```

# Copy List with Random Pointer

#### Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Challenge

Could you solve it with O(1) space?

## Solution1: O(n) space, using HashMap put save (node, new node) pairs

```public RandomListNode copyRandomList(RandomListNode head) {
//O(n) space version, using hashMap
if (head == null) {
return null;
}
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode runner = head;
RandomListNode headCopy = new RandomListNode(head.label);
map.put(head, headCopy);
RandomListNode copyRunner = headCopy;
//deep copy nodes and next pointers
while (runner.next != null) {
copyRunner.next = new RandomListNode(runner.next.label);
runner = runner.next;
copyRunner = copyRunner.next;
map.put(runner, copyRunner);
}
//deep copy random pointers
for (RandomListNode node : map.keySet()) {
map.get(node).random = map.get(node.random);
}
return headCopy;
}```

Solution2: O(1) space

# K Sum

Lintcode Online Judge

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given `[1,2,3,4]`, k = `2`, target = `5`.

There are `2` solutions: `[1,4]` and `[2,3]`.

Return `2`.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

```public int kSum(int A[], int k, int target) {
if (A == null) {
return 0;
}
//kSum[i][j][t]:find j integers from first i integers in the array
//how many solutions there are to sum up to t
int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
for (int i = 0; i <= A.length; i++) {
kSum[i][0][0] = 1; //select nothing which is also a solution
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k; j++) {
for (int t = 1; t <= target; t++) {
kSum[i][j][t] = kSum[i - 1][j][t];
if (t >= A[i - 1]) {
kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
}
}
}
}
return kSum[A.length][k][target];
}```

# Minimum Adjustment Cost

Online Judge

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of `|A[i]-B[i]|`

Example

Given `[1,4,2,3]` and target = `1`, one of the solutions is `[2,3,2,3]`, the adjustment cost is `2` and it’s minimal.

Return `2`.

Note

You can assume each number in the array is a positive integer and not greater than `100`.

Solution: DP

state: f[i][v] 前i个数，第i个数调整为v，满足相邻两数<=target，所需要的最小代价

function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)

Time Complexity: O(m*n*t) m: array size n:最大可能的数 t:required range

Space Complexity: O(m*n)

```public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
if (A == null || A.size() <= 1) {
return 0;
}
int maxInt = 100;//assume each number in the array is a positive integer and not greater than 100
int[][] minCost = new int[A.size() + 1][maxInt + 1];
for (int i = 0; i <= maxInt; i++) {
minCost[0][i] = 0;
}
for (int i = 1; i <= A.size(); i++) {
for (int j = 0; j <= maxInt; j++) {
int costAiToJ = Math.abs(A.get(i - 1) - j);
int min = Integer.MAX_VALUE;
//|k-j|<=target
//max(0, j-target) <= k <= min(target+j, maxInt)
for (int k = Math.max(0, j - target); k <= Math.min(target + j, maxInt); k++) {
if (minCost[i - 1][k] + costAiToJ < min) {
min = minCost[i - 1][k] + costAiToJ;
}
}
minCost[i][j] = min;
}
}
int finalMinCost = minCost[A.size()][0];
for (int i = 0; i <= maxInt; i++) {
if (minCost[A.size()][i] < finalMinCost) {
finalMinCost = minCost[A.size()][i];
}
}
return finalMinCost;
}```

# Backpack I&II

## – different sizes same price, ask maximum solution with fixed bag size

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Example

If we have `4` items with size `[2, 3, 5, 7]`, the backpack size is 11, we can select `[2, 3, 5]`, so that the max size we can fill this backpack is `10`. If the backpack size is `12`. we can select `[2, 3, 7]` so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

### Solution 1: DP – O(nm) time and O(nm) memory

state: f[i][j] = “前i”个数，取出一些组成和为<=j的最大值

function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况

o f[i-1][j] //不取a[i]的情况

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i][j] = backPack[i - 1][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i][j] > max) {
max = backPack[i][j];
}
}
}
return max;
}```

### Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i % 2][j] = backPack[(i - 1) % 2][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i % 2][j] > max) {
max = backPack[i % 2][j];
}
}
}
return max;
}```

### Solution 3: dp

f[i][j] = 前i个item能不能正好组成j

f[i][j] = f[i-1][j-a[i]] //取a[i]

f[i-1][j] //不取a[i]

return max j which f[i][j] == true

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
boolean[][] backPack = new boolean[A.length + 1][m + 1];
backPack[0][0] = true;
for (int i = 1; i <= A.length; i++) {
backPack[i][0] = true;
}
for (int j = 1; j <= m; j++) {
backPack[0][j] = false;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
backPack[i][j] = backPack[i - 1][j];
if (j >= A[i - 1]) {
backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
}
if (backPack[i][j]) {
max = j;
}
}
}
return max;
}```

## – different size and price, ask for maximum value with fixed bag size

### Solution 1. O(m*n) time, O(m*n) space

f[i][j]:maximum value with first i items in A with a m sized bag

f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况

= f[i-1][j] //不取a[i]的情况

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i][j] = maxValue[i - 1][j];
if (j >= A[i - 1]) {
maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length][m];
}```

### Solution 2: O(m*n) time, O(m) space

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
if (j >= A[i - 1]) {
maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length % 2][m];
}```

# Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example

For `"ABCD"` and `"EDCA"`, the LCS is `"A"` (or `"D"`, `"C"`), return `1`.

For `"ABCD"` and `"EACB"`, the LCS is `"AC"`, return `2`.

Clarification

What’s the definition of Longest Common Subsequence?

Solution: Dynamic Programming

```public int longestCommonSubsequence(String A, String B) {
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}
int[][] lcs = new int[A.length()][B.length()];
for (int i = 0; i < A.length(); i++) {
for (int j = 0; j < B.length(); j++) {
if (i == 0 || j == 0) {
lcs[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
} else {
if (A.charAt(i) == B.charAt(j)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
}
return lcs[A.length() - 1][B.length() - 1];
}```

## Leetcode/Lintcode Online Judge Solutions

### Featured

Cheat Sheet

Question D F Data Structure Algorithms Comments
3Sum 3 5 array two pointers
3Sum Closest 3 1 array two pointers
4Sum 3 2 array
Add Binary 2 4 string two pointers
math
Add Two Numbers 3 4 linked list two pointers
math
Anagrams 3 4 string
hashtable
BackPack I 4 4 backpack dp
BackPack II 4 4 backpack dp
Balanced Binary Tree 1 2 tree dfs
Best Time to Buy and Sell Stock 2 1 array dp
Best Time to Buy and Sell Stock II 3 1 array greedy
Best Time to Buy and Sell Stock III 4 1 array dp
Binary Search Tree Iterator 5 2 BST Iterator
Binary Tree Inorder Traversal 4 3 tree
hashtable
recursion
morris
stack
Binary Tree Level Order Traversal 3 4 tree bfs
Binary Tree Level Order Traversal II 3 1 tree bfs
Binary Tree Maximum Path Sum 4 2 tree dfs
Binary Tree Zigzag Level Order Traversal 4 3 queue
tree
bfs
stack
Climbing Stairs 2 5 dp
Clone Graph 4 3 Graph BFS
HashMap
4*
Combination Sum 3 3 array combination DFS
Combination Sum II 4 2 array combination
Combinations 3 4 combination
Construct Binary Tree from Inorder and Postorder Traversal 3 3 array
tree
dfs
Construct Binary Tree from Preorder and Inorder Traversal 3 3 array
tree
dfs
Container With Most Water 3 2 array two pointers
Convert Sorted Array to Binary Search Tree 2 3 tree dfs
Convert Sorted List to Binary Search Tree 4 3 linked list recursion
two pointers
Copy List with Random Pointer 4 2 LinkedList O(1)方法还没做
Count and Say 2 2 string two pointers
Count of Smaller Number I 4 3 array sort+binary search
segment tree
Count of Smaller Number II 5 3 array segment tree 值型线段树
Data Stream Median 5 2 heap min/max heap 10*
new comparator用法
Decode Ways 3 4 string recursion
dp
Distinct Subsequences 4 2 string dp
Divide Two Integers 4 3 binary search
math
Edit Distance 4 3 string dp
First Missing Positive 5 2 array sort
Flatten Binary Tree to Linked List 3 3 tree recursion
stack
Generate Parentheses 3 4 string dfs
Gray Code 4 2 combination
Hash Function 3 1 hash
math

Heapify 3 3 Heap 掌握siftup/siftdown两种方法 知道时间复杂度怎么算的
House Robber 3 2 dp
Implement strStr() 4 5 string two pointers
KMP
rolling hash
Insert Interval 4 5 array
linked list
red black tree
sort
merge
Integer to Roman 3 4 math
Interleaving String 5 2 string recursion
dp
Jump Game 3 2 array
Jump Game II 4 2 array
K Sum 5 2 backpack dp
K Sum II 3 2 DFS 时间复杂度多少？
Largest Rectangle in Histogram 5 2 array stack
Length of Last Word 1 1 string
Letter Combinations of a Phone Number 3 3 string dfs
Linked List Cycle I 3 3 LinkedList fast slow pointers
Linked List Cycle II 4 3 LinkedList fast slow pointers
Longest Common Prefix 2 1 string
Longest Common Subsequence 4 2 2 Strings dp
Longest Common Substring 4 2 2 Strings dp
Longest Consecutive Sequence 4 3 array
Longest Increasing Subsequence 3 3 array dp
Longest Increasing Continuous subsequence I 3 3 array dp
Longest Increasing Continuous subsequence II 4 3 array dp
Longest Palindromic Substring 4 2 string
Longest Substring Without Repeating Characters 3 2 string
hashtable
two pointers
Longest Valid Parentheses 4 1 string dp
Lowest Common Ancestor 4 2 Binary Tree Divide&Conquer
LRU Cache 5 2 Doubly linked list Cache概念

Majority Number I 3 2 抵消的概念
Majority Number II 4 2 抵消的概念
Majority Number III 5 2 抵消的概念
Max Square 3 3 dp
Max Tree 5 1 stack 有空重新做一遍
Maximal Rectangle 5 1 array dp
stack
Maximum Depth of Binary Tree 1 1 tree dfs
Maximum Product Subarray 4 3 Array SubArray
prefix sum
SubArray系列问题

Maximum Subarray I 3 3 array prefix sum
Maximum Subarray II 4 2 array
Maximum Subarray III 5 1 array
Median of Two Sorted Arrays 5 3 array binary search
Merge Intervals 4 5 array
linked list
red black tree
sort
merge
Merge k Sorted Lists 3 4 linked list
heap
sort
two pointers
merge

Merge Sorted Array 2 5 array two pointers
merge
Merge Two Sorted Lists 2 5 linked list sort
two pointers
merge
Min Stack 3 3 Stack
Minimum Adjustment Cost 5 1 array dp
Minimum Depth of Binary Tree 1 1 tree dfs
Minimum Path Sum 3 3 array dp
Minimum Subarray 3 3 subarray prefix sum 掌握前缀和概念
Minimum Window Substring 4 2 string two pointers
Multiply Strings 4 3 string two pointers
math
N Queens 4 3 array dfs
N Queens II 4 3 array dfs
Next Permutation 5 2 array permutation
Palindrome Number 2 2 math
Palindrome Partitioning 3 4 string dfs
Palindrome Partitioning II 4 3 string dp
Partition List 3 3 linked list two pointers
dummy node
Pascal's Triangle 2 1 array
Pascal's Triangle II 2 1 array
Path Sum 1 3 tree dfs
Path Sum II 2 2 tree dfs
Permutation Sequence 5 1 permutation math
Permutations 3 4 array permutation
Permutations II 4 2 array permutation
Plus One 1 2 array math
Populating Next Right Pointers in Each Node 3 3 tree dfs
Populating Next Right Pointers in Each Node II 4 2 tree dfs
Pow(x,n) 3 5 binary search math
Recover Binary Search Tree 4 2 tree dfs
Regular Expression Matching 5 3 string recursion
dp
Rehashing 3 1 Hashing 怎么对负数取模
Remove Duplicates from Sorted Array 1 3 array two pointers
Remove Duplicates from Sorted Array II 2 2 array two pointers
Remove Duplicates from Sorted List 1 3 linked list
Remove Duplicates from Sorted List II 3 3 linked list dummy node
Remove Element 1 4 array two pointers
Remove Nth Node From End of List 2 3 linked list fast slow pointers
Reorder List 4 2 LinkedList findMid/reverse/dummyHead
Restore IP Addresses 3 3 string dfs
Reverse Integer 2 3 math
Reverse Linked List I 2 3 Linked List dummy node 1
Reverse Linked List II 3 2 linked list two pointers
Reverse Nodes in k Group 4 2 linked list recursion
two pointers
Roman to Integer 2 4 math
Rotate Image 4 2 array
Rotate List 3 2 linked list two pointers
Same Tree 1 1 tree dfs
Scramble String 5 2 string recursion
dp
Search a 2D Matrix 3 3 array binary search
Search for a Range 4 3 array binary search
Search in Rotated Sorted Array 4 3 array binary search
Search in Rotated Sorted Array II 5 3 array binary search
Search Insert Position 2 2 array
Search Range in Binary Search Tree 3 3 BST
Set Matrix Zeroes 3 5 array
Simplify Path 3 1 string stack
Sliding Window Maximum 5 2 array deque Deque d = new ArrayDeque<>()，以及pollFirst(), pollLast(), offerFirst, offerLast(), peekFirst(), peekLast()用法以及时间复杂度分析，以及为什么要用deque
Sliding Window Median 5 2 array heap 两个heap维护一个median结构，注意hashHeap在此的运用和时间复杂度关系
Sort List 4 2 List fast slow pointers 涉及到findLinkedListMiddle, mergeLinkedList等基本功
Sort Colors 4 2 array sort
two pointers
Spiral Matrix 4 2 array
Spiral Matrix II 3 2 array
Sqrt(x) 4 4 binary search
String to Integer (atoi) 2 5 string math
Subsets 3 4 array recursion
combination
Subsets II 4 2 array recursion
combination
Substring with Concatenation of All Words 3 1 string two pointers
Sudoku Solver 4 2 array dfs
Sum Root to Leaf Numbers 2 4 tree dfs
Surrounded Regions 4 3 array bfs
dfs
Swap Nodes in Pairs 2 4 linked list
Symmetric Tree 1 2 tree dfs
Text Justification 4 2 string
Topological Sorting 4 3 Graph BFS
indegrees
4*
Trailing Zeros 3 1 math
Trapping Rain Water 4 2 array two pointers
stack
Triangle 3 1 array dp
Two Sum 2 5 array
set
sort
two pointers
Unique Binary Search Trees 3 1 tree dp
Unique Binary Search Trees II 4 1 tree dp
dfs
Unique Paths 2 3 array dp
Unique Paths II 3 3 array dp
Valid Number 2 5 string math
Valid Palindrome 2 5 string two pointers
Valid Parentheses 2 5 string stack
Valid Sudoku 2 2 array
Validate Binary Search Tree 3 5 tree dfs
Wildcard Matching 5 3 string recursion
dp
greedy
FB喜欢
Word Break 4 3 String dp
Word Ladder 3 5 graph bfs
shortest path
Word Ladder II 5 1 graph bfs+dfs 10*
Word Search 3 4 array dfs
ZigZag Conversion 3 1 string

Credits to:
1. All the questions are from Leetcode Online Judge/Lintcode
2. Some of the stats in (Difficulty|Frequency|Data Structure|Algorithms)columns are defined by peking2 in http://leetcode.cloudfoundry.com/
3. Some of the solutions are from 九章算法