Java@點到為止: 3月 2020

2020年3月8日星期日

a147. Print it all

核心：i % 7 == 0? "": i + " "
如果i被7整除就輸出空字串，不整除就輸出i加空白。Yeah

BTW科皓不要

程式碼如下：

/* Pa147.java
* a147. Print it all 
*
* 我的意思是說 科皓不要啦
* 2020/3/8
*/

import java.util.Scanner;

public class Pa147{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int n = scanner.nextInt();

            for(int i = 1; i < n; i++){
                System.out.print(i % 7 == 0? "": i + " ");
            }

            System.out.println();
        }

    } 
}

a121. 質數又來囉

決定使用比較懶的方法，BigInteger再度出場，大材小用，牛刀割雞，把你用在這邊真是抱歉哈～

        if(big(元a)是質數) // 因為不管怎樣下面的迴圈都會執行一次，導致sum+1，所以如果a是質數的話要先-1，免得加兩次
            sum = -1
        else
            sum = 0
        
        while(big <= b){
            big = 下一個可能質數
            sum++
        }

很棒吧，只是單單輸出sum還不夠，因為不知道哪一筆資料會讓sum = -1，想破頭也想不出來什麼樣的情況會讓sum = -1，索性在sum == -1時輸出0
可能是真的有BUG吧，阿彌陀佛。

程式碼如下：

/* Pa121.java
 * a121. 質數又來囉 
 *
 * 科皓不要
 * 2020/3/8
 */

import java.util.Scanner;
import java.math.BigInteger;

public class Pa121{

 public static void main(String[] args){
  Scanner scanner = new Scanner(System.in);

  while(scanner.hasNext()){
   BigInteger big = new BigInteger(scanner.next());
   BigInteger b = new BigInteger(scanner.next());
   
   int sum = big.isProbablePrime(1000)? 0: -1;

   while(big.compareTo(b) != 1){
    big = big.nextProbablePrime();
    sum++;
   }

   System.out.println(sum == -1? 0: sum);
  }

 } 
}

Arrays提供了sort（排序）方法，如果想要了解實作可以參考：演算法筆記Sort
Arrays還有toString，可以印出陣列，比方說{0, 1, 2, 3}的陣列會印成[0, 1, 2, 3]，可是不需要逗號和中括號，所以用String本身就有的replaceAll方法，用正規表示式(regular expression)去把[或]或,挑出來取代成空字串（殺掉）。
那個括號居然要兩個反斜線來表示，真是攪死我了。參考：Backslashes, escapes, and quoting

程式碼如下：

/* Pa104.java
* a104. 排序 
*
* 科皓不要
* 2020/3/8
*/

import java.util.Scanner;
import java.util.Arrays;

public class Pa104{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int[] nums = new int[scanner.nextInt()];
            
            for(int i = 0; i < nums.length; i++){
                nums[i] = scanner.nextInt();
            } 

            Arrays.sort(nums);

            System.out.println(Arrays.toString(nums).replaceAll("[\\[\\],]", ""));
        }

    } 
}

2020年3月7日星期六

[zerojudge]a095. 麥哲倫的陰謀

a095. 麥哲倫的陰謀

因為黃色比較漂亮，絕對不是因為我畫錯了

1個紅帽：
1. 紅帽看到其他人都是黃帽→我就是紅帽，出去
2. 黃帽發現紅帽走了→我不是紅帽，出去
2個紅帽：
1. 紅帽看到有一個紅帽，不能確定自己是不是紅帽
2. 紅帽發現那個紅帽沒有走→那個紅帽看到有其他紅帽→那個紅帽就是我，出去
3. 黃帽發現兩個紅帽都走了→我是黃帽，出去
3個紅帽：
1. 紅帽看到有兩個紅帽，不能確定自己是不是紅帽
2. 紅帽發現那兩個紅帽都沒有走，不能確定自己是不是紅帽
3. 紅帽發現那兩個紅帽都沒有走→我是紅帽，出去
4. 黃帽發現三個紅帽都走了→我是黃帽，出去
4個紅帽：
1. 紅帽看到有三個紅帽，不能確定自己是不是紅帽
2. 紅帽發現那三個紅帽都沒有走，不能確定自己是不是紅帽
3. 紅帽發現那三個紅帽都沒有走，不能確定自己是不是紅帽
4. 紅帽發現那三個紅帽都沒有走→我就是紅帽，出去

