数组暂存

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/
这道题首先要把所有数需要相乘的左侧的数都乘好放在该位置上。然后需要一个变量，从右边开始乘，在和当前位置上的左侧数乘，就是答案。

public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int[] res = new int[l];
        res[0] = 1;
        for(int i=1;i<l;i++){
            res[i] = res[i-1]*nums[i-1];
        }
        int cur = nums[l-1];
        for(int i=l-2;i>=0;i--){
            res[i] = res[i]*cur;
            cur*=nums[i];
        }
        return res;
    }

还有一种方法 当禁用除法的时候，我们可以巧妙的使用LOG，来把乘除法变成加减法。

public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int zero = 0;
        int neg = 0;
        double pro = 0;
        for(int i=0;i<l;i++){
            if(nums[i] == 0) zero++;
            else if(nums[i]<0){
                neg++;
                pro+=Math.log(-nums[i]);
            }else{
                pro+=Math.log(nums[i]);
            }
        }
        int[] res = new int[l];
        if(zero>=2) return res;
        for(int i=0;i<l;i++){
            if(zero == 1){
                if(nums[i]==0) res[i] = ((neg)%2==0?1:-1) * (int) Math.round(Math.exp(pro));
            }else{
               if(nums[i]<0){
                    res[i] = ((neg-1)%2==0?1:-1) * (int)Math.round(Math.exp(pro-Math.log(-nums[i])));
                }else{
                    res[i] = ((neg)%2==0?1:-1) * (int)Math.round(Math.exp(pro-Math.log(nums[i])));
                } 
            }
            
        }
        
        return res;
    }

快慢指针

287. Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/description/

public int findDuplicate(int[] nums) {
        int l = nums.length;
        if(l <= 1) return 0;
        int slow = 0, fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow==fast) break;
        }
        slow = 0;
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

负数的利用

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

public List<Integer> findDuplicates(int[] nums) {
        int l = nums.length;
        List<Integer> res = new ArrayList<>();
        if(l<=1) return res;
        for(int i = 0; i < l; i++){
            int pos = Math.abs(nums[i])-1;
            if(nums[pos]<0){
                res.add(pos+1);
            }
            nums[pos] = -nums[pos]; 
        }
        return res;
    }

565. Array Nesting

https://leetcode.com/problems/array-nesting/description/

public int arrayNesting(int[] nums) {
        int max = 0;
        int l = nums.length;
        //boolean[] set = new boolean[l];
        for(int i=0;i<l;i++) {
            if(nums[i]<0) continue;
            int cnt = 0;
            int j = i;
            while(nums[j]>=0){
                nums[j] = -nums[j]-1;
                j = Math.abs(nums[j]+1);
                cnt++;
            }
            max = Math.max(max,cnt);
        }
        return max;
    }

二维数组旋转

如果是顺时针旋转90度。 就按主对线，对折交换。随后再按竖中轴线交换。
180度。先按朱对线，对折交换。在按辅对线，对折交换。
270度。主对角线对折交换，再按横中轴线交换。

48. Rotate Image

https://leetcode.com/problems/rotate-image/description/

public void rotate(int[][] matrix) {
        int l = matrix.length;
        for(int i=l-2;i>=0;i--){
            for(int j=i+1;j<l;j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        for(int i=0;i<l/2;i++){
            for(int j=0;j<l;j++){
                int tmp = matrix[j][i];
                matrix[j][i] = matrix[j][l-i-1];
                matrix[j][l-i-1] = tmp;
            }
        }
    }

前向型指针

80. Remove Duplicates from Sorted Array II

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

public int removeDuplicates(int[] nums) {
        if(nums.length == 0) return 0;
        int l = nums.length;
        int cur = nums[0];
        int cnt = 1;
        int j = 1;
        for(int i=1; i < l; i++){
            if(nums[i] == cur){
                cnt++;
                if(cnt==2)
                    nums[j++] = cur;
            }else{
                cur = nums[i];
                cnt = 1;
                nums[j++] = cur;
            }
        }
        return j;
    }

169. Majority Element

https://leetcode.com/problems/majority-element/description/

public int majorityElement(int[] nums) {
        int major = 0;
        int cnt = 0;
        for(int num : nums){
            if(cnt == 0){
                major = num;
                cnt++;
            }else{
                if(major == num) cnt++;
                else cnt--;
            }
        }
        return major;
    }

229. Majority Element II

https://leetcode.com/problems/majority-element-ii/description/
这个方法可以判断N个大于1/(N+1)个数的元素。但是一定要先判断是否等于候选。

public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int cnt1 = 0, cnt2 = 0, n1 = 0, n2 = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == n1){
                cnt1++;
            }else if(nums[i] == n2){
                cnt2++;
            }
            else if(cnt1==0){
                n1 = nums[i];
                cnt1++;
            }else if(cnt2==0){
                n2 = nums[i];
                cnt2++;
            }else{
                cnt1--;
                cnt2--;
            }
        }
        int up = nums.length/3;
        int cnt=0,cntt=0;
        System.out.println(n1+","+n2);
        for(int i=0;i<nums.length;i++){
            if(nums[i] == n1)
                cnt++;
            if(nums[i] == n2){
                cntt++;
            }
        }
        if(cnt>up) res.add(n1);
        if(n2!=n1 && cntt>up) res.add(n2);
        return res;
        
    }

