2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
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 32 class Solution : def addTwoNumbers (self, l1: Optional [ListNode], l2: Optional [ListNode] ) -> Optional [ListNode]: num_l1=num_l2=0 mult=1 ''' 将链表中的data提出，累加为十进制数 ''' while l1: num_l1+=l1.val*mult mult*=10 l1=l1.next mult=1 while l2: num_l2+=l2.val*mult mult*=10 l2=l2.next num=num_l1+num_l2 head=ListNode() probe=head if num==0 : return head while num>0 : probe.next =ListNode(num%10 ) probe=probe.next num //=10 return head.next
学习了链表的定义和用法，代码思路基本是照抄题解
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
中等难度题，第一种方法是刚学习时的简单想法，时间复杂度到了n3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def lengthOfLongestSubstring (self, s: str ) -> int : c='' n=0 i=0 while i<len (s): if s[i] not in c: c+=s[i] else : n=max (n,len (c)) i+=c.find(s[i])-len (c)+1 c=s[i] i+=1 n=max (n,len (c)) return n
学习数据结构后使用的两种新方法，实际上动态规划和第一种相同
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def lengthOfLongestSubstring (self, s: str ) -> int : if not s: return 0 dp, res = '' , 0 for item in s: if item not in dp: dp += item else : if dp[-1 ] == item: dp = item else : dp = dp[dp.find(item)+1 :] + item res = max (res, len (dp)) return res
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution : def lengthOfLongestSubstring (self, s: str ) -> int : if not s: return 0 res, dic = 1 , {} i, j = -1 , 0 while j < len (s): if s[j] in dic: i = max (i,dic[s[j]]) dic[s[j]] = j res = max (j-i, res) j += 1 return res
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果
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 class Solution : def myAtoi (self, str : str ) -> int : str = str .lstrip() if not str : return 0 flag1, flag2 = False , False if str [0 ] == '+' : flag1, flag2 = True , False if str [0 ] == '-' : flag1, flag2 = True , True if flag1: if len (str ) == 1 or not str [1 ].isdigit(): return 0 else : if not str [0 ].isdigit(): return 0 i = 1 while i < len (str ): if not str [i].isdigit(): break i += 1 num = int (str [0 :i]) if not flag1 else int (str [1 :i]) if flag2: num = -num if num < -2 ** 31 : num = -2 ** 31 elif num >= 2 ** 31 : num = 2 ** 31 - 1 return num
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
1 2 3 4 5 6 7 class Solution : def searchRange (self, nums: List [int ], target: int ) -> List [int ]: a = bisect_left(nums,target) b = bisect_right(nums,target) if a == b: return [-1 ,-1 ] else : return [a,b-1 ]
实现 pow(x , n ) ，即计算 x 的 n 次幂函数（即，x^n）。
1 2 3 4 5 6 7 8 9 10 class Solution : def myPow (self, x: float , n: int ) -> float : if x == 0 : return 0 if n < 0 : x, n = 1 /x, -n res = 1 while n: if n & 1 : res *= x x *= x n >>= 1 return res
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
1 2 3 4 5 class Solution : def maxSubArray (self, nums: List [int ] ) -> int : for i in range (1 ,len (nums)): nums[i] += max (nums[i-1 ], 0 ) return max (nums)
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution : def exist (self, board: List [List [str ]], word: str ) -> bool : def dfs (i,j,k ): if not 0 <= i < len (board) or not 0 <= j < len (board[0 ]) or board[i][j] != word[k]: return False if k == len (word) - 1 : return True board[i][j] = '' res = dfs(i+1 ,j,k+1 ) or dfs(i-1 ,j,k+1 ) or dfs(i,j+1 ,k+1 ) or dfs(i,j-1 ,k+1 ) board[i][j] = word[k] return res for i in range (len (board)): for j in range (len (board[0 ])): if dfs(i,j,0 ): return True return False
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历 ， inorder 是同一棵树的中序遍历 ，请构造二叉树并返回其根节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def buildTree (self, preorder: List [int ], inorder: List [int ] ) -> Optional [TreeNode]: def recur (root,left,right ): if left > right: return node = TreeNode(preorder[root]) i = dic[preorder[root]] node.left = recur(root+1 , left, i-1 ) node.right = recur(root+1 +i-left, i+1 , right) return node dic = {} for i in range (len (inorder)): dic[inorder[i]] = i return recur(0 , 0 , len (inorder)-1 )
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def pathSum (self, root: Optional [TreeNode], targetSum: int ) -> List [List [int ]]: path, res = [], [] def dfs (root,target ): if not root: return path.append(root.val) target -= root.val if target == 0 and not root.left and not root.right: res.append(list (path)) dfs(root.left,target) dfs(root.right,target) path.pop() dfs(root,targetSum) return res
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
1 2 3 class Solution : def reverseWords (self, s: str ) -> str : return ' ' .join(s.split()[::-1 ])
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class MinStack : def __init__ (self ): self .lst = [] self .lst2 = [] def push (self, val: int ) -> None : self .lst.append(val) if not self .lst2 or val <= self .lst2[-1 ]: self .lst2.append(val) def pop (self ) -> None : popval = self .lst.pop() if self .lst2[-1 ] == popval: self .lst2.pop() def top (self ) -> int : return self .lst[-1 ] def getMin (self ) -> int : return self .lst2[-1 ]
编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
1 2 3 4 5 6 7 8 9 class Solution : def searchMatrix (self, matrix: List [List [int ]], target: int ) -> bool : i, j = len (matrix) - 1 , 0 while 0 <= i < len (matrix) and 0 <= j < len (matrix[0 ]): if matrix[i][j] > target: i -= 1 elif matrix[i][j] < target: j += 1 else : return True return False
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def nthUglyNumber (self, n: int ) -> int : f = [1 ] * n a = b = c = 0 for i in range (1 ,n): n2, n3, n5 = 2 * f[a], 3 * f[b], 5 * f[c] f[i] = min (n2, n3, n5) if f[i] == n2: a += 1 if f[i] == n3: b += 1 if f[i] == n5: c += 1 return f[-1 ]
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
1 2 3 4 5 6 7 8 class Solution : def integerBreak (self, n: int ) -> int : if n < 4 : return n-1 x = n // 3 y = n % 3 if y == 0 : return 3 **x elif y == 1 : return 3 **(x-1 )*4 else : return 3 **x*2
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
1 2 3 4 5 6 7 8 9 10 class Solution : def findNthDigit (self, n: int ) -> int : res, k, nine = 0 , 0 , 0.9 while res < n: nine *= 10 k += 1 res += nine * k x, y = (int (res) - n) // k, (int (res) - n) % k pur = 10 **k - 1 - x return int (str (pur)[-1 -y])
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def countSubstrings (self, s: str ) -> int : res = 0 n = len (s) for k in range (2 *n-1 ): l, r = k//2 , k//2 + k%2 while l>=0 and r<=n-1 and s[l] == s[r]: res += 1 l -= 1 r += 1 return res
