LeetCode | Learn for Master

Leetcode Path Sum

August 26, 2016 Author: david

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

1

2

3

4

5

6

7

8

5

/ \

4 8

/ / \

11 13 4

/ \ \

7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == sum;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

public boolean hasPathSum(TreeNode root, int sum) {

if (root == null) return false;

if (root.left == null && root.right == null) return root.val == sum;

return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

}

[Read More...]

Leetcode Permutation Sequence

August 26, 2016 Author: david

No comment yet

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):

“123”
“132”
“213”
“231”
“312”
“321”

Given n and k, return the kth permutation sequence.

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

Java solution:

public class Solution {
    public String getPermutation(int n, int k) {
        if ( n ==  1) return "1";
        
        int factor = 1;
        //cause time limit error
        // ArrayList<Integer> res = new ArrayList<>();
        int[] res = new int[n];
        for(int i = 1; i <= n; i++) {
            // res.add(i);
            factor *= i;
            res[i - 1] = i;
        }
        int index = 0;
        // StringBuilder sb = new StringBuilder();
        char[] ary = new char[n];
        k--;
        for(int i = 0; i < n ; i++) {
            factor /= (n - i);
            index = k / factor;
            k = k % factor;
            ary[i] = (char)(res[index] + '0');
            // sb.append(res[index]);
            // res.remove(index);
            for(int j = index; j < n - i - 1; j++) {
                res[j]= res[j + 1];
            }
        }
        return String.valueOf(ary);
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

public class Solution {

public String getPermutation(int n, int k) {

if ( n == 1) return "1";

int factor = 1;

//cause time limit error

// ArrayList<Integer> res = new ArrayList<>();

int[] res = new int[n];

for(int i = 1; i <= n; i++) {

// res.add(i);

factor *= i;

res[i - 1] = i;

}

int index = 0;

// StringBuilder sb = new StringBuilder();

char[] ary = new char[n];

k--;

for(int i = 0; i < n ; i++) {

factor /= (n - i);

index = k / factor;

k = k % factor;

ary[i] = (char)(res[index] + '0');

// sb.append(res[index]);

// res.remove(index);

for(int j = index; j < n - i - 1; j++) {

res[j]= res[j + 1];

}

return String.valueOf(ary);

}

Refernce:

https://leetcode.com/problems/permutation-sequence/

http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html

[Read More...]

Leetcode Flatten Nested List Iterator (Java)

August 24, 2016 Author: david

No comment yet

Given a nested list of integers, implement an iterator to flatten it.

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

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

[Read More...]

LeetCode Shuffle an Array (Java)

August 23, 2016 Author: david

No comment yet

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

1

2

3

4

5

6

7

8

9

10

11

12

13

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

Java Solution

public class Solution {

    int[] origin;
    int[] res;
    Random r;
    public Solution(int[] nums) {
        origin = nums;
        res = Arrays.copyOf(nums, nums.length);
        r = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        res = Arrays.copyOf(origin, origin.length);
        return res;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int right = res.length - 1;
        int j;
        
        while(right > 0) {
            j = r.nextInt(right + 1);
            swap(res, j, right);
            right--;
        }
        return res;
    }
    
    void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

public class Solution {

int[] origin;

int[] res;

Random r;

public Solution(int[] nums) {

origin = nums;

res = Arrays.copyOf(nums, nums.length);

r = new Random();

}

/** Resets the array to its original configuration and return it. */

public int[] reset() {

res = Arrays.copyOf(origin, origin.length);

return res;

}

/** Returns a random shuffling of the array. */

public int[] shuffle() {

int right = res.length - 1;

int j;

while(right > 0) {

j = r.nextInt(right + 1);

swap(res, j, right);

right--;

}

return res;

}

void swap(int[] A, int i, int j) {

int tmp = A[i];

A[i] = A[j];

A[j] = tmp;

}

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* int[] param_1 = obj.reset();

* int[] param_2 = obj.shuffle();

*/

[Read More...]

LeetCode Linked List Cycle (java)

August 22, 2016 Author: david

No comment yet

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

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

Java Solution

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode fastP = head.next;
        ListNode slowP = head;
        while(fastP != null && fastP != slowP) {
            if(fastP.next == null) return false;
            fastP = fastP.next.next;
            slowP = slowP.next;
        }
        return fastP == slowP;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

*/

public class Solution {

public boolean hasCycle(ListNode head) {

if(head == null || head.next == null) return false;

ListNode fastP = head.next;

ListNode slowP = head;

while(fastP != null && fastP != slowP) {

if(fastP.next == null) return false;

fastP = fastP.next.next;

slowP = slowP.next;

}

return fastP == slowP;

}

[Read More...]

LeetCode Ransom Note (Java)

August 22, 2016 Author: david

No comment yet

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.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

1

2

3

4

canConstruct("a", "b") -> false

canConstruct("aa", "ab") -> false

canConstruct("aa", "aab") -> true

Java Solution

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // if(ransomNote == null && magazine == null) return true;
        // if(ransomNote == null) return true;
        // if(magazine == null) return false;
        // if(ransomNote.length() == 0 && magazine.length() == 0) return true;
        // if(ransomNote.length() > magazine.length()) return false;
        
        Map<Character, Integer> freq = new HashMap<>();
        for(char c: magazine.toCharArray()) {
            if(freq.containsKey(c)) {
                freq.put(c, freq.get(c) + 1);
            } else {
                freq.put(c, 1);
            }
        }
        for(char c: ransomNote.toCharArray()) {
            if (freq.containsKey(c)) {
                if(freq.get(c) > 1) {
                    freq.put(c, freq.get(c) - 1);
                } else {
                    freq.remove(c);
                }
            }else{
                return false;
            }
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

public class Solution {

public boolean canConstruct(String ransomNote, String magazine) {

// if(ransomNote == null && magazine == null) return true;

// if(ransomNote == null) return true;

// if(magazine == null) return false;

// if(ransomNote.length() == 0 && magazine.length() == 0) return true;

// if(ransomNote.length() > magazine.length()) return false;

Map<Character, Integer> freq = new HashMap<>();

for(char c: magazine.toCharArray()) {

if(freq.containsKey(c)) {

freq.put(c, freq.get(c) + 1);

} else {

freq.put(c, 1);

}

for(char c: ransomNote.toCharArray()) {

if (freq.containsKey(c)) {

if(freq.get(c) > 1) {

freq.put(c, freq.get(c) - 1);

} else {

freq.remove(c);

}

}else{

return false;

}

return true;

}

[Read More...]

Leetcode Jump Game I & II (Java)

August 22, 2016 Author: david

No comment yet

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:

public class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        if (size == 0) return true;
        int curMax = nums[0];
        for(int i = 1; i < size; i++) {
            if( i <= curMax) {
                curMax = Math.max(curMax, nums[i] + i);
            }else{
                return false;
            }
        }
        return true;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

public class Solution {

public boolean canJump(int[] nums) {

int size = nums.length;

if (size == 0) return true;

int curMax = nums[0];

for(int i = 1; i < size; i++) {

if( i <= curMax) {

curMax = Math.max(curMax, nums[i] + i);

}else{

return false;

}

return true;

}

Jump Game II

Given an array of non-negative integers,

[Read More...]

Leetcode mini parser

August 22, 2016 Author: david

No comment yet

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:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

1

2

3

4

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

1

2

3

4

5

6

7

8

9

10

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.

2. A nested list containing two elements:

i. An integer containing value 456.

ii. A nested list with one element:

a. An integer containing value 789.

Analysis

Define num to store the current number,

[Read More...]

Leetcode Expression Add Operators (Java)

August 20, 2016 Author: david

No comment yet

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:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

1

2

3

4

5

6

"123", 6 -> ["1+2+3", "1*2*3"]

"232", 8 -> ["2*3+2", "2+3*2"]

"105", 5 -> ["1*0+5","10-5"]

"00", 0 -> ["0+0", "0-0", "0*0"]

"3456237490", 9191 -> []

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

August 8, 2016 Author: david

No comment yet

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:

1

2

3

4

5

6

1

/ \

2 2

/ \ / \

3 4 4 3

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

1

2

3

4

5

6

1

/ \

2 2

\ \

3 3

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 Path Sum

Leetcode Permutation Sequence

Leetcode Flatten Nested List Iterator (Java)

LeetCode Shuffle an Array (Java)

LeetCode Linked List Cycle (java)

LeetCode Ransom Note (Java)

Leetcode Jump Game I & II (Java)

Leetcode mini parser

Leetcode Expression Add Operators (Java)

Leetcode Symmetric Tree

Get $35 Toward a New Fire TV 4K Device

Shop Amazon Gift Cards. Any Occasion. No Expiration

Best books to master algorithms

Best books to master machine learning

Recommended books to master big data

Search

Category List

Featured Categories

Rss Feeds

Categories

Subscribe

Contact US

Popular Posts

learn4master.com 2016 Accelerated by keyCDN

Get $35 Toward a New Fire TV 4K Device

Shop Amazon Gift Cards. Any Occasion. No Expiration

Best books to master algorithms

Best books to master machine learning

Recommended books to master big data

Search

Category List

Featured Categories

Tags

Categories

Subscribe

Categories

Contact US

Tags

Popular Posts

learn4master.com 2016 Accelerated by keyCDN