給定一個(gè)數(shù)字列表和一個(gè)目標(biāo)數(shù)字,編寫一個(gè)程序來(lái)確定是否可以通過(guò)對(duì)數(shù)字列表應(yīng)用“+-*/”運(yùn)算來(lái)計(jì)算目標(biāo)數(shù)字?你可以假設(shè) () 會(huì)在必要時(shí)自動(dòng)添加。應(yīng)在每?jī)蓚€(gè)連續(xù)數(shù)字之間放置一個(gè)運(yùn)算符。所以每個(gè)數(shù)字都必須使用。
例如,給定 {1,2,3,4} 和 21,返回 true。因?yàn)?(1+2)*(3+4)=21
Java解決方案
這是一個(gè)分區(qū)問(wèn)題,可以通過(guò)使用深度優(yōu)先搜索來(lái)解決。
public boolean isReachable(ArrayList<Integer> list, int target) {
if (list == null || list.size() == 0)
return false;
int i = 0;
int j = list.size() - 1;
ArrayList<Integer> results = getResults(list, i, j);
for (int num : results) {
if (num == target) {
return true;
}
}
return false;
}
public ArrayList<Integer> getResults(ArrayList<Integer> list,
int left, int right) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (left > right) {
return result;
} else if (left == right) {
result.add(list.get(left));
return result;
}
for (int i = left; i < right; i++) {
ArrayList<Integer> result1 = getResults(list, left, i);
ArrayList<Integer> result2 = getResults(list, i + 1, right);
for (int x : result1) {
for (int y : result2) {
result.add(x + y);
result.add(x - y);
result.add(x * y);
if (y != 0)
result.add(x / y);
}
}
}
return result;
}
以上就是關(guān)于Java 使用數(shù)字列表和算術(shù)運(yùn)算獲取目標(biāo)數(shù)字的全部?jī)?nèi)容,感謝各位的閱讀。