[leetcode]第八部分

40-Combination Sum II

问题描述

给定一个候选数的集合candidates)和一个目标数target。找到candidates中所有和为target的唯一组合。

candidates中的每个数字只能使用一次

注意

  • 所有数字(包括target)都为正整数
  • 答案集不要包括重复组合

示例1

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例2

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

解题思路

这题题目和之前的题目类似,也可以使用回溯法进行求解。不过需要注意两个地方:

  • 不能出现重复的答案对
  • 一个数字只能出现一次

因此,与之前的题目相比,只需要修改两个小地方即可:

  • 由于数组为有序数组,那么有重复的答案对的话,其顺序必然一致,因此使用一个dict存储该值
  • 在向前试探的时候,需要把指针往前挪一位,不过得特别注意:往前挪动的时候得判断当前是否已经到末尾,如果已经到末尾,则无需继续试探

代码

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        total_com = list()
        total_dict = dict()
        self.backtrack(total_com, list(), candidates, target, 0, total_dict)
        return total_com


    def backtrack(self, total_com, tmp_list, candidates, remain, start, total_dict):
        if remain < 0:
            return False
        elif remain == 0:
            if str(tmp_list[:len(tmp_list)]) not in total_dict:
                total_com.append(tmp_list[:len(tmp_list)])
                total_dict[str(tmp_list[:len(tmp_list)])] = 1
            return False
        else:
            for i in range(start, len(candidates)):
                tmp_list.append(candidates[i])
                if i < len(candidates):
                    flag = self.backtrack(total_com, tmp_list, candidates, remain - candidates[i], i+1, total_dict)
                    tmp_list.pop()
                    if not flag:
                        break
            return True

41-First Missing Positive

问题描述

给定一个未排序的整数数组,找到最小的/缺失的正整数。

示例1

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

示例2

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

示例3

Input: [7,8,9,11,12]
Output: 1

注意
算法的时间复杂度必须不超过O(n)并且只能使用固定的额外空间。

解题思路

最简单的方法是:维护一个长度为n的数组idx,遍历nums数组,如果其值小于len(nums),那么将idx中该索引的值设置为1,然后找到idx中第一个不为0的值,返回即可。

但是,很明显,其额外空间为O(n)不满足条件。

另外一种:先排序,找到第一个大于0的数,取得其下标为idx,继续向后遍历,使用nums[i]-i,判断其是否等于idx,如果不等于,那么就直接返回nums[i]-[i],排序的话额外空间能满足要求,但是时间复杂度没办法满足要求。

话说回来,第一种方法,需要使用额外空间,那么我们能不能之间利用nums进行存储呢?答案是:能!从前向后进行遍历(指针为i),如果nums[i]大于0小于len(nums),那么将nums[i]放在nums[nums[i]-1]下面(当前,为了避免漏掉,得使用一个循环进行遍历,直到交换的值不满足要求为止)

代码

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_len = len(nums)
        for i in range(nums_len):
            while 0 < nums[i] <= nums_len and nums[nums[i]-1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i]-1]
        for i in range(0, nums_len):
            if i+1 != nums[i]:
                return i + 1
        return nums_len + 1

42-Trapping Rain Water

问题描述

给定n个非负的整数来表示海拔地图,其中,每条的宽度均为1,计算在下雨之后能够盛多少谁。


