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

简介: 学习 [299. 猜数字游戏 ] [1.两数之和] [面试题 01.09. 字符串轮转 ]。

刷题打卡,第 十六 天


题目一、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";
    }
}

提交结果:

微信图片_20221030170923.png


题目二、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;
    }
}

提交结果:

微信图片_20221030170931.png

题目三、面试题 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);
  }
}

提交结果:

微信图片_20221030170938.png

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔

⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~

微信图片_20221029111446.jpg


目录
相关文章
|
3天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
7 0
|
4天前
|
SQL 存储 Java
致远互联java实习生面试
致远互联java实习生面试
20 0
|
4天前
|
缓存 安全 Java
java-- 字符串+拼接详解, 性能调优 (底层原理实现)
java-- 字符串+拼接详解, 性能调优 (底层原理实现)
10 0
|
4天前
|
Java C++
java面试基础 -- 深克隆 & 浅克隆
java面试基础 -- 深克隆 & 浅克隆
8 1
|
4天前
|
Java
java面试基础 -- 普通类 & 抽象类 & 接口
java面试基础 -- 普通类 & 抽象类 & 接口
9 0
|
4天前
|
存储 安全 Java
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
8 0
|
4天前
|
Java
java面试基础 -- 方法重载 & 方法重写
java面试基础 -- 方法重载 & 方法重写
6 0
|
5天前
|
消息中间件 存储 Java
Java分布式技术面试总结(全面,实时更新)
Java分布式技术面试总结(全面,实时更新)
|
12天前
|
存储 XML 缓存
Java字符串内幕:String、StringBuffer和StringBuilder的奥秘
Java字符串内幕:String、StringBuffer和StringBuilder的奥秘
27 0
|
10天前
|
存储 Java
Java基础复习(DayThree):字符串基础与StringBuffer、StringBuilder源码研究
Java基础复习(DayThree):字符串基础与StringBuffer、StringBuilder源码研究
Java基础复习(DayThree):字符串基础与StringBuffer、StringBuilder源码研究