滑动窗口

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256];
        int lt = s.length();
        int l=0,r=-1;
        int max = 0;
        while(l<lt){
            if(r+1<lt && map[s.charAt(r+1)]==0){
                ++map[s.charAt(++r)];
            }else{
                --map[s.charAt(l++)];
            }
            max = Math.max(max,r-l+1);
        }
        return max;
    }
}

209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/

public int minSubArrayLen(int s, int[] nums) {
        int min = Integer.MAX_VALUE;
        int l = nums.length;
        if(l == 0) return 0;
        int ed = -1, st = 0;
        int sum = 0;
        while(st<l){
            if(ed+1<l && sum<s){
                sum = sum+nums[++ed];
            }else{
                sum = sum-nums[st++];
            }
            if(sum>=s)
                min = Math.min(ed-st+1,min);
        }
        return min==Integer.MAX_VALUE?0:min;
    }

713. Subarray Product Less Than K

https://leetcode.com/problems/subarray-product-less-than-k/description/

public int numSubarrayProductLessThanK(int[] nums, int k) {
        int i = 0;
        int l = nums.length;
        if(l == 0 || k<=1) return 0;
        int sum = 1;
        int res = 0;
        for(int j=0;j<l;j++){
            sum *= nums[j];
            while(i<=j && sum>=k) sum/=nums[i++];
            res+= j-i+1;
        }
        return res;
    }

1.将小数组归并到大数组里
http://www.lintcode.com/zh-cn/problem/merge-sorted-array/
这道题是默认A有足够的空间，我们可以通过比谁大，先放在A的最后。这样就不需要额外的空间了

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m-1, j = n-1;
        int l = A.length-1;
        while(i >= 0 && j >= 0){
            if(A[i]>B[j]) A[l--] = A[i--];
            else A[l--] = B[j--];
        }
        while(i>=0) A[l--] = A[i--];
        while(j>=0) A[l--] = B[j--];
    }

http://www.lintcode.com/zh-cn/problem/merge-two-sorted-arrays/
基本功

public int[] mergeSortedArray(int[] A, int[] B) {
        int[] ans = new int[A.length+B.length];
        int i = 0, j = 0,l = 0;
        while(i<A.length && j<B.length){
            if(A[i]<B[j]) ans[l++] = A[i++];
            else ans[l++] = B[j++];
        }
        while(i<A.length){
            ans[l++] = A[i++];
        }
        while(j<B.length){
            ans[l++] = B[j++];
        }
        return ans;
    }

2.两个数组的交
方法1.排序加2根指针。

方法2. HASH

方法3. sort+二分查找

LeetCode

667. Beautiful Arrangement II

https://leetcode.com/problems/beautiful-arrangement-ii/description/
这道题的核心就是要知道如果N为10，那么K最多为9.需要最小最大，次小次大这样构建。
192837.。。
那么如果K=2的时候，我们就不能用19来构建，得需把9放第一位。
所以k%2 == 0 我们用后面的数字，1 我们用前面的数字。
最后统一放i++

public int[] constructArray(int n, int k) {
        int[] A = new int[n];
        int m = 0;
        for(int i=1,j=n;i<=j;){
            if(k>1){
                A[m++] = k-- % 2 == 0? j-- : i++;
            }else{
                A[m++] = i++;
            }
        }
        return A;
        
    }

769. Max Chunks To Make Sorted

https://leetcode.com/problems/max-chunks-to-make-sorted/description/
如果左边最大可以小于右边最小，那么就可以切这一刀。

public int maxChunksToSorted(int[] arr) {
        int l = arr.length;
        int[] left = new int[l];
        for(int i=1;i<l;i++){
            left[i] = Math.max(left[i-1],arr[i-1]);
        }
        int[] right = new int[l];
        right[l-1] = l;
        for(int i=l-2;i>=0;i--){
            right[i] = Math.min(right[i+1],arr[i+1]);
        }
        int cnt = 0;
        for(int i=l-2;i>=0;i--){
            if(right[i]>left[i+1]) cnt++;
        }
        return cnt+1;
    }

