leecode

1.两个数的交集(350)

使用map
解题思路，分成以下4个小问题：
1.先遍历第一个数组，把数字和次数放进map，然后遍历第二个
2.遍历第一个时有如下2种情况：1.map中没有怎么办？ 2.map中有怎么办？
3.遍历第二个也有上面2个问题
4.构建合适的数组。（不要用list，用list还需要多一次遍历）

使用双指针
解题思路：保证参数前小后大；构建容积不定的数组；构建双指针；比较双指针读数；处理结尾；

方法1：利用map

    public static int[] intersect2(int[] a1, int[] a2) {
        //之所以比较
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a1.length; i++) {
            map.put(a1[i], map.getOrDefault(a1[i], 0) + 1);
        }
        int[] result = new int[a2.length];
        int index = 0;
        for (int i = 0; i < a2.length; i++) {
            int times = map.getOrDefault(a2[i], 0);
            if (times != 0) {
                result[index++] = a2[i];
                map.put(a2[i], times - 1);
            }
        }
        return Arrays.copyOfRange(result, 0, index);
    }
/**
 * 分成以下4个小问题：
 * 1.先遍历第一个数组，把数字和次数放进map，然后遍历第二个
 * 2.遍历第一个时有如下2种情况：1.map中没有怎么办？ 2.map中有怎么办？
 * 3.遍历第二个也有上面2个问题
 * 4.构建合适的数组。（不要用list，用list还需要多一次遍历）
 * <p>
 * 学到的知识点：
 * 1.map要获取不确定是否存在的元素：getOrDefault()
 * 2.构建长度不确定的数组。可以先规定最大长度，然后CopyOfRange()。另外构建数组的时候一定要有指针index
 */

方法2：进阶，使用双指针。

    public static int[] betterInteract(int[] a1, int[] a2) {
        if (a1.length > a2.length) {
            return betterInteract(a2, a1);
        }
        int index = 0, rindex = 0;
        int[] result = new int[a1.length];
        for (int i = 0; i < a1.length; i++) {
            while (index < a2.length && a2[index] < a1[i]) {
                index++;
            }
            if (a2[index] == a1[i]) {
                result[rindex++] = a1[i];
            }
        }
        //保证参数前小后大；构建容积不定的数组；构建双指针；比较双指针读数；处理结尾；
        return Arrays.copyOfRange(result,0,rindex);
    }

学到的知识点：1-6

1.map要获取不确定是否存在的元素：getOrDefault()
2.构建容积不定的数组。可以先规定最大长度，然后CopyOfRange()。另外构建数组的时候一定要有指针index

3.保证参数前小后大；（调用函数自身）
4.构建双指针；使用for和 一个指针。
5.比较双指针读数；（大于，小于，等于）
6.处理结尾；（任意数组到头了）

2.最长公共子前缀(14)

思路：选基准，依次把剩下的数据和基准比较； 寻找两个字符串的最长共同前缀； 分析并处理最后可能的各种结果

public static String getLargestLengthFix(String[] strs) {
    if(strs.length == 0) return "";
    String pivot = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(pivot) != 0) {
            pivot = pivot.substring(0,pivot.length()-1);
            if(pivot.equals("")) return "";
        }
    }
    return pivot;
}

学到的知识点：7-8

7.寻找两个字符串的最长公共子前缀。（String.substring())
8.如果在遍历过程中，已经产生了最终结果，就直接返回。 if() return

3.买卖股票的最佳时机(122)

    public static int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length-1; i++) {
            int temp = prices[i+1] - prices[i];
            if(temp>0) {
                profit += temp;
            }
        }
        return profit;
    }

4.旋转数组

    public static int gcd(int min, int max) {
        return max > 0 ? gcd(max, min % max) : min; //辗转相除法求gcd
    }
    //1.确定循环次数  2.确定每趟的终止条件  3.需要继续循环的交换位置（固定一边交换位置）
    public static int[] traverse(int[] arr, int k) {
        int n = arr.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; start++) {
            int current = start;
            int prev = arr[current];
            do {
                int pos = (current + k) % n;
                int temp = arr[pos];
                arr[pos] = prev;
                prev = temp;
                current = pos;
            } while (current != start);
        }
        return arr;
    }

学到的知识点9-12

9.数组以k个为一组循环，循环次数是n和k的公约数。
10.最大公约数的代码。
11.k组循环每组终止条件：记录开始指针，当前指针==开始指针，就结束
12.固定一边交换位置：正常的交换，少一步填坑就行了。

5.删除数组中的重复元素

首先数组是有序数组。
这种要统计数组中每个数出现次数的。要么用hash，但是如果要求本地删除（空间复杂度为1），那就一定得是有序的了。
如果不是有序的，仍然要空间复杂度为1呢？那就时间换空间。用复杂度为O(n^2)的算法。两个for循环。
第一个for循环是遍历arr数组，第二个for循环是遍历arr前面已经整理好的部分。