Java 笔试强训篇- Day1

🔥博客主页: 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍

文章目录

        1.2 解题思路二

        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;
    }
}

 

版权声明:本文为博主作者:小扳原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/Tingfeng__/article/details/137826156

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2024年4月22日
下一篇 2024年4月22日

相关推荐