73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/
这道题O 1 空间的思路，就是如何这一列需要置为0的话，就把第一行的该列置为0.行同样如此处理。
因为需要占用第一行 第一列。所以在一开始的时候我们就需要2个BOOLEAN值，代表开始状态时，第一行是否需要全为0，第一列是否需要全为0.

 public void setZeroes(int[][] matrix) {
        if(matrix==null||matrix.length==0) return;
        int h = matrix.length;
        int l = matrix[0].length;
        boolean row0 = false;
        boolean col0 = false;
        for(int i=0;i<l;i++){
            if(matrix[0][i] == 0){
                row0 = true;
                break;
            }
        }
        for(int i=0;i<h;i++){
            if(matrix[i][0] == 0){
                col0 = true;
                break;
            }
        }
        for(int i=1;i<h;i++){
            for(int j=1;j<l;j++){
                if(matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for(int i=1;i<l;i++){
            if(matrix[0][i] == 0){
                for(int j=1;j<h;j++) matrix[j][i] = 0;
            }
        }
        for(int i=1;i<h;i++){
            if(matrix[i][0] == 0){
                for(int j=1;j<l;j++) matrix[i][j] = 0;
            }
        }
        if(row0)
            for(int i=0;i<l;i++) matrix[0][i] = 0;
        if(col0)
            for(int i=0;i<h;i++) matrix[i][0] = 0;
    }

795. Number of Subarrays with Bounded Maximum

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/
这道题带点动规的思想。如果有一个数大于R了。那么就需要隔断。
如果这是数在范围里，那么以它结尾的数，就是前面所有的子集加上这个数，再单独加上自己。
如果这个数小于范围。那么就用前面所有的子集+自己。

public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int l = A.length;
        int[] dp = new int[l+1];
        int cnt = 0;
        for(int i=0;i<l;i++){
            if(A[i]>=L && A[i]<=R){
                dp[i+1] = dp[i]+1+cnt;
                cnt = 0;
            }else if(A[i]>R){
                dp[i+1] = 0;
                cnt = 0;
            }else{
                dp[i+1] = dp[i];
                cnt++;
            }
        }
        int res = 0;
        for(int i=0;i<=l;i++){
            res+=dp[i];
        }
            
        return res;
    }

如果题目要求的子集和在这个范围里的话，解答如下：

public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int l = A.length;
        int[] presum = new int[l+1];
        for(int i=1;i<=l;i++){
            presum[i] = presum[i-1]+A[i-1];
        }
        int sum = 0;
        int res = 0;
        for(int i=0;i<l;i++){
            sum += A[i];
            int lb = sum-R;
            int ub = sum-L+1;
            int ll = Arrays.binarySearch(presum,0,i+1,lb);
            if(ll<0) ll = -ll-1;
            int uu = Arrays.binarySearch(presum,0,i+1,ub);
            if(uu<0) uu = -uu-1;
            res+= uu-ll;
        }
        return res;
    }

670. Maximum Swap

https://leetcode.com/problems/maximum-swap/description/
桶排，随后就是看最前面的字母和桶里最大数的坐标，是不是在这个坐标前，在的话，就可以换了。

 public int maximumSwap(int num) {
        char[] ds = (num+"").toCharArray();
        int[] buk = new int[10];
        for(int i=0;i<ds.length;i++){
            buk[ds[i]-'0'] = i;
        }
        for(int i=0;i<ds.length;i++){
            for(int k=9; k>(ds[i]-'0'); k--){
                if(buk[k] > i){
                    char tmp = ds[i];
                    ds[i] = ds[buk[k]];
                    ds[buk[k]] = tmp;
                    return Integer.parseInt(new String(ds));
                }
            }
        }
        
        return num;
    }

792. Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/description/
根据字母存索引，之后用2分搜索。

Map<String,Boolean> m = new HashMap<>();
    public int numMatchingSubseq(String S, String[] words) {
        int cnt = 0;
        List[] map = new List[26];
        for(int i=0;i<26;i++){
            map[i] = new ArrayList<Integer>();
        }
        int j = 0;
        for(char c : S.toCharArray()){
            map[c-'a'].add(j++);
        }
        for(String word : words){
            if(isS(map,word))cnt++;
        }
        return cnt;
    }
    private boolean isS(List[] map,String b){
        if(m.containsKey(b)) return m.get(b);
        int l = 0;
        for(int i=0;i<b.length();i++){
            char c = b.charAt(i);
            List<Integer> k = map[c-'a'];
            int index = Collections.binarySearch(k,l);
            if(index<0) index = -index-1;
            if(index == k.size()){
                m.put(b,false);
                return false;
            } 
            l = k.get(index)+1;
        
        }
        m.put(b,true);
        return true;
    }

775. Global and Local Inversions

https://leetcode.com/problems/global-and-local-inversions/description/
这道题就是不能存在跳一级的前面比后面大，所以就是前面最大的数，不能比N+2要大

public boolean isIdealPermutation(int[] A) {
        int l = A.length;
        int max = -1;
        for(int i=0;i<l-2;i++){
            max = Math.max(max,A[i]);
            if(max>A[i+2]) return false;
        }
        return true;
    }

835. Image Overlap

https://leetcode.com/problems/image-overlap/description/
暴力搜索也是不好写的。我们需要让i从-l+1,j也从-l+1.
然后就是各种枚举MIN,MAX在内层循环里。
因为K开始必须是0，我们又希望后面只要是1，所以后面就是min(l,i+l); 那么前面起点就是max(0,i)

public int largestOverlap(int[][] A, int[][] B) {
        int l = A.length;
        if(l == 0) return 0;
        int max = 0;
        for(int i=-l+1;i<l;i++){
            for(int j=-l+1;j<l;j++){
                int cnt = 0;
                for(int k=Math.max(0,i);k<Math.min(l,i+l);k++){
                    for(int m=Math.max(0,j);m<Math.min(l,j+l);m++){
                        if(B[k][m] == 1 && A[Math.abs(k-i)][Math.abs(m-j)] == B[k][m]){
                            cnt++;
                        }
                    }
                }
                max = Math.max(max,cnt);
            }
        }
        return max;
    }

75. Sort Colors

https://leetcode.com/problems/sort-colors/description/
三路快排的变种。
这里要注意的是J<=K。因为K的位置是未知的。

public void sortColors(int[] nums) {
        int i = 0, j = 0, k = nums.length-1;
        while(j<=k){
            if(nums[j]==1) j++;
            else if(nums[j]==0){
                swap(nums,i,j);
                i++;
                j++;
            }else{
                swap(nums,j,k);
                k--;
            }
        }
        
    }
    
    private void swap(int[] A,int i,int j){
        int tmp  =A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array/description/
归并排序变种

public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=m-1,j=n-1,k=m+n-1;i>=0||j>=0;){
            if(i==-1 || (j>=0 && nums2[j]>=nums1[i])) nums1[k--] = nums2[j--];
            else if(j==-1 || (i>=0 && nums1[i]>=nums2[j])) nums1[k--] = nums1[i--];  
        }
    }

