Java刷力扣技巧總結-思想與技巧

Java刷題技巧

Java輸入輸出問題

Scanner sc=new Scanner(System.in);
           

輸入一行字元串:sc.nextLine()

輸入一個基本類型：sc.nextInt、nextLong、nextDouble

輸入一個字元：scanner.next().charAt(0);

輸出

System.out.printf("%d",value);

力扣刷題常見的特殊情況

1，常見的&操作便捷的含義

n&(-n)表示去lowbits，取二進制最低位，樹形數組中應用。

n&(n-1)表示将二進制最低位進行取反。

2，常見的list轉換成[]int、[]String方法

list-->[]int:list.stream().mapToInt(Integer::valueOf).toArray();

list-->[]String:list.toArray(new String[0]);

3，list轉換成[][]int方法

ArrayList<int []> res=new ArrayList<>();

res.toArray(new int [0][]);

4，堆資料結構

PriorityQueue<Integer> q=new PriorityQueue<>(new Comparator<Integer>(

int compare(Integer o1,Integer o2) {return 0;}

));

5.Java中Long轉換成int

（int）Long，可能出現溢出，且java不支援。

Long.intValue(),Long對象中包含此轉換方法。

Integer.parseInt(String.valueOf(long)),先轉成字元串，在轉成int。

6、快速幂

思想：

88 * 0110 0011(2) = 88 * 0 * 2^7 
                  + 88 * 1 * 2^6 
                  + 88 * 1 * 2^5 
                  + 88 * 0 * 2^4 
                  + 88 * 0 * 2^3 
                  + 88 * 0 * 2^2 
                  + 88 * 1 * 2^1
                  + 88 * 1 * 2^0
代碼：

