[leetcode]第二十一部分

132- Palindrome Partitioning II

问题难度: ♣ ♣ ♣ ♣ ♣

问题难度

给定一个字符串s, 对s进行分割使得每个子串部分都是回文。

返回s的回文分割中需要的最小切割次数。

示例

Input: "aab"
Output: 1
解释: 只切割1次就能形成: ["aa","b"]

解题思路

还是一句老话:所有字符串相关的题目都能用动态规划法进行求解。

数学化: 使用cuts[i]表示从ilen(s)的最小切割数,假设ij之间为回文,那么cuts[i] = min(cuts[i], cuts[j+1] + 1);初始化:cuts[i]=len(s)-i-1,最后返回cuts[0]

问题变成了如何判断ij是否为回文:
– 如果j-i<=1,那么只需要判断s[i] == s[j]
– 否则, 只需要判断s[i]==s[j] && p[i-1][j+1]

代码

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        s_len = len(s)
        cuts = []
        p = [[False for _ in range(s_len)] for _ in range(s_len)]
        for i in range(s_len + 1):
            cuts.append(s_len-i- 1)
        for i in range(s_len-1, -1, -1):
            for j in range(i, s_len):
                if (s[i]==s[j] and (j-i<=1 or p[i+1][j-1])):
                    p[i][j] = True
                    if cuts[j+1] + 1 < cuts[i]:
                        cuts[i] = cuts[j+1] + 1
        return cuts[0]

133- Clone Graph

问题难度: ♣ ♣ ♣

问题描述

给定一个图的头,返回图的深度复制。图中的每个节点都包含一个标签(int)和它邻居节点的列表(List[UndirectedGraphNode])。给定节点和其邻居节点之间都有一条边。

OJ的无向图系列(从而我们可以了解错误的输出):节点的标签具有唯一性。

我们使用#作为每个节点之间的分隔符,,作为节点的标签以及节点的所有邻居。

