经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » Go语言 » 查看文章
2023-10-25：用go语言，假如某公司目前推出了N个在售的金融产品(1＜=N＜=100) 对于张三，用ai表示他购买了ai(0＜=ai＜=10^4)份额的第i个产品(1＜=i＜=N) 现给出K(
来源：cnblogs　　作者：福大大架构师每日一题　　时间：2023/10/25 15:13:17　　对本文有异议

2023-10-25：用go语言，假如某公司目前推出了N个在售的金融产品(1<=N<=100)

对于张三，用ai表示他购买了ai(0<=ai<=10^4)份额的第i个产品(1<=i<=N)

现给出K(1<=K<=N)个方案，通过这些方案，能够支持将多个不同的产品进行整合

(也可以对单个产品进行优化)形成新的产品。

新的产品形成后，若用户持有了组成新产品所需的全部的原产品份额，

则能够将用户持有的原产品份额转换为新产品的份额，各原产品份额与新产品份额比例均为1:1

我们保证对于每个产品最多存在一个方案使用旧产品整合成该产品

并且根据方案产出的新产品的产品编号均大于各旧产品的产品编号

现计划根据这些方案，帮助部分愿意升级到最新产品的用户对产品进行升级

请协助工作人员计算当前用户能够转换出的最新产品份额的最大值

输入描述

第一行包含整数N，第二行包含N个整数ai，第三行包含整数K

接下来的K行，每一行代表一个方案，每一行包含整数1和M(M>=1)

L为该方案产生的新产品的编号，M代表方案所需原产品个数

接下来的M个整数代表了该方案所需的每个原产品的个数

输出描述

根据日前的份额和给出的方案，经过若干次转换，输出当前用户能够得到产品N的份额最大值

举例

输入:

5

2 0 0 1 0

3

5 2 3 4

2 1 1

3 1 2

输出:

1

解释:

第一步将1份1产品转化为1份2产品

第二步将1份2产品转化为1份3产品

第三步将1份3产品和1份4产品，转成为1份5产品

然后不能得到更多的5产品了，所以返回1

实在是太困惑了，上文说的意思可谓不做人，那么我们改写一下意思，变得好理解

如下是改写后的题目描述

给定一个数组arr，长度为n，产品编号从0~n-1

arr[i]代表初始时i号产品有多少份

存在一系列的产品转化方案的数组convert，长度为k，代表k个方案

比如具体某一个方案，convert[j] = {a, b, c, d, ...}

表示当前的j号方案转化出来的产品是a，转化1份a需要：1份b、1份c、1份d...

其中a、b、c、d...一定都在0~n-1范围内

并且题目保证a > Math.max(b, c, d, ....)

而且题目保证所有方案转化出来的产品编号一定是不重复的

请返回最终能得到的第n-1号商品的最大值

1 <= n <= 100

0 <= arr[i] <= 10^4

k < n

来自招商银行。

来自左程云。

答案2023-10-25：

这次代码生成用的讯飞星火，生成完后，要略微修改下代码才能通过。另外c代码的生成，一直有问题，索性就不管了。

大体过程如下：

首先，我们需要定义一个函数ok(arr, graph, aim)来判断当前的方案是否可行。这个函数的输入参数包括：

1.arr：表示每个产品的初始份额数组；

2.graph：表示产品转化方案的邻接表；

3.aim：表示目标产品编号。

在这个函数中，我们首先初始化一些变量，然后遍历所有的产品，对于每个产品，我们检查它是否可以被转化到目标产品。如果可以，我们就更新它的转化后的数量，并继续检查下一个产品。最后，我们返回一个布尔值，表示当前的方案是否可行。

接下来，我们需要定义一个函数maxValue(arr, convert)来计算当前用户能够转换出的最新产品份额的最大值。这个函数的输入参数包括：

1.arr：表示每个产品的初始份额数组；

2.convert：表示产品转化方案的二维数组。

在这个函数中，我们首先初始化一些变量，然后使用二分查找的方法来寻找最大的转化后的产品份额。具体来说，我们将转化后的产品份额范围设置为0到所有初始产品份额之和，然后不断地将范围缩小一半，直到找到一个可行的方案或者范围已经缩小到无法再缩小为止。

最后，我们需要在主函数中调用这两个函数，并输出结果。

总的时间复杂度为O(nlogn)，其中n表示产品的数量。这是因为我们需要遍历所有的产品，并对每个产品进行二分查找。总的空间复杂度为O(n)，其中n表示产品的数量。这是因为我们需要存储每个产品的初始份额数组和转化方案的邻接表。

go完整代码如下：

  1. package main
  3. import (
  4. 	"fmt"
  5. )
  7. const MAXN = 101
  9. var indegree [MAXN]int
  10. var help [MAXN]int
  11. var zeroQueue [MAXN]int
  12. var need [MAXN]int
  13. var n int
  15. func maxValue(arr []int, convert [][]int) int {
  16. 	n = len(arr)
  17. 	graph := make([][]int, n)
  18. 	for i := range graph {
  19. 		graph[i] = make([]int, 0)
  20. 	}
  21. 	t := make([]int, n)
  22. 	copy(indegree[:], t)
  23. 	for _, relation := range convert {
  24. 		for i := 1; i < len(relation); i++ {
  25. 			graph[relation[0]] = append(graph[relation[0]], relation[i])
  26. 			indegree[relation[i]]++
  27. 		}
  28. 	}
  29. 	l := arr[n-1] + 1
  30. 	r := 0
  31. 	for _, num := range arr {
  32. 		r += num
  33. 	}
  34. 	m := 0
  35. 	ans := arr[n-1]
  36. 	for l <= r {
  37. 		m = (l + r) / 2
  38. 		if ok(arr, graph, m) {
  39. 			ans = m
  40. 			l = m + 1
  41. 		} else {
  42. 			r = m - 1
  43. 		}
  44. 	}
  45. 	return ans
  46. }
  48. func ok(arr []int, graph [][]int, aim int) bool {
  49. 	l := 0
  50. 	r := 0
  51. 	for i := 0; i < n; i++ {
  52. 		help[i] = indegree[i]
  53. 		if help[i] == 0 {
  54. 			zeroQueue[r] = i
  55. 			r++
  56. 		}
  57. 	}
  58. 	t := make([]int, n)
  59. 	copy(need[:], t)
  60. 	need[n-1] = aim
  61. 	for l < r {
  62. 		cur := zeroQueue[l]
  63. 		supplement := max(need[cur]-arr[cur], 0)
  64. 		if len(graph[cur]) == 0 && supplement > 0 {
  65. 			return false
  66. 		}
  67. 		for _, next := range graph[cur] {
  68. 			need[next] += supplement
  69. 			help[next]--
  70. 			if help[next] == 0 {
  71. 				zeroQueue[r] = next
  72. 				r++
  73. 			}
  74. 		}
  75. 		l++
  76. 	}
  77. 	return true
  78. }
  80. func max(a, b int) int {
  81. 	if a > b {
  82. 		return a
  83. 	}
  84. 	return b
  85. }
  87. func main() {
  88. 	arr1 := []int{2, 0, 0, 1, 0}
  89. 	convert1 := [][]int{{4, 2, 3}, {1, 0}, {2, 1}}
  90. 	fmt.Println(maxValue(arr1, convert1))
  92. 	arr2 := []int{100, 5, 5, 0}
  93. 	convert2 := [][]int{{1, 0}, {2, 0, 1}, {3, 0, 1, 2}}
  94. 	fmt.Println(maxValue(arr2, convert2))
  95. }

在这里插入图片描述

rust完整代码如下：

  1. use std::cmp::max;
  3. const MAXN: usize = 101;
  4. static mut indegree: [i32; MAXN] = [0; MAXN];
  5. static mut help: [i32; MAXN] = [0; MAXN];
  6. static mut zeroQueue: [i32; MAXN] = [0; MAXN];
  7. static mut need: [i32; MAXN] = [0; MAXN];
  8. static mut n: i32 = 0;
  10. fn maxValue(arr: &[i32], convert: &Vec<Vec<i32>>) -> i32 {
  11.     unsafe {
  12.         n = arr.len() as i32;
  13.         let mut graph = vec![vec![] as Vec<i32>; n as usize];
  14.         for i in 0..n {
  15.             indegree[i as usize] = 0;
  16.         }
  17.         for relation in convert.iter() {
  18.             for i in 1..relation.len() {
  19.                 graph[relation[0] as usize].push(relation[i]);
  20.                 indegree[relation[i] as usize] += 1;
  21.             }
  22.         }
  23.         let mut l = arr[(n - 1) as usize] + 1;
  24.         let mut r = 0;
  25.         for num in arr.iter() {
  26.             r += *num;
  27.         }
  28.         let mut m = 0;
  29.         let mut ans = arr[(n - 1) as usize];
  30.         while l <= r {
  31.             m = (l + r) / 2;
  32.             if ok(&arr, &graph, m) {
  33.                 ans = m;
  34.                 l = m + 1;
  35.             } else {
  36.                 r = m - 1;
  37.             }
  38.         }
  39.         ans
  40.     }
  41. }
  43. fn ok(arr: &[i32], graph: &Vec<Vec<i32>>, aim: i32) -> bool {
  44.     unsafe {
  45.         let mut l = 0;
  46.         let mut r = 0;
  47.         for i in 0..n {
  48.             help[i as usize] = indegree[i as usize];
  49.             if help[i as usize] == 0 {
  50.                 zeroQueue[r as usize] = i;
  51.                 r += 1;
  52.             }
  53.         }
  54.         for i in 0..n {
  55.             need[i as usize] = 0;
  56.         }
  57.         need[(n - 1) as usize] = aim;
  58.         while l < r {
  59.             let cur = zeroQueue[l as usize] as i32;
  60.             l += 1;
  61.             let supplement = max(need[cur as usize] - arr[cur as usize], 0);
  62.             if graph[cur as usize].is_empty() && supplement > 0 {
  63.                 return false;
  64.             }
  65.             for next in graph[cur as usize].iter() {
  66.                 need[*next as usize] += supplement;
  67.                 help[*next as usize] -= 1;
  68.                 if help[*next as usize] == 0 {
  69.                     zeroQueue[r as usize] = *next as i32;
  70.                     r += 1;
  71.                 }
  72.             }
  73.         }
  74.         true
  75.     }
  76. }
  78. fn main() {
  79.     let arr1 = [2, 0, 0, 1, 0];
  80.     let convert1 = vec![vec![4, 2, 3], vec![1, 0], vec![2, 1]];
  81.     println!("{}", maxValue(&arr1, &convert1));
  83.     let arr2 = [100, 5, 5, 0];
  84.     let convert2 = vec![vec![1, 0], vec![2, 0, 1], vec![3, 0, 1, 2]];
  85.     println!("{}", maxValue(&arr2, &convert2));
  86. }

在这里插入图片描述

c++完整代码如下：

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  6. const int MAXN = 101;
  8. int indegree[MAXN];
  9. int help[MAXN];
  10. int zeroQueue[MAXN];
  11. int need[MAXN];
  12. int n;
  14. bool ok(vector<int>& arr, vector<vector<int>>& graph, int aim);
  16. int maxValue(vector<int>& arr, vector<vector<int>>& convert) {
  17.     n = arr.size();
  18.     vector<vector<int>> graph(n);
  19.     for (int i = 0; i < n; i++) {
  20.         indegree[i] = 0;
  21.     }
  22.     for (auto& relation : convert) {
  23.         for (int i = 1; i < relation.size(); i++) {
  24.             graph[relation[0]].push_back(relation[i]);
  25.             indegree[relation[i]]++;
  26.         }
  27.     }
  28.     // arr[n-1] 初始就有100份
  29.     // 101 ~ 整体累加和
  30.     int l = arr[n - 1] + 1;
  31.     int r = 0;
  32.     for (int num : arr) {
  33.         r += num;
  34.     }
  35.     int m = 0, ans = arr[n - 1];
  36.     while (l <= r) {
  37.         m = (l + r) / 2;
  38.         if (ok(arr, graph, m)) {
  39.             ans = m;
  40.             l = m + 1;
  41.         }
  42.         else {
  43.             r = m - 1;
  44.         }
  45.     }
  46.     return ans;
  47. }
  49. bool ok(vector<int>& arr, vector<vector<int>>& graph, int aim) {
  50.     int l = 0;
  51.     int r = 0;
  52.     for (int i = 0; i < n; i++) {
  53.         help[i] = indegree[i];
  54.         if (help[i] == 0) {
  55.             zeroQueue[r++] = i;
  56.         }
  57.     }
  58.     for (int i = 0; i < n; i++) {
  59.         need[i] = 0;
  60.     }
  61.     need[n - 1] = aim;
  62.     while (l < r) {
  63.         int cur = zeroQueue[l++];
  64.         int supplement = max(need[cur] - arr[cur], 0);
  65.         if (graph[cur].empty() && supplement > 0) {
  66.             return false;
  67.         }
  68.         for (int next : graph[cur]) {
  69.             need[next] += supplement;
  70.             if (--help[next] == 0) {
  71.                 zeroQueue[r++] = next;
  72.             }
  73.         }
  74.     }
  75.     return true;
  76. }
  78. int main() {
  79.     vector<int> arr1 = { 2, 0, 0, 1, 0 };
  80.     vector<vector<int>> convert1 = { { 4, 2, 3 }, { 1, 0 }, { 2, 1 } };
  81.     cout << maxValue(arr1, convert1) << endl;
  83.     vector<int> arr2 = { 100, 5, 5, 0 };
  84.     vector<vector<int>> convert2 = { { 1, 0 }, { 2, 0, 1 }, { 3, 0, 1, 2 } };
  85.     cout << maxValue(arr2, convert2) << endl;
  87.     return 0;
  88. }

在这里插入图片描述

原文链接：https://www.cnblogs.com/moonfdd/p/17787277.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Go语言热门文章

  • Golang从文件服务器获取图片显示到客户端
  • 谈谈Go语言中的内存重排
  • Golang&nbsp;模块引入及表格读写业务快速实现示例
  • 创建并使用https证书
  • golang的reflection（转）
  • TICK技术栈（一）TICK技术栈介绍
  • beego解读Cache之MemoryCache
  • go语言reflect包最佳实践之struct操作（遍历、赋值与方法调用）
  • golang中gin框架接入jwt使用token验证身份
  • Golang解析、验证、修改URL之Host、Port、Path

    • Go语言推荐文章

  • Go 互斥锁 Mutex 源码分析(二)
  • golang对遍历目录操作的优化
  • 美团VS饿了么，到底谁更胜一筹？
  • 解码 xsync 的 map 实现
  • [golang]在Gin框架中使用JWT鉴权
  • Golang 依赖注入设计哲学｜12.6K &#127775; 的依赖注入库 wire
  • 这么简单的问题都不会，那还面试什么！？
  • golang select 和外层的 for 搭配
  • Go语言的100个错误使用场景（61-68）｜并发实践
  • 实战：如何优雅的从 Skywalking 切换到 OpenTelemetry

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号