LeetCode刷题之HOT100之下一个排列

2024-06-01 22:20

本文主要是介绍LeetCode刷题之HOT100之下一个排列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《百年孤独》看到了255页,还有100页就看完了,每个人物的一生就像流水,波澜不惊下是暗流涌动。值得一提的是外国小说对人性的描写更为深入,每个人物性格都被刻画的淋漓。是的,今天雨一直在下,淋湿我的身上,独自一人在偌大的会议室,不知所措。孤独与倦怠像洪水吞噬了我,残存的躯壳在这里机械的打着稍有点人情味的字,一切都令人感到无趣,孤独占有了我。可能是看了这本书的后遗症,也同样可能是我矫揉造作、无病呻吟,在为我拥有这种感受与情愫喝彩,认为孤独是小众,是高于其他,这一切都不无可能。

1、题目描述

在这里插入图片描述

2、逻辑分析

通过不了的植物大战僵尸杂交版,让我想起了来做LeetCoed,可当我看到这个题后,又感觉被僵尸吃掉了脑子。说实话,不太理解这个题目索要表述的到底是什么。看了题解后才知道,大致意思如下图:

在这里插入图片描述

怎么处理该题目呢?解法思路:

  1. 从右向左找到第一个相邻的元素对 (i, i+1),使得 nums[i] < nums[i+1]。这意味着在 i
    之前的元素(如果有的话)都已经是降序排列的,且 i 之后的元素(如果有的话)都小于或等于 nums[i]。
  2. 如果不存在这样的元素对(即 i 小于
    0),那么整个数组已经是降序排列的(即已经是最大的排列)。在这种情况下,我们将整个数组反转以得到最小的排列。
  3. 如果存在这样的元素对 (i, i+1),则从右向左找到第一个比 nums[i] 大的元素 nums[j],并将 nums[i] 和
    nums[j] 交换。这样可以确保 i 之后的元素尽可能小,且 i 之前的元素保持不变(因为它们已经是降序排列的)。
  4. 最后,将 i+1 之后的数组部分反转,以确保在交换了 nums[i] 之后,我们得到的排列是尽可能小的。

使用一个具体例子来佐证:

在这里插入图片描述

3、代码演示

 public void nextPermutation(int[] nums) {// 从右向左找到第一个相邻的元素对 (i, i+1),使得 nums[i] < nums[i+1]  // 这样的元素对意味着我们可以通过重新排列i之后的元素来得到一个更大的排列int i = nums.length - 2;while(i >= 0 && nums[i] >= nums[i + 1]){i--;}// 如果i小于0,说明整个数组是降序排列的(即已经是最大的排列)  // 这时候,我们需要将整个数组反转以得到最小的排列 if(i >= 0){// 从右向左找到第一个比nums[i]大的元素nums[j]  // 我们需要将nums[i]与nums[j]交换,这样可以确保交换后的nums[i]后面部分的元素尽可能小int j = nums.length -1;while(j >= 0 && nums[i] >= nums[j]){j--;}// 交换nums[i]和nums[j]  swap(nums, i , j);}/ 将i+1之后的数组部分反转  // 这样做是为了确保在交换了nums[i]之后,我们得到的排列是尽可能小的reverse(nums, i + 1);}// 辅助函数:交换数组中的两个元素  public void swap(int[] nums, int i, int j){int temp = 0;temp = nums[i];nums[i] = nums[j];nums[j] = temp;}// 辅助函数:反转数组中从start开始到末尾的部分public void reverse(int []nums, int start){int left = start, right = nums.length -1;while(left < right){swap(nums, left, right);left++;right--;}}

时间复杂度:O(n),空间复杂度:O(1)。

刚开始看题解真的想放弃,后面慢慢一步步理清思路就感觉很轻松了。未知让人恐惧,舒适区就像温水煮青蛙,还是得适当跳脱出,去拉伸区转转,好了,题目就到这儿了,拜拜!

这篇关于LeetCode刷题之HOT100之下一个排列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1022260

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar