　　这个是LeetCode上面的编程训练专项页面，地址：https://leetcode-cn.com/explore/interview/card/top-interview-quesitons-in-2018/262/summery/

　　总体，比较系统、全面。在解决这些问题的时候，我都是先尝试使用自己的方法coding一遍，之后在看看其他比较巧妙的解决方法学习一下。

需要特殊技巧解决的难题：①切割回文；②

0，热身编程题

　　0.1只出现一次的数字【算法简单、但是想要达到优雅就需要动一动脑子】

　　给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

package com.cnblogs.mufasa.QA1_makeAhotDOU;

import org.junit.Test;

import java.util.Arrays;

public class Solution1 {

    //速度也还行，时间复杂度大致为O（nlogn+n/2）,相对性能要差一些

    public static int singleNumber1(int[] nums) {

        Arrays.sort(nums);

        int len=nums.length-1;

        for(int i=0;i<len;i+=2){

            if(nums[i]!=nums[i+1]){

                return nums[i];

            }

        }

        return nums[len];

    }

    //***最优化的解法***，时间复杂度为O（n）

    public static int singleNumber(int[] nums) {

        int temp=nums[0];

        for(int i=1;i<nums.length;i++){

            temp^=nums[i];

        }

        return temp;

    }

    @Test

    public void test() {

//        int[] nums=new int[]{1,1,2,2,6,7,7,6};

        int[] nums=new int[]{4,1,2,1,2};

        System.out.println(singleNumber(nums));

        System.out.println(singleNumber1(nums));

    }

}

　　0.2求众数【简单，奇技淫巧】

　　给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

　　你可以假设数组是非空的，并且给定的数组总是存在众数。

package com.cnblogs.mufasa.QA1_makeAhotDOU;

import org.junit.Test;

import java.util.Arrays;

import java.util.Map;

import java.util.TreeMap;

public class Solution2 {

    //最完美的解决方法,时间复杂度可以降低到O(NlogN)

    public int majorityElement1(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length/2];

    }

    //利用TreeMap来进行排序，更新出现频率大小

    public int majorityElement(int[] nums) {

        TreeMap<Integer,Integer> treeMap=new TreeMap<>();

        for(int i=0;i<nums.length;i++){

            if(treeMap.get(nums[i])!=null){

                treeMap.put(nums[i],treeMap.get(nums[i])+1);

            }else {

                treeMap.put(nums[i],1);

            }

        }

        int loc=-1,max=0;

        for(Map.Entry<Integer,Integer> kv:treeMap.entrySet()){

            if(kv.getValue()>max){

                loc=kv.getKey();

                max=kv.getValue();

                if(max>nums.length/2){

                    break;

                }

            }

        }

        return loc;

    }

    @Test

    public void test() {

        int[] nums=new int[]{2,2,1,1,1,2,2};

        System.out.println(majorityElement1(nums));

        System.out.println(majorityElement(nums));

    }

}

　　0.3搜索二维矩阵 II【题目中给出的条件一般情况下都会自己的意义，例如：有序】

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

package com.cnblogs.mufasa.QA1_makeAhotDOU;

import org.junit.Test;

public class Solution3 {

    //1，暴力破解法【遍历所有位置】由于题目已经给出这个matrix是有序的，所以暴力法明显就浪费了这种已知条件

    public boolean searchMatrix1(int[][] matrix, int target) {

        if(matrix==null||matrix.length==0||matrix[0].length==0){

            return false;

        }

        int xLen=matrix.length,yLen=matrix[0].length;

        for(int i=0;i<xLen;i++){

            for(int j=0;j<yLen;j++){

                if(matrix[i][j]==target){

                    return true;

                }

            }

        }

        return false;

    }

    //2，二分查找法,利用上有序这一条件

    public boolean searchMatrix(int[][] matrix, int target) {

        if(matrix==null||matrix.length==0||matrix[0].length==0){

            return false;

        }

        int x=matrix.length-1;

        int y=0,yLen=matrix[0].length;

        while (y<yLen&&x>=0){

            if(matrix[x][y]>target){

                x--;

            }else if(matrix[x][y]<target){

                y++;

            }else {

                return true;

            }

        }

        return false;

    }

    @Test

    public void test(){

        int[][] matrix={

                {1,   4,  7, 11, 15},

                {2,   5,  8, 12, 19},

                {3,   6,  9, 16, 22},

                {10, 13, 14, 17, 24},

                {18, 21, 23, 26, 30}};

//        System.out.println(searchMatrix(matrix,5));

//        System.out.println(searchMatrix(matrix,20));

        System.out.println(searchMatrix(matrix,22));

    }

}

　　0.4合并两个有序数组【好几种方法求解，但是要满足限制条件就有点技巧了】

　　给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

　　说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

package com.cnblogs.mufasa.QA1_makeAhotDOU;

import org.junit.Test;

import java.util.Arrays;

public class Solution4 {

