Stay Hungry.Stay Foolish.

LeetCode1-5

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

Solution:
使用字典,将出现的数字当作键,索引当作值以此存储到字典中。这样,当差值在字典当中时,直接返回索引即可。因为字典复杂度为 O(1),因此此算法复杂度为 O(n)。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        for i,n in enumerate(nums):
            m = target - n
            if m in dic:
                return [dic[m], i]
            else:
                dic[n] = i

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.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:
看到这一题后首先想到的是先求和,然后将最后的和进行分解生成链表,但是这样效率比较低。实际上,链表对应位相加对10求余,得到的就是结果链表对应位置的值,同时将进位保存起来,链表指针后移,加上上次计算的进位,然后再对10求数,就得到了结果链表下一个节点的值。以此类推,可以完成整个过程的计算。

divmod(x, y): 返回商和余数 (x//y, x%y).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0 # 进位,初始值为0
        result = n = ListNode(0)
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            carry, val = divmod(carry, 10)
            n.next = ListNode(val)
            n = n.next
        return result.next

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.

Solution:
从左到右依次遍历,记录当前最长子串。遇到重复字符,则将检索开始 start 置为重复字符的下一个,继续从此处开始扫描检索。注意, start 必须位于重复字符的左边或者重合。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        used = {}
        start = max_length = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_length = max(max_length, i - start + 1)
            used[c] = i
        return max_length

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution:
对于长度为 N 的数组 A,无论奇偶,其中位数都为:

(L + R)/2 = (A[(N-1)/2] + A[N/2])/2
N        Index of L / R
1               0 / 0
2               0 / 1
3               1 / 1  
4               1 / 2      
5               2 / 2
6               2 / 3
7               3 / 3
8               3 / 4

为了解决两个数组的问题,我们可以假想一些位置(用 ‘#’ 表示)出来,数字本身也是一种位置:

[6 9 13 18]  ->   [# 6 # 9 # 13 # 18 #]    (N = 4)
position index     0 1 2 3 4 5  6 7  8     (N_Position = 9)

[6 9 11 13 18]->   [# 6 # 9 # 11 # 13 # 18 #]   (N = 5)
position index      0 1 2 3 4 5  6 7  8 9 10    (N_Position = 11)

如上,任意长度数组均有 2 * N + 1 个位置,切剪切位置 CutPosition 总为 N。因此 index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2。

对于两个数组,我们需要找到两个 CutPosition(每个数组各一个),因此两个数组一共有 2N1 + 2N2 + 2 个位置,左边 N1 + N2 个,右边 N1 + N2 个(剩下两个为两个剪切位置)。因此确定数组 A2 的剪切位置 C2 = k 时,A1 的剪切位置 C1 = N1 + N2 - k。例如 C2 = 2, 则 C1 = 4 + 5 - C2 = 7。

 [# 1 # 2 # 3 # (4/4) # 5 #]    

 [# 1 / 1 # 1 # 1 #]   

同时还需满足条件, A1左长度 + A2左长度 = A1右长度 + A2右长度 并且 L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2。这些条件满足时,则 中位数为:(max(L1, L2) + min(R1, R2)) / 2

因为是已排序数组,因此 L1 <= R1 和 L2 <= R2 已经满足。如果 L1 > R2 ,说明 A1 左半部分大数比较多,因此需要将 C1 左移(等同于 C2 右移)。如果 L2 > R1,说明 A2 左半部分大数比较多,因此需要将 C2 左移。至此,我们可以用二分法完成剪切点的搜索,算法复杂度为 O(log(min(M,N)))。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        INT_MAX = 999999999
        INT_MIN = -INT_MAX
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 < n2:
            return self.findMedianSortedArrays(nums2, nums1)
        low, high = 0, n2 * 2
        while low <= high:
            mid2 = (low + high) // 2  # cut 2
            mid1 = n1 + n2 - mid2  # cut 1
            l1 = INT_MIN if mid1 == 0 else nums1[(mid1 - 1) // 2]
            l2 = INT_MIN if mid2 == 0 else nums2[(mid2 - 1) // 2]
            r1 = INT_MAX if mid1 == n1 * 2 else nums1[mid1 // 2]
            r2 = INT_MAX if mid2 == n2 * 2 else nums2[mid2 // 2]
            if l1 > r2:
                low = mid2 + 1
            elif l2 > r1:
                high = mid2 - 1
            else:
                return (max(l1, l2) + min(r1, r2)) / 2
        return -1

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.

Example1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example2:

Input: "cbbd"

Output: "bb"

Solution:
最简单的方法,对每个字符串,分别向左向右进行检索,判断是否为同一个字符,是的话继续向左向右进行检索,直到找到最长的。

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        if l < 2:
            return s
        start = 0
        max_length = 1
        for i, c in enumerate(s):
            if l - i <= max_length // 2:
                break
            j = k = i
            while k < l - 1 and s[k + 1] == s[k]:
                k += 1  # Skip duplicate characters.
            while j > 0 and k < l - 1 and s[k + 1] == s[j - 1]:
                j -= 1
                k += 1
            new_length = k - j + 1
            if new_length > max_length:
                max_length = new_length
                start = j
        return s[start:start + max_length]

⬆️

写的不错,帮助到了您,赞助一下主机费~

扫一扫,用支付宝赞赏
扫一扫,用微信赞赏
LeetCode-32 2018-10-22

暂无评论~~