java每日练习-day10

今天写一下关于Java中全排列的问题，从最基础入门加上几道练习题，希望自己加深一下印象～～～ 基础匹配子序列的单词数全排列全排列 II字符串的排列 1. 基础： package 每日博客_day10全排列; import java.util.Arrays; public class 基础_01 { public static void main(String[] args) { int [] arr=new int [] {1,2,3,4}; getSort(arr,0,arr.length-1); } private static void getSort(int[] arr, int start, int end) { //结束条件 if(start==end) { System.out.println(Arrays.toString(arr)); }else { for(int i=start;i<=end;i++) { swap(arr,start,i); getSort(arr,start+1,end); swap(arr,start,i); } } } private static void swap(int[] arr, int start, int i) { int temp=arr[start]; arr[start]=arr[i]; arr[i]=temp; } }

2. 给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。 示例: 输入: S = “abcde” words = [“a”, “bb”, “acd”, “ace”] 输出: 3 解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。

“dsahjpjauf” [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]

public static int numMatchingSubseq(String S, String[] words) { int count=words.length; for(int i=0;i<words.length;i++) { int index=-1; String new_s=words[i]; char [] chs=new_s.toCharArray(); for(int j=0;j<chs.length;j++) { index=S.indexOf(chs[j],index+1); if(index==-1) { count--; break; } } } return count; }

3. 给定一个没有重复数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

public static List<List<Integer>> permute(int[] nums) { List<List<Integer>>arraylist=new ArrayList<>(); return recursion(arraylist, nums, 0, nums.length-1); } //核心 public static List<List<Integer>> recursion(List<List<Integer>> al,int[]nums,int begin,int end){ List<Integer>al2=new ArrayList<>(); if(begin==end){ for(int i=0;i<=end;i++){ al2.add(nums[i]); } al.add(al2); return al; }else{ for(int j=begin;j<=end;j++){ exch(nums,begin,j); recursion(al,nums, begin+1, end); exch(nums,begin,j); } return al; } } //交换 private static void exch(int[] nums, int i, int j) { int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; }

4. 给定一个可包含重复数字的序列，返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

public static List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> arrayList=new ArrayList<>(); return getSort(arrayList,nums,0,nums.length-1); } private static List<List<Integer>> getSort(List<List<Integer>> arrayList, int[] nums, int start, int end) { List<Integer> al=new ArrayList<>(); //结束标志 if(start==end) { for(int num:nums) { al.add(num); } if(!arrayList.contains(al)) { arrayList.add(al); } }else { for(int j=start;j<=end;j++) { // if(j!=start && nums[start]==nums[j]) { // continue; // } swap(nums,start,j); getSort(arrayList,nums,start+1,end); swap(nums,start,j); } } return arrayList; } private static void swap(int[] nums, int start, int j) { int temp=nums[start]; nums[start]=nums[j]; nums[j]=temp; }

5. 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”). 示例2: 输入: s1= “ab” s2 = “eidboaoo” 输出: False

private static boolean checkInclusion(String s1, String s2) { if(s1==null||s2==null||s1.length()>s2.length()) { return false; } //找出出现的次数，比较次数是否相同 int [] count1=new int[26]; int [] count2=new int[26]; for(int i=0;i<s1.length();i++) { count1[s1.charAt(i)-'a']++; count2[s2.charAt(i)-'a']++; } int [] diff=new int[26]; for(int i=0;i<diff.length;i++) { diff[i]=count2[i]-count1[i]; } for(int i=s1.length();i<s2.length();i++) { if(isSame(diff)) { return true; } diff[s2.charAt(i-s1.length())-'a']--; diff[s2.charAt(i)-'a']++; } return isSame(diff); } private static boolean isSame(int[] diff) { for(int d:diff) { if(d!=0) { return false; } } return true; }