24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

 

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function swapPairs($head) {
        if($head === null || $head->next === null){
            return $head;
        }
        
        $r = $head->next;
        $temp = $r->next;
        $r->next = $head;
        $r->next ->next = $this->swapPairs($temp);
        return $r;
    }
}

 

1031. Maximum Sum of Two Non-Overlapping Subarrays

Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M.  (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

  • 0 <= i < i + L - 1 < j < j + M - 1 < A.lengthor
  • 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

 

Example 1:

Input:

A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2

Output:

20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input:

A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2

Output:

29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input:

A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3

Output:

31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

 

Note:

  1. L >= 1
  2. M >= 1
  3. L + M <= A.length <= 1000
  4. 0 <= A[i] <= 1000
class Solution {

    /**
     * @param Integer[] $A
     * @param Integer $L
     * @param Integer $M
     * @return Integer
     */
    function maxSumTwoNoOverlap($A, $L, $M) {
        $max  = 0;
        $a = [];
        $b = [];
        for($i  = 0; $i < count($A)-$L+1; $i ++){
            $a[$i] =  array_sum(array_slice($A,$i,$L));
        }
        
        for($j = 0; $j < count($A)-$M+1; $j ++){
            $b[$j] = array_sum(array_slice($A,$j,$M));
        }
        arsort($a);arsort($b);
        foreach($a as $ak => $av){
            foreach($b as $bk => $bv){
                if($bk + $M <= $ak || $ak + $L <= $bk){
                    $max = max($max, $av + $bv);

                }
            }
        }
        
        return $max;
    }
}

160ms

Thoughts:

  • My code is the version used for contest, so..
  • The length of inputs (1000) seems relatively small, so just follow your heart, again…
  • Idea, scan & store sums for L &  M fixed size arrays.
  • for each sum L and for each sum M, if no overlap, the check and update max total.
  • What makes it slow:
    • array_sum.. fixed size sliding door works better, but more codes…
    • double for each, there’s an obvious pattern to move index out of overlap.
  • Having these sorts have 10ms improvement, which is quite interesting.

Improved Version

class Solution {

    /**
     * @param Integer[] $A
     * @param Integer $L
     * @param Integer $M
     * @return Integer
     */
    function maxSumTwoNoOverlap($A, $L, $M) {
        $max  = 0;
        $a = [];
        $b = [];

        for($i  = 0; $i < count($A)-$L+1; $i ++){
            if($i == 0){
                $a[$i] =  array_sum(array_slice($A,$i,$L));
            } else {
                $a[$i] = $a[$i-1] - $A[$i-1] + $A[$i+$L-1];
            }
        }
        
        for($i = 0; $i < count($A)-$M+1; $i ++){
            if($i == 0){
                $b[$i] =  array_sum(array_slice($A,$i,$M));
            } else {
                $b[$i] = $b[$i-1] - $A[$i-1] + $A[$i+$M-1];
            }
        }
        for($i = 0; $i < count($a); $i++){
            for($j = 0; $j < count($b);$j++){
                if($j + $M <= $i || $i + $L <= $j){
                    $max = max($max, $a[$i] + $b[$j]);
                } else if($j + $M <= $i){
                    $j += ($M-1);
                }
            }
        }
        
        return $max;
    }
}
  • The “fixed size sliding door” saved about 20ms
  • No significant improvement for the double for each.

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function frequencySort($s) {
        $c = [];
        for($i = 0 ; $i < strlen($s); $i++){
            $char = $s[$i];
            $c[$char] ++;
        }
        
        arsort($c);
        $result = "";
        foreach($c as $k => $v){
            while($v > 0){
                $result .= $k;
                $v --;
            }
        }
        return $result;
    }
}

well, PHP is actually pretty good at this.

Doing same thing in Java is quite annoying (typing speed matters)

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution {

    /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $result = [];
        $this->helper(0, 0, $n, "", $result);
        return $result;
    }
    
    function helper($l, $r, $max, $str, &$result){
        if($l + $r == $max*2){
            $result[] = $str;
            return;
        }
        if($l < $max){
            $this->helper($l+1, $r, $max, $str."(", $result);
        }
        
        if($r < $l){
            $this->helper($l, $r+1, $max, $str.")", $result);
        }
    }
}

1023. Binary String With Substrings Representing 1 To N

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. 1 <= S.length <= 1000
  2. 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
  1. 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)

  1. 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 <= 1000N <= 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;
    }
}

 

1021. Best Sightseeing Pair

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:

  1. 2 <= A.length <= 50000
  2. 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.

1022. Smallest Integer Divisible by K

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:

 1

Output:

 1

Explanation:

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

Example 2:

Input:

 2

Output:

 -1

Explanation:

 There is no such positive integer N divisible by 2.

Example 3:

Input:

 3

Output:

 3

Explanation:

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

 

Note:

  • 1 <= K <= 10^5

Thoughts:

Two tricky parts.

  1. $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/]
  2. 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;
    }
}

 

 

1006. Clumsy Factorial

Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n.  For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.

For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.  However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11.  This guarantees the result is an integer.

Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.

 

Example 1:

Input:

4

Output:

 7

Explanation:

 7 = 4 * 3 / 2 + 1

Example 2:

Input:

10

Output:

12

Explanation:

12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

 

Note:

  1. 1 <= N <= 10000
  2. -2^31 <= answer <= 2^31 - 1  (The answer is guaranteed to fit within a 32-bit integer.)

 


Thoughts:

  • Split into chunks of size 4, then deal with case 3 or 2 or 1
  • The first chunk has a positive sign, then negative starting from the second trunk, including the remaining (3, 2, or 1) part
  • if n < 4, the sign is positive

 


 

class Solution {

    /**
     * @param Integer $N
     * @return Integer
     */
    function clumsy($n) {
        $r = 0;
        $f = 0;
        $first_positive_chunk_set = false;
        
        if($n >= 4){
            $r = floor($n*($n-1)/($n-2)) + $n-3;
            $n -= 4;
            $first_positive_chunk_set = true;
        }
     
        
        while(floor($n / 4) >= 1){
            $r -= floor($n*($n-1)/($n-2)) - $n+3;
            $n -= 4;
        }
        if($n >= 3){
            $r -= floor($n*($n-1)/($n-2)) ;
            $n -= 3;
        }
        if($n >= 2){
            $r -= $n*($n-1) ;
            $n -= 2;
        }
        if($n >= 1){
            $r -= $n ;
            $n -= 1;
        }
        return $first_positive_chunk_set?$r:-$r;
    }
}

Another Solution Inspired by Other

  • Base on math
  • Other than that(short), this solution is hard to read and understand.
class Solution {

    /**
     * @param Integer $N
     * @return Integer
     */
    function clumsy($n) {
        if ($n<5){
            return  $n+3*($n>2);
        }
        return $n+2-3*($n%4==3)-($n%4==0);
    }
}