我的程式取一個數字并檢查每個數字，向其添加 5 并生成一個修改后的數字。現在找到最大的修改值作為結果。
例子：
輸入：
555
輸出：
5510
說明： 所有可能的組合是：
1055
5105
5510
Maximum in these is 5510.
例子：
Input : 444, output : 944.
限制條件：輸入數字的范圍可以從 0 到 100000。
這是我的代碼，適用于這個例子。
public static int process(int number) {
int n = number;
List<Integer> list = new ArrayList<>();
if (n == 0)
return 5;
while (n > 0) {
list.add(n % 10);
n /= 10;
}
int out = -1;
for (int i = list.size() - 1; i >= 0; i--) {
StringBuilder sb = new StringBuilder();
for (int j = list.size() - 1; j >= 0; j--) {
int e = list.get(j);
if (i == j) {
e = 5;
}
sb.append(e);
}
out = Math.max(out, Integer.parseInt(sb.toString()));
}
return out;
}
如何通過降低時間復雜度來改進此代碼。
uj5u.com熱心網友回復：
如果該號碼有任何大于等于 5 的數字，請選擇最右邊的此類數字。否則選擇最左邊的數字。
如果存在，我們必須選擇一個 >= 5 的數字，因為這會給我們帶來一個額外的數字，并將數字增加更多，而任何小于 5 的數字都不會給我們帶來額外的數字。我們選擇最右邊的，因為我們的新數字將是 1x，我們希望 1 盡可能靠右。
如果所有數字都 < 5，那么 5 只會增加它應用的任何數字，我們希望對最左邊的數字進行。
所以數字數量的線性時間：掃描數字 >= 5，然后修改你找到的最后一個數字，或者如果你沒有找到第一個數字。
uj5u.com熱心網友回復：
如果不解決char/ String/StringBuilder可能是這樣的：
- 使用標志
found5來檢測第一次出現digit >= 5 - 當
digit >= 5檢測到第一個時，加 5，重置標志，并使用額外的移位power - 在主回圈體??中，通過加法計算結果
power * digit，將 n 除以 10，乘以power10 * shift - 回圈完成后，檢查標志并將 5 添加到最左邊的數字
private static int numAnd5(int n) {
boolean found5 = false;
int result = 0;
int power = 1;
while (n > 0) {
int shift = 1;
int digit = n % 10;
if (!found5 && digit >= 5) {
found5 = true;
digit = 5;
shift = 10;
}
result = power * digit;
power *= 10 * shift;
n /= 10;
}
if (!found5) {
result = 5 * Math.max(1, power / 10);
}
return result;
}
測驗：
for (int x : new int[]{0, 1, 2, 7, 10, 14, 16, 61, 125, 153, 111, 145071, 4321023 }) {
System.out.println(x " -> " numAnd5(x));
}
輸出：
0 -> 5
1 -> 6
2 -> 7
7 -> 12
10 -> 60
14 -> 64
16 -> 111
61 -> 111
125 -> 1210
153 -> 1103
111 -> 611
145071 -> 1450121
4321023 -> 9321023
uj5u.com熱心網友回復：
以下應將其從輸入中的字符數減少O(n^2)到O(n)where n。
請注意，我不了解 Java 并且目前無法訪問 IDE，因此以下是未經測驗的 C#/Java 類偽代碼：
public static int process(int number) {
int n = number;
List<Integer> list = new ArrayList<>();
if (n == 0)
return 5;
while (n > 0) {
list.add(n % 10);
n /= 10;
}
// convenient list of powers of 10
List<Integer> powers = new ArrayList<>(list.size);
n = 1;
for (int i = powers.size() - 1; i >= 0; i--) {
powers[i] = n;
n *= 10;
}
int out = -1;
int top = 0;
int bottom = number;
for (int i = list.size() - 1; i >= 0; i--) {
//StringBuilder sb = new StringBuilder();
int curr = list[i] * power[i];
bottom -= curr;
int newTop = top;
int newCurr = (list[i] 5) * power[i];
if (list[i] 5 > 9) {
newTop *= 10;
}
out = Math.max(out, newTop newCurr bottom);
top = curr;
}
return out;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325465.html
上一篇：MySQL 學習筆記（五）