1.小美的加法【简单题】
题意理解：
给定一个数组做连加操作，其中只能将一个加号变成乘号
将哪个加号变成乘号，使式子最后的结果最大
解题思路：
只有将两个相邻且乘机最大的数之间变成乘号后，才能保证整个式子结果最大
所以第一步找到这两个数的位置
在所有元素和中减去这两个元素，加上这两个元素的乘积即可。
这里采用滑动窗口来找相邻乘积最大的两个元素，其中滑动窗口大小为2.
注意：数组的元素顺序不能变，所以不能排序
1.滑动窗口解题
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len=in.nextInt();
long[] nums=new long[len];
for(int i=0;i<len;i++) nums[i]=in.nextLong();
Main main=new Main();
System.out.println(main.compute(nums));
}
public Long compute(long[] nums){
long result=0;
int maxNeighbor=0;
for(int i=0;i<nums.length-1;i++){
result+=nums[i];
if(nums[i]+nums[i+1]>nums[maxNeighbor]+nums[maxNeighbor+1]){
maxNeighbor=i;
}
}
result+=nums[nums.length-1];
result=result-nums[maxNeighbor]-nums[maxNeighbor+1]+nums[maxNeighbor]*nums[maxNeighbor+1];
return result;
}
}2.复杂度分析
时间复杂度：O(n) 遍历数组的时间耗费
空间复杂度：O(n) 数组存储的空间耗费
2.小美的数组操作【技巧】
题意理解：
给定一个数组，每次选中两个数，一个元素+1，一个元素-1
最终使数组中的众数出现的次数最多。
解题思路：
我的思路：求平均数，然后将数组排序，让所有的数都向平均数靠近。
对于平均数为整数的来说，可以实现。但对于平均数不为整数的发生错误。
借鉴大佬的思路：
个人理解：
对于平均数为整数的，所有数向平均数靠近。
对于平均数部位整数的，去掉一个元素，保证其他元素的平均数是整数，此时重复上述操作。 关键：如何挑选去除的那个元素呢，即如何选取垃圾数。
贪心思路：选取最大值或最小值为垃圾数，将多余的位数分给垃圾数——将avg+1和avg-1分别作为众数来计算，进行比较。
注意：+1和-1操作是对称的，有k个+1则有k个-1操作
对于[2,2,4,4]来说，不操作，2/4都是众数，都有两个。但是不满组足众数最多。
操作后：[3,3,3,3]，众数是3有4个
1.贪心解题
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = in.nextInt();
long[] nums = new long[len];
for (int i = 0; i < len; i++) {
nums[i] = in.nextLong();
}
Main main = new Main();
System.out.println(main.compute(nums));
}
public long compute(long[] nums){
long count=0;
int len=nums.length;
Arrays.sort(nums);
long sum=0;
for(int i=0;i<len;i++){
sum+=nums[i];
}
if(sum%len==0){
//没有垃圾数
count=countK(nums,sum/len,0,len-1)/2;
}else{
//选最大的数为垃圾数
long avg=(sum-nums[len-1])/(len-1);
//丢垃圾
long countMA1=countK(nums,avg,1,len-2)+Math.abs(avg-nums[0])+Math.abs((sum-nums[len-1]-avg*(len-1)));//中间得操作+第一个数取+垃圾桶丢
long countMA2=countK(nums,avg+1,1,len-2)+Math.abs(avg+1-nums[0])+Math.abs((sum-nums[len-1]-(avg+1)*(len-1)));//中间操作+第一个数取+垃圾桶拿
//选最小的数为垃圾数
avg=(sum-nums[0])/(len-1);
long countMI1=countK(nums,avg,1,len-2)+Math.abs(avg-nums[len-1])+Math.abs((sum-nums[0]-avg*(len-1)));//中间操作数+最后一个数丢+垃圾桶丢
long countMI2=countK(nums,avg+1,1,len-2)+Math.abs(avg+1-nums[len-1])+Math.abs((sum-nums[0]-(avg+1)*(len-1)));//中间操作数+最后一个数丢+垃圾桶拿
count=Math.min(Math.min(countMI1,countMI2),Math.min(countMA1,countMA2))/2;
}
return count;
}
public long countK(long[] nums,long avg,int left,int right){
long count=0;
for(int i=left;i<=right;i++){
if(nums[i]<avg){
count+=avg-nums[i];
}
if(nums[i]>avg){
count+=nums[i]-avg;
}
}
return count;
}
}代码里有一个技巧：
2.复杂度分析
时间复杂度：O(n*log(n)) 排序的时间复杂度
空间复杂度：O(n) 排序所需的额外空间
主要是Arrays.sort的损耗
3.小美的01串翻转【技巧】-动态规划
题意理解：
这道题理解起来有点绕：首先明确： 一个01串的权重：使得相邻位不同的最小操作数
其次：统计所有子串（包含其本身、长度>=2的）权重的和。即为所求的值。
解题思路：
不成熟且错误的思路，故借鉴大佬思路：
个人理解：
操作字符串的目的：为了使字符串相邻字符不相同
那么：长度为s.len 的满足条件的子串有两种，要么以1开头，要么以0开头
即：s=10001 那么满足条件的修改为： 10101 或01010
将其子串与这两个目标串进行比较,同一位置值不同则说明需要修改，统计不同的字符，即为修改次数。
两个修改次数取最小值，即为所求。
上表中的每个位置[i,j]表示从i到位置j的子串的权值是多少
重新发现思路：
这道题目可以用动态规划来解决。其中如何和动态规划结合起来呢。
首先是子串，子串有一个开始位置和起始位置，其中每个位置有两种可能0或1
（1）定义三维dp数组
dp[i][j][0]表示从i开始到j位置的子串，若以0结尾的权值
dp[i][j][1]表示从i开始到j位置的子串，若以1结尾的权值
（2）递推公式
dp[i][j][x] 表示从i到j位置得子串，以x结尾的权值
//子串当前以0结尾
dp[i][j][0]=dp[i][j-1][1];
dp[i][j][1]=dp[i][j-1][0]+1;
//当前以1结尾
dp[i][j][0]=dp[i][j-1][1]+1;
dp[i][j][1]=dp[i][j-1][0];（3）初始化：
则i,j的权值=min(dp[i][j][0],dp[i][j][1])
初始化： 对于dp[i][j]的值总是和dp[i][j-1]有关，所以从左到右填数
dp[i][i]=0
1.解题
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String num = in.nextLine();
Main main = new Main();
System.out.println(main.compute(num));
}
public int compute(String num){
/**
* dp[i][j][x] 表示从i到j位置得子串，以x结尾的权值
* //当前以0结尾
* dp[i][j][0]=dp[i][j-1][1];
* dp[i][j][1]=dp[i][j-1][0]+1;
* //当前以1结尾
* dp[i][j][0]=dp[i][j-1][1]+1;
* dp[i][j][1]=dp[i][j-1][0];
* }
* 则i,j的权值=min(dp[i][j][0],dp[i][j][1])
* 初始化： 对于dp[i][j]的值总是和dp[i][j-1]有关，所以从左到右填数
* dp[i][i]=0
*/
int sum=0;
int len=num.length();
int[][][] dp=new int[len][len][2];
for(int i=0;i<len;i++){
if(num.charAt(i)=='0'){
dp[i][i][0]=0;
dp[i][i][1]=1;
}else{
dp[i][i][0]=1;
dp[i][i][1]=0;
}
}
//遍历所有的子串
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(num.charAt(j)=='0'){//当前以0结尾
dp[i][j][0]=dp[i][j-1][1];
dp[i][j][1]=dp[i][j-1][0]+1;
}else{//当前以1结尾
dp[i][j][0]=dp[i][j-1][1]+1;
dp[i][j][1]=dp[i][j-1][0];
}
sum+=Math.min(dp[i][j][0],dp[i][j][1]);
}
}
return sum;
}
}2.复杂度分析
时间复杂度：O(n^2) 遍历所有子串（开始和截止位置）
空间复杂度：O(n^3) 记录结果值得损耗
4.小美的外卖订单编号【简单题】
题意理解：
订单号：[1,m],超过m时，重新从1开始计数
题目的问题是：第q个订单的订单编号x是多少?
解题思路：
编号1到m，很容易想到取余的操作。
一个数对m取余获得[0,m-1]的区域
第1单： 1%m==1
第2单： 2%m==2
……
第m单：m%m==0，此时单号应该是m，而不是0
除第m单特殊之外，其余单没有什么不同。
1.解题
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len=in.nextInt();
int[][] nums=new int[len][2];
for(int i=0;i<len;i++){
nums[i][0]=in.nextInt();
nums[i][1]=in.nextInt();
}
Main main=new Main();
int[] result= main.compute(nums);
for(int i=0;i<len;i++){
System.out.println(result[i]);
}
}
public int[] compute(int[][] nums){
int[] result=new int[nums.length];
for(int i=0;i<nums.length;i++){
if(nums[i][1]%nums[i][0]==0){
result[i]=nums[i][0];
}else{
result[i]=nums[i][1]%nums[i][0];
}
}
return result;
}
}2.复杂度分析
时间复杂度：O(n) 遍历的时间损耗
空间复杂度：O(n) 保存结果的时间损耗
5.小美的数组操作2【简单题】
题意理解：
根据选择的数，做出对应操作，最后判断数组是否是递增序列。
是输出Yes,否则输出No
解题思路：
根据输入，做指定操作，
遍历检查数组是否是递增的
1.解题
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t=in.nextInt();
Main main=new Main();
String[] result=new String[t];
for(int i=0;i<t;i++){//t次询问
int n=in.nextInt();//数组长度
int k=in.nextInt();//k次操作
int[] nums=new int[n];
int[][] kOpt=new int[k][2];
for(int j=0;j<n;j++) nums[j]=in.nextInt();
for(int j=0;j<k;j++){
kOpt[j][0]=in.nextInt();
kOpt[j][1]=in.nextInt();
}
result[i]=main.compute(nums,k,kOpt);
}
for(int i=0;i<t;i++){
System.out.println(result[i]);
}
}
public String compute(int[] nums,int k,int[][] kOpt){
for(int i=0;i<k;i++){
int u=kOpt[i][0]-1;
int v=kOpt[i][1]-1;
nums[u]++;
nums[v]--;
}
for(int i=1;i<nums.length;i++){
if(nums[i]<nums[i-1]) return "No";
}
return "Yes";
}
}2.复杂度分析
时间复杂度：O(n) 遍历数组进行检查的时间损耗
空间复杂度：O(n) 保存结果的空间损耗
6.小美的数组构造【较难】-动态规划
题意理解：
数组a和数组b对应位置数不同，但a和b元素和相等。
构造符合条件的正整数b有多少种方式。
解题思路：
没思路，这道题。
结果这道题是一个动态规划类的题目。
我去看了下别人的思路，然后猛的一看，不懂。纯看代码分析思路太难受了。啊啊啊啊
理解了，分析一下：
这道题目还是一个动态规划的题，里面涉及状态转移的思路。
以1 1 1数序列来演示
dp[i][j]:表示sum=i,长度为j的串的可能的构造次数。
则有：dp.size=(sum+1,len+1)=(4,4)其中特别的要求：b的元素是正整数，所以b的元素>=1
根据题意：dp[0][j] 和dp[i][0]是没有意义的，全部初始化为0dp[j][j]（j>=1）可以构造出全1的数列，若对应位置 a[j-1]不等于1，则该位置上可以取1，一种构造方式，否则为0.【题目要求对应位置元素不一致】
当计算dp[3][3]时，我们可以将3分解为：（1，2）（2，1）两种方式
当第3位取2时，前面的数有dp[1][2]种方式(nums[3-1]=1,此位置可以取2)
当第2位取1时，前面的数有dp[2][2]种方式(nums[3-1]=1,此位置不可以取2)——不符合要求
即dp[3][3]=dp[1][2]=0
具体步骤来说：
（1）首先定义二维dp数组，其中size 为[sum+1][len+1]
dp[i][j]表示和为i，长度为j的，符合条件的构造方式有几种。
（2）递推公式
dp[i][j]首先判断，将sum=i分解为两部分，有多少种排列
如：sum=3 则有（1，2）、（2，1）两种方式
sum=i时，第j位的取值范围是[1,j-1]
其中第j位的值==a[j-1]时，j值不能取，应为会和a的j-1位置重复，不符合要求
当第j位取k值时，sum=i-k,长度=j-1有dp[i-k][j-1]种构造方法
遍历k值，若第j位能取k，则dp[i][j]+=dpdp[i-k][j-1]
(3) 初始化
dp[0][j] 和dp[i][0]是没有意义的，全部初始化为0
dp[j][j]（j>=1）可以构造出全1的数列，若对应位置 a[j-1]不等于1，则该位置上可以取1，一种构造方式，否则为0.【题目要求对应位置元素不一致】
特别的：
这道题目计算的数值会很大，所以元素及需要求和的值定义为long
同时某个元素也可能会很大，所以在做加时，及时对元素做取模操作(%(7+10^9))
这道题目对我来说算是这7个里面最难的了，理解题想了半天，然后看明白了，不知道咋动手，想到应该用动态规划做，有没有思路了。想到了dp[sum][len]，搞明白意义，理清楚之后，突然豁然开朗，也不是很难了，好像。但是搞明白还是花了很长时间。
1.解题
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
long[] arrA = new long[len];
for(int i=0;i<len;i++){
arrA[i]=scanner.nextLong();
}
Main main=new Main();
System.out.println(main.compute(arrA));
}
public long compute(long[] nums ) {
long sum = 0;
int len = nums.length;
for (int i = 0; i < nums.length; i++) sum += nums[i];
long[][] dp = new long[(int) (sum + 1)][len + 1];//求dp[sum][0];
for (int i = 1; i < sum + 1; i++) {
Arrays.fill(dp[i], 0);
if (nums[0] == i) {
dp[i][1] = 0;
} else {
dp[i][1] = 1;
}
}
for (long i = 2; i <= sum; i++) { //遍历和sum
for (int j = 2; j <= len; j++) { //遍历长度len
/**
* 计算dp[i][j]只需要固定第j个位置上的数字+dp[i-1][j-1]集合
* 其中位置j可以取的值：从1开始，到i-1,用k来遍历，为了不和原串a冲突
* 要判断j位置不可以取nums[j-1]的值
*/
long res=0;
for (int k = 1; k <= i - 1; k++) {
if (nums[j - 1] == k) continue;
res= (long) ((res%(7+Math.pow(10,9)))+ (dp[(int)i - k][j - 1]%(7+Math.pow(10,9))));
}
dp[(int)i][j]=res;
}
}
return dp[(int)sum][len];
}
}2.复杂度分析
时间复杂度：O(n^2) for循环时间损耗
空间复杂度：O(n^2) dp数组空间损耗
7.美团商家注册系统【简单题】
题意理解：
这道题不难，考验数据的一个处理过程。
其中我们需要统计的信息包含： 店铺名，主店地址，分店地址
其中一些操作包含：
只包含小写字母的店铺名；
存在的店铺，比较地址是否和主店一致：
和主店一致：注册失败
和主店不一致：注册为分店
注册为分店时：店铺名一致，地址一致，注册失败
按店铺名升序输出
解题思路：
使用两个map来对数据进行组织
businessMap维护店铺名和主店地址
businessInfoMap维护店铺名，分店地址Set
Set将分店地址去重，即可获得分店数量。
1.解题
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
Map<String,String> businessMap=new HashMap<>();
Map<String, Set<String>> businessInfoMap=new HashMap<>();
public static void main(String[] args) {
Main main=new Main();
Scanner in = new Scanner(System.in);
int n=in.nextInt();
in.nextLine();
for(int i=0;i<n;i++){
String business=in.nextLine();
main.compute(business.split(" "));
}
String[] names=new String[main.businessMap.size()];
int index=0;
for(String name:main.businessMap.keySet()){
names[index++]=name;
}
Arrays.sort(names);
for(String name:names){
System.out.println(name+" "+main.businessMap.get(name)+" "+main.businessInfoMap.get(name).size());
}
}
public void compute(String[] businessInfo){
//只能是小写字母
char[] letter=businessInfo[0].toCharArray();
for(int i=0;i<letter.length;i++){
if(letter[i]>'z'||letter[i]<'a') return;
}
//注册
if(!businessMap.containsKey(businessInfo[0])){//未注册过
//注册
businessMap.put(businessInfo[0],businessInfo[1]);
businessInfoMap.put(businessInfo[0],new HashSet<>());
}else{
//已经注册过:是分店吗？
if(!businessMap.get(businessInfo[0]).equals(businessInfo[1])){//是分店
businessInfoMap.get(businessInfo[0]).add(businessInfo[1]);
}
}
}
}代码有个能改进的地方：关于按照餐厅名升序输出
List<String> keys=new ArrayList<>(businessMap.keySet())
Collections.sort(keys);
2.时间复杂度分析
时间复杂度：O(n*logn)主要耗费在店铺排序
空间复杂度：O(n)数据保存得空间耗费
总结
题目见的得少，结果看到题目的时候，看了半天没理解题目的意思
对于int long的范围要有概念，否则会导致结果出错
看懂题目后，大部分其实是简单题，一些难一点的题目是动态规划问题。
关键点在于如何和动态规划思路联合起来，说起来还是题目做的少了。
