[leetcode]第十四部分(082-088)

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

从头开始遍历数组, 分别遍历两遍, i0len(heights), jilen(heights), ij的长方形计算公式如下: 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

问题难度:♣♣♣♣♣

问题描述

给定一个使用01填充的二维二进制矩阵, 找到只包含1的最大矩阵, 并且返回这个矩阵的面积.

示例

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

解题思路

暴力破解法

对于这个二维矩阵, 从头开始遍历, 对于当前的索引ij, 如果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

同样地, 如果我们继续交换节点eatat的孩子节点, 将会生成一个打乱的字符串: rgtea

   rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

我们说rgteagreat的打乱字符串.

给定两个长度相同的zifucs1s1, 判断s2是否是s1的打乱字符串.

示例1

Input: s1 = "great", s2 = "rgeat"
Output: true

示例2

Input: s1 = "abcde", s2 = "caebd"
Output: false

解题思路

递归法

针对s_1s_2, 假设它们两个是scramble的, 那么必然存在一个长度l_1, 可以将s_1分割成s_11s_12, 将s_2分割成s_21s_22, 使得s_11s_21 scramble并且s_12s_22 scramble 或者 s_11s_22 scramble并且s_12s_2 scramble.

那么问题来了, 怎么直接判断两个字符串是否scamble呢? 两个字符串相等时, 肯定scramble.
例如, 示例1中的两个字符串: greatrgeat, 存在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

问题难度: ♣

问题描述

给定两个排好序的整数数组nums1nums2, 将nums2nums1 合并成一个排好序的数组.

注意:

  • nums1nums2 中的原始元素数目分别为 mn
  • 我们可以假设 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]
打赏

mickey

记录生活,写给几十年后的自己。