Algorithm | Learn for Master - Part 2
  • LeetCode Linked List Cycle (java)

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

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

    Java Solution
     

    [Read More...]
  • LeetCode Ransom Note (Java)

    Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



    Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

    Note:
    You may assume that both strings contain only lowercase letters.

     
    Java Solution

     

    [Read More...]
  • Leetcode Jump Game I & II (Java)

    Jump Game I 

    Given an array of non-negative integers, you are initially positioned at the first index of the array.

    Each element in the array represents your maximum jump length at that position.

    Determine if you are able to reach the last index.

    For example:
    A = [2,3,1,1,4], return true.

    A = [3,2,1,0,4], return false.

     
    Analysis:
    We maintain the max step can be reached so far.  If an index i is larger than the current max step that can be reached, it returns false.
     
    Java Solution:

     
     
    Jump Game II

    Given an array of non-negative integers,

    [Read More...]
  • Leetcode mini parser

    Given a nested list of integers represented as a string, implement a parser to deserialize it.

    Each element is either an integer, or a list — whose elements may also be integers or other lists.

    Note: You may assume that the string is well-formed:

    • String is non-empty.
    • String does not contain white spaces.
    • String contains only digits 0-9, [, – ,, ].

    Example 1:

    Example 2:

     

    Analysis

    Define num to store the current number,

    [Read More...]
  • Leetcode Expression Add Operators (Java)

    Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or *between the digits so they evaluate to the target value.

    Examples:

    Analysis:

    This problem can be solved using DFS algorithm. For example, given the input “123456“, suppose we encounter the last digit “6”, at which we already have the result of solve(“12345“). Then there are three cases:

    solve(“123456”) = solve(“12345”) + 6

    solve(“123456”) = solve(“12345”) – 6

    solve(“123456”) = cal( solve(“12345”) ,

    [Read More...]
  • Leetcode Symmetric Tree

    Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    But the following [1,2,2,null,3,null,3] is not:

    Note:
    Bonus points if you could solve it both recursively and iteratively.

     Analysis
    This problem can be easily solved using a recursive algorithm.  We defined a method with the following signature:
     
    equal(left, right)

    then we recursively call equal(left.left, right.right) and equal(left.right, right.left). 

    The method returns false as long as only one of the two nodes is null,

    [Read More...]
  • Leetcode Remove Linked List Elements

    Remove all elements from a linked list of integers that have value val.

    Example
    Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
    Return: 1 –> 2 –> 3 –> 4 –> 5

    Analysis

    To solve this problem, we keep two pointers pre and cur when scanning the LinkedList. Once the current node’s value equals to the target value, we remove the cur node by set pre.next = cur.next;

    To make the implementation easier,

    [Read More...]
  • Leetcode Intersection of Two Arrays

    Intersection of Two unsorted Arrays

    Given two arrays, write a function to compute their intersection.

    Example:
    Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

    Note:

    • Each element in the result must be unique.
    • The result can be in any order.

    Analysis

    Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

    We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays

    [Read More...]
  • Union and Intersection of two sorted arrays (Java)

    Given two sorted arrays or lists, get their union and intersection.

    For example, if the input arrays are:
    int[] list1 = {1, 3, 4, 5, 6, 7}
    int[] list2 = {2, 3, 5, 6}
    Then the union is {1, 2, 3, 4, 5, 6, 7} and the Intersection is {3, 5, 6}.

    Analysis

    We can solve this problem using the same idea of merging sorted list.

    Union of two sorted lists algorithm

     define two index variables p1 and p2, initialized as 0

    define List<Integer> 

    [Read More...]
  • LeetCode move zeroes

    Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

    For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

    Note:

    1. You must do this in-place without making a copy of the array.
    2. Minimize the total number of operations.

     Analysis
     

    We can use a pointer zeroIndex to always point to the index of the first 0. We scan the array, if we encounter a non-zero element,

    [Read More...]
Page 2 of 712345...Last »