[LeetCode]Permutations,解题报告 - c++编程基础

前言

今天用java写了LeetCode oj上关于全排列的代码，这个算法之前我用c代码详细的讲解过，想看原理的移步：字符串全排列算法
感觉java的集合是神器，而且全排列算法在找工作笔试和面试中经常会出现，所以把java实现的代码也分享以下

题目

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

AC代码

这道题目没有对子ArrayList的顺序有要求

public class Solution {
    public static ArrayList
  
   > permute(int[] num) {
        ArrayList
   
    > list = new ArrayList
    
     >(); if (num.length == 0) { return list; } permutationProcess(num, 0, num.length - 1, list); return list; } public static boolean shouldSwap(int[] num, int bt, int k) { boolean flag = true; for (int i = bt; i < k; i++) { if (num[i] == num[k]) { flag = false; break; } } return flag; } public static void swapArray(int[] num, int a, int b) { if (a != b) { num[a] = num[a] ^ num[b]; num[b] = num[a] ^ num[b]; num[a] = num[a] ^ num[b]; } } public static void permutationProcess(int[] num, int bt, int ed, ArrayList
     
      > list) { if (bt == ed) { ArrayList
      
        newlist = new ArrayList
       
        (num.length); for (int val : num) { newlist.add(Integer.valueOf(val)); } list.add(newlist); } else { for (int k = bt; k <= ed; k++) { if (shouldSwap(num, bt, k)) { swapArray(num, bt, k); permutationProcess(num, bt + 1, ed, list); swapArray(num, bt, k); } } } } }