Leetcode Weekly 304

6132. 使数组中所有元素都等于零

给你一个非负整数数组 nums .在一步操作中,你必须：

选出一个正整数 x ,x 需要小于或等于 nums 中 最小 的 非零 元素.
nums 中的每个正整数都减去 x.
返回使 nums 中所有元素都等于 0 需要的 最少 操作数.

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ,之后 nums = [0,4,0,2,4] .
第二步操作：选出 x = 2 ,之后 nums = [0,2,0,0,2] .
第三步操作：选出 x = 2 ,之后 nums = [0,0,0,0,0] .
示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ,所以不需要执行任何操作.

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

Because of the smallest reduction,All numbers are reduced,So no matter how small it is,Big numbers are still big,
The crux of the matter is to make the smallest number every time 0
所以问题就变成了,The question of how many different numbers are there

去重

class Solution {
    
    public int minimumOperations(int[] nums) {
    
        HashSet<Integer> hashset = new HashSet();
        for (int i : nums) {
    
            if (i != 0)
                hashset.add(i);
        }
        return hashset.size();
    }
}

Dummy code in the game

class Solution {
    
    public int minimumOperations(int[] nums) {
    
        Arrays.sort(nums);
        int n = nums.length - 1;
        if (nums[n] == 0)
            return 0;
        int ans = 0;
        int p = 0;
        while (nums[p] == 0) p++;
        int cnt = 0;
        while (nums[n] > 0) {
    
            
            nums[p] -= cnt;
            
            if (nums[p] <= 0) {
    
                if (p == n) ans++;
                p++;
                continue;
            }
            nums[n] -= nums[p];
            cnt += nums[p];
            p++;
            ans++;
        }
        return ans;
    }
    
    public boolean check(int[] s) {
    
        boolean flag = true;
        for (int i : s) {
    
            if (i != 0)
                return false;
        }
        return true;
    }
}

6133. 分组的最大数量

给你一个正整数数组 grades ,表示大学中一些学生的成绩.你打算将 所有 学生分为一些 有序 的非空分组,其中分组间的顺序满足以下全部条件：

第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩,对所有组均成立（除了最后一组）.
第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数,对所有组均成立（除了最后一组）.
返回可以形成的 最大 组数.

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：下面是形成 3 个分组的一种可行方法：

• 第 1 个分组的学生成绩为 grades = [12] ,总成绩：12 ,学生数：1
• 第 2 个分组的学生成绩为 grades = [6,7] ,总成绩：6 + 7 = 13 ,学生数：2
• 第 3 个分组的学生成绩为 grades = [10,3,5] ,总成绩：10 + 3 + 5 = 18 ,学生数：3
  可以证明无法形成超过 3 个分组.
  示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组,因为如果要形成 2 个分组的话,会导致每个分组中的学生数目相等.

提示：

1 <= grades.length <= 105
1 <= grades[i] <= 105

思路

说实话,I didn't understand why when I wrote it,I saw someone say it's an easy question,I thought I should,Then it was written in twos.

The topic is confusing,In fact, we sort everything in ascending order,Then the latter number must be greater than the former number,所以,To find the largest grouping,Then our numbers must be 从一开始的,1 2 3 4 …
很显然,等差数列,Divide to find the number of groups,The excess is directly merged into the last group

思维？+ 二分

class Solution {
    
    public int maximumGroups(int[] s) {
    
        int l = 1, r = (int)(1e5);
        int ans = 0;
        while (l <= r) {
    
            int mid = l + (r - l) / 2;
            if ((mid + 1l) * mid / 2 <= s.length) {
    
                ans = mid;
                l = mid + 1;
            } else 
                r = mid - 1;
        }
        
        return ans;
    }
}

6134. 找到离给定两个节点最近的节点

给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,每个节点 至多 有一条出边.

有向图用大小为 n 下标从 0 开始的数组 edges 表示,表示节点 i 有一条有向边指向 edges[i] .如果节点 i 没有出边,那么 edges[i] == -1 .

同时给你两个节点 node1 和 node2 .

请你返回一个从 node1 和 node2 都能到达节点的编号,使节点 node1 和节点 node2 到这个节点的距离 较大值最小化.如果有多个答案,请返回 最小 的节点编号.如果答案不存在,返回 -1 .

注意 edges 可能包含环.

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ,从节点 1 到节点 2 的距离为 1 .
两个距离的较大值为 1 .我们无法得到一个比 1 更小的较大值,所以我们返回节点 2 .
示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ,节点 2 到它自己的距离为 0 .
两个距离的较大值为 2 .我们无法得到一个比 2 更小的较大值,所以我们返回节点 2 .

提示：

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

思路

经典的bfs问题,两次bfs 求出来 node1 和 node2 distances to other points,recorded in two arrays,Then traverse the array to get the final result

暴力遍历

Because each point has only one outgoing edge,So I chose to traverse directly to find the distance（In fact, graph theory is written too little）

class Solution {
    
    public int closestMeetingNode(int[] edges, int node1, int node2) {
    
        int n = edges.length;
        int[] v1 = new int[n];
        int[] v2 = new int[n];
        Arrays.fill(v1, -1);
        Arrays.fill(v2, -1);

        v1[node1] = 0;
        v2[node2] = 0;
        int ans = 1000000, p = -1;
        int cnt = 1;
        for (int i = edges[node1]; i != -1; ) {
    
            if (v1[i] != -1) 
                break; // 环,退出来
            
            v1[i] = cnt++;
            i = edges[i];
        }
        cnt = 1;
        for (int i = edges[node2]; i != -1; ) {
    
            if (v2[i] != -1) 
                break; // 环,退出来
            
            v2[i] = cnt++;
            i = edges[i];
        }
        
        for (int i = 0; i < n; i++) {
    
            if (v1[i] != -1 && v2[i] != -1) {
    
                int t = Math.max(v1[i], v2[i]);
                if (t < ans) {
    
                    ans = t;
                    p = i;
                }
            }
        }
        
        return p;
    }
}

bfs

class Solution {
    
public:
    void bfs(const vector<int> &edges, int s, vector<int> &dis) {
    
        dis[s] = 0;
        queue<int> q;
        q.push(s);
        
        while (q.empty() == false) {
    
            auto f = q.front();
            q.pop();
            
            if (edges[f] == -1) continue;
            int next = edges[f];
            if (dis[next] != -1) continue;
            dis[next] = dis[f] + 1;
            q.push(next);
        }
    }
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    
        vector<int> d1(edges.size(), -1);
        vector<int> d2(edges.size(), -1);
        
        bfs(edges, node1, d1);
        bfs(edges, node2, d2);
        
        int anw = -1;
        int anw_id = -1;
        for (int i = 0; i < edges.size(); i++) {
    
            if (d1[i] != -1 && d2[i] != -1) {
    
                if (anw == -1 || max(d1[i], d2[i]) < anw) {
    
                    anw = max(d1[i], d2[i]);
                    anw_id = i;
                }
            }
        }
        return anw_id;
    }
};