未命名分组 - 数组-数学 - 《数据结构 · Leetcode · SQL · 刷题笔记》

数组

二分搜索模板

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1, mid = 0;
    while (lo <= hi) {
        mid = lo + ((hi - lo) >> 1);
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

二分搜索的思路

剑指 Offer 11. 旋转数组的最小数字

class Solution {
    public int minArray(int[] numbers) {
        if(numbers.length<1||numbers==null)return 0;
        if(numbers.length==1)return numbers[0];
        int left = 0;
        int right = numbers.length-1;
        while (left<right){
            int mid = left+(right-left)/2;
            if(numbers[mid]>numbers[right]){
                left = mid+1;
            }else if(numbers[mid]<numbers[right]){
                right = mid;
            }else{
                right--;
            }
        }
        return numbers[left];
    }
}

287. 寻找重复数

思路1：
二分搜索的思路。因为这个数组里面一共有1-n的数字，然而有n+1的个数。所以每次计算 mid 统计小于等于 mid的数。在[left,mid]中有重复的数值，那么，统计出来的cnt会大于mid。这就知=知道了在哪个区间里的数字重复了。

 public int findDuplicate(int[] nums) {
        int left= 0;
        int right = nums.length;


        while (left<right){
            int cnt = 0;
            int mid = left+(right-left)/2;

            for(int i:nums){
                if(i<=mid){
                    cnt++;
                }
            }
            if(cnt>mid){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return left;


    }

思路2：快慢指针
快慢指针的话，因为里面存在一个环的结构，fast走两步，slow 走一步。遇到了之后，slow从头开始走，一次走一步，遇到的地方就是环的入口。那就是重复的数字。

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = nums[nums[0]];
        int slow = nums[0];
        while (fast!=slow){
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        slow = 0;
        while (fast!=slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;

    }
}

1095. 山脉数组中查找目标值

思路：这道题的话，可以理解成是一个二分的变化题。首先需要找到数组里面的最大值，然后在前面找目标，在后面找目标。

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int top = findTop(mountainArr);

        int res = 0;

        res = findInLeft(target,mountainArr,0,top);
        if(res ==-1){
            res = findInRight(target,mountainArr,top,mountainArr.length()-1);
        }
        return res;
    }
    private int findInRight(int target,MountainArray mountainArr, int left, int right){
        while(left<=right){
            int mid = left+(right-left)/2;

            if(mountainArr.get(mid) == target)return mid;
            if(mountainArr.get(mid)>target){
                left = mid+1;
            }else{
                right  = mid-1;
            }
        }
        return -1;
    }
    private int findInLeft(int target,MountainArray mountainArr,int left,int right){
        while(left<=right){
            int mid = left+(right-left)/2;
            if(mountainArr.get(mid) == target) return mid;
            if(mountainArr.get(mid)>target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;
    }

    private int findTop(MountainArray mountainArr){
        int left = 0;
        int right = mountainArr.length()-1;

        while(left<right){
            int mid = left+(right-left)/2;
            if(mountainArr.get(mid)>mountainArr.get(mid+1)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
}

甜姨的解法，使用万能的二分解法。

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // 先找到峰顶索引 peakIdx
        int lo = 0, hi = mountainArr.length() - 1;
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            int midVal = mountainArr.get(mid);

            if (midVal > mountainArr.get(mid - 1)) {
                lo = mid;
            } else {
                hi = mid;
            } 
        }
        int peakIdx = mountainArr.get(lo) > mountainArr.get(hi)? lo: hi;


        // 根据峰顶将山脉数组分为「升序数组」和「降序数组」两段，分别进行二分查找
        int idx = binSearch(mountainArr, 0, peakIdx, target, true);
        return idx != -1? idx: binSearch(mountainArr, peakIdx + 1, mountainArr.length() - 1, target, false);
    }

    private int binSearch(MountainArray mountainArr, int lo, int hi, int target, boolean asc) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int midVal = mountainArr.get(mid);

            if (midVal == target) {
                return mid;
            }
            if (midVal < target) {
                lo = asc? mid + 1: lo;
                hi = asc? hi: mid - 1;
            } else {
                hi = asc? mid - 1: hi;
                lo = asc? lo: mid + 1;
            }
        }
        return -1;
    }
}

33. 搜索旋转排序数组

思路：直接在数组上面做一个二分搜索。每次寻找使用mid切分，都会得到一个有序的数组。在这个有序的数组里面、必须要满足nums[left]<=target<=nums[right]。不然就缩小这个范围。

class Solution {
   public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1,mid = 0;
        if(nums.length<1)return -1;

        while (left<=right){
            mid = left+(right-left)/2;
            if(target ==nums[mid])return mid;
            if(nums[left]<=nums[mid]){// 左边有序
                if(target<=nums[mid]&&target>=nums[left]){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else{
                if(target>=nums[mid]&&target<=nums[right]){
                    left = mid+1;
                }else {
                    right = mid-1;
                }
            }

        }
        return -1;
    }
}

前缀和，后缀和思路

238. 除自身以外数组的乘积

思路：想到的方法就是，这个结果的我们可以这么看待。res = 这个数左边的积*这个数右边的积。左边的积我们可以使用前缀来表示。perfix[i]代第i个数前面的的积。suffix代表的是第i个数后面的积。最后把这两个称一下，就是最后的结果。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] perfix = new int[nums.length];
        int[] suffiix = new int[nums.length];
        int[] res = new int[nums.length];
        int per = 1;
        perfix[0] = 1;
        suffiix[nums.length-1] = 1;
        for(int i=1;i<nums.length;i++){
            per *=nums[i-1];
            perfix[i] = per;
        }
        int suf = 1;
        for(int i=nums.length-2;i>=0;i--){
            suf*=nums[i+1];
            suffiix[i] = suf;
        }
        for(int i=0;i<nums.length;i++){
            res[i] = suffiix[i]*perfix[i];
        }
        return res;

    }
}

优化，其实我们不需要直接开辟一个空间，不需要把这个数储存起来。直接在res 上面进行一个操作。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int k = 1;

        for(int i=0;i<nums.length;i++){
            res[i] = k;
            k*=nums[i];
        }
        k=1;
        for(int i=nums.length-1;i>=0;i--){
            res[i]*=k;
            k*=nums[i];
        }
        return res;

    }
}

