leetcode2023-07-04

矩阵中的和

public int matrixSum(int[][] nums) {
        int len = nums.length;
        for (int i = 0; i < len; ++i) {
            Arrays.sort(nums[i]);
        }

        int ans = 0;
        int len2 = nums[0].length;

        for (int i = len2 - 1; i >= 0; --i) {
           int max = 0;
            for (int j = 0; j < len; ++j) {
                max = Math.max(max, nums[j][i]);
            }
            
            ans += max;
        }
        return ans;
    }

等式方程的可满足性

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        int len = equations.length;
        int count = 0;
        for (String str : equations) {
            if (str.charAt(1) == '=') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                uf.union(index1, index2);
            }
        }
        // 同一个不等式中的两个变量不能属于同一个连通分量
        for (String str : equations) {
            if (str.charAt(1) == '!') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                if (uf.find(index1) == uf.find(index2)) {
                    return false;
                }
            }
        }
        return true;
    }
}

class UnionFind {
    private int[] id;
    // 当前连通分量数目
    private int count;
    private int[] size;
    public UnionFind(int n) {
        this.count = n;
        this.id = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            id[i] = i;
        }
    }

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

    public void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        //如果已经在同一个连通分量中，就不进行任何操作
        if (xRoot == yRoot) return;
        if (size[xRoot] < size[yRoot]) {
            xRoot = xRoot ^ yRoot;
            yRoot = xRoot ^ yRoot;
            xRoot = xRoot ^ yRoot;
        }
        id[yRoot] = xRoot;
        size[xRoot] += size[yRoot];
        --count;
    }
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int count() {
        return count;
    }
}

找出数组中的所有 K 近邻下标

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            boolean flag = false;
            for (int j = i; j >= i - k && j >= 0; --j) {
                if (nums[j] == key) {
                    flag = true;
                    break;
                }
            }

            for (int j = i; !flag && j <= i + k && j < n; ++j) {
                if (nums[j] == key) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                ans.add(i);
            }
        }

        return ans;
    }
}