出去的前提是「完全確定自己是什麼顏色」，反過來說不出去是因為「不能確定自己是什麼顏色」。

完全不知道自己在講什麼，反正就是if(n == m) m天，else就m + 1天。

程式碼如下：

/* Pa095.java
* a095. 麥哲倫的陰謀 
*
* 科皓不要
* 2020/3/8
*/

import java.util.Scanner;

public class Pa095{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int m = scanner.nextInt(); 
            
            System.out.println(n == m? m: m + 1);
        }

    }
    
}

[zerojudge]a065. 提款卡密碼

a065. 提款卡密碼

迴圈次數
很顯然你只要跑n-1次迴圈兩兩比對就可以了。
字元可以做運算，酷吧！

程式碼如下：

/* Pa065.java
* a065. 提款卡密碼 
*
* 科皓不要
* 2020/3/7
*/

import java.util.Scanner;

public class Pa065{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            char[] chs = scanner.next().toCharArray();
            
            for(int i = 0; i < chs.length - 1; i++){
                System.out.print(Math.abs(chs[i] - chs[i+1]));
            } 

            System.out.println();
        }
    }
}

[zerojudge]a059. 完全平方和

a059. 完全平方和

在a~b之間尋找平方數然後加總，所以要找平方後>=a與平方後<=b的兩個數當作起點和終點
開根號a之後可能是整數或小數，如果是小數就要「無條件進位」(ceiling)，b則「無條件捨去」(floor)。
ceiling = 天花板
floor = 地板

程式碼如下：

/* Pa059.java
* a059. 完全平方和 
*
* 科皓不要
* 2020/3/7
*/

import java.util.Scanner;

public class Pa059{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){

            int T = scanner.nextInt();

            for(int i = 1; i <= T; i++){
                int sum = 0;
                int a = (int)Math.ceil(Math.sqrt(scanner.nextInt()));
                int b = (int)Math.floor(Math.sqrt(scanner.nextInt()));

                for(; a <= b; a++){
                    sum += a * a;
                }

                System.out.println("Case " + i + ": " + sum);
            }
        }
    }
}

[zerojudge]a058. MOD3

a058. MOD3

一臉就是要用陣列解的樣子，不用對不起它。因為%3, %3 + 1, %3 + 2是連續的嘛～

程式碼如下：

/* a058. MOD3
* Pa058.java
*
* 科皓不要
* 2020/3/7
*/

import java.util.Scanner;

public class Pa058{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int[] k = {0, 0, 0};
            int n = scanner.nextInt();

            for(int i = 0; i < n; i++){
                k[scanner.nextInt() % 3]++;
            }

            System.out.printf("%d %d %d%n", k[0], k[1], k[2]);
        }
    }
}

[zerojudge]a054. 電話客服中心

a054. 電話客服中心

根據輸入提供的身分證後9碼，去列出符合規範的首位字母碼。
想到之前「a020. 身分證檢驗」寫過的程式，複製貼上變成一個方法，檢查該身分證字號是否有效。
main裡面只要簡單的for迴圈讓A~Z跑過一遍，符合的列印出來就好，太輕鬆了吧！但是效率並沒有反向推算來的高喔，有興趣的可以試試看。

程式碼如下：

/* a054. 電話客服中心
*
*
* 2020/3/7
*/

import java.util.Scanner;

public class Pa054{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            String s = scanner.nextLine();

            for(int i = 'A'; i <= 'Z'; i++){
                System.out.print(isValidid((char)i + s)? (char)i: "");
            }

            System.out.println();
        }
    }

    public static boolean isValidid(String input){
        String[] idNum = {"10", "11", "12", "13", "14", "15", "16", "17", "34",
            "18", "19", "20", "21", "22", "35", "23", "24", "25",
            "26", "27", "28", "29", "32", "30", "31", "33"};  

        int[] num = {1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1};

        input = idNum[input.charAt(0) - 'A'] + input.substring(1);

        int sum = 0;

        for(int i = 0; i < input.length(); i++){
            sum += num[i] * Character.getNumericValue(input.charAt(i));
        }

        return sum % 10 == 0; 
    }
}

