前言：
- 大家好，我是良辰丫，第二十一篇,牛客网选择题+编程题洗牌+MP3光标位置.💞💞💞
- 生活就像一只盲盒，藏着意想不到的辛苦，当然也有万般惊喜的可能。不管是次次都如愿以偿，还是赢面寥寥无几，终究起起伏伏才是常态。我们既有过顺遂，也难免绝望，但若一陷入困境就立即抽身而退，那就再也没有翻盘的可能。只要生活还在继续，就有赢的可能。
🧑个人主页：良辰针不戳
📖所属专栏：百日冲大厂
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
💌作者能力有限，可能也会出错，欢迎大家指正。
💞愿与君为伴，共探Java汪洋大海。
目录
- 1. 选择题
- 2. 编程题
-
- 2.1 洗牌
- 2.2 MP3光标位置
1. 选择题
- 时间复杂度往往说的是最坏的情况下.
- 我们假设最后一个节点是插入新节点的位置,因此时间复杂度为O(n).
栈 符合
先进后出的特点.
- 栈是先进后出原则,队列是先进先出原则.
- 根据出队列的顺序,e2先出队列,那么e2先进队列,因此e1和e2先依次入栈,此时容量为2.
- e2出栈后剩余e1,根据队列的序列,下一个出队列的是e4,那么此时e3和e4入栈,这个时候容量为3,最大容量更新为3.
- 紧接着e4出栈,进队列,然后出队列.
- 下一个出队列的是e3,此时e3出栈出队列…
- 最后所有元素出队列更新的最大容量为3.
- 这里考察的是递归.
- 3 * foo(14,6)
- 3* 3 *foo(8,3)
- 3 * 3 * 3 * foo(2,1)
- 3 * 3 * 3 * 3 *foo(-4,0)
- 此时到达递归结束的条件,最终结果为3 * 3 * 3 * 3 = 81.
- n0 = n2 + 1得出n2 = n0 – 1
- 根据题目n0 + n1 + n2 = 2n.
- 合并得 2n0 = 2n + 1 – n1
- n1可能为1或者0,在这里只能为1,因为要满足最终结果可以被整除.
- 2n0 = 2n得出n0 = n.
循环队列使用的是数组
- 二叉排序树和AVL树都叫做二叉搜索排序树,为什么A和C不对呢?任意节点出发到根的路径上,可能左上和右上同时出现,假设左节点比根小,右节点比根大,那么此时就不是有序.
- 堆从任意节点出发到根的路径上一定是有序的,拿最小堆举例,根总是小于它的左右孩子.
- 哈夫曼树是带权值的树,与元素大小没有必然关系.
增大装载因子会增大元素冲突,查找效率变慢.
- 首元素与最后一个元素交换,此时最后一个元素就是最大值,不再进行整理.
- 除去最后一个元素,剩余的元素在排列成大根堆.
2. 编程题
2.1 洗牌
做题链接:
链接: 洗牌
题目描述:
题目解析:
一看这种洗牌之类的,各种各样的序列,一般都是找规律题,找到规律的式子,问题就能迎刃而解了,那么我们先来简单分析一下题目.
- 题目中的n表示每组有几张牌,k表示要洗牌几次.
- 1,2,3,4,5,6洗牌一次,先分成左右手两组,左手为1,2,3 . 右手为4,5,6.从右往左进行放牌,先放右手,再放左手.1,4,2,5,3,6 .当然我们也可以从左向右进行放牌,然后进行逆序.
- 题目分析就到这里了,接下来我们通过代码的角度来与大家一起做题.
- 需要逆序的代码.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
//t表示组数(共有几组数)
while(t-->0){
//n表示分成左右手两组牌,每组有n张牌
int n = in.nextInt();
//k表示要洗牌几次
int k = in.nextInt();
//arr数组存放牌的序列
int[] arr = new int[2*n];
//循环填充arr数组
for(int i = 0;iarr.length;i++){
arr[i] = in.nextInt();
}
//下面的while循环控制洗牌次数(n次)
while(k-->0){
//开辟新数组记录原数组洗牌
//如果使用原数组会进行覆盖
int[] newArr = new int[2*n];
for(int i = 0;i2*n;i++){
//分成奇偶数满足不同的规律
if(i % 2 == 0){
newArr[i] = arr[2*n-i/2-1];
} else{
newArr[i] = arr[n-i/2-1];
}
}
arr = newArr;
//逆序
reverse(arr);
}
for(int i = 0;i2*n;i++){
System.out.print(arr[i] +" ");
}
System.out.println();
}
}
public static void reverse(int[] arr){
int left = 0;
int right = arr.length-1;
while(left right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
- 不需要逆序的代码
import java.util.*;
public class Main
{
public static void playCard(int[] cards, int n, int k)
{
// i --> 2 * i
// i + n ---> 2 * i + 1
for(int i = 0; i k; ++i)
{
//一次洗牌的过程
int[] newCards = new int[cards.length];
//遍历编号为 0 ~ n - 1
for(int j = 0; j n; ++j)
{
newCards[2 * j] = cards[j];
newCards[2 * j + 1] = cards[j + n];
}
//注意这种修改引用的方式,我们传参修改引用,但是返回原来的函数
//数组并没有发生变化,因此在这里我们直接在本函数进行打印操作
cards = newCards;
}
//从上往下打印
//本函数进行打印
printCard(cards);
}
public static void printCard(int[] cards)
{
for(int i = 0; i cards.length - 1; ++i)
{
System.out.print(cards[i] + " ");
}
System.out.println(cards[cards.length - 1]);
}
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
int groups = s.nextInt();
for(int i = 0;i groups; ++i)
{
//读入每组数据
int n = s.nextInt();
int k = s.nextInt();
int[] cards = new int[2 * n];
for(int j = 0; j 2 * n; ++j)
{
cards[j] = s.nextInt();
}
//洗牌
playCard(cards, n, k);
}
}
}
2.2 MP3光标位置
做题链接:
链接: MP3光标位置
题目描述:
题目分析:
- 是不是这道题给人的第一眼感觉是头大,让人有一种窒息的感觉,不要被题目的长度蒙蔽了自己,题目越长越能给自己安全感,记住这句话.
- 这道题考察的就是逻辑性,其实这也可以看成是模拟题.
- 我们把歌曲总数分为小于等于4和大于4两种情况.因为小于等于4的时候不需要翻页.
- 接下来我们通过代码的角度进行分析.
- 自己写的代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//n表示歌曲的数量
int n = sc.nextInt();
//str存储输入的字符串(UUUU)
String str = sc.next();
//cur表示光标当前的位置
int cur = 1;
//歌曲数量小于等于4的情况
if (n 4) {
//取出字符串的每个字符
for (int i = 0; i str.length(); i++) {
char ch = str.charAt(i);
//U表示向上移动
if (ch == 'U') {
//如果当前位置,刚好在第一个
//向上移动之后,当前位置会跳到最后一首歌的位置)(末尾位置)
if (cur == 1) {
cur = n;
} else {
//当前位置不是在第一个位置的时候
//向上移动的时候当前位置减1
cur -= 1;
}
//下面表示向下移动
} else {
//向下移动的时候
//如果光标的当前位置在最后一个
//当前位置直接跳转到第一个位置
if (cur == n) {
cur = 1;
} else {
cur += 1;
}
}
}
//因为歌曲数目小于等于4,直接打印歌曲列表
for (int i = 1; i n; i++) {
System.out.print(i + " ");
}
System.out.println();
//cur表示当前位置
System.out.println(cur);
//下面的else表示歌曲数目大于4,
//此时需要记录顶部和底部的歌曲
} else {
//刚开始顶部为1位置,底部为4位置
int top = 1;
int bottom = 4;
for (int i = 0; i str.length(); i++) {
char ch = str.charAt(i);
//向上移动的时候
if (ch == 'U') {
//当前位置为1的时候
//cur跳转到n位置(最后一个位置)
//此时底部也跳转到n位置
//顶部为bottom - 3
if (cur == 1) {
cur = n;
bottom = n;
top = bottom - 3;
//当前位置等于顶部位置
} else if (cur == top) {
cur = top - 1;
top = top - 1;
bottom = top + 3;
} else {
cur -= 1;
}
//下面的else是向下移动的时候
} else {
//当前位置在最后一个的时候
//当前位置变为第一个位置
//顶部位置变为1
if (cur == n) {
cur = 1;
top = 1;
bottom = 4;
//当前位置等于bottom
} else if (cur == bottom) {
cur = bottom + 1;
bottom += 1;
top = bottom - 3;
} else {
cur += 1;
}
}
}
//打印屏幕上歌曲列表
for (int i = top; i bottom; i++) {
System.out.print(i + " ");
}
System.out.println();
System.out.println(cur);
}
}
}
- 别人的参考代码
import java.util.*;
import java.io.*;
public class Main
{
public static void mouseMove(String numStr, String orderStr)
{
//歌曲数量
int n = Integer.parseInt(numStr);
//指令数组： UD
char[] order = orderStr.toCharArray();
//当前鼠标所在的位置
int mouse = 1;
//显示列表所在的起始位置
int first = 1;
//指令处理
//n
if(n 4)
{
//循环处理每一个指令
for(int i = 0; i order.length; ++i)
{
//光标在第一首歌曲上时，按Up键光标挪到最后一首歌曲
if(mouse == 1 && order[i] == 'U')
mouse = n;
//光标在最后一首歌曲时，按Down键光标挪到第一首歌曲
else if(mouse == n && order[i] == 'D')
mouse = 1;
//其他情况下用户按Up键，光标挪到上一首歌曲
else if(order[i] == 'U')
--mouse;
//用户按Down键，光标挪到下一首歌曲
else if(order[i] == 'D')
++mouse;
}
//输出
//打印当前的显示列表
for(int i = 1; i n; ++i)
System.out.print(i + " ");
System.out.println(n);
//打印当前歌曲
System.out.println(mouse);
}
//n > 4
else
{
for(int i = 0; i order.length; ++i)
{
//屏幕显示的是第一页（即显示第1 – 4首）时，光标在第一首歌曲上
//用户按Up键后，屏幕要显示最后一页（即显示第7-10首歌），
//同时光标放到最后一首歌上。
if(first == 1 && mouse == 1 && order[i] == 'U')
{
//最右一页的起始位置
first = n - 3;
mouse = n;
}
//同样的，屏幕显示最后一页时，光标在最后一首歌曲上，
//用户按Down键，屏幕要显示第一页，光标挪到第一首歌上。
else if(first == n - 3 && mouse == n && order[i] == 'D')
{
first = 1;
mouse = 1;
}
//屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，
//屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。
else if(first != 1 && mouse == first && order[i] == 'U')
{
--mouse;
--first;
}
//屏幕显示的不是第一页时,光标在当前屏幕的最后一首歌时的
//按Down键，屏幕从当前歌曲的下一首开始显示，光标也挪到下一首歌曲
else if(first != n - 3 && mouse == first + 3 && order[i] == 'D')
{
first++;
mouse++;
}
//其它情况，只移动光标
else if(order[i] == 'U')
--mouse;
else if(order[i] == 'D')
++mouse;
}
//打印当前的显示列表
for(int i = first; i first + 3; ++i)
System.out.print(i + " ");
System.out.println(first + 3);
//打印当前歌曲
System.out.println(mouse);
}
}
public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String numStr;
while((numStr = reader.readLine()) != null)
{
String orderStr = reader.readLine();
mouseMove(numStr, orderStr);
}
}
}
小结:
- 找规律题一般找到了规律题目就会非常简单,得心应手,而且在我们写代码中,找规律题的规律也不是那么难找,我们需要列举题目的示例,根据例子找规律.我们以前做的兔子问题,说白了就是斐波那契变形,还有变形的杨辉三角,用暴力解出来了,但是超时了,然后列举了几组数字,没想到这么简单的规律题.
- 模拟题,一般考虑我们的逻辑思维,重要的是逻辑,考虑边界情况,根据边界情况划分区域,根据条件去求解即可,没有什么技术含量.
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
