leetcode-09（下一个排列+快乐数+全排列）

大家好，欢迎来到IT知识分享网。

思路：我们希望下一个数比当前数大，所以我们只需要将后面的大数与前面的小数交换即可，另外，增加的幅度要是最小，满足紧密排列

所以我们需要从右往左进行低位交换，比如 ，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换，所以这里思路是先循环找到>低位的低位位置，然后再来个循环从右边遍历，进行交换；

交换完后，还需要考虑低位后的字串情况，可能是个降序的，比如 ，首先按照上一步，交换 5 和 4，得到 ，那么低位后面也就是64明显是个降序，所以需要反转一下

以求  的下一个排列为例：

首先从后向前查找第一个相邻升序的元素对 (i,j)。这里 i=4，j=5，对应的值为 5，7：（这里目的是找到低位位置）

然后在 [j,end) 从后向前查找第一个大于 A[i] 的值 A[k]。这里 A[i] 是 5，故 A[k] 是 6：（从后面再遍历找到大于低位的值）

将 A[i] 与 A[k] 交换。这里交换 5、6：

这时 [j,end) 必然是降序，逆置 [j,end)，使其升序。这里逆置 [7,5,4]：（需要考虑交换后，低位后面的数是一个降序的数，毕竟小的放后面了）

因此， 的下一个排列就是 

class Solution { //从后往前找，直至arr[i]>arr[i-1]，如果没有找到说明是降序，那么直接返回倒序，否则找到arr[i]>arr[i-1]的地方，将其换一下 public static void nextPermutation(int[] nums) { boolean flag = true; int aid = -1; for (int i = nums.length - 1; i > 0; i--) { //1.找到后一个比前一个大的，用aid记录前一个状态,找到就说明不是降序 if (nums[i] > nums[i - 1]) { aid = i - 1; flag = false; break; } } //2.根据flag状态进行判断是否为降序,true说明为降序 if (flag) { reverse(nums, 0, nums.length - 1); return; } //3.因为第一个for是确定低位的，这里的for是确定大于低位的最小值然后进行交换 for (int i = nums.length - 1; i > aid; i--) { //将遍历过的部分比i-1大的最小值和i-1的位置交换 if(nums[i]>nums[aid]){ int temp=nums[i]; nums[i]=nums[aid]; nums[aid]=temp; break; } } //4.交换后低位后的值为降序需要反转 reverse(nums,aid+1, nums.length-1); return; } / * 反转数组 */ public static void reverse(int[] nums, int start, int end) { while (start < end) { //1.交换 int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; //2.缩小范围进一步交换 start++; end--; } } }

class Solution { public static boolean isHappy(int n){ HashSet<Integer> set = new HashSet<>(); while (n!=1){ set.add(n); //1.找到子数 n=getNum(n); //2.去重 if(set.contains(getNum(n))){ return false; } } return true; } / * 2.找到一个数的各个位数的和 * @return */ public static int getNum(int n){ int num=0; while(n>0){ int a = n % 10; num+=a*a; n/=10; } return num; } }

class Solution { //将其分析为DFS，看做树形 //结果集 public List<List<Integer>> permute(int[] nums) { List<List<Integer>>result=new ArrayList<>(); List<Integer> list=new ArrayList<>(); dfs(result,list,nums); return result; } //首先，自己定义一个dfs方法 private void dfs(List<List<Integer>>result,List<Integer>list,int[] nums){ //结束条件 if(list.size()==nums.length){ result.add(new ArrayList<Integer>(list)); return; } //分支操作 for(int num:nums){ //进行分支中放值的一个判断 if(!list.contains(num)){ list.add(num); //进行分支当中的一个递归 dfs(result,list,nums); list.remove(list.size()-1); } } } }