Leetcode 544. Output Contest Matches

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you're given n teams, you need to output their final contest matches in the form of a string.

The n teams are given in the form of positive integers from 1 to n, which represents their initial rank. (Rank 1 is the strongest team and Rank n is the weakest team.) We'll use parentheses('(', ')') and commas(',') to represent the contest team pairing - parentheses('(' , ')') for pairing and commas(',') for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Example 1:

Input: 2
Output: (1,2)
Explanation: 
Initially, we have the team 1 and the team 2, placed like: 1,2.
Then we pair the team (1,2) together with '(', ')' and ',', which is the final answer.

Example 2:

Input: 4
Output: ((1,4),(2,3))
Explanation: 
In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1,4),(2,3).
In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).

Example 3:

Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation: 
First round: (1,8),(2,7),(3,6),(4,5)
Second round: ((1,8),(4,5)),((2,7),(3,6))
Third round: (((1,8),(4,5)),((2,7),(3,6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).

Note:

1. The n is in range [2, 212].
2. We ensure that the input n can be converted into the form 2k, where k is a positive integer.

Code (Java):

class Solution {
    public String findContestMatch(int n) {
        List<String> prev = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            prev.add(i + "");
        }
        
        while (n > 1) {
            List<String> curr = new ArrayList<>();
            for (int i = 0; i < prev.size() / 2; i++) {
                String a = prev.get(i);
                String b = prev.get(prev.size() - i - 1);
                String s = '(' + a + ',' + b + ')';
                curr.add(s);
            }
            prev = curr;
            n /= 2;
        }
        
        return prev.get(0);
    }
}

Leetcode 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

1. The string consists of lower English letters only.
2. Length of the given string and k will in the range [1, 10000]

Code (Java):

class Solution {
    public String reverseStr(String s, int k) {
        if (k <= 1) {
            return s;
        }

        char[] charArr = s.toCharArray();
        int start = 0;
        int end = 0;

        while (start < charArr.length) {
            end = Math.min(start + k - 1, charArr.length - 1);
            reverse(charArr, start, end);

            start += k * 2;
        }

        return new String(charArr);
    }

    private void reverse(char[] charArr, int start, int end) {
        while (start < end) {
            char temp = charArr[start];
            charArr[start] = charArr[end];
            charArr[end] = temp;

            start++;
            end--;
        }
    }
}

Leetcode 539. Minimum Time Difference

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

1. The number of time points in the given list is at least 2 and won't exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

Code (Java):

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] minutes = new boolean[1440];

        for (String time : timePoints) {
            int minute = convertToMinutes(time);
            if (minutes[minute]) {
                return 0;
            }

            minutes[minute] = true;
        }

        // iterate through the minutes and find the minimum findMinDifference
        //
        int prev = -1;
        int first = -1;
        int curr = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < minutes.length; i++) {
            if (prev == -1) {
                if (minutes[i] == true) {
                    prev = i;
                    first = i;
                }
                continue;
            }

            if (minutes[i]) {
                curr = i;
                int diff = i - prev;
                diff = Math.min(diff, 1440 - diff);
                min = Math.min(min, diff);
                prev = i;
            }
        }
        int diff = curr - first;
        min = Math.min(min, Math.min(diff, 1440 - diff));

        return min;
    }

    private int convertToMinutes(String s) {
        String[] tokens = s.split("[:]");
        int hour = Integer.parseInt(tokens[0]);
        int minute = Integer.parseInt(tokens[1]);

        return hour * 60 + minute;
    }
}

Leetcode 537. Complex Number Multiplication

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

Code (Java):

class Solution {
    public String complexNumberMultiply(String a, String b) {
        // parse the r and i
        //
        String delim = "[+]";
        String[] tokensA = a.split(delim);
        String[] tokensB = b.split(delim);

        // get real part
        //
        int r1 = getInteger(tokensA[0]);
        int r2 = getInteger(tokensB[0]);

        // get imiminary part
        //
        int i1 = getInteger(tokensA[1].substring(0, tokensA[1].length() - 1));
        int i2 = getInteger(tokensB[1].substring(0, tokensB[1].length() - 1));

        // compose the result
        //
        int r3 = r1 * r2 - i1 * i2;
        int i3 = r1 * i2 + r2 * i1;

        return r3 + "+" + i3 + "i";
    }

