LeetCode - Algorithms - 701. Insert into a Binary Search Tree

Problem

701. Insert into a Binary Search Tree

Java

Recursion

© Robert Sedgewick and Kevin Wayne

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return recur(root, val);
    }
    
    private  TreeNode recur(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val < node.val) {
            node.left = recur(node.left, val);
        } else if (val > node.val) {
            node.right = recur(node.right, val);
        } else {
            node.val = val;
        }
        return node;
    }
}

Submission Detail

  • 35 / 35 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Insert into a Binary Search Tree.
  • Memory Usage: 39.1 MB, less than 98.22% of Java online submissions for Insert into a Binary Search Tree.

LeetCode - Algorithms - 442. Find All Duplicates in an Array

Problem

442. Find All Duplicates in an Array

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        final int N = nums.length;
        int[] arr = new int[N + 1];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > 1) {
                list.add(i);
            }
        }
        return list;        
    }
}

Submission Detail

  • 28 / 28 test cases passed.
  • Runtime: 6 ms, faster than 50.21% of Java online submissions for Find All Duplicates in an Array.
  • Memory Usage: 64.1 MB, less than 5.07% of Java online submissions for Find All Duplicates in an Array.

LeetCode - Algorithms - 448. Find All Numbers Disappeared in an Array

Problem

448. Find All Numbers Disappeared in an Array

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        final int N = nums.length;
        int[] arr = new int[N+1];
        for(int i=0;i<nums.length;i++) {
            arr[nums[i]]++;
        }
        List<Integer> list = new ArrayList<Integer>();
        for(int i=1;i<arr.length;i++) {
            if (arr[i]==0) {
                list.add(i);
            }
        }
        return list;
    }
}

Submission Detail

  • 33 / 33 test cases passed.
  • Runtime: 6 ms, faster than 37.69% of Java online submissions for Find All Numbers Disappeared in an Array.
  • Memory Usage: 64 MB, less than 5.08% of Java online submissions for Find All Numbers Disappeared in an Array.

LeetCode - Algorithms - 1662. Check If Two String Arrays are Equivalent

Problem

1662. Check If Two String Arrays are Equivalent

Java

jdk

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder sb1 = new StringBuilder();
        for(int i=0;i<word1.length;i++)
            sb1.append(word1[i]);
        StringBuilder sb2 = new StringBuilder();
        for(int i=0;i<word2.length;i++)
            sb2.append(word2[i]);
        return sb1.toString().equals(sb2.toString());
    }
}

Submission Detail

  • 109 / 109 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Check If Two String Arrays are Equivalent.
  • Memory Usage: 36.7 MB, less than 88.84% of Java online submissions for Check If Two String Arrays are Equivalent.

LeetCode - Algorithms - 700. Search in a Binary Search Tree

Problem

700. Search in a Binary Search Tree

Java

Recursion

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode recur(TreeNode node, int val) {
        if (node.val == val)
            return node;
        else if (val < node.val) {
            if (node.left == null)
                return null;
            else
                return recur(node.left, val);
        } else {
            if (node.right == null)
                return null;
            else
                return recur(node.right, val);
        }
    }
    
    public TreeNode searchBST(TreeNode root, int val) {
        return recur(root, val);
    }
}

Submission Detail

  • 36 / 36 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in a Binary Search Tree.
  • Memory Usage: 39.7 MB, less than 16.71% of Java online submissions for Search in a Binary Search Tree.

LeetCode - Algorithms - 1365. How Many Numbers Are Smaller Than the Current Number

Problem

1365. How Many Numbers Are Smaller Than the Current Number

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        final int N = nums.length;
        int[] arr = new int[N];
        for(int i=0;i<N;i++)
            arr[i]=nums[i];
        Arrays.sort(arr);
        int[] r = new int[N];
        for(int i=0;i<N;i++) {
            int n = 0;
            for(int j=0;j<N && arr[j]<nums[i];j++) {
                n++;
            }
            r[i] = n;
        }
        return r;
    }
}

Submission Detail

  • 103 / 103 test cases passed.
  • Runtime: 4 ms, faster than 66.15% of Java online submissions for How Many Numbers Are Smaller Than the Current Number.
  • Memory Usage: 38.8 MB, less than 84.14% of Java online submissions for How Many Numbers Are Smaller Than the Current Number.

LeetCode - Algorithms - 771. Jewels and Stones

Problem

771. Jewels and Stones

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> j = new HashSet<Character>();
        for(int i=0;i<jewels.length();i++)
            j.add(jewels.charAt(i));
        int n = 0;
        for(int i=0;i<stones.length();i++)
            if (j.contains(stones.charAt(i)))
                n++;
        return n;
    }
}

Submission Detail

  • 255 / 255 test cases passed.
  • Runtime: 1 ms, faster than 64.92% of Java online submissions for Jewels and Stones.
  • Memory Usage: 37 MB, less than 89.30% of Java online submissions for Jewels and Stones.

LeetCode - Algorithms - 1528. Shuffle String

Problem

1528. Shuffle String

Java

1

1
2
3
4
5
6
7
8
9
class Solution {
    public String restoreString(String s, int[] indices) {
        char[] t = new char[s.length()];
        for(int i=0;i<indices.length;i++) {
            t[indices[i]] = s.charAt(i);
        }
        return new String(t);
    }
}

Submission Detail

  • 399 / 399 test cases passed.
  • Runtime: 2 ms, faster than 28.58% of Java online submissions for Shuffle String.
  • Memory Usage: 41.9 MB, less than 5.19% of Java online submissions for Shuffle String.

LeetCode - Algorithms - 389. Find the Difference

Problem

389. Find the Difference

Java

bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public char findTheDifference(String s, String t) {
        char c = ' ';
        s += t;
        int x = (int) (s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            x ^= (int) (s.charAt(i));
        }
        c = (char) x;
        return c;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.4 MB, less than 50.18% of Java online submissions for Find the Difference.

bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public char findTheDifference(String s, String t) {
        char c = ' ';
        final int N = 26;
        int[] a = new int[N];
        for (int i = 0; i < t.length(); i++) {
            a[t.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            a[s.charAt(i) - 'a']--;
        }
        for (int i = 0; i < N; i++) {
            if (a[i] > 0) {
                c = (char) (i + 'a');
                break;
            }
        }
        return c;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.2 MB, less than 88.24% of Java online submissions for Find the Difference.

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public char findTheDifference(String s, String t) {
        char r = ' ';
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        char c = ' ';
        for(int i=0;i<t.length();i++) {
            c = t.charAt(i);
            if (map.containsKey(c))
                map.put(c, map.get(c)+1);
            else
                map.put(c,1);
        }
        for(int i=0;i<s.length();i++) {
            c = s.charAt(i);
            if (map.containsKey(c))
                map.put(c, map.get(c)-1);
        }
        for(Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue()>0)
                r = e.getKey();
        }
        return r;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 8 ms, faster than 16.46% of Java online submissions for Find the Difference.
  • Memory Usage: 37.5 MB, less than 35.41% of Java online submissions for Find the Difference.

LeetCode - Algorithms - 504. Base 7

Problem

504. Base 7

Java

jdk

public static String Integer.toString(int i, int radix)

1
2
3
4
5
class Solution {
    public String convertToBase7(int num) {
        return Integer.toString(num, 7);
    }
}

Submission Detail

  • 241 / 241 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Base 7.
  • Memory Usage: 35.9 MB, less than 95.07% of Java online submissions for Base 7.