【2019-07-10】leetcode(81-90)
81、Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
"""
旋转排序数组
生序旋转排序数组
查询一个目标值是否存在
"""
class Solution:
def search( self,nums: List[int], target: int) -> bool:
left=0
right=len(nums)
while(right>=left):
mid=(left+right)//2
if target==nums[mid]:
return True
if nums[mid]<num[right]:
if nums[mid] < target and nums[right] >= target:
left=mid+1
else:
right=mid-1
elif nums[mid]>num[right]:
if (nums[left] <= target and nums[mid] > target):
right = mid - 1
else:
left = mid + 1
else:
right-=1
return False
82、Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
"""
从排序链表中移除重复数据
所有重复的数据 全部删除
"""
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head==None or head.next==None:
return head
dummy=ListNode(0)
dummy.next=head
pre=dummy
cur=dummy.next
while cur!=None:
while cur.next and cur.next.val==pre.next.val:
cur=cur.next
if pre.next==cur:
pre=pre.next
else:
pre.next=cur.next
cur=cur.next
return dummy.next
83、Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
"""
移除重复元素，重复元素只保留一个
"""
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head==None or head.next==None:
return head
dummy=ListNode(0)
dummy.next=head
pre=dummy
cur=dummy.next
while cur!=None:
if pre.val!=cur.val:
pre=cur
cur=cur.next
else:
pre.next=cur.next
cur=cur.next
return dummy.next
84、 Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
柱状图
最大面积10
"""
在直方图里寻找最大的长方形
n个非负整数用直方图的高度表示
【最大面积】
栈
栈中的元素升序加入，如果下一个要加入的元素小于栈顶元素，弹出栈顶，替换为下一个栈顶的元素大小。
ex:
2,1,5,6,2,3
(1)r=0,s={2}
(2)r=0,1<2,pop 2,push 1 s={1,1} r=2
(3)r=2,2>1,s={1,1,5}
(4)r=2,6>5,s={1,1,5,6}
(5)r=2,2<6,pop 6, r=6,2<5 pop 5,s={1,1,2,2,2},r=10
(6)r=10,3>2,s={1,1,2,2,2,3} 10>6 s=10
"""
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
stack = list()
res = 0
heights.append(0)
N = len(heights)
for i in range(N):
if not stack or heights[i] > heights[stack[-1]]:
stack.append(i)
else:
while stack and heights[i] <= heights[stack[-1]]:
h = heights[stack[-1]]
stack.pop()
w = i if not stack else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
85、Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
def solve(s):
mans = 0
ans,ansindex,i = [],[],0
while i < len(s):
if len(ans) == 0 or s[i] >ans[-1]:
ans.append(s[i]);ansindex.append(i)
elif s[i] < ans[-1]:
lastindex = 0
while len(ans) > 0 and ans[-1] > s[i]:
lastindex = ansindex.pop()
mans = max(mans,ans.pop() * (i - lastindex))
ans.append(s[i]);ansindex.append(lastindex)
i += 1
while len(ans) != 0:
mans = max(mans,ans.pop() * (len(s) - ansindex.pop()))
return mans
s = [0 for i in range(n)]
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
s[j] += 1
else:
s[j] = 0
ans = max(ans,solve(s))
return ans
86、Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
"""
划分list
给定链表和target，划分链表左边是比target小的值，右边是大的值
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
原有的位置关系不变
"""
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
l,r = slow,fast = ListNode(None),ListNode(None)
while head:
if head.val < x:
l.next = head
l = l.next
else:
r.next = head
r = r.next
head = head.next
l.next,r.next = fast.next,None
return slow.next
87、Scramble String
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
great
rgeat
"""
给定字符串s1，通过一个二叉树来表示它，二叉树是通过递归的划分该字符串为两个非空子字符串。
为了扰乱字符串，我们可以选择任何非叶节点并交换其两个孩子。
"rgeat" 是 "great"的一种扰乱字符串
思路：
递归
s1 -> a1+a2
s2 -> b1+b2
"""
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1)!=len(s2):
return False
if s1==s2:
return True
l1=list(s1)
l2=list(s2)
l1.sort()
l2.sort()
if l1!=l2:
return False
length=len(s1)
for i in range(1,length):
if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):
return True
if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]):
return True
return False
88、Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
"""
合并排序的数组
给定两个排序后的数组1和数组2，将2合并到1中
归并排序
"""
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p, q, k = m-1, n-1, m+n-1
while p >= 0 and q >= 0:
if nums1[p] > nums2[q]:
nums1[k] = nums1[p]
p, k = p-1, k-1
else:
nums1[k] = nums2[q]
q, k = q-1, k-1
nums1[:q+1] = nums2[:q+1]
89、Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1
"""
二进制编码
给定代表代码中总位数的非负整数n，打印格雷码序列。 格雷码序列必须以0开头。
以0开始，每次变化一个位，从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值
"""
class Solution:
def grayCode(self, n: int) -> List[int]:
res=[]
for i in range(0,2**n):
grayCode = (i >> 1)^i
res.append(grayCode)
return res
90、SubsetsII
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
"""
子集
给一个有重复数据的整数集，返回所有的子集
"""
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(depth,start,valuelist):
if valuelist not in res:
res.append(valuelist)
if depth==len(nums):
return
for i in range(start,len(nums)):
dfs(depth+1,i+1,valuelist+[nums[i]])
nums.sort()
res=[]
dfs(0,0,[])
return res
