回溯/贪心高频题

原创

王脸小

修改于 2020-08-06 11:10:37

1.3K0

修改于 2020-08-06 11:10:37

文章被收录于专栏：王漂亮王漂亮

回溯算法

"有关递归的算法，都离不开“树”的遍历这一抽象模型。只不过对于不同的算法，在前（中）后序遍历的时候，所做的事不同而已。 "

算法的整体框架

"回溯算法就是 N 叉树的遍历，这个 N 等于当前可做的选择（choices）的总数，同时，在前序遍历的位置作出当前选择（choose 过程），然后开始递归，最后在后序遍历的位置取消当前选择（unchoose 过程）。回溯算法伪代码模板如下："

"""
choiceList：当前可以进行的选择列表
track：可以理解为决策路径，即已经做出一系列选择
answer：用来储存我们的符合条件决策路径
"""

def backtrack(choiceList, track, answer):
    if track is OK:
        answer.add(track)
    else:
        for choice in choiceList:
            # choose：选择一个 choice 加入 track
            backtrack(choices, track, answer)
            # unchoose：从 track 中撤销上面的选择

"回溯算法的核心就在于如何设计 choose 和 unchoose 部分的逻辑。"

注意

Append Copy: res.append(track.copy())

待学习

回溯时间复杂度计算；带memo的回溯；动规-非所有解题

分析一下回溯算法的时间复杂度吧。递归树的复杂度都是这样分析：总时间 = 递归树的节点总数 × 每个递归节点需要的时间。全排列问题，节点总数等于 n + n*(n-1)+ n*(n-2)...* n!，总之不超过 O(n*n!)。

对于 Java 代码的那个解法，处理每个节点需要 O(n) 的时间，因为 track.contains(nums[i]) 这个操作要扫描数组。所以全排列问题总时间不超过 O(n^2* n!)。

46. 全排列

Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

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

Solution

用used数组标识已选择

class Solution(object):
    def permute(self, nums):
        
        res = []
        used = [False]*len(nums)
        
        def backtrack(nums, track):
            if len(track) == len(nums):
                res.append(track.copy())
                
            for i in range(len(nums)):
                if not used[i]:
                    used[i] = True
                    backtrack(nums, track+[nums[i]])
                    used[i] = False
                    
        backtrack(nums, [])
        
        return res

78. 子集

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Solution

和前面全排列区分一下

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def backtrack(track, i):
            res.append(track)

            for j in range(i, len(nums)):
                backtrack(track + [nums[j]], j+1)
                        
        backtrack([], 0)
        
        return res

10.28 开始想得很复杂，需要再做一遍

22. 括号生成

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

左括号数量没到就可以随时出现，右括号只能在数量小于左括号时出现，用dict计数

class Solution:
    def generateParenthesis(self, n: int):
        
        res = []
        counter = {"(":0, ")":0}
        
        def backtrack(counter, track):
            if counter["("] == counter[")"] == n:
                res.append(track)
                
            for p in ["(", ")"]:
                if counter[p] < n:
                    if (p == ")" and counter["("]>counter[")"]) or p == "(":
                        counter[p] += 1
                        backtrack(counter, track+p)
                        counter[p] -= 1
                    
        backtrack(counter, "")
        
        return res

131. 分割回文串

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution

class Solution(object):
    def partition(self, s):
        res = []
        
        def backtrack(track, s):
            if not s:
                res.append(track.copy())
                
            for i in range(1, len(s)+1):
                if s[:i] == s[:i][::-1]:
                    backtrack(track+[s[:i]], s[i:])
            
        backtrack([], s)
        
        return res

开始想复杂的了，一直想用DP来判断字串是不是回文，但似乎直接反转就可以了，需要看一下之前用DP求回文的题。

17. 电话号码的字母组合

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
        
        res = []
        def backtrack(next_digits, track):
            if len(next_digits) == 0:
                res.append(track)
                return
                
            for letter in phone[next_digits[0]]:
                backtrack(next_digits[1:], track+letter)

        backtrack(digits, '')
        return res

非常直白的回溯

贪心算法

252. 会议室

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，请你判断一个人是否能够参加这里面的全部会议。

示例 1:

输入: [[0,30],[5,10],[15,20]]
输出: false

示例 2:

输入: [[7,10],[2,4]]
输出: true

太简单不写了，暴力两两比较；优化排序后比较Onlgn

253. 会议室 II

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例 2:

输入: [[7,10],[2,4]]
输出: 1

Solution

1. n^2, 自己做的，按开始时间排序，依次迭代消消乐。（Reference）

2. 最小堆。按结束时间排序，堆里只记录结束时间，每次遍历到下一个看要不要和堆顶合并

import heapq
class Solution(object):
    def minMeetingRooms(self, intervals):
        if not intervals: return 0
        intervals.sort()

        free_rooms = []
        heapq.heappush(free_rooms, intervals[0][1])

        for i in intervals[1:]:

            if free_rooms[0] <= i[0]:
                heapq.heappop(free_rooms)
            heapq.heappush(free_rooms, i[1])

        return len(free_rooms)

56. 合并区间

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

powcai

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        intervals.sort()
        res = []
        i = 0
        while i < len(intervals):
            l, r = intervals[i][0], intervals[i][1]
            
            while i < len(intervals)-1 and intervals[i+1][0] <= r:
                i += 1
                r = max(intervals[i][1], r)
            res.append([l,r])
            i += 1
        
        return res

134. 加油站

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.

Example 1:

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

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

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

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Solution

class Solution:
    def canCompleteCircuit(self, gas, cost) -> int:
        if sum(gas) < sum(cost): return -1
        
        for start in range(len(gas)):
            gas_store = 0
            for posi in range(start+1, start+len(gas)+1):
                posi = posi%(len(gas))
                gas_store = gas_store + gas[posi-1] - cost[posi-1] 
                if gas_store < 0: break
            
            if gas_store>=0 and start==posi: return start
                
        return -1

暴力法(调试了很多次)，超时

待优化：贪心

55. 跳跃游戏

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
Solution

class Solution:
    def canJump(self, nums) -> bool:
        
        def backtrack(posi):
            if posi == len(nums)-1:
                return True
            
            if nums[posi] == 0: return False
            
            for i in reversed(range(1, nums[posi]+1)):
                if posi+i <= len(nums)-1:
                    if backtrack(posi+i): 
                        return True
                
        return backtrack(0)

回溯+贪心，超时

优化：带memo的回溯 -> DP

DP思路：dp = [False] * len, 小于等于step的都可置为true，返回dp[-1]

Reference: 回溯算法详解

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

登录后参与评论

0 条评论

热度