LeetCode刷题(1-100)

2018-08-01

字数统计: 1.8k字 | 阅读时长: 8分

× 文章目录

1. 1. Two Sum（求两个数的和）
2. 2. Add Two Numbers（单链表表示的两个数相加）
3. 3. Longest Substring Without Repeating Characters（最长非重复子字符串）
4. 4. Median of Two Sorted Arrays（两个排序数组的中位数）
5. 5. Longest Palindromic Substring（最长回文子串）
6. 6. 006-ZigZag Conversion（Z字型转换）
7. 7. Reverse Integer（翻转整数）
8. 7. String to Integer (atoi) （字符串转成整数）

　　LeetCode是一个准备面试非常有用的网站，是每个程序员求职面试必刷的题库之一，中文版本网站领扣。其中题目按照难易程度分为易，中，难三等，同时也按照专题进行了分类。本博客记录本人的刷题过程，参考了很多大神的优质实现，权当笔记，供自己以后复习之用。

1. Two Sum（求两个数的和）

　　题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
　　方法一：双重循环，时间按复杂度:O(n)
　　方法二：通过哈希表/字典存储数组元素及位置，判断target - nums[i]是否在字典中,同样元素不能重复：下标不能一样。时间复杂度：O(n),空间复杂度：O(n)
　　方法三：排序后，左右“指针”对应数字求和，若小于target，小指针往后移动(low++),若大于target，大指针往前移动(high—)，相等，返回结果。时间复杂度：O(n),空间复杂度：O(1)

class Solution:
	
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = dict()
        res = []
        for ind, i in enumerate(nums):
            d[i] = ind
        for ind, i in enumerate(nums):
            tmp = target - i
            if tmp in d and ind != d[tmp]:
                res.append(ind)
                res.append(d[tmp])
                return res
        return res
	
	def twoSum2(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = []
        nums = [(k,v) for v, k in enumerate(nums)]
        nums = sorted(nums, key=lambda d:d[0])
        low = 0
        high = len(nums) -1
        while low < high:
            sum2 = nums[low][0] + nums[high][0]
            if sum2 == target:
                res.append(nums[low][1])
                res.append(nums[high][1])
                return res
            elif sum2 < target:
                low += 1
            else:
                high -= 1
                
        return res

2. Add Two Numbers（单链表表示的两个数相加）

　　题目：给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
　　你可以假设除了数字 0 之外，这两个数字都不会以零开头。
　　示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

　　方法：遍历链表相加sum(链表为空、进位)，新节点数字为（sum%10），进位为sum/10(python中使用//整除)，注意考虑最终是否还有进位。

# 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
        """
        jinwei = 0
        res = ListNode(0)
        cur1 = l1
        cur2 = l2
        cur = res
        while cur1 != None or cur2 != None:
            x = cur1.val if cur1 != None else 0
            y = cur2.val if cur2 != None else 0
            sum2 = jinwei + x + y
            jinwei = sum2 // 10
            cur.next = ListNode(sum2 % 10)
            cur = cur.next
            if cur1 != None:cur1 = cur1.next
            if cur2 != None:cur2 = cur2.next            
        if jinwei > 0:
            cur.next = ListNode(jinwei) 
        return res.next

3. Longest Substring Without Repeating Characters（最长非重复子字符串）

　　题目：给定一个字符串，找出不含有重复字符的最长子串的长度。
　　示例：

输入: “pwwkew”
输出: 3
解释: 无重复字符的最长子串是 “wke”，其长度为 3。
请注意，答案必须是一个子串，”pwke” 是一个子序列而不是子串。

　　方法：用字典charindex存储每个字符的位置，start表示子串开始位置，更新策略为：如果当前字符已经在字典存在，并且start小于charindex[char] + 1,同时维护最长不重复子串长度res。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        charindex = {}
        res = 0
        start = 0
        for ind, char in enumerate(s):
            if char in charindex:
                start = max(charindex[char] + 1, start)
            res = max(res, ind-start+1)
            charindex[char] = ind
        return res

4. Median of Two Sorted Arrays（两个排序数组的中位数）

　　题目：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 不同时为空。
　　示例：

nums1 = [1, 3]，nums2 = [2]，中位数是 2.0
nums1 = [1, 2]，nums2 = [3, 4]，中位数是 (2 + 3)/2 = 2.5

　　方法：参考[here],

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) // 2
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) // 2
            if after-i-1 < 0 or a[i] >= b[after-i-1]:
                hi = i
            else:
                lo = i + 1
        i = lo
        nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0

5. Longest Palindromic Substring（最长回文子串）

　　题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
　　示例：

输入: “babad”
输出: “bab”
注意: “aba”也是一个有效答案。

　　方法一：暴力枚举，枚举所有子串（最长子串开始）+判断子串是否为回文，时间复杂度为：O(n^3)
　　方法一：动态规划，时间复杂度为：O(n^2)
　　方法二：Manacher算法，时间复杂度为：O(n),分析参考最长回文子串（Longest Palindromic Substring）——三种时间复杂度的解法

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        s='#'+'#'.join(s)+'#' 
  
        RL=[0]*len(s)  
        MaxRight=0  
        Pos=0  
        Maxlen=0  

        for i in range(len(s)):  
            if i < MaxRight: 
                RL[i]=min(RL[2*Pos-i],MaxRight-i)  
            else:  #i在maxright右边，以i为中心的回文串还没扫到，此时，以i为中心向两边扩展  
                RL[i]=1 #RL=1：只有自己  

            #以i为中心扩展，直到左 != 右or达到边界(先判断边界)  
            while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:  
                RL[i]+=1  

            #更新Maxright pos:  
            if RL[i]+i-1>MaxRight:  
                MaxRight=RL[i]+i-1  
                Pos=i  

        #更新最长回文子串的长;  
        Maxlen=max(RL)  
        s=s[RL.index(Maxlen)-(Maxlen-1):RL.index(Maxlen)+(Maxlen-1)]  
        s=s.replace('#','')  
        return s

6. 006-ZigZag Conversion（Z字型转换）

　　题目：将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数：
　　P A H N
　　A P L S I I G
　　Y I R
　　示例：

输入: s = “PAYPALISHIRING”, numRows = 4
输出: “PINALSIGYAHRPI”

　　方法：数学规律，第一行和最后一行的字母下标数（下标数从0开始）可以看成一个等差数列，中间的几行也有规律。把满列的和单列的分成两部分来看，满列的按等差数列来做，单列的用单列的规律加进去。

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows <= 1:
            return s
        n = len(s)
        ans = []
        step = 2 * numRows - 2
        for i in range(numRows):
            for j in range(i, n, step):
                ans.append(s[j])
                if i != 0 and i != numRows - 1 and j - 2*i + step < n:
                    ans.append(s[j - 2*i + step])
                    
        return "".join(ans)

7. Reverse Integer（翻转整数）

　　题目：给定一个 32 位有符号整数，将整数中的数字进行反转。

示例：输入: 123输出: 321
输入: -123 输出: -321

　　方法：通过求余数求商法进行操作。

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        res= 0
        tmp = x if x > 0 else -x
        while tmp != 0:
            res = res * 10 + tmp % 10
            tmp = tmp // 10

        if res > 2**31-1 or res < (-2)**31:
            res = 0

        res = res if x > 0 else -res
        return res