LeetCode Blog for course "Algorithms" -- Problem 11

Problem 11. Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.


My solution in Python:

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height) - 1
        ans = 0
        while left < right:
            if height[left] < height[right]:
                area = height[left] * (right - left)
                left += 1
            else:
                area = height[right] * (right - left)
                right -= 1
            ans = max(ans, area) 
        return ans

Review:

This problem belongs to the more simple ones. The trick here is that we don't really need to examine all combinations of two vertical lines, we only need to discard the shorter one. The height used in calculating area is the shorter one of the two lines, so it does no good to retain the shorter one after computing the current area. We move on and retain the longer line, until the two lines meet.

LeetCode Blog for course "Algorithms" -- Problem 9

Problem 9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

My solution in Python:

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        copy, reverse = x, 0

        while copy:
            reverse *= 10
            reverse += copy % 10
            copy /= 10

        return x == reverse

Review:

After much thought, I cannot solve the problem without using extra space, so my solution does use some extra space as a new integer is constructed.
Negative numbers cannot be palindromic due to the preceding "-" sign which doesn't exist at the end, so we first check whether the given number is less than 0.
If it is greater than or equals 0, we construct a reversed version of this integer, then compare them. If the original integer equals to its reversed version, then the number is palindromic.

LeetCode Blog for course "Algorithms" -- Problem 8

Problem 8. String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (i.e. no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

My solution in Python:

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        if str == "" :
            return 0
        i = 0
        sign = 1
        ret = 0
        length = len(str)
        MaxInt = (1 << 31) - 1
        if str[i] == '+':
            i += 1
        elif str[i] == '-' :
            i += 1
            sign = -1
        
        for i in range(i, length) :
            if str[i] < '0' or str[i] > '9' :
                break
            ret = ret * 10 + int(str[i])
            if ret > sys.maxint:
                break
        ret *= sign
        if ret >= MaxInt:
            return MaxInt
        if ret < MaxInt * -1 :
            return MaxInt * - 1 - 1 
        return ret

Review:

According to the requirements in the description, as long as the string starts with number digits (ignoring whitespaces), that substring of number digits is converted to an integer. So first we use the "strip" function to remove all consecutive whitespaces from the beginning and end of the original string. Then we check if there is a sign character ("+" or "-") at the start of the string. Then we read the string one character by one character until a non-number character or the end of the string is reached. We check if the converted integer exceeds the limits of integer. The algorithm ends here.

LeetCode Blog for course "Algorithms" -- Problem 7

Problem 7. Reverse Integer

Reverse digits of an integer.
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? i.e. cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

My solution in Python:

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
            
        neg = 1
        if x < 0:
            neg, x = -1, -x
        
        reverse = 0
        while x > 0:
            reverse = reverse * 10 + x % 10
            x = x / 10
        
        reverse = reverse * neg
        if reverse < -(1 << 31) or reverse > (1 << 31) - 1:
            return 0
        return reverse

Review:

This problem belongs to the more simple questions. However, we do need to consider the special conditions, such as numbers that exceeds the limit of 32 bits when reversed. Therefore, after reversing all the digits, we check to see whether it exceeds -(1<<31) or (1>>31), and if it does, we set the reversed value to 0.

LeetCode Blog for course "Algorithms" -- Problem 6

Problem 6. Zigzag Conversion

Write the code that will take a string and make this conversion given a number of rows.

My solution in Python:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows==1: return s
        tmp=['' for i in range(numRows)]
        index=-1; step=1
        for i in range(len(s)):
            index+=step
            if index==numRows:
                index-=2; step=-1
            elif index==-1:
                index=1; step=1
            tmp[index]+=s[i]
        return ''.join(tmp)

Review:

This problem asks us to convert a given string to a zigzag form, giving the number of rows the zigzag shape should contain of. It does not require the exact shape to be drawn, only the result string combining the rows of the zigzag is required. Thus, this problem is basically asks for a new arrangement of the original string.
First we construct a certain number of strings, the number of strings equals to the number of rows in the zigzag. Then for each character in the original string, we decide which of the substrings should it goes to (be appended to). The decision is made using the following procedure.
First we put the first character in the original string in the first substring. Then for each following letter, we put it in the next substring (the next row in the zigzag). This is achieved by setting the "step" variable (increment) to 1.
When the last row of the zigzag is reached, after putting the corresponding letter in that row, we alter the value of "step" to -1. Thus in each following iteration, rather than going down, we going up along the zigzag, putting the next letter one row above the previous one. "Step" is again set to 1 when the first row of the zigzag is reached.
The algorithm ends when the last letter in the original string is processed this way.

LeetCode Blog for course "Algorithms" -- Problem 3 & 5

Problem 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.


My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ answer = 0; left = 0; last = {}; for i in range(len(s)): if s[i] in last and last[s[i]] >= left: left = last[s[i]] +1; last[s[i]] = i; answer = max(answer, i - left + 1); return answer;

Review:
We make good use of the "dictionary" in Python here. Starting with the first character in the string, we go through the string characters one by one, and store one item in the dictionary, with the character being the key, and the place it appears in the string being the value. When we encounter a character that has already appeared previously, we immediately know because this particular key (the character) is already in the dictionary. Thus we move the starting character of the substring to the next position of which the repeated character first appeared in the original string. We then compare the length of the current non-repeated-character-substring with the longest substring we already know. When "i" reaches the last character of the original string, the "answer" should be the length of the longest substring without repeated character.


Problem 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:
Input: "cbbd"
Output: "bb"

My solution in Python: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ ansl, ansr, maxx = 0, 0, 0 length = len(s) for i in range(1, length * 2): if i & 1 : left = i / 2 right = left else : left = i / 2 - 1 right = left + 1 while (left >= 0) and (right < length) and (s[left] == s[right]): left -= 1 right += 1 left += 1 right -= 1 if right - left > maxx: maxx = right - left ansl = left ansr = right return s[ansl: ansr + 1]

Review:
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only $\mathrm{2n-1}$ such centers. By treating odd "i" and even "i" differently, we are able to examine both palindromes with even length and with odd length. This question is actually very interesting and has many (at least 5) different solutions, each with different time and space efficiency. The most advanced one, the Manacher's algorithm, can be found here.

LeetCode Blog for course "Algorithms" -- Problem 1 & 2

Problem 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My solution in Python:

1 2 3 4 5 6 7 8 9 10

class Solution(object):     def twoSum(self,nums,target):         first=0         second=0         for x in range(0,len(nums)):             for y in range(x+1,len(nums)):                 if nums[x]+nums[y]==target:                     first=x                     second=y                     return [first,second]

Review:
We use nested iterations here. For each number in the array, we go through the numbers in the array after it to see if there is a required match. Because there is only one such pair that suits the requirement (add up to a specific target), once we find such a match, we can stop the iteration here.


Problem 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ answer = ListNode(0); pointer = answer; carry = 0; while True: if l1 != None: carry += l1.val; l1 = l1.next; if l2 != None: carry += l2.val; l2 = l2.next; pointer.val = carry % 10; carry /= 10; if l1 != None or l2 != None or carry != 0: pointer.next = ListNode(0); pointer = pointer.next; else: break; return answer;

Review:
Given that the digits are stored in reverse order in the list, the first node in the list is the least significant bit in the integer, so we can add the two lists directly from the first node to the last node. The solution is very straight-forward. Note that along with checking whether both l1 and l2 have reached their ends, we also must check whether the carry bit equals 0. A non-zero carry bit must be carried to the next iteration and have a new node in the answer list to store it. When both l1 and l2 have reached their end, and the carry bit is 0, the algorithm ends.