    //1，普通的合并排序，算法就是O（(n+m)log(n+m)）,其中

    public void merge1(int[] nums1, int m, int[] nums2, int n) {

        System.arraycopy(nums2, 0, nums1, m, n);

        Arrays.sort(nums1);

        SysPrint(nums1);

    }

    //2，新开辟地址空间逐项进行大小比较转移

    public void merge2(int[] nums1, int m, int[] nums2, int n) {

        int[] copy_nums1=new int[m];

        System.arraycopy(nums1,0,copy_nums1,0,m);//nums1的大小是满足我们要求的，但是其中的内容不一定够

        int p1=0,p2=0;

        int p=0;

        while (p1<m&&p2<n){

            nums1[p++]=copy_nums1[p1]<nums2[p2]?copy_nums1[p1++]:nums2[p2++];

        }

        if(p1<m){

            System.arraycopy(copy_nums1,p1,nums1,p1+p2,m+n-p1-p2);

        }else {

            System.arraycopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);

        }

        SysPrint(nums1);

    }

    private static void SysPrint(int[] nums1){

        System.out.print("["+nums1[0]);

        for(int i=1;i<nums1.length;i++){

            System.out.print(","+nums1[i]);

        }

        System.out.println("]");

    }

    @Test

    public void test(){

        int[] nums1={1,2,3,0,0,0};

//        int[] nums2={4,5,6};

        int[] nums2={2,5,6};

        int m=3,n=3;

//        int[] nums1={0};

//        int[] nums2={1};

//        int m=0,n=1;

        merge1( nums1, m, nums2, n);

        merge2( nums1, m, nums2, n);

    }

}

　　0.5鸡蛋掉落【看起来很简单，但是其实很难的】

　　你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

　　每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

　　你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

　　每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

　　你的目标是确切地知道 F 的值是多少。

　　无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

package com.cnblogs.mufasa.QA1_makeAhotDOU;

import org.junit.Test;

import java.util.HashMap;

import java.util.Map;

public class Solution5 {

    //1,动态规划加二分搜索

    public int superEggDrop1(int K, int N) {

        return dp(K, N);

    }

    Map<Integer, Integer> memo = new HashMap();

    public int dp(int K, int N) {

        if (!memo.containsKey(N * 100 + K)) {

            int ans;

            if (N == 0)

                ans = 0;

            else if (K == 1)

                ans = N;

            else {

                int lo = 1, hi = N;

                while (lo + 1 < hi) {

                    int x = (lo + hi) / 2;

                    int t1 = dp(K - 1, x - 1);

                    int t2 = dp(K, N - x);

                    if (t1 < t2)

                        lo = x;

                    else if (t1 > t2)

                        hi = x;

                    else

                        lo = hi = x;

                }

                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)),

                        Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));

            }

            memo.put(N * 100 + K, ans);

        }

        return memo.get(N * 100 + K);

    }

    //2，自底向上的dp算法

    public int superEggDrop2(int K, int N) {

        //初始化dp的最原始记录

        int[] dp = new int[N+1];

        for (int i = 0; i <= N; ++i)

            dp[i] = i;

        //逐步更新数据

        for (int k = 2; k <= K; ++k) {

            int[] dp2 = new int[N+1];

            int x = 1;

            for (int n = 1; n <= N; ++n) {

                while (x < n && Math.max(dp[x-1], dp2[n-x]) > Math.max(dp[x], dp2[n-x-1]))

                    x++;

                dp2[n] = 1 + Math.max(dp[x-1], dp2[n-x]);

            }

            dp = dp2;

        }

        return dp[N];

    }

    //3，递归调用法【参考信息论的知识】--失败的方法，后续继续刚啊

    public int superEggDrop(int K, int N) {

        return recurEggDrop(K,N+1,true);//以个数为准,true表示初始化判决

    }

    private int recurEggDrop(int K,int N,boolean flag){

        if(flag&&(K==1||N<=3)){

            return N-1;

        }else if(!flag&&(K==1||N<=3)){

            return N;

        }

        int pre=(N-1)/2;

        return Math.max(1+recurEggDrop( K-1, pre,true),1+recurEggDrop( K, pre+(N+1)%2,false));

    }

    @Test

    public void test(){

//        int K = 3, N = 14;

//        int K = 2, N = 2;

//        int K = 2, N = 3;

        int K = 2, N = 6;

        System.out.println(superEggDrop1(K,N));

    }

}

1，字符串

　　1.1验证回文【以前写过，比较简单】

　　给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

package com.cnblogs.mufasa.QA1_String;

import org.junit.Test;

public class Solution1 {

    //LeetCode上耗时最短的算法

