专栏名称: Python爱好者社区
人生苦短,我用Python。分享Python相关的技术文章、工具资源、精选课程、视频教程、热点资讯、学习资料等。每天自动更新和推送。
目录
相关文章推荐
Python爱好者社区  ·  GPT-5被曝不及预期,OpenAI员工:没 ... ·  2 天前  
Python开发者  ·  太荒谬了!千人公司一刀切禁用 ... ·  3 天前  
Python爱好者社区  ·  太强了!35个python案例.pdf ·  1 周前  
Python爱好者社区  ·  700篇大模型论文 ·  6 天前  
Python爱好者社区  ·  python学习手册 ·  5 天前  
51好读  ›  专栏  ›  Python爱好者社区

离职后收到最逆天的消息是什么。。。

Python爱好者社区  · 公众号  · Python  · 2024-11-11 15:00

正文

一网友离职后,突然收到前公司员工分配的任务,关键是人家都离职了,并且分配任务的人也不是他们之前部门的。这种事但凡正常人应该都做不出来,网友评论先加钱在干活


我之前离职之后收到几个同事的消息问有没有时间,一起吃个饭,我感觉都已经走了,在回去吃饭有点不妥,最终还是没去。该网友收到的消息是有没有时间干点活,干活可以,先发个大大的红包,一切都好说。。。



网友评论:


--------------下面是今天的算法题--------------


来看下今天的算法题,这题是LeetCode的第31题:下一个排列。


问题描述



来源:LeetCode第31题
难度:中等

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列(即,组合出下一个更大的整数)。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。


必须原地修改,只允许使用额外常数空间。


示例1:

输入:nums = [1,2,3]

输出:[1,3,2]

示例2:

输入:nums = [3,2,1]

输出:[1,2,3]


  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 100


问题分析



这题说的是计算数字序列重新排列成字典序中下一个更大的排列。举个例子,比如数字213的下一个排列是231,231的下一个排列是312。


那么这题的规律该怎么找呢,我们来看这样一组数字

[7,5,4,3,2]

这些数字从后往前都是升序的,无论怎么调换位置都不可能获得更大的排列。


再来看一组数字

[1,4,7,6,5,3,2]

从后往前看2→3→5→6→7是升序的,但7→4是降序的,我们只需要把4和7交换一下就可以获得比原来更大的排列。但这里要等一下,题中要求的是找出比原来大的最小的排列。交换4和7虽然比原来大,但不是最小的。实际上用5和4交换要比7和4交换更小。


所以这里当我们从后往前找到第一个降序的数字之后(比如上面的4),我们还要从后往前找到第一个比降序数字大的值(比如上面的5),然后这两个数字交换(比如上面的4和5交换)。


交换完之后(比如上面的交换之后是[1,5,7,6,4,3,2]),这个排列肯定是比原来的大,因为5比4大,我们只需要让5后面的排列数字最小即可。


因为5后面的数字[7,6,4,3,2]从后往前是升序的,我们只需要把他反转即可,所以[1,4,7,6,5,3,2]的下一个排列是[1,5,2,3,4,6,7],画个图来加深一下理解。


JAVA:
public void nextPermutation(int[] nums) {
    int left = nums.length - 2;
    // 两两比较,从后面往前找第一个降序的
    while (left >= 0 && nums[left] >= nums[left + 1])
        left--;
    // 如果数组nums中的元素都是倒叙,那么left就等于-1
    if (left >= 0) {
        int right = nums.length - 1;
        // 从后面查找第一个比nums[left]大的值
        while (nums[right] <= nums[left])
            right--;
        swap(nums, left, right);
    }
    // 反转后面升序的数字
    reverse(nums, left + 1, nums.length - 1);
}

// 反转子数组[left,right]中的元素
private void reverse(int[] nums, int left, int right) {
    while (left         swap(nums, left++, right--);
}

// 交换数组中的两个数字
private void swap(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

C++:
public:
    void nextPermutation(vector<int> &nums) {
        int left = nums.size() - 2;
        // 两两比较,从后面往前找第一个降序的
        while (left >= 0 && nums[left] >= nums[left + 1])
            left--;
        // 如果数组nums中的元素都是倒叙,那么left就等于-1
        if (left >= 0) {
            int right = nums.size() - 1;
            // 从后面查找第一个比nums[left]大的值
            while (nums[right] <= nums[left])
                right--;
            swap(nums[left], nums[right]);
        }
        // 反转后面升序的数字
        reverse(nums.begin() + left + 1, nums.end());
    }

Python:
def nextPermutation(self, nums: List[int]) -> None:
    left = len(nums) - 2
    # 两两比较,从后面往前找第一个降序的
    while left >= 0 and nums[left] >= nums[left + 1]:
        left -= 1
    # 如果数组nums中的元素都是倒叙,那么left就等于-1
    if left >= 0:
        right = len(nums) - 1
        # 从后面查找第一个比nums[left]大的值
        while nums[right] <= nums[left]:
            right -= 1
        # 交换nums[left]和nums[right]
        nums[left], nums[right] = nums[right], nums[left]
    # 反转后面升序的数字
    nums[left + 1:] = reversed(nums[left + 1:])

来自:数据结构与算法