【Day16】Java算法刷题 [299. 猜数字游戏 ] [1.两数之和] [面试题 01.09. 字符串轮转 ]

CSDN话题挑战赛第2期 参赛话题：学习笔记

在这里插入图片描述

刷题打卡，第 十六 天

• 题目一、299. 猜数字游戏
• 题目二、1.两数之和
• 题目三、面试题 01.09. 字符串轮转

题目一、299. 猜数字游戏

原题链接：299. 猜数字游戏

题目描述：

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下： / 写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示： 猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛）， 有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。 也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。 提示的格式为 “xAyB” ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。 请注意秘密数字和朋友猜测的数字都可能含有重复数字。 / 示例 1： 输入：secret = “1807”, guess = “7810” 输出：“1A3B” 解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。 “1807” | “7810” / 示例 2： 输入：secret = “1123”, guess = “0111” 输出：“1A1B” 解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。 “1123” “1123” | or | “0111” “0111” 注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

解题思路： 题目中给到我们两串数字，一串是secret 另外一串是 guess，分别是游戏的答案 与 参与者猜测的答案。 简单总结一下游戏规则，当我们猜的一串数字中，撞到了答案中某个出现的数字时，有两种情况：

数字就在对应位置上，那么这个数字就是Bulls； 数字不在对应位置上，那么就是Cows； 需要注意的是Cows不能重复累加，就如题目给到的 示例2

Bulls最容易找，只需要同时遍历两个串，位置相同的字符也相同，那么就是Bulls就找到了，同时记录下Bulls数量即可、

Cows就比较麻烦，我们可以准备两个数组，分别存放两个串中字符出现的次数（不用记录满足Bulls条件的字符）： 当guess出现了而secret没有出现的，cows += 0； 在guess出现两次，secret出现一次，cows += 1； 在guess出现一次，secret出现三次，cows += 1； 当在两个串中出现的次数都为 2 ，那么cows+=2； … 看起来情况很多，如果我们从中找到规律，就可以用同一的公式表示：cows += 较小的出现次数

到这里我们就分别得出了Bulls 和 Cows 按照要求输出即可。

提交代码：

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0; //记录Bulls数量
        int cows = 0;  //记录Cows数量

        
        //字符串转化数组
        char[] st = secret.toCharArray(); //获取字符串secre的每个字符
        char[] gs = guess.toCharArray();  //获取字符串guess的每个字符

        int[] S = new int[10];    //创建数组，记录字符在secret出现的次数
        int[] G = new int[10];    //创建数组，记录字符在guess出现的次数 

        for(int i = 0;i < guess.length();++i){ //遍历两个字符串
        //找出 猜测数字中有多少位属于数字和确切位置都猜对（称为 "Bulls"，公牛）情况
            if(st[i] == gs[i])
            //记录数量加一
            ++bulls;
            else{//否则
            //使用数组存储非Bulls情况下字符出现的次数，为节省位置，下标用 Ascii码值的差 充当
                ++S[st[i]-'0'];
                ++G[gs[i]-'0'];
            }
        }

        //遍历两个记录字符数的数组，同一个字符，出现次数少的那边，代表了Cows数
        for(int i = 0;i < 10;++i){
            cows += Math.min(S[i],G[i]);
        }

        //按照题目要求输出
        return bulls + "A" + cows + "B";
    }
}

提交结果：

在这里插入图片描述

题目二、1.两数之和

原题链接：1.两数之和

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 / 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 / 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2] / 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1]

解题思路： 题目给出了一个目标数target，要求我们从给定的数组中找出两个数，两数之和等于target，然后还需要输出这两个元素的下标。 咋一看其实不难，完全可以暴力解题，直接给数组双层循环遍历，当找到两数之和为target的元素，返回遍历到的下标就可以。 但是这样耗费的时间太长，时间复杂度不够理想。

我这里的思路，就是使用HashMap集合来存放键值对，主键存放数组元素，Value值存放对应的下标，那么我们就只需要单层的循环就能完成相同效果的遍历，大大节省了时间。

提交代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //创建map集合，存放键值对，Key值为数组元素，value值为下标
        Map<Integer,Integer> map = new HashMap<>();

        //遍历数组，将键值对存入集合
        for(int i = 0;i < nums.length;++i){
            map.put(nums[i],i);
        }

        //创建数组，用于存放符合题目要求的下标
        int[] arr = null;

        //再次遍历数组，每遍历一个元素，寻找集合中两者之和为target的元素
        //注意还需要比较两者下标是否相同，相同代表元素重复，不符合要求
        for(int i = 0;i < nums.length;++i){
            if(map.containsKey(target-nums[i]) && map.get(target-nums[i]) != i){
                //找到就记录下标，终止循环
                arr =  new int[]{i , map.get(target-nums[i])};
                break;
            }
        }
        //返回下标数组
        return arr;
    }
}

提交结果：

在这里插入图片描述

题目三、面试题 01.09. 字符串轮转

原题链接：面试题 01.09. 字符串轮转

题目描述：

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。 / 示例1: 输入：s1 = “waterbottle”, s2 = “erbottlewat” 输出：True / 示例2: 输入：s1 = “aa”, s2 = “aba” 输出：False

解题思路： 这道题有些一言难尽的味道，我们借助API，直接无脑完成； 将两个s1字符串拼接起来，只要s2是其字串，那么必定就是轮转而来的…

提交代码：

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        //长度不同，不可能是轮转的来的
        if(len1 != len2) return false;

        //两个s1字符串拼接起来，若s2是其子串，说明是轮转得来的
        return (s1+s1).contains(s2);

    }
}

提交结果：

在这里插入图片描述

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔ ⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

在这里插入图片描述