[Easy] 299. Bulls and Cows

傳入純數字的密碼字串與猜測字串，位置與數字相同是A，位置不同但數字相同則是B。

Discuss 1ms寫法

    public String getHint(String secret, String guess) {
        int a = 0;
        int b = 0;
        int[] m1 = new int[10];
        int[] m2 = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) 
                a++;
            else {
                m1[secret.charAt(i) - '0']++;
                m2[guess.charAt(i) - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) 
            b += Math.min(m1[i], m2[i]);
        
        return a + "A" + b + "B";        
    }

自己 2ms寫法

    public String getHint(String secret, String guess) {
        int acount = 0,bcount = 0;
        int gca[] = new int[10];
        StringBuilder sb = new StringBuilder(secret);
        for(int i=0;i<secret.length();i++){
            char sc = secret.charAt(i);
            char gc = guess.charAt(i);
            if(sc==gc){
                acount++;
                sb.replace(i,i+1,"a");
            }
            else
                gca[gc-'0']++;
        }
        for(int i=0;i<sb.length();i++){
            char c = sb.charAt(i);            
            if(c>='0'&&c<='9'&&gca[c-'0']-->0)
                bcount++;            
        }
        
        return acount+"A"+bcount+"B";        
        
    }

二分搜尋法 Binary Search

基本概念:

1. 從排序後的陣列中搜尋特定元素
2. 搜尋過程由中間的元素位置開始，將要找的元素值與中間值比較
3. 假設中間值比較大則要找的元素在左半邊，start位置固定，end位置為中間位置-1
4. 假設中間值比較小則代表要找的元素在右半邊，end位置固定，start位置為中間位置+1
5. 若中間值與要找的元素值相等，則直接返回中間值位置
6. 假設搜尋過程做到start>end 還未返回要找的元素位置，則代表陣列中此元素並不存在，返回-1
7.  start>end  = 要找的元素值過大 ; end<start = 要找的元素值過小

最佳時間複雜度:  O(1)
最壞時間複雜度:  O(logn)

while寫法

    public static int bs1(int[] sortedArr,int findNum){
        int start = 0;
        int end = sortedArr.length-1;
        while(start<=end){
            int mid = (start+end)/2;
            //int mid = start + (end-start)/2; //防止int溢位
            if(findNum>sortedArr[mid])
                start = mid+1;
            else if(findNum<sortedArr[mid])
                end = mid-1;
            else
                return mid;
        }
        
        return -1;
    }

遞迴寫法

    public static int bs2(int[] sortedArr,int findNum,int start,int end){        
        if(start>end)
            return -1;
        int mid = (start+end)/2;        
        if(findNum>sortedArr[mid])
            return bs2(sortedArr,findNum,mid+1,end);
        else if(findNum<sortedArr[mid])
            return bs2(sortedArr,findNum,start,mid-1);
        else
            return mid;
    }

呼叫函式

    int sortedArr[] = {1,2,44,55,66,77,88,99};

    System.out.println(bs1(sortedArr,1));
    System.out.println(bs2(sortedArr,77,0,sortedArr.length-1));
    System.out.println(Arrays.binarySearch(sortedArr,99));

二進位與十進位互轉

自行實作 :

1. decimalToBinary : 將數字除2求餘數與商，新增一個字串將每次的餘數串到最前面，商則覆蓋原本數字直到為0，跳出迴圈，返回二進位數字字串。
2. binaryToDecimal : 將二進位字串從第一個字元到最後一個依序個別乘上2的(字串長度-1)次方直到0次方，並相加，返回相加之後的十進位數字。

    public static String decimalToBinary(int n){
        String str = ""; 
        while(n!=0){ 
            str = n%2+str;
            n = n/2; 
        }
        return str;
    }

    public static int binaryToDecimal(String binStr){
         int sum = 0; 
         int len = binStr.length(); 
         for (int i=1;i<=len;i++){
            int dt = Integer.parseInt(binStr.substring(i-1,i));
            sum+=(int)Math.pow(2,len-i)*dt; 
         } 
         
         return sum; 
    }

使用函式 :

    String bsapi = Integer.toBinaryString(num);
    int diapi = Integer.parseInt(bsapi,2);

[Easy] 806. Number of Lines To Write String

widths為寫入a~z字母個別所需的寬度，每行的上限是100，超過就寫下一行，答案返回寫入S所需的行數和最後一行的寬度。

    public int[] numberOfLines(int[] widths, String S) {
        char ca[] = S.toCharArray();
        int wtmp = 0,ltmp = 1;
        for(char c:ca){
            int ctmp = widths[c-'a'];           
            if(wtmp+ctmp>100){
                ltmp++;
                wtmp=0;
            }
            wtmp+=ctmp;            
        }
        
        int ans[] = {ltmp,wtmp};
        return ans;
    }

[Easy] 1. Two Sum

雙for loop寫法

    public int[] twoSum(int[] nums, int target) {
        int ans[] = new int[2];
        for(int i=0;i<nums.length;i++){
            int tmp = target-nums[i];
            for(int j=0;j<nums.length;j++){
                if(j!=i&&nums[j]==tmp){
                    ans[0]=i;
                    ans[1]=j;
                    break;
                }
            }    
        }
        
        return ans;
    }

Map寫法

    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap();
        int ans[] = new int[2];
        for(int i=0;i<nums.length;i++){
            int diff = target-nums[i];            
            if(map.containsKey(diff)){               
                ans[0] = map.get(diff);
                ans[1] = i;
                break;
            }else{
                map.put(nums[i],i);
            }
        }
       
        return ans;
    }

氣泡排序法 Bubble Sort

基本概念:

1. 兩相鄰的元素互相比較(看要做升冪或是降冪)，將元素互換位置，每做完一輪，最後的元素會是最大或最小
2. 下一輪的比較重複以上步驟，除了最後一個元素已經完成排序，不需要再做
3. 持續對越來越少的元素重複步驟，直到沒有任何元素需要比較
4. 可建立一個flag來記錄每一輪的比較是否有執行互換，如果下一輪偵測到上一輪沒有互換則直接完成排序，最優情況時間複雜度可降低到O(n)

最佳時間複雜度: O(n)
最壞時間複雜度: O(n^2)

   static void sort1(int arr[]){
        for(int i=arr.length-1;i>0;i--){
            boolean flag = false;
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flag = true;
                }
            }
            if(!flag) break;
        }
    }

   static void sort2(int arr[]){
        boolean flag;
        int j = arr.length-1;
        do{            
            flag = false;
            for(int i=0;i<j;i++){
                if(arr[i]>arr[i+1]){
                    int tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    flag = true;
                }
            }
            j--;
        }while(flag);
    }