双指针

524. 通过删除字母匹配到字典里最长单词

思路一：使用HashSet储存一下里面有啥字符，这个方法不行，HashSet会破环S里面的相对顺序。
思路二：使用双指针，对于每一个字符，如果一样的话就++，到底了就计算一下长度，更新答案

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String res = "";

        for (String ssr:d){
            for (int i=0,j=0;i<s.length()&&j<ssr.length();i++){
                if(s.charAt(i)==ssr.charAt(j))j++;

                if(j==ssr.length()){
                    if(ssr.length()>res.length()||(ssr.length()==res.length()&&res.compareTo(ssr)>0))res = ssr;
                }
            }
        }
        return res;
    }
}

167. 两数之和 II - 输入有序数组

左右两个指针往里面扫一下

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        int sum = 0;
        while (left<right){
            sum = numbers[left]+numbers[right];
            if(sum ==target){
               break;
            }else if(sum>target){
                right--;
            }else {
                left++;
            }
        }
        return new int[]{left+1,right+1};

    }
}

633. 平方数之和

right限制在平方根的附近，双指针扫一下，中间是停止。

class Solution {
    public boolean judgeSquareSum(int c) {
        int left=0;
        int right = (int)Math.sqrt(c)+1;
        int num = 0;
        while (left<=right){
            num = left*left+right*right;
            if(num == c){
                return true;
            }else if(num>c){
                right--;
            }else {
                left++;
            }
        }
        return false;
    }
}

345. 反转字符串中的元音字母

思路：
拿元音做一个哈希set，到时候都查一下。双指针，指向两侧，不是元音的话就跳过。

class Solution {
    public String reverseVowels(String s) {
        HashSet<Character> set = new HashSet<>();
        char[] charArray = s.toCharArray();
        String vowels = "aeiouAEIOU";
        for (char c:vowels.toCharArray()){
            set.add(c);
        }

        int left = 0;
        int right = s.length()-1;

        while (left<right){
            if(!set.contains(charArray[left])){
                left++;
                continue;
            }
            if(!set.contains(charArray[right])){
                right--;
                continue;
            }

            char tmp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = tmp;
            left++;
            right--;
        }
        return String.valueOf(charArray);
    }
}

9. 回文数

思路：最简单的方法就是吧这个数字变成一个字符串数组，之后两个指针从前往后的遍历一下。但是这样会消耗比较多的内存。

    public boolean isPalindrome(int x) {
        if(x<0)return false;
        String s = String.valueOf(x);
        char[] charArray = s.toCharArray();
        for (int i=0;i<charArray.length;i++){
            if(charArray[i]!=charArray[charArray.length-i-1]){
                return false;
            }
        }
        return true;


    }

第二种方法就是我们反转一半的数字，看一下后面的一般和前面的一般是不是一样的。

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0 || x%10==0&&x!=0){
            return false;
        }
        int reverseNum = 0;
        while (reverseNum<x){
            reverseNum = reverseNum*10+x%10;
            x/=10;
        }
        return reverseNum==x || x == reverseNum/10;
    }
}

125. 验证回文串

也是回文串的一种，那就是使用双指针的方式了。左右两边往里面扫，去掉一些没用的符号。转换大小写。
转换大写的方法

ch& 0xDF; 大写
ch| 0x20; 小写

完整如下：

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        while (left<=right){
            if(!Character.isLetterOrDigit(s.charAt(left))){
                left++;
                continue;
            }
            if(!Character.isLetterOrDigit(s.charAt(right))){
                right--;
                continue;
            }

            if((s.charAt(left)&0xDF)== (s.charAt(right)&0xDF)){
                left++;
                right--;
            }else {
                return false;
            }

        }
        return true;
    }
}

1370. 上升下降字符串

思路：把里面的字母出现的次数统计一下，从投遍历一下，冲尾巴遍历一下。得到结果

class Solution {
    public String sortString(String s) {
        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)-'a']++;
        }
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        while (n>0){
            for (int i = 0; i < count.length; i++) {
                if(count[i]>0){
                    sb.append((char)(i+'a'));
                    count[i]--;
                    n--;
                }
            }
            for (int i = 25; i >= 0; i--) {
                if(count[i]>0){
                    sb.append((char)(i+'a'));
                    count[i]--;
                    n--;
                }
            }
        }
        return sb.toString();
    }
}

31. 下一个排列

求的是下一个比他大的数值，这个数字必须是按序排好的下一位。

思路如下：
从后往前寻找不是升序的数字位置 p，之后再次从后面开始往前去寻找第一个比这个数要大的数 q。将他们做交换。之后将p后面的数字做一个排序。

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length-1;
        int p = len-1;

        while (p>=0 && nums[p]>=nums[p+1]){
            p--;
        }
        if(p >= 0){
            int q = len;

            while (q>=0 &&nums[q]<=nums[p]){
                q--;
            }
            swap(nums,p,q);
        }
        Arrays.sort(nums,p+1,len+1);
    }
        private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

349. 两个数组的交集

使用两个Set做一下去重的事情，记录到里面的去就好了。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();

        for (int i:nums1){
            set.add(i);
        }

        for (int i:nums2){
            if(set.contains(i)){
                resSet.add(i);
            }
        }

        int[] res = new int[resSet.size()];

        int index = 0;

        for (int i:resSet){
            res[index++] = i;
        }

        return res;
    }
}

941. 有效的山脉数组

这道题就是判断一下这个数组是不是一个山脉数组，山脉数组必须有一个顶点，两边的数需要比里面的小。
思路如下：
首先找到里面最大的的那个数以及他的下标，作为一个分割线，前面的的数需要是升序的，后面的数需要是逆序的。在这个里面做一下判断。

class Solution {
    public boolean validMountainArray(int[] A) {
        int maxIndex = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            if(A[i]>max){
                max = A[i];
                maxIndex = i;
            }
        }
        if(maxIndex == 0 || maxIndex ==A.length-1){
            return false;
        }
        for (int i = 0; i < maxIndex; i++) {
            if(A[i]>=A[i+1]){
                return false;
            }
        }
        for (int i = maxIndex; i < A.length-1; i++) {
            if(A[i]<=A[i+1]){
                return false;
            }
        }
        return true;
    }
}

