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 res=new ArrayList<>();

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

4，堆数据结构

PriorityQueue q=new PriorityQueue<>(new Comparator(

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 
 
14，N皇后问题-回朔法
 
 
NxN的期盼，放置n个皇后，要求行列对角线不能重复。
 
 
思路一：一行一行进行试探，每次试探一步进行标记，然后求出所有的可能。
思路二：用arr[n]记录每次放皇后的列行，arr[i]表示第i行的皇后位置放在arr[i]位置上面，满足列不相等的情况只要arr[i]!=arr[j](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  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set 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(lk) r=p-1;
        else l=p+1;
}
}