华为OD机考算法题:根据某条件聚类最少交换次数

这篇具有很好参考价值的文章主要介绍了华为OD机考算法题:根据某条件聚类最少交换次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目部分

解读与思路

代码实现


题目部分

题目 根据某条件聚类最少交换次数
难度
题目说明 给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。
组合一起是指满足条件的数字相邻,不要求相邻后在数组中的位置。
数据范围
-100 <=K <= 100
-100 <= 数组中数值 <= 100
输入描述 第一行输入数组:1 3 1 4 0
第二行输入K数值:2
输出描述 第一行输出最少较好次数:1
补充说明 小于2的表达式是 1 1 0,共三种可能将所有符合要求数字组合在一起,最少交换1次。
没有数字小于K,即不存在满足条件的数字时,返回 0。
交换规则为,任意两个位置的数字可以相互交换。(笔者注)
-----------------------------------------
示例
示例1
输入 1 3 1 4 0
2
输出 1
说明
示例2
输入 0 0 0 1 0
2
输出 0
说明
示例3
输入 2 3 2
1
输出 0
说明

解读与思路

题目解读

第一行输入整形数字 K,第二行输入一串整形数字(假设这一串整形数字存放在一个数组中)。

题目要求,从第二行整形数字中,找出所有小于 K 的数字。然后通过交换位置的方式,使找出的这些数字聚合在一块。

  • 聚合在一块的意思是,这些数字两两相邻,中间不存在不符合条件(大于或等于K)的数字。
  • 交换位置的规则是,数组(根据之前的假设,数字存放在数组中)中的任意两个下标的数字交换都可以交换位置。

在示例 1 中,下标为0的数字 1和下标为3的数字4交换后,数字串变成了 4 3 1 0。此时,从第2个元素到第4个元素,这3个数字全都小于2(K等于2)。再次过程中,交换了1次。

特别注意,在示例 3 中,没有数字小于K,即不存在满足条件的数字时,返回 0。

此题立意很好,但在表述上还有很大的提升空间。
题干应该准确描述背景、条件和要求。晦涩难懂或有歧义的题目容易产生误导。示例作用是进一步印证题干的描述,而不应用于补充题目说明。
出题人在描述问题时,部分隐含条件没有描述出来(当找不到满足条件的交换次数时,返回值应该是多少),而且表述不够清晰(应明示交换规则为,任意两个位置的数字可以相互交换),需要结合示例才能准确理解题目意思。

分析与思路

第一行输入的数字设为 k。
第二行输入的一串数字,把它存到一个整形数组 arr[] 中。

先遍历数组 arr,统计 arr 中小于 k 的数字个数 count,并记录这些数字的最小下标 minIdx 和 最大下标 maxIdx。如果 count 为 0,则直接返回 0。

题目要求小于 k 的数字聚合在一起,那么最终聚合的块的数字是连续的,假设聚合块中数字的最小下标为 iMin,最大小标为 iMax,那么 iMax - iMin == count - 1,且下标在iMin与iMax之间的所有数字都小于 k 。

对于原始数组,如果某个小于 k 的数字,其在 arr 中的下标处于闭区间 [iMin, iMax] 中,那么它不需要交换;如果在此闭区间之外,需要和其他下标在 [ iMin, iMax ] 中且大于 k 的数字交换。显而易见,交换次数为 [iMin, iMax] 这个闭区间(闭区间为arr数组的下标)中大于 k 的数字的个数。

由于 iMin >= minIdx,iMax >= maxIdx,此题的要求可以转换成,从 [minIdx, maxIdx] 这个闭区间中,找出一个长度为 count 的闭区间(闭区间为arr数组的下标),使 arr 数组中大于 k 的数字的个数最小。计算出的最小个数,即为最终的输出。

此算法需要遍历数组两次(第二次只需要遍历 [ minIdx, maxIdx - count ]),其时间复杂度为 O(n)。实现过程中使用了辅助数组用于存储数字,空间复杂度为 O(n)。


代码实现

Java代码

import java.util.Scanner;

/**
 * 根据某条件聚类最少交换次数
 * 
 * @since 2023.09.13
 * @version 0.2
 * @author Frank
 *
 */
public class TogetherChgCnt {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			// 第一行输入一串数字,以空格分隔
			String stream = sc.nextLine();
			String[] strArr = stream.split(" ");
			int[] arr = new int[strArr.length];
			for (int i = 0; i < strArr.length; i++) {
				arr[i] = Integer.parseInt(strArr[i]);
			}
			// 第二行, k
			String strK = sc.nextLine();
			int k = Integer.parseInt(strK);
			processTogetherChgCnt(k, arr);
		}
	}

	private static void processTogetherChgCnt(int k, int[] arr) {
		int minIdx = -1;
		int maxIdx = -1;
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] >= k) {
				continue;
			}
			count++;
			if (minIdx == -1) {
				minIdx = i;
				maxIdx = i;
			} else {
				maxIdx = i;
			}
		}

		if (count == 0) {
			System.out.println(0);
			return;
		}

		int curCnt = 0;
		for (int i = 0; i < count; i++) {
			if (arr[minIdx + i] >= k) {
				curCnt++;
			}
		}

		int rangeCnt = curCnt;
		int stepSize = maxIdx - minIdx - count + 1;
		// 在区间[ minIdx, maxIdx ]范围内,
		// 逐个向右移动,计算移动后的闭区间中大于 k 的个数 curCnt。
		for (int i = 0; i < stepSize; i++) {
			if (arr[minIdx + i] >= k) {
				curCnt--;
			}
			if (arr[minIdx + count + i] >= k) {
				curCnt++;
			}
			if (curCnt < rangeCnt) {
				rangeCnt = curCnt;
			}
		}
		System.out.println(rangeCnt);
	}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        // 第一行数据转换成数组
        var arr = line.split(" ");
        for (var i = 0; i < arr.length; i++) {
            arr[i] = parseInt(arr[i]);
        }
        // 第二行数据,k
        line = await readline();
        var k = parseInt( line );
        processTogetherChgCnt(k, arr);
    }

}();

