鱼C论坛

 找回密码
 立即注册
查看: 1367|回复: 0

[学习笔记] leetcode 31. Next Permutation 谷歌面试题

[复制链接]
发表于 2019-8-17 10:28:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 Seawolf 于 2019-8-17 14:21 编辑

另一道Google 面试题!

  1. Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

  2. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

  3. The replacement must be in-place and use only constant extra memory.

  4. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

  5. 1,2,3 → 1,3,2
  6. 3,2,1 → 1,2,3
  7. 1,1,5 → 1,5,1
复制代码


  1. import java.util.*;

  2. public class Solution {
  3.        
  4.         static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
  5.        
  6.         static ArrayList<Integer> list = new ArrayList<Integer>();
  7.        
  8.         public static void main(String[] args) {
  9.                
  10.                 int[] array = {4,3,2,1};
  11.                
  12.                 nextPermutation(array);

  13.        for(int i = 0; i< array.length; i++) {
  14.               
  15.                System.out.println(array[i]);
  16.        }

  17.                
  18.         }
  19.        
  20.         public static void permute(ArrayList<Integer> lst, ArrayList<ArrayList <Integer>> result, int[] input) {
  21.                
  22.                 if(lst.size() == input.length) {
  23.                        
  24.                         result.add(new ArrayList<Integer>(lst));
  25.                         return;
  26.                        
  27.                 }
  28.                
  29.                 for(int i = 0; i < input.length; i++) {
  30.                        
  31.                         if(lst.contains(input[i])) {
  32.                                
  33.                                 continue;
  34.                                
  35.                         }
  36.                        
  37.                         lst.add(input[i]);
  38.                        
  39.                         permute(lst,result,input);
  40.                        
  41.                         lst.remove(lst.size()-1);
  42.                        
  43.                 }
  44.                
  45.         }
  46.        
  47.     public static void nextPermutation(int[] nums) {
  48.         
  49.         int[] base = Arrays.copyOf(nums, nums.length);
  50.         
  51.         Arrays.sort(nums);
  52.         
  53.         permute(list, result, nums);
  54.         
  55.         for(int i = 0 ; i < result.size(); i++){
  56.                
  57.                 boolean is = false;
  58.                
  59.                 int count = 0;
  60.                
  61.                 for(int x = 0; x< base.length; x++) {
  62.                        
  63.                         if(base[x] == result.get(i).get(x)) {
  64.                                                            
  65.                                 count++;
  66.                         }
  67.                 }
  68.                
  69.                 if(count == base.length) {
  70.                        
  71.                         is = true;
  72.                 }
  73.             
  74.             if(is && i != result.size()-1){
  75.                
  76.                
  77.                 for(int j = 0; j < nums.length; j++){
  78.                     
  79.                     nums[j] = result.get(i+1).get(j);
  80.                 }
  81.                
  82.             }
  83.             
  84.             else if (is && i == result.size()-1){
  85.                
  86.                 for(int j = 0; j < nums.length; j++){
  87.                     
  88.                     nums[j] = result.get(0).get(j);
  89.                 }
  90.             }
  91.         }
  92.         
  93.     }

  94. }
复制代码



