Day31 LeetCode

1. 数组序号转换

给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号.

序号代表了一个元素有多大.序号编号的规则如下：

• 序号从 1 开始编号.
• 一个元素越大,那么序号越大.如果两个元素相等,那么它们的序号相同.
• 每个数字的序号都应该尽可能地小.

分析：

先对arrDuplicate and sort to getarr1,Create a hash table and comparearr1Iterate over to get the sorted position of each number,然后创建一个数组res大小与arr相同,遍历arr,Find the current number in the hash tablevalue并把它value写进resin the current location of.

class Solution {
    
    public int[] arrayRankTransform(int[] arr) {
    
        int[] sortedArr = new int[arr.length];
        System.arraycopy(arr, 0, sortedArr, 0, arr.length);
        Arrays.sort(sortedArr);
        Map<Integer, Integer> ranks = new HashMap<Integer, Integer>();
        int[] ans = new int[arr.length];
        for (int a : sortedArr) {
    
            if (!ranks.containsKey(a)) {
    
                ranks.put(a, ranks.size() + 1);
            }
        }
        for (int i = 0; i < arr.length; i++) {
    
            ans[i] = ranks.get(arr[i]);
        }
        return ans;
    }
}

2. 完全平方数

给你一个整数 n ,返回和为 n 的完全平方数的最少数量 .完全平方数是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积.例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是.
示例：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

分析：

动态规划：

• 首先初始化长度为 n+1 的数组 dp,每个位置都为 0
• 如果 n 为 0,则结果为 0
• 对数组进行遍历,下标为 i,每次都将当前数字先更新为最大的结果,即 dp[i]=i,比如 i=4,最坏结果为 4=1+1+1+1 即为 4 个数字
• 动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1),i 表示当前数字,j*j 表示平方数

class Solution {
    
    public int numSquares(int n) {
    
        int[] dp = new int[n+1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
    
            dp[i] = i;
            for (int j = 1; i-j*j>=0; j++) {
    
                dp[i] = Math.min(dp[i], dp[i - j*j]+1);
            }
        }
        return dp[n];
    }
}

3. 有效的正方形

给定2D空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true .点的坐标 pi 表示为 [xi, yi] .Inputs are not given in any order.A valid square has four equal sides and four equal angles(90度角).

分析：

求出6条边,Four side lengths and two diagonals.Only squares and rhombus have sides of equal length,Only squares have equal diagonals
Therefore, the sorting can determine whether the side lengths and the diagonals are equal.

class Solution {
    
    public long len(int[] x,int[] y){
    
        return 1L * (x[0] - y[0]) * (x[0] - y[0]) + 1L * (x[1] - y[1]) * (x[1] - y[1]);
    }
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
    
        if(p1[0] == p2[0] && p1[1] == p2[1]) return false;
        long[] l = new long[6];
        l[0] = len(p1,p2);
        l[1] = len(p1,p3);
        l[2] = len(p1,p4);
        l[3] = len(p2,p3);
        l[4] = len(p2,p4);
        l[5] = len(p3,p4);
        Arrays.sort(l);
        return l[0] == l[1] && l[0] == l[2] && l[0] == l[3] && l[4] == l[5];
    }
}