将序列图{0,1,2#1,2#2,2}作为一个示例:

从上面可以看出,这个图一共有使用#分割的三个节点。

  • 第1个节点的标签为0,节点0同时连接12
  • 第2个节点的标签为1,节点1连接2
  • 第3个节点的标签为2,节点2只连接它自己,形成一个环

可视化之后如下图所示:

       1
      / \
     /   \
    0 --- 2
        / \
        \_/

注意:树序列化的信息只是为了帮助我们了解错误的输出。我们不需要了解序列化来解决这个问题。

解题思路

emmm… 其实这道题目的意思没怎么看懂. 大概就是需要遍历一遍所有节点. 在这里可以采用深度优先或者广度优先的算法进行遍历.

首先, 深度优先, 顾名思义, 就是深度搜索, 一条路走到黑, 再选新的路. 可以使用递归和非递归的方法进行实现. 伪代码如下:

递归

procedure DFS(G,v):
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
    if vertex w is not labeled as discovered then
        recursively call DFS(G,w)

非递归

procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
            v ← S.pop() 
            if v is not labeled as discovered:
                label v as discovered
                for all edges from v to w in G.adjacentEdges(v) do
                    S.push(w)

然后是广度优先, 对于一个节点来说先把所有neighbors都检查一遍, 再从第一个neighbor开始, 循环往复. 由于BFS的这个特质,BFS可以帮助寻找最短路径. 伪代码如下:

procedure BFS(G,v) is
      create a queue Q
      create a set V
      add v to V
      enqueue v onto Q
      while Q is not empty loop
         t ← Q.dequeue()
         if t is what we are looking for then
            return t
        end if
        for all edges e in G.adjacentEdges(t) loop
           u ← G.adjacentVertex(t,e)
           if u is not in V then
               add u to V
               enqueue u onto Q
           end if
        end loop
     end loop
     return none
 end BFS

在本题中, 我们可以使用一个哈希结构来存储对应的节点.

代码

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if node is None:
            return node
        head = UndirectedGraphNode(node.label)
        discovered_dict = {node: head}
        queue = [node]
        while len(queue) > 0:
            cur_node = queue.pop()
            for neighbor in cur_node.neighbors:
                if neighbor not in discovered_dict:
                    queue.append(neighbor)
                    new_neighbor = UndirectedGraphNode(neighbor.label)
                    discovered_dict[neighbor] = new_neighbor
                discovered_dict[cur_node].neighbors.append(discovered_dict[neighbor])
        return head

134- Gas Station

问题难度: ♣ ♣ ♣

问题描述

假设有一个环形的路线上有N个加油站,在第i个加油站的油量为gas[i].

假设我们有一辆无限邮箱的车,从第i个加油站到下一个加油站i+1需要花费cost[i]. 我们在其中一个加油站带着空油桶开始行程.

如果我们能验证顺时针的方向完成线路, 就返回起始加油站的下标, 否则返回-1.

注意

  • 最多只存在一个解决方案
  • 两个输入数组均非空并且有相同的长度
  • 输入数组中的元素是非负的整数

示例1

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

解释:
从站点3开始 (下标 3) 然后填充 4 个单位的油. 油箱容量为: 0 + 4 = 4
开到站点 4. 油箱容量为: 4 - 1 + 5 = 8
开到站点 0. 油箱容量为: 8 - 2 + 1 = 7
开到站点 1. 油箱容量为: 7 - 3 + 2 = 6
开到站点 2. 油箱容量为: 6 - 4 + 3 = 5
开到站点 3. 花费为 5. 油量正好够开到站点 3.
因此, 返回 3 为起始下标.

示例2

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

解释:
我们不能从站点 0 或者站点 1 开始, 因为没有足够的油量开到下一个站点.
从站点 2 开始,然后加4个单位的油. 油箱容量为: 0 + 4 = 4
开到站点 0. 油箱容量为: 4 - 3 + 2 = 3
开到站点 1. 油箱容量为: 3 - 3 + 3 = 3
我们无法开回站点 2, 因为中间需要 4 个单位的油,而我们只有 3个单位.
因此, 无论从哪个站点开始,我们都无法绕一圈.

解题思路

先来一个简单的想法, 使用一个变量tank来存储当前油量,然后从前往后遍历列表:

  • tank += gas[i],如果 tank >= cost[i],那么i += 1, tank -= cost[i]; 否则直接停止,说明不能从当前开始

一次遍历结束之后,如果有满足条件的, 那么直接返回,否则的话移动下标, 将当前列表的第一个移动到最后一个.

然而…TLE了. 然后认真思考了一下, 发现其实有很多重复计算…

考虑一下, 假设从0开始, 到了某个站点i发现走不下去了, 其实就没有必要遍历0i-1的值了. 证明一下: 假设中间存在一个站点j,使得可以从j站点走到i站点, 那么必然存在tank[j, i-1] > 0, 但是由于tank[0, j] > 0, 因此必然可以得到tank[0, i-1]>0, 与前提不符. 因此, 如果0i走不了的话,下一个起始点可以从i开始了.避免了重复比较. 同理, 如果从i站点到最后一个站点可以通过,但是在0站点到j站点出现问题的话, 就不用比较i站点之后的值了.

o(╯□╰)o, 然后参考了一下标准答案…发现: 只要sum(gas) >= sum(cost), 那么肯定会找到一个起始站点的, 因此只要一路遍历下去即可…

代码

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        start, m = 0, len(gas)
        while start < m:
            tank = 0
            is_stop = False
            for i in range(start, m):
                tank += gas[i]
                if tank >= cost[i]:
                    tank -= cost[i]
                else:
                    start = i + 1
                    is_stop = True
                    break
            if not is_stop:
                for i in range(0, start):
                    tank += gas[i]
                    if tank >= cost[i]:
                        tank -= cost[i]
                    else:
                        return -1
                return start
        return -1

    def canCompleteCircuitSmart(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if sum(gas) < sum(cost):
            return -1
        start = 0
        tank = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start = i + 1
                tank = 0
        return start

135- Candy

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

假设有N个小孩站成一列, 每个小孩都有一个评分值. 我们需要给这些孩子分发糖果, 但是需要满足下面的要求:

  • 每个孩子至少有1块糖
  • 如果孩子的评分比他的邻居高, 那么需要给他更多的糖果

我们必须发多少糖果?

示例1

Input: [1,0,2]
Output: 5
解释:我们可以分别给3个孩子分发 2, 1, 2 块糖果.

示例2

Input: [1,2,2]
Output: 4
解释: 们可以分别给3个孩子分发 1, 2, 1 块糖果.由于满足上面的挑个条件,因此第三个孩子可以得到 1 块糖果.

解题思路

分析一下, 不难发现:
ratings[i] < ratings[i-1]的时候, candy[i] = candy[i-1] + 1即可, 否则, 先不更新.
遍历一遍结束之后,再从后往前遍历一遍即可.

emmm…思考一种不需要额外空间的方法. 正如刚刚所分析的, 当序列为非递减序列时,我们能简单地获取到需要发放的糖果: 当ratings[i] < ratings[i-1]的时候, candy[i] = candy[i-1] + 1, 当ratings[i] == ratings[i-1]的时候, candy[i] = 1即可.

而出现非递减序列时, 可能需要额外添加, 例如: [1,2,4,4,3,2,1], 对于前3个孩子, 分别分发糖果: [1,2,3]即可, 但是对于第4个, 如果按照刚刚说的规则,只能发1个, 但是很明显, ta后面的孩子就无法发了, 因此需要考虑这种情况. 记录一个修正值, 当递减序列的长度大于当前糖果的数目时, 则需要增加一个修正值.

代码

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        m = len(ratings)
        if m == 0:
            return 0
        candy = [0  for _ in range(m)]
        candy[0] = 1
        for i in range(m):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
            else:
                candy[i] = 1
        for i in range(m-2, -1, -1):
            #反向扫描一遍,如果左边的rating比右边高,并且左边的糖果数比右边少,那么左边的糖果数应比右边多一
            if ratings[i] > ratings[i+1] and candy[i+1] >= candy[i]:
                candy[i] = candy[i+1] + 1
        return sum(candy)

    def candyOnce(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        m = len(ratings)
        if m == 0:
            return 0
        total = 1
        before_des = 1
        pre_candy = 1
        des_len = 0
        for i in range(1, m):
            if ratings[i] >= ratings[i-1]:
                if ratings[i] == ratings[i-1]:
                    # 相等, 直接设置为1
                    pre_candy = 1
                else:
                    # 递增, 直接前面的数+1即可
                    pre_candy += 1
                total += pre_candy
                des_len = 0
                before_des = pre_candy
            else:
                # 递减
                des_len += 1
                if before_des <= des_len:
                    total += 1
                total += des_len
                pre_candy = 1
        return total

136- Single Number

问题难度: ♣

问题描述

给定一个非空的整数数组, 除了一个元素之外其它元素都会出现两次, 找到单个的数.

注意:

算法的时间复杂度应该控制在线性运行时间, 我们能否在不使用额外内存的前提下完成?

示例1

Input: [2,2,1]
Output: 1

示例2

Input: [4,1,2,1,2]
Output: 4

解题思路

最最直观的想法:使用一个哈希结构存储已经出现过的数字, 遍历数组, 如果已经存在, 则将它放在另外一个哈希结构里面, 最后取两个哈希结构的差值即可.

但是! 这个不满足不适用额外空间的需求啊!

于是乎, 参考了下网上代码… 发现:如果两个数相等的话, 异或会取1,否则异或取0

因此得到代码如下.

代码

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
            res ^= num
        return res

137-Single Number II

问题难度: ♣ ♣ ♣

问题描述

给定一个非空的整数数组, 除了一个元素之外其它元素都会出现三次, 它只会出现一次, 找到单个的数.

注意:

算法的时间复杂度应该控制在线性运行时间, 我们能否在不使用额外内存的前提下完成?

示例1

Input: [2,2,3,2]
Output: 3

示例2

Input: [0,1,0,1,0,1,99]
Output: 99

解题思路

emmm… 又是一个非常巧妙的解决方案… 分别使用one/two/three来存储出现1次/2次/3次的数字.

三个变量的更新方法如下:

two  |= one & nums[i]
one ^= nums[i]
three = one & two
one &= ~three
two &= ~three

代码

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, three = 0, 0, 0
        for num in nums:
            two |= one & num
            one ^= num
            three = one & two
            one &= ~three
            two &= ~three
        return one

138- Copy List with Random Pointer

问题难度: ♣ ♣ ♣

问题描述

给定一个链式列表使得每个节点都包含一个额外的/可以指向列表中任何节点或者null的额外随机指针.

返回列表的深度复制.

解题思路

这道题目和之前的题目类似, 可以使用一个额外的哈希结构来存储新旧节点的对应关系, 其它的就是遍历节点即可.

代码

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if head is None:
            return head
        node_dict = {}
        new_head = RandomListNode(head.label)
        pre = new_head
        cur_node = head.next
        node_dict[head] = new_head
        while cur_node is not None:
            new_node = RandomListNode(cur_node.label)
            node_dict[cur_node] = new_node
            pre.next = new_node
            pre = new_node
            cur_node = cur_node.next
        cur_node = head
        copy_node = new_head
        while cur_node is not None:
            if cur_node.random is not None:
                    random = node_dict[cur_node.random]
            else:
                random = None
            copy_node.random = random
            copy_node = copy_node.next
            cur_node = cur_node.next
        return new_head
打赏

mickey

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注