845. 数组中的最长山脉

思路：
主要需要两个数组来辅助，left[i] 代表A[i]的左边有几个连续的数比他小。同理需要一个right的数组来记录。这个时候对于每一个A[i]里面的数据，只要 left 和 right的数值不是0 就计算一下里面的数值。

class Solution {
    public int longestMountain(int[] A) {
        int len = A.length;
        if(len == 0){
            return 0;
        }

        int[] left = new int[A.length];
        int[] right = new int[A.length];

        for (int i = 1; i < A.length; i++) {
            left[i] = A[i-1]<A[i]?left[i-1]+1:0;
        }
        for (int i = len-2; i >=0 ; i--) {
            right[i] = A[i+1]<A[i]?right[i+1]+1:0;
        }
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            if(left[i]>0 && right[i]>0){
                res = Math.max(res,right[i]+left[i]+1);
            }
        }
        return res;

    }
}

922. 按奇偶排序数组 II

很简单，就是两个指针，一个是指向奇数的位置的，一个指向偶数的位置。

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int[] res = new int[A.length];

        int i = 0;
        int j = 1;

        for (int k = 0; k < A.length; k++) {
            if((A[k]&1)==1){
                res[j] = A[k];
                j+=2;
            }else {
                res[i] = A[k];
                i+=2;
            }
        }
        return res;
    }
}

415. 字符串相加

使用两个指针，都是从后面往前面扫描，假如一个扫完了，就补充为0，存入StringBuilder 里面。最后导出。

class Solution {
    public String addStrings(String num1, String num2) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = num1.length()-1,j = num2.length()-1; i >= 0||j >= 0 ; i--,j--) {
            int n1 = i >=0 ? num1.charAt(i)-'0':0;
            int n2 = j >=0 ? num2.charAt(j) -'0':0;
            int sum = n1+n2+carry;
            carry = sum/10;
            sum %= 10;
            sb.append(String.valueOf(sum));
        }
        if(carry!=0){
            sb.append(carry);
        }
        return sb.reverse().toString();
    }
}

43. 字符串相乘

其实就是模拟竖式，对于num2的每一个数值，都拿去乘num1。后面的累加其实就是415这道题的解法。

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        String res = "0";

        for (int i = num2.length()-1; i >=0 ; i--) {
            int carry = 0;
            StringBuilder sb = new StringBuilder();

            for (int j = 0; j < num2.length() - 1 - i; j++) {
                sb.append(0);
            }
            int n2 = num2.charAt(i)-'0';

            for (int j = num1.length()-1; j >=0||carry!=0 ; j--) {
                int n1=j<0?0:num1.charAt(j)-'0';
                int product = (n1*n2+carry)%10;
                sb.append(product);
                carry = (n1*n2+carry)/10;
            }
            res = addStrings(res,sb.reverse().toString());
        }
        return res;
    }
    public String addStrings(String num1, String num2) {
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        for (int i = num1.length()-1,j=num2.length()-1; i >=0||j>=0; i--,j--) {
            int n1 = i>=0?num1.charAt(i)-'0':0;
            int n2 = j>=0?num2.charAt(j)-'0':0;

            int sum = n1+n2+carry;
            carry = sum/10;
            sum%=10;
            sb.append(sum);
        }
        if(carry==1){
            sb.append(carry);
        }
        return sb.reverse().toString();
    }
}

80. 删除排序数组中的重复项 II

思路： index 代表的是下一个需要填充的位置，然后遍历一下里面的数组。遇到这个数比11前两个数还要大的话，那就进行一个填充。

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;

        for (int num:nums){
            if(index<2 || nums[index-2]<num){
                nums[index++] = num;
            }
        }
        return index;
    }
}

35. 搜索插入位置

就是搜索一下，需要注意的就是最后一个位置的地方，

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target){
                return i;
            }else if(nums[i]>target){
                return i;
            }

            if(i == nums.length-1){
                return i+1;
            }
        }
        return -1;
    }
}

75. 颜色分类

这是快速排序里面的 patition 过程。把一个数组分为三个部分，第一个部分是小于1的数字，第二部分是等于1的部分，第三部分是2 的数。其实可以使用双指针分别代表各个部分，在中间进行一个遍历。进行交换。

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int zero = 0;
        int two = len;
        if(nums.length<2){
            return;
        }
        int i = 0;
        while ( i<two){
            if(nums[i]  ==0){
                swap(nums,zero,i);
                zero++;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else {
                two--;
                swap(nums,i,two);

            }
        }
    }
    private void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

5453. 所有蚂蚁掉下来前的最后一刻

解题思路：
其实我们可以认为这个蚂蚁在遇到的时候他是穿过去了。因为其实这个碰头没有什么意义。你可以认为是这两个蚂蚁进行了交换。也可以认为是这两个之间是透明的，直接就过去了。

class Solution {
    public int getLastMoment(int n, int[] left, int[] right) {
        int leftMax = 0;
        int rightMax = 0;
        for (int i:left){
            leftMax = Math.max(leftMax,i);
        }
        for(int i:right){
            rightMax = Math.max(rightMax,n-i);
        }
        return Math.max(rightMax,leftMax);
    }
}

209. 长度最小的子数组

第一个想到的方法就是使用使用滑动窗口的思路去做。题目里面的连续子数组提示使用滑动窗口的思路去做。使用两个指针指一下，扩展的时候加入sum。 sum大于s的时候就开始计算下标的变化。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length<1)return 0;
        int left = 0;
        int right = 0;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        while (right<nums.length){
            int c = nums[right++];
            sum += c;
            while (sum>=s){
                res = Math.min(right-left,res);
                int d = nums[left++];
                sum -= d;
            }

        }
        return res==Integer.MAX_VALUE?0:res;
    }
}

41. 缺失的第一个正数