function processTogetherChgCnt(k, arr) {
    var minIdx = -1;
    var maxIdx = -1;
    var count = 0;
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] >= k) {
            continue;
        }
        count++;
        if (minIdx == -1) {
            minIdx = i;
            maxIdx = i;
        } else {
            maxIdx = i;
        }
    }

    if (count == 0) {
        console.log(0);
        return;
    }

    var curCnt = 0;
    for (var i = 0; i < count; i++) {
        if (arr[minIdx + i] >= k) {
            curCnt++;
        }
    }

    var rangeCnt = curCnt;
    var stepSize = maxIdx - minIdx - count + 1;
    for (var i = 0; i < stepSize; i++) {
        if (arr[minIdx + i] >= k) {
            curCnt--;
        }
        if (arr[minIdx + count + i] >= k) {
            curCnt++;
        }
        if (curCnt < rangeCnt) {
            rangeCnt = curCnt;
        }
    }
    console.log(rangeCnt);
}

(完)文章来源地址https://www.toymoban.com/news/detail-697754.html

到了这里,关于华为OD机考算法题:根据某条件聚类最少交换次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为OD机试 - 最少数量线段覆盖| 机试题算法思路 【2023】

    华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 - 自动曝光(Python) | 机试题算法

    2023年04月25日
    浏览(41)
  • 华为OD机考算法题:高效的任务规划

    题目 高效的任务规划 难度 难 题目说明 你有 n 台机器编号为  1 ~ n ,每台都需要完成一项工作, 机器经过配置后都能独立完成一项工作。 假设第  i  台机器你需要花  分钟进行设置, 然后开始运行,   分钟后完成任务。 现在,你需要选择布置工作的顺序,使得用最短的

    2024年02月07日
    浏览(30)
  • 华为OD机考算法题:区块链文件转储系统

    题目部分 解读与分析 代码实现 题目 区块链文件转储系统 难度 难 题目说明 区块链底层存储是一个链式文件系统,由顺序的N个文件组成,每个文件的大小不一,依次为F1、F2……Fn。随着时间的推移,所占存储会越来越大。 云平台考虑将区块链按文件转储到廉价的SATA盘,只

    2024年02月08日
    浏览(33)
  • 华为OD机考算法题:数字加减游戏

    题目部分 解读与分析 代码实现 题目 数字加减游戏 难度 难 题目说明 小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字 s 变成数字 t 。 每个回合,小明可以用当前的数字加上或减去一个数字。 现在有两种数字可以用来加减,分别为 a, b (a≠b),其中 b 没有使用

    2024年02月09日
    浏览(35)
  • 华为OD机考算法题:MVP争夺战

    题目部分 解读与分析 代码实现 题目 MVP争夺战 难度 易 题目说明 在星球争霸篮球赛对抗赛中,强大的宇宙战队,希望每个人都能拿到MVP。 MVP的条件是,单场最高分得分获得者,可以并列,所以宇宙战队决定在比赛中,尽可能让更多的队员上场,且让所有有得分的队员得分都

    2024年02月09日
    浏览(32)
  • 华为OD机考算法题:阿里巴巴找黄金宝箱(1)

    题目 阿里巴巴找黄金宝箱(1) 难度 易 题目说明 一贫如洗的樵夫阿里巴巴在去砍柴的路上,无意中发现了强盗集团的藏宝地,藏宝地有编号从 0 ~ N 的箱子,每个箱子上面贴有一个数字,箱子中可能有一个黄金宝箱。 黄金宝箱满足排在它之前的所有箱子数字和等于排在它之

    2024年02月07日
    浏览(43)
  • 【华为OD机考 统一考试机试C卷】特殊的加密算法(C++ Java JavaScript Python C语言)

    真题目录:华为OD机考机试 真题目录( D卷 +C卷 + B卷 + A卷) + 考点说明 在线OJ:点击立即刷题,模拟真实机考环境 华为OD面试真题精选:华为OD面试真题精选 有一种特殊的加密算法,明文为一段数字串,经过密码本查找转换,生成另一段密文数字串。 规则如下: 明文为一段

    2024年04月16日
    浏览(43)
  • 【华为OD机考 统一考试机试C卷】素数之积/RSA加密算法(C++ Java JavaScript Python C语言)

    目前在考C卷,经过两个月的收集整理, C卷真题已基本整理完毕 抽到原题的概率为2/3到3/3, 也就是最少抽到两道原题。 请注意:大家刷完C卷真题,最好要把B卷的真题刷一下,因为C卷的部分真题来自B卷。 另外订阅专栏还可以联系笔者开通在线OJ进行刷题,提高刷题效率。

    2024年03月21日
    浏览(44)
  • 华为OD机试(含B卷)真题2023 算法分类版,58道20个算法分类,如果距离机考时间不多了,就看这个吧,稳稳的

    很多小伙伴问我,华为OD机试算法题太多了,知识点繁杂,如何刷题更有效率呢? 我觉得可以按照“算法和数据结构”去刷,把华为OD机试涉及到的“算法和数据结构”列出来,一个算法刷10道题,那我岂不是无敌了? 首先,了解算法和数据结构有哪些知识点,在后面的刷题

    2024年02月14日
    浏览(36)
  • 【华为OD机试】根据IP查找城市(贪心算法—Java&Python&C++&JS实现)

    本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月15日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包