|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 Seawolf 于 2019-8-17 14:21 编辑
另一道Google 面试题!
- Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
- If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
- The replacement must be in-place and use only constant extra memory.
- Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
- 1,2,3 → 1,3,2
- 3,2,1 → 1,2,3
- 1,1,5 → 1,5,1
复制代码
- import java.util.*;
- public class Solution {
-
- static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
-
- static ArrayList<Integer> list = new ArrayList<Integer>();
-
- public static void main(String[] args) {
-
- int[] array = {4,3,2,1};
-
- nextPermutation(array);
- for(int i = 0; i< array.length; i++) {
-
- System.out.println(array[i]);
- }
-
- }
-
- public static void permute(ArrayList<Integer> lst, ArrayList<ArrayList <Integer>> result, int[] input) {
-
- if(lst.size() == input.length) {
-
- result.add(new ArrayList<Integer>(lst));
- return;
-
- }
-
- for(int i = 0; i < input.length; i++) {
-
- if(lst.contains(input[i])) {
-
- continue;
-
- }
-
- lst.add(input[i]);
-
- permute(lst,result,input);
-
- lst.remove(lst.size()-1);
-
- }
-
- }
-
- public static void nextPermutation(int[] nums) {
-
- int[] base = Arrays.copyOf(nums, nums.length);
-
- Arrays.sort(nums);
-
- permute(list, result, nums);
-
- for(int i = 0 ; i < result.size(); i++){
-
- boolean is = false;
-
- int count = 0;
-
- for(int x = 0; x< base.length; x++) {
-
- if(base[x] == result.get(i).get(x)) {
-
- count++;
- }
- }
-
- if(count == base.length) {
-
- is = true;
- }
-
- if(is && i != result.size()-1){
-
-
- for(int j = 0; j < nums.length; j++){
-
- nums[j] = result.get(i+1).get(j);
- }
-
- }
-
- else if (is && i == result.size()-1){
-
- for(int j = 0; j < nums.length; j++){
-
- nums[j] = result.get(0).get(j);
- }
- }
- }
-
- }
- }
复制代码
这个代码可以算出给定数组的所有可能的排列,但是还是有一个比较大的问题,就是给定的数组如果含有重复的元素,那么这个方法将会失效,因为permute方法里面是以contains作为判断条件的。
所以对以上代码进行修改,使之可以兼容repeated number。
- import java.util.*;
- public class Solution {
-
- static ArrayList<ArrayList <Integer>> result = new ArrayList<>();
-
- public static void main(String[] args) {
-
- int[] nums = {1,2};
-
- int[] base = Arrays.copyOf(nums, nums.length);
-
- Arrays.sort(nums);
-
- permute(result, nums,0,nums.length);
-
-
- // System.out.println(result);
-
- for(int i = 0 ; i < result.size(); i++){
-
- boolean is = false;
-
- int count = 0;
-
- for(int x = 0; x< base.length; x++) {
-
- if(base[x] == result.get(i).get(x)) {
-
- count++;
- }
- }
-
- if(count == base.length) {
-
- is = true;
- }
-
- if(is && i != result.size()-1){
-
-
- for(int j = 0; j < nums.length; j++){
-
- nums[j] = result.get(i+1).get(j);
- }
-
- }
-
- else if (is && i == result.size()-1){
-
- for(int j = 0; j < nums.length; j++){
-
- nums[j] = result.get(0).get(j);
- }
- }
- }
-
-
- for(int p = 0; p< nums.length; p++) {
-
- System.out.println(nums[p]);
- }
-
- }
-
- public static void permute(ArrayList<ArrayList <Integer>> result, int[] input, int i ,int length) {
-
- if(i == length-1) {
-
- ArrayList<Integer> list = new ArrayList<Integer>();
-
- for(int n = 0 ; n< input.length; n++) {
-
- Integer mm = new Integer(input[n]);
- list.add(mm);
- }
-
- result.add(list);
- return;
-
- }
-
- for(int j = i; j < length; j++) {
-
- if(!isExist(input,i,j)) {
-
- swap(input, i ,j);
-
- permute(result,input,i+1,input.length);
-
- swap(input, i,j);
-
- }
-
- }
-
- }
-
- public static boolean isExist(int[] lst, int i, int j) {
-
- for(int x = i ; x < j ; x++) {
-
- if(lst[x] == lst[j]) {
-
- return true;
-
- }
- }
-
- return false;
- }
-
- public static void swap(int[] lst ,int i, int j) {
-
- int temp = lst[j];
-
- lst[j] = lst[i];
-
- lst[i] = temp;
- }
- }
复制代码
尽管答案是正确的,提交leetcode依然会报错。
原因是因为题目中要求只允许只用 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:
- import java.util.*;
- public class Solution {
-
- public static void nextPermutation(int[] nums) {
-
-
- int start = nums.length -2;
-
- while(start >= 0 && nums[start] >= nums[start +1]) {
-
- start --;
- }
-
- if(start >= 0){
-
- int end = nums.length -1;
-
- while(end >= 0 && nums[end] <= nums[start]){
-
- end -- ;
- }
-
- swap(nums,start,end);
- }
-
-
- reverse(nums, start+1);
-
-
- }
-
- public static void reverse(int[] nums, int i) {
-
- int len = nums.length-1;
-
- while(i < len) {
-
- swap(nums, i++ , len--);
- }
- }
-
- public static void swap(int[] nums, int i, int j) {
-
- int temp = nums[i];
-
- nums[i] = nums[j];
-
- nums[j] = temp;
- }
- }
复制代码
|
|