[LeetCode] 556. Next Greater Element III

_ang 發(fā)布于2019-08-16 13:47 / 2686人閱讀

Problem

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

Example 3:

Input: 123987
Output: 127389

Solution

class Solution {
    public int nextGreaterElement(int n) {
        char[] num = (n+"").toCharArray();
        int i;
        for (i = num.length-1; i > 0; i--) {
            if (num[i-1] < num[i]) break;
        }
        //when all digits are in decreasing order, no greater num
        if (i == 0) return -1; 
        
        //otherwise we get the last increasing digit: num[i-1]
        //and loop to the end finding the smallest greater digit than num[i-1]
        int smallestGreaterIndex = i;
        int lastIncreasing = num[i-1];
        for (int j = i+1; j < num.length; j++) {
            if (num[j] > lastIncreasing && num[j] <= num[smallestGreaterIndex]) {
                smallestGreaterIndex = j;
            }
        }
        //123987 -> lastIncreasing = 3, smallestGreaterIndex = 5
        //swap 3 and 7 -> 127983
        char temp = num[i-1];
        num[i-1] = num[smallestGreaterIndex];
        num[smallestGreaterIndex] = temp;
        
        //reorder 983 to 389 -> 127389
        Arrays.sort(num, i, num.length);
        
        //parse to long to avoid overflow
        long val = Long.parseLong(new String(num));
        return val > Integer.MAX_VALUE ? -1 : (int) val;
    }
}

GPU云服務(wù)器云服務(wù)器 Greater III Element LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/72322.html

相關(guān)文章

Leetcode PHP題解--D52 496. Next Greater Element I

摘要：題目鏈接題目分析給定兩個(gè)數(shù)組，其內(nèi)元素不重復(fù)。數(shù)組是數(shù)組的子集，返回每個(gè)在數(shù)組中的元素在數(shù)組對(duì)應(yīng)位置以右最大的元素。思路只能逐個(gè)遍歷吧。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D52 496. Next Greater Element I 題目鏈接 496. Next Greater Element I 題目分析給定兩個(gè)數(shù)組，其內(nèi)元素不重復(fù)。數(shù)組1是數(shù)組2的子集，返回每個(gè)...

only_do 2019-07-01 12:44 評(píng)論0 收藏0
前端 | 每天一個(gè) LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

張漢慶 2019-08-23 13:42 評(píng)論0 收藏0
13. 羅馬數(shù)字轉(zhuǎn)整數(shù)-----leetcode刷題（python解題）

摘要：題目羅馬數(shù)字包含以下七種字符，，，，，和。字符數(shù)值例如，羅馬數(shù)字寫做，即為兩個(gè)并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。同樣地，數(shù)字表示為。給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。 [TOC] 題目羅馬數(shù)字包含以下七種字符: I， V， X， L，C，D 和 M。字符數(shù)值 I 1 V 5 X ...

Gu_Yan 2019-07-31 10:38 評(píng)論0 收藏0
LeetCode707：設(shè)計(jì)鏈表 Design Linked List

摘要：愛寫設(shè)計(jì)鏈表的實(shí)現(xiàn)。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性和。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。將值為的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。如果等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個(gè)節(jié)點(diǎn)。操作次數(shù)將在之內(nèi)。愛寫bug (ID:iCodeBugs) 設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是...

iliyaku 2019-08-16 18:34 評(píng)論0 收藏0
LeetCode707：設(shè)計(jì)鏈表 Design Linked List

摘要：愛寫設(shè)計(jì)鏈表的實(shí)現(xiàn)。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性和。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。將值為的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。如果等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個(gè)節(jié)點(diǎn)。操作次數(shù)將在之內(nèi)。愛寫bug (ID:iCodeBugs) 設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是...

FullStackDeveloper 2019-07-31 11:28 評(píng)論0 收藏0