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
要知道如何避免乘法overflow
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
用heap再做一遍
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 九章算法

FacebookTwitterGoogle+Share

Leetcode: Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

 

public ArrayList<String> anagrams(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        HashMap<String,ArrayList<String>> records = new HashMap<String, ArrayList<String>>();
        ArrayList<String> output = new ArrayList<String>();
        for(int i = 0; i<strs.length;i++){
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sorted = new String(charArr);
            if(records.containsKey(sorted)){
                records.get(sorted).add(strs[i]);
            }else{
                ArrayList<String> strings = new ArrayList<String>();
                strings.add(strs[i]);
                records.put(sorted, strings);
            }
        }
        
        for(ArrayList<String> currArr : records.values()){
            if(currArr.size()>1){
                output.addAll(currArr);
            }    
        }    
        return output;
    }