LeetCode初级算法题：寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149：直线上最多的点数 Java详解
1 寻找数组的中心索引
解题思路与代码
数组中某一个下标，左右两边的元素之后相等，该下标即为中心索引
思路：先统计出整个数组的总和，然后从第一个元素开始叠加
总和递减当前元素，叠加递增当前元素，知道两个值相等
public static int pivotIndex(int[] nums) { int sum1 = Arrays.stream(nums).sum(); int sum2 = 0; for(int i = 0; i<nums.length; i++){ sum2 += nums[i]; if(sum1 == sum2){ return i; } sum1 = sum1 - nums[i]; } return -1; }
2 x的平方根
1 题目
在不使用 sqrt(x) 函数的情况下，得到 x的平方根的整数部分
2 解题思路与代码
解法一：二分查找
x的平方根肯定在0到x之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，m平方值如果大于x、则往左边找，如果小于等于x则往右边找找到0和X的最中间的数m，
如果m * m > x，则m取x/2到x的中间数字，直到m * m < x，m则为平方根的整数部分
如果m * m <= x，则取0到x/2的中间值，知道两边的界限重合，找到最大的整数，则为x平方根的整数部分
间复杂度：O(logN)
代码
public static int binarySearch(int x) { int l = 0, r = x, index = -1; while (l <= r) { int mid = l + (r - l) / 2; if ((long) mid * mid <= x) { index = mid; l = mid + 1; } else { r = mid - 1; } } return index; }
解法二：牛顿迭代
假设平方根是 i ，则 i 和 x/i 必然都是x的因子，而 x/i 必然等于 i ，推导出 i + x / i = 2 * i，得出 i = (i + x / i) / 2
由此得出解法，i 可以任选一个值，只要上述公式成立，i 必然就是x的平方根，如果不成立， (i + x / i) / 2得出的值进行递归，直至得出正确解
代码
public static int newton(int x) { if(x==0) return 0; return ((int)(sqrts(x,x))); } public static double sqrts(double i,int x){ double res = (i + x / i) / 2; if (res == i) { return i; } else { return sqrts(res,x); } }
3 三个数的最大乘积
1 题目
一个整型数组 nums ，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。
乘积不会越界
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
2 解题思路与代码
解法一：排序
public static int sort(int[] nums) { Arrays.sort(nums); int n = nums.length; return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]); }
解法二：线性扫描
public static int getMaxMin(int[] nums) { // 最小的和第二小的 int min1 = 0, min2 = 0; // 最大的、第二大的和第三大的 int max1 = 0, max2 = 0, max3 = 0; for (int x : nums) { if (x < min1) { min2 = min1; min1 = x; } else if (x < min2) { min2 = x; } if (x > max1) { max3 = max2; max2 = max1; max1 = x; } else if (x > max2) { max3 = max2; max2 = x; } else if (x > max3) { max3 = x; } } return Math.max(min1 * min2 * max1, max1 * max2 * max3); }
4 Leetcode 149：直线上最多的点数
题目描述
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例1：
输入: [[1,1],[2,2],[3,3]] 输出: 3 解释: ^ | | o | o | o +-------------> 0 1 2 3 4
示例2：
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] 输出: 4 解释: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
解题代码
java
class Sulution{ 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>slpe = new HashMap<>(); int repeat = 0; int tmp_max = 0; for (int j =i +1;i<n; i++) { 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); } }
python
from decimal import Decimal Decimal((point2.y - point1.y))/Decimal((point2.x - point1.x)) class Solution: def maxPoints(self, points): """ :type points: List[Point] :rtype: int """ slopes, result = defaultdict(int), 0 for i, point1 in enumerate(points): slopes.clear() duplicate = 1 for _, point2 in enumerate(points[i+1:]): if point1.x == point2.x and point1.y == point2.y: duplicate += 1 continue slope = float('inf') if point1.x == point2.x else \ (point1.y - point2.y)/(point1.x - point2.x) slopes[slope] += 1 if result < duplicate: result = duplicate for _, val in slopes.items(): if val + duplicate > result: result = val + duplicate return result
