Tag Archives: Leetcode

21. Merge Two Sorted Lists

2019/04/03 shiji

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(0); // Put something to start
        ListNode result = cur;
        while(l1 != null || l2 != null){
            if(l1 == null){
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            } else if(l2 == null){
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else if(l1.val < l2.val){
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return result.next; // Igonre the first node
    }
}

1 ms 37.1 MB

Leetcode

20. Valid Parentheses

2019/04/03 shiji

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input:

 "()"

Output:

 true

Example 2:

Input:

 "()[]{}"

Output:

 true

Example 3:

Input:

 "(]"

Output:

 false

Example 4:

Input:

 "([)]"

Output:

 false

Example 5:

Input:

 "{[]}"

Output:

 true

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            switch(c){
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                default:
                    if(stack.isEmpty() || stack.peek() != c){
                        return false;
                    }
                    stack.pop();
                    
            }
        }
        return stack.isEmpty();
    }
}

Leetcode

14. Longest Common Prefix

2019/04/03 shiji

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input:

["flower","flow","flight"]

Output:

 "fl"

Example 2:

Input:

["dog","racecar","car"]

Output:

""

Explanation:

 There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if(empty($strs)){
            return "";
        }
        $result = "";
        for($i = 0; $i < strlen($strs[0]); $i ++){
            $cur = $strs[0][$i];
            foreach ($strs as $s){
                if($s[$i] != $cur){
                    return $result;
                }
            }
            $result.= $cur;
        }
        return $result;
        
    }
}

Leetcode

13. Roman to Integer

2019/04/03 shiji

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol

Value

I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input:

 "III"

Output:

Example 2:

Input:

 "IV"

Output:

Example 3:

Input:

 "IX"

Output:

Example 4:

Input:

 "LVIII"

Output:

Explanation:

 L = 50, V= 5, III = 3.

Example 5:

Input:

 "MCMXCIV"

Output:

Explanation:

 M = 1000, CM = 900, XC = 90 and IV = 4.

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s) {
        $i= 0;
        $p = ["I"=>1, "V"=>5, "X"=>10, "L"=>50, "C"=> 100, "D"=>500, "M"=>1000];
        $result = 0;
        $increment = INF;
        while($i < strlen($s)){
            $new_increment =  $p[$s[$i]];
            if($increment < $new_increment){
                $result -= (2 * $increment);
            }
            $increment = $new_increment;
            $result += $increment;
            $i ++;
        }
        return $result;
    }
}

The solution is based on the fact that the input is valid, otherwise won’t work

Leetcode

1023. Binary String With Substrings Representing 1 To N

2019/03/24 shiji

Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input:

S = "0110", N = 3

Output:

true

Example 2:

Input:

S = "0110", N = 4

Output:

false

Note:

1 <= S.length <= 1000
1 <= N <= 10^9

Thoughts:

I was thinking there could be an amazing algo to deal with it.

Well, the solution is quite straight forward, just follow your mind. I didn’t even give it a try during the contest.

It’s kind of unexpected for a median level question.

For the time complexity, here’s a great analysis from lee215:

Time Complexity

Prove I, check number of substring

Pick two indices, there are at most S^2 substrings,
so S can contains at most S^2 integers
Time complexity upper bound O(S^2)

Prove II, Check the continuous digits
Meanwhile I know the interviewer and my reader won’t be satisfied,
as they want no more “cheat”.

Here I have a brief demonstration to give the time complexity an acceptable upper bound.

Have a look at the number 1001 ~ 2000 and their values in binary.

1001 0b1111101001
1002 0b1111101010
1003 0b1111101011
…
1997 0b11111001101
1998 0b11111001110
1999 0b11111001111
2000 0b11111010000

The number 1001 ~ 2000 have 1000 different continuous 10 digits.
The string of length S has at most S - 9 different continuous 10 digits.
So S <= 1000, N <= 2000.

So S * 2 is a upper bound for N.
If N > S * 2, we can return false directly.

It’s the same to prove with the numbers 512 ~ 1511, or even smaller range.

Time complexity upper bound O(S)

And finally, the code:

class Solution {

    /**
     * @param String $S
     * @param Integer $N
     * @return Boolean
     */
    function queryString($S, $N) {
        while($N > 1){
            $binary = decbin($N);
            if(strpos($S, $binary) === false){
                return false;
            }
            $N --;
        }
        return true;
    }
}

Leetcode

1021. Best Sightseeing Pair

2019/03/24 shiji

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input:

[8,1,5,2,6]

Output:

11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

2 <= A.length <= 50000
1 <= A[i] <= 1000