最简单的思路是使用一个哈希表来存储一下数据。然后我们从1开始查找，哪个是哈希表里面没有的，没有的那个数就是我们需要的答案。
思路2：
数组的长度是N，所以这个数肯定在 0-N+1的范围内。可以设计一个原地哈希的算法。把num映射到num-1的下标位置上去。映射完成之后，从头开始遍历，发现不再自己的位置上的数，那就说明是我们需要的答案。

李伟伟的答案：https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i]>0&&nums[i]<nums.length&& nums[nums[i]-1]!=nums[i]){ // nums[i]<nums.length 因为答案就在 1 -N+1的范围内。 大于这个的数其实和负数一样
                // 需要舍去的。
                // 而nums[nums[i]-1]!=nums[i] 是对于重复数值的处理。
                swap(nums,i,nums[i]-1);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return nums.length+1;
    }

    private void swap(int[] nums, int i, int i1) {
        int tmp = nums[i];
        nums[i] = nums[i1];
        nums[i1] = tmp;
    }
}

67. 二进制求和

思路：二进制求和，首先把字符串进行一个补全，使得长度为一样。使用一个指针从后面开始往前面扫描。记录一下进位。

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        while(a.length()>b.length()){
            b = "0" + b;
        }
        while (a.length()<b.length()){
            a = "0" + a;
        }
        for (int i=a.length()-1;i>=0;i--){
            int num = a.charAt(i)-'0'+b.charAt(i)-'0'+carry;
            carry = num>1?1:0;
            num = num>1?num-2:num;
            sb.insert(0,num);
        }
        if(carry!=0){
            sb.insert(0,1);
        }
        return sb.toString();        
    }
}

剑指 Offer 45. 把数组排成最小的数

思路，其实这道题的嗯目的是让你制定一个排序的策略。对于给定的数字，需要转换成str，因为存在转换之后int溢出的问题。那如何定义str的排序呢，其实就是 x+y 和y+x 的比较，str数组里面的比较。

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i=0;i<nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for (String s: strs){
            res.append(s);
        }
        return res.toString();
    }
}

1014. 最佳观光组合

最简单的方法是两层的循环来计算一下，但是这样是O（n2）的复杂度。可以一次遍历来获得，因为 num[i]+i 这个数字其实是固定的，我们只需要计算一下num[j]-j的最大值。在遍历的同时更新一下num[i]+i 的结果。

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        int preCount = A[0]+0;
        int max = 0;
        for (int j=1;j<A.length;j++){
            max = Math.max(max,preCount+A[j]-j);
            preCount = Math.max(preCount,A[j]+j);
        }
        return max;
    }
}

面试题39. 数组中出现次数超过一半的数字

遍历一下里面的数组，我们假设这个数就是res，计算他的频率，一旦频率=0，那就换一个。因为这个数超过一半的次数所以一定会可以把所有的数抵消了。

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0,votes = 0;
        for (int num:nums){
            if(votes==0) x = num;
            votes += num ==x?1:-1;
        }
        return x;
    }
}

1300. 转变数组后最接近目标值的数组和

思路：其实我也不大会- - 截取一下别人的好了

class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int len = arr.length;
        int cursum = 0;
        for (int i=0;i<len;i++){
            int curAve = (target-cursum)/(len-i);
            if(curAve<=arr[i]){
                double curAveDou = (target*1.0-cursum)/(len-i);
                if(curAveDou-curAve<=0.5){
                    return curAve;
                }else {
                    return curAve+1;
                }
            }
            cursum+=arr[i];
        }
        return arr[len-1];

    }
}

680. 验证回文字符串 Ⅱ

思路：
双指针，这道题可以有一个字母不一样。假如遇到了这种情况，左边进一个试试，右边也进去一位试试。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;

        while(left<right){
            if(s.charAt(left)!= s.charAt(right)){
                return validPalindrome(s,left+1,right)||validPalindrome(s,left,right-1);
            }

            left++;
            right--;
        }
        return true;

    }
    private boolean validPalindrome(String s,int left, int right){
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

思路2：
dfs的思想，用一个标志位来记录一下有没有删除过字符。

class Solution {
    public boolean validPalindrome(String s) {
        return dfs(s,0,s.length()-1,true);

    }

    private boolean dfs(String s, int left, int right,boolean use) {
        if(left>=right){
            return true;
        }
        if(s.charAt(left)==s.charAt(right)){
            return dfs(s,left+1,right-1,use);
        }else {
            if(!use)return false;
            return dfs(s,left+1,right,false)||dfs(s,left,right-1,false);
        }
    }
}

1431. 拥有最多糖果的孩子

这道题比较简单，直接模拟就可以了。首先找到孩子里面糖果最多的那位。之后用可以加的糖果对每一个小朋友加一下。如果比max大的话，那就把true加入到结果中去。

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int max = 0;
        List<Boolean> res = new ArrayList<>();
        for(int i:candies){
            max = Math.max(max,i);
        }
        for(int i:candies){
            if(i+extraCandies>=max){
                res.add(true);
            }else{
                res.add(false);
            }
        }
        return res;

    }
}

5. 最长回文子串

两边扩展的思路。
对于每一个回文串，我们可以认为是中间部分是一样的，两边分别对应的一个情况。所以使用两个指针对着指向。先把重复的给去除掉了先。之后再处理对应的。

class Solution {
    public String longestPalindrome(String s) {
        if(s ==null|| s.length()<1)return "";
        char[] str = s.toCharArray();
        int[] res = new int[2];
        for(int i=0;i<str.length;i++){
          i =   findTheLongest(str,i,res);
        }

        return s.substring(res[0],res[1]+1);

    }

    private int findTheLongest(char[] str, int low, int[] res) {
        int high = low;
//        high开始往左边扩展，回文串我们认为是一个中间字符一样的，两边的字符一一对称。
        while (high<str.length-1&&str[high+1]==str[low]){
            high++;
        }
        int ans = high;
//        此刻，low 和high 站在相同字符的两侧。接下来需要往两边遍历一下。
        while (low>0&&high<str.length-1&&str[low-1] == str[high+1]){
            high ++;
            low --;
        }
        if(high-low>res[1]-res[0]){
            res[0] = low;
            res[1] = high;
        }
        return ans;
    }
}

面试题64. 求1+2+…+n

