我正在解決以下問題：
數字n作為輸入給出
看看它是否是單調的？
單調數被稱為 - 單調減少或單調增加的數字。例如：110、111、122、123、455、554。- 是單調的。101、121、231是非單調的。
約束：不能使用陣列和字串。
我寫了一個函式來檢查單調遞增的數字：
public static boolean isMonotonic(int num) {
int n = num; // Copy of num to be modified
int b = (n/10)%10; // Step for a number if it is monotone
n /= 10;
if (num < 100) return true; // all two-digit numbers are monotonic
while (n > 0 && n > b) {
if ((n/10)%10 != b){
return false;
}
n /= 10;
}
return true;
}
但我不知道如何為單調遞減的數字制作函式。
uj5u.com熱心網友回復：
因為根據您的要求，有效單調數的數字可以相等（例如110，455），在檢查數字時，降序和升序很容易混淆。并且我們也有所有數字都相等的情況，即數字既不增加也不減少，但它被認為是一個有效的單調數（例如111）。
我想出了以下演算法：
當一個數字可以被認為是單調的時，保持三個
boolean標志代表三種情況，如上所述。要初始化這些標志，我們需要訪問給定數字的第一個和最后一個數字。因為相鄰的數字可以相等，所以只有第一個和最后一個數字的比較才能提供有關數字預期排序的足夠資訊。以下是所有三個標志的初始化方式：isEqual = first == last;isIncreasing = first >= last;isDeceasing = first <= last;
維護一個保存前一個數字的值的變數。
遍歷給定數字的數字并比較下一個和前一個數字。如果條件與標志一致 - 繼續進一步迭代，否則使回傳的數字無效
false。
作為一個小的優化，我們可以洗掉所有小于 then 的數字，100因為根據要求是單調的。
這就是實作的樣子：
public static boolean isMonotonic(int num) {
// NOTE: use Math.abs() to adjust the input if negative values are allowed
if (num <= 100) return true; // early kill for small number
int last = num % 10;
int first = num / (int) Math.pow(10, (int) Math.log10(num));
int prev = last;
num /= 10;
boolean isEqual = isEqual(first, last);
boolean isIncreasing = isIncreasing(first, last);
boolean isDeceasing = isDecreasing(first, last);
while (num > 0) {
int next = num % 10;
if (isEqual && !isEqual(next, prev)) return false; // next is passed before previous because we are iterating from right to left
if (isIncreasing != isIncreasing(next, prev) && isDeceasing != isDecreasing(next, prev)) {
return false;
}
prev = next;
num /= 10;
}
return true; // the number is proved to be monotonic
}
public static boolean isEqual(int left, int right) {
return left == right;
}
public static boolean isIncreasing(int left, int right) {
return left <= right;
}
public static boolean isDecreasing(int left, int right) {
return left >= right;
}
main()
public static void main(String[] args) {
System.out.println("Digits are equal:");
System.out.println(111 " " isMonotonic(111));
System.out.println(333 " " isMonotonic(333));
System.out.println(999 " " isMonotonic(999));
System.out.println("Increasing:");
System.out.println(189 " " isMonotonic(189));
System.out.println(577 " " isMonotonic(577));
System.out.println(779 " " isMonotonic(779));
System.out.println("Decreasing");
System.out.println(775 " " isMonotonic(775));
System.out.println(831 " " isMonotonic(831));
System.out.println(99333 " " isMonotonic(99333));
System.out.println("Non-monotonic");
System.out.println(101 " " isMonotonic(101));
System.out.println(45551 " " isMonotonic(45551));
System.out.println(95559 " " isMonotonic(95559));
}
輸出：
Digits are equal:
111 true
333 true
999 true
Increasing:
189 true
577 true
779 true
Decreasing
775 true
831 true
99333 true
Non-monotonic
101 false
45551 false
95559 false
uj5u.com熱心網友回復：
在不處理n/10's 的情況下解決此問題的一種簡單方法是轉換num為字串
public static boolean isMonotonicDecreasing(int num) {
//First, convert num into a string
String numString = String.valueOf(num);
//Iterate across numString - 1
for (int i = 0; i < numString.length() - 1; i ){
//If the current digit (character at index i, converted to integer)
//is less than the next digit, return false
if ((int)numString.charAt(i) < (int)numString.charAt(i 1)){
return false;
}
}
//Return true after reaching end of loop
return true;
}
uj5u.com熱心網友回復：
要比較數字是上升還是下降，請比較前一個數字和當前數字。每次迭代，我們必須將前一個數字更新為當前數字，并將當前數字移動到下一個數字，并將整數中的數字向右移動。
您需要兩個布爾變數：跟蹤單調遞增和單調遞減。最后，回傳兩個布爾變數的 OR。
static boolean isMonotonic(int n){
boolean inc = true; //assume monotonic increasing
boolean dec = true; //assume monotonic decreasing
int prev = n%10; //previous is right most digit
n/=10; //shift digits to the right
while(n > 0){
int cur = n%10; //current is right most digit
inc &= prev >= cur; //is monotonic increasing ?
dec &= prev <= cur; //is monotonic decreasing ?
prev = cur; //previous is set to current digit
n/=10; //shift digits to the right.
}
return inc || dec;
}
uj5u.com熱心網友回復：
讓我們介紹一下int order， 1如果我們有遞增序列，-1在遞減序列的情況下，0如果我們到目前為止還不知道（例如...111111）。那么我們應該做的就是覆寫數字：
public static bool isMonotonic(int num) {
if (num > -100 && num < 100)
return true;
int order = 0;
int prior = num % 10;
for (; num != 0; num /= 10) {
int current = num % 10;
if (order > 0 && current < prior || order < 0 && current > prior)
return false;
if (current != prior)
order = Math.sign(current - prior);
prior = current;
}
return true;
}
另一種可能性是嘗試找到反例：一個大于其鄰居或小于其鄰居的數字。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/520207.html
標籤：爪哇算法数学