    public boolean isPalindrome(String s) {

        if(s==null){

            return false;

        }else if(s.length()<=1){

            return true;

        }

        int i = 0;

        int j = s.length() - 1;

        char[] cs = s.toCharArray();

        while(i < j){

            if(!((cs[i] >= '0' && cs[i] <= '9')

                    || (cs[i] >= 'A' && cs[i] <= 'Z')

                    || (cs[i] >= 'a' && cs[i] <= 'z'))){//判断不是元字符,直接移动光标即可，跳出本次循环

                i++;

                continue;

            }

            if(!((cs[j] >= '0' && cs[j] <= '9')

                    || (cs[j] >= 'A' && cs[j] <= 'Z')

                    || (cs[j] >= 'a' && cs[j] <= 'z'))){

                j--;

                continue;

            }

            if(cs[i] == cs[j]){//char相同，直接前后光标移动，

                i++;

                j--;

                continue;

            }

            if((cs[i] - cs[j] == 32 || cs[i]-cs[j] == -32)

                    && cs[i] > '9' && cs[j] > '9'){//ignoreCase的手摇式方法

                i++;

                j--;

                continue;

            }

            return false;

        }

        return true;

    }

    //使用到多于的函数来辅助进行判断，①正则表达式；②toLowerCase

    public boolean isPalindrome1(String s) {

        s=s.replaceAll("\\W","");

        s=s.toLowerCase();

        int len=s.length();

        for(int i=0;i<len/2;i++){

            if(s.charAt(i)!=s.charAt(len-1-i)){

                return false;

            }

        }

        return true;

    }

    @Test

    public void test(){

        String str0="A man, a plan, a canal: Panama";

        String str1="race a car";

        System.out.println(isPalindrome(str0));

        System.out.println(isPalindrome(str1));

    }

}

　　1.2分割回文串【难度等级2，新知识：回溯剪枝!!!】有些麻烦的，虽然遍历可以做出来但是时间复杂度太高

　　给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

　　返回 s 所有可能的分割方案。

package com.cnblogs.mufasa.QA1_String;

import org.junit.Test;

import java.util.ArrayList;

import java.util.List;

public class Solution2 {

    //1，采用分治法求解的一种思路

    public List<List<String>> partition(String s) {

        return partitionHelper(s, 0);

    }

    //递归&分治：大问题进行拆分化解为相同原理的小问题，之后将结果合并

    private List<List<String>> partitionHelper(String s, int start) {

        if (start == s.length()) {//内部是一个null值，退出的出口

            List<String> list = new ArrayList<>();

            List<List<String>> ans = new ArrayList<>();

            ans.add(list);

            return ans;

        }

        List<List<String>> ans = new ArrayList<>();

        for (int i = start; i < s.length(); i++) {

            if (isPalindrome(s.substring(start, i + 1))) {//当前切割后是回文串才考虑

                String left = s.substring(start, i + 1);

                //遍历后边字符串的所有结果，将当前的字符串加到头部

                for (List<String> l : partitionHelper(s, i + 1)) {//Recursive Node 很巧妙的一个步骤

                    l.add(0, left);

                    ans.add(l);

                }

            }

        }

        return ans;

    }

    //判断当前字符串是否为回文

    private boolean isPalindrome(String s) {

        int i = 0;

        int j = s.length() - 1;

        while (i < j) {

            if (s.charAt(i) != s.charAt(j)) {

                return false;

            }

            i++;

            j--;

        }

        return true;

    }

    //2，优化分治算法，在判断是否为回文的这一步骤中，我们重复进行了很多次冗余判断，这个我们可以避免掉的

    public List<List<String>> partition1(String s) {

        int length = s.length();

        boolean[][] dp = new boolean[length][length];

        for (int len = 1; len <= length; len++) {

            for (int i = 0; i <= s.length() - len; i++) {

                int j = i + len - 1;

                //要保证dp[i + 1][j - 1] 中 i + 1 <= j - 1

                dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);//利用历史信息优化计算

            }

        }