int quickMulti(int A, int B) {
    int ans = 0;
    for ( ; B; B >>= 1) {
        if (B & 1) {
            ans += A;
        }
        A <<= 1;
    }
    return ans;
           

7、摩爾投票法

應用：找出數組中出現次數超過一半的數

具體步驟：相同的數，則保留記錄，不同的數則删除，，直到末尾。

8、樹狀數組

應用：求逆序數

class BIT{
    int []tree;
    int n;
    public BIT(int n){
         tree=new int[n+1];
         this.n=n;
    }
    public int lowbit(int n){
        return (n)&(-n);
    }
    public int query(int index){
        int res=0;
        while(index!=0){
            res+=tree[index];
            index-=lowbit(index);
        }
        return res;
    }
    public void add(int index){
        while(index<=n){
            tree[index]++;
            index-=tree[index];
        }
    }
}
           

9、質數的判斷方法

1，常見方法，直接通過周遊到n的開平法進行整除判斷，效率不高。

2，通過标志方法，設定一個bool數組，先進行初始化，奇數設定為true，偶數設定為false，隻需将前面為true表示為質數的倍數設定為flase即可，效率較上面高。

3，質數分布的規律：大于等于5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等；

bool isPrime( int num )
{
    //兩個較小數另外處理
    if(num == 2||num == 3 )
        return 1;
    //不在6的倍數兩側的一定不是質數
    if(num % 6 != 1&&num % 6 != 5)
        return 0;
    int tmp = sqrt(num);
    //在6的倍數兩側的也可能不是質數
    for(int i = 5;i <= tmp;i += 6)
        if(num %i == 0||num % (i+ 2) == 0)
            return 0;
    //排除所有，剩餘的是質數
    return 1;
           

10、博弈-NIm遊戲

n個石子，兩個人取，每次可以取1-m個石子，誰取到最後一個石子就赢得比賽，取的局面為（m+1）的時候必輸，且為（m+1）的倍數時候也必輸。

11，new Comparator<>(){}

int compare(Integer o1,Integer o2)方法中的簡單寫法為：return o1-o2;

一般最簡單寫法：

• Collections.sort(arr,(o1,o2)->o1.val-o2.val);// 升序
• Collection.sort(arr,(o1,o2)->{return o1.val-o2.val;}
• new Comparator<>(){}中的int compare(Integer o1,Integer o2)
• Arrays.sort(T[],new Comparator<>(){});

12，Arrays.copyOf（arr[],len）和System.arraycopy(src, srcPos, dest, destPos, length)

前者一般是數組的擴容，産生一個新的對象，後者是數組的複制，會對源數組進行指派，不會産生新的數組。

13，快速排序

思想：随機取一個值作為基準（一般去做下标），對數組的值分為大于和小于基準兩部分，然後采用遞歸的方式全部使得數組有序。

public static void quickSort(int []nums,int l,int r){
        if(l<r){
            int index=partition(nums,l,r);
            //分治遞歸
            quickSort(nums,l,index-1);
            quickSort(nums,index+1,r);
        }
    }
    // partition就是讓按照基準劃分兩部分
    public static int partition(int []nums,int l,int r){
        int flag=l;//辨別
        int index=l+1;//辨別右部分的初始位置
        for(int i=index;i<=r;i++){
            if(nums[i]<nums[flag]){
                // 交換
                swap(nums,i,index);
                index++;
            }
        }
        //将flag和前半部分最後一個進行交換
        swap(nums,index-1,flag);
        // index-1是辨別的下标
        return index-1;
    }
    public static  void swap(int [] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
           

14，N皇後問題-回朔法

NxN的期盼，放置n個皇後，要求行列對角線不能重複。

1. 思路一：一行一行進行試探，每次試探一步進行标記，然後求出所有的可能。
2. 思路二：用arr[n]記錄每次放皇後的列行，arr[i]表示第i行的皇後位置放在arr[i]位置上面，滿足列不相等的情況隻要arr[i]!=arr[j](j<i),對角線不相等的情況是i+arr[i]!=j+arr[j],進行遞歸即可。

class Main {
    static int resultCount = 0;

    private static boolean place(int[] arr, int s) {
        for(int i = 0; i < s; i++) {
            if((arr[i] == arr[s]) || (Math.abs(i-s) == Math.abs(arr[i]-arr[s]))) {
                return false;
            }
        }

        return true;
    }

    public static void tria(int[] arr, int i, int n) {
        if(i >= n) {
            // 列印出來
            for(int j=0;j<8;j++){
                for(int k=0;k<8;k++){
                    if(arr[j]==k){
                        System.out.print("*");
                    }else{
                        System.out.print(".");
                    }
                }
                System.out.println();

            }
            System.out.println("------------------------");
            ++resultCount;
        } else {
            for(int j = 0; j < n; j++) {
                arr[i] = j;
                if(place(arr, i)) {
                    tria(arr, i+1, n);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] queen = new int[8];
        tria(queen, 0, 8);

        System.out.println(resultCount);
    }
}
           

15，Collections常用的工具方法

排序操作

void reverse(List list)//反轉
void shuffle(List list)//随機排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序邏輯
void swap(List list, int i , int j)//交換兩個索引位置的元素
void rotate(List list, int distance)//旋轉。當distance為正數時，将list後distance個元素整體移到前面。當distance為負數時，将 list的前distance個元素整體移到後面
           

 查找替換

int binarySearch(List list, Object key)//對List進行二分查找，傳回索引，注意List必須是有序的
int max(Collection coll)//根據元素的自然順序，傳回最大的元素。 類比int min(Collection coll)
int max(Collection coll, Comparator c)//根據定制排序，傳回最大元素，排序規則由Comparatator類控制。類比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//統計元素出現次數
int indexOfSubList(List list, List target)//統計target在list中第一次出現的索引，找不到則傳回-1，類比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替換舊元素
           

 安全（Collections可以将不安全的容易變為安全的）

synchronizedCollection(Collection<T>  c) //傳回指定 collection 支援的同步（線程安全的）collection。
synchronizedList(List<T> list)//傳回指定清單支援的同步（線程安全的）List。
synchronizedMap(Map<K,V> m) //傳回由指定映射支援的同步（線程安全的）Map。
synchronizedSet(Set<T> s) //傳回指定 set 支援的同步（線程安全的）set。
           

 16，Arrays.asList(new int[]{}

數組轉換成集合，直接轉換成的是Array&ArrayList,并不是真正的ArrayList，在在一個new ArrayList<>(Arrays.asList(new int[]{}));

17，LinkedHashMap

應用：LRU

構造方法：public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

accessOrder=false表示插入順序，true表示通路順序，且HashMap并不能保持插入順序，LinkedHashMap的子類從寫removeEldestEntry（）方法可以實作LRU固定緩沖區大小置換的功能。

18，拓撲排序

多任務存在先後，找出合法的任務執行序列，應用（課程表中的先修問題-解決存在環的問題）

思想：可以将入度為0的結點加入隊列，然後進行出隊為key，将其餘入度為key的結點入度數減一，并将入度為0的加入隊列，總的出隊數等于總的結點數的話則表明存在拓撲排序。

19，數組中第k大的數-面試題

排序+找下标

小根堆，将數組一步一步加入根堆，節點數量超出k範圍則剔除，直到末尾。

快速标記法-基于快速排序實，partition不變，增加quickSelect方法

quickSelect(int l,int r,int k,int []nums){
    if(l>r)return;
    while(l<r){
        int p=partition(l,r,nums);
        if(p==k)return nums[p];
        else if(p>k) r=p-1;
        else l=p+1;
}
}