我一直在嘗試制作一個簡單的函式來檢查一個陣列是否與另一個陣列 reversed相同。
例如，比較[0, 1, 2]and [2, 1, 0] 會回傳true，但比較[0, 1, 2]and[2, 1, 1]會回傳false。
我也在嘗試使用分而治之的方法，遞回地使用函式。
這是我撰寫的代碼，但它沒有按預期作業，false在它應該回傳時回傳true：
public class ReverseCheck {
// Check if an array is the reverse of another array
// Use divide and conquer
public static boolean isReverse(int[] a, int[] b) {
if (a.length != b.length) {
return false;
}
return isReverse(a, b, 0, a.length - 1);
}
private static boolean isReverse(int[] a, int[] b, int start, int end) {
if (start == end) {
return a[start] == b[end];
}
int mid = (start end) / 2;
return isReverse(a, b, start, mid) && isReverse(a, b, mid 1, end);
}
public static void main (String[] args) {
int[] a = {1, 2, 3, 4, 5, 6};
int[] b = {6, 5, 4, 3, 2, 1};
int[] c = {1, 2, 3, 4, 5, 6, 7};
int[] d = {6, 5, 5, 3, 2, 1};
System.out.println(isReverse(a, b)); // Should return true, returns false
System.out.println(isReverse(a, c)); // Should return false, returns false
System.out.println(isReverse(a, d)); // Should return false, returns false
}
}
uj5u.com熱心網友回復：
您的解決方案中有幾個問題：
基本案例有一個邏輯缺陷。回傳值表示
a[start] == b[end]索引相等時的比較結果。這不是驗證一個陣列是否是另一個陣列的反向副本的正確方法。讓我們考慮兩個陣列a = [1, 2, 3]和b = [3, 2, 1]。我們必須檢查是否a[0] == b[2]和。正如您所看到的那樣，索引相等的情況僅發生一次并且僅在長度為奇數時，如果長度為偶數，則所有元素對中的索引將不同。a[1] == b[1]a[2] == b[0]第二個問題是您采取的總體方法。對于這個問題，我們必須檢查所有的值對。分而治之的方法在這里是徒勞的，因為我們不能減少操作量，在最壞的情況下，每對值都需要進行比較。
我建議通過在每次方法呼叫時簡單地移動兩個陣列的索引來解決這個問題，而不使用分而治之，因為我們無法從中受益。1
首先，讓我們修復遞回的基本情況。
遞回應該終止的情況有兩種：當對中的值不匹配并且到達最后一個有效索引時。
第一種情況的條件，當對應于當前索引的值不相等時，將看起來：
if (a[start] != b[end]) return false;
第二部分可能會這樣寫：
if (start == a.length - 1) return a[start] == b[end];
要么
if (start == a.length - 1) return true;
兩者的含義幾乎相同——我們已經設法比較了所有的值對（或者最后一對被比較）。第一個版本稍微好一點，它會節省一個方法呼叫。
在遞回的情況下，我們只是通過傳遞start遞增的 by1和end遞減的 by來呼叫方法1。
private static boolean isReverse(int[] a, int[] b, int start, int end) {
if (start == a.length - 1) {
return a[start] == b[end];
}
if (a[start] != b[end]) {
return false;
}
return isReverse(a, b, start 1, end - 1);
}
main()
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6};
int[] b = {6, 5, 4, 3, 2, 1};
int[] c = {1, 2, 3, 4, 5, 6, 7};
int[] d = {6, 5, 5, 3, 2, 1};
System.out.println(isReverse(a, b)); // Should return true, returns false
System.out.println(isReverse(a, c)); // Should return false, returns false
System.out.println(isReverse(a, d)); // Should return false, returns false
}
輸出
true
false
false
修復最初的分而治之版本
As I've said earlier, the problem resides in the base case. Instead of comparing the elements at the same position a[start] == b[end] (when start equals to end it will not make sense), we need to adjust the end index:
if (start == end) {
return a[start] == b[(b.length - 1) - end];
}
That's the only change that needs to be applied to the original code listed in the question.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/455701.html
上一篇：無法理解遞回模式及其函式呼叫