Leetcode刷题记录

LC1232. 缀点成线：简单

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
分析：
判断所有点是否在同一条直线上，需要根据同一条直线上点的特性来解题，那就是斜率相等，但要避免涉及到出发运算。
思路：
1.计算出第2个点和第1个点的横纵差值，然后用从第3个点起后的每一个点与第1个点的横纵差值，然后循环计算差值相乘是否相等来判断是否在同一条直线上。
2.先将第1个点移动到原点，然后利用第2个点算出 Ax+By=0(说明所在直线过原点)算出A与B的值，再判断所有的点是不是都满足 Ax+By=0这个方程。
知识点：
尽量避免使用斜率相等而使用除法，效率低而且可能出现除0的问题。
代码实现：

//思路1
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x0 = coordinates[0][0];
        int y0 = coordinates[0][1];
        int x = coordinates[1][0]-x0;
        int y = coordinates[1][1]-y0;
        int xi = 0;
        int yi = 0;
        for(int i = 2;i < coordinates.length;i++){
           xi = coordinates[i][0]-x0;
           yi = coordinates[i][1]-y0;
           if(xi*y!=yi*x){
              return false;
           }
        }
        return true;
    }
}
//思路2
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int deltaX = coordinates[0][0], deltaY = coordinates[0][1];
        int n = coordinates.length;
        for (int i = 0; i < n; i++) {
            coordinates[i][0] -= deltaX;
            coordinates[i][1] -= deltaY;
        }
        int A = coordinates[1][1], B = -coordinates[1][0];
        for (int i = 2; i < n; i++) {
            int x = coordinates[i][0], y = coordinates[i][1];
            if (A * x + B * y != 0) {
                return false;
            }
        }
        return true;
    }
}

LC628. 三个数的最大乘积:简单

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
分析：
思路：
1.方法一：排序
首先将数组排序。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
复杂度分析：
时间复杂度：O(NlogN)，其中 NN 为数组长度。排序需要 O(NlogN) 的时间。
空间复杂度：O(logN)，主要为排序的空间开销
2.方法二：线性扫描
在方法一中，我们实际上只要求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。
复杂度分析：
时间复杂度：O(N)，其中 N为数组长度。我们仅需遍历数组一次。
空间复杂度：O(1)。
知识点：
代码实现：

//思路1:数组排序，取最大三个数和最小两个数进行比较
class Solution {
    public int maximumProduct(int[] nums) {
        if(nums.length<3) return 0;
        Arrays.sort(nums);
        int len=nums.length;
        return Math.max(nums[0]*nums[1]*nums[len-1],nums[len-3]*nums[len-2]*nums[len-1]);
    }
}
//思路2：线性查找
class Solution {
    public int maximumProduct(int[] nums) {
        if(nums.length<3) return 0;
        int min1=Integer.MAX_VALUE,min2=Integer.MAX_VALUE;// 最小的和第二小的
        int max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;// 最大的、第二大的和第三大的
        for(int num:nums){
            if(min1>num){
                min2=min1;
                min1=num;//最小第1给min1
            }else if(min2>num){2
                min2=num;//最小第2给min2
            }
            if(max1<num){
                max3=max2;//第3大给max3
                max2=max1;//第2大给max2
                max1=num;//第1大给max1
            }else if(max2<num){
                max3=max2;
                max2=num;
            }else if(max3<num){
                max3=num;
            }
        }
        return Math.max(max1*max2*max3,min1*min2*max1);
    }
}

LC989. 数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
提示：
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0
分析：
让我们逐位将数字加在一起。例如计算 123+912，我们从低位到高位依次计算 3+2、2+1 和 1+9。任何时候，若加法的结果大于等于 10，把进位的 1 加入到下一位的计算中，所以最终结果为 1035。
复杂度分析：
时间复杂度：O(max(n,logK))，其中 nn 为数组的长度。
空间复杂度：O(max(n,logK))。
思路：
1.直接逐位相加
2.将整个加数 KK 加入数组表示的数的最低位。
上面的例子 123+912，我们把它表示成 [1,2,3+912]。
然后，我们计算 3+912=915。5 留在当前这一位，将 910/10=91 以进位的形式加入下一位。
然后，我们再重复这个过程，计算 [1,2+91,5]。我们得到 93，3 留在当前位，将 90/10=9 以进位的形式加入下一位。
继而又得到 [1+9,3,5]，重复这个过程之后，最终得到结果 [1,0,3,5]。
知识点：
1.使用 list.add(0,num) 比 使用 Collections.reverse(list) 的效率更低，时间更长 【小数据量时】
代码实现：

//思路1：逐位相加
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> res = new ArrayList<>();
        int n = A.length;
        for (int i = n - 1; i >= 0; i--) {
            int sum = A[i] + K % 10;
            K /= 10;
            if (sum >= 10) {
                K++;
                sum -= 10;
            }
            res.add(sum);
        }
        for (; K > 0; K /= 10) {
            res.add(K % 10);
        }
        Collections.reverse(res);
        return res;
    }
}
//思路2：逐位取余
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> res = new ArrayList<Integer>();
        int n = A.length;
        for (int i = n - 1; i >= 0 || K > 0; --i, K /= 10) {
            if (i >= 0) {
                K += A[i];
            }
            res.add(K % 10);
        }
        Collections.reverse(res);
        return res;
    }
}

LC888. 公平的糖果棒交换

爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j] 是鲍勃拥有的第 j 根糖果棒的大小。因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）
返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。如果有多个答案，你可以返回其中任何一个。保证答案存在。
分析：
Set集合：去重和比较方法

• hashset 具有去重功能，去重且无序(不是按照输入顺序打印)
• LinkedHashSet 有序的HashSet(按照存入集合的顺序打印)
• TreeSet用来排序,输出结果自动去重排序

思路：
使用哈希表

记爱丽丝的糖果棒的总大小为sumA，鲍勃的糖果棒的总大小为sumB。设答案为{x,y}，即爱丽丝的大小为 x 的糖果棒与鲍勃的大小为 y 的糖果棒交换，则有如下等式：sumA−x+y=sumB+x−y。化简得：x = y + (sumA-sumB)/2;即对于 B 中的任意一个数 y，只要 A 中存在一个数 x ，满足x=y + (sumA−sumB)/2；那么{x,y }即为一组可行解。为了快速查询 A 中是否存在某个数，我们可以先将 A 中的数字存入哈希表中(无序去重)。然后遍历 B 序列中的数 y ，在哈希表中查询是否有对应的 x。
知识点：
1.Arrays jdk的常用方法：

1.1 获取一个int数组的最大值和最小值
return Arrays.stream(arr).max().getAsInt();
return Arrays.stream(arr).min().getAsInt();
1.2 获取一个数组的和
return Arrays.stream(arr).sum();

代码实现：

//哈希表
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA=Arrays.stream(A).sum();
        int sumB=Arrays.stream(B).sum();
        int delta=(sumA-sumB)/2;
        HashSet<Integer> set=new HashSet<>();
        for(int num : A){
            set.add(num);
        }
        int[] ans=new int[2];
        for(int y : B){
            int x=y+delta;
            if(set.contains(x)){
                ans[0]=x;
                ans[1]=y;
                break;
            }
        }
        return ans;
    }
}