StringTokenizer和进制的转变,关于各类排列组合java算法完成方式
分类:高并发

~~~~~~~~~~~~~~~~~~~~··

一.施用二进制状态法求排列组合,此种方法相比较便于懂,不过运转功能不高,小数目排列组合能够运用

此地指的java速成,只限于java语法,富含输入输出,运算管理,字符串和高精度的管理,进制之间的更换等,能化解OJ上的片段高精度标题。

<h2>剑指offer(四)</h2>

package com.yds.text4;

复制代码 代码如下:
import java.util.Arrays;

  1. 输入:
    格式为:Scanner cin = new Scanner (new BufferedInputStream(System.in));

<h3>面试题三十:数组中只现出1次的数字</h3>

import java.util.StringTokenizer;

//利用二进制算法实行全排列
//count1:170187
//count2:291656

例程:

<blockquote>
难点:三个整形数组里除了七个数字之外,其余的数字都现身了五回,请写程序找寻那多个只现出一遍的数字。供给时间复杂度是O(n卡塔尔,空间复杂度是O(1State of Qatar;
</blockquote>

public class StringTokenizeor {

public class test {
public static void main(String[] args) {
long start=System.currentTimeMillis();
count2();
long end=System.currentTimeMillis();
System.out.println(end-start);
}
private static void count2(){
int[] num=new int []{1,2,3,4,5,6,7,8,9};
for(int i=1;i<Math.pow(9, 9);i++){
String str=Integer.toString(i,9);
int sz=str.length();
for(int j=0;j<9-sz;j++){
str="0"+str;
}
char[] temp=str.toCharArray();
Arrays.sort(temp);
String gl=new String(temp);
if(!gl.equals("012345678")){
continue;
}
String result="";
for(int m=0;m<str.length();m++){
result+=num[Integer.parseInt(str.charAt(m)+"")];
}
System.out.println(result);
}
}
public static void count1(){
int[] num=new int []{1,2,3,4,5,6,7,8,9};
int[] ss=new int []{0,1,2,3,4,5,6,7,8};
int[] temp=new int[9];
while(temp[0]<9){
temp[temp.length-1]++;
for(int i=temp.length-1;i>0;i--){
if(temp[i]==9){
temp[i]=0;
temp[i-1]++;
}
}
int []tt=temp.clone();
Arrays.sort(tt);
if(!Arrays.equals(tt,ss)){
continue;
}
String result="";
for(int i=0;i<num.length;i++){
result+=num[temp[i]];
}
System.out.println(result);

图片 1import java.io.*;
图片 2import java.math.*;
图片 3import java.util.*;
图片 4import java.text.*;
图片 5
图片 6public class Main
图片 7图片 8图片 9{
图片 10    public static void main(String[] args) 
图片 11图片 12    图片 13{
图片 14        Scanner cin = new Scanner (new BufferedInputStream(System.in));
图片 15        int a; double b; BigInteger c; String d;
图片 16        a = cin.nextInt(卡塔尔国; b = cin.nextDouble(卡塔尔国; c = cin.nextBigInteger(卡塔尔国; d = cin.nextLine(State of Qatar; // 每连串型都有相应的输入函数.
图片 17    }
图片 18}

<pre><code class="java">package offer;

 /**
  * @param args
  */
 public static void main(String[] args) {
    String m="I am a stud,ents";
    StringTokenizer st=new StringTokenizer(m," ,"卡塔尔(قطر‎;//将字段串按空格和逗号分开
   while(st.hasMoreTokens(卡塔尔卡塔尔(قطر‎{//直到最后一个字符串,重返false
    String str=st.nextToken(State of Qatar;//找到下叁个字符串
    System.out.println(str);
   }

}
}
}

  1. 输出
    函数:System.out.print(); System.out.println(); System.out.printf();
    System.out.print(); // cout << …;
    System.out.println(); // cout << … << endl;
    System.out.printf(卡塔尔国; // 与C中的printf用法相近.

/**

 }

二.用递归的出主意来求排列跟组合,代码量十分的大

例程:

  • Created by KiSoo on 2017/2/7.
    */
    public class Offer40 {
    public static int[] findNumbersAppearanceOnce(int[] data) {
    int[] result = {0, 0};
    if (data == null || data.length < 2) {
    return result;
    }
    int xor = 0;
    for (int i : data) {
    xor ^= i;
    }
    int indexOf1 = findFirstBit1(xor);
    for (int i : data) {
    if (isBit1(i, indexOf1)) {
    result[0] ^= i;
    } else {
    result[1] ^= i;
    }
    }
    return result;
    }

    private static int findFirstBit1(int num) {
    int index = 0;
    while ((num & 1) == 0 && index < 32) {
    num = num >> 1;
    index++;
    }
    return index;
    }

    private static boolean isBit1(int num, int indexBit) {
    num = num >> indexBit;
    return (num & 1) == 1;
    }

    public static void main(String[] args) {
    int[] data1 = {2, 4, 3, 6, 3, 2, 5, 5};
    int[] result1 = findNumbersAppearanceOnce(data1);
    System.out.println(result1[0] + " " + result1[1]);
    int[] data2 = {4, 6};
    int[] result2 = findNumbersAppearanceOnce(data2);
    System.out.println(result2[0] + " " + result2[1]);
    int[] data3 = {4, 6, 1, 1, 1, 1};
    int[] result3 = findNumbersAppearanceOnce(data3);
    System.out.println(result3[0] + " " + result3[1]);
    }
    }

}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~··

复制代码 代码如下:
package practice;

图片 19import java.io.*;
图片 20import java.math.*;
图片 21import java.util.*;
图片 22import java.text.*;
图片 23
图片 24public class Main
图片 25图片 26图片 27{
图片 28    public static void main(String[] args) 
图片 29图片 30    图片 31{
图片 32        int a; double b;
图片 33        a = 12345; b = 1.234567;
图片 34        System.out.println(a + " " + b);
图片 35        System.out.printf("%d %10.5fn", a, b卡塔尔(قطر‎; // 输出b为字宽为10,右对齐,保留小数点后5位,四舍五入.
图片 36    }
图片 37}

</code></pre>

package com.yds.text4;

import java.util.ArrayList;
import java.util.List;

规格化的出口:
函数:
// 这里0指壹位数字,#指除0以外的数字(即便是0,则不出示State of Qatar,四舍五入.
    DecimalFormat fd = new DecimalFormat("#.00#");
    DecimalFormat gd = new DecimalFormat("0.000");
    System.out.println("x =" + fd.format(x));
    System.out.println("x =" + gd.format(x));

<h4>思路</h4>

public class NumberTet {

public class Test1 {

  1. 字符串管理
    java中字符串String是不可能改正的,要改善只可以调换为字符数组.

先将数组中的全数数字异或操作。然后,取得得出的数值的最高位数字k,剖断数字右移k后是还是不是为0。假使为0,则为率先个数字,而将余下的数字全体异或后就得出第一个不重复的数字啦。

 /**
  * @param args
  */
 public static void main(String[] args) {
 int number=342;
            String n= Long.toBinaryString(number);
            System.out.println(number+"的二进制"+nState of Qatar;
            System.out.println(number+"的十五进制"+Long.toString(number,16卡塔尔(قطر‎卡塔尔(قطر‎;
            System.out.println(number+"的八进制"+Long.toString(number,8卡塔尔(قطر‎卡塔尔(قطر‎;
            int wn=0,mn=0;
            for(int i=n.length()-1;i>=0;i--){
             char m=n.charAt(i);
             int w=Integer.parseInt(m+"");
             wn=(int) (wn+(w*Math.pow(2,mn卡塔尔国State of Qatar卡塔尔(قطر‎;//将二进制转变成十进制
             mn++;
            }
            System.out.println(wn);
 }

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Object[] tmp={1,2,3,4,5,6};
// ArrayList<Object[]> rs=RandomC(tmp);
ArrayList<Object[]> rs=cmn(tmp,3);
for(int i=0;i<rs.size();i++)
{
// System.out.print(i+"=");
for(int j=0;j<rs.get(i).length;j++)
{
System.out.print(rs.get(i)[j]+",");
}
System.out.println();

例程:

<h3>面试题四十九:和为s的多少个数字VS和为s的总是正数种类</h3>

}

}
}

图片 38import java.io.*;
图片 39import java.math.*;
图片 40import java.util.*;
图片 41import java.text.*;
图片 42
图片 43public class Main
图片 44图片 45图片 46{
图片 47    public static void main(String[] args) 
图片 48图片 49    图片 50{
图片 51        int i;
图片 52        String st = "abcdefg";
图片 53        System.out.println(st.charAt(0卡塔尔(قطر‎卡塔尔(قطر‎; // st.charAt(iState of Qatar就一定于st[i].
图片 54        char [] ch;
图片 55        ch = st.toCharArray(卡塔尔国; // 字符串转变为字符数组.
图片 56        for (i = 0; i < ch.length; i++) ch[i] += 1;
图片 57        System.out.println(ch); // 输出为“bcdefgh”.
图片 58        if (st.startsWith("a"卡塔尔(قطر‎卡塔尔 // 如若字符串以'0'发轫.
图片 59图片 60        图片 61{
图片 62            st = st.substring(1卡塔尔; // 则从第2位初步copy(初始为第0位).
图片 63        }
图片 64    }
图片 65}

<blockquote>
题材一:输入贰个依次增加排序的数组和叁个数字s,在数组中寻觅多个数,使得它们的和刚刚是s。若是有多对数字的和等于s。输出大肆一对就能够。
</blockquote>

// 求一个数组的自便组合
static ArrayList<Object[]> RandomC(Object[] source)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(source.length==1)
{
result.add(source);
}
else
{
Object[] psource=new Object[source.length-1];
for(int i=0;i<psource.length;i++)
{
psource[i]=source[i];
}
result=RandomC(psource);
int len=result.size(卡塔尔;//fn组合的尺寸
result.add((new Object[]{source[source.length-1]}));
for(int i=0;i<len;i++)
{
Object[] tmp=new Object[result.get(i).length+1];
for(int j=0;j<tmp.length-1;j++)
{
tmp[j]=result.get(i)[j];
}
tmp[tmp.length-1]=source[source.length-1];
result.add(tmp);
}

 

<pre><code class="java">package offer;

}
return result;
}

  1. 高精度
    BigInteger和BigDecimal能够说是acmer选用java的重视原因。
    函数:add, subtract, divide, mod, compareTo等,在那之中加减乘除模都要求是BigInteger(BigDecimal卡塔尔国和BigInteger(BigDecimal卡塔尔(قطر‎之间的演算,所以须要把int(double)类型调换为BigInteger(BigDecimal卡塔尔(قطر‎,用函数BigInteger.valueOf(卡塔尔国.

import java.util.Arrays;

static ArrayList<Object[]> cmn(Object[] source,int n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(n==1)
{
for(int i=0;i<source.length;i++)
{
result.add(new Object[]{source[i]});

例程:

/**

}
}
else if(source.length==n)
{
result.add(source);
}
else
{
Object[] psource=new Object[source.length-1];
for(int i=0;i<psource.length;i++)
{
psource[i]=source[i];
}
result=cmn(psource,n);
ArrayList<Object[]> tmp=cmn(psource,n-1);
for(int i=0;i<tmp.size();i++)
{
Object[] rs=new Object[n];
for(int j=0;j<n-1;j++)
{
rs[j]=tmp.get(i)[j];
}
rs[n-1]=source[source.length-1];
result.add(rs);
}
}
return result;
}

图片 66import java.io.*;
图片 67import java.math.*;
图片 68import java.util.*;
图片 69import java.text.*;
图片 70
图片 71public class Main
图片 72图片 73图片 74{
图片 75    public static void main(String[] args) 
图片 76图片 77    图片 78{
图片 79        int a = 123, b = 456, c = 7890;
图片 80        BigInteger x, y, z, ans;
图片 81        x = BigInteger.valueOf(a); y = BigInteger.valueOf(b); z = BigInteger.valueOf(c);
图片 82        ans = x.add(y); System.out.println(ans);
图片 83        ans = z.divide(y); System.out.println(ans);
图片 84        ans = x.mod(z); System.out.println(ans);
图片 85        if (ans.compareTo(x) == 0) System.out.println("1");
图片 86    }
图片 87}

  • Created by KiSoo on 2017/2/7.
    */
    public class offer41 {

    public static void main(String... args) {
    int[] a = {1, 2, 4, 7, 11, 15};
    Utils.syso(Arrays.toString(getResult(a, 15)));
    }

    public static int[] getResult(int[] data, int target) {
    int[] result = {0, 0};
    if (data == null) {
    return result;
    }
    int index1 = data.length - 1;
    int index2 = 0;
    while (index1 > index2) {
    int curr = data[index1] + data[index2];
    if (curr == target) {
    result[0] = data[index1];
    result[1] = data[index2];
    return result;
    } else if (curr > target) {
    index1--;
    } else index2++;
    }
    return result;
    }
    }

}

 

</code></pre>

三.利用动态规划的动脑筋求排列和组成

  1. 进制调换
    java很强盛的一个效果与利益。
    函数:
    String st = Integer.toString(num, base卡塔尔(قطر‎; // 把num当作10进制的数转成base进制的st(base <= 35卡塔尔.
    int num = Integer.parseInt(st, base卡塔尔; // 把st当作base进制,转成10进制的int(parseInt有七个参数,第二个为要转的字符串,第二个为证实是哪些进制卡塔尔(قطر‎.  
    BigInter m = new BigInteger(st, base卡塔尔; // st是字符串,base是st的进制.

<h4>思路</h4>

复制代码 代码如下:
package Acm;
//强盛的求组合数
public class MainApp {
public static void main(String[] args) {
int[] num=new int[]{1,2,3,4,5};
String str="";
//求3个数的结合个数
// count(0,str,num,3);
// 求1-n个数的构成个数
count1(0,str,num);
}

(1卡塔尔国.借使要将叁个天数以2进制方式读入 可以采纳cin.nextBigInteger(2卡塔尔(قطر‎;
自然也能够利用别的进制形式读入;
(2卡塔尔国.借使要将一个天数转换到别的进制形式的字符串 使用cin.toString(2卡塔尔(قطر‎;//将它调换到2进制表示的字符串
例程:POJ 2305

七个指针,分别指向首尾,然后各种相加,大于的话,尾指针前移,小于则首指针后移。

private static void count1(int i, String str, int[] num) {
if(i==num.length){
System.out.println(str);
return;
}
count1(i+1,str,num);
count1(i+1,str+num[i]+",",num);
}

图片 88import java.io.*;
图片 89import java.util.*;
图片 90import java.math.*;
图片 91
图片 92public class Main
图片 93图片 94图片 95{
图片 96    public static void main(String[] args)
图片 97图片 98    图片 99{
图片 100        int b;
图片 101        BigInteger p,m,ans;
图片 102        String str ;
图片 103        Scanner cin = new Scanner (new BufferedInputStream(System.in));
图片 104        while(cin.hasNext())
图片 105图片 106        图片 107{
图片 108            b=cin.nextInt();
图片 109            if(b==0)
图片 110                break;
图片 111            p=cin.nextBigInteger(b);
图片 112            m=cin.nextBigInteger(b);
图片 113            ans=p.mod(m);
图片 114            str=ans.toString(b);
图片 115            System.out.println(str);
图片 116        }
图片 117    }
图片 118}

<blockquote>
标题二:输入多个正数s,打字与印刷出全体和为s的连年正数系列。
</blockquote>

private static void count(int i, String str, int[] num,int n) {
if(n==0){
System.out.println(str);
return;
}
if(i==num.length){
return;
}
count(i+1,str+num[i]+",",num,n-1);
count(i+1,str,num,n);
}
}

  1. 排序
    函数:Arrays.sort();

<pre><code class="java">public static void findArray(int num) {
if (num < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + num) / 2;
int curSum = small + big;
while (small < middle) {
if (curSum == num)
System.out.println(small + "-->" + big);
while (curSum > num && small < middle) {
curSum -= small;
small++;
if (curSum == num)
System.out.println(small + "-->" + big);
}
big++;
curSum += big;
}
}
</code></pre>

上边是求排列

例程:

<h4>思路</h4>

复制代码 代码如下:

图片 119import java.io.*;
图片 120import java.math.*;
图片 121import java.util.*;
图片 122import java.text.*;
图片 123
图片 124public class Main
图片 125图片 126图片 127{
图片 128    public static void main(String[] args) 
图片 129图片 130    图片 131{
图片 132        Scanner cin = new Scanner (new BufferedInputStream(System.in));
图片 133        int n = cin.nextInt();
图片 134        int a[] = new int [n];
图片 135        for (int i = 0; i < n; i++) a[i] = cin.nextInt();
图片 136        Arrays.sort(a);
图片 137        for (int i = 0; i < n; i++) System.out.print(a[i] + " ");
图片 138    }
图片 139}

遍历(k+1卡塔尔国/2,不停地叠加终点,要是超越,就减去起点。起源++。直到起源大于半值。

package Acm;
//求排列,求种种排列或结成后排列
import java.util.Arrays;
import java.util.Scanner; public class Demo19 {
private static boolean f[];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int sz=sc.nextInt();
for(int i=0;i<sz;i++){
int sum=sc.nextInt();
f=new boolean[sum];
Arrays.fill(f, true);
int[] num=new int[sum];
for(int j=0;j<sum;j++){
num[j]=j+1;
}
int nn=sc.nextInt();
String str="";
count(num,str,nn);
}
}
/**
*
* @param num 代表要排列的数组
* @param str 以排列好的字符串
* @param nn 剩下要求排列的个数,假设需求全排列,则nn为数首席营业官度
*/
private static void count(int[] num, String str, int nn) {
if(nn==0){
System.out.println(str);
return;
}
for(int i=0;i<num.length;i++){
if(!f[i]){
continue;
}
f[i]=false;
count(num,str+num[i],nn-1);
f[i]=true;
}
}
}

  1. POJ高精度标题汇总:
    POJ 1131 1205 1220 1405 1503 1604 1894 2084 2305 2325 2389 2413 3101 3199

<h3>面试题三十三:翻转单词顺序 VS 左旋旋转字符串</h3>

复制代码 代码如下: import java.util...

<blockquote>
难点一:输入二个葡萄牙语句子,反转句子中单词的相继,但单词内字符串的相继不改变。为简便起见,标点符号和平日字母相像管理。举例,输入字符串"I am a student.",则输出“student. a am I"。
</blockquote>

<h4>思路</h4>

1.先全勤反转,再分单词反转。
2.施用栈,把单词全拷贝步向,然后再分单词读出。

<pre><code class="java">package offer;

import java.util.Stack;

/**

  • Created by KiSoo on 2017/2/8.
    */
    public class Offer42 {
    public static void main(String... args) {
    String str = "I am a student.";
    String str1 = getReverse(str);
    Utils.syso(str1);
    }

    private static String getReverse2(String str) {
    StringBuilder temp = new StringBuilder();
    Stack<String> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    if (c != ' ') {
    temp.append(c);
    } else {
    stack.push(temp.toString());
    temp.delete(0, temp.length() - 1);
    }
    }
    stack.push(temp.toString());
    temp.delete(0, temp.length() - 1);
    for (String c : stack) {
    temp.append(c).append(" ");
    }
    temp.delete(temp.length() - 1, temp.length());
    return temp.toString();
    }

    private static String getReverse(String str) {
    char[] chars = str.toCharArray();
    reverse(chars, 0, chars.length - 1);
    reverseSentence(chars);
    return new String(chars);
    }

    public static void reverseSentence(char[] chars) {
    if (chars == null)
    return;
    int begin = 0, end = 0;
    while (begin < chars.length - 1) {
    if (chars[begin] == ' ') {
    begin++;
    end++;
    } else if (chars[end] == ' ' || end == chars.length - 1) {
    reverse(chars, begin, end - 1);
    begin = end;
    } else {
    end++;
    }
    }

    }

    private static char[] reverse(char[] chars, int index1, int index2) {
    while (index1 < index2) {
    char temp = chars[index1];
    chars[index1] = chars[index2];
    chars[index2] = temp;
    index1++;
    index2--;
    }
    return chars;
    }
    }

</code></pre>

<blockquote>
主题素材二:字符串的左旋转操作是把字符串前边的好五个字符转移到字符串的尾巴,请定义叁个函数完成字符串左旋转操作的效果与利益。举个例子输入字符串abcdefg和数字2,该函数将回来左旋转2位获得的结果“cdefgab”。
</blockquote>

<pre><code> public static void leftRotate(char[] data,int n){
reverse(data,0,n-1);
reverse(data,n,data.length-1);
reverse(data,0,data.length-1);
}
</code></pre>

<h3>面试题二十九:n个骰子的罗列</h3>

<pre><code>package offer;

public class Offer43 {
/**
* 基于通归求解
*
* @param number 色子个数
* @param max 色子的最大值
/
public static void printProbability(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int maxSum = number
max;
int[] probabilities = new int[maxSum - number + 1];
probability(number, probabilities, max);
double total = 1;
for (int i = 0; i < number; i++) {
total = max;
}
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[i - number] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
/**
@param number 色子个数
* @param probabilities 不相同色子数现身次数的计数数组
* @param max 色子的最大值
/
private static void probability(int number, int[] probabilities, int max) {
for (int i = 1; i <= max; i++) {
probability(number, number, i, probabilities, max);
}
}
/
*
* @param original 总的色子数
* @param current 当前拍卖的是第多少个
* @param sum 已经后面包车型大巴色子数和
* @param probabilities 区别色子数现身次数的计数数组
* @param max 色子的最大值
/
private static void probability(int original, int current, int sum, int[] probabilities, int max) {
if (current == 1) {
probabilities[sum - original]++;
} else {
for (int i = 1; i <= max; i++) {
probability(original, current - 1, i + sum, probabilities, max);
}
}
}
/
*
* 基于循环求解
* @param number 色子个数
* @param max 色子的最大值
*/
public static void printProbability2(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int[][] probabilities = new int[2][max * number + 1];
// 数据开头化
for (int i = 0; i < max * number + 1; i++) {
probabilities[0][i] = 0;
probabilities[1][i] = 0;
}
// 标识当前要接纳的是第0个数组依然第4个数组
int flag = 0;
// 抛出多少个骰龙时现身的各样情况
for (int i = 1; i <= max; i++) {
probabilities[flag][i] = 1;
}
// 抛出此外骰子
for (int k = 2; k <= number; k++) {
// 若是抛出了k个骰子,那么和为[0, k-1]的现身次数为0
for (int i = 0; i < k; i++) {
probabilities[1 - flag][i] = 0;
}
// 抛出k个骰子,全数和的恐怕
for (int i = k; i <= max * k; i++) {
probabilities[1 - flag][i] = 0;
// 每一种骰子的面世的具有恐怕的罗列
for (int j = 1; j <= i && j <= max; j++) {
// 总结出和为i的点数现身的次数
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = 1;
for (int i = 0; i < number; i++) {
total *= max;
}
int maxSum = number * max;
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[flag][i] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
public static void main(String[] args) {
test01();
test02();
}
private static void test01() {
printProbability(2, 4);
}
private static void test02() {
printProbability2(2, 4);
}
}
</code></pre>

<h3>面试题八十六:扑克牌的顺子</h3>

<blockquote>
主题素材:从扑克牌中随机抽5张牌,判定是还是不是一个顺子,即这五张牌是还是不是连连的,2~10为数字本身,A为1,J为11,Q为12,K为13。大小王能够作为自便数字。
</blockquote>

<h4>思路</h4>

超快排序那组数组。

<pre><code>package offer;

import static offer.SortUtils.exchangeE;

/**

  • Created by KiSoo on 2017/2/10.
    */
    public class Offer44 {
    public static void main(String... args) {
    int[] a = {7, 6, 4, 8, 2};
    Utils.syso(isContinous(a));
    }

    public static boolean isContinous(int[] numbers) {
    if (numbers == null || numbers.length < 5) {
    return false;
    }
    quickSort(numbers, 0, numbers.length - 1);
    int numOfZero = 0;
    int numOfGap = 0;
    for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == 0)
    numOfZero++;
    }
    int small = numOfZero;
    int big = small + 1;
    while (big < numbers.length) {
    if (numbers[small] == numbers[big]) {
    return false;
    }
    numOfGap += numbers[big] - numbers[small] - 1;
    small = big;
    big++;
    }
    return numOfZero >= numOfGap;
    }

    private static void quickSort(int[] numbers, int start, int end) {
    if (start > end)
    return;
    int i = sort(numbers, start, end);
    if (i == start) {
    quickSort(numbers, start + 1, end);
    } else if (i == end) {
    quickSort(numbers, start, end - 1);
    } else {
    quickSort(numbers, start, i - 1);
    quickSort(numbers, i + 1, end);
    }
    }

    private static int sort(int[] numbers, int left, int right) {
    int index = left;
    int target = numbers[right];
    for (int i = left; i < right; i++) {
    if (numbers[i] < target) {
    if (i != index) {
    exchangeE(numbers, index, i);
    }
    index++;
    }
    }
    exchangeE(numbers, index, right);
    return index;
    }
    }

</code></pre>

<h3>面试题二十四:圆圈中最终剩下的数字</h3>

<blockquote>
主题素材:从0,1,...,n-1这n个数字排成多个圆形,从数字0起初每一次从那些圈子里删除第m个数字,求出这些圈子里剩余的末尾贰个数字。
</blockquote>

<h4>思路</h4>

<ol>
<li>使用一个环形链表,模拟圆圈。</li>
<li>推倒出公式,利用递归或循环。</li>
</ol>

<pre><code class="java">package offer;

import java.util.ArrayList;

/**

  • Created by KiSoo on 2017/2/10.
    */
    public class Offer45 {
    public static void main(String... args) {
    Utils.syso(lastRemaining(5, 3));
    }

    public static int lastRemaining(int n, int m) {
    ArrayList<Integer> array = new ArrayList<>();
    for (int i = 0; i < n; i++) {
    array.add(i);
    }
    int idx = 0;
    while (array.size() != 1) {
    idx = (idx + m - 1) % array.size();
    array.remove(idx);
    }
    return array.get(0);
    }

    public static int getM(int m, int size) {
    m = 3 + m;
    while (m > size) {
    m = m - size;
    }
    return m;
    }
    }

</code></pre>

本文由10bet手机官网发布于高并发,转载请注明出处:StringTokenizer和进制的转变,关于各类排列组合java算法完成方式

上一篇:图形界面编程,坦克大战 下一篇:没有了
猜你喜欢
热门排行
精彩图文