头像

hpstory

专注C++++




离线:2小时前


最近来访(264)
用户头像
一万小时定律
用户头像
一颗水果糖
用户头像
Unnatural
用户头像
ffffffffffffffffffffffffffffff
用户头像
sdhj7133
用户头像
回首已惘然
用户头像
muxu
用户头像
L-L
用户头像
qimu
用户头像
rech
用户头像
AWilliamLiu
用户头像
GreatestOliveira
用户头像
轻舟已过万重山
用户头像
寻找藤井树
用户头像
倦鸟思归林
用户头像
Ethanyyc
用户头像
Kir
用户头像
GTR
用户头像
Westife_
用户头像
yxc的小迷妹


hpstory
21小时前

C# 代码

public class Solution {
    public int CollectTheCoins(int[] coins, int[][] edges) {
        int n = coins.Length;
        // 用hashset代替统计入度的列表
        List<HashSet<int>> graph = new List<HashSet<int>>();
        int result = n - 1;
        for (int i = 0; i <= n; i++){
            graph.Add(new HashSet<int>());
        }

        foreach (int[] edge in edges){
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        // 第一轮拓扑排序,删除没有金币的子树
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i <= n; i++){
            if (graph[i].Count == 1 && coins[i] == 0) queue.Enqueue(i);
        }

        while (queue.Count > 0){
            int t = queue.Dequeue();
            foreach (int i in graph[t]){
                graph[i].Remove(t);
                result--;
                if (graph[i].Count == 1 && coins[i] == 0){
                    queue.Enqueue(i);
                }
            }
        }

        // 第二轮拓扑排序,删除有金币的叶子节点和该节点相邻的,且删除该节点后入度为1的节点
        for (int i = 0; i <= n; i++){
            if (graph[i].Count == 1 && coins[i] == 1) queue.Enqueue(i);
        }   

        result -= queue.Count;
        foreach (int t in queue){
            foreach (int i in graph[t]){
                graph[i].Remove(t);            
                if (graph[i].Count == 1){
                    result--;
                }
            }
        }  

        // 树中没有金币会导致结果为负,需要和0取max
        return Math.Max(result * 2, 0);
    }
}



hpstory
21小时前
public class Solution {
    public int CollectTheCoins(int[] coins, int[][] edges) {
        int n = coins.Length;
        List<HashSet<int>> graph = new List<HashSet<int>>();
        int result = n - 1;
        for (int i = 0; i <= n; i++){
            graph.Add(new HashSet<int>());
        }

        foreach (int[] edge in edges){
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        Queue<int> queue = new Queue<int>();
        for (int i = 0; i <= n; i++){
            if (graph[i].Count == 1 && coins[i] == 0) queue.Enqueue(i);
        }

        while (queue.Count > 0){
            int t = queue.Dequeue();
            foreach (int i in graph[t]){
                graph[i].Remove(t);
                result--;
                if (graph[i].Count == 1 && coins[i] == 0){
                    queue.Enqueue(i);
                }
            }
        }

        for (int i = 0; i <= n; i++){
            if (graph[i].Count == 1 && coins[i] == 1) queue.Enqueue(i);
        }   

        result -= queue.Count;
        foreach (int t in queue){
            foreach (int i in graph[t]){
                graph[i].Remove(t);            
                if (graph[i].Count == 1){
                    result--;
                }
            }
        }  

        return Math.Max(result * 2, 0);
    }
}



hpstory
1天前

C# 代码

类似题:1838. 最高频元素的频数

public class Solution {
    public IList<long> MinOperations(int[] nums, int[] queries) {
        int n = nums.Length, m = queries.Length;
        Array.Sort(nums);
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        List<long> result = new List<long>();
        for (int i = 0; i < m; i++){
            int left = 0, right = n - 1;
            while (left < right){
                int mid = left + right >> 1;
                if (nums[mid] >= queries[i]) right = mid;
                else left = mid + 1;
            }

            if (nums[left] < queries[i]) left++;
            result.Add((long)queries[i] * left - sum[left] + sum[n] - sum[left] - (long) queries[i] * (n - left));
        }

        return result;
    }
}



hpstory
1天前
public class Solution {
    public IList<long> MinOperations(int[] nums, int[] queries) {
        int n = nums.Length, m = queries.Length;
        Array.Sort(nums);
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        List<long> result = new List<long>();
        for (int i = 0; i < m; i++){
            int left = 0, right = n - 1;
            while (left < right){
                int mid = left + right >> 1;
                if (nums[mid] >= queries[i]) right = mid;
                else left = mid + 1;
            }

            if (nums[left] < queries[i]) left++;
            result.Add((long)queries[i] * left - sum[left] + sum[n] - sum[left] - (long) queries[i] * (n - left));
        }

        return result;
    }
}



hpstory
1天前

C# 正向处理代码

// 筛质数可以优化成埃式筛,查找质数可以优化成二分
public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        int n = nums.Length;
        List<int> primes = new List<int>();
        // 可以不减
        primes.Add(0);
        for (int i = 2; i <= 1000; i++){
            if (IsPrime(i)) primes.Add(i);
        }

