萌新的我遇到了一道算法, 苦手求大佬

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2103 天前的主题，其中的信息可能已经有所发展或是发生改变。

需要将借款与还款作配对, 借款与还款是是多对多关系, 通俗说明:借款与还款先后进行匹配, 多余部分匹配到对应的下一笔上,示例 loan = [5000, 4000, 1000]; repay = [2000, 4000,3000]; 则输出

relation = [{
    loanId: 0,
    loanAmount: 5000,
    repay: [{
    	repayId: 0,
        repayAmount:2000
    }, {
    	repayId: 1,
        repayAmount:3000
    }]
}, {
    loanId:1,
    loanAmount:4000,
    repay: [{
    	repayId:1,
        repayAmount: 1000
    }, {
    	repayId:2,
        repayAmount:3000
    }]
}, {
    loanId:2,
    loanAmount:1000,
    repay:[]
}]

31 条回复 • 2019-02-19 23:22:24 +08:00

awesomelei

2019-02-19 15:16:36 +08:00

以上的 xxxxId 指的是数组的索引编号

awesomelei

2019-02-19 15:19:12 +08:00

这种匹配有什么好的算法吗? 劳烦大佬们给点关键词线索也行, 数据源 loan 跟 repay 是固定的, 不考虑动态问题

yesterdaysun

2019-02-19 15:25:42 +08:00

loan 的和是 10000, repay 的和是 9000, 是题有问题吗? 还是可能会出现不对等的情况?

dark3212

2019-02-19 15:27:37 +08:00

两个数组都取第一个值，分别记录到借款总和变量、还款总和变量。
哪个大就从另一个数组取下一个值，一直循环到取不出值为止。

hinate

2019-02-19 15:32:40 +08:00

@yesterdaysun 看题目和输出，是有不对等的。不对等的部分生成了一个新的 loanAmount

shylockhg

2019-02-19 15:37:58 +08:00

先把 load[0]赋值到 current_load ；
然后 current_load = current_load - repay，大于零换下一个 repay，等于零环下一个 load，负数说明数据错误。

shylockhg

2019-02-19 15:39:48 +08:00

数组是时序排列？

shylockhg

2019-02-19 15:40:37 +08:00

话说你们借钱都不收利息么

awesomelei

2019-02-19 15:49:55 +08:00

@shylockhg 这里还得考虑到用户的还款可能不仅仅针对 1 笔的, 比如 5000, 4000, 用户先还了 8000, 再还 1000, 8000 对应的可能是两笔, 数组是时序排的,

shylockhg

2019-02-19 15:51:17 +08:00

@awesomelei 那我这个没问题啊

shylockhg

2019-02-19 15:51:50 +08:00

@awesomelei 哦看错了

awesomelei

2019-02-19 15:52:50 +08:00

@dark3212 好想法

murmur

2019-02-19 15:56:48 +08:00

@shylockhg 互联网金融本金都不还的

reus

2019-02-19 16:01:18 +08:00

两个数组，比较第一个元素的大小，把小的移除，把大的减去小的
重复这个步骤，直到其中一个数组为空
[5 4 1] [2 4 3]
移除 2 => [3 4 1] [4 3]
移除 3 => [4 1] [1 3]
移除 1 => [4 1] [3]
移除 3 => [1 1] []
把每一步的信息按 loanID 分组即可。

GeruzoniAnsasu

2019-02-19 16:01:26 +08:00

https://pastebin.ubuntu.com/p/4pbNGVGBk2/

awesomelei

2019-02-19 16:23:24 +08:00

@GeruzoniAnsasu V 站都是实干派, 为你点赞

abeholder

2019-02-19 16:28:17 +08:00

直接贴个 js 代码

const loan = [5000, 4000, 1000];
const repay = [2000, 4000, 3000];

let relation = [];