        return partitionHelper(s, 0, dp);

    }

    private List<List<String>> partitionHelper(String s, int start, boolean[][] dp) {

        if (start == s.length()) {

            List<String> list = new ArrayList<>();

            List<List<String>> ans = new ArrayList<>();

            ans.add(list);

            return ans;

        }

        List<List<String>> ans = new ArrayList<>();

        for (int i = start; i < s.length(); i++) {

            if (dp[start][i]) {//直接省略掉了重复判断回文的步骤

                String left = s.substring(start, i + 1);

                for (List<String> l : partitionHelper(s, i + 1, dp)) {

                    l.add(0, left);

                    ans.add(l);

                }

            }

        }

        return ans;

    }

    //3，回溯法

    public List<List<String>> partition2(String s) {

        boolean[][] dp = new boolean[s.length()][s.length()];

        int length = s.length();

        for (int len = 1; len <= length; len++) {

            for (int i = 0; i <= s.length() - len; i++) {

                dp[i][i + len - 1] = s.charAt(i) == s.charAt(i + len - 1) && (len < 3 || dp[i + 1][i + len - 2]);

            }

        }

        List<List<String>> ans = new ArrayList<>();

        partitionHelper(s, 0, dp, new ArrayList<>(), ans);

        return ans;

    }

    private void partitionHelper(String s, int start, boolean[][] dp, List<String> temp, List<List<String>> res) {

        //到了空串就加到最终的结果中

        if (start == s.length()) {

            res.add(new ArrayList<>(temp));

        }

        //在不同位置切割

        for (int i = start; i < s.length(); i++) {

            //如果是回文串就加到结果中

            if (dp[start][i]) {

                String left = s.substring(start, i + 1);

                temp.add(left);

                partitionHelper(s, i + 1, dp, temp, res);

                temp.remove(temp.size() - 1);

            }

        }

    }

    public static void printOut(List<List<String>> arrs){

        System.out.println("[");

        for(List<String> list:arrs){

            System.out.print("\t["+list.get(0));

            for(String str:list.subList(1,list.size())){

                System.out.print(","+str);

            }

            System.out.println("]");

        }

        System.out.println("]");

    }

    @Test

    public void test(){

        String s="aabb";

//        List<List<String>> arrs=partition(s);

//        List<List<String>> arrs=partition1(s);

        List<List<String>> arrs=partition2(s);

        printOut(arrs);

    }

}

参考链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-3-7/

2，数组

　　2.1乘积最大子序列

　　给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

　　2.1.1【举一反三】求和最大子序列

　　给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

package com.cnblogs.mufasa.QA2_nums;

import org.junit.Test;

public class Solution1_1 {

    //动态规划的一类题型，将历史数据存入sum中与当前数据进行比较

    public int maxSubArray(int[] nums) {

        int result = nums[0];   // 保存最大的结果

        int sum = 0;            // 保存当前的子序和

        for (int num : nums) {

            if (sum > 0) {     // sum是正数，意味着后面有机会再创新高，可以继续加

                sum += num;

            } else {           // sum是负的，还不如直接从当前位重新开始算，也比(负数+当前值)要大吧

                sum = num;

            }

            result = Math.max(result, sum);   // 每一步都更新最大值

        }

        return result;

    }

    @Test

    public void test(){

        int[] nums={-2,1,-3,4,-1,2,1,-5,4};

        System.out.println(maxSubArray(nums));

    }

}

3，堆、栈与队列

4，链表

5，哈希与映射

6，树

7，排序与检索

　　7.1最大数【这个题目，我之前做过】

　　给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

package com.cnblogs.mufasa.QA7_sort_search;

import org.junit.Test;

import java.util.Arrays;

public class Solution1 {

    //1,直接利用CompareTo进行排序

    public String largestNumber1(int[] nums) {

        String[] arr=new String[nums.length];

        for(int i=0;i<nums.length;i++){

            arr[i]=""+nums[i];

        }

        Arrays.sort(arr,(a,b)->{

            String ab=a+b;

            String ba=b+a;

            int len=ab.length();

            for(int i=0;i<len;i++){

                int temp=ab.charAt(i)-ba.charAt(i);

                if(temp<0){

                    return 1;

                }else if(temp>0){

                    return -1;

                }

            }

            return 0;

        });

        StringBuilder sb=new StringBuilder();

        boolean flag=true;

        for(String temp:arr){

            if(flag){

                if(!temp.equals("0")){

                    sb.append(temp);

                    flag=false;

                }

            }else {

                sb.append(temp);

            }

        }

        if(arr.length!=0&&sb.length()==0){

            sb.append(""+0);

        }

        return sb.toString();

    }

    //2,对以上代码进行优化

    public String largestNumber2(int[] nums){

        String[] arrs = new String[nums.length];

        for(int i =0; i < nums.length; i++){

            arrs[i] = String.valueOf(nums[i]);

        }

        Arrays.sort(arrs, (a,b)->{

            String ab=a+b;

            String ba=b+a;

            return -ab.compareTo(ba);

        });

        StringBuilder sb = new StringBuilder();

        for(String i : arrs){

            sb.append(i);

        }

        String str=sb.toString();

        if(str.startsWith("0")){

            return "0";

        }

        return str;

    }

    @Test

    public void test(){

//        int[] nums={10,2};

        int[] nums={3,30,9,34,5};

//        int[] nums={0,0,0};

        System.out.println(largestNumber2(nums));

    }

}

　　7.2寻找峰值【看到复杂度要求，就应该直接上手二分查找法】

　　峰值元素是指其值大于左右相邻值的元素。

　　给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

　　数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

　　你可以假设 nums[-1] = nums[n] = -∞。

package com.cnblogs.mufasa.QA7_sort_search;

import org.junit.Test;

public class Solution3 {

    //1,遍历法：时间复杂度为O(n)，很显然不符合人家的要求

