Re: [閒聊] 每日leetcode

[sixB (6B)]

670.

swap 2 digit to get max

看到這個直覺開bitset

把leading 1 之後的第一個0跟最後一個1換

能換的話

換完才發現他是要直接換數字

超姆咪==

## 真的解

從屁股掃回來

記0-9最大的position

再從頭開始跑

如果比當前數字大的pos

也比i大就能換

也比大熊

換完就returnㄌ

class Solution {
public:
    int maximumSwap(int num) {
        string s =  to_string(num);
        int pos[10] = {0};
        int len = s.length();
        for(int i = len - 1; i >= 0; i--){
            int n = s[i] - '0';
            pos[n] = max(pos[n], i);
        }
        bool sw = false;
        for(int i = 0; i < len and !sw; i++){
            int n = s[i] - '0';
            for(int j = 9; j > n and !sw; j--){
                if(pos[j] > i) {
                    swap(s[ pos[j] ], s[i]);
                    sw = true;
                }
            }
        }
        return stoi(s);
    }
};

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729131231.A.C47.html
推 DJYOSHITAKA: 大師