[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);
    }

Android 透過 jni 呼叫C

稍微說個為何要在安卓使用C語言開發東西，大學專題有用到手機寫影像辨識，利用camera2 api擷取到影像，直接用android sdk的bitmap + get/set pixel 硬幹，後果當然是慘不忍睹，效能說能多慢就有多慢，好像一張640*480的影像轉成灰階就要幾分鐘，而那時候採取的臨時解決方案是用get/set pixels ，這個也是sdk提供的原始方法之一，是利用陣列先做完運算再一次處理，減少了反覆呼叫方法的次數，結果速度有了很大的提升，就一直用這個方法到畢業展了，但我知道如果做影像處理，遲早還是要和底層打交道，而唸研究所的時間，打算來面對。

日前在github上有看到一個照片濾鏡的專案，核心照片濾鏡處理是一個library，透過JNI call底層C語言來加速，我覺得很重要，所以這篇分成兩個方式實作Android呼叫jni (javah、CMake)來測試看看

濾鏡專案 : https://github.com/Zomato/AndroidPhotoFilters

---

第一種 : 利用javah、ndkbuild

1. AS裡面 -> SDK Manager -> SDK Tools -> 先把CMake、NDK 裝起來，沒問題的話IDE會自動設置套件路徑

2. AS裡面 -> File -> Settings -> Tools -> External Tools



3. 上面 +號 新增Tools (這個動作主要是把指令和參數寫成工具，以後要使用可以直接套用)

4. 新增 javah

參數 :

C:\Program Files\Java\jdk1.8.0_201\bin\javah.exe (這裡要對應自己jdk的路徑 需要注意的是用jdk10以下的，以上的沒有javah)

-v -jni -d $ModuleFileDir$/src/main/jni $FileClass$

$SourcepathEntry$




5. 新增 ndkbuild

參數 :

D:\Android\Sdk\ndk-bundle\ndk-build.cmd (這裡要對應自己ndk的路徑)

NDK_PROJECT_PATH=$ModuleFileDir$/build/intermediates/ndk NDK_LIBS_OUT=$ModuleFileDir$/src/main/jniLibs
NDK_APPLICATION_MK=$ModuleFileDir$/src/main/jni/Application.mk APP_BUILD_SCRIPT=$ModuleFileDir$/src/main/jni/Android.mk V=1

$ProjectFileDir$



6. 在Main方法下新增一個java類別 myNDK ， 裡面寫兩個對應c語言要呼叫的function

public class myNDK {
    static {
        System.loadLibrary("myJNI");
    }
    public native  String getMycstring();
    public native int getJniAdd(int a, int b);
}

7. 切成Project模式 -> 在src/main下面新增 jni 資料夾

8. 設定app的build.gradle (這裡的modeulName 要和在 myNDK loadLibrary寫的一樣，jniLibs是之後ndkbuild放置so檔的地方)

9. 對剛剛新增的myNDK按右鍵 -> External Tools -> javah ，就會發現指令會自動執行，jni目錄下會產生header檔
裡面分別有兩個對應myNDK的function

10. 接著就是在jni目錄下，新增c++檔案 ，檔名必須和myNDK裡面loadLibrary那個名字一樣，所以取作myJNI.cpp

*注意，這裡的function要根據header的方法參數寫，不然會找不到拋錯

#include "com_aaron_jnitester3_myNDK.h"

JNIEXPORT jstring JNICALL Java_com_aaron_jnitester3_myNDK_getMycstring
        (JNIEnv *env, jobject){
    return (*env).NewStringUTF("MY !!  NDKString!!");
}

JNIEXPORT jint JNICALL Java_com_aaron_jnitester3_myNDK_getJniAdd
        (JNIEnv *env, jobject object, jint a, jint b) {
    return a + b;
}

11. 接著就是在jni目錄下新增File Android.mk 和 Application.mk

Android.mk

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE := myJNI
LOCAL_SRC_FILES := myJNI.cpp

include $(BUILD_SHARED_LIBRARY)

Application.mk

APP_ABI := all

12. 對jni目錄按右鍵 -> External Tools -> ndkBuild ， 會發現指令自動執行，並且新增一個叫jniLibs的資料夾，裡面放置手機版本的so檔


13. 撰寫demo程式

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        TextView textView = findViewById(R.id.textView);

        myNDK myndk = new myNDK();
        textView.setText(myndk.getMycstring() + myndk.getJniAdd(8,7));  //呼叫NDK方法
  
    }
}

DEMO :

Source Code : https://github.com/tks3589/BloggerCode/tree/master/android/jniTester3

---

第二種 : 利用CMake，直接建立預設支援C++專案

1. 直接 File -> New -> New Project -> Native C++

2. 裡面的檔案結構長這樣，基本上要寫自己的function，只要在Main裡面直接加，Alt + Enter 就會自動幫你在cpp檔裡面補方法了

DEMO:

CMakeLists.txt裡面應該是更改library的參數，沒用過先記錄

build出來的模擬器apk有 so檔案

Source Code : https://github.com/tks3589/BloggerCode/tree/master/android/jniTester4

---

結論 :

第二種方法明顯快速許多，但陽春點的做法能更理解原理也是好事 ，還不是很熟悉，有問題的地方還請大家多多提出，謝謝。