[LeetCode] 556. Next Greater Element III

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

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云服務器 Greater III Element LeetCode

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

轉載請注明本文地址：http://systransis.cn/yun/72322.html

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

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

only_do 2019-07-01 12:44 評論0 收藏0
前端 | 每天一個 LeetCode

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

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

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

Gu_Yan 2019-07-31 10:38 評論0 收藏0
LeetCode707：設計鏈表 Design Linked List

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

iliyaku 2019-08-16 18:34 評論0 收藏0
LeetCode707：設計鏈表 Design Linked List

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

FullStackDeveloper 2019-07-31 11:28 評論0 收藏0