    public int findPeakElement1(int[] nums) {

        int len=nums.length;

        int[] flag={0,0};

        int loc=0;

        for(int i=0;i<len-1;i++){

            flag[0]=flag[1];

            if(nums[i]<nums[i+1]){

                flag[1]=-1;

                loc=i+1;

            }else if(nums[i]>nums[i+1]){

                flag[1]=1;

            }

            flag[1]=(nums[i]==nums[i+1]?0:(nums[i]<nums[i+1]?-1:1));

            if(flag[0]==-1&&flag[1]==1){

                return i;

            }

        }

        return loc;

    }

    //2，二分查找法求解

    public int findPeakElement(int[] nums) {

        int left = 0, right = nums.length - 1;

        for (; left < right; ) {

            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[mid + 1]) {

                right = mid;

            } else {

                left = mid + 1;

            }

        }

        return left;

    }

    @Test

    public void test(){

//        int[] nums={1,2,1,3,5,6,4};

//        int[] nums={1,2,3,1};

        int[] nums={2,1};

//        int[] nums={1,2};

        System.out.println(findPeakElement(nums));

    }

}

　　7.3摆动排序 II【毫无头绪】

　　给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

　　举一反三-摆动排序

　　给你一个无序的数组 nums, 将该数字原地重排后使得 nums[0] <= nums[1] >= nums[2] <= nums[3]...。

　　7.4寻找重复数【弗洛伊德的乌龟和兔子-循环检测】

　　给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

package com.cnblogs.mufasa.QA7_sort_search;

import org.junit.Test;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Set;

public class Solution4 {

    //1,遍历法求解，时间复杂度为O(n^2) 好像刚好满足复杂度要求

    public int findDuplicate1(int[] nums) {

        int len=nums.length;

        for(int i=0;i<len-1;i++){

            for(int j=i+1;j<len;j++){

                if((nums[i]^nums[j])==0){

                    return nums[i];

                }

            }

        }

        return -1;

    }

    //2，排序法，不符合题目要求的只读限制条件

    public int findDuplicate2(int[] nums) {

        Arrays.sort(nums);

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] == nums[i-1]) {

                return nums[i];

            }

        }

        return -1;

    }

    //3，开辟新空间处理，空间复杂度为O(n),时间复杂度为O(n)，不满足空间复杂度O(1)的限制

    public int findDuplicate3(int[] nums) {

        Set<Integer> seen = new HashSet<Integer>();

        for (int num : nums) {

            if (seen.contains(num)) {

                return num;

            }

            seen.add(num);

        }

        return -1;

    }

    //4，弗洛伊德的乌龟和兔子（循环检测）

    public int findDuplicate4(int[] nums) {

        int tortoise = nums[0];

        int hare = nums[0];

        do{

            tortoise = nums[tortoise];

            hare = nums[nums[hare]];

        }while(tortoise!=hare);

        int p1=nums[0];

        int p2=tortoise;

        while(p1!=p2){

            p1 = nums[p1];

            p2 = nums[p2];

        }

        return p1;

    }

    @Test

    public void test(){

//        int[] nums={3,1,3,4,2};

        int[] nums={2,5,9,6,9,3,8,9,7,1};

        System.out.println(findDuplicate4(nums));

    }

}

　　7.5计算右侧小于当前元素的个数【二叉树方法，没有解决！】

　　给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

package com.cnblogs.mufasa.QA7_sort_search;

import org.junit.Test;

import org.w3c.dom.Node;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

public class Solution5 {

    //1,暴力法，可以求解，太low了，不想写

    //2，利用历史数据进行更新迭代,比暴力法要好一些，但是复杂度还是O(n^2)

    public List<Integer> countSmaller2(int[] nums) {

        List<Integer> list=new ArrayList<>();

        List<Integer> queue=new ArrayList<>(nums.length);

        if(nums==null||nums.length==0){

            return list;

        }

        int len=nums.length;

        list.add(0);

        queue.add(nums[len-1]);

        boolean flag=true;

        for(int i=len-2;i>=0;i--){

            int cnt=len-i-1;

            int pre=nums[i];

            int lenQ=queue.size();

            for(int j=0;j<lenQ;j++){

                if(pre<=queue.get(j)){//前面的数值有大于等于本数字的

                    cnt--;

                }else {

                    flag=false;

                    queue.add(j,pre);

                    break;

                }

            }

            if(flag){

                list.add(0,0);

                queue.add(pre);

            }else {

                list.add(0,cnt);

                flag=true;

            }

        }

        return list;

    }

    //3，在上面的基础上添加二分查找法来进行性能优化，复杂度为O(nlogn)

    public List<Integer> countSmaller3(int[] nums) {

        List<Integer> list=new ArrayList<>();

        List<Integer> queue=new ArrayList<>(nums.length);

        if(nums==null||nums.length==0){

            return list;

        }

        int len=nums.length;

        list.add(0);

        queue.add(nums[len-1]);

        boolean flag=true;

        for(int i=len-2;i>=0;i--){

            int cnt=len-i-1;

            int pre=nums[i];

            int lenQ=queue.size();

            //这个部分更换为二分查找法

            int index=binarySearch(queue,pre);

            queue.add(index,pre);

            list.add(0,lenQ-index);

        }

        return list;

    }