2020年3月6日星期五

[zerojudge]a053. Sagit's 計分程式

a053. Sagit's 計分程式

答對的題數越多單題得就越低，可以透過巢狀if、for迴圈、多重if之類的來達成，方法很多樣，我使用的是多重if，算式可以再進一步簡化。

想說一下關於&&和&的差別，&是只要一個是False就回傳False了，&&是即便第一個就是False，也會去執行判斷第二個項目。
如果判斷是這樣：a == b & a++ == c，那如果a != b 那 a 就不會+1了。若是寫成 a == b && a++ == c 那不論 a 是否等於 b ，到最後 a 都會+1

	T	F
T	T	F
F	F	F

程式碼如下：

/* a053. Sagit's 計分程式 
*
* 2020/3/7
*/

import java.util.Scanner;

public class Pa053{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int score = 0;

            if(isBetween(0, n, 10)){
                score += n * 6;
            }else if(isBetween(11, n, 20)){
                score += 10 * 6;
                score += (n - 10) * 2;
            }else if(isBetween(21, n, 40)){
                score += 10 * 6;
                score += 10 * 2;
                score += (n - 20) * 1;
            }else{
                score = 100;
            } 

            System.out.println(score);
        }
    }

    public static boolean isBetween(int min, int v, int max){
        return min <= v & v <= max;
    }
}

2020年3月5日星期四

[zerojudge]a044. 空間切割

a044. 空間切割

參考影片：(DM10-20131118-03) 平面分割空間

沒有用lineCut和spaceCut是因為會超時TLE(Time Limit Exceed)

程式碼如下：

/* a044. 空間切割  
*
* 2020/3/5
*/

import java.util.Scanner;

public class Pa044{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            System.out.println(spaceCutSuper(scanner.nextInt()));
        }
    }

    public static int lineCut(int n){
        return n == 0? 1: lineCut(n - 1) + n;
    }

    public static int spaceCut(int n){
        return n == 0? 1: spaceCut(n - 1) + lineCut(n - 1);
    }

    public static int spaceCutSuper(int n){
        return (n * n * n + 5 * n + 6 ) / 6;
    }
}

2020年3月4日星期三

[zerojudge]a042. 平面圓形切割

a042. 平面圓形切割

平面圓形切割

a_n - a_n-1 = 2 * (n - 1), if n > 1
=> a_n = 2 * (n - 1) + a_n-1

寫成遞迴就OK了，也可以寫成公式

a_n = n² - n + 2, if n > 0

程式碼如下：

/* a042. 平面圓形切割  
*
* 2020/3/3
*/

import java.util.Scanner;

public class Pa042{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            System.out.println(circleCut(scanner.nextInt())); 
        }
    }

    public static int circleCut(int n){
        return n == 1? 2: 2 * (n - 1) + circleCut(n - 1);
    }

}

2020年3月2日星期一

[zerojudge]a040. 阿姆斯壯數

a040. 阿姆斯壯數

阿姆斯壯數有好多名字，我聽過的是水仙花數。
其特徵就是長度n位的數，各位數的n次方總和等於自身，例如115 = 1^3 + 1^3 + 5^3

解題想法：
寫一個方法(method)來判斷一數是否為水仙花數，是回傳true，不是就回傳false。
方法內容是先將整數換成字串再換成字元陣列方便對各位數計算，for迴圈之中使用之前用過得Character.getNumericValue。

程式碼如下：

/* a040. 阿姆斯壯數  
*
* 2020/3/2
*/

import java.util.Scanner;

public class Pa040{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int m = scanner.nextInt();

            boolean none = true;

            for(; n <= m; n++){
                if(isNarcissistic(n)){
                    System.out.print(n + " ");
                    none = false;
                }
            }

            System.out.println(none? "none": "");
        }
    }

    public static boolean isNarcissistic(int num){
        char[] nums = Integer.toString(num).toCharArray();

        int sum = 0;

        for(char ch: nums){
            sum += (int)Math.pow(Character.getNumericValue(ch), nums.length);
        }

        return num == sum;
    }
}

