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]是没有意义的，全部初始化为0

       dp[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++) { //遍历和sumfor (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的范围要有概念，否则会导致结果出错

看懂题目后，大部分其实是简单题，一些难一点的题目是动态规划问题。

关键点在于如何和动态规划思路联合起来，说起来还是题目做的少了。