## 21. Merge Two Sorted Lists

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
```

```/**
* 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

## 20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. 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();
}
}```

## 14. Longest Common Prefix

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;

}
}```

## 13. Roman to Integer

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:

` 3`

Example 2:

Input:

``` "IV"
```

Output:

` 4`

Example 3:

Input:

``` "IX"
```

Output:

` 9`

Example 4:

Input:

``` "LVIII"
```

Output:

``` 58
```

Explanation:

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

Example 5:

Input:

``` "MCMXCIV"
```

Output:

``` 1994
```

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

## 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 <= 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;
}
}```

## 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.

## 1020. Partition Array Into Three Parts With Equal Sum

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:

1. `3 <= A.length <= 50000`
2. `-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;
}
}```

## 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;
}
}```