hpstory

4.5万

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++){
}

foreach (int[] edge in edges){
}

// 第一轮拓扑排序，删除没有金币的子树
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++){
}

foreach (int[] edge in edges){
}

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# 代码

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>();
// 可以不减
for (int i = 2; i <= 1000; 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]){
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>();
for (int i = 2; i <= 1000; 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;
}
}