Category Archives: Leetcode

Leetcode

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)

Leetcode

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);
        }
    }
}
Leetcode

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

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

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();
    }
}

 

Leetcode

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

 

Leetcode

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





	

	
	




	
	

				

			Leetcode
		

			
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. 

  2. 1 <= N <= 10^9
    3. 









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



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”.
    2. 



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

		

			 		

	


		

		




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. 

  2. 1 <= A[i] <= 1000
    3. 







 


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.