[zerojudge]a038. 數字翻轉

a038. 數字翻轉

1234 → 4321，1000 → 0001 → 1，000 → 0。
之前迴文用過的StringBuffer加上Integer.parseInt()就完成了。

程式碼如下：

/* a038. 數字翻轉
*
* 2020/3/2
*/

import java.util.Scanner;

public class Pa038{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            StringBuffer sb = new StringBuffer(scanner.next());

            System.out.println(Integer.parseInt(sb.reverse().toString())); 
        }
    }
}

2020年3月1日星期日

[zerojudge]a034. 二進位制轉換

a034. 二進位制轉換

日常生活中使用的是十進位，遇到十就進位，那二進位就是遇到二就進位。十進位轉二進位可以參考：【CodingBar】什麼是二進位？｜程人式界科普 #01

方法一—直接toBinaryString，超簡單暴力。
方法二—樸實除除樂，如上圖去取除二之後的餘數，然後把順序倒過來輸出。

方法一：

/* a034. 二進位制轉換
*
* 2020/3/2
*/

import java.util.Scanner;

public class Pa034{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            System.out.println(Integer.toBinaryString(scanner.nextInt()));
        }
    }
}

方法二：

/* a034. 二進位制轉換
*
* 2020/3/2
*/

import java.util.Scanner;

public class Pa034_2{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            int decNum = scanner.nextInt();

            boolean[] binNum = new boolean[(int)(Math.log(decNum) / Math.log(2)) + 1];

            for(int i = binNum.length - 1; i >= 0; i--){
                binNum[i] = decNum % 2 == 0? false: true; 
                decNum /= 2;
            } 

            for(int i = 0; i < binNum.length; i++){
                System.out.print(binNum[i]? 1: 0);
            }

            System.out.println();
        }
    }
}

[zerojudge]a024. 最大公因數(GCD)

a024. 最大公因數(GCD)

我作弊，用BigInteger.gcd()，缺點是比較慢。
另一個方法是輾轉相除法，非常經典的遞迴，可以看看這個影片：歐幾里得演算法(輾轉相除法)

        輾轉相除法：
        public static int gcd(int a, int b){
            return b == 0 ? a: gcd(b, a % b);
        }

程式碼如下：

/* a024. 最大公因數(GCD) 
*
* 2020/3/2
*/

import java.util.Scanner;
import java.math.BigInteger;

public class Pa024{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            BigInteger big_a = new BigInteger(scanner.next());
            BigInteger big_b = new BigInteger(scanner.next());
                
            System.out.println(big_a.gcd(big_b));
        }
    }
}

[zerojudge]a022. 迴文

a022. 迴文

正向和反向讀起來一樣就是迴文，例如說：上海自來水來自海上，用迴圈不就好了嗎？不好意思我太懶了，馬上查查有沒有把String倒過來的方法，發現用StringBuffer（和String很像的類別）可以做到，兩行解決！

        迴圈解：
        boolean isPalindrome = true;

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                isPalindrome = false;
            }
        }

        print(isPalindrome? "yes": "no");

程式碼如下：

/* a022. 迴文
*
* 2020/3/2
*/

import java.util.Scanner;

public class Pa022{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            StringBuffer sb = new StringBuffer(scanner.next());

            System.out.println(sb.toString().equals(sb.reverse().toString())? "yes": "no");
        }
    } 
}

[zerojudge]a021. 大數運算

a021. 大數運算

理論上大數運算是很驚悚的問題，因為就算是long long int也不夠儲存，所以要把每個位數存進陣列然後透過超複雜的演算法才能得到答案。幸好Java有幫我們寫好了函式庫可用，那就是BigInteger這個神奇類別，提供很多大數的計算方法，輕輕鬆鬆解決這個地獄難題。

如果對大數運算的實作有興趣的話可以看這個演算法筆記，裡面詳盡介紹了如何用優雅至極的語法完成大數運算。

程式碼如下：

/* a021. 大數運算
*
*  2020/3/2
*/

import java.util.Scanner;
import java.math.BigInteger;

public class Pa021{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            BigInteger big_a = new BigInteger(scanner.next());
            String op = scanner.next();
            BigInteger big_b = new BigInteger(scanner.next());
                
