给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
方法：滑动窗口
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
#滑动窗口
# stack=[]
max=0
first_pos=0 #记录滑动窗口的起点
while first_pos<len(s):
stack=[]
pos=first_pos
while pos<len(s) and s[pos] not in stack :
stack.append(s[pos])
pos+=1
first_pos=pos-len(stack)+1 #更新滑动窗口的起点，去掉栈内重复的首字母即可
if len(stack)>max:
max=len(stack)
return max
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
s3=ListNode(None)
result=s3
jinwei=0
while l1 or l2:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
ret=x+y+jinwei
s3.next=ListNode(ret%10)
s3=s3.next
if ret>=10:
jinwei=1
else:
jinwei=0
if l1:
l1=l1.next
if l2:
l2=l2.next
if jinwei==1: #特例如l1=[9,9,9,9,9,9,9] l2=[9,9,9,9]
s3.next=ListNode(1)
return result.next
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2**31, 2**31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
s=str(x)
minus=0
res=[]
if s[0]=="-":
minus=1
if minus==0:
for i in range(-1,-(len(s)+1),-1):
res.append(s[i])
else:
for i in range(-1,-len(s),-1):
res.append(s[i])
if minus:
result=int("-"+"".join(res))
else:
result=int("".join(res))
if result>2147483647 or result<-2147483648: #[−2**31, 2**31 − 1]
return 0
return result
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
#必须射出的最小弓箭数
#先排列
points.sort(key=lambda ballon:ballon[1])
pos=points[0][1] #记录首次射出箭的位置
ans=1 #首次射出一支箭
for i in range(len(points)):
if points[i][0]>pos: #当出现气球的Xstart要超出已有箭的射程范围
pos=points[i][1] #更新箭的射出位置
ans+=1 #添加一支箭
#如果有完全被重叠的小区间 符合要求嘛？按照Xend排序的，符合要求
#比如points =[[1,10],[2,3],[7,8]]
#sort完points =[[2,3],[7,8],[1,10]]
return ans
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
#得到的index记得加1
##二分法
n=len(numbers)
left,right=0,n-1
while left<right:
if numbers[left]+numbers[right]==target: ##关于是否相等的判断放到后面可以提高速度，因为之前的判断一般都是>target或者
return [left+1,right+1]
elif numbers[left]+numbers[right]>target:
right-=1
else:
left+=1
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# #dp[i]代表偷窃到第i个房子时，可以偷窃到的最大金额(第i个房子还没有偷)
n=len(nums)
dp=[0]*(n+1)
dp[1]=nums[0]
for i in range(2,n+1):
dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
#dp[i-2]+nums[i-1]表示不偷i-2但偷i-1；dp[i-1]表示i-1前偷窃到的最大金额
#之前有个小疑惑，就是最大金额为什么不可以是dp[i-3]+nums[i]，这里要理解dp[i]表示第i个房子还没有偷时已偷到手的最大金额
return dp[n]
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
本题可以二分法找到一个大于左右相邻元素的target
但是疑问在于不对数组进行排序的前提下，二分法怎么保证总可以找到一个峰值元素
1. 由于 nums[-1] = nums[n] = -∞，所以只要nums数组不为空，总存在一个峰值
2. 每次二分找到中间的数，比较它和左右相邻数的大小，如果它比左右数都要大，lucky,峰值就这么被找到了。如果不是，设令右边的值大于它，那么可以推断得到它的右边一定存在一个峰值，因为 nums[n] = -∞，继续往右边找总能找到一个峰值；如果右边的值小于它，左边的值大于它，由于nums[-1] = -∞，那么左边总有一个峰值，继续往左边找
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
"方法一：虽然时间复杂度是o(n),但是值得学习的代码"
# 1.生成随机数，在数组中随机位置开始找
# 2.为了方便考虑nums[-1] = nums[n] = -∞，虽然可以重新设一个数组，但是为降低空间复杂度，用一个函数
# n=len(nums)
# #例外case
# if n==1:
# return nums
# idx=random.randint(0,n-1)
# def get(idx):
# if idx==-1 or idx==n:
# return float("-inf")
# else:
# return nums[idx]
# while not (get(idx-1)get(idx+1)):
# if get(idx)
# idx+=1
# else:
# idx-=1
# return idx
"方法二：二分查找"
n=len(nums)
#例外case
def get(idx):
if idx==-1 or idx==n:
return float("-inf")
else:
return nums[idx]
# left<=right,等于right的情况
left,right,ans=0,n-1,-1
while left<=right:
mid=(left+right)//2
if (get(mid-1)<get(mid) and get(mid)>get(mid+1)):
return mid
if get(mid)<get(mid+1):
left=mid+1
else:
right=mid-1
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）