import java.util.*;
public class Main {
public static void main(String[] args) {
// while (true){
// Scanner in=new Scanner(System.in);
// Object data = in.next();
// System.out.println(data);
// if ("exit".equals(data)){
// return;
// }
// }
// GCD1(27,15);
// GCD2(27,15);
// cr(1);
// cr(2); // 2--》1.599 216--》6.0
// zfnx("I am a student"); // tneduts a ma I
// zmhz(new int[]{2, 5, 1, 5, 4, 5});
// zmhz(new int[]{1,2,3,4,5,5});
// zftj("aadddccddc");
// zftj("abbcccdddd");
// zftj("aabbgggeee");
// pf(24);
// ws();
// oneCount(5);
}
// public static void s(){
//
// }
// 二進制 1的二叔
// 5 -> 2
public static void oneCount(int a){
int count=0;
String str=Integer.toBinaryString(a);
for (int j = 0; j <str.length() ; j++) {
if(str.charAt(j)=='1'){
count++;
}
}
System.out.println(String.format("%d 的二進制中 1 的個數: %d",a,count));
}
// 單詞排序 word sort
public static void ws(){
String[] words = new String[]{"oyester", "orange", "cherry", "apple"};
for (int i = 0; i < words.length; i++) {
for (int j = i+1; j < words.length ; j++) {
if (words[i].compareTo(words[j])>0){ // 前比後大，交換
String tmp = words[i];
words[i] = words[j];
words[j] = tmp;
}
}
}
System.out.println(Arrays.asList(words));
}
//分解質因數,Prime factorization
// 180 -> 2 2 3 3 5
// 24 -> 2 2 2 3
public static void pf(int a){
int a1 =a;
int i=2;
while(i<=a1)
{
if(a1%i==0)
{
System.out.println(String.format("%d 的一個質因數: %d",a, i));
a1/=i;
}
else
i++;
}
}
// 最大公約數 Greatest Common Divisor(GCD)
// 兩個整數的最大公約數，27，15 --》 最大公約數 3
public static void GCD1(int a, int b){
int a1=0; // 臨時變數確保 a》b
int b1=0;
if (a>b){
a1=a;
b1=b;
}else{
a1=b;
b1=a;
}
int c1 = a1 % b1;
while (c1 != 0){
a1=b1;
b1=c1;
c1 = a1 % b1;
}
System.out.println(String.format("%d,%d 的最大公約數是 %d", a,b,b1));
}
// 窮舉法求最大公約數
public static void GCD2(int a, int b){
int c=0;
if (a>b){
c=b;
}else{
c=a;
}
for (int i = c; i > 0; i--) {
if (a % i == 0 && b % i == 0) {
c = i;
break;
}
}
System.out.println(String.format("%d,%d 的最大公約數是 %d", a,b,c));
}
// 最小公倍數 Least Common Multiple
// 公式：最小公倍數=兩整數的乘積÷最大公約數
public static void LCM(int a, int b){
System.out.println();
}
// 立方根 Cube root
public static void cr(double a){
double c = 0;
if(a==0 || a==1 || a==-1){
System.out.println(String.format("%.0f 立方根是 %.1f", a, c));
}
double l=a>0?0:a,r=a>0?a:0; // l, r 是左右邊界，正數就是 l=0 r=正數本身
// 求左右邊界的中值的立方比較大小，窮舉
double m1 = a; //上次的根
while(l<r)
{
double m=(l+r)/2;
// 如果m與上次計算的m的前幾位（取決於精度要求）相同，則停止後面的計算
double cha = m1 - m;
if (cha < 0) cha *=-1;
if (cha > 0 && cha < 0.0001){
c = m;
break;
}
double t=m*m*m;
if(t>a) r=m; //如果要求保留五位小數t-x<0.00001
else if(t<a) l=m;
else c=m;
m1= m;
}
System.out.println(String.format("%.0f 立方根是 %.3f", a, c));
}
// 字串逆序
public static void zfnx(String s){
System.out.println();
char[] c = s.toCharArray();
for (int i = 0; i < c.length/2; i++) {
char temp = c[i];
c[i] = c[ c.length-i-1];
c[ c.length-i-1] = temp;
}
System.out.println(String.format("%s 的字元逆序:%s,%s",s, new StringBuilder(s).reverse().toString(),new String(c)));
}
// 負數個數，正數平均值, 負個正均
public static void fgzj(int[] a){
int fcount = 0; //負數統計
int zcount = 0; // 正數統計
int zsum = 0; // 正數和
for (int i = 0; i < a.length; i++) {
if (a[i] < 0){
fcount++;
}else{
zcount++;
zsum+=a[i];
}
}
}
// Redraiment是走梅花樁的高手
// 2 5 1 5 4 5 --> 3步
// 最長遞增子序列的長度
public static void zmhz(int[] a){
int n = a.length;
// 用於存放f(i)值；
int[] f = new int[n];
// 以第a1爲末元素的最長遞增子序列長度爲1；
f[0] = 1;
for (int i = 1; i < n; i++) {// 回圈n-1次
// f[i]的最小值爲1；
f[i] = 1;
for (int j = 0; j < i; j++) {// 回圈i次
if (a[j] < a[i] && f[j] > f[i] - 1) {
// 更新f[i]的值。
f[i] = f[j] + 1;
}
}
}
// 這個演算法有兩層回圈，外層回圈次數爲n-1次，內層回圈次數爲i次，
// 演算法的時間複雜度所以T(n)=O(n2)。
System.out.println(f[n - 1]);
}
// 字元統計,統計字串中每個字元頻次，按頻次 高-》低 輸出，頻次相同按ascii 小-》大 輸出
// aadddccddc --> dca
// aabbgggeee --> egab
public static void zftj(String s){
char[] c = s.toCharArray();
int[] asciiCount = new int[256]; // 索引就是 字元對應的ascii 碼
for (int i = 0; i < c.length; i++) {
asciiCount[c[i]]++;
}
TreeMap<Integer,Character> cCount = new TreeMap<>(Comparator.reverseOrder());
HashMap<Character, TreeSet<Character>> cCollision = new HashMap<>();
for (int i = 0; i < asciiCount.length; i++) {
int charAscii = i;
int charCount = asciiCount[i];
if (charCount == 0 ) continue; // ascii碼爲i的字元統計頻次爲0
if (cCount.containsKey(charCount)){ //相同頻次，碰撞，ascii排序
char c1 = cCount.get(charCount); // 相同頻次的第一個字元
TreeSet<Character> cSet = cCollision.get(c1);
if (cSet == null){
cSet = new TreeSet<>();
cSet.add(cCount.get(charCount));
cCollision.put(c1,cSet);
}
cSet.add((char) i);
}else{
cCount.put(charCount,(char) i);
}
}
cCount.forEach((k,v1)->{
if (cCollision.containsKey(v1)){
TreeSet<Character> cSet = cCollision.get(v1);
cSet.forEach(v2-> System.out.print(v2));
}else{
System.out.print(v1);
}
});
}
}