这个代码可以算出给定数组的所有可能的排列,但是还是有一个比较大的问题,就是给定的数组如果含有重复的元素,那么这个方法将会失效,因为permute方法里面是以contains作为判断条件的。
所以对以上代码进行修改,使之可以兼容repeated number。

  1. import java.util.*;

  2. public class Solution {
  3.        
  4.         static ArrayList<ArrayList <Integer>> result = new ArrayList<>();
  5.        
  6.         public static void main(String[] args) {
  7.                
  8.                 int[] nums = {1,2};
  9.                
  10.                 int[] base = Arrays.copyOf(nums, nums.length);
  11.                
  12.                 Arrays.sort(nums);
  13.                
  14.                 permute(result, nums,0,nums.length);
  15.         
  16.         
  17. //            System.out.println(result);
  18.            
  19.         for(int i = 0 ; i < result.size(); i++){
  20.                
  21.                 boolean is = false;
  22.                
  23.                 int count = 0;
  24.                
  25.                 for(int x = 0; x< base.length; x++) {
  26.                        
  27.                         if(base[x] == result.get(i).get(x)) {
  28.                                                            
  29.                                 count++;
  30.                         }
  31.                 }
  32.                
  33.                 if(count == base.length) {
  34.                        
  35.                         is = true;
  36.                 }
  37.             
  38.             if(is && i != result.size()-1){
  39.                
  40.                
  41.                 for(int j = 0; j < nums.length; j++){
  42.                     
  43.                     nums[j] = result.get(i+1).get(j);
  44.                 }
  45.                
  46.             }
  47.             
  48.             else if (is && i == result.size()-1){
  49.                
  50.                 for(int j = 0; j < nums.length; j++){
  51.                     
  52.                     nums[j] = result.get(0).get(j);
  53.                 }
  54.             }
  55.         }
  56.         
  57.         
  58.         for(int p = 0; p< nums.length; p++) {
  59.                
  60.                 System.out.println(nums[p]);
  61.         }
  62.                
  63.         }
  64.        
  65.         public static void permute(ArrayList<ArrayList <Integer>> result, int[] input, int i ,int length) {
  66.                
  67.                 if(i == length-1) {
  68.                        
  69.                         ArrayList<Integer> list = new ArrayList<Integer>();
  70.                        
  71.                         for(int n = 0 ; n< input.length; n++) {
  72.                                
  73.                                 Integer mm = new Integer(input[n]);
  74.                                 list.add(mm);
  75.                         }
  76.                                
  77.                         result.add(list);
  78.                         return;
  79.                        
  80.                 }
  81.                
  82.                 for(int j = i; j < length; j++) {
  83.                        
  84.                         if(!isExist(input,i,j)) {
  85.                                
  86.                                 swap(input, i ,j);
  87.                                
  88.                                 permute(result,input,i+1,input.length);
  89.                                
  90.                                 swap(input, i,j);
  91.                                
  92.                         }
  93.                        
  94.                 }
  95.                
  96.         }
  97.        
  98.         public static boolean isExist(int[] lst, int i, int j) {
  99.                
  100.                 for(int x = i ; x < j ; x++) {
  101.                        
  102.                         if(lst[x] == lst[j]) {
  103.                                
  104.                                 return true;
  105.                                
  106.                         }
  107.                 }
  108.                
  109.                 return false;
  110.         }
  111.        
  112.         public static void swap(int[] lst ,int i, int j) {
  113.                
  114.                 int temp = lst[j];
  115.                
  116.                 lst[j] = lst[i];
  117.                
  118.                 lst[i] = temp;
  119.         }

  120. }
复制代码



尽管答案是正确的,提交leetcode依然会报错。

14.jpg

原因是因为题目中要求只允许只用 constant extra memory.

实现方法:

1.从 input list a[n] 的倒数第二位开始向前循环,找到第一个下降序列,记为index1
2.从input list a[n] 的倒数第一位开始向前循环,找到第一个大于a[index1] 的元素 index2
3. 交换 index1 和 index2 对应的元素
4.对 index2 + 1 到 a.length -1 之间的元素进行 reverse 得到 nextpermutation


Here is the code:

  1. import java.util.*;

  2. public class Solution {
  3.        
  4.         public static void nextPermutation(int[] nums)  {
  5.                
  6.                
  7.                 int start = nums.length -2;
  8.                
  9.                 while(start >= 0 && nums[start] >= nums[start +1]) {
  10.                        
  11.                         start --;
  12.                 }
  13.                
  14.         if(start >= 0){
  15.             
  16.                      int end = nums.length -1;   
  17.             
  18.             while(end >= 0 && nums[end] <= nums[start]){
  19.                
  20.                 end -- ;
  21.             }
  22.             
  23.             swap(nums,start,end);
  24.         }
  25.                
  26.                
  27.                 reverse(nums, start+1);
  28.                
  29.                
  30.         }
  31.        
  32.         public static void reverse(int[] nums, int i) {
  33.         
  34.         int len = nums.length-1;
  35.                
  36.                 while(i < len) {
  37.                        
  38.                         swap(nums, i++ , len--);
  39.                 }
  40.         }
  41.        
  42.         public static void swap(int[] nums, int i, int j) {
  43.                
  44.                 int temp = nums[i];
  45.                
  46.                 nums[i] = nums[j];
  47.                
  48.                 nums[j] = temp;
  49.         }
  50. }
复制代码


15.jpg

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 08:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表