Java 笔试强训篇- Day1
🔥博客主页: 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
文章目录
1.0 点击消除
1.1 解题思路一
1.2 解题思路二
2.0 在两个数组中找出相同的数
2.1 解题思路
笔试强训说明:有一些题目提供不了原题。
1.0 点击消除
该题链接:点击消除_牛客题霸_牛客网 (nowcoder.com)
描述
牛牛拿到了一个字符串。
他每次“点击”,可以把字符串中相邻两个相同字母消除,例如,字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道,当他点击了足够多次之后,字符串的最终形态是什么?
输入描述:
一个字符串,仅由小写字母组成。(字符串长度不大于300000)
输出描述:
一个字符串,为“点击消除”后的最终形态。若最终的字符串为空串,则输出0。
实例1:
输入:
abbc
输出:
ac
示例2:
输入:
abba
输出:
0
1.1 解题思路一
可以用到双指针的方法:用 StringBuilder 来接收字符串,因为该类对象可以在原本的字符串中是可变的,而 String 类对象是不可变的。
首先先遍历字符串,for 循环 int i 从 0 到 str.length()-1 的位置,因为 i 只是第一个指针到达的位置,对于第二个指针 i + 1 来说,永比第一个指针先走一步。
接着,判断当前两个指针 i 与 i + 1 所对应的字符是否相同,如果相同,那么直接删除,删除方法 str.delete(i,i+2),包前不包后,所以需要 +2 操作,以保证将两个相同的字符都可以删除掉,删除完毕之后,还得继续将 i = -1 赋值处理。
代码如下:
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case StringBuilder stringBuilder = new StringBuilder(in.next()); for (int i = 0; i在牛客上跑的结果:
很显然,虽然逻辑是可以的,不会有问题,但是复杂度太高了。面对长度很长很长的字符串会跑不过去。原因是 i = - 1 的原因,一旦删除完相同的字符之后,就会重新开始新的循环。
1.2 解题思路二
可以用到栈的思想:当要往栈中放字符的时候,先判断栈是否为空并且栈顶字符与当前要往栈中放的字符进行比较,如果都满足的话,那么就可以将栈顶中的字符弹出来,继续找下一个字符;如果不满足,很简单,直接入栈即可。
最后,遍历完字符串之后,就可以将栈中的字符进行头插到 StringBuilder 类对象中。这样的好处:只需要遍历一遍字符串即可。
代码如下:
import java.util.Scanner; import java.util.Stack; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case Stack stack = new Stack(); String s = in.next(); for (int i = 0; i在牛客上跑的结果:
2.0 在两个数组中找出相同的数
该题链接:无
给定两个整数数组分别为 nums1,nums2 ,找到它们的公共元素并按返回。
数据范围:
1
还没有评论,来说两句吧...