目录：
1. 两数之和
3. 无重复字符的最长子串
7. 整数反转
8. 字符串转换整数 (atoi)
217. 存在重复元素
219. 存在重复元素 II
238. 除自身以外数组的乘积
345. 反转字符串中的元音字母
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
解题思路如下：
这道题的重点在于首先找到这2个数，且输出的值不重复。我们就做2个for循环，然后再输出即可
代码：
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ lenth = len(nums) for i in range(lenth): for j in range(i+1,lenth): c=nums[i]+nums[j] if c==target: return [i,j]
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
解题思路：使用滑动思想，只要该字符没有出现，都可以添加进去，如果遇到重复字符，需要往后移动，具体看代码吧，表达能力差
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s=='': return 0 max_s=[s[0]] #最长子串 max_l=1 #最长子串长度 start , end =0,1 #子串起始位置 while end<len(s): #循环截止条件 if s[end] not in s[start:end] and end<len(s)-1: #当结束位置的元素不在start:end中， #end+1,但是要注意end不能是最后一个 end=end+1 elif s[end] not in s[start:end] and end==len(s)-1: #对前面的条件的补充 max_s=s[start:end+1] max_l=max(max_l,len(max_s)) break else: max_s=s[start:end] #最大子串 max_l=max(max_l,len(max_s)) #最大子串长度 start=max_s.index(s[end])+start+1 #最大子串的开始位置 end=end+1 #结束位置 #print(max_l,max_s,start,end) return max_l
7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
解题思路：
翻转可以使用str[::-1]实现，然后注意一下负数，以及尾部是0（反正类似100,10,1000之类的），这个可以使用int(解决）
代码：
class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ if x>=0: x=str(x) x=x[::-1] if int(x)<=2**31-1: return int(x) else: return 0 else: x=abs(x) x=str(x) x=x[::-1] if int(x)<=2**31: return -int(x) else: return 0
8. 字符串转换整数 (atoi)
请你来实现一个 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 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
解题思路：首先去空格，然后读取字符，注意首位一定是list('+-1234567890')中的一个，然后后面的只能是数字，还的找到循环中断的条件，最后转换成int，然后判断怎么输出好
class Solution(object): def myAtoi(self, s): """ :type s: str :rtype: int """ s = s.lstrip() a=list('+-1234567890') b=list('1234567890') l='' for i in range(len(s)): if i==0 and s[i] in a: l=l+s[i] elif i>=1 and s[i] in b: l=l+s[i] else: break if l=='' or l=='+' or l=='-': return 0 else: l=int(l) if l>2147483647: return 2147483647 elif l<(-2147483648): return -2147483648 else: return l
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
示例 4：
输入：x = -101
输出：false
解题思路：
这个也可以使用翻转的思路str[::-1]，然后注意一下细节问题
代码：
class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return False elif x==0: return True else: x=str(x) if x==x[::-1]: return True else: return False
13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。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:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
解题思路：
首先构造一个字典，将7个字符作为key，对应值作为value，然后每一个位置的值都要和下一个位置的值比较，如果后面的值得等级比前面的值得等级大，则前面的值需要减，最后将结果全部加起来
代码：
class Solution(object): def romanToInt(self, s): """ :type s: str :rtype: int """ dict1={"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000} lenth = len(s) a=0 for i in range(lenth): if i<lenth-1: if dict1[s[i]]>=dict1[s[i+1]]: a=a+dict1[s[i]] else: a=a-dict1[s[i]] else: a=a+dict1[s[i]] return a
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
解题思路：
利用max(str),min(str)得到排序好的字段，后面只需要比较这2个字段即可
代码
class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return "" s1 = min(strs) s2 = max(strs) for i,x in enumerate(s1): if x != s2[i]: return s2[:i] return s1
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
解题思路：
该题重点是括号成对且顺序不能乱，因此我们只需要采取消消乐的思想，将一对对消成空即可
代码：
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ while '{}' in s or '()' in s or '[]' in s: s = s.replace('{}', '') s = s.replace('[]', '') s = s.replace('()', '') return s == ''
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ def get_pwd(str, num): if(num == 1): for x in str: yield x else: for x in str: for y in get_pwd(str, num-1): yield x+y l=[] strKey="()" import copy for x in get_pwd(strKey,2*n): s=copy.deepcopy(x) while '()' in s : s = s.replace('()', '') if s=='': l.append(x) return l
26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
解题思路：nums[:]=去重后的list，还得注意set(list)之后的顺序问题，set之后改变了顺序，如果我们使用set，则需要sort
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ l = [] for i in nums: if i not in l: l.append(i) nums[:]=l return len(nums)
方法二：
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ a=list(set(nums)) a.sort() nums[:]=a return len(nums)
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
解题思路：
本来想使用2次循环的思路，但是超时， 翻看了一下别人的做法，发现一个比较好的思路，具体看代码
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(1, len(nums)): nums[i]= nums[i] + max(nums[i-1], 0) return max(nums)
125. 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
解题思路：本来想使用正则表达式，但是用得不是很熟练，就使用简单的枚举了
class Solution(object): def isPalindrome(self, s): """ :type s: str :rtype: bool """ s=s.lower() l=[] for i in s: if i in 'qwertyuiopasdfghjklzxcvbnm0987654321': l.append(i) s=''.join(l) if s==s[::-1]: return True else: return False
122. 买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题思路：这个比之前的股票题简单很多，我们只需要求出后面一个减去前面的值，然后将大于0的值全部加起来，得到就是全部收益
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ import numpy as np s=0 for i in np.diff(prices): if i>0: s=s+i return s
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
解题思路：这个更加简单了，只需要比较原来的长度和set之后的长度
class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ l=len(nums) l1=len(set(nums)) if l>l1: return True else: return False
219. 存在重复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
解题思路：详情见代码
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: l_ = len(nums) if l_ == len(set(nums)): #如果长度相等，则没有重复值 return False else: for i in range(l_): if nums[i] in nums[i+1:i+k+1]: #如果能在i+k+1内找到和第i个值相等的值，则返回true，并且找到即可中断循环break return True break elif i==l_-1: #否则等到i为最后一个未知，则反正false return False
238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
解题思路：1、本来是想将nums的乘积计算出来，然后做一次for循环，每次除以该位置的值即可，但是如果元素中存在着0，这种做法就不适用了
2、每次计算一次乘积，该方法超时了
3、使用进出思想，减少乘的计算，只需要原来的乘/出去的*进来的，最后注意一下0，减少了操作时间
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: def f(x,a): if a > 1: return f(x,a-1)*x[a-1] else: return x[0] l_= len(nums) s=f(nums[1:],l_-1) #先计算不要第一个数后的乘 l=[s] in_num , ou_num = 1,1 for i in range(1,l_): #从第二个元素开始 in_num = nums[i-1] #进来的元素 out_num = nums[i] #出去的元素 if out_num!=0: s=int(s/out_num*in_num) #出去的元素非0，就可以直接计算 else: s=f([nums[j] for j in range(0,l_) if j!=i ],l_-1) #出去的元素为0，等重新再计算乘 l.append(s) return l
345. 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1：
输入："hello"
输出："holle"
示例 2：
输入："leetcode"
输出："leotcede"
解题思路：看代码，主要是记住这个位置和值得使用
class Solution: def reverseVowels(self, s: str) -> str: yuanyin = list('aeiouAEIOU') #元音字母 a='' l=[] for i in range(len(s)): if s[i] in yuanyin: a=a+s[i] #保存s出现的元音字母 l.append(i) #保存出现的位置 a=a[::-1] #反转元音 s=list(s) #主要是str不能直接切片赋值 for i,j in enumerate(l): #只需要遍历出现的位置 s[j]=a[i] #直接替换 return ''.join(s) #再合并
367. 有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
解题思路：只要能找到一个正整数n*n=num,即可，本来是想使用for循环的，但是超时警告，然后转为while
class Solution(object): def isPerfectSquare(self, num): """ :type num: int :rtype: bool """ l=[] i=1 while i*i<=num: if i**2==num: l.append(i) i=i+1 if len(l)>=1: return True else: return False
349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
解题思路：首先将2个数组合在一起，在set()去重，然后for循环去重后的set，如果在2个数组中都能找到，则添加到一个list里面去，最后输出list
class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l=[] for i in set(nums1+nums2): if i in nums1 and i in nums2: l.append(i) return l
350. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解题思路：这个和上面的思路基本一致，只不过在添加到list里面时，根据元素出现最小次数觉得生成元素的个数
class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l=[] for i in set(nums1+nums2): if i in nums1 and i in nums2: n=min(nums1.count(i),nums2.count(i)) l=l+([i]*n) return l
374. 猜数字大小
猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。
示例 1：
输入：n = 10, pick = 6
输出：6
示例 2：
输入：n = 1, pick = 1
输出：1
示例 3：
输入：n = 2, pick = 1
输出：1
示例 4：
输入：n = 2, pick = 2
输出：2
解题思路：本来想使用while循环，在1-n里面选择答案，但是这种方法很容易超时，因此改用二分法去寻找，每次使用i~(n-i)/2（就是说i~n的中值）寻找，猜中值和pick是否相等
# The guess API is already defined for you. # @param num, your guess # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num): class Solution(object): def guessNumber(self, n): """ :type n: int :rtype: int """ left = 1 right = n while left < right: mid = left + (right - left) // 2 #二分法，也即是说在1~(n-i)/2里面去寻找 if guess(mid) == 1: left = mid + 1 else: right = mid return left
434. 字符串中的单词数
统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。
解题思路：str.split(' ')，然后再注意一下分割之后是否是空格，将非空格的装到一个list去，然后计算list的长度
class Solution(object): def countSegments(self, s): """ :type s: str :rtype: int """ l = (s.split(' ')) l1=[] for i in l: if i!='': l1.append(i) return len(l1)