[LeetCode] 556. Next Greater Element III

_ang 發布于2019-08-16 13:47 / 2695人閱讀

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

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72322.html

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

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

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

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

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

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

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

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

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

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

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