    private int getInteger(String s) {
        boolean isNeg = false;
        int i = 0;
        if (s.charAt(0) == '-') {
            isNeg = true;
            i++;
        }

        int result = 0;
        while (i < s.length()) {
            int digit = Character.getNumericValue(s.charAt(i));
            result = result * 10 + digit;
            i++;
        }

        if (isNeg) {
            result = -result;
        }

        return result;
    }
}

Leetcode 522. Longest Uncommon Subsequence II

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.

Example 1:

Input: "aba", "cdc", "eae"
Output: 3

Note:

1. All the given strings' lengths will not exceed 10.
2. The length of the given list will be in the range of [2, 50].

Code (Java):

class Solution {
    public int findLUSlength(String[] strs) {
        if (strs == null || strs.length <= 1) {
            return -1;
        }

        // sort in reverse reverseOrder
        //
        Arrays.sort(strs, new MyComparator());

        for (int i = 0; i < strs.length; i++) {
            if ((i != strs.length - 1) && strs[i].equals(strs[i + 1])) {
                continue;
            }

            if (!isSubsequence(i, strs)) {
                return strs[i].length();
            }
        }

        return -1;
    }

    private boolean isSubsequence(int curr, String[] strs) {
        String currStr = strs[curr];

        for (int i = 0; i < curr; i++) {
            if (isSubsequenceHelper(currStr, strs[i])) {
                return true;
            }
        }

        return false;
    }

    private boolean isSubsequenceHelper(String a, String b) {
        int i = 0;
        int j = 0;
        while (i < a.length() && j < b.length()) {
            if (a.charAt(i) == b.charAt(j)) {
                i++;
                j++;
            } else {
                j++;
            }
        }

        return i == a.length();
    }
}

 class MyComparator implements Comparator<String> {
    public int compare(String a, String b) {
        if (a.length() < b.length()) {
            return 1;
        } else if (a.length() > b.length()) {
            return -1;
        }
        
        // length is equal
        //
        if (a.equals(b)) {
            return 0;
        }
        
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == b.charAt(i)) {
                continue;
            }
            
            return b.charAt(i) - a.charAt(i); 
        }
        
        return 0;
    }
}

Leetcode 520. Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

1. All letters in this word are capitals, like "USA".
2. All letters in this word are not capitals, like "leetcode".
3. Only the first letter in this word is capital if it has more than one letter, like "Google".

Otherwise, we define that this word doesn't use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

Code (Java):

class Solution {
    public boolean detectCapitalUse(String word) {
        if (word == null || word.isEmpty()) {
            return true;
        }

        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c >= 'A' && c <= 'Z') {
                count++;
            }
        }

        if (count == 0 || count == word.length()) {
            return true;
        }

        if (count == 1 && word.charAt(0) >= 'A' && word.charAt(0) <= 'Z') {
            return true;
        }

        return false;
    }
}

Leetcode 468. Validate IP Address

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:

Input: "172.16.254.1"

Output: "IPv4"

Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"

Output: "IPv6"

Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"

Output: "Neither"

Explanation: This is neither a IPv4 address nor a IPv6 address.

Code (Java):

class Solution {
    public String validIPAddress(String IP) {
        if (IP == null || IP.length() == 0) {
            return "Neither";
        }

        if (IP.contains(".")) {
            boolean valid = validateIPv4(IP);
            if (valid) {
                return "IPv4";
            }
        } else if (IP.contains(":")) {
            boolean valid = validateIPv6(IP);
            if (valid) {
                return "IPv6";
            }
        }

        return "Neither";
    }

    private boolean validateIPv4(String s) {
        String[] tokens = s.split("[.]");
        if (tokens.length != 4) {
            return false;
        }
        
        if (s.charAt(0) == '.' || s.charAt(s.length() - 1) == '.') {
            return false;
        }

        for (String token : tokens) {
            if (!validateIpv4Helper(token)) {
                return false;
            }
        }

        return true;
    }

    private boolean validateIpv4Helper(String s) {
        if (s == null || s.length() == 0 || s.length() > 3) {
            return false;
        }
        
        if (s.length() > 1 && s.charAt(0) == '0') {
            return false;
        }

        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }

