小红书-2020校招测开（一）

假如一个作业的页面走向是:1,2,3,4,2,1,5,2,1。当内存块数量为3时,请问LRU,FIFO这两种置换算法的缺页次数各是多少? ()

答案
6,7
题解
LRU: least recently used

内存为3，读1,2,3,4,2,1,5,2,1

1, 2, 3 为3次page fault

读4时，4取代1，page fault，内存为 4,2,3

读2时，2存在

读1时，page fault.                 内存更新为 4,2,1

读5，page fault，                  内存更新为 5,2,1

读2，2存在

读1，1存在

总共6 次page fault.

FIFO: First in First out

1,2,3 为3次page fault. 内存更新为 1,2,3

读4, page fault.                     内存更新为 4,2,3

读2，2存在

读1，page fault.                   内存更新为 4,1,3

读5，page fault.                   内存更新为 4,1,5

读2，page fault                    内存更新为 2,1,5

读1，1存在

总共7次page fault.

以下关于sql查询语句执行顺序描述正确的是：（）

答案
from->where->group by→having→select→order by
题解
(7) SELECT

(8) DISTINCT

(1) FROM

(3) <join_type> JOIN </join_type>

(2) ON

(4) WHERE

(5) GROUP BY

(6) HAVING

(9) ORDER BY

(10) LIMIT

标号为执行顺序
3. 一位老师有2个推理能力很强的学生，他告诉学生他手里有以下的牌：
黑桃：2 ， 5 ， 7 ， 9 ， J ， K
红心：3 ， 4 ， 9 ， J ， K
梅花：5 ， 8 ， 9 ， Q
方块：2 ， 7 ， 8
然后从中拿出一张牌，告诉A这张牌的大小，告诉了B这张牌的花***r>A：我不知道这张是什么牌
B：我就知道你肯定不知道这张是什么牌
A：现在我知道
B：现在我也知道了
请问这张是什么牌？（）
答案
方片8
题解
由第一个条件可知，这个数字必须出现两种以上花***r>由第二个条件可知，这种花色的所有数字必须出现两次以上，所以排除红心、梅花，只剩黑桃和方块；
由第三个条件可知，这个数字在黑桃和方块仅出现一次；
由第四个条件可知，这种花色里符合以上条件的数字唯一，所以排除黑桃，只剩方块8；
句1：排除了只出现一次的值（3，Q）；
句2：花色中所有的值都至少出现两次，排除红心和梅花；
句3：排除2和7，此时还剩5种可能（黑桃5、9、J、K和方块8）
句4：如果是黑桃的话，B不能唯一确定哪张牌，只能是方块。
4. 下列排序算法在最好情况下的时间复杂度为O(n)的是()
答案
冒泡排序插入排序桶排序

编程题

薯券使用问题 - 动态规划
某小红薯在小红书的活动中抽奖中了一定价值的薯券，这些薯券可以用来购买一批商品，求有多少种购买组合。其中一件商品可以买多件。
输入:薯券金额、商品分别价格
输出 :组合数

题解思路
f(i,j)表示选择前i种商品构成消费券价值为j的方案数量，price_i表示第i种商品的价格。
状态转移：
f(i,j) = f(i-1,j)+ f(i-1,j-1price_i)...+f(i-1,j-kprice_i), k=(j/price_i)
因为
f(i,j-price_i) = f(i-1,j-price_i)+.....+f(i-1,j-k*price_i)
故状态转移方程：
f(i,j) = f(i-1,j)+f(i,j-price_i)
dp[j]为当前价格j时的方案数，dp[0]就是价格为0时有一种方案（不给就好了），然后从每张券开始遍历就好了。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        String[] tmp = s.substring(1, s.length() - 1).split(",");
        int[] arr = new int[n + 1];
        int[] p = new int[tmp.length];
        for(int i = 0; i < tmp.length; i++) {
            p[i] = Integer.parseInt(tmp[i]);
        }

        arr[0] = 1;

        for(int a : p) {
            for(int i = a; i < arr.length; i++) {
                arr[i] = (arr[i] + arr[i - a]);
            }
        }

        System.out.println(arr[n]);
    }

}

2.字符串倒序
薯队长带着小红薯参加密室逃脱团建游戏，首先遇到了反转游戏，小红薯们根据游戏提示收集了多个单词线索，并将单词按要求加一个空格组成了句子，最终要求把句子按单词反转解密。说明：收集的时候单词前后可能会有多个空格，反转后单词不能有多个空格，具体见输入输出样例。
输入一个字符串。包含空格和可见字符。长度<=100000。
输出一个字符串，表示反转后结果。
输入
the sky is blue!
输出
blue! is sky the

import java.util.*;
public class Main{
public static void main(String[] args)
{
    Scanner in=new Scanner(System.in);
    String str=in.nextLine();
    List<String> words=Arrays.asList(str.split("\\s+"));
    Collections.reverse(words);
    String res=String.join(" ", words);
    System.out.print(res);
}
}

笔记精选 - 动态规划
薯队长写了n篇笔记，编号从1~n,每篇笔记都获得了不少点赞数。
薯队长想从中选出一些笔记，作一个精选集合。挑选的时候有两个规则：
1.不能出现连续编号的笔记。
总点赞总数最多
如果满足1，2条件有多种方案，挑选笔记总数最少的那种
输入包含两行。第一行整数n表示多少篇笔记。第二行n个整数分别表示n篇笔记的获得的点赞数。
（0<n<=1000, 0<=点赞数<=1000)
输出两个整数x,y。空格分割。
x表示总点赞数，y表示挑选的笔记总数。
输入
4
1 2 3 1
输出
4 2

题解
dp[i] = x 表示从i开始选笔记，最大点赞数为x。dpNum[i]表示此时选取的次数
动态转移方程为dp[i] = max(dp[i+1], dp[i+2]+nums[i])
由于本题还需要求次数，所以再构造一个dpNum数组，用来存储得到dp[i]时，选取的笔记次数。状态方程与dp数组类似，当选取了nums[i]，则dpNum[i] = dpNum[i+2]+1,否则在不选取的情况下，dpNum[i]=dpNum[i+1]
从后往前迭代求解，所以数组需初始化大小为n+2,初值均为0(方便求解dp[n-1])

import java.util.*;
public class Main{

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        int[] nums = new int[length];
        for(int i = 0; i<length; i++){
            nums[i] = in.nextInt();
        }
        // rob houses
        int[] count = new int[length];
        int[] dp = new int[length];
        dp[0] = nums[0];
        count[0] = 1;
        if(length == 1){
            System.out.print(dp[0] + " " + 1);
        }
        dp[1] = Math.max(nums[0], nums[1]);
        count[1] = 1;
        for(int i = 2; i<length; i++){
            // take current
            if(nums[i] + dp[i-2] > dp[i-1]){
                dp[i] = nums[i] + dp[i-2];
                count[i] = 1 + count[i-2];
            }else{
                // don't take current
                dp[i] = dp[i-1];
                count[i] = Math.min(count[i-1], 1 + count[i-2]);
            }
        }
        System.out.println(dp[length-1]+" "+count[length-1]);
    }
}