82-Remove Duplicates from Sorted List II
问题难度: ♣♣♣
问题描述
给定一个排好序的链式列表, 删除所有有重复节点的数字, 只留下原始链表中的唯一字符.
示例1
Input: 1->2->3->3->4->4->5
Output: 1->2->5
示例2
Input: 1->1->1->2->3
Output: 2->3
解题思路
本质思想与之前删除数组中重复的数字类似, 只不过把存储格式从数组换成了链表. 在这里,我们使用了三个指针, 分别标识:
– 新链表当前元素, 用于移动元素, 如果某个数字不重复,则将该结点加入到新链表中,并将链表前移动;如果重复的话,暂时将链表的next指向下一个结点
– 原链表前元素, 判断元素是否重复,至少需要比较两个结点, 便于在数字不重复的情况下将其加入新链表
– 原链表后后元素, 用于判断元素是否与之前的节点数值相同
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
ans = ListNode(0)
tmp = ListNode(0)
now, end = head, head.next
now_num = now.val
ans.next = tmp
is_dup = False
while end is not None:
while end is not None and end.val == now_num:
is_dup = True
end = end.next
if not is_dup:
tmp.next = now
tmp = tmp.next
else:
tmp.next = end
if end is not None:
now = end
now_num = now.val
is_dup = False
end = end.next
return ans.next.next
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(3)
e = ListNode(3)
f = ListNode(4)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
s = Solution()
res = s.deleteDuplicates(a)
while res is not None:
print(res.val)
res = res.next
1
2
4
83-Remove Duplicates from Sorted List
问题难度: ♣
问题描述
给定一个排好序的链表, 删除所有重复的元素以保证每个元素只会出现一次.
示例1
Input: 1->1->2
Output: 1->2
示例2
Input: 1->1->2->3->3
Output: 1->2->3
解题思路
应该是属于比较简单的题目, 使用两个指针, 分别指向当前节点和下一个疑似的节点, 如果两个节点的值相等, 那么当前节点不动, 疑似节点向前移动一步; 如果值不相等, 那么当前节点的next指向疑似节点, 两个指针都分别向前移动一步, 直到疑似节点指向末尾为止.
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
ans = ListNode(0)
ans.next = head
tail = head.next
while tail is not None and head is not None:
if head.val == tail.val:
tail = tail.next
else:
head.next = tail
head = head.next
tail = tail.next
if head is not None:
head.next = tail
return ans.next
a = ListNode(1)
b = ListNode(2)
c = ListNode(2)
d = ListNode(2)
e = ListNode(2)
f = ListNode(4)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
s = Solution()
ans = s.deleteDuplicates(f)
while ans is not None:
print(ans.val)
ans = ans.next
4
84-Largest Rectangle in Histogram
问题难度:♣♣♣♣♣
问题描述
给定n个非负的整数表示直方图的块权重, 其中每一块的宽度均为1, 找到直方图中最大长方形的面积.
上面是一个直方图, 每一块的宽度均为1, 给定的高度为[2,1,5,6,2,3]
最大的长方形展示为阴影处, 其面积为10个单位
示例
Input: [2,1,5,6,2,3]
Output: 10
解题思路
方法1
从头开始遍历数组, 分别遍历两遍, i从0到len(heights), j从i到len(heights), i到j的长方形计算公式如下: min(nums[i:j])*(j-i+1). 这样, 自然而然可以得到一个o(n^2)复杂度的算法. 但是, 很明显,这样肯定会超过时间复杂度, 无法AC.
方法2
网上看到一种借助栈的算法, 思路如下:
– 如果已知heights是升序, 例如[1,2,3,4,5], 那么需要比较1*5 Vs 2*4 Vs 3*3 Vs 4*2 Vs 5*1, 归纳一下为: heights[i] * (len(heights) - i)
– 但是heights本身不一定是升序的, 因此需要考虑构造这样的升序序列(假设用栈存储). 以[2,1,5,6,2,3]为例, 具体的构造过程如下:
– 2进栈, s={2}, 此时ans = 2
– 1不满足升序, 将2弹出, 并记录当前结果2*1=2, 将2替换为1重新进栈, s={1,1}, ans=2
– 5满足升序, 直接进栈, s={1,1,5}, ans=2
– 6满足升序, 直接进栈, s={1,1,5,6}, ans=2
– 2不满足升序, 将6弹出, 并记录当前结果6*1=6,s={1,1,5}, ans=6, 仍然不满足升序条件, 将5弹出, 并记录当前结果5*2=10, s={1,1}, ans=10, 此时终于满足升序条件了, 将弹出的5,6全部替换为2重新进栈, s={1,1,2,2,2}, ans=10
– 3满足升序, 直接进栈, s={1,1,2,2,2,3}, ans=10
构造完成, 只需要按照上一种条件遍历计算即可. 整体时间复杂度为O(n).
代码
class Solution(object):
# method 1: brute force
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
max_area = 0
if len(heights) == 0:
return max_area
for i in range(len(heights)):
min_num = heights[i]
for j in range(i, len(heights)):
if heights[j] < min_num:
min_num = heights[j]
area = (j-i + 1) * min_num
if area > max_area:
max_area = area
return max_area
# method 2: stack method
def largestRectangleAreaStack(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if len(heights) == 0:
return 0
ans = 0
s = [heights[0]]
for i in range(1, len(heights)):
num = heights[i]
if num >= s[-1]:
s.append(num)
else:
j = len(s) - 1
tmp = list()
while j >= 0:
if num >= s[j]:
break
now_ans = s[j] * (len(s) - j)
if now_ans > ans:
ans = now_ans
j -= 1
j += 1
while j < len(s):
s[j] = num
j += 1
s.append(num)
for i in range(len(s)):
now_ans = s[i] * (len(s)-i)
if now_ans > ans:
ans = now_ans
return ans
s = Solution()
heights = [4,2,0,3,2,5]
print (s.largestRectangleAreaStack(heights))
6
85-Maximal Rectangle
问题难度:♣♣♣♣♣
问题描述
给定一个使用0和1填充的二维二进制矩阵, 找到只包含1的最大矩阵, 并且返回这个矩阵的面积.
示例
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
解题思路
暴力破解法
对于这个二维矩阵, 从头开始遍历, 对于当前的索引i和j, 如果matrix[i][j] == 1, 那么:
找到从i``j开始的所有矩形:
- 向右遍历, 直到遇到
0为止, 记录当前行中1的个数(记为num), 设置min_col=num - 向下遍历, 直到遇到
0为止, 记录每一行从第i列到第min_col列中1的个数, 更新min_col的值
延伸拓展
其中这一题还可以从每一层来看, 可以延伸拓展为上面提到的直方图计算最大的矩形面积的题目, 针对每一行, 都可以向上形成一个直方图, 再针对每个直方图调用上面84题的解决方案即可.
代码
class Solution(object):
# brute force
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return 0
max_area = 0
m, n = len(matrix), len(matrix[0])
for i in range(len(matrix)):
for j in range(len(matrix[i])):
cur_num = matrix[i][j]
if cur_num == "1":
area = self.getRecArea(matrix, i, j, m, n)
if area > max_area:
max_area = area
#print 'i: %d, j:%d, area: %d' %(i, j, area)
return max_area
def getRecArea(self, matrix, i, j, m, n):
max_area = 0
start_row, start_col = i+1, j
min_col = 0
area = 0
while start_col < n and matrix[i][start_col] == "1":
start_col += 1
min_col += 1
area += 1
#print 'i: %d, j:%d, min_col:%d' %(i, j, min_col)
if area > max_area:
max_area = area
while start_row < m and matrix[start_row][j] == "1":
start_col = j
num = 0
while start_col < n and start_col < start_col + min_col and matrix[start_row][start_col] == "1":
start_col += 1
num += 1
if num < min_col:
min_col = num
area = (start_row - i + 1) * min_col
#print 'start_row: %d, min_col: %d, area: %d' %(start_row, min_col, area)
if area > max_area:
max_area = area
start_row += 1
return max_area
# dynamic programming
def maximalRectangleStack(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return 0
max_area = 0
m, n = len(matrix), len(matrix[0])
heights = [0] * (n+1)
for i in range(m):
# construct the histogram
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
stack = [-1]
for j in range(n+1):
while heights[j] < heights[stack[-1]]:
height = heights[stack.pop()]
width = j - stack[-1] - 1
area = height * width
if area > max_area:
max_area = area
stack.append(j)
return max_area
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
s = Solution()
ans = s.maximalRectangleStack(matrix)
print(ans)
6
86-Partition List
问题难度: ♣ ♣ ♣
问题描述
给定一个链表和值x, 对其进行分区, 使得小于x的所有节点链接到左边,而大于或等于x的所有节点链接到右边.
我们应该保留两个分区中每个分区的节点中的原始相对顺序.
示例
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
解题思路
维护两个指针分别指向小于x的值(left)和大于等于x的值(right), 遍历链表, 根据情况更新对应指针的next值.最后将left指针的next值指向right指针即可.
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
left = ListNode(0)
left_tmp = ListNode(0)
left.next = left_tmp
right = ListNode(0)
right_tmp = ListNode(0)
right.next = right_tmp
while head is not None:
while head is not None and head.val < x:
left_tmp.next = head
left_tmp = left_tmp.next
head = head.next
left_tmp.next = None
while head is not None and head.val >= x:
right_tmp.next = head
right_tmp = right_tmp.next
head = head.next
right_tmp.next = None
left_tmp.next = right.next.next
return left.next.next
a = ListNode(1)
b = ListNode(1)
c = ListNode(4)
d = ListNode(2)
e = ListNode(2)
f = ListNode(3)
g = ListNode(5)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
f.next = g
s = Solution()
res = s.partition(a, 3)
while res is not None:
print(res.val)
res = res.next
1
1
2
2
4
3
5
87-Scramble String
问题难度: ♣♣♣♣♣
问题描述
给定一个字符串s1, 我们可以通过递归地将字符串分割为两个非空的子字符串来表示为一个二进制树.
下面是s1=great的一个可能表示:
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
为了打散这个字符串, 我们可以选择任一非叶子节点然后交换它的两个孩子节点. 这样就会构成打乱的字符串rgeat:
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
同样地, 如果我们继续交换节点eat和at的孩子节点, 将会生成一个打乱的字符串: rgtea”
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
我们说rgtea是great的打乱字符串.
给定两个长度相同的zifucs1和s1, 判断s2是否是s1的打乱字符串.
示例1
Input: s1 = "great", s2 = "rgeat"
Output: true
示例2
Input: s1 = "abcde", s2 = "caebd"
Output: false
解题思路
递归法
针对s_1和s_2, 假设它们两个是scramble的, 那么必然存在一个长度l_1, 可以将s_1分割成s_11和s_12, 将s_2分割成s_21和s_22, 使得s_11和s_21 scramble并且s_12和s_22 scramble 或者 s_11和s_22 scramble并且s_12和s_2 scramble.
那么问题来了, 怎么直接判断两个字符串是否scamble呢? 两个字符串相等时, 肯定scramble.
例如, 示例1中的两个字符串: great和rgeat, 存在l_1=2, 使得eat == eat, 存在l_1=1, 使得g==g, r==r.
动态规划法
参考博客, 可以使用动态规划法进行求解.
第一步: 用数学形式定义问题- 使用memo[i][j][len]标识s_1起始索引为i, s_2起始索引为j, 长度为len的两个字符串是否互为scramble.
第二步: 得到递推公式- 假设s_1[i: i+len]和s[j:j+len]为scramble, 那么必然存在一个len_1, 使得满足以下条件之一:
– s_1[i:i+len_1]与s_2[j:j+len_1]``scramble并且s_1[i+len_1: i+len]与s_2[j+len_1: j+len] scramble
– s_1[i:i+len_1]与s_2[j+len-len_1:j+len] scramble并且 s[i+len_1:i+len]与s_2[j: len-len_1+j] scramble
上面两种情况, 只要有一种满足条件就能说明这两个字符串scramble了.
对于len, 一共有1,2,...,len-1 len-1中切法.
那么可以得到递归公式:
memo[i][j][len] = || (memo[i][j][k] && memo[i+k][j+k][len-k] || memo[i][j+len-k][k] && memo[i+k][j][len-k]) for k in range(1, len)
因为信息都是计算过的，对于每种切法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种切法）。
如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大优势的，空间复杂度是O(n^3)。
代码
class Solution(object):
# recursion
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1) != len(s2):
return False
if s1 == s2:
return True
tmp1="".join((lambda x:(x.sort(),x)[1])(list(s1)))
tmp2 ="".join((lambda x:(x.sort(),x)[1])(list(s2)))
if tmp1 != tmp2:
return False
for i in range(1, len(s1)):
s11, s12 = s1[:i], s1[i:]
s21, s22 = s2[:i], s2[i:]
if self.isScramble(s11, s21) and self.isScramble(s12, s22):
return True
s22, s21 = s2[:len(s1)-i], s2[len(s1)-i:]
if self.isScramble(s11, s21) and self.isScramble(s12, s22):
return True
return False
#dynamic programming
def isScrambleDP(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1) != len(s2):
return False
m = len(s1)
if len(s1) == 0:
return True
memo = [[[False for i in range(m+1)] for j in range(m)] for k in range(m)]
for i in range(m):
for j in range(m):
memo[i][j][1] = (s1[i] == s2[j])
for t_len in range(2, m+2):
for i in range(m-t_len+1):
for j in range(m-t_len+1):
now = False
for k in range(1, t_len):
now = (memo[i][j][k] and memo[i+k][j+k][t_len-k]) or (memo[i][j+t_len-k][k] and memo[i+k][j][t_len-k])
if now:
break
memo[i][j][t_len] = now
return memo[0][0][m]
s1="great"
s2="rgtea"
s = Solution()
print(s.isScrambleDP(s1,s2))
True
88-Merge Sorted Array
问题难度: ♣
问题描述
给定两个排好序的整数数组nums1 和 nums2, 将nums2 与 nums1 合并成一个排好序的数组.
注意:
nums1和nums2中的原始元素数目分别为m和n- 我们可以假设
nums1有足够的空间 (数组长度大于或等于m + n) 来容纳来自nums2的元素
示例
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
解题思路
核心思想为插入排序, 使用三个指针,num_insert指向nums1数组中待插入的地址, start指向nums2数组中需要插入的起始元素位置, end指向nums_2数组中需要插入的末尾元素位置
那么如何更新三个值呢?
- 初始化:
num_insert = 0, start = 0, end = 0 - 更新:
- 如果
num1[num_insert]<=num2[end]并且num_insert<m,num_insert += 1, 直到num1[num_insert] > num2[end]为止 end += 1, 直到num1[num_insert] < num2[end]或者end>n为止, 将nums2[start: end]插入到nums1[num_insert + start - end - 1 ,num_insert-1], 将num1[num_insert:]向后移,start=end, m+= end-start
- 如果
代码
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
num_insert, start, end = 0, 0, 0
pivot = nums1[num_insert]
num1_len = len(nums1)
while num_insert < m and end < n:
while num_insert < m and nums1[num_insert] <= nums2[end]:
pivot = nums1[num_insert]
num_insert += 1
if num_insert < m:
pivot = nums1[num_insert]
while end < n and nums2[end] <= pivot:
end += 1
move_len = end - start
nums1[num_insert + move_len:] = nums1[num_insert:num1_len - move_len]
nums1[num_insert: num_insert + move_len] = nums2[start: end]
start = end
m += move_len
num_insert += move_len
if end < n and num_insert >= m:
nums1[num_insert:n+1-start+num_insert] = nums2[start:n+1]
nums1 = [1,2,4,5,6,0]
m = 5
nums2 = [3]
n = 1
s = Solution()
s.merge(nums1, m, nums2, n)
print(nums1)
[1, 2, 3, 4, 5, 6]
微信扫一扫，打赏作者吧～