            switch(op){
                case "+":
                    big_a = big_a.add(big_b);
                    break;
                case "-":
                    big_a = big_a.add(big_b.negate());
                    break;
                case "*":
                    big_a = big_a.multiply(big_b);
                    break;
                case "/":
                    big_a = big_a.divide(big_b);
                    break;
            }

            System.out.println(big_a);
        }
    }
}

[zerojudge]a020. 身分證檢驗

a020. 身分證檢驗

請先閱讀：身分證驗證規則

英文代號看似連續，結果參雜一些例外，只好依照英文字母的順序打成字串陣列:( 然後用整數陣列儲存每個編號要乘上的值。
值得提的點應該是Character.getNumericValue()，可以把字元換算成unicode的編碼。

題外話：A123456789是真有其人，被別人盜用的頻率超高，三天兩頭就要跑一次法院，但是這位勇者不換號碼，因為很麻煩。

程式碼如下：

/* a020. 身份證檢驗
*
*
* 2020/3/1
*/

import java.util.Scanner;

public class Pa020{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        String[] idNum = {"10", "11", "12", "13", "14", "15", "16", "17", "34",
                    "18", "19", "20", "21", "22", "35", "23", "24", "25",
            "26", "27", "28", "29", "32", "30", "31", "33"};  

        int[] num = {1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1};

        while(scanner.hasNext()){
            String input = scanner.nextLine();
            
            input = idNum[Character.getNumericValue(input.charAt(0)) - Character.getNumericValue('A')] + input.substring(1);

            int sum = 0;

            for(int i = 0; i < input.length(); i++){
                sum += num[i] * Character.getNumericValue(input.charAt(i));
            }

            System.out.println(sum % 10 == 0 ? "real": "fake");
        }
    }
}

[zerojudge]a017. 五則運算

a017. 五則運算

先乘除後加減、括號優先程式是怎麼寫的？！不知道你小時後有沒有想過這種問題，至少我是沒有啦:D

做這題要先了解堆疊，對堆疊(Stack)這種資料結構不熟的話可以看看【Ken將】電腦課小教室 - Class.Null - 堆疊與佇列，再來了解運算式的前序、中序、後序表示法資料結構教學 : Infix 轉 Postfix

手稿

程式碼如下：

/*a017. 五則運算
*
* 2020/2/28
*/
import java.util.Scanner;
import java.util.Stack;

public class Pa017{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){
            System.out.println(evaluate(scanner.nextLine())); 
        }
    }

    public static int evaluate(String s){
        String[] exp = s.split(" ");

        Stack ops = new Stack();
        Stack vals = new Stack();

        for(String token: exp){
            if("(".equals(token)){ 
                ops.push(token);
            }else if(")".equals(token)){ 

                // 不斷計算直到遇到右括號
                while(!"(".equals(ops.peek())){
                    vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
                }

                // 把遇到的右括號pop掉
                ops.pop();

            }else if("+-*/%".contains(token)){

                // 如果ops還有運算子 且 ops最頂層運算子的優先順序 >= token運算子的優先順序
                while(!ops.isEmpty() && priority(ops.peek()) >= priority(token)){
                    vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
                }

                ops.push(token);
            }else{
                vals.push(Integer.parseInt(token));
            }
        } 

        while(!ops.isEmpty()){
            vals.push(calc(vals.pop(), ops.pop(), vals.pop()));
        }

        return vals.pop();
    } 

    public static int priority(String op){
        return "*/%".contains(op) ? 2 : "+-".contains(op) ? 1 : 0;
    }

    // ab位置對調
    public static int calc(int b, String operator, int a){
        switch(operator){
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            case "%": return a % b;
            default:
                    System.out.println("unknown operator");
                    return 0;
        }
    }

}

2020年3月8日 星期日

2020年3月7日 星期六

2020年3月6日 星期五

2020年3月5日 星期四

2020年3月4日 星期三

2020年3月2日 星期一

2020年3月1日 星期日

2020年3月8日星期日

2020年3月7日星期六

2020年3月6日星期五

2020年3月5日星期四

2020年3月4日星期三

2020年3月2日星期一

2020年3月1日星期日