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.