当前位置:网站首页>Sword finger offer 38 Arrangement of strings
Sword finger offer 38 Arrangement of strings
2022-07-06 01:40:00 【Yake1965】
The finger of the sword Offer 38. Arrangement of strings
to flash back : Decide what character to fill in a bit of the current string .
General method of weight removal :
- Use Set Achieve de duplication ;
- First sort the original string , Then make sure that the same character is passed into the same target location only once .
Method 1 : Set duplicate removal
De duplication of results only , Double counting is not removed .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; // to flash back
}
}
}
Bit by bit weight removal 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<>(); // duplicate removal
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;
}
}
}
Traverse through exchange 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); // Replace the current bit with the following letters
backtrack(idx + 1);
swap(idx, i);
}
}
void swap(int i, int j){
char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
Method 2 : Sort and de duplicate
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. Full Permutation 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]
## Depth-first search
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] Than used[i-1] Hurry up
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;
}
}
Method 3 :31. Next spread
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. Next spread
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--);
}
}
}
边栏推荐
- Initialize MySQL database when docker container starts
- 一图看懂!为什么学校教了你Coding但还是不会的原因...
- Redis-Key的操作
- leetcode-2.回文判断
- NumPy 数组索引 切片
- Leetcode skimming questions_ Verify palindrome string II
- 国家级非遗传承人高清旺《四大美人》皮影数字藏品惊艳亮相!
- Shutter doctor: Xcode installation is incomplete
- Folio.ink 免费、快速、易用的图片分享工具
- Ali test open-ended questions
猜你喜欢
Basic operations of databases and tables ----- primary key constraints
leetcode刷题_反转字符串中的元音字母
NLP fourth paradigm: overview of prompt [pre train, prompt, predict] [Liu Pengfei]
[flask] official tutorial -part1: project layout, application settings, definition and database access
【Flask】官方教程(Tutorial)-part3:blog蓝图、项目可安装化
Alibaba canal usage details (pit draining version)_ MySQL and ES data synchronization
c#网页打开winform exe
leetcode3、实现 strStr()
Une image! Pourquoi l'école t'a - t - elle appris à coder, mais pourquoi pas...
Folio.ink 免费、快速、易用的图片分享工具
随机推荐
Format code_ What does formatting code mean
[the most complete in the whole network] |mysql explain full interpretation
leetcode3、实现 strStr()
【已解决】如何生成漂亮的静态文档说明页
[flask] official tutorial -part2: Blueprint - view, template, static file
阿里测开面试题
Une image! Pourquoi l'école t'a - t - elle appris à coder, mais pourquoi pas...
Basic operations of databases and tables ----- primary key constraints
Ali test Open face test
MATLB|实时机会约束决策及其在电力系统中的应用
Dynamics 365 开发协作最佳实践思考
Unreal browser plug-in
插卡4G工业路由器充电桩智能柜专网视频监控4G转以太网转WiFi有线网速测试 软硬件定制
Crawler request module
01.Go语言介绍
Reasonable and sensible
Force buckle 9 palindromes
Unity VR resource flash surface in scene
Threedposetracker project resolution
Cadre du Paddle: aperçu du paddlelnp [bibliothèque de développement pour le traitement du langage naturel des rames volantes]