力扣(LeetCode)31

forrest23 发布于2019-08-16 15:17 / 1180人阅读

摘要：如果不存在下一个更大的排列，则将数字重新排列成最小的排列即升序排列。必须原地修改，只允许使用额外常数空间。

题目地址：
https://leetcode-cn.com/probl...

题目描述：
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解答：
直接给出步骤：
1从右到左扫描数组找出第一个升序对(nums[j-1],nums[j])
2从右到左扫描数组找出第一个大于nums[j-1]的数nums[k]
3交换nums[j-1],nums[k]
4对num[j...nums.length-1]转置。

java ac代码:

class Solution {
    public void nextPermutation(int[] nums) {
        boolean flag = true;
        int i = 0;
        for(;i < nums.length-1;i++)
            if(nums[i] < nums[i+1])
            {
                flag = false;
                break;
            }
        if(flag)
        {
            int x = 0,y = nums.length-1;
            while(x < y)
            {
                swap(nums,x,y);
                x++;
                y--;
            }
        }
        else
        {
            i = nums.length-1;
            while(i >= 1)
                if(nums[i] <= nums[i-1])i--;
            else break;
            int j = nums.length-1;
            for(;j >= 0;j--)
                if(nums[j] > nums[i-1])break;
            swap(nums,i-1,j);
            int x = i,y = nums.length-1;
            while(x < y)
            {
                swap(nums,x,y);
                x++;
                y--;
            }
        }
        
        
    }
    
    void swap(int[] nums,int x,int y)
    {
          int temp = nums[x];
          nums[x] = nums[y];
          nums[y] = temp;
        
    }
}

私有云 GPU服务器力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73392.html

＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0
leetcode刷题-----7. 整数反转

摘要：题目给出一个位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例输入输出示例输入输出示例输入输出注意假设我们的环境只能存储得下位的有符号整数，则其数值范围为。解答关键将整数转换为字符串进行切片反转注意溢出注意符号题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1:输入: 123输出: 321 示例 2:输入: -123输出: -32...

daydream 2019-07-31 10:37 评论0 收藏0
力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0