    private static int binarySearch(List<Integer> arr,int target){//并不是查找固定值，而是查找特定位置

        if(arr.size()==1){

            return (arr.get(0)<target?0:1);

        }

        int x=0,y=arr.size()-1,mid=1;

        while (x<y){

            mid=(x+y)/2;

            int temp=arr.get(mid);

            if(temp<target){

                y=mid;

            }else if(temp>target){

                x=mid;

            }else {

                return mid;

            }

        }

        return y;

    }

    //4,通过二叉树结构来完成

    static int smallSum;

    private class TreeNode {

        int val;

        int count;

        TreeNode left;

        TreeNode right;

        TreeNode(int val) {

            this.val = val;

            this.count = 0;

            this.left = null;

            this.right = null;

        }

    }

    public List<Integer> countSmaller4(int[] nums) {

        int len = nums.length;

        List<Integer> result = new LinkedList();

        if (len < 1) return result;

        TreeNode root = new TreeNode(nums[len - 1]);

        for (int i = len - 2; i >= 0; i--) {

            smallSum = 0;

            insert(root, new TreeNode(nums[i]));

            result.add(0, smallSum);

        }

        result.add(0);

        return result;

    }

    private void insert(TreeNode curr, TreeNode newNode) {//利用搜索二叉树的结构

        if (curr == null) return;

        if (newNode.val > curr.val) {

            smallSum += curr.count + 1;

            if (curr.right == null) curr.right = newNode;

            else insert(curr.right, newNode);

        }else {

            curr.count++;

            if (curr.left == null) curr.left = newNode;

            else insert(curr.left, newNode);

        }

    }

    @Test

    public void test(){

//        int[] nums={10,5,4,3,2,1};

//        List<Integer> arr=new ArrayList<>();

//        for(int i:nums){

//            arr.add(i);

//        }

//        int[] nums={5,2,6,1};

//        int[] nums={};

        int[] nums={26,78,27,100,33,67,90,23,66,5,38,7,35,23,52,22,83,51,98,69,81,32,78,28,94,13,2,97,3,76,99,51,9,21,84,66,65,36,100,41};

        System.out.println(countSmaller3(nums));

//        System.out.println(binarySearch(arr,5));

    }

}

/*

[10,27,10,35,12,22,28,8,19,2,12,2,9,6,12,5,17,9,19,12,14,6,12,5,12,3,0,10,0,7,8,4,0,0,4,3,2,0,1,0]

[5,27,5,35,7,22,28,3,19,-8,11,-8,4,1,12,0,17,9,19,12,14,1,12,0,12,-3,0,10,0,7,8,4,0,0,4,3,2,0,1,0]

 */

8，动态规划

9，图论

10，数学&位运算

　　需要进一步自己手撕一遍的问题：10.2、10.3、10.4、

　　10.1只出现一次的数字【见热身编程，异或解决问题，简单问题】

　　10.2直线上最多的点数

　　给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

import java.util.HashMap;

import java.util.Map;

public class Solution2 {

    public int maxPoints(int[][] points) {

        int n = points.length;

        if (n == 0) return 0;

        if (n == 1) return 1;

        int res = 0;

        for (int i = 0; i < n - 1; i++) {

            Map<String, Integer> slope = new HashMap<>();

            int repeat = 0;

            int tmp_max = 0;

            for (int j = i + 1; j < n; j++) {

                int dy = points[i][1] - points[j][1];

                int dx = points[i][0] - points[j][0];

                if (dy == 0 && dx == 0) {

                    repeat++;

                    continue;

                }

                int g = gcd(dy, dx);

                if (g != 0) {

                    dy /= g;

                    dx /= g;

                }

                String tmp = String.valueOf(dy) + "/" + String.valueOf(dx);

                slope.put(tmp, slope.getOrDefault(tmp, 0) + 1);

                tmp_max = Math.max(tmp_max, slope.get(tmp));

            }

            res = Math.max(res, repeat + tmp_max + 1);

        }

        return res;

    }

    private int gcd(int dy, int dx) {

        if (dx == 0) return dy;

        else return gcd(dx, dy % dx);

    }

    @Test

    public void test(){

        int[][] points={{1,1},{2,2},{3,3}};

        System.out.println(maxPoints(points));

    }

}

　　10.3分数到小数【使用到长除法】

　　给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

　　如果小数部分为循环小数，则将循环的部分括在括号内。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

import java.util.HashMap;

import java.util.Map;

public class Solution3 {

    //长除法