思路：
由于题目不能使用乘除和循环语句。所以想到的一个方法是递归

if(n==1){
    return n;
}
return n+sum(n-1);

由于不能使用if的原因，所以把想到了短路与的情况、
a&&b 假如a是false的话，那就不会执行第二个表达式。
具体实现如下：

class Solution {
    public int sumNums(int n) {
        boolean s = n>0 && (n+=sumNums(n-1))>0;
        return n;  
    }
}

50. Pow(x, n)

思路1：
使用暴力的方法来，每次循环*一个x。
思路2：
使用快速幂算法来进行一个二分的累积乘法。一定要注意的是，题目里的n是32位有符号的。所以可能会int类型的溢出。
对n负的最大值直接取反，会造成溢出。

yuqtquanclass Solution {
    public double myPow(double x, int n) {
        long N = n;


        return n<0?1.0/ipow(x,-N):ipow(x,N);
    }
    private double ipow(double x, long n){

        double res = 1.0;
        double tmp_x = x;
        while (n>0){
            if((n&1)==1){
                res*=tmp_x;
            }
            tmp_x *= tmp_x;
            n>>=1;
        }
        return res;
    }
}

202. 快乐数

两种方法，第一种是诗一个哈希表来记录一下里面的数据。发现有重复的话，那我就退出。

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> res = new HashSet<>();
        int tmp = n;
        while (tmp !=1){
            tmp = culNum(tmp);
            if(res.contains(tmp)){
                return false;
            }
            res.add(tmp);
            System.out.println(tmp);
        }
        return true;
    }

    private int culNum(int n) {
        int tmp = 0;

        while (n>0){
            int x = n%10;
            tmp += x*x;
            n/=10;
        }
        return tmp;
    }
}

第二种的话，我们可以把这个看作是一个链表的环的问题，链表的环问题，最贱的做法的使用一个快慢指针来做。

class Solution {
public boolean isHappy(int n) {
        int slow = n;
        int fast = culNum(n);
        while (slow !=fast){
            slow =culNum(slow);
            fast = culNum(fast);
            fast = culNum(fast);
        }
        if(fast == 1){
            return true;
        }
        return  false;

    }

    private int culNum(int n) {
        int res = 0;
        while (n>0){
            int x = n%10;
            res+= x*x;
            n/=10;
        }
        return res;
    }
}

面试题51. 数组中的逆序对

归并和分治的思想。把数组越分越小的时候，直到只有两个时候，做一个merge的行为。在这里计算一下逆序对。

class Solution {
public int reversePairs(int[] nums) {
        int len = nums.length;
        if(len<2)return 0;

        int[] copy = new int[len];
        for(int i=0;i<len;i++){
            copy[i] = nums[i];
        }
        int[] tmp = new int[len];
        return reversePairs(0,len-1,copy,tmp);
    }

    private int reversePairs(int left, int right, int[] copy, int[] tmp) {
        if(left ==right){
            return 0;
        }
        int mid = left+(right-left)/2;
        int leftPoints = reversePairs(left,mid,copy,tmp);
        int rightPoints = reversePairs(mid+1,right,copy,tmp);

        int crossPairs = mergeAndCoubt(copy,left,mid,right,tmp);
        return leftPoints+rightPoints+crossPairs;


    }

    private int mergeAndCoubt(int[] nums, int left, int mid, int right, int[] tmp) {
        for(int i=left;i<=right;i++){
            tmp[i] = nums[i];
        }
        int i = left;
        int j = mid+1;
        int count = 0;
        for(int k = left;k<=right;k++){
            if(i==mid+1){
                nums[k] = tmp[j];
                j++;
            }
            else if(j==right+1){
                nums[k] = tmp[i];
                i++;
            }

            else if(tmp[i]<=tmp[j]){
                nums[k] = tmp[i];
                i++;
            }else {
                nums[k] = tmp[j];
                j++;
                count+=(mid-i+1);
            }
        }
        return count;
    }
}

1248. 统计「优美子数组」

这道题首先就是需要找到一个k个数字是奇数。然后往两边进行一个扩散，计算一下边上有戢偶数。乘一下。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int left = 0, right = 0, oddCnt = 0, res = 0;
        while (right<nums.length){
            if((nums[right++]&1)==1){
                oddCnt++;
            }
            if(oddCnt== k){
                int tmp = right;
                while (right<nums.length&&(nums[right]&1)==0){
                    right++;
                }
                int rightEnvrnCnt = right-tmp;
                int leftEventCut = 0;
                while ((nums[left]&1)==0){
                    leftEventCut++;
                    left++;
                }
                res+=(leftEventCut+1)*(rightEnvrnCnt+1);
                left++;
                oddCnt--;
            }
        }
        return res;
    }
}

242. 有效的字母异位词

思路：主要就是想让你判断一下这个字符串里面的字符出现的频率是不是一样的。
思路1：直接对数组进行一个排序，对比一下是不是一样的。
思路2：使用一个哈希表来记录一下里面的频率。第二个字符就相应的减去。最后判断一下是不是空的。
思路3：使用一个26的数组来记录一下里面出现的频率。

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1= t.toCharArray();

        Arrays.sort(s1);
        Arrays.sort(t1);
        return Arrays.equals(s1,t1);

    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char tmp = s.charAt(i);
            if(!map.containsKey(tmp)){
                map.put(tmp,1);
            }else{
                map.put(tmp,map.get(tmp)+1);
            }
        }
        for(int i=0;i<t.length();i++){
            char tmp = t.charAt(i);
            if(map.containsKey(tmp)){
                int count = map.get(tmp);
                if(count ==1){
                    map.remove(tmp);
                }else{
                    map.put(tmp,map.get(tmp)-1);
                }

            }else {
                return false;
            }
        }
        return map.isEmpty();

    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count = new int[26];
        if(s.length()!=t.length()){
            return false;
        }

        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-'a']++;
            count[t.charAt(i)-'a']--;
        }
        for(int i:count){
            if(i!=0)return false;

        }
        return true;

    }
}

49. 字母异位词分组

