百度20220914

题解链接

有n个怪物排成一排，第i个怪物的血量为ai。小红有两个技能可以打怪：
1. 强力攻击，消耗1mp，对一只怪物造成1点伤害。
2. 踏前斩，消耗5mp，对当前怪物造成1的伤害，同时剑气将波及后两个怪物，对下一个怪物造成2点伤害，对下下个怪物造成3点伤害。
如果一个怪物受伤后血量小于等于0，则怪物死亡。死亡后怪物的尸体依然占据一个位置，会被踏前斩的剑气打到。
小红想知道，击杀全部怪物至少需要花费多少mp？

输入一个n和n个数字作为所有怪物血量
输出最小使用的mp

input:
5
1 2 4 2 3

output:
10

此处注意若以1，2，3这样遍历会引起断层，需要先遍历第三个能否扣3，逆序，从大到小，才不会断层，反例如 1，2，3，4，5，只能塔前赞一次

小红拿到了一段java代码，请你判断其中最多有多少层for循环嵌套。
保证代码合法，且不含注释。循环语句只有for，条件语句只有if，循环语句和条件语句保证包含大括号用来控制范围。
代码中只有一个类和一个主函数。

多行输入
输出最大嵌套数

input：
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int a = 0 , b = 0;
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            if ( a < b ) {
                a += b / 2;
            }
            for (int j = 0; j < n; j++) {
                b++;
                a += b;
            }
            for (int j = 1; j < n; j *= 2) {
                b--;
            }
        }
        System.out.println(a);
    }
}

output:
2

当遇到文本解析类型的题目时，要用字符为基本单位，而不要使用行为单位，容易错

京东20220904

题目描述
定义一个括号串的权值为，它的最长合法括号子序列的长度。
例如，"())())的权值是4，它的最长合法括号子序列为"()()”
现在求一个给定括号串的所有子串权值之和。
输入描述：
一个仅包含'('和')'的字符串，长度不超过2e5。
输出描述：
所有子串的权值和。

input:
(()())

output:
26

解释：
权值为2的子串有2个
权值为4的子串有2个

题解
逆向思维，如果正向dfs还需要考虑什么情况下才能组成正确的括号，但是，逆向的话，只需要考虑每一个正确的括号杯多少个子窜包含！
当遇到多个子窜序列时，考虑是否能从解集入手，判断解集会包含的条件，然后从这些条件入手，遍历所有的条件，得出结果

360笔试

取矩阵中的最大正方形，dp思路：dp(i,j) = min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1)) + 1,dp元素表示以该点为右下的正方形的最大边长

2.重排序列
单调栈解决，若用栈但是又有从头开始遍历的需求，可以先把栈填满，再把栈复制到一个链表中，如果一开始就用链表，则编码复杂度会很高

滴滴笔试

第一题 选取尽量多的元素，但其中最大值不能超过平均值的k倍

思考：用滑动窗口从小到大遍历失败了，若遇到从小到大遍历失败，则首先改为从大到小遍历(先选大，再选小)，做题经验，再考虑是否越界，如果题目的范围不大，考虑直接遍历所有初始化所有解集

第二题 定义f(x)=x的十进制各位的异或和，最多70000次询问，询问[L,R]中f(x)为t的值有多少个。1<=L<=R<=70000

所有0-9的异或结果只可能是在0-16中取值！！