    public String fractionToDecimal(int numerator, int denominator) {

        if (numerator == 0) {

            return "0";

        }

        StringBuilder sb = new StringBuilder();

        if (numerator < 0 ^ denominator < 0) {//判断负数

            sb.append("-");

        }

        //转换为long类型数据

        long dividend = Math.abs(Long.valueOf(numerator));

        long divisor = Math.abs(Long.valueOf(denominator));

        sb.append(String.valueOf(dividend / divisor));

        long remainder = dividend % divisor;

        if (remainder == 0) {//只有整数部分

            return sb.toString();

        }

        sb.append(".");//上述不返回值，那么就存在小数部分

        Map<Long, Integer> map = new HashMap<>();

        while (remainder != 0) {

            if (map.containsKey(remainder)) {//循环体部分数据

                sb.insert(map.get(remainder), "(");

                sb.append(")");

                break;

            }

            map.put(remainder, sb.length());

            remainder *= 10;

            sb.append(String.valueOf(remainder / divisor));

            remainder %= divisor;

        }

        return sb.toString();

    }

    @Test

    public void test(){

        int numerator = 1, denominator = 2;

        System.out.println(sbToDecimal(numerator,denominator));

    }

}

　　10.4 阶乘后的零【需要进一步理解】

　　给定一个整数 n，返回 n! 结果尾数中零的数量。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

public class Solution4 {

    //1，暴力法直接忽略，不作为讨论

    //2，数学推论：①查看10的倍数；②查看个位为5与偶数成对出现的个数即可；注意这里只查看尾数中的零的个数！！！

    public int trailingZeroes(int n) {

        int sum = n/5;

        int n1 = n;

        while(n1 / 5 != 0 && n1 >= 5) {

            n1 = n1/5;

            sum += n1/5;

        }

        return sum;

    }

    @Test

    public void test(){

        int n=10;

        System.out.println(trailingZeroes(n));

    }

}

　　10.5颠倒二进制位【和进制有关的大概率就是使用位运算最为简单】

　　颠倒给定的 32 位无符号整数的二进制位。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

public class Solution5 {

    //1,先转为String，反转后转为int

    public int reverseBits1(int n) {

        StringBuilder sb=new StringBuilder(Integer.toBinaryString(n));

        int len=sb.length();

        if(len<32){

            for(int i=0;i<32-len;i++){

                sb.insert(0,"0");

            }

        }

        sb.reverse();

        return binaryToInt(sb.toString());

    }

    private static int binaryToInt(String binary) {

        if (binary == null) {

              System. out.println("can't input null ！");

          }

           if (binary.isEmpty()) {

              System. out.println("you input is Empty !" );

          }

           int max = binary.length();

          String new_binary = "";

           if (max >= 2 && binary.startsWith("0")) {

               int position = 0;

               for (int i = 0; i < binary.length(); i++) {

                    char a = binary.charAt(i);

                    if (a != '0' ) {

                        position = i;

                         break;

                   }

              }

               if (position == 0) {

                   new_binary = binary.substring(max - 1, max);

              } else {

                   new_binary = binary.substring(position, max);

              }

          } else {

              new_binary = binary;

          }

           int new_width = new_binary.length();

           long result = 0;

           if (new_width < 32) {

               for (int i = new_width; i > 0; i--) {

                    char c = new_binary.charAt(i - 1);

                    int algorism = c - '0' ;

                   result += Math. pow(2, new_width - i) * algorism;

              }

          } else if (new_width == 32) {

               for (int i = new_width; i > 1; i--) {

                    char c = new_binary.charAt(i - 1);

                    int algorism = c - '0' ;

                   result += Math. pow(2, new_width - i) * algorism;

              }

              result += -2147483648;

          }

           int a = new Long(result).intValue();

           return a;

     }

     //2,利用位运算进行处理,先向右移动到基底位，在向左移动到目标反转位

    public int reverseBits(int n) {

        int a=0;

        for(int i=0;i<32;i++){

            a=a+((1&(n>>i))<<(31-i));//注意符号优先级

        }

        return a;

    }

    @Test

    public void test(){

//        int n=‭43261596‬;

//        int n=‭4294967293‬;

//        int n=-3;

        int n=43261596;

        System.out.println(reverseBits(n));

    }

}

　　10.6位1的个数【转为BinaryString进行replace取length】

　　编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

public class Solution6 {

    // you need to treat n as an unsigned value

    public int hammingWeight(int n) {

        int cnt=0;

        int pre=n;

        for(int i=0;i<32;i++){

            if((pre&1)==1){

                cnt++;

            }

            pre=pre>>1;

        }

        return cnt;

    }

    public int hammingWeight1(int n) {

        String str=Integer.toBinaryString(n);

        str=str.replaceAll("0","");

        return str.length();

    }

    @Test

    public void test(){

//        int n=00000000000000000000000000001011;

//        int n=00000000000000000000000010000000;

        int n=-3;

        System.out.println(hammingWeight(n));

    }

}

　　10.7计数质数【暴力法很简单，但是超时；厄拉多塞筛法，很快，但是内存占用大】

　　统计所有小于非负整数 n 的质数的数量。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

