Leetcode_Python_Medium

Posted on

2. Add Two Numbers

题目描述

给出两个 非空 的链表( linked lists)用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

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

Solution

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
26
27
28
29
30
31
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = curr = ListNode(0)
        carry = 0 # 进位
        while l1 or l2:
            # 从低到高 逐位相加
            sum = carry
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            curr.next = ListNode(sum%10)  # 个位保留 十位做进位
            curr = curr.next
            carry = sum / 10
        if carry > 0: # 特别注意 两个链表都加完后是否还有进位
            curr.next = ListNode(carry)
        return head.next

注意

1.Python2用/ Python3用 // 表示下取整的除法
2.链表的构建

1
2
3
4
5
6
head = curr = ListNode(0)
...
curr.next = ListNode(XX)
curr = curr.next
...
return head.next

3.生成链表的方法及本题测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def generateList(l: list) -> ListNode:
    prenode = ListNode(0)
    lastnode = prenode
    for val in l:
        lastnode.next = ListNode(val)
        lastnode = lastnode.next
    return prenode.next


def printList(l: ListNode):
    while l:
        print("%d, " %(l.val), end = '')
        l = l.next
    print('')

if __name__ == "__main__":
    l1 = generateList([1, 5, 8])
    l2 = generateList([9, 1, 2, 9])
    printList(l1)
    printList(l2)
    s = Solution()
    sum = s.addTwoNumbers(l1, l2)
    printList(sum)

3. Longest Substring Without Repeating Characters

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。。

示例

1
2
3
4
5
6
7
8
9
10
11
12
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

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

Solution1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0 # 储存最大长度
        start = 0 # 记录子串开始的index
        substring = {}
        for index, c in enumerate(s):
            # 不断记录下子串，直到出现重复字符，记录下原子串的长度，
            # 并丢弃原子串中该字符及之前的字符（更新start位置），将新的字符加入子串中
            if c in substring and substring[c] >= start:
                max_len = max(max_len, index-start)
                start = substring[c] + 1
            substring[c] = index
        return max(max_len, len(s) - start)  #遍历到最后的一串无重复字符子串长度为len(s)-start

Solution2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        substring = ""
        max_len = 0
        for c in s:  
            index = substring.find(c)  # 直接对字符串操作
            if index == -1:
                substring += c
            else:
                max_len = max(max_len, len(substring))         
                substring = substring[index+1:] + c  #注意这里不是[index+1:-1]
            
        return max(max_len, len(substring))

5. Longest Palindromic(回文) Substring ！！！！！！！！！！！！！！！！

题目描述

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

示例

1
2
3
4
5
6
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

Solution

6. ZigZag Conversion (Z字形变换)

相关标签: 字符串

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

1
2
3
L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数 string convert(string s, int numRows);

示例

1
2
3
4
5
6
7
8
9
10
11
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2:
            return s
        row = ["" for _ in range(numRows)]
        row_id = 0
        flag = -1
        for c in s:
            row[row_id] += c
            if row_id==0 or row_id == numRows - 1:
                flag = -flag
            row_id += flag
        return "".join(row)

11. Container With Most Water

相关标签: 双指针

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

示例

1
2
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        res = 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

思路

算法流程： 设置双指针 i,j 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 res，直到 i == j 时返回 res。

指针移动规则与证明： 每次选定围成水槽两板高度 h[i],h[j]中的短板，向中间收窄 111 格。以下证明：

  • 设每一状态下水槽面积为 S(i,j),(0<=i<j<n)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i,j)=min(h[i],h[j])×(j−i)S(i, j)。
  • 在每一个状态下，无论长板或短板收窄 1格，都会导致水槽 底边宽度 −1。
  • 若向内移动短板，水槽的短板 min(h[i],h[j])可能变大，因此水槽面积 S(i,j)S(i, j)S(i,j) 可能增大。
  • 若向内移动长板，水槽的短板 min(h[i],h[j])不变或变小，下个水槽的面积一定小于当前水槽面积。

12. Integer to Roman

相关标签: 字符串

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 I。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 3
输出: "III"

输入: 4
输出: "IV"

输入: 9
输出: "IX"

输入: 58
输出: "LVIII"

输入: 1994
输出: "MCMXCIV"

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def intToRoman(self, num: int) -> str:
        res = ""
        values = [1000, 900, 500, 400,
                  100, 90, 50, 40,
                  10, 9, 5, 4,
                  1]
        symbols = ['M', 'CM', 'D', 'CD',
                   'C', 'XC', 'L', 'XL',
                   'X', 'IX', 'V', 'IV',
                   'I']
        i = 0
        while num > 0:
            count = num // values[i]
            res += "".join([symbols[i] for _ in range(count)])
            num -= count * values[i]
            i += 1
        return res

15. 3SUM

相关标签: 双指针 数组

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例

1
2
3
4
5
6
7
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

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:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        for k in range(len(nums)-2):
            if nums[k] > 0: break
            if k > 0 and nums[k] == nums[k-1]: continue
            i, j = k+1, len(nums)-1

            while i < j:
                s = nums[k] + nums[i] + nums[j]

                if s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                elif s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i-1]: i += 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                    while i < j and nums[i] == nums[i-1]: i += 1
        return res

思路

16. 3Sum Closest

相关标签: 双指针 数组

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例

1
2
3
给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = float("inf")
        for k in range(len(nums)-2):
            if k > 0 and nums[k] == nums[k-1]: continue
            i, j = k+1, len(nums)-1

            while i < j:
                s = nums[k] + nums[i] + nums[j]
                if s == target:
                    return s
                elif abs(s-target) < abs(res-target):
                    res = s
                
                if s < target:
                    i+=1
                    while i < j and nums[i] == nums[i-1]: i += 1
                elif s > target:
                    j -= 1
                    while i < j and nums[j] == nums[j+1]: j -= 1
                
        return res