首页 > 其他分享 >【美团3.18校招真题2】

【美团3.18校招真题2】

时间:2023-10-06 10:04:10浏览次数:38  
标签:3.18 int 美团 位置 --- 修改 对称 校招 回文


大厂笔试真题网址:https://codefun2000.com/

塔子哥刷题网站博客:https://blog.codefun2000.com/

最多修改两个字符,生成字典序最小的回文串

提交网址:https://codefun2000.com/p/P1089

【美团3.18校招真题2】_字符串

【美团3.18校招真题2】_字符串_02


由于字符串经过修改一定为回文串,且最多修改两次,所以原字符串位置i与对称位置n-i-1不一样的个数最多为2。所以统计一下需要改的位置个数,记为cnt

  1. cnt=0,即原字符串就是回文串,找到第一个不为a的位置i,将i与对称位置n-i-1都改为a
aca      ---> aaa
acca     ---> aaaa
acbca    ---> aabaa
  1. cnt=1,只有一个位置需要修改,此时分两种情况
  • 如果 i与对称位置n-i-1都不是a,将这俩位置都改为a即可
  • 如果 i与对称位置n-i-1只有一个为a,将另一个不是a的改为a。此时只改了一个字母,还可以改一个。当字符串长度为奇数时,将中间字符改为a
abcdba  ---> abaaba
abcea   ---> aacaa
cbcac   ---> caaac
  1. cnt=2,两个对称位置需要修改, i与对称位置n-i-1,谁小就改为谁
abcde  ---> abcba
int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<int> idxs;
	for (int i = 0; i < n / 2; i++) {
		if (s[i] != s[n - 1 - i]) {
			idxs.push_back(i);
		}
	}
	int cnt = idxs.size();
	if (cnt == 0) {
		// 本身就是回文串,需要找到第一个不是a的地方修改
		for (int i = 0; i <= n / 2; i++) {
			if (s[i] != 'a') {
				s[i] = 'a';
				s[n - 1 - i] = 'a';
				break;
			}
		}
	}
	else if (cnt == 1) {
		// 只有一个需要修改的地方
		if (s[idxs[0]] != 'a' && s[n - 1 - idxs[0]] != 'a') {
			// 如果对称位置都不是a,则两个都改为a
			s[idxs[0]] = 'a';
			s[n - 1 - idxs[0]] = 'a';
		}
		else {
			// 如果只有一个为a,则修改不是a的那个
			// 如果当前串为奇数,还要修改中间位置的为a
			s[idxs[0]] = 'a';
			s[n - 1 - idxs[0]] = 'a';
			if (n & 1) {
				s[n / 2] = 'a';
			}
		}
	}
	else {
		// 有两个需要修改的地方,当前位置idxs[i]和对称位置n - 1 - idxs[i],谁小就改为谁
		for (int i = 0; i < cnt; i++) {
			char c = min(s[idxs[i]], s[n - 1 - idxs[i]]);
			s[idxs[i]] = c;
			s[n - 1 - idxs[i]] = c;
		}
	}
	cout << s << endl;
	return 0;
}


标签:3.18,int,美团,位置,---,修改,对称,校招,回文
From: https://blog.51cto.com/BugMaker/7721523

相关文章

  • 【美团3.18校招真题1】
    大厂笔试真题网址:https://codefun2000.com/塔子哥刷题网站博客:https://blog.codefun2000.com/小美剪彩带提交网址:https://codefun2000.com/p/P1088题意:找出区间内不超过k种数字子数组的最大长度使用双指针的方式,用哈希表来统计每个数出现次数。在双指针移动的过程中,动态的维护区间......
  • Leaf-美团的分布式ID生成器
    简介在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯......
  • 外卖霸王餐系统 美团试吃系统 支持分销代理
    微客云免费提供外卖霸王餐系统,支持分站、运营商、商家后台、独立域名,自定义品牌,自主收款。想做霸王餐的可以参考下联系微客云。地址:微客云-淘宝客CMS,公众号,小程序,淘客APP,外卖返利CPS,私域电商系统分站后台演示: ......
  • 大厂裁员,社招锁 HC,行业内卷严重,Java工程师校招该何去何从?
    一、背景2021年底到2022年,受到疫情和业务发展的影响,很多大厂都开始裁员,社招也开始锁HC,只出不进。而且现在Java面试日益内卷,“面试造火箭,入职拧螺丝”已经不再是啥令人惊讶的事情。这这个大背景下,对我们的校招又会有怎样的影响,我们又该如何应对?本文简单聊下这个话题。二、校......
  • 大厂校招缩招,今年 Java 后端同学校招该何去何从?
    一、背景最近有一些学弟学妹请教一些校招相关的问题。作为一个经历过校招(校招拿到了美团、网易等公司Offer)、社招(在阿里工作),当过面试官的过来人,希望通过本文让大家能够意识到今年校招的形势,帮助大家了解校招复习的误区。前几年互联网很好找工作,尤其是985和211高校的同学,找......
  • 【校招VIP】产品思维考察之用户体验
    考点介绍:在设计产品的功能点时,我们需要设想我们的用户到底是谁?他的需求是什么?为此我们需要做用户分析,从而得出我们的用户画像,提供解决方案。用户调研是用户分析的一种方法,用户画像是结果,提供解决方案(需求)是用户分析的目的。产品思维考察之用户体验-相关题目及解析内容可点击文章......
  • 【校招VIP】前端计算机网络之webSocket相关
    考点介绍WebSocket是一种网络通信协议,很多高级功能都需要它。初次接触WebSocket的人,都会问同样的问题:我们已经有了HTTP协议,为什么还需要另一个协议?它能带来什么好处?答案很简单,因为HTTP协议有一个缺陷:通信只能由客户端发起。答案详情解析和文章内容可点击下方链接即可查......
  • 【校招VIP】测试算法考点之链表
    考点介绍:链表是一种逻辑简单的、实用的数据结构,几乎被所有程序设计语言支持。单链表的操作算法是笔试面试中较为常见的题目。相关题目及解析内容可点击文章末尾链接查看!一、考点试题1.一个长度为n的单向链表,用O(1)空间复杂度来实现倒转输出,使用最低时间复杂度解答:思路:读题(......
  • 【校招VIP】产品群面角色之计时者
    考点介绍:这个角色是项目管理能力的体现,不过在这个角色容易被Leader角色抢戏甚至被其兼职,然而反过来说,Time-keeper也可以以提醒时间为名义辅助Leader工作。产品群面角色之计时者-相关题目及解析内容可点击文章末尾链接查看!一、考点题目1.作为职能者(leader、计时者、记录者),怎么......
  • 【校招VIP】java语言考点之多态
    考点介绍:多态是校招常考考点之一。多态是面向对象程序设计(ooP)的一个重要特征,指同一个实体同时具有多种形式,即同个对象在不同时刻代表对象不一样,指的是对象的多种形态。答案详情解析和文章内容可扫下方海报二维码或点击链接即可查看!一、考点试题1、如何理解多态?类与对象的......