2022-07-29

[Zheaoli]

2022-07-29

[SaraadKun]

593. 有效的正方形

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        //根据x,y坐标从左到右从上到下对点排序,验证: 
        // 1.四条边p1p2,p1p3,p2p4,p3p4是否相等; 并排除输入四点为同一点的情况
        // 2.若满足1,验证∠p1p2p4是否为直角, 即(p1p2)^2 + (p2p4)^2 = (p1p4)^2
        int[][] ps = Stream.of(p1, p2, p3, p4)
                .sorted((a, b) -> {
                    if (a[0] == b[0]) {
                        return a[1] - b[1];
                    }
                    return a[0] - b[0];
                }).toArray(int[][]::new);
        int d12 = distance(ps[0], ps[1]);
        int d13 = distance(ps[0], ps[2]);
        int d24 = distance(ps[1], ps[3]);
        int d34 = distance(ps[2], ps[3]);
        //若四条边相等,排除输入坐标为同一点的情况
        if (d12 != d13 || d12 != d24 || d12 != d34 || (p1[0] == p2[0] && p1[1] == p2[1])) {
            return false;
        }
        int d14 = distance(ps[0], ps[3]);
        return d12 + d24 == d14;
    }

    private int distance(int[] a, int[] b) {
        int x1 = a[0], y1 = a[1], x2 = b[0], y2 = b[1];
        return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
    }
}

---

虾球写 WeChat: Saraad

[gongpeione]

/*
 * @lc app=leetcode id=35 lang=javascript
 *
 * [35] Search Insert Position
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let start = 0;
    let end = nums.length - 1;

    if (target > nums[end]) {
        return end + 1;
    }

    if (target <= nums[start]) {
        return start;
    }

    while(start < end) {
        const mid = start + Math.floor((end - start) / 2);
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] > target) {
            end = mid;
        } else {
            start = mid;
        }
        if (end - start === 1) {
            return end;
        }
    }

    return start;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件

[SaraadKun]

778. 水位上升的泳池中游泳

class Solution {

    int[] id;

    private boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    private int find(int x) {
        if (id[x] != x) {
            id[x] = find(id[x]);
        }
        return id[x];
    }

    private void union(int x, int y) {
        int idx = find(x), idy = find(y);
        if (idx == idy) {
            return;
        }
        id[idx] = idy;
    }

    public int swimInWater(int[][] grid) {
        //遍历点集,相邻的点构造边并附权重,对边按权重排序
        //创建UF,遍历排序后的边集合,每加一条边判断首尾点是否连通
        //若联通,则本次添加的边的权重即为最大高度,也即最大等待时间;
        int n = grid.length;
        //初始化UF
        id = new int[n * n];
        for (int i = 0; i < n * n; i++) {
            id[i] = i;
        }
        int[][] edges = new int[2 * n * (n - 1)][];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int cid = i * n + j;
                //构造边
                if (j != n - 1) {
                    edges[idx++] = new int[]{cid, cid + 1, Math.max(grid[i][j], grid[i][j + 1])};
                }
                if (i != n - 1) {
                    edges[idx++] = new int[]{cid, cid + n, Math.max(grid[i][j], grid[i + 1][j])};
                }
            }
        }
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
        int start = 0, end = n * n - 1;
        for (int[] edge : edges) {
            union(edge[0], edge[1]);
            if (connected(start, end)) {
                return edge[2];
            }
        }
        return 0;
    }

}

---

WeChat: Saraad

[SaraadKun]

1631. 最小体力消耗路径

class Solution {

    int[] f;

    private boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    private int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    private void union(int x, int y) {
        int idx = find(x), idy = find(y);
        if (idx == idy) {
            return;
        }
        f[idx] = idy;
    }

    public int minimumEffortPath(int[][] heights) {
        //预处理点,每两个相邻的点创建一条加权的无向边,用三元组表示[id1, id2, w]
        //将所有的边按权重排序,从小到大加入UF中,若加入一条边后首尾节点联通,则当前边的权重即为答案
        int m = heights.length, n = heights[0].length;
        f = new int[m * n];
        for (int i = 0; i < f.length; i++) {
            f[i] = i;
        }
        int[][] edges = new int[2 * m * n - m - n][];
        int idx = 0;
        for (int i = 0; i < m; i++) {
           for (int j = 0; j < n; j++) { 
               int k = i * n + j;
               if (j != n - 1) {
                   edges[idx++] = new int[] {k, k + 1, Math.abs(heights[i][j + 1] - heights[i][j])};
               }
               if (i != m - 1) {
                   edges[idx++] = new int[] {k, k + n, Math.abs(heights[i + 1][j] - heights[i][j])};
               }
           }
        }
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
        int start = 0, end = m * n - 1;
        for (int[] edge : edges) {
            union(edge[0], edge[1]);
            if (isConnected(start, end)) {
                return edge[2];
            }
        }
        return 0;
    }
}

---

WeChat: Saraad