首页 > 编程语言 >大厂算法每日总结(GB字符串至少交换几次)

大厂算法每日总结(GB字符串至少交换几次)

时间:2023-08-26 15:22:50浏览次数:37  
标签:str int step2 char 算法 GB step1 gi 大厂

//一个数组中只有两种字符'G'和'B',
//想要所有的G都放左边, 所有的B都放右边或者所有的B都放左边, 所有的G都放右边
//但只能在相邻字符之间进行交换操作
//返回至少需要交换几次
//方法1
public static int minSteps1(String s) {
if(s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int gi = 0;
for(int i = 0;i<str.length;i++) {
if(str[i] == 'G') {
step1 +=i -(gi++);//每次遇到G就放到gi的后面就行了,距离gi位置差多少就换几次
}
}
int step2 = 0;
int bi = 0;
for(int i=0;i<str.length;i++) {
if(str[i] == 'B') {
step2 += i - (bi++);
}
}
return Math.min(step1,step2);//返回GB最少交换次数
}
//方法2
public static int minSteps2(String s) {
if(s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int step2 = 0;
int gi = 0;
int bi = 0;
for(int i = 0;i<str.length;i++) {
if(str[i] == 'G') {
step1 +=i-(gi++);
}else {
step2 +=i-(bi++);
}
}
return Math.min(step1,step2);
}

public static String randomString(int maxLen) {
	char[] str = new char[(int)(Math.random()*maxLen)];
	for(int i=0;i<str.length;i++) {
		str[i]=Math.random() < 0.5 ? 'G' : 'B';	
	}
	return String.valueOf(str);
}

public static void main(String[] args) {
	int maxLen = 100;
	int testTime = 1000000;
	System.out.println("测试开始");
	for(int i =0;i<testTime;i++) {
		String str = randomString(maxLen);//生成1000000个随机字符串
		int ans1 = minSteps1(str);
		System.out.println(ans1);
		int ans2 = minSteps2(str);
		System.out.println(ans2);
		if(ans1 != ans2) {
			System.out.println("Oops!");
		}
	}
	System.out.println("测试结束");
}

标签:str,int,step2,char,算法,GB,step1,gi,大厂
From: https://www.cnblogs.com/15078480385zyc/p/17658834.html

相关文章

  • 大厂算法题每日总结(绳子最大能盖的数组节点)
    //绳子最大能盖的数组节点publicstaticvoidmain(String[]args){int[]arr={1,4,7,9,60};System.out.println(maxPoint2(arr,50));}publicstaticintmaxPoint(int[]arr,intL){//L是绳子的长度 intres=1; for(inti=0;i<arr.length;i++){ intnearest=n......
  • GBU812-ASEMI逆变器专用整流桥GBU812
    编辑:llGBU812-ASEMI逆变器专用整流桥GBU812型号:GBU812品牌:ASEMI芯片个数:4封装:GBU-4恢复时间:>50ns工作温度:-55°C~150°C浪涌电流:200A正向电流:8A反向耐压:1200V正向压降:1.10V引脚数量:4GBU812特性:ASEMI品牌GBU812是采用工艺芯片,该芯片具有良好的稳定性及抗冲击能力,能够持续保证了GBU812......
  • 代码随想录算法训练营第二十四天| 理论基础 77. 组合
     理论基础    卡哥建议:其实在讲解二叉树的时候,就给大家介绍过回溯,这次正式开启回溯算法,大家可以先看视频,对回溯算法有一个整体的了解。   题目链接/文章讲解:https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8......
  • GBU812-ASEMI逆变器专用整流桥GBU812
    编辑:llGBU812-ASEMI逆变器专用整流桥GBU812型号:GBU812品牌:ASEMI芯片个数:4封装:GBU-4恢复时间:>50ns工作温度:-55°C~150°C浪涌电流:200A正向电流:8A反向耐压:1200V正向压降:1.10V引脚数量:4GBU812特性:ASEMI品牌GBU812是采用工艺芯片,该芯片具有良好的稳定性及抗冲击能力,能够......
  • 代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜
     669. 修剪二叉搜索树    卡哥建议:这道题目比较难,比 添加增加和删除节点难的多,建议先看视频理解。   题目链接/文章讲解:https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html   视频讲解:https://www.......
  • 基于springboot的图书馆管理系统
    随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了疫情下图书馆管理系统的开发全过程。通过分析疫情下图书馆管理系统管理的不足,创建了一个计算机管理疫情下图书馆管理系统的方案。文章介绍了疫情下图书馆管理系统的系统分析部分,包括可......
  • 代码随想录算法训练营第二十二天| 235. 二叉搜索树的最近公共祖先 701.二叉搜索树
      235. 二叉搜索树的最近公共祖先    卡哥建议:相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。   题目链接/文章讲解:https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%B......
  • 基于springboot编程训练系统设计与实现
    随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了编程训练系统的开发全过程。通过分析编程训练系统管理的不足,创建了一个计算机管理编程训练系统的方案。文章介绍了编程训练系统的系统分析部分,包括可行性分析等,系统设计部分主要介绍了......
  • SpringBoot集成shiro权限安全框架
    在java开发中常用到两个权限安全框架,一是spring security,二是shiro。两者区别是spring security是针对spring和springboot项目的权限安全框架,而shiro则对环境无特别要求,可用于多种开发环境,并且相对简单,入门更加容易。本次主要就是分享shiro框架下对项目权限实现细粒度的划分,以及......
  • 基于springboot框架的网上商城系统的设计与实现
    系统实现系统实现部分就是将系统分析,系统设计部分的内容通过编码进行功能实现,以一个实际应用系统的形式展示系统分析与系统设计的结果。前面提到的系统分析,系统设计最主要还是进行功能,系统操作逻辑的设计,也包括了存储数据的数据库方面的设计等内容,系统实现就是一个最终的实施阶段,将......