🔥博客主页： 【小扳_-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 < stringBuilder.length() - 1; i++) { if (stringBuilder.charAt(i) == stringBuilder.charAt(i+1)){ stringBuilder.delete(i,i+2); i = -1; } } if (stringBuilder.length() == 0){ System.out.println(0); }else { System.out.println(stringBuilder); } } } }在牛客上跑的结果：
很显然，虽然逻辑是可以的，不会有问题，但是复杂度太高了。面对长度很长很长的字符串会跑不过去。原因是 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<Character> stack = new Stack<>(); String s = in.next(); for (int i = 0; i < s.length(); i++) { if ( !stack.isEmpty() && stack.peek() == s.charAt(i)){ stack.pop(); }else { stack.push(s.charAt(i)); } } StringBuilder stringBuilder = new StringBuilder(); while (!stack.isEmpty()){ stringBuilder.insert(0,stack.pop()); } if (stringBuilder.length() == 0){ System.out.println(0); }else { System.out.println(stringBuilder); } } } }在牛客上跑的结果：
2.0 在两个数组中找出相同的数
该题链接：无
给定两个整数数组分别为 nums1,nums2 ，找到它们的公共元素并按返回。
数据范围：
1 <= nums1.length，nums2.length <= 1000
示例1：
输入：
[1,2] [2,2,2,2]
输出：
[2]
说明两个数组的公共元素只有 2 。
2.1 解题思路
直接暴力解即可，用 nums1 中每一个数与 nums2 中的每一个数进行比较，嵌套 for 循环。如果相同就写入到新的数组中，如果之前就已经有了，就不用再写到数组中了。
代码如下：
import java.util.ArrayList; public class Solution { /* *//** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums1 int整型ArrayList * @param nums2 int整型ArrayList * @return int整型ArrayList */ public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) { // write code here ArrayList<Integer> temp = new ArrayList<>(); for (int i = 0; i < nums1.size(); i++) { int j = nums1.get(i); for (int k = 0; k < nums2.size(); k++) { if (j == nums2.get(k)){ if (temp.contains(j)){ continue; } temp.add(j); } } } return temp; } }
以上这是我一开始的思路，后来想了想还有更加简单的，只用一个 for 循环即可，用 nums1 中的每一个数来判断 nums2 是否包含这个数即可。就不过多赘述了。
代码如下：
import java.util.ArrayList; public class Solution2 { public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) { // write code here ArrayList<Integer> temp = new ArrayList<>(); for (int i = 0; i < nums1.size(); i++) { int j = nums1.get(i); if (nums2.contains(j)){ if (!temp.contains(j)){ temp.add(j); } } } return temp; } }