215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/description/
快排变种。

public int findKthLargest(int[] nums, int k) {
        return quickselect(nums,0,nums.length-1,nums.length-k);
    }
    private int quickselect(int[] A,int s,int e, int k){
        int tar = A[s];
        int m = s;
        for(int i=s+1;i<=e;i++){
            if(A[i]<tar) swap(A,++m,i);
        }
        swap(A,s,m);
        if(m==k) return A[m];
        else if(m<k) return quickselect(A,m+1,e,k);
        return quickselect(A,s,m-1,k);
    }
    private void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

对撞指针

611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/description/
锁定大的边。

public int triangleNumber(int[] S) {
        if(S.length<3) return 0;
        Arrays.sort(S);
        int ans = 0;
        for(int i=S.length-1;i>=2;i--){
            int s = 0, e = i-1;
            int three = S[i];
            while(s<e){
                int one = S[s];
                int two = S[e];
                if(one+two>three){
                    ans+=(e-s);
                    e--;
                }else{
                    s++;
                }
            }
        }
        return ans;
    }

345. Reverse Vowels of a String

https://leetcode.com/problems/reverse-vowels-of-a-string/description/
对撞指针

public String reverseVowels(String s) {
        int st = 0, ed = s.length()-1;
        char[] cs = s.toCharArray();
        Set<Character> vow = new HashSet<>();
        vow.addAll(Arrays.asList(new Character[]{'a','e','i','o','u','A','E','I','O','U'}));
        
        //String vow = "aeiouAEIOU";
        while(st<ed){
            while(st<ed && !vow.contains(cs[st])) st++;
            while(st<ed && !vow.contains(cs[ed])) ed--;
            if(st>=ed) break;
            char tmp = cs[st];
            cs[st] = cs[ed];
            cs[ed] = tmp;
            st++;
            ed--;
        }
        return new String(cs);
    }

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/
对撞指针

public int maxArea(int[] height) {
        int st = 0, ed = height.length-1;
        int res = 0;
        while(st<ed){
            res = Math.max(res,(ed-st)*Math.min(height[st],height[ed]));
            if(height[st]<height[ed]) st++;
            else ed--;
        }
        return res;
    }

204. Count Primes

https://leetcode.com/problems/count-primes/description/
用筛选法做。所有素数的倍数都不是素数了。余下来的空隙就是素数

public int countPrimes(int n) {
        boolean[] p = new boolean[n];
        Arrays.fill(p,true);
        for(int i=2;i<n;i++){
            if(!p[i]) continue;
            for(int j=i+i;j<n;j+=i){
                p[j] = false;
            }
        }
        int res = 0;
        for(int i=2;i<n;i++){
            if(p[i]) res++;
        }
        return res;
    }