→ ririoshi: 大師 01/21 02:58
推 Murasakisalt: 大師 01/21 02:59
※ 引述《pandix (麵包屌)》之銘言：
: 491. Non-decreasing Subsequences
: 給你一個 array nums，要你回傳他的所有非嚴格遞增的 subsequences，順序任意
: subsequence 長度至少要是 2
: Example 1:
: Input: nums = [4,6,7,7]
: Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
: Example 2:
: Input: nums = [4,4,3,2,1]
: Output: [[4,4]]
: 思路:
1.看到要求所有的可能性而且測資的數量很小，基本上百分之百是用回溯法窮舉。
2.用回溯法可以輕易的求出所有的子序列組合，有問題的是[4,6,x,7]和[4,6,7,x]
都是[4,6,7]算是同一個，我們要對他去重。
3.去重的辦法就是用一個Set來記錄當前起點後面的數字，如果遇到已經用過的就跳
過就可以過濾掉上面那種case。
Java Code：
---------------------------------------
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backTracking(nums, new ArrayList<>(), res, 0);
return res;
}
private void backTracking(int[] nums, List<Integer> curr,
List<List<Integer>> res, int start) {
if (curr.size() > 1) {
res.add(new ArrayList<>(curr));
}
Set<Integer> visited = new HashSet<>();
for (int i = start; i < nums.length; i++) {
if (visited.contains(nums[i])) continue;
if (curr.isEmpty() || nums[i] >= curr.get(curr.size() - 1)) {
visited.add(nums[i]);
curr.add(nums[i]);
backTracking(nums, curr, res, i + 1);
curr.remove(curr.size() - 1);
}
}
}
}
---------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674241005.A.C05.html