我一直在解決一個面試問題。目標是從長度未知（不能使用.length）的陣列中找到特定元素并回傳步數，但是對于長度為n的陣列，保證元素從0到n-1，沒有重復。例如，如果陣列的長度為 5，則元素為 {0, 1, 2, 3, 4} 但順序可能不同。附加要求是沒有回圈，沒有靜態/全域變數，沒有輔助函式，傳入的唯一引數是陣列 int[] arr 和目標值 int x，不允許額外的引數，陣列保持不變操作已經完成。
//So you can only write in the body of the following method, no outside variables nor methods could be used.
private int findElement (int[] arr, int x) {
}
到目前為止我得到的是，由于元素保證為 0 到 n-1，我可以使用目標數字作為索引并回傳陣列查看數字arr[x]是否等于數字x I想。如果不是，我將這個數字arr[x] 設為我的新索引，重復直到找到目標值。
int[] arr = {4, 1, 0, 2, 3}
int target = 3;
arr[3] = 2; //take target as the initial index
arr[2] = 0;
arr[0] = 4;
arr[4] = 3; //we got the number we want
//steps total is 3 since the question says the first time doesn't count.
問題：我試圖通過遞回來解決這個問題，但是由于我總是將以下值與初始引數值進行比較，因此在上述情況下我總是想找到 3。所以如何在沒有靜態變數或額外引數的情況下存盤該資訊是我的大問題。有沒有其他方法可以存盤初始引數值并將其傳遞給整個程序？
private int findElement(int [] arr, int x) {
int actualN = arr[x];
if (actualN == **???**) { //can't be x cuz x is changing but I always want 3
return 0;
} else {
return findElement(arr, arr[x]) 1;
}
}
最好使用 Java 任何提示或幫助將不勝感激。
uj5u.com熱心網友回復：
可能這應該作業：
private int findElement(int [] arr, int x) {
int currValue = arr[x], returnValue;
if(arr[x]>0)
arr[x] = 0;//setting the actual element of the array to 0
else
arr[x]--;// decrementing the search index so it goes from 0-> -1 -> -2 -> -3...
if(Math.abs(arr[-arr[x]]) == x)//We check if the number is at our search index...
returnValue = 0;
else
returnValue = findElement(arr, x) 1;
arr[x] = currValue;//We take the value of the index from when the function was called and then reassign it to the same index after our work with it is done.
return returnValue;
}
由于陣列只在執行后必須相同，并且執行期間的狀態無關緊要，因此這可能有效。注意：我沒有對此進行詳細的測驗，所以請在提交之前測驗代碼
uj5u.com熱心網友回復：
你快到了
// t is the target number, o is teh array offset
static int find(int [] arr, int t, int o) {
if (arr[o] == t)
return o;
return find(arr, t, o 1);
}
和
static void Main(string[] args) {
int[] arr = { 4, 1, 0, 2, 3 };
int target = 3;
int x = find(arr, 3, 0);
}
如果只允許 2 個引數 - 我錯過了
在 c
static int* find(int* arr, int t) {
if (*arr == t)
return arr;
return find(arr 1, t);
}
int main() {
int arr[] = {4, 1, 0, 2, 3};
int target = 2;
int x = find(arr, target) - arr;
}
在c#中
static unsafe int* find(int * arr, int t) {
if (*arr == t)
return arr;
return find(arr 1,t);
}
static void Main(string[] args) {
int[] arr = { 4, 1, 0, 2, 3 };
int target = 3;
unsafe {
fixed (int * p = &arr[0]) {
int x = (int)(find(p, target) - p);
}
}
}
uj5u.com熱心網友回復：
我假設arr可以修改，只要在獲得答案后保持不變。
因為只有“最好”的答案是用 Java（而且我不知道 Java），所以我將用 Ruby 提供一個解決方案。憑借其偽代碼外觀和添加的注釋，不熟悉 Ruby 的讀者應該能夠進行計算。
具體來說，我將一個元素附加到給定陣列，該元素等于要檢查的陣列的當前元素的索引（最初為零）。如果該元素等于目標值，我們回傳遞回鏈，最初回傳零，然后在鏈的每個后續點加一。在回傳所需的計數之前doit，洗掉陣列的最后一個元素以將陣列恢復為其初始值。
如果由陣列的最后一個元素（當前索引）索引的陣列值不等于目標值，則陣列的最后一個元素遞增 1，并遞回呼叫該方法。
def doit(arr,target)
arr << 0 # append the index 0 to arr
n = recurse(arr, target)
arr.pop # remove the last element of arr
n
end
def recurse(arr, target)
return 0 if arr[arr[-1]] == target
arr[-1] = 1 # increment last value of arr by 1
1 recurse(arr, target)
end
arr = [4, 1, 0, 2, 3]
doit(arr, 4) #=> 0
doit(arr, 1) #=> 1
doit(arr, 0) #=> 2
doit(arr, 2) #=> 3
doit(arr, 3) #=> 4
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452516.html
上一篇：R：定制旅行商問題