当前位置:网站首页>剑指 Offer 38. 字符串的排列
剑指 Offer 38. 字符串的排列
2022-07-06 01:28:00 【Yake1965】
剑指 Offer 38. 字符串的排列
回溯:决策当前字符串的某一位填入什么字符。
去重通用方法:
- 使用 Set 实现去重;
- 先对原字符串进行排序,然后确保相同字符传入同一目标位置的动作只发生一次。
方法一: Set 去重
只对结果去重,没有去除重复计算。42 ms
class Solution {
Set<String> set = new HashSet<>();
char[] arr;
boolean[] vis;
public String[] permutation(String s) {
arr = s.toCharArray();
vis = new boolean[arr.length];
backtrack(0, "");
return set.toArray(String[]::new);
}
void backtrack(int idx, String t){
if(idx == arr.length) {
set.add(t);
return;
}
for(int i = 0; i < arr.length; i++){
if(vis[i]) continue;
vis[i] = true;
backtrack(idx + 1, t + arr[i]);
vis[i] = false; // 回溯
}
}
}
逐位去重 21 ms
class Solution {
List<String> list = new ArrayList<>();
char[] arr;
boolean[] vis;
public String[] permutation(String s) {
arr = s.toCharArray();
vis = new boolean[arr.length];
backtrack(0, "");
return list.toArray(String[]::new);
}
void backtrack(int idx, String t){
if(idx == arr.length) {
list.add(t);
return;
}
Set<Character> set = new HashSet<>(); // 去重
for(int i = 0; i < arr.length; i++){
if(vis[i] || set.contains(arr[i])) continue;
vis[i] = true;
set.add(arr[i]);
backtrack(idx + 1, t + arr[i]);
vis[i] = false;
}
}
}
通过交换遍历 6 ms
class Solution {
List<String> list = new ArrayList<>();
char[] arr;
public String[] permutation(String s) {
arr = s.toCharArray();
backtrack(0);
return list.toArray(String[]::new);
}
void backtrack(int idx){
if(idx == arr.length - 1) {
list.add(new String(arr)); // String.valueOf(arr)
return;
}
Set<Character> set = new HashSet<>();
for(int i = idx; i < arr.length; i++){
if(set.contains(arr[i])) continue;
set.add(arr[i]);
swap(i, idx); // 当前位分别替换成后面的其它字母
backtrack(idx + 1);
swap(idx, i);
}
}
void swap(int i, int j){
char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
方法二:排序去重
class Solution {
List<String> list = new ArrayList<>();
char[] arr;
boolean[] vis;
public String[] permutation(String s) {
arr = s.toCharArray();
vis = new boolean[arr.length];
Arrays.sort(arr);
backtrack(0, "");
return list.toArray(String[]::new);
}
void backtrack(int idx, String t){
if(idx == arr.length) {
list.add(t);
return;
}
for(int i = 0; i < arr.length; i++){
if(vis[i] || i > 0 && !vis[i-1] && arr[i] == arr[i-1]) continue;
vis[i] = true;
backtrack(idx + 1, t + String.valueOf(arr[i]));
vis[i] = false;
}
}
}
47.全排列II
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(depth=0, path=[]):
if depth == n:
res.append(path[:])
return
for i in range(n):
if used[i] or (i > 0 and nums[i] == nums[i - 1] and used[i - 1]): continue
path.append(nums[i])
used[i] = True
backtrack(depth + 1, path)
path.pop()
used[i] = False
def backtrack1(depth=0):
if depth == n: res.append(nums[:])
for i in range(depth, n):
nums[depth], nums[i] = nums[i], nums[depth]
backtrack1(depth + 1)
nums[depth], nums[i] = nums[i], nums[depth]
## 深度优先搜索
def dfs(depth=0, path=[], tmp=nums):
if depth == n:
res.append(path)
return
for i in range(len(tmp)):
dfs(depth + 1, path + [tmp[i]], tmp[:i] + tmp[i + 1:])
n, res = len(nums), []
nums.sort()
used = [False] * n
backtrack()
# backtrack1()
# dfs()
return res
# return list(set(permutations(nums)))
class Solution {
boolean[] vis;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> perm = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
vis = new boolean[nums.length];
Arrays.sort(arr);
backtrack(0, nums);
return ans;
}
public void backtrack(int idx, int[] arr){
if (idx == arr.length) {
ans.add(new ArrayList<Integer>(perm));
return;
}
for (int i = 0; i < arr.length; ++i) {
if (vis[i] || i > 0 && arr[i] == arr[i-1] && !vis[i-1]) continue; // !used[i-1] 比 used[i-1] 快点
perm.add(arr[i]);
vis[i] = true;
backtrack(idx + 1, arr);
vis[i] = false;
perm.remove(idx);
}
}
}
class Solution {
List<List<Integer>> ans;
public List<List<Integer>> permuteUnique(int[] nums) {
ans = new LinkedList<>();
backtrack(0, nums);
return ans;
}
void backtrack(int idx, int[] arr) {
if (idx == arr.length) {
// ans.add(Arrays.stream(arr).boxed().toList());
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < arr.length; i++) tmp.add(arr[i]);
ans.add(tmp);
return;
}
Set<Integer> set = new HashSet<>();
for (int j = idx; j < arr.length; j++) {
if (!set.contains(arr[j])) {
set.add(arr[j]);
swap(arr, j, idx);
backtrack(idx + 1, arr);
swap(arr, j, idx);
}
}
}
void swap(int[] nums, int i, int j) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}
}
方法三:31. 下一个排列
class Solution {
public String[] permutation(String s) {
List<String> ans = new ArrayList<String>();
char[] arr = s.toCharArray();
Arrays.sort(arr);
do {
ans.add(new String(arr));
} while (nextPermutation(arr));
return ans.toArray(String[]::new);
}
boolean nextPermutation(char[] arr) {
int i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) i--;
if (i < 0) return false;
int j = arr.length - 1;
while (j >= 0 && arr[i] >= arr[j]) j--;
swap(arr, i, j);
reverse(arr, i + 1);
return true;
}
void swap(char[] arr, int i, int j) {
char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
void reverse(char[] arr, int left) {
int right = arr.length - 1;
while (left < right) {
swap(arr, left++, right--);
}
}
}
31. 下一个排列
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i < 0){
reverse(nums, 0);
return;
}
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) j--;
swap(nums, i, j);
reverse(nums, i + 1);
return;
}
void swap(int[] arr, int i, int j) {
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
void reverse(int[] arr, int left) {
int right = arr.length - 1;
while (left < right) {
swap(arr, left++, right--);
}
}
}
边栏推荐
- Daily practice - February 13, 2022
- Blue Bridge Cup embedded stm32g431 - the real topic and code of the eighth provincial competition
- Cadre du Paddle: aperçu du paddlelnp [bibliothèque de développement pour le traitement du langage naturel des rames volantes]
- [le plus complet du réseau] | interprétation complète de MySQL explicite
- 电气数据|IEEE118(含风能太阳能)
- A glimpse of spir-v
- 基于DVWA的文件上传漏洞测试
- Development trend of Ali Taobao fine sorting model
- Vulhub vulnerability recurrence 74_ Wordpress
- VMware Tools installation error: unable to automatically install vsock driver
猜你喜欢
[detailed] several ways to quickly realize object mapping
电气数据|IEEE118(含风能太阳能)
037 PHP login, registration, message, personal Center Design
【Flask】官方教程(Tutorial)-part2:蓝图-视图、模板、静态文件
MySQL learning notes 2
【已解决】如何生成漂亮的静态文档说明页
leetcode刷题_验证回文字符串 Ⅱ
How does the crystal oscillator vibrate?
C web page open WinForm exe
Threedposetracker project resolution
随机推荐
WGet: command line download tool
Cadre du Paddle: aperçu du paddlelnp [bibliothèque de développement pour le traitement du langage naturel des rames volantes]
[understanding of opportunity-39]: Guiguzi - Chapter 5 flying clamp - warning 2: there are six types of praise. Be careful to enjoy praise as fish enjoy bait.
[Jiudu OJ 09] two points to find student information
基于DVWA的文件上传漏洞测试
MATLB | real time opportunity constrained decision making and its application in power system
leetcode刷题_平方数之和
Huawei converged VLAN principle and configuration
Basic operations of databases and tables ----- non empty constraints
MATLB|实时机会约束决策及其在电力系统中的应用
What is weak reference? What are the weak reference data types in ES6? What are weak references in JS?
Netease smart enterprises enter the market against the trend, and there is a new possibility for game industrialization
Remember that a version of @nestjs/typeorm^8.1.4 cannot be obtained Env option problem
PHP error what is an error?
现货白银的一般操作方法
Spir - V premier aperçu
How to get all sequences in Oracle database- How can I get all sequences in an Oracle database?
A picture to understand! Why did the school teach you coding but still not
什么是弱引用?es6中有哪些弱引用数据类型?js中的弱引用是什么?
How does Huawei enable debug and how to make an image port