Leetcode字符串算法
【LeetCode-python 7.整数反转】
难度:简单 类型: 字符串给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例1
输入: 123
输出: 321
示例2
输入: -123
输出: -321
示例3
输入: 120
输出: 21
代码实现
class Solution: def reverse(self, x: int) -> int: sign = 1 if x>0 else -1 stringre = str(abs(x)) sumre = 0 for num, value in enumerate(stringre): sumre += int(value)*(10**int(num)) return sign*sumre*(sumre<2**31)
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
sign = 1 if x>0 else -1
x = abs(x)
stack = []
while x>=1:
stack.append(x%10)
x = x / 10
res = 0
i = 0
while stack:
res += stack.pop() * 10**i
i += 1
return res*sign*(res<2**31)
【LeetCode-python 14.最长公共前缀】
难度:简单 类型: 数组,字符串
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例1
输入: ["flower","flow","flight"]
输出: "fl"
示例2
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
思路:
重要用python中的zip函数, 它接收可迭代的对象, 把所有元素中,每个元素对应的元素,打包成元祖为元素的列表(现在是对象需要用list转换)
例如:
lis = ['fdss','frge']
lisx = list(zip(*lis))
print(lisx)
作者:Rye_frenzy
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/my-leetcode-share-4-by-rye_frenzy/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: s = "" for i in zip(*strs): if len(set(i)) == 1: s += i[0] else: break return s
3.无重复字符的最长子串
难度:中等 类型: 字符串、双指针
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路
双指针:
指针l指在头,另一个指针r滑动遍历,在字典中记录遇到过的字符及下标
若指针r指向的字符没有出现过,记录并更新当前字串的长度
若出现过,l移到上次出现的坐标的下一位,不用比较当前的长度,因为当前的长度一定小于上一次的长度
直到r指向字符串最后一位
代码实现
class Solution: def romanToInt(self, s: str) -> int: listdic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000} sum_result = 0 for k in range(0,len(s)-1): if listdic[s[k]] < listdic[s[k+1]]: sum_result -= int(listdic[s[k]]) else: sum_result += int(listdic[s[k]]) sum_result += int(listdic[s[-1]]) return sum_result
443. 压缩字符串
难度简单给定一组字符,使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。
在完成原地修改输入数组后,返回数组的新长度。
进阶:
你能否仅使用O(1) 空间解决问题?
class Solution(object): def compress(self, chars): anchor = write = 0 for read, c in enumerate(chars): if read + 1 == len(chars) or chars[read + 1] != c: chars[write] = chars[anchor] write += 1 if read > anchor: for digit in str(read - anchor + 1): chars[write] = digit write += 1 anchor = read + 1 return write
643. 子数组最大平均数 I
https://leetcode-cn.com/problems/maximum-average-subarray-i/
class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: sum_all = max_num = sum(nums[0:k]) for i in range(k, len(nums)): sum_all = sum_all + nums[i] - nums[i-k] max_num = max(max_num, sum_all) return max_num/k 题目解法:采用滑动窗口,截取减枝的算法