美文网首页
【教3妹学算法-每日3题(1)】下一个更大元素 III

【教3妹学算法-每日3题(1)】下一个更大元素 III

作者: 程序员小2 | 来源:发表于2022-07-05 09:04 被阅读0次

    插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
    坚持不懈,越努力越幸运,大家一起学习鸭~~~

    3妹

    3妹:2哥,今天周日,出去玩一玩,爬爬山怎么样。
    2哥:还出去玩呢,现在全国疫情又反复了, 前段时间上海疫情刚控制住,现在宿州泗县和无锡疫情又爆发了,还是注意一些,不要随便出去走动了。
    3妹:哦,是哦,普通公民能做的就是尽量居家,不能防疫添麻烦。
    2哥:对,还是在家打会儿游戏吧,来,带你打野。
    3妹:切,我对打游戏没兴趣,我还是做几道题,然后看我的韩剧吧

    讲课

    题目:

    给你一个正整数 n ,请你找出符合条件的最小整数,其由重新排列 n 中存在的每位数字组成,并且其值大于 n 。如果不存在这样的正整数,则返回 -1 。

    注意 ,返回的整数应当是一个 32 位整数 ,如果存在满足题意的答案,但不是 32 位整数 ,同样返回 -1 。

    示例 1:

    输入:n = 12
    输出:21
    示例 2:

    输入:n = 21
    输出:-1

    提示:

    1 <= n <= 2^31 - 1

    思路:

    我们从 n 开始,不断比较其最低位数字和次低位数字的大小,如果次低位数字不低于最低位数字,则移除最低位数字,继续循环。循环结束后的 n 就对应着方法一的下标 i,即nums 的前 i+1个字符。

    对于方法一中下标 j 的计算也是同理。

    最后,将 +1 之后的部分反转,即得到下一个整数。如果中途计算会溢出,则返回 -1。

    java代码:

    class Solution {
        public int nextGreaterElement(int n) {
            int x = n, cnt = 1;
            for (; x >= 10 && x / 10 % 10 >= x % 10; x /= 10) {
                ++cnt;
            åc}
            x /= 10;
            if (x == 0) {
                return -1;
            }
    
            int targetDigit = x % 10;
            int x2 = n, cnt2 = 0;
            for (; x2 % 10 <= targetDigit; x2 /= 10) {
                ++cnt2;
            }
            x += x2 % 10 - targetDigit; // 把 x2 % 10 换到 targetDigit 上
    
            for (int i = 0; i < cnt; ++i, n /= 10) { // 反转 n 末尾的 cnt 个数字拼到 x 后
                int d = i != cnt2 ? n % 10 : targetDigit;
                if (x > Integer.MAX_VALUE / 10 || x == Integer.MAX_VALUE / 10 && d > 7) {
                    return -1;
                }
                x = x * 10 + d;
            }
            return x;
        }
    }
    

    相关文章

      网友评论

          本文标题:【教3妹学算法-每日3题(1)】下一个更大元素 III

          本文链接:https://www.haomeiwen.com/subject/sjulbrtx.html