6.25号刷题

第一题 279. Perfect Squares

题目描述

给定一个正整数n，求相加等于n的完全平方数（例如 1, 4, 9, 16, …）的最小个数。

例如，给定n = 12，返回3，因为12 = 4 + 4 + 4；给定n = 13，返回2，因为13 = 4 + 9。

算法

利用动态规划的思想，由于需要求最小值，可以考虑保存之前的每一个状态。然后统计到现阶段的最小值，然后再不断循环更新。

public class Solution {
    public int numSquares(int n) {
        if (n <= 0) return 0;
        int[] res = new int[n + 1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        for (int i = 1; i < n + 1; i++) {
            int j = 1;
            int min = Integer.MAX_VALUE;
            while (i >= j * j) {
                min = Math.min(min, res[i - j * j] + 1);
                j++;
            }
            res[i] = min;
        }
        return res[n];        
    }
}

第二题 204. Count Primes

题目描述

统计小于非负整数n的素数的个数

提示：n的范围是100,000到5,000,000

算法

利用乘法，将所有之后不可能的都筛去，然后剩下的就是我们需要的答案。

public class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                for (int j = 2; j * i < n; j++) {
                    notPrime[j * i] = true;
                }
            }
        }
        return count;        
    }
}

第三题 593. Valid Square

题目描述

给定平面上的4个点，判断是否围成一个正方形。

注意：

1. 坐标的范围[-10000, 10000]
2. 有效的正方形有4条相等的长度为正数的边，并且四个内角为直角。
3. 输入点无序

算法

查看边的长度是否只有两种，并且如果边长为0的话是无效的

public class validSquare593 {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> set = new HashSet<>(Arrays.asList(dis(p1, p2), dis(p1, p3), dis(p1, p4), dis(p2, p3), dis(p2, p4), dis(p3, p4)));

        return !set.contains(0) && set.size() == 2;
    }

    public int dis(int[] a, int[] b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }
}

第四题 441. Arranging Coins

题目描述

你有n枚硬币，想要组成一个阶梯形状，其中第k行放置k枚硬币。

给定n，计算可以形成的满阶梯的最大行数。

n是非负整数，并且在32位带符号整数范围之内。

算法

二分法

public class arrangeCoins441 {
    public int arrangeCoins2(int n) {
        if (n <= 0) return 0;
        int left = 0, right = n, ans = 0;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid + (mid - 1) * mid / 2 <= n ) {
                left = (int) mid + 1;
                ans = (int) mid;
            } else {
                right = (int) mid - 1;
            }
        }
        return ans;

    }
}

解方程法

public class Solution {
    public int arrangeCoins(int n) {
        double temp = n;
        return (int) (Math.sqrt(2 * temp + 0.25) - 0.5);
    }
}

第五题 517. Super Washing Machines

题目描述

给定一个长度为n的整数数组nums，每一次选择m个数(1 ≤ m ≤ n)进行移动：将这m个数-1，同时令其相邻元素+1（这m个数同时可以是被加元素）

求最少需要多少次移动，使得nums的所有元素均相等。如果不能，则返回-1

算法

对于每一个数字，我们需要到达average 这个大小。为了达到这个大小，我们需要移出(正数)或者已入(负数)个数字，对于位置0的需求，肯定是1移动过来的。确定0的需求后，1的平衡后的需求(0的需求和1本身的需求)是由2来满足的。依次内推，可以写出DP的解

DP

public class Solution {
    public int findMinMoves(int[] machines) {
        int sum = 0;
        for (int num : machines) sum += num;
        if (sum % machines.length != 0) return -1;
        int avg = sum / machines.length, max = 0;
        
        int[] dp = new int[machines.length];
        dp[0] = machines[0] - avg;
        max = dp[0];
        
        for (int i = 1; i < machines.length; i++) {
            dp[i] = dp[i - 1] + machines[i] - avg;
            max = Math.max(Math.abs(dp[i]), Math.max(max, machines[i] - avg));
        }
        return max;        
    }
}

简化

public class findMinMoves517 {
    public int findMinMoves(int[] machines) {
        int sum = 0;
        for (int num : machines) sum += num;
        if (sum % machines.length != 0) return -1;
        int avg = sum / machines.length, cnt = 0, max = 0;

        for (int num : machines) {
            cnt += num - avg;
            max = Math.max(Math.max(max, Math.abs(cnt)), num - avg);
        }
        return max;
    }
}