        int prev = 0;
        for (int i = 0; i < n; i++){
            if (nums[i] <= prev) return false;
            // 每次减掉满足条件的最大质数
            nums[i] -= Get(nums[i]);
            prev = nums[i];
        }

        return true;

        bool IsPrime(int x){
            if (x < 2) return false;
            for (int i = 2; i <= x / i; i++){
                if (x % i == 0) return false;
            }

            return true;
        }

        int Get(int x){
            for (int i = primes.Count - 1; i >= 0; i--){
                if (primes[i] < x && primes[i] < x - prev) return primes[i];
            }

            return -2000;
        }
    }
}

C# 反向处理代码

public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        int n = nums.Length;
        List<int> primes = new List<int>();
        bool[] isPrime = new bool[1010];
        for (int i = 2; i <= 1000; i++){
            if (!isPrime[i]){
                primes.Add(i);
                for (int j = i; j <= 1000 / i; j++){
                    isPrime[j * i] = true;
                }
            }
        }

        for (int i = n - 1; i > 0; i--){
            if (nums[i] > nums[i - 1]) continue;
            // 每次减掉满足条件的最小质数
            nums[i - 1] -= Get(nums[i - 1], nums[i - 1] - nums[i]);           
            if (nums[i - 1] < 0) return false;
        }

        return true;

        int Get(int x, int diff){
            for (int i = 0; i < primes.Count; i++){
                if (primes[i] > diff && primes[i] < x) return primes[i];
            }

            return 2000;
        }
    }
}



hpstory
1天前
public class Solution {
    public bool PrimeSubOperation(int[] nums) {
        int n = nums.Length;
        List<int> primes = new List<int>();
        primes.Add(0);
        for (int i = 2; i <= 1000; i++){
            if (IsPrime(i)) primes.Add(i);
        }

        int prev = 0;
        for (int i = 0; i < n; i++){
            if (nums[i] <= prev) return false;
            nums[i] -= Get(nums[i]);
            prev = nums[i];
        }

        return true;

        bool IsPrime(int x){
            if (x < 2) return false;
            for (int i = 2; i <= x / i; i++){
                if (x % i == 0) return false;
            }

            return true;
        }

        int Get(int x){
            for (int i = primes.Count - 1; i >= 0; i--){
                if (primes[i] < x && primes[i] < x - prev) return primes[i];
            }

            return -2000;
        }
    }
}



hpstory
1天前

C# 代码

public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        return k <= numOnes + numZeros ? Math.Min(k, numOnes) : numOnes - (k - numOnes - numZeros);
    }
}



hpstory
1天前
public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        return k <= numOnes + numZeros ? Math.Min(k, numOnes) : numOnes - (k - numOnes - numZeros);
    }
}



hpstory
6天前

C# 代码

public class Solution {
    public int FindSmallestInteger(int[] nums, int value) {
        int n = nums.Length;
        int[] count = new int[value];
        for (int i = 0; i < n; i++){
            count[(nums[i] % value + value) % value]++;
        }

        for (int i = 0; i < n; i++){
            if (count[i % value] == 0) return i;
            count[i % value]--;
        }

        return n;
    }
}



hpstory
6天前
public class Solution {
    public int FindSmallestInteger(int[] nums, int value) {
        int n = nums.Length;
        int[] count = new int[value];
        for (int i = 0; i < n; i++){
            count[(nums[i] % value + value) % value]++;
        }

        for (int i = 0; i < n; i++){
            if (count[i % value] == 0) return i;
            count[i % value]--;
        }

        return n;
    }
}