1 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j] == target:
print (nums[i],nums[j])
return i,j
return None 思路1：暴力遍历法，注意第二次循环要从i+1开始，注意range的用法。复杂度高。
range(start, stop[, step])
hashmap = {}
for i,value in enumerate(nums):
value_need = target - value
if value_need in hashmap:
return [hashmap[value_need],i]
hashmap[value] = i
return None 思路2：哈希表法。
来源https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
标签：哈希映射
这道题本身如果通过暴力遍历的话也是很容易解决的，时间复杂度在 O(n2)
由于哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 降低时间复杂度
遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 target-nums[i] 的 key 值
如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止
如果最终都没有结果则抛出异常
时间复杂度：O(n)
2 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807 思路：先将两链表相加，之后再将其转换成新链表。注意逆序。
p1 = l1
p2 = l2
ten = 1
num1 = num2 = 0
while p1:
num1 = p1.val*ten+num1
ten = 10*ten
p1 =p1.next
ten = 1
while p2:
num2 = p2.val*ten+num2
ten = 10*ten
p2 =p2.next
result = num1+num2 #以上部分求出两个链表的和的值
result = str(result) #转换成字符串
res = []
for i in range(len(result)):
res.append(result[i])
res.reverse() #转换成List并倒序
node = ListNode(int(res[0])) #新建一个头节点，注意要把res中的元素变成int
First = node #头节点又名first
for i in res[1:]: #建立新链表
node.next = ListNode(int(i))
node = node.next
return First #返回结果
思路2：一边计算和一边建新链表，注意的是进位与两数长度不同的情况。特殊情况：
p1 = l1
p2 = l2
node = ListNode((p1.val + p2.val)%10)
First = node
if p1.val + p2.val>=10:
carry = 1
else:
carry = 0
while p1.next and p2.next:
p1 = p1.next
p2 = p2.next
if p1.val + p2.val + carry < 10:
add = p1.val + p2.val + carry
node.next = ListNode(add)
node = node.next
carry = 0
else:
add = (p1.val + p2.val + carry)%10
node.next = ListNode(add)
node = node.next
carry = 1
while p1.next: #不是if,而是while
p1 = p1.next
if p1.val + carry < 10:
add = p1.val + carry
node.next = ListNode(add)
node = node.next
carry = 0
else:
add = (p1.val + carry)%10
node.next = ListNode(add)
node = node.next
carry = 1
while p2.next:
p2 = p2.next
if p2.val + carry < 10:
add = p2.val + carry
node.next = ListNode(add)
node = node.next
carry = 0
else:
add = (p2.val + carry)%10
node.next = ListNode(add)
node = node.next
carry = 1
if carry == 1: #双冒号
node.next = ListNode(carry)
node = node.next
return First
执行用时 :
100 ms
, 在所有Python3提交中击败了
88.60%
的用户
内存消耗 :
13.2 MB
, 在所有Python3提交中击败了
52.23%
的用户 小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
3 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
if not s:
return 0
nowmax = 1
temp = []
res = []
for i in range(len(s)):
nowmax = 1
temp = [s[i]]
while i+1<len(s) and s[i+1] not in temp: #and的前后顺序
nowmax = nowmax+1
i = i+1
temp.append(s[i])
res.append(nowmax)
#print(res)
return max(res) 思路1：暴力法,最后一个测试用例超出时间限制
if not s:return 0
left = 0
lookup = []
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup: #如果出现在队列里，则一直右移，直到移除
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.append(s[i])
return max_len
这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
时间复杂度：O(n)
4 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
res = nums1+nums2
res.sort()
if len(res)%2 == 1:
return res[int((len(res) -1)/2)] #要int
else:
return (res[int(len(res)/2 - 1) ] + res[int(len(res)/2)])/2
思路：利用自带的sort函数，注意要int。
5 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
class Solution:
def longestPalindrome(self, s):
size = len(s)
if size == 0:
return ''
# 至少是 1
longest_palindrome = 1
longest_palindrome_str = s[0]
for i in range(size):
palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)
# 当前找到的最长回文子串
cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
if len(cur_max_sub) > longest_palindrome:
longest_palindrome = len(cur_max_sub)
longest_palindrome_str = cur_max_sub
return longest_palindrome_str
def __center_spread(self, s, size, left, right): #中心扩散算法
"""
left = right 的时候，此时回文中心是一条线，回文串的长度是奇数
right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数
"""
l = left
r = right
while l >= 0 and r < size and s[l] == s[r]:
l -= 1
r += 1
return s[l + 1:r], r - l - 1
6 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
方法一：回溯法
class Solution(object):
def isMatch(self, text, pattern):
if not pattern:
return not text #如果text为空，则返回True
first_match = bool(text) and pattern[0] in {text[0], '.'} #不考虑*的情况
if len(pattern) >= 2 and pattern[1] == '*':
return (self.isMatch(text, pattern[2:]) or
first_match and self.isMatch(text[1:], pattern))
#忽略这一部分，或者删除匹配串的第一个字符，若其能匹配当前位置字符
# 解释：如果发现有字符和 '*' 结合，
# 或者匹配该字符 0 次，然后跳过该字符和 '*'
# 或者当 pattern[0] 和 text[0] 匹配后，移动 text
else:
return first_match and self.isMatch(text[1:], pattern[1:]) 方法二：动态规划
使用「备忘录」递归的方法来降低复杂度。有了暴力解法，优化的过程及其简单，就是使用两个变量 i, j 记录当前匹配到的位置，从而避免使用子字符串切片，并且将 i, j 存入备忘录，避免重复计算即可。
我将暴力解法和优化解法放在一起，方便你对比，你可以发现优化解法无非就是把暴力解法「翻译」了一遍，加了个 memo 作为备忘录，仅此而已。
# 带备忘录的递归
def isMatch(text, pattern) -> bool:
memo = dict() # 备忘录
def dp(i, j):
if (i, j) in memo: return memo[(i, j)]
if j == len(pattern): return i == len(text)
first = i < len(text) and pattern[j] in {text[i], '.'}
if j <= len(pattern) - 2 and pattern[j + 1] == '*':
ans = dp(i, j + 2) or \
first and dp(i + 1, j)
else:
ans = first and dp(i + 1, j + 1)
memo[(i, j)] = ans
return ans
return dp(0, 0)
# 暴力递归
def isMatch(text, pattern) -> bool:
if not pattern: return not text
first = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return isMatch(text, pattern[2:]) or \
first and isMatch(text[1:], pattern)
else:
return first and isMatch(text[1:], pattern[1:])
作者：labuladong
链接：https://leetcode-cn.com/problems/two-sum/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
9 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 回溯法：是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。（其实本题就是深度优先搜索）
#官方题解
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']} #定义一个数字与字母对应的字典，大括号
def backtrack(combination, next_digits): #回溯函数
# if there is no more digits to check
if len(next_digits) == 0: #如果没有数字（最后一位）
# the combination is done
output.append(combination) #添加结果，字符串
# if there are still digits to check
else:
# iterate over all letters which map
# the next available digit
for letter in phone[next_digits[0]]: #对于第一位对应的每一个字母
# append the current letter to the combination
# and proceed to the next digits
backtrack(combination + letter, next_digits[1:]) #将这个字母与之前字符串相加，将数字后移
output = []
if digits:
backtrack("", digits)
return output
京公网安备 11010502036488号