LeetCode 47全排列Ⅱ&48旋转图像
原创公众号：
bigsai如果不错记得点赞收藏！
关注回复 bigsai 领取Java进阶pdf资源，回复进群加入力扣打卡群。
上周打卡内容：43字符串相乘&44通配符匹配 45跳跃游戏&46全排列
全排列Ⅱ
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
法一 哈希
这题相比之前的就是有重复的情况，最笨的方法就是用哈希将各种序列存到Set中最后返回，但是这也是一种方法和策略：
Set<String>set=new HashSet<String>();
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> list=new ArrayList<List<Integer>>(); Arrays.sort(nums); arrange(nums, 0, nums.length-1, list); return list;
} private void arrange(int[] nums, int start, int end, List<List<Integer>> list) { if(start==end) { List<Integer>list2=new ArrayList<Integer>(); StringBuilder sBuilder=new StringBuilder(); for(int a:nums) { sBuilder.append(a); list2.add(a); } if(!set.contains(sBuilder.toString())) { list.add(list2); set.add(sBuilder.toString()); } } for(int i=start;i<=end;i++) { swap(nums,i,start); arrange(nums, start+1, end, list); swap(nums, i, start); } }
private void swap(int[] nums, int i, int j) {
int team=nums[i];
nums[i]=nums[j];
nums[j]=team;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
但是效果比较差：
法二 递归剪枝
第一个是真的很慢，但是有什么可以优化的方案吗？答案当然是有的，我们在执行递归全排列的时候，主要考的是要把重复的情况搞下去，怎么思考这个问题呢？
我们在进行交换swap的时候从前往后，前面的确定之后就不会在动，所以我们要慎重考虑和谁交换。剩下所有数默认不重复会排列所有情况，所以1 2 3和3 2 1在这个问题上等价，但是1 1 2 3第一个数有三种情况而不是四种情况：
1 1 2 3
2 1 1 3
3 1 2 1
另外比如3 1 1,3和自己交换，和后面两个1只能和其中一个进行交换，我们这里可以约定和第一个出现的进行交换，我们看一个图解部分过程：
所以，当我们从一个index开始的时候要记住以下的规则：同一个数只交换一次(包括自己的数)。
在判断的时候，你可以遍历，也可以使用hashSet().
具体实现的代码为：
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> list=new ArrayList<List<Integer>>(); arrange(nums, 0, nums.length-1, list); return list;
}
private void arrange(int[] nums, int start, int end, List<List<Integer>> list) { if(start==end) { List<Integer>list2=new ArrayList<Integer>(); for(int a:nums) { list2.add(a); } list.add(list2); } Set<Integer>set=new HashSet<Integer>(); for(int i=start;i<=end;i++) { if(set.contains(nums[i])) continue; set.add(nums[i]); swap(nums,i,start); arrange(nums, start+1, end, list); swap(nums, i, start); }
}
private void swap(int[] nums, int i, int j) {
int team=nums[i];
nums[i]=nums[j];
nums[j]=team;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
法三 回溯剪枝
我是压根没考虑用回溯，因为回溯完整的比直接递归慢，但是这里用回溯剪枝比较好，剪枝条的规则如下：
- 先对序列进行排序
- 试探性将数据放到当前位置
- 如果当前位置数字已经被使用，那么不可使用
- 如果当前数字和前一个相等但是前一个没有被使用，那么前当前不能使用，需要使用前一个数字。
思路很简单，实现起来也很简单：
List<List<Integer>> list;
public List<List<Integer>> permuteUnique(int[] nums) {
list=new ArrayList<List<Integer>>();
List<Integer> team=new ArrayList<Integer>();
boolean jud[]=new boolean[nums.length];
Arrays.sort(nums);
dfs(jud, nums, team, 0);
return list;
}
private void dfs(boolean[] jud, int[] nums, List<Integer> team, int index) {
// TODO Auto-generated method stub
int len = nums.length;
if (index == len)// 停止
{
list.add(new ArrayList<Integer>(team));
} else
for (int i = 0; i < len; i++) { if (jud[i]||(i>0&&nums[i]==nums[i-1]&&!jud[i-1])) //当前数字被用过 或者前一个相等的还没用，当前即不可用 continue; team.add(nums[i]); jud[i]=true; dfs(jud, nums, team, index + 1); jud[i] = false;// 还原 team.remove(index);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
旋转图像
题目描述：
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
这题思路可能比较清晰，但实现起来磕磕绊绊的地方可能比较多。每个人按照自己的思维找到一个好的方法就可以了，我把我自己的方法分享一下：
首先要看到重要信息：
- n*n的矩阵
- 不可创建新的矩阵
- 顺时针旋转
旋转其实就是一个中心对称问题找点的问题，我们可以将这个矩阵分为任意四部分，其中一个部分某个点作为起始点开始交换操作。明显看的出来是左开右闭的操作。
在具体确定好(i,j)后，找到对应其他三个点的坐标。坐标其实也是很有规律的，需要自己相通就行，这里就不带大家推导了，点和对面的点中点是矩阵中心，可以进行验算。
实现代码为：
public void rotate(int[][] matrix) {
int len=matrix.length;
for(int i=0;i<len/2;i++)//第i行
{ int team=0; for(int j=i;j<len-i-1;j++)//每个数进行四次操作 { int x1=i,y1=j; int x2=j,y2=len-i-1; int x3=len-i-1,y3=len-j-1; int x4=len-j-1,y4=i; team=matrix[x1][y1]; matrix[x1][y1]=matrix[x4][y4]; matrix[x4][y4]=matrix[x3][y3]; matrix[x3][y3]=matrix[x2][y2]; matrix[x2][y2]=team; }
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
结语：好了今天就到这里了，欢迎关注原创技术公众号：【bigsai】，回复进群加笔者微信一起加入打卡！
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/109405060
- 点赞
- 收藏
- 关注作者
评论（0）