有一個島嶼，中間一條通路連接兩個碼頭，到兩端的碼頭才可以逃脫，通路只能過一個人。
每個人都有自己的戰斗力，自己的絕對值就是戰斗力，不同方向的人遇到后會決斗，留下的戰斗力為絕對值相減，保留到戰斗力絕對值大的人身上，比如8和-2相遇那么8 就變成6。
給定一個陣列：
#正數表示向右→
#負數表示向左←
樣例輸入：
test_cast = '[5 10 8 -8 -5]'
輸出：[5,10] 表明最后這倆可以逃出升天
test_cast = '[ -1 -5]'
輸出：[-1,-5] 表明最后這倆可以逃出升天，同向的都可以走出去，類似一秒移動一個單位那么他們都遇不到
test_cast = '[1 -1]'
輸出：[] 表明最后這倆同歸于盡
#先進行兩個方向的遍歷：
#從右到左，先看陣列末尾的正數，肯定出去了
#從左到右，看陣列頭的負數，肯定出去了
再對剩下的進行處理，我怎么感覺好像 可以用遞回，求大牛給個 樣例代碼，學習一下。
uj5u.com熱心網友回復：
test_cast = '[5 10 8 -8 -5]'下一個階段是： 8 和-8 相遇，同歸于盡
5 10 -5
再下一個 階段，10和-5 相遇 剩下5
最終兩人站點力5，5
但是要輸出【5 10】，也就是原始兩人的戰斗力
uj5u.com熱心網友回復：
看不懂你說什么？畫個圖吧！你這表達能力不適合做專案開發經理啊！只能碼農uj5u.com熱心網友回復：
沒用遞回
var arr = [5, 10, 8, -8, -5];
var res0 = arr.reduce((obj, num)=>{obj.total+=num;if(obj.total<0)obj.temp.push(num);return obj;},{total: 0,temp:[]});
var res1 = arr.reverse().reduce((obj, num)=>{obj.total+=num;if(obj.total>0)obj.temp.push(num);return obj;},{total: 0,temp:[]});
console.log(res0.temp);
console.log(res1.temp.reverse());
uj5u.com熱心網友回復：
沒有處理[ -8 -5 5 10 8]
這種有正負不會相遇的情況
uj5u.com熱心網友回復：
感謝老哥回答，我不太明白js 的編程，能說一下您的大致流程是啥么
uj5u.com熱心網友回復：
順序遍歷做加和，如果加和變成小于0，則從當前元素開始的一直到結束的元素就是向右的結果。反向遍歷做加和，如果加和變成大于0，則從當前元素開始的一直到起始的元素就是向左的結果。
uj5u.com熱心網友回復：
那如果是這樣：
[5, -10, 8, -8, -5]
最后出去的是 -10 ，-5
你這個代碼可能就不太對了
uj5u.com熱心網友回復：
代碼太亂，重新發一版，chrome瀏覽器可以F12后打開控制臺查看結果。
var exec = function(origin){
var right = origin
.reduce((ctx, item)=>{
ctx.sum += item;
if(ctx.sum < 0) ctx.res.push(item);
return ctx;
},
{sum: 0, res: []}
);
var left = origin
.reverse()
.reduce((ctx, item)=>{
ctx.sum += item;
if(ctx.sum > 0) ctx.res.push(item);
return ctx;
},
{sum: 0, res: []}
);
console.log([...right.res, ...left.res.reverse()]);
}
exec([5, 10, 8, -8, -5]);
exec([-1, -5]);
exec([1, 5]);
exec([1, -1]);
uj5u.com熱心網友回復：
你說的沒錯，確實沒考慮這種情況
uj5u.com熱心網友回復：
var exec = function(origin){
origin = origin.map(x=>{
return {
base: x,
currentRight: x,
currentLeft: x
};
});
var stackRight = [];
origin.forEach(x=>{
if(x.currentRight > 0) {
stackRight.push(x);
}
else{
while(true){
if(stackRight.length <= 0) break;
var temp = stackRight.pop();
x.currentRight += temp.currentRight;
if(x.currentRight > 0){
temp.currentRight = x.currentRight;
stackRight.push(temp);
break;
}
}
}
})
var stackLeft = [];
origin
.reverse()
.forEach(x=>{
if(x.currentLeft < 0) {
stackLeft.push(x);
}
else{
while(true){
if(stackLeft.length <= 0) break;
var temp = stackLeft.pop();
x.currentLeft += temp.currentLeft;
if(x.currentLeft < 0){
temp.currentLeft = x.currentLeft;
stackLeft.push(temp);
break;
}
}
}
})
return [...stackLeft.reverse(), ...stackRight].map(x=>x.base);
}
console.log(exec([5, 10, -8, -8, -5])); //[-8, -5]
console.log(exec([5, 10, -8, 8, -5])); //[5, 10, 8]
uj5u.com熱心網友回復：
如果有兩個人戰斗力相同呢？最終只顯示原始戰斗力的話豈不是不知道是哪個逃了出去？還是可以忽略這種情況，假設大家的初始戰斗力都不同啊？uj5u.com熱心網友回復：
同向的話，不牽扯，逆向的話，相遇就都死了啊
uj5u.com熱心網友回復：
用dijsktra演算法uj5u.com熱心網友回復：
把陣列元素映射成[
{
base: 1, //記錄原始戰力
right: 1 //記錄剩余戰力
},
{
base: -1,
right: -1
},
]
準備個空堆疊
正向遍歷
遇到大于0的元素時壓堆疊
遇到小于0的元素時
如果此時堆疊為空，啥都不做直接繼續遍歷
如果堆疊不為空，則彈出堆疊頂元素與當前元素進行相加看結果
結果大于0則把結果賦給彈出堆疊頂元素的right欄位，并且把彈出的堆疊頂元素壓回堆疊，繼續遍歷
結果小于或等于0則繼續彈出下一個堆疊頂元素繼續進行相加看結果，重復上述步驟直至堆疊為慷訓結果大于0繼續遍歷
遍歷完畢之后堆疊內的元素就是從右方逃出來的人。
左方逃出來的人同理。
兩方逃出來的人合并到一起就是結果。
uj5u.com熱心網友回復：
每天回復一次，增加可用分10分 （每天限領一次）uj5u.com熱心網友回復：
上面大神真厲害啊uj5u.com熱心網友回復：
遇到小于0的元素時
如果此時堆疊為空，啥都不做直接繼續遍歷
按你說的話了一下似乎這里啥都不做的就是從左邊逃出來的人
uj5u.com熱心網友回復：
我咋覺得一個堆疊就可以搞定uj5u.com熱心網友回復：
厲害厲害，當時沒有考慮用一些特別的資料結構uj5u.com熱心網友回復：
不錯不錯，沒有考慮到這些問題uj5u.com熱心網友回復：
直接暴力回圈啊package test.lt20;
import java.util.ArrayList;
import java.util.List;
public class Test05 {
public static void main(String[] args) {
int[] iii = {5, -10, 8, -8, -5};
List<Integer> src = new ArrayList();
List<Integer> ft = new ArrayList();
for(int i: iii) {
src.add(i);
ft.add(i);
}
for(int i = 0; i < src.size() - 1; i++) {
if(src.get(i) > 0 && src.get(i + 1) < 0) {
int tmp = ft.get(i) + ft.get(i + 1);
if(tmp > 0) {
ft.set(i, tmp);
src.remove(i + 1);
ft.remove(i + 1);
i = 0;
}else if(tmp < 0) {
ft.set(i + 1, tmp);
src.remove(i);
ft.remove(i);
i = 0;
}else {
src.remove(i + 1);
ft.remove(i + 1);
src.remove(i);
ft.remove(i);
}
}
}
System.out.println(src);
//System.out.println(ft);
}
}
uj5u.com熱心網友回復：
你說的沒錯，這樣的話只用一個堆疊并且只遍歷一遍應該就可以了
var exec = function(origin){
origin = origin.map(x=>{
return {
base: x,
current: x,
};
});
var stack = [];
origin.forEach(x=>{
if(x.current > 0) {
stack.push(x);
}
else{
while(true){
if(stack.length <= 0){
stack.push(x);
break;
}
if(stack[stack.length - 1].current < 0){
stack.push(x);
break;
}
var temp = stack.pop();
x.current += temp.current;
if(x.current > 0){
temp.current = x.current;
stack.push(temp);
break;
}
}
}
});
return stack.map(x => x.base);
}
console.log(exec([5, 10, -8, -8, -5])); //[-8, -5]
console.log(exec([5, 10, -8, 8, -5])); //[5, 10, 8]
console.log(exec([5, 8, -8, 8, -5])); //[5, 8]
uj5u.com熱心網友回復：
感覺學到了呢uj5u.com熱心網友回復：
忘置零了，改一下
import java.util.ArrayList;
import java.util.List;
public class Test05 {
public static void main(String[] args) {
int[] iii = {-50, 123, 1, 8, 7, -10, 8, -8, -5, 100};
//int[] iii = {-111, 1, -1, 2, -2, 3, -4, 5};
List<Integer> src = new ArrayList();
List<Integer> ft = new ArrayList();
for(int i: iii) {
src.add(i);
ft.add(i);
}
for(int i = 0; i < src.size() - 1;) {
if(src.get(i) > 0 && src.get(i + 1) < 0) {
int tmp = ft.get(i) + ft.get(i + 1);
if(tmp > 0) {
ft.set(i, tmp);
src.remove(i + 1);
ft.remove(i + 1);
}else if(tmp < 0) {
ft.set(i + 1, tmp);
src.remove(i);
ft.remove(i);
}else {
src.remove(i + 1);
ft.remove(i + 1);
src.remove(i);
ft.remove(i);
}
i = i == 0 ? 0 : i - 1;
continue;
}
i++;
}
System.out.println(src);
//System.out.println(ft);
}
}
uj5u.com熱心網友回復：
蠻力法解決的，沒有使用到遞回，就是判斷和遍歷下面是代碼，代碼還需要優化。
https://blog.csdn.net/zhj_1121/article/details/103178012
uj5u.com熱心網友回復：
資料里面隱藏了幾個資訊一個是當前位置，一個是問戰斗力
資料的個數代表需要移動的格子數，這就是回圈的次數，回圈這個次數，每次將位置移動1（對應到某個方向是這個方向只移0.5），將位置相同做決斗，剩下的人繼續
data = [5, -10, 8, -8, -5]
data = [5, 10, 8, -8, -5]
# data = [8, -8]
process_data = { p:[p,v,v] for p,v in enumerate(data) }
for i in range(len(data)):
# 移動位置
for k in process_data:
process_data[k][0] += 0.5 if process_data[k][2]>0 else -0.5
# 相同位置的決斗
for p in set([ process_data[k][0] for k in process_data ]):
process_item = [ k for k in process_data if process_data[k][0] == p ]
if len( process_item ) > 1:
k1, k2 = process_item
v1, v2 = process_data[k1][1], process_data[k2][1]
v = v1+v2
if v == 0:
del(process_data[k1])
del(process_data[k2])
elif abs(v1) > abs(v2):
process_data[k1][1] = v
del(process_data[k2])
else:
del(process_data[k1])
process_data[k2][1] = v
print([ process_data[k][2] for k in process_data ])
uj5u.com熱心網友回復：
把所有元素相加，得到的結果如果是正的就從左邊開始比較，如果元素絕對值比這個累加結果絕對值小或相等，就輸出存活，并將累加結果減去原數值以后繼續。如果元素比這個累加結果大，那么輸出為存活，累加值清零，繼續。如果累加值為0 結束輸出
如果得到的結果是負數，就從右邊開始。
舉例
1 、 [5 10 8 -8 -5]
所有數值累加，得到累加值絕對值 10 ，大于0 從左邊開始比較。 第一個元素5絕對值5 小于 累加值絕對值10 ，輸出存活 [5] ，累加值做減法 10-5 =5 繼續。第二個元素 10 絕對值10 比 此時的累加值絕對值 5 大，于是 輸出存活 [5,10] 累加值清零，結束。
最終輸出[5,10]
2、 [ -1 -5]
所有數值累加 ，得到累加值-6絕對值 6 ，小于0 從右邊開始比較。第一個元素 -5絕對值5，小于累加值絕對值，輸出存活[-5]，累加值做減法 6-5=1 繼續。第二個元素 -1 絕對值1 與此時的累加值絕對值1 相等，輸出存活 [-1,-5] 累加值做減法 1-1 =0，繼續。累加值為0，結束。
最終輸出 [-1,5]
3、[1 -1]
所有數值累加，累加值0，結束
最終輸出 []
uj5u.com熱心網友回復：
樓上的不對吧，如果是 [-1,1] ，這個的累加值也是0，但兩個顯然不會相遇，應該都輸出uj5u.com熱心網友回復：
有點厲害，看來這個題目的解法有很多，但是我沒弄清歸屬哪一類數學問題？uj5u.com熱心網友回復：
請謹慎發表博客，此題涉及 知名公司著作權
uj5u.com熱心網友回復：
好的，我這就刪掉(湊字數湊字數)
uj5u.com熱心網友回復：
按照題意，不會出現這種情況
uj5u.com熱心網友回復：
初步想，把和第一個元素同號的元素都壓堆疊，設計一個指標(儲存資料下標的變數)i指向第一個與首元素異號的元素。然后不斷相加堆疊頂和a[i]，結果與首元素同號就壓堆疊并i++，異號就把結果存于a[i]。若堆疊空了說明陣列剩下的能跑，若i==length，說明堆疊里的能跑。uj5u.com熱心網友回復：
[-1,1] 的這個情況是會有的，兩個人都走出去了啊
uj5u.com熱心網友回復：
那么 [1,-1,1] 這個輸入應該怎么判定？到底是右邊那個1跑了還是說這三個人都在管子左邊，-1可以在管子外面讓過所有的1,于是大家都跑了皆大歡喜？
根據題主給出的輸入規則和案例，這個一維陣列唯一能夠區分方向的就是正負分界點，并且這個分界點只能有一個。
如果非要說最左側可以有負數，最右側可以有正數，那就是在我那個演算法的之前再嵌套一層把兩端的這種情況剝離出來再說咯。
uj5u.com熱心網友回復：
1,-1,1這個就是和一個1右移，第2仆-1左移，所以相遇兩個都沒了
第3個1右移出去了
所以最終結果是1
uj5u.com熱心網友回復：
1,-1,1這個就是和一個1右移，第2仆-1左移，所以相遇兩個都沒了
第3個1右移出去了
所以最終結果是1
uj5u.com熱心網友回復：
[1,-1,1] 這個輸入應該怎么判定？到底是右邊那個1跑了
只有1 跑了
uj5u.com熱心網友回復：
1,-1,1用放格子的方法表示一下，如下所示（也就是我前面說的隱藏資訊，第幾個數字代表它所在的當前位置）
1 ------------ 第一個數
-- -1 -------- 第二個數
----------1-- 第三個數
然后移動一次
--1 ----------- 正數右移
-1 ----------- 負數左移
-------------1 正數右移
可以看到 ，移動后第1和第2個數字位置相同，也就是它們相遇，戰斗力相同，所以它們都沒了，只剩下第3個數字1，它出去了
uj5u.com熱心網友回復：
來個暴力回圈吧，有興趣的可以改成加堆疊優化def test(test_num):
test_cast = []
i=0
for n in test_num:
test_cast.append({'i':i,'ori':n,'new':n})
i+=1
while True:
flag=False
last = None
for i in test_cast:
if i['new']>0:
last=i
elif i['new']==0 or (not last and i['new']<0):
continue
else:
flag= True
if i['new']+last['new']==0:
i['new']=0
last['new']=0
elif i['new']+last['new']>0:
last['new']=i['new']+last['new']
i['new']=0
else:
i['new']=i['new']+last['new']
last['new']=0
if last['new']==0: break
if not last or not flag:
return test_cast
test_num = [5, -10, 8, -8, -5]
for i in test(test_num):
if i['new']>0 or i['new']<0:
print (i)
uj5u.com熱心網友回復：
圍觀學習下
uj5u.com熱心網友回復：
大神真多??????，??????uj5u.com熱心網友回復：
沒看懂題目，所以問下這為兄臺，為什么是8和-8相遇，10和-5相遇？也就是我沒明白這個相遇的規則是什么。謝謝
沒看懂題目，所以問下這為兄臺，為什么是8和-8相遇，10和-5相遇？也就是我沒明白這個相遇的規則是什么。謝謝
uj5u.com熱心網友回復：
def run(a):
print('a==%s'%a)
result = []
arr = []
for x in a:
if len(arr) == 0:
if x<0:
result.append(x)
else:
arr.append([x,x])
else:
if x < 0:
s = x
while s < 0:
if len(arr) == 0:
result.append(x)
break
last = arr.pop(-1)
s += last[1]
if s > 0:
last[1] = s
arr.append(last)
else:
arr.append([x,x])
result.extend([r[0] for r in arr])
print(result)
run([5, 10, 8, -8, -5])
run([-1, -5])
run([1, -1])
run([5, -10, 8, -8, -5])
a==[5, 10, 8, -8, -5]
[5, 10]
a==[-1, -5]
[-1, -5]
a==[1, -1]
[]
a==[5, -10, 8, -8, -5]
[-10, -5]
uj5u.com熱心網友回復：
https://blog.csdn.net/qq_34262886/article/details/107814976，思路在這uj5u.com熱心網友回復：
詳細的更好,或者來個圖.轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/7035.html
上一篇：求助如何實作湊數？
下一篇：Matlab求助