思路：使用一个哈希表来记录一下里面的异味词。如何来构造这样的一个key呢？
我们可以取出里面的一个str，使用sort来排序一下，之后变成一个字符串来作为key。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs.length==0) return  new ArrayList<>();
        Map<String,List> map = new HashMap<>();

        for(String s:strs){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            if(!map.containsKey(key)){
                map.put(key,new ArrayList());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());

    }


}

面试题 01.07. 旋转矩阵

把数组旋转，我们要做的事情是首先做一个对角线的旋转（转置)，再对每一行做一个旋转。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        int count = matrix.length>>1;
        for(int i =0;i<n;i++){
            for(int j=0;j<count;j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n-j-1];
                matrix[i][n-j-1] = tmp;
            }
        }

    }
}

88. 合并两个有序数组

思路：从头开始往后遍历，一个一个放到正确的位置上

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int s1end = nums1.length-1;
        int s1index = m-1;
        int s2index = n-1;

        while(s1index>=0&&s2index>=0){
            if(nums1[s1index]>nums2[s2index]){
                nums1[s1end] = nums1[s1index];
                s1index--;
                s1end--;
            }else{
                nums1[s1end] = nums2[s2index];
                s2index--;
                s1end--;
            }
        }

        while(s2index>=0){
            nums1[s2index] = nums2[s2index];
            s2index--;
        }



    }
}

11. 盛最多水的容器

思路：使用头尾指针进行逼近。计算area，如果head大的话end向里缩进。

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for(int i=0,j = height.length-1;i<j;){
            int minHeight = height[i]>height[j]?height[j--]:height[i++];
            int area = (j-i+1)*minHeight;
            max = Math.max(area,max);
        }
        return max;
    }
}

1. 两数之和

使用一个哈希表来记录一下数组的数据，假如target-num不在里面的话，那就把这个数放入到map里面去

class Solution {
       public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> res = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int tmp = target-nums[i];
            if(res.containsKey(tmp)){
                return new int[]{i,res.get(tmp)};
            }
            res.put(nums[i],i);
        }


        throw new IllegalArgumentException("No two sum solution");
    }
}

15. 三数之和

思路：主要的思路就是排序加上双指针的思路。固定住一个值之后，两个指针从头尾依次遍历。有几个点需要注意：

固定的数大于0 则break
跳过相同的数据。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0)break;
            if(i>0&&nums[i] == nums[i-1]) continue;
            int head = i+1;
            int end = nums.length-1;
            while (head<end){
                int sum = nums[i]+nums[head]+nums[end];
                if(sum == 0){
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[head],nums[end])));
                    while (head<end&&nums[head] == nums[++head]);
                    while (head<end && nums[end] ==nums[--end]);
                }
                else if(sum<0){
                    while (head<end&&nums[head] == nums[++head]);
                }else {
                    while (head<end && nums[end] ==nums[--end]);
                }
            }
        }
        return res;

    }
}

26. 删除排序数组中的重复项

g用一个外面的j来进行标记

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null) return -1;
        int j = 1;
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i-1] != nums[i]){
                nums[j] = nums[i];
                    j++;
            }
        }
        return j;

    }
}

42. 接雨水

其实和单调栈的题目有一点像。先说一下包里的解法:
对于每一个位置i，我们都对他的两边进行遍历。这个格子能放的水的量就是max（leftMax，rightMax）-hwight[i]的数值。对每一个格子进行这样的判断。

所以我们看到，这道题的关键就是在找左右的最大值。和自己做一个比较。
双指针的方法：设立左右两个最大值，进行一个遍历

class Solution {
    public int trap(int[] height) {

        if(height.length<1||height==null) return 0;
        int left = 0;
        int right = height.length-1;

        int leftMax = height[0];
        int rightMax = height[right];
        int res=0;
        while(left<=right){
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);

            if(leftMax<rightMax){
                res+= leftMax-height[left];
                left++;
            }else{
                res+= rightMax-height[right];
                right--;
            }

        }
        return res;
    }
}

1013-将数组分成和相等的三个部分

思路：让我们将这个数组分成三个和相等不同的部分。那我们就知道，和一定能被3除。每一部分的sum就是sum/3。我们使用前后两次遍历，head遍历到sum的时候break，位置head。 end从后面开始遍历，计算sum，break记录end的位置。最后，只要head>end-1（因为中间至少需要一个）则return true；

class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int totalSum = 0;

        for(int i=0;i<A.length;i++){
            totalSum+=A[i];
        }
        if(totalSum%3!=0){
            return false;//必须要能够被3除
        }
        int part = totalSum/3;


        int head = 0;
        int sum=0;//从前面开始遍历
        for(int i=0;i<A.length;i++){
            sum+=A[i];
            if(sum == part){
                head = i;
                sum = 0;
                break;
            }
        }
        int end = 0;//从后面开始遍历
        for(int i=A.length-1;i>0;i--){
            sum+=A[i];
            if(sum ==part){
                end = i;
                break;
            }
        }
        if(head<end-1)return true;
        else return false;

    }
}

优化吧两个循环放在一起

class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int totalSum = 0;

        for(int i=0;i<A.length;i++){
            totalSum+=A[i];
        }
        if(totalSum%3!=0){
            return false;
        }
        int part = totalSum/3;


        int left = 0;
        int leftSum=A[left];
        int right = A.length-1;
        int rightSum = A[right];

        while(right>left+1){
            if(leftSum == part&& rightSum ==part){
                return true;
            }
            if(leftSum!=part){
                leftSum+=A[++left];
            }
            if(rightSum!=part){
                rightSum+=A[--right];
            }
        }

        return false;


    }
}

169-多数元素

思路1：
因为要找到大于n/2的数，所以吧数组排序一下肯定在中间的位置。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length>>1];
    }
}

思路2：
使用摩尔投票法。把第一个设置成结果，遇到相同的就count+1遇到不同的就-1，直到count=0，就更换一下候选人。因为这个数的出现次数大于n/2所以一直抵消下去，也依然是正数。

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count =1;

        for(int i=0;i<nums.length;i++){
            if(res == nums[i]){
                count++;
            }else{
                count--;
                if(count == 0){
                    res = nums[i];
                    count =1;
                }
            }
        }
        return res;
    }
}

