[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

---

結論 :

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

java 透過 jni 呼叫 C

1. 首先建個資料夾，裡面新增一個java檔案

class helloworld {
    private native void print();
    public static void main(String[] args) {
        new helloworld().print();
    }
    static {
        System.loadLibrary("helloworld");
    }
}

2. 打開cmd，利用javah產生header檔

 // 因為我的jdk是10，把javah拿掉了 所以這樣使用 ，10以前 javah -jni xxxx
 javac -h . helloworld.java

3. 產生header檔之後，打開來看，會發現有一段 JNIEXPORT void JNICALL Java_helloworld_print
(JNIEnv *, jobject); 這個就是要寫在C++裡面的方法，供java呼叫

新增 helloworld.cpp

#include 
#include 
#include "helloworld.h"

JNIEXPORT void JNICALL
Java_helloworld_print(JNIEnv *env, jobject obj)
{
    printf("哈囉哈囉世界!\n");
    return;
}

4. 下載mingw64 (連結)

載完安裝後，打開cmd，輸入 gcc 看有沒有指令，沒有的話要自己新增環境變數
gcc路徑 : C:\Program Files\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin (不一樣的話要改)

5. 打開cmd 輸入指令 ，輸出dll檔

gcc -I "C:\Program Files\Java\jdk-10.0.2\include" -I "C:\Program Files\Java\jdk-10.0.2\include\win32" -shared -o helloworld.dll helloworld.cpp

6. class檔和dll檔放在同一個目錄下， cmd輸入 java helloworld 即可成功從java呼叫使用c方法

---

使用gcc編譯C語言

Source Code : https://github.com/tks3589/BloggerCode/tree/master/java/jjj

在Android上使用opencv

網路上有許多方式，這邊紀錄我認為比較簡單的一種，基本上就是在專案內建立模組，匯入opencv，設定完lib就能用了

IDE : Android Studio 3.3 (以下簡稱AS)
opencv android sdk : 3.3.0 (官方連結)




1. 下載下來解壓縮

2. 在AS內 : File -> New -> New Module -> 拉到下面選擇 Import Eclipse ADT Project -> Next

3. Source directory的地方填入剛剛解壓縮完的 (....\OpenCV-android-sdk\sdk\java) ， 下面的Module name會自動填入 -> Next -> Finish

4. 這裡遇到的錯誤點擊 Affected Modules: openCVLibrary330 -> 註解掉 "uses-sdk android:minsdkversion="8" android:targetsdkversion="21" -> Try Again

5. 在src/main下面新增一個叫 jniLibs 的資料夾

6. 將opencv android sdk (....\OpenCV-android-sdk\sdk\native\libs\)這個路徑裡面的 armeabi-v7a(一般手機)、x86_64(模擬器) 放進jniLibs裡面

7. 將opencvlibrary330裡的build.gradle和app的build.gradle ，compileSdkVersion , minSdkVersion，targetSdkVersion要相同

8. 這樣opencv就載入了，再來就是用函式庫寫個demo

ex. 放個按鈕，按一下轉灰階，再按一下變原圖

layout只是個ImageView + Button 這裡就不放上來了

主要程式碼如下 :

 
   public class MainActivity extends AppCompatActivity implements View.OnClickListener{
     Button button;
     ImageView imageView;
     Bitmap srcBitmap,grayBitmap;
     boolean flag = false;

    static {
        System.loadLibrary("opencv_java3");
    }

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        button = findViewById(R.id.button);
        imageView = findViewById(R.id.imageView);
        button.setOnClickListener(this);
        proc();
    }

    @Override
    public void onClick(View v) {
        if(v == button){
            if(!flag) {
                imageView.setImageBitmap(grayBitmap);
                flag = true;
                button.setText("GRAY");
            }else{
                imageView.setImageBitmap(srcBitmap);
                flag = false;
                button.setText("RAW");
            }
        }
    }

    public void proc(){
        Mat rgbMat = new Mat();
        Mat grayMat = new Mat();
        srcBitmap = BitmapFactory.decodeResource(getResources(),R.drawable.photo);
        grayBitmap = Bitmap.createBitmap(srcBitmap.getWidth(),srcBitmap.getHeight(),Bitmap.Config.RGB_565);
        Utils.bitmapToMat(srcBitmap,rgbMat);
        Imgproc.cvtColor(rgbMat,grayMat,Imgproc.COLOR_RGB2GRAY);
        Utils.matToBitmap(grayMat,grayBitmap);
    }

}

 
   
  // 這一段主要是抓取jniLibs裡的lib (libopencv_java3.so) ，所以跑的機器如果沒有相對應的版本就會拋錯
   
    static { 
        System.loadLibrary("opencv_java3");
    }

 

//呼叫opencv函式庫，如果第一次使用，需要在紅線的地方 Alt + Enter IDE會自動載入opencv (在build.gradle -> dependencies會發現implementation project(path: ':openCVLibrary330') ，載入後再 Alt + Enter一次import function即可

    public void proc(){
        Mat rgbMat = new Mat();
        Mat grayMat = new Mat();
        srcBitmap = BitmapFactory.decodeResource(getResources(),R.drawable.photo);
        grayBitmap = Bitmap.createBitmap(srcBitmap.getWidth(),srcBitmap.getHeight(),Bitmap.Config.RGB_565);
        Utils.bitmapToMat(srcBitmap,rgbMat);
        Imgproc.cvtColor(rgbMat,grayMat,Imgproc.COLOR_RGB2GRAY);
        Utils.matToBitmap(grayMat,grayBitmap);
    }

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

strings xml 中圖片資源使用方式

在xml中寫陣列，取出的方式

字串 :

圖片資源ID(int) :

取出方式 :