casyup.me@outlook.com

0%

leetcode/31ZNextPermutation

Posted on

31 Next Permutation

简单来说就是找下一个比当前数字更大的数, 如果没有, 就重新排序

my code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        size_t size = nums.size();

        for (int i = size - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                int i2 = nums[i - 1];
                vector<int>::iterator it = nums.end();
                while ( ++i2 < size ) {
                    if ( ( it = find(nums.begin() + i + 1, nums.end(), i2) ) != nums.end() )
                        break;
                }

                if ( it != nums.end() ) {
                    *it ^= nums[i - 1];
                    nums[i - 1] ^= *it;
                    *it ^= nums[i - 1];
                } else {
                    nums[i] ^= nums[i - 1];
                    nums[i - 1] ^= nums[i];
                    nums[i] ^= nums[i - 1];
                }

                sort(nums.begin() + i, nums.end());
                return;
            }
        }

        return sort(nums.begin(), nums.end());
    }
};

思路很简单, 从右到左找到第一个”不和谐”的点B (该点数字比前面的数字A大)

然后拿A, 从这个不和谐的点B往右找下一个比A大的数, 交换

之后重排序B右边的数字(包括B)

emmmm… 结果不太好呢…

dalao’s code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static const int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();
// 很 6 啊, 这里实际是一个值, 全局的 static 变量, 他的执行会在 main 之前 
// 会求值 lambda 表达式中的内容, 而值并不是主要的目的, 甚至不是目的  
// 他是想调用其中的加速流操作的函数, 所以lambda最后有个()运算符, 果然我是条咸鱼...

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end()); // emm. 这是标准库函数...
    }
};

里面有一些我看不懂的东西, 涉及到 c++ 的流

ios::sync_with_stdio(false);    // 是否兼容printf
cin.tie(nullptr);        // 在每一次输入之前, 不要让他调用 cout 的 flushing

网上查了一下, 加速流的输入输出…

http://www.hankcs.com/program/cpp/cin-tie-with-sync_with_stdio-acceleration-input-and-output.html

https://www.geeksforgeeks.org/fast-io-for-competitive-programming/

dalao 就是 dalao…

我是怎么在不知道这一对函数的情况下活到今天的img