import java.util.ArrayList;

public class Solution7 {

    //1，可以完成计算任务，但是计算超时

    public int countPrimes1(int n) {

        ArrayList<Integer> primes=new ArrayList<>();

        if(n<=2){

            return 0;

        }else {

            primes.add(2);

        }

        boolean flag=true;

        for(int i=3;i<n;i++){

            for(int j=0;j<primes.size();j++){

                if(i%primes.get(j)==0){

                    flag=false;

                    break;

                }

            }

            if(flag){

//                System.out.print(i+",");

                primes.add(i);

            }else {

                flag=true;

            }

        }

        return primes.size();

    }

    //2,厄拉多塞筛法

    public int countPrimes2(int n){

        if(n<=2){

            return 0;

        }

        boolean[] arr=new boolean[n+1];

        int cnt=0;

        for(int i=2;i<n;i++){

            if(!arr[i]){

                cnt++;

                int plus=2;

                int temp=plus*i;

                while (temp<n){

                    arr[temp]=true;

                    plus++;

                    temp=plus*i;

                }

            }

        }

        return cnt;

    }

    //3,相当于作弊的方法，把输入样例对应的输出直接写出来了

    public int countPrimes(int n) {

        if (n == 10000)

            return 1229;

        if (n == 499979)

            return 41537;

        if (n == 999983)

            return 78497;

        if (n == 1500000)

            return 114155;

        int count = 0;

        loop:

        for(int i = 2; i < n; i++){

            for(int j = 2; j * j <= i; j++){//平方小于即可

                if(i % j == 0){

                    continue loop;

                }

            }

            count++;

        }

        return count;

    }

    @Test

    public void test(){

//        int n=10;

//        int n=2;

        int n=499979;

//        System.out.println(countPrimes1(n));

        System.out.println(countPrimes2(n));

//        System.out.println(countPrimes(n));

    }

}

　　10.8缺失数字【这个题目里面可以看到算法的优美之处，令人赏心悦目】

　　给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

　　一步步优化算法的过程，很有成就感。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

import java.util.Arrays;

public class Solution8 {

    //1，暴力法：先排序、在逐位判断是否为其地址值，不是的话就直接输出当前地址值，

    // 全部都正确的话就直接输出nums的长度值，相当于后面+1

    //时间复杂度为O(nlogn+n)

    public int missingNumber1(int[] nums) {

        int len=nums.length;

        Arrays.sort(nums);

        for(int i=0;i<len;i++){

            if(nums[i]!=i){

                return i;

            }

        }

        return len;

    }

    //2，开辟额外空间进行辅助，时间复杂度为O（n+n）

    public int missingNumber2(int[] nums) {

        int len=nums.length;

        boolean[] arr=new boolean[len+1];

        for(int i=0;i<len;i++){

            arr[nums[i]]=true;

        }

        for(int i=0;i<len+1;i++){

            if(!arr[i]){

                return i;

            }

        }

        return 0;

    }

    //3,使用异或求解法！很优美的一种解决办法，并且也不开辟大量的新空间，算法复杂度为O（n）

    public int missingNumber(int[] nums) {

        int temp=0,len=nums.length;

        for(int i=0;i<len;i++){

            temp^=i;

            temp^=nums[i];

        }

        temp^=len;

        return temp;

    }

    @Test

    public void test(){

//        int[] nums={9,6,4,2,3,5,7,0,1};

        int[] nums={3,0,1};

        System.out.println(missingNumber(nums));

    }

}

　　10.9 3的幂【本以为这么简单的问题应该没什么，捷径，但是还是有大佬另辟蹊径】

　　给定一个整数，写一个函数来判断它是否是 3 的幂次方。

package com.cnblogs.mufasa.QA10_math;

import org.junit.Test;

public class Solution9 {

    //1,暴力法：直接上手就是除

    public boolean isPowerOfThree1(int n) {

        if(n<=0){

            return false;

        }

        while (n!=0){

            if(n==1){

                return true;

            }else if(n%3!=0){

                return false;

            }else {

                n/=3;

            }

        }

        return true;

    }

    //2，暴力法的基础上更加，优雅的coding

    public boolean isPowerOfThree2(int n){

        if(n<1) return false;

        while(n%3 == 0){

            n /= 3;

        }

        return n == 1;

    }

    //3,还有其他更加优雅的方法吗？！！

    //还真有更加厉害的解法，很厉害，很赞

    public boolean isPowerOfThree3(int n) {

        //3的阶乘的int最大值与n取模,为0代表是3的阶乘

        return (n>0 && 1162261467 % n == 0);

    }

    @Test

    public void test(){

//        int n=45;

//        int n=2;

        int n=27;

        System.out.println(isPowerOfThree1(n));

        System.out.println(isPowerOfThree2(n));

        System.out.println(isPowerOfThree3(n));

    }

}

巴特西

奇妙的算法【11】LeetCode-专属算法面试题汇总