每日一练2024.5.10

2024-05-09 16:04
文章标签 每日 一练 2024.5

本文主要是介绍每日一练2024.5.10,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

给定一个非负整数数组 nums,  nums 中一半整数是 奇数 ,一半整数是 偶数 。

对数组进行排序,以便当 nums[i] 为奇数时,i 也是 奇数 ;当 nums[i] 为偶数时, i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

 

示例 1:

输入:nums = [4,2,5,7]
输出:[4,5,2,7]
解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。

示例 2:

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

 

提示:

  • 2 <= nums.length <= 2 * 104
  • nums.length 是偶数
  • nums 中一半是偶数
  • 0 <= nums[i] <= 1000

 

进阶:可以不使用额外空间解决问题吗?

解题:

        这道题的目标是重新排序给定的非负整数数组nums,使数组满足特定的位置规则:位于偶数索引的元素是偶数,位于奇数索引的元素是奇数。根据题目的提示,我们知道数组长度是偶数,且一半元素是偶数,另一半是奇数。解决这个问题有几种方法:

 

  1. 两个指针法:利用两个指针,一个只在偶数索引移动,一个只在奇数索引移动。交换两个指针指向的不符合位置要求的数。

  2. 分类后重组:创建两个数组,一个存放所有的偶数,另一个存放所有的奇数,最后交替把它们重组到原数组中。

 

对于进阶问题:题目询问你是否能在不使用额外空间的情况下解决这个问题。可以运用第一种方法(两个指针法),因为这种方法不需要创建额外的数组,直接在原数组上进行操作即可。步骤大致如下:

 

  1. 初始化两个指针,evenIndex从0开始(用于偶数索引),oddIndex从1开始(用于奇数索引)。
  2. 遍历数组直至evenIndex或者oddIndex到达数组末尾。
  3. evenIndex指向的数字是奇数,且oddIndex指向的数字是偶数时,则交换这两个数。
  4. 如果evenIndex指向的数字已经是偶数,则evenIndex增加2;同理,如果oddIndex指向的数字是奇数,则oddIndex增加2。
  5. 重复步骤3和4,直到整个数组被正确排序。

 

实现这个算法,只需要在原数组上进行指针移动和元素交换操作,不会占用除输入数组以外的额外空间,因此是一个原地排序算法。

代码:

class Solution {public int[] sortArrayByParityII(int[] nums) {int n = nums.length;int evenIndex = 0; // 偶数索引int oddIndex = 1;  // 奇数索引while (evenIndex < n && oddIndex < n) {// 寻找错位的偶数索引while (evenIndex < n && nums[evenIndex] % 2 == 0) {evenIndex += 2;}// 寻找错位的奇数索引while (oddIndex < n && nums[oddIndex] % 2 != 0) {oddIndex += 2;}// 交换if (evenIndex < n && oddIndex < n) {int temp = nums[evenIndex];nums[evenIndex] = nums[oddIndex];nums[oddIndex] = temp;}}return nums;}
}

知识点概览:

        这段代码是为了解决一个特定的问题,即在给定的非负整数数组中,按照特定规则重新排序数组,使偶数索引处的元素为偶数,奇数索引处的元素为奇数。这个问题的解决方法采用了就地排序的策略,意味着不需要额外的数组来存储结果,而是直接在输入数组上操作。这里用到的主要Java编程知识点包括:

 

  1. 数组:使用数组来存储输入的整数序列。数组是一种基本的数据结构,支持通过索引快速访问元素。

  2. 变量:定义了几个整型变量(nevenIndexoddIndex)用于存储数组长度和控制循环中的索引位置。

  3. 循环控制(while循环和嵌套while循环):使用两层while循环来遍历数组并找到需要交换的元素位置。外层循环控制整个过程直到所有元素被正确排序,内层循环分别找到不在正确位置的偶数元素和奇数元素。

  4. 条件判断(if语句):利用if语句和求余运算符%来检查元素是否符合其索引的奇偶性要求。

  5. 算术运算:使用%求余运算符来判断数字的奇偶性(偶数 % 2 == 0,奇数 % 2 != 0)。

  6. 变量交换:在找到不符合位置要求的一对偶数索引和奇数索引的元素后,通过临时变量temp执行数组内元素的交换。

  7. 空间复杂度控制:这个解决方案遵循就地操作的原则,除了原数组以外,不需要分配额外的空间来存储数据或结果,因此空间复杂度为O(1)。

  8. 索引控制:通过精确地控制evenIndexoddIndex,保证了即使发生了交换操作,也能再次回到循环中继续寻找下一个不在正确位置上的元素。这里的索引控制确保了算法的完整性和效率。

知识点类别描述
数组使用数组存储输入的整数序列,支持通过索引快速访问元素。
变量定义整型变量(例如nevenIndexoddIndex)来存储数组长度和控制索引位置。
循环控制使用while循环及嵌套while循环遍历数组并查找需要交换的元素位置。外层循环控制整个过程,内层循环分别寻找错位的偶数和奇数元素。
条件判断利用if语句合并求余运算符%判断元素与其索引奇偶性是否匹配。
算术运算使用%求余运算符判断数字的奇偶性(偶数为% 2 == 0,奇数为% 2 != 0)。
变量交换在找到不符合位置要求的元素对时,通过临时变量temp执行数组内的元素交换。
空间复杂度控制整个算法运行过程中,除原数组外没有使用额外的存储空间,空间复杂度为O(1)。
索引控制精确控制evenIndexoddIndex确保算法能继续寻找不在正确位置的元素,这种控制方式保证了算法的完整性和效率。

fb14efc1f6f34b2daefee3768bb6b90d.png

 2024.5.10

这篇关于每日一练2024.5.10的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

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

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

英语每日一段 195

Promising economic indicators won’t instantly reverse the lingering impact of hard times for millions of families, workplace culture expert Jessica Kriegel said. “Perception and reality are sometimes

GitHub每日最火火火项目(9.7)

项目名称:polarsource / polar 项目介绍:polar 是一个开源的项目,它是 Lemon Squeezy 的替代方案,具有更优惠的价格。该项目旨在让开发者能够凭借自己的热情进行编码并获得报酬。通过使用 polar,开发者可以更轻松地实现自己的创意和项目,并从中获得收益。 项目地址:https://github.com/polarsource/polar项目名称:psf / bla

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口) 题目描述 给定一个字符串 blocks,其中每个字符代表一个颜色块,可以是 ‘W’(白色)或 ‘B’(黑色)。你需要找到一个至少包含 k 个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k 个黑色块的最少操作次数。 和该题目类似:【每日一题】LeetCode 202