let loanCount = 0;
let repayCount = 0;
let index = 0;
for (;index < loan.length; index++) {
let json = {};
json.loanId = index;
json.loanAmount = loan[index];
json.repay = [];
json.repay.push({"repayId" : index, "repayAmount" : repay[index] - (loanCount - repayCount)});
loanCount += loan[index];
repayCount += repay[index];
json.repay.push({"repayId" : index + 1, "repayAmount" : loanCount - repayCount})
relation.push(json);
}
console.log(relation)

awesomelei

2019-02-19 16:29:59 +08:00

@reus 这里最后, 把每一步的信息按 loanId 分组不是特别明白

awesomelei

2019-02-19 16:34:46 +08:00

@abeholder 老弟, 把 repay = [6000, 4000, 3000] 代入, 这段程序可能不符合题意了嗷

abeholder

2019-02-19 16:37:47 +08:00

@awesomelei ？
哪里不符合，还的比欠的还多不应该是负数？

abeholder

2019-02-19 16:39:00 +08:00

@awesomelei 你这个用例最后结果 - 3000 难道不对吗？

awesomelei

2019-02-19 16:41:11 +08:00

以这个为例子
```
const loan = [5000, 4000, 1000];
const repay = [6000];
```
看下输出, 有些 loan 对应的可能还是 NaN 的类型
@abeholder

awesomelei

2019-02-19 16:41:58 +08:00

@abeholder 当我举措例子, 以 const repay = [6000]为准= =抱歉

awesomelei

2019-02-19 16:45:42 +08:00

@abeholder 不合题意的在于第一笔 repay 如果大于第一笔 loan, 可能出现将负数 loan 添加进去, 这边还有个隐藏要求是,不显示负数, 到最后一轮循环匹配不上的数目就结束= =

abeholder

2019-02-19 16:47:59 +08:00

@awesomelei 所以 [6000] 这个用例的输出结果是？

awesomelei

2019-02-19 16:52:54 +08:00

@abeholder
relation = [{
loanId: 0,
loanAmount: 5000,
repay: [{
repayId: 0,
repayAmount:5000
}
}, {
loanId:1,
loanAmount:4000,
repay: [{
repayId:0,
repayAmount: 1000
}]
}, {
loanID:2,
loanAmount:1000,
repay:[]
}]

awesomelei

2019-02-19 16:56:05 +08:00

@abeholder
```
relation = [{
loanId: 0,
loanAmount: 5000,
repay: [{
repayId: 0,
repayAmount:5000
}]
}, {
loanId:1,
loanAmount:4000,
repay: [{
repayId:0,
repayAmount: 1000
}]
}, {
loanId:2,
loanAmount:1000,
repay:[]
}]
```

abeholder

2019-02-19 16:58:50 +08:00

@awesomelei 好麻烦啊，不会 = =

awesomelei

2019-02-19 17:08:21 +08:00

@dark3212 对了, 但这样好像没有差额的概念了, 这里还可能需要把一笔还款拆分成多笔, 加入到 loan 中,需要具体的金额

dark3212

2019-02-19 17:42:28 +08:00

变换下思路就行啊，
思路给你了，多 debug 啥都就有了。
假设借款总额变量是 loanSum，还款总额变量是 repaySum。

当前循环借款更大的情况
nextRepay = 取下一个还款
if(loanSum>repaySum+nextRepay)
差额 = nextRepay
else
差额= loanSum - repaySum
repaySum += nextRepay
继续循环

还款更大的情况
nextLoan = 取下一个借款
if(loanSum + nextLoan >repaySum)
差额 =repaySum - loanSum
else
差额= nextLoan
loanSum += nextLoan
继续循环

injy

2019-02-19 23:22:24 +08:00 via Android

是不是可以直接按照题意:
tmpNum=repay1

if(loan1>tmpNum)
arr1[]=tmpNum
tmpNum+=repay2
else
arr1=loan1-(tmpNum-repay1)
tmpNum-=loan1

return arr1