Thoughts:

Scan from left to right, record:

best score so far()
the best left element which could generate the largest score with the next element.
- As we move on to the next, gap ++, impact/score — with the prev. best left element

class Solution {

    /**
     * @param Integer[] $A
     * @return Integer
     */
    function maxScoreSightseeingPair($A) {
        $bestResult = 0;    // Best Score (A[i] + A[j] + i - j)
        $bestAI = 0;        // The best choice of A[i] so far
        foreach($A as $a){
            // Moved to next, gap++, then the "sightseeing value" --
            $bestAI --; 
            // Best result = 
            $bestResult = max($bestResult, $bestAI + $a );
            $bestAI = max($a, $bestAI);
        }
        return $bestResult;
    }
}

well sure I can combine $bestAI –; into other expressions. Just to make it clear in this way.

Leetcode

1020. Partition Array Into Three Parts With Equal Sum

2019/03/23 shiji

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])

Example 1:

Input:

[0,2,1,-6,6,-7,9,1,2,0,1]

Output:

true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

Input:

[0,2,1,-6,6,7,9,-1,2,0,1]

Output:

false

Example 3:

Input:

[3,3,6,5,-2,2,5,1,-9,4]

Output:

true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Note:

3 <= A.length <= 50000
-10000 <= A[i] <= 10000

class Solution {

    /**
     * @param Integer[] $A
     * @return Boolean
     */
    function canThreePartsEqualSum($A) {
        $mean = array_sum($A) / 3;
        if (floor($mean) != $mean){
            return false;
        }
        
        $count  = 0;
        $sum = 0;
        $i = 0;
        while ($i < count($A)){    
            $sum += $A[$i];
            $i ++;
            if($sum == $mean){
                $count ++;
                $sum = 0;
            }
        }
        return $count == 3;
    }
}

Leetcode

1022. Smallest Integer Divisible by K

2019/03/23 shiji

Given a positive integer K, you need find the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.

Return the length of N. If there is no such N, return -1.

Example 1:

Input:

Output:

Explanation:

 The smallest answer is N = 1, which has length 1.

Example 2:

Input:

Output:

-1

Explanation:

 There is no such positive integer N divisible by 2.

Example 3:

Input:

Output:

Explanation:

 The smallest answer is N = 111, which has length 3.

Note:

1 <= K <= 10^5

Thoughts:

Two tricky parts.

$n = ($n * 10 +1) % $K;Suppose r = (aK + b) when r > K, next r supposed to be 10r+1 = 10aK + 10b + 1. Since 10aK is divisible by K, we just need to consider 10b + 1. b is r % K, so we can update r = r % K. [By https://leetcode.com/wangqiuc/]
The exit condition for loop, $n <= $K, actually, there always exist an answer, we can use while true instead.

Proof [By https://leetcode.com/starsthu2016/]

It is obvious that if K is the multiple of 2 or multiple of 5, N is definitely not multiple of K because the ones digit of N is 1. Thus, return -1 for this case.

If K is neither multiple of 2 nor multiple of 5, we have this theorem.

Theorem: there must be one number from the K-long candidates list [1, 11, 111, …, 111..111(with K ones)], which is the multiple of K.

Why? Let’s think in the opposite way. Is it possible that none of the K candidates is the multiple of K?

If true, then the module of these K candidate numbers (mod K) must be in [1, .., K-1] (K-1 possible module values). Thus, there must be 2 candidate numbers with the same module. Let’s denote these two numbers as N_i with i ones, and N_j with j ones and i<j.

Thus N_j-N_i = 1111…1000…0 with (j-i) ones and i zeros. N_j-N_i = 111..11 (j-i ones) * 100000..000 (i zeros). We know that N_i and N_j have the same module of K. Then N_j-N_i is the multiple of K. However, 100000..000 (i zeros) does not contain any factors of K (K is neither multiple of 2 nor multiple of 5). Thus, 111..11 (j-i ones) is the multiple of K. This is contradictory to our assumption that all K candidates including 111..11 (j-i ones) are not multiple of K.

Finally, we know that there is at least one number, from the first K candidates, which is the multiple of K.

class Solution {

    /**
     * @param Integer $K
     * @return Integer
     */
    function smallestRepunitDivByK($K) {
        if($K % 2 == 0 || $K % 5 == 0){
            return -1;
        }
        $n = 1;
        $r = 1;
        while($n <= $K ){
            if($n % $K == 0){
                return  $r;
            }
            $n = ($n * 10 +1) % $K;
            $r ++;
        }
        return -1;
    }
}