Leetcode 388. Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

Code (Java):

class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) {
            return 0;
        }
        
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        
        // step 1: split input into tokens
        //
        String[] tokens = input.split("[\n]");
        
        int curLen = 0;
        
        for (String token : tokens) {
            int level = getLevel(token);
            
            while (level < stack.size()) {
                curLen -= stack.pop();
            }
            
            int len = getLength(token);
            curLen += len;
            
            if (token.contains(".")) {
                maxLen = Math.max(maxLen, curLen - 1);
            }
            
            stack.push(len);
        }
        
        return maxLen;
    }
    
    private int getLevel(String token) {
        int level = 0;
        
        level = token.lastIndexOf("\t") + 1;
                
        return level;
    }
    
    private int getLength(String token) {
        String s = token.replaceAll("\t", "");
        return s.length() + 1;
    }
}

Leetcode 412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Code (java):

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> ans = new ArrayList<>();
        
        if (n <= 0) {
            return ans;
        }
        
        for (int i = 1; i <= n; i++) {
            String s = "";
            
            if (i % 3 == 0) {
                s = "Fizz";
            }
            
            if (i % 5 == 0) {
                s += "Buzz";
            } else if (i % 3 != 0) {
                s = i + "";
            }
            
            ans.add(s);
        }
        
        return ans;
    }
}

Leetcode 617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
 Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
      3
     / \
    4   5
   / \   \ 
  5   4   7

Note: The merging process must start from the root nodes of both trees.

Analysis:

The idea is just divide and conquer. 

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        
        TreeNode root = new TreeNode((t1 != null ? t1.val : 0) + (t2 != null ? t2.val : 0));
        
        root.left = mergeTrees(t1 != null ? t1.left : null, t2 != null ? t2.left : null);
        root.right = mergeTrees(t1 != null ? t1.right : null, t2 != null ? t2.right : null);
        
        return root;
    }
}

Leetcode 561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

Code (Java):

class Solution {
    public int arrayPairSum(int[] nums) {
        int sum = 0;
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        
        return sum;
    }
}

Leetcode 771. Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in Sis a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

Code (Java):

class Solution {
    public int numJewelsInStones(String J, String S) {
        if (J == null || J.length() == 0 || S == null || S.length() == 0) {
            return 0;
        }
        
        int ans = 0;
        
        boolean[] dictS = new boolean[26];
        boolean[] dictL = new boolean[26];
        
        // step 1: pre-process the string J and put chars into the dict
        //
        for (int i = 0; i < J.length(); i++) {
            char c = J.charAt(i);
            if (c >= 'a' && c <= 'z') {
                dictS[c - 'a'] = true;
            } else {
                dictL[c - 'A'] = true;
            }
        }
        
        // step 2: check each char in S and see if it's in the dict
        //
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if (c >= 'a' && c <= 'z' && dictS[c - 'a']) {
                ans++;
            } else if (c >= 'A' && c <= 'Z' && dictL[c - 'A']) {
                ans++;
            }
        }
        
        return ans;
    }
}

Leetcode 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Code (Java):

class Solution {
    public int hammingDistance(int x, int y) {
        // step 1: get xor for x and y
        //
        int xorNum = x ^ y;
        
        // step 2: check how many bit 1s in the xorNum
        //
        int mask = 1;
        int distance = 0;
        
        
        for (int i = 0; i < 32; i++) {
            distance += xorNum & mask;
            xorNum = xorNum >> 1;
        }
        
        return distance;
    }
}