每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！
第一题：46. 全排列 - 力扣（LeetCode）
class Solution {
//这道题就是一个dfs
//把所有结果遍历，到叶子节点就可以添加结果了
List<Integer> path = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
//要给一个flag数组来判断是否被选过
//以此来成为排列、不是组合
int[] flag = new int[nums.length];
traversal(0, nums, flag);
return res;
}
private void traversal(int startindex, int[] nums, int[] flag){
if(startindex == nums.length){
res.add(new ArrayList(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(flag[i] == 0){
flag[i] = 1;
path.add(nums[i]);
traversal(startindex + 1, nums, flag);
path.removeLast();
flag[i] = 0;
}
}
}
}第二题：47. 全排列 II - 力扣（LeetCode）
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
int[] flag = new int[nums.length];
traversal(0, res, path, nums, flag);
return res;
}
private void traversal(int start, List<List<Integer>> res, List<Integer> path, int[] nums, int[] flag){
if(start == nums.length){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
//和上一题一样，但是数组会有重复的，
//所以我们要剪枝去重
if(flag[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == 0)){
continue;
}
flag[i] = 1;
path.add(nums[i]);
traversal(start + 1, res ,path, nums, flag);
path.removeLast();
flag[i] = 0;
}
}
}第三题：48. 旋转图像 - 力扣（LeetCode）
class Solution {
public void rotate(int[][] matrix) {
//题目要求不能复制来实现，要原地调转，
//所以不能笨笨地复制粘贴，那样会用很多额外空间
int n = matrix.length;
// 先沿对角线翻转
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 再沿中线左右翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}
第四题：49. 字母异位词分组 - 力扣（LeetCode）
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 朴素的做法，时间长但是空间非常小
// 使用 flag 数组标记已经处理过的字符串
int[] flag = new int[strs.length];
// 结果列表
List<List<String>> res = new ArrayList<>();
// 遍历每个字符串
for(int i = 0; i < strs.length; i++){
// 如果当前字符串已经处理过，直接跳过
if(flag[i] == 1){
continue;
}
// 临时列表，用于存放同一组异位词
List<String> tmp = new ArrayList<>();
// 统计当前字符串的字符频率
int[] fre = new int[26];
for(int j = 0; j < strs[i].length(); j++){
fre[strs[i].charAt(j) - 'a']++;
}
// 遍历剩余字符串，寻找异位词
for(int k = i; k < strs.length; k++){
int flagg = 0;
// 如果当前字符串已经处理过，直接跳过
if(flag[k] == 1){
continue;
}
// 统计当前遍历到的字符串的字符频率
int[] free = new int[26];
for(int j = 0; j < strs[k].length(); j++){
free[strs[k].charAt(j) - 'a']++;
}
// 检查是否为异位词
for(int x = 0; x < 26; x++){
if(fre[x] != free[x]){
flagg = 1;
break;
}
}
// 如果是异位词，则加入临时列表，并标记已处理
if(flagg == 0){
tmp.add(strs[k]);
flag[k] = 1;
}
}
// 将当前异位词组加入结果列表
res.add(tmp);
}
return res;
}
}
第五题：50. Pow(x, n) - 力扣（LeetCode）
class Solution {
public double myPow(double x, int n) {
// 这道题最适合就是使用递归来实现
// 如果指数为0，则结果为1
if(n == 0) {
return 1.0;
}
// 如果指数为负数，则将底数取倒数，指数取绝对值
if(n < 0) {
return 1 / (x * myPow(x, -(n + 1)));
}
// 如果指数为正数，则使用递归计算幂
double temp = myPow(x, n / 2);
// 如果指数为偶数，则结果为 temp 的平方
if(n % 2 == 0) {
return temp * temp;
} else { // 如果指数为奇数，则结果为 temp 的平方乘以底数
return temp * temp * x;
}
}
}