上面的海拔地图表示为数组:[0,1,0,2,1,0,1,3,2,1,2,1,在本案例中,将会留存6个单位的雨水(如蓝色部分所示)

示例

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解题思路

方法1:暴力破解

针对海拔地图中的每一个元素:我们分别向左和向右找到从它开始的最高值,然后将其中的较小值减去当前的至就可以求得这个元素储水的量了,例如,当i=2时,左边最大值是1,右边最大值是3,那么i=2的储水量便为1。只要将每个元素的储水量都叠加起来就可以获得所有储水量了。此时,时间复杂度为O(n^2)

遗憾的是:这种方法的时间复杂度过高,无法AC,只能另找方法。

方法2:动态规划法
延续上一种方法,我们不难发现:其实每次向左找和向右找的最大值都差不多,只不过需要移动下轴点:当当前值小于max_left的时候,max_left的值可以不变;而当前值大于max_left时,只需要将max_left的值修改为当前值即可;max_right的值有点复杂,因为右边的元素是减少的,为了减少时间复杂度,我们可以使用一个辅助的数组nums存储从右边开始到索引位置的最大值,这样时间复杂度就缩短为O(2n)了。这种方法被AC了。

方法3:两个指针
再思考一下,其实这道题目还是可以继续优化的:如果max_left小于max_right的话,那么就只用考虑max_left即可;反之,如果max_right小于max_left的话,只用考虑max_right的值。具体做法如下:

  • 使用两个指针分别指向头部和尾部
  • left<right的时候:
    • 如果height[left]小于height[right]
      • 如果height[left] > = left_max,那么就更新left_max=height[left]
      • 否则的话,ans += left_max - height[left]
      • 左边往前移动:left+=1
    • 否则:
      • 如果height[right] >= right_max,那么就更新right_max=height[right]
      • 否则,ans += right_max - height[right]
      • 右边向左移动 right -= 1

其实,总的说来就是把方法二中更新nums数组的地方直接放在了遍历中,节省了空间。

代码

方法2

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        height_len = len(height)
        if height_len == 0:
            return ans
        nums = [0 for _ in range(height_len)]
        max_right = 0
        for i in range(height_len-1, -1, -1):
            max_right = max_right if max_right > height[i] else height[i]
            nums[i] = max_right
        max_left = 0
        for i in range(0, len(height)):
            now_num = height[i]
            if now_num > max_left:
                max_left = now_num
            max_right = nums[i]
            ans += (max_left if max_left < max_right else max_right) - now_num
        return ans

方法3

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        if len(height) == 0:
            return ans
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        while left < right:
            if height[left] < height[right]:
                if left_max > height[left]:
                    ans += left_max - height[left]
                else:
                    left_max = height[left]
                left += 1
            else:
                if right_max > height[right]:
                    ans += right_max - height[right]
                else:
                    right_max = height[right]
                right -= 1
        return ans

43-Multiply Strings

问题描述

给定两个非负整数num1num2表示为字符串,返回num1num2的乘积,也表示为字符串。

示例1

Input: num1 = "2", num2 = "3"
Output: "6"

示例2

Input: num1 = "123", num2 = "456"
Output: "56088"

注意

  • num1num2的长度均小于110
  • num1num2均只包含0-9的数字
  • num1num2不包含任何前置0(除了0本身以外)
  • 禁止使用任何内置的大整数库或者直接将输入转化为整数

解题思路

考虑我们直接手算乘法时,一般是使用单个数字与乘数相乘,然后再累加。

代码

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if num1 == "0" or num2 == 0:
            return "0"
        num2_len = len(num2)
        ans = ""
        for i in range(num2_len):
            idx = num2_len - i - 1
            cur = int(num2[idx])
            now_ans = self.multiplyOne(num1, cur, i)
            ans = self.addStr(ans, now_ans)
        return ans

    def addStr(self, ans, now_ans):
        if len(ans) < len(now_ans):
            # len(ans) >= len(now_ans)
            return self.addStr(now_ans, ans)
        ret = ""
        i, j = len(ans)-1, len(now_ans) - 1
        flag = 0
        while i >= 0 and j >= 0:
            cur = flag + int(ans[i]) + int(now_ans[j])
            ret = str(cur % 10) + ret
            flag = cur / 10
            i -= 1
            j -= 1
        while flag > 0 and i >= 0:
            cur = flag + int(ans[i])
            ret = str(cur % 10) + ret
            flag = cur/10
            i -= 1
        if flag == 0:
            ret = ans[:i+1] + ret
        else:
            ret = str(flag) + ret
        return ret


    def multiplyOne(self, num1, cur, idx):
        ans = ""
        for i in range(idx):
            ans += "0"
        flag = 0
        for i in range(len(num1)-1, -1, -1):
            int_num = int(num1[i])
            now_mul = flag + cur * int_num
            ans = str(now_mul % 10) + ans
            flag = now_mul / 10
        if flag > 0:
            ans = str(flag) + ans
        return ans

44-Wildcard Matching

问题描述

给定一个输入字符串(s)和一个模式(p),实现支持'?''*'的通配符模式匹配。

'?'匹配任何单一的字符
'*'匹配字符的任何序列(包括空序列)

匹配必须覆盖整个输入字符串(而不是部分)。

注意
s可以是空字符串,或者只包含小写字符a-z的字符串
p可以是空字符串,或者只包含小写字符a-z以及?或者*的字符串

示例1

Input:
s = "aa"
p = "a"
Output: false
解释:"a" 无法匹配完整的字符串 "aa"。

示例2

Input:
s = "aa"
p = "*"
Output: true
解释: '*' 匹配任何序列。

示例3

Input:
s = "cb"
p = "?a"
Output: false
解释: '?' 匹配 'c', 但是第二个字符是 'a', 无法匹配 'b'。

示例4

Input:
s = "adceb"
p = "*a*b"
Output: true
解释: 第一个 '*' 匹配空序列,而第二个 '*' 匹配子字符串 "dce"。

示例5

Input:
s = "acdcb"
p = "a*c?b"
Output: false

解题思路

需要考虑模式串中的两种特殊字符:

  • ?比较好解决,两个串的指针都直接往前挪即可
  • *得分情况讨论:匹配0次,或者匹配一次以上,一次以上可以迭代完成,只要有一种情况满足条件都可以

上面这种方法提交的时候显示超时了。那么我们就得思考怎么缩短计算时间:考虑到到匹配串中有*时,其实只需要考虑在遇到不匹配的情况时,回溯一下:将已经移动的指针往前挪一挪就可以继续匹配,直到遇到下一个*时,更新回溯点即可。

代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        s_idx = 0
        p_idx = 0
        match = 0
        start_idx = -1
        p = self.removeConMark(p)
        while s_idx < len(s):
            if p_idx < len(p) and (p[p_idx] == '?' or p[p_idx] == s[s_idx] ):
                s_idx += 1
                p_idx += 1
            elif p_idx < len(p) and p[p_idx] == '*':
                start_idx = p_idx
                match = s_idx
                p_idx += 1
            elif start_idx != -1:
                p_idx = start_idx + 1
                match += 1
                s_idx = match
            else:
                return False
        while p_idx < len(p) and p[p_idx] == '*':
            p_idx += 1
        return p_idx == len(p)


    def removeConMark(self, p):
        ans = ""
        for i in range(0, len(p)):
            if i >= 1 and p[i] == p[i-1] == "*":
                continue
            else:
                ans += p[i]
        return ans

45-Jump Game II

问题描述

给定一个非负整数的数组,初始的时候我们位于数组的第一个下标。

数组中的每个元素表示在该位置我们可以跳的最大长度。

我们的目标是在最小的跳转次数下到达最后一个索引。

示例

Input: [2,3,1,1,4]
Output: 2
解释: 达到最大下标的最小跳转次数为 2。第一次从0跳到1, 然后从1跳3步跳到4。

注意
可以假设我们一直能跳到最后一位。

解题思路

分别使用两个变量lastcur来表示上次跳跃和这次跳跃能覆盖到的最大范围,使用一个变量i来表示当前的索引,当i的值不大于last的时候,说明这次跳跃不是必要的,根据情况判断是否需要更新cur的值;如果i的值大于last的值,说明这次跳跃是必要的,step需要加1并且更新last。此时,算法复杂度为O(n)

代码

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_len = len(nums)
        last, cur, step = 0, 0, 0
        for i in range(num_len):
            if i > last:
                last = cur
                step += 1
            now = nums[i] + i
            if now > cur:
                cur = now
        return step if cur >= num_len - 1 else 0

46-Permutations

问题描述:

给定一个不重复整数的集合,返回所有可能的遍历。

示例

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

解题思路

注意到题干中说的没有重复的数字,因此完全可以把这个题目分解为最简单的情况:

  • 两个数求全排列
  • 第三个数插入…

代码

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret_list = [[]]
        for i in range(len(nums)):
            ret_list = self.permuteList(nums[i], ret_list)
        return ret_list


    def permuteList(self, num, now_list):
        ret_list = list()
        for i in range(len(now_list)):
            n_list = now_list[i]
            for j in range(len(n_list)+1):
                tmp_list = n_list[:j] + [num] + n_list[j:]
                ret_list.append(tmp_list)
        return ret_list

mickey

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

发表评论

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