Leetcode: Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

 

public boolean isNumber(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()==0){
            return false;
        }
        //continuous zeros from beginning since begin is true
        int cont = 0;
        boolean hasDot = false;
        boolean begin = false;
        boolean end = false;
        boolean hasSign = false;
        boolean hasE = false;
        
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            
            
            if(c=='+'||c=='-'){
                if(hasSign||begin){
                    return false;
                }else{
                    hasSign = true;
                }
                continue;
            }
            
            if(c=='e'){
                if(hasE||!begin){
                    return false;
                }else{
                    return isInteger(s.substring(i+1));
                    //return true;
                }
            }
            
            if(c=='.'){
                if(hasDot||end){
                    return false;
                }else{
                    hasDot = true;
                }
                continue;
            }
            
            if(c==' '){
                if((begin ||hasSign) && !end){
                    end=true;
                }
                continue;
            }
            
            if(!(isDigit(s,i))){
                return false;
            }else{
                if(end){
                    return false;
                }else{
                    if(!begin){
                        begin=true;
                    }
                }
            }
            
            
        }
        
        if(!begin){
            return false;
        }
        return true;
        
        
    }
    public boolean isInteger(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return ifAllSpace(s.substring(1));
        }
        int zeors = 0;
        for(int i=0;i<s.length();i++){
            if(i==0){
                if(c=='+'||c=='-'){
                    return isIntegerWithoutSign(s.substring(i+1));
                }else
                if(!isDigit(s,i)){
                    return false;
                }
            }else
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i+1));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean ifAllSpace(String s){
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!=' '){
                return false;
            }
        }
        return true;
    }
    
    public boolean isIntegerWithoutSign(String s){
        if(s==null||s.length()==0){
            return false;
        }
        if(s.length()==1 && isDigit(s,0)){
            return true;
        }
        char c = s.charAt(0);
        if(c=='0'){
            return false;
        }
        for(int i=0;i<s.length();i++){
            if(!isDigit(s,i)){
                if(c==' '){
                    return ifAllSpace(s.substring(i));
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean isDigit(String s,int index){
        char c = s.charAt(index);
        if(c<(int)'0' || c>(int)'9'){
            return false;
        }
        return true;
    }
FacebookTwitterGoogle+Share

Leetcode: Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

 

public int[] twoSum(int[] numbers, int target) {
        //use hashmap to store <val,index> pairs of all the numbers
        //in this algorithm, we assume all the numbers are different
        //and we need to add one to the index as the final output as requried by this question
        int[] output = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<numbers.length;i++){
            map.put(numbers[i],i);
        }
        for(int i=0;i<numbers.length;i++){
            int val = target-numbers[i];
            if(map.containsKey(val)){
                int index = map.get(val);
                if(index!=i){
                    if(i<index){
                        output[0] = i+1;
                        output[1] = index+1;
                    }else{
                        output[0] = index+1;
                        output[1] = i+1;
                    }
                    return output;
                }
            }
        }
        return output;
    }

The time complexity is O(N). Since we only need constant time for each HashMap search operation.

Leetcode: Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

public void setZeroes(int[][] matrix) {
        //to achieve constant space, we need to use the space of the first row and first col
        //to store information
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return;
        }
        
        //1. determine if the first row needs to be set zero because of itself
        //which means are there any zeros in the first row
        boolean zeroFirstRow = false;
        for(int i=0;i<matrix[0].length;i++){
            if(matrix[0][i]==0){
                zeroFirstRow=true;
                break;
            }
        }
        //2. determine if the first col needs to be set zero because of itself
        //which means are there any zeros in the first col
        boolean zeroFirstCol = false;
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][0]==0){
                zeroFirstCol=true;
                break;
            }
        }
        //3. then we can use the first row and first col to store the information of 
        //the rest elements
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //4. set the matrix to zero according to the information stored in the first row and first col
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[0][j]==0||matrix[i][0]==0){
                    matrix[i][j]=0;
                }    
            }
        }
        //set the first row
        if(zeroFirstRow){
            for(int i=0;i<matrix[0].length;i++){
                matrix[0][i]=0;
            }
        }
        //set the first col
        if(zeroFirstCol){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0]=0;
            }
        }
    }

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 九章算法

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;
    }

Leetcode: Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

 

public int removeElement(int[] A, int elem) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A==null||A.length==0){
            return 0;
        }
        int end = A.length-1;
        int index = 0;
        while(index<=end){
            if(A[index]==elem){
                swap(A, index, end);
                end--;
            }else{
                index++;
            }            
        }
        return end+1;
    }
    
    public void swap(int[] A, int i, int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

Leetcode: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 //non-recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode runner = head;
        ListNode newHead = null;
        ListNode tail = null;
        while(runner!=null && runner.next!=null){
            ListNode runnernext = runner.next;
            ListNode runnernextnext = runnernext.next;
            if(tail!=null){
                tail.next = runnernext;                
            }else{
                newHead=runnernext;
            }
            runnernext.next = runner;
            runner.next = null;
            tail=runner;
            runner = runnernextnext;
        }
        if(runner!=null){
            tail.next = runner;
        }
        return newHead;
    }
//recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode headnext =head.next;
        ListNode headnextnext=headnext.next;
        head.next = swapPairs(headnextnext);
        headnext.next=head;
        return headnext;
    }

Leetcode: Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

 

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for(int i=1;i<=n;i++){
            nums.add(i);
        }
        k--;//k originally starts from 1
        int index=0;
        while(k!=0){
            int frac = frac(n-index-1);
            int targetNumIndex = k/frac+index;
            int targetNum = nums.remove(targetNumIndex);
            nums.add(index,targetNum);
            index++;
            k=k%frac;
        }
        String output = "";
        for(Integer num:nums){
            output+=num;
        }
        return output;
    }
    
    public int frac(int n){
        int sum = 1;
        for(int i=1;i<=n;i++){
            sum*=i;
        }
        return sum;
    }

 

Leetcode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

 

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

1. One Queue Solution — Better

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    //one queue
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root != null) {
        q.offer(root);
    }
    while (!q.isEmpty()) {
        ArrayList<Integer> levelNodes = new ArrayList<>();
        int size = q.size(); //this is the # of nodes in current level
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();
            levelNodes.add(curr.val);
            if (curr.left != null) {
                q.offer(curr.left);
            }
            if (curr.right != null) {
                q.offer(curr.right);
            }
        }
        result.add(levelNodes);
    }
    return result;
}

2. Two Queues Solution — Easier to Understand

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> output= new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return output;
        }
        ArrayList<TreeNode> current = new ArrayList<TreeNode>();
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        current.add(root);
        while(current.size()!=0){
            children = new ArrayList<TreeNode>();
            ArrayList<Integer> levelNodes= new ArrayList<Integer>();
            for(TreeNode t : current){
                levelNodes.add(t.val);
                if(t.left!=null){
                    children.add(t.left);
                }
                if(t.right!=null){
                    children.add(t.right);
                }
            }
            output.add(levelNodes);
            current = children;
        }
        return output;
    }