            int digit = (int)(c - '0');
            num = num * 10 + digit;
        }

        if (num < 0 || num > 255) {
            return false;
        }

        return true;
    }

    private boolean validateIPv6(String s) {
        if (s.charAt(0) == ':' || s.charAt(s.length() - 1) == ':') {
            return false;
        }
        
        String[] tokens = s.split("[:]");
        if (tokens.length != 8) {
            return false;
        }

        for (String token : tokens) {
            if (!validateIpv6Helper(token)) {
                return false;
            }
        }

        return true;
    }

    private boolean validateIpv6Helper(String s) {
        if (s == null || s.length() == 0 || s.length() > 4) {
            return false;
        }

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                if (c < '0' || c > '9') {
                    return false;
                }
            } else {
                if (c < 'a' || c > 'f') {
                    return false;
                }
            }
        }

        return true;
    }
}

Leetcode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5   

Note:

1. There will only be '(', ')', '-' and '0' ~ '9' in the input string.
2. An empty tree is represented by "" instead of "()"

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int start = 0;
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        return str2treeHelper(s);
    }

    private TreeNode str2treeHelper(String s) {
        if (start >= s.length()) {
            return null;
        }

        // parse int
        //
        boolean neg = false;
        if (s.charAt(start) == '-') {
            neg = true;
            start++;
        }
        int num = 0;
        while (start < s.length() && Character.isDigit(s.charAt(start))) {
            int digit = Character.getNumericValue(s.charAt(start));
            num = num * 10 + digit;
            start++;
        }

        if (neg) {
            num = -num;
        }

        TreeNode root = new TreeNode(num);

        if (start >= s.length()) {
            return root;
        }

        // go to left child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.left = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        // go to the right child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.right = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        return root;
    }
}

Leetcode 443. String Compression

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.

Code (Java):

class Solution {
    public int compress(char[] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }
        
        int newPos = 0;
        int count = 1;
        for (int i = 0; i < chars.length; i++) {
            count = 1;
            while (i < chars.length && i != chars.length - 1 && (chars[i] == chars[i + 1])) {
                count++;
                i++;
            }

            int numChars = getNumberofChars(count);
            newPos = copyArray(chars, newPos, chars[i], count, numChars);
        }
        
        return newPos;
    }

    private int copyArray(char[] chars, int pos, char c, int count, int numChars) {
        chars[pos] = c;
        pos++;

        if (count > 1) {
            int end = pos + numChars - 1;
            while (count > 0) {
                int digit = count % 10;
                chars[end] = (char)(digit + '0');
                end--;

                count /= 10;
            }

            pos += numChars;
        }

        return pos;
    }

    private int getNumberofChars(int num) {
        int ans = 0;
        if (num < 10) {
            ans = 1;
        } else if (num < 100) {
            ans = 2;
        } else if (num < 1000) {
            ans = 3;
        } else {
            ans = 4;
        }

        return ans;
    }
}

Leetcode 408. Valid Word Abbreviation

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

Code (Java):

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        if (word.isEmpty()) {
            return abbr.isEmpty();
        }

        int pWord = 0;
        int pAbbr = 0;

        while (pWord < word.length() && pAbbr < abbr.length()) {
            if (!Character.isDigit(abbr.charAt(pAbbr))) {
                if (word.charAt(pWord) == abbr.charAt(pAbbr)) {
                    pWord++;
                    pAbbr++;
                } else {
                    return false;
                }
            } else {           
                // edge case: leading zero
                //
                if (abbr.charAt(pAbbr) == '0') {
                    return false;
                }
                
                int num = 0;
                while (pAbbr < abbr.length() && Character.isDigit(abbr.charAt(pAbbr))) {
                    int digit = Character.getNumericValue(abbr.charAt(pAbbr));
                    num = num * 10 + digit;
                    pAbbr++;
                }

                pWord += num;
            }
        }

        return pWord == word.length() && pAbbr == abbr.length();
    }
}

Leetcode 387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Code (Java):

class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        int[] counts = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (counts[c - 'a'] == 1) {
                return i;
            }
        }

        return -1;
    }
}