Leetcode-Python3

Leetcode-Python3 [1.两数之和]

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

常规：暴力查找

常见解法：使用字典存储已出现值的下标，O(n)匹配

 1 class Solution:
 2     def twoSum(self, nums: List[int], target:int) -> List[int]:
 3         dict = {}
 4         ll = len(nums)
 5         for i in range(ll):
 6             if(target - nums[i] in dict):
 7                 return [dict[target - nums[i]], i]
 8             else:
 9                 dict[nums[i]] = i;
10                 
11 if __name__ == '__main__':
12     n = [2, 7, 11, 15]
13     tar = 9
14     s = Solution()
15     a = s.twoSum(n,tar)
16     print(a)

View Code

Leetcode-Python3 [2.两数相加]

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

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

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

解法：同时遍历，记录进位

 1 # Definition for singly-linked list.
 2 class ListNode:
 3     def __init__(self, x):
 4         self.val = x
 5         self.next = None
 6 
 7 class Solution:
 8     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
 9         dd = ListNode(0)
10         cur = dd
11         carry = 0
12         while l1 or l2:
13             num1 = l1.val if l1 else 0
14             num2 = l2.val if l2 else 0
15             sum = num1+num2+carry
16             
17             carry = sum//10
18             cur.next = ListNode(sum%10)
19             cur = cur.next
20             l1 = l1.next if l1 else None
21             l2 = l2.next if l2 else None
22         if carry:
23             cur.next = ListNode(carry)
24         return dd.next

View Code

Leetcode-Python3 [3.无重复字符的最长子串]

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

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

解法：滑动窗口 [i, j]，滑动 j 直到遇到 str[j] == str[i] ,更新最大值，并且把 i 跳转到最新出现的 str[j]字符的位置。滑动 j 的同时更新每种字符的最新下标。

 1 class Solution:
 2     def lengthOfLongestSubstring(self, s: str) -> int:
 3         st = 0
 4         udChar = {}
 5         max_ans = 0
 6         ll = len(s)
 7         for i in range(ll):
 8             if(s[i] in udChar and udChar[s[i]] >= st):
 9                 st = udChar[s[i]]+1
10             else:
11                 max_ans = max(max_ans, i-st+1)
12             udChar[s[i]] = i
13             
14         return max_ans
15

View Code

Leetcode-Python3 [4.寻找两个有序数组的中位数]

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0
示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

解法：给出的数组是有序的，要求的时间复杂度是 O(log) 往二分方向思考。

解法一：合并两个数组，排序后二分（归并排序），用python的sorted可以过...

解法二：两边同时二分，动态查找中位数。因为区间长度会动态改变，所以就转换成了二分查找第K大的数，注意边界的处理。

 1 class Solution:
 2     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
 3         ll = len(nums1)+len(nums2)
 4         if(ll%2 == 1):
 5             return self.findk(nums1, nums2, ll//2)
 6         else:
 7             return (self.findk(nums1, nums2, ll//2)+self.findk(nums1, nums2, ll//2-1))/2
 8         
 9     def findk(self, nums1, nums2, k):
10         if not nums1:
11             return nums2[k]
12         if not nums2:
13             return nums1[k]
14         i1, i2 = len(nums1)//2, len(nums2)//2
15         
16         m1, m2 = nums1[i1], nums2[i2]
17 #        print(i1, i2, k, m1, m2)
18         
19         if i1+i2 < k:
20             if m1 > m2:
21                 return self.findk(nums1, nums2[i2+1:], k-i2-1)
22             else:
23                 return self.findk(nums1[i1+1:], nums2,k-i1-1)
24         else:
25             if m1 > m2:
26                 return self.findk(nums1[:i1], nums2, k)
27             else:
28                 return self.findk(nums1, nums2[:i2], k)
29

View Code