189. 旋转数组

先全体反转，反转前k个，反转后n-k个

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        swap(0,nums.length-1,nums);
        swap(0,k-1,nums);
        swap(k,nums.length-1,nums);

    }
    private void swap(int i,int j,int[] nums){
        while(i<j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            j--;
            i++;
        }

    }
}

283. 移动零

使用另外一个j来表示实际上非零的位置在哪。i只管遍历，遇到0的时候将0移动到后面

class Solution {
    public void moveZeroes(int[] nums) {
        // j非零的位置
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[j] = nums[i];
                if(j!=i){
                    nums[i] = 0;
                }
                j++;
            }
        }
    }
}

289. 生命游戏

这道题的主要问题在于如何在数组的上面做一个修改。可以吧数值作为一个二进制进行储存。比如说，现在是1以后是0 可以设置为0b01.最后我们可以对其进行一个移位操作。

class Solution {
    public void gameOfLife(int[][] board) {
        int[] dx = new int[]{1,-1,0,0,-1,-1,1,1};
        int[] dy = new int[]{0,0,1,-1,-1,1,-1,1};

        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                int nearCount = 0;
                for(int g=0;g<dx.length;g++){
                    int x = i+dx[g];
                    int y = j+dy[g];
                    if(x<0||x>=board.length||y<0||y>=board[0].length){
                        continue;
                    }
                    nearCount += board[x][y]&1;
                }
                if((board[i][j] & 1) > 0){
                    if(nearCount>=2&&nearCount<=3){
                        board[i][j] = 0b11;
                    }else if(nearCount>3){
                        board[i][j] = 0b01;
                    }
                }else{
                    if(nearCount==3){
                        board[i][j] = 0b10;
                    }
                }
            }
        }

        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                board[i][j]>>=1;
            }
        }
    }
}

1160-拼写单词

思路：
这里有一个套路，字符串的题目设定了只包含小写的（大写）字母。可以使用26的数组来代替哈希表的实现。
统计一下每个字符串里面字符出现的个数，做一个比较。每个字符出现的次数都需要比字母表要小才行。

class Solution {
public int countCharacters(String[] words, String chars) {
        int[] char_count = count(chars);
        int res = 0;
        for(String s:words){
            int[] s_count = count(s);
            if(compare(s_count,char_count)){
                res+=s.length();
            }

        }
        return res;

    }
    private int[] count(String s){
        int[] count = new int[26];
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-'a']++;
        }
        return count;
    }
    private boolean compare(int[] word,int[] char_count){
        for(int i=0;i<26;i++){
            if(word[i]>char_count[i]){
                return false;
            }
        }
        return true;

    }
}

945. 使数组唯一的最小增量

思路：
使用计数排序的思想来做，题目中提到数据量的问题，我们可以创建一个40001大小的数组，遍历一下里面每个数值出现的次数。获得最大值。
遍历的时候，如果遇到的数次数》1，我们就将num-1 把这个值直接加到后面的位置上去。res+=num-1
这样可以两次遍历就得到结果。

class Solution {
    public int minIncrementForUnique(int[] A) {
        if(A.length<1){
            return 0;
        }
        int[] nums = new int[400001];

        int max = -1;
        for(int num:A){
            nums[num]++;
            max = Math.max(num,max);
        }
        int res = 0;
        for(int i=0;i<max;i++){
            if(nums[i]>1){
                int d = nums[i]-1;
                res+=d;
                nums[i+1]+=d;
            }
        }

        if(nums[max]>1){
            int d = nums[max]-1;
            res+=(1+d)*d/2;
        }
        return res;

    }
}

999. 车的可用捕获量

按照题目的要求做，注意一个是使用一个方向数组来代表上下左右。

class Solution {
   public int numRookCaptures(char[][] board) {
        int res = 0;
        int [][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                if(board[i][j] =='R'){
                    for(int[] direction:directions){
                        if(burnout(i,j,direction,board)){
                            res++;
                        }
                    }
                    return res;
                }

            }
        }
        return res;

    }

    private boolean burnout(int i, int j, int[] direction, char[][] board) {
        int x = i;
        int y = j;
        while (isArea(x,y)){
            if(board[x][y] =='B')break;
            if(board[x][y] == 'p')return true;
            x+=direction[0];
            y+=direction[1];
        }
        return false;
    }

    private boolean isArea(int i, int j) {
        if(i<8&&i>=0&&j<8&&j>=0){
            return true;
        }
        return false;
    }
}
// 1. loop get rock
// 2. 判断上下左右的位置上是否有p

数学

异或-只出现一次的数字系列

136. 只出现一次的数字

思路：异或的操作。a^a=0;
a^0= a ;
(a^b)^b = a^(b^b) = a;
所以我们可以拿一个数不断地异或过去
xor^=i 因为相同的数据会异或成0；数组里面只有一个数字是不重复的。所以这个结果就是我们要找的数。

class Solution {
    public int singleNumber(int[] nums) {
        int target = 0;

        for(int i:nums){
            target^=i;
        }
        return target;

    }
}

137. 只出现一次的数字 II

这道题的意思是说，这个数组里面有一个数只出现了一次，其他的出现了3次。如何去判断一下这个数。按照位运算来思考。假如这个数的某个位上有数，那么在整个数组中，应该是3的倍数。如果不是的话，说明哪个只有一个的数也在这个位上是1,。所以可以用32位来进行一个轮流的计数。如果这个位置上有的话，就拿结果去|=这个结果。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i=0;i<32;i++){
            int cnt = 0;
            int bit = 1<<i;

            for(int num:nums){
                if((num&bit)!=0){
                    cnt++;
                }
            }
            if(cnt%3!=0){
                res|=bit;
            }
        }
        return res;

    }
}

260. 只出现一次的数字 III

这道题需要满足的这个数组里面都是出现两次。只有两个数字出现了一次。要找到这两个数字。
按照以前的思路，这需要对这个数组进行一个异或的操作。但是里面有两个数字。所以我们的想法是把这个数组分成两部分。

相同的数组在一个里面。
只出现一次的数字要在不同的分区里面。

