遮天,已完结小说排行榜,yy玄幻小说排行榜完本

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案

代碼隨想錄算法訓(xùn)練營(yíng)第三十七天|738.單調(diào)遞增的數(shù)字總結(jié)-創(chuàng)新互聯(lián)

貪心算法一、738.單調(diào)遞增的數(shù)字題目：

給定一個(gè)非負(fù)整數(shù)?N，找出小于或等于?N?的大的整數(shù)，同時(shí)這個(gè)整數(shù)需要滿足其各個(gè)位數(shù)上的數(shù)字是單調(diào)遞增。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊(cè)、網(wǎng)站空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、遂寧網(wǎng)站維護(hù)、網(wǎng)站推廣。

（當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字?x?和?y?滿足?x<= y?時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的。）

示例 1:

輸入: N = 10
輸出: 9

示例 2:

輸入: N = 1234
輸出: 1234

示例 3:

輸入: N = 332
輸出: 299

說(shuō)明: N?是在?[0, 10^9]?范圍內(nèi)的一個(gè)整數(shù)。

思路：

1、例如：98，一旦出現(xiàn)strNum[i - 1] >strNum[i]的情況（非單調(diào)遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個(gè)整數(shù)就是89，即小于98的大的單調(diào)遞增整數(shù)。

2、局部最優(yōu)：遇到strNum[i - 1] >strNum[i]的情況，讓strNum[i - 1]--，然后strNum[i]給為9，可以保證這兩位變成大單調(diào)遞增整數(shù)。

全局最優(yōu)：得到小于等于N的大單調(diào)遞增的整數(shù)。

但這里局部最優(yōu)推出全局最優(yōu)，還需要其他條件，即遍歷順序，和標(biāo)記從哪一位開(kāi)始統(tǒng)一改成9。

3、此時(shí)是從前向后遍歷還是從后向前遍歷呢？

從前向后遍歷的話，遇到strNum[i - 1] >strNum[i]的情況，讓strNum[i - 1]減一，但此時(shí)如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。

這么說(shuō)有點(diǎn)抽象，舉個(gè)例子，數(shù)字：332，從前向后遍歷的話，那么就把變成了329，此時(shí)2又小于了第一位的3了，真正的結(jié)果應(yīng)該是299。

所以從前后向遍歷會(huì)改變已經(jīng)遍歷過(guò)的結(jié)果！

那么從后向前遍歷，就可以重復(fù)利用上次比較得出的結(jié)果了，從后向前遍歷332的數(shù)值變化為：332 ->329 ->299

確定了遍歷順序之后，那么此時(shí)局部最優(yōu)就可以推出全局。

//版本1
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i >0; i--) {
            if (Integer.parseInt(strings[i])< Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i< strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("",strings));
    }
}

java版本1中創(chuàng)建了String數(shù)組，多次使用Integer.parseInt了方法，這導(dǎo)致不管是耗時(shí)還是空間占用都非常高，用時(shí)12ms，下面提供一個(gè)版本在char數(shù)組上原地修改，用時(shí)1ms的版本

//版本2
class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] >chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i< s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

二、總結(jié)

/file/tupian/20230121/貪心總結(jié)water.jpg

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：代碼隨想錄算法訓(xùn)練營(yíng)第三十七天|738.單調(diào)遞增的數(shù)字總結(jié)-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://fisionsoft.com.cn/article/csgecj.html

新聞中心

其他資訊