对这个数组进行一个遍历的异或操作我们可以得到什么？一个不为0的数据。我们遍历一下这个数。找到里面二进制为一的那一位。以哪个作为我们分组的依据。这样就可以满足我们需要的两个条件了。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        int a = 0;
        int b = 0;

        for(int num:nums){
            res^=num;
        }
        int h = 1;
       while ((res&h)==0){
           h<<=1;
       }
       for(int num:nums){
           if((num&h)==0){
               a^=num;
           }else {
               b^=num;
           }
       }
       return new int[]{a,b};

    }
}

888. 公平的糖果交换

剑指 Offer 65. 不用加减乘除做加法

思路：

利用或和与的方式可以得到这个结果

class Solution {
    public int add(int a, int b) {
        if(b == 0){
            return a;
        }
        return add(a^b,(a&b)<<1);
    }
}

面试题 16.11. 跳水板

其实这是一道数学题。我们需要求出可能拼出来的数字。

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        int[] res = new int[k+1];
        if(k ==0) return new int[0];
        if(shorter == longer){
            return new int[]{shorter*k};
        }
        for (int i = 0; i < k+1; i++) {
            res[i] = shorter*k+(longer-shorter)*i;
        }
        return res;
    }
}

69. x 的平方根

其实和二分是差不多的。里面一个点需要注意的是integer的上限是2147483647，这个数开根号的结果是46340。
把这个设为max的上限。一旦超出了这个范围，那就把这个设为初始值。再里面寻找。这个数需要平方比x小，但是+1 的话就需要比他大。

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int max = (int)Math.sqrt(Integer.MAX_VALUE);

        while(left<=right){
            int mid = left+(right-left)/2;
            if(mid>max){
                mid = max;
            }
            int tmp = mid*mid;
            if(tmp ==x){
                return mid;
            }
            if(tmp<x&&(mid+1)>x/(mid+1)){
                return mid;
            }

            if(x<mid*mid){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;

    }
}

66. 加一

思路：有三种情况，第一种么有进位，比如123，第二种有进位，199，我们需要依次遍历到不是9的位置。第三种999，和上面一样遇到9就变0，如果发现到头了，就新建一个更大的数组。

class Solution {
    public int[] plusOne(int[] digits) {
        // if(digits ==null||digits.length<1)return digits;
        int last = digits.length-1;
        while(last>=0&&digits[last]==9){
                digits[last] = 0;
                last--;
            }
            if(last ==-1){
            int res[] = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        if(digits[last]!=9){
            digits[last]++;          
        }
    return digits;
    }
}

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i =len-1;i>=0;i--){
            if(digits[i]==9){
                digits[i] = 0;
            }else{
                digits[i]++;
                break;
            }
        }
        if(digits[0] == 0){
            int[] tmp = new int[len+1];
            tmp[0] = 1;
            digits = tmp;
        }
        return digits;

    }
}

1103-分糖果2

思路：
1. 暴力法：
依次遍历一下数组，每次给里面的元素加等差数列的数值。

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        int index = 0;
        // 用这个index 来同时表示当前的位置和糖果的数量。TAT tql
        while(candies>0){
            res[index%num_people] += Math.min(index+1,candies);
            candies-=index+1;

            index++;
        }


        return res;

    }
}

2. 数学方法

利用等差数列的特质，求出一共需要多少步，然后计算需要多少轮。每一个小孩获得是糖果也是一个等差数列，计算累加。

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        int p = (int)(Math.sqrt(2*candies+0.25)-0.5);// 需要多少step
        int remaing = (int)(candies -p*(p+1)*0.5);// 最后一个剩下的


        int row = p/num_people;// 多少轮
        int cols = p%num_people;// 最后一个的位置

        for(int i=0;i<num_people;++i){
            res[i] = (i+1)*row+num_people*(int)(0.5*row*(row-1));
            if(i<cols){// 最后一次的各个累加的数值。
                res[i]+=i+1+num_people*row;
            }
        }
        res[cols] += remaing;
        return res;  



    }
}

836. 矩形重叠

思路：
考虑一下两个矩形重叠是怎么样的。我们把矩形的边投影到x轴上，如果有重合的话，min(x1[2],x2[2])>max(x1[0],x2[0])。y轴也是一样的。

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return(Math.min(rec1[2],rec2[2])>Math.max(rec1[0],rec2[0])&&
        Math.min(rec1[3],rec2[3])>Math.max(rec1[1],rec2[1]));
    }
}

892. 三维形体的表面积

思路：
把重叠的部分，分为三种。垂直，横向，竖向三种。

ublic int surfaceArea(int[][] grid) {
        if(grid.length<0)return 0;

        int verticalOverlap = 0;
        int rowOverlap = 0;
        int columOverlap = 0;
        int boxNum = 0;
        for(int i=0;i<grid.length;i++){
            for (int j=0;j<grid.length;j++){
                boxNum+= grid[i][j];
                if(grid[i][j]>0){
//                    对于垂直的而言，只需要-1
                    verticalOverlap += grid[i][j]-1;
                }
                if(j>0){
//                    对于水平和横向的，我们需要取最小值
                    rowOverlap+=Math.min(grid[i][j],grid[i][j-1]);
                }
                if(i>0){
                    columOverlap+= Math.min(grid[i-1][j],grid[i][j]);
                }
            }
        }
// 个数*6 -重叠部分面积*2
        return boxNum*6-(columOverlap+rowOverlap+verticalOverlap)*2;

914. 卡牌分组

思路：首先使用一个数组记录一下里面的频次，开始遍历求出公约数。如果=1，直接false，全部循环完了true。

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        if(deck.length<2)return false;
        int max = 0;
        for(int i=0;i<deck.length;i++){
            max = Math.max(max,deck[i]);
        }

        int[] res = new int[max+1];
        for(int i=0;i<deck.length;i++){
            res[deck[i]]++;
        }

        int x = res[deck[0]];
        for(int i=0;i<res.length;i++){
            if(res[i] == 1) return false;
            if(res[i]>1){
                x = gcd(x,res[i]);
                if(x ==1)return false;
            }

        }
        return true;


    }
    private int  gcd(int a,int b){
        if(b ==0)return a;
        return gcd(b,a%b);
    }
}