3.16美团复盘
第一题
题目分析
这一题比较简单，直接模拟即可，sum(a)-t1-t2;
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long sum=0;
while(n-->0){
sum+=sc.nextInt();
}
sum-=sc.nextInt();
sum-=sc.nextInt();
System.out.println(sum);
}
}
第二题
思路分析
- 同样是一道模拟题
- 我们可以统计大写数目
- 全部变为小写：cnt，如果第一个字母大写（cnt–）
- 全部变为大写：n-cnt;(小写字母的数量)
- 比较两个值，输出最小的
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
char[] ch=sc.next().toCharArray();
int cnt=0;//大写的数量
for(int i=0;i<ch.length;i++){
if(isA(ch[i]))cnt++;
}
int t1=cnt;//全部变为小写
if(isA(ch[0]))t1--;
int t2=ch.length-cnt;//全部变为大写
System.out.println(Math.min(t1,t2));
}
static boolean isA(char c){
return c>='A'&&c<='Z';
}
}
第三题
题意分析
考察知识点：快速幂算法
static long qmi(int a,int k,int q){ long res=1; long t=a; while(k>0){ if((k&1)==1)res=(res*t)%q; k=k>>1; t=(t*t)%q; } return res; }我们只需要统计每个下标对应的翻倍次数，而后计算即可
import java.util.*;
class Main{
static int mod=1_000_000_007;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int q=sc.nextInt();
int[] a=new int[n+1];
for(int i=1;i<=n;i++)a[i]=sc.nextInt();
int[] pow=new int[n+1];
Arrays.fill(pow,q);
for(int i=1;i<=q;i++){
int index=sc.nextInt();
pow[index]--;
}
long sum=0;
for(int i=1;i<=n;i++){
sum = (sum+ qmi(2, pow[i], mod) * a[i] % mod) % mod;
}
System.out.println(sum);
}
static long qmi(int a,int k,int q){
long res=1;
long t=a;
while(k>0){
if((k&1)==1)res=(res*t)%q;
k=k>>1;
t=(t*t)%q;
}
return res;
}
}
题目四
1.树状数组（知识补充）
1.1lowbit
//求二进制最后一位1和后边0形成的数；11000则为 1000()
static int lowbit(int x){8
return x&-x;
}
1.2 树状数组
-
应用场景：支持单点修改和区间查询的数据结构;
- 区间和：两个前缀和相减即可
- 区间乘积
- 区间异或
-
注意下标从1开始
-
一些操作
- x 上一个c数组的右边界为 x-lowbit(x);
- x 的祖先节点为: x+lowit(x);
//1.初始化，建树操作
//针对每个节点，把当前的值"贡献给父节点"
void init(){
for(int i=1;i<=n;i++){
c[i]+=a[i];
int j=i+lowbit(i);
if(j<=n){//父节点在范围内
c[j]+=c[i];
}
}
}
//2.求前缀和即 [1....x]的和
static int sum(int x){
int sum=0;
while(x>0){
sum+=c[x];
x=x-lowbit(x);
}
return sum;
}
//3. 单点修改a[x],我们只修改管辖a[x] 的c[y];向后遍历
void add(int x,int k){//给a[x]加上k
while(x<=n){
c[x]=c[x]+k;
x=x+lowbit(x);
}
}
1.2题目分析
思路分析
- 我们发现 a[i]取值只有1和2两个，所以我们可以统计出所有的众数为2的区间 [l,r]即可
- 我们令 1=-1;2=1;则对于每一个 r 如果sum[l,r]>0则众数为2
- 为了求区间和我们可以使用前缀和数组来维护，但是搜索时会超时，所以我们使用树状数组维护左边小于我们的数
- 在这里我们使用前缀和作为下标，而每个前缀和的权值作为值
- 如果体现左边的: 从左都又遍历即可
继续分析
- 我们发现前缀和的取值范围为[-n.n],而树状数组下标从1开始，所以我们增加一个偏移量 n+1;
- 此时 取值范围为[1,2n+1],所以tr长度应该为 2n+2
import java.util.*;
class Main{
//树状数组的数据结构
static int n;
static int[] tr;
static int lowbit(int x){
return -x&x;
}
static void add(int x,int k){
while(x<=n+n+2){
tr[x]+=k;
x=x+lowbit(x);
}
}
//查找x位置的前缀和
static int get(int x){
int sum=0;
while(x>0){
sum+=tr[x];
x=x-lowbit(x);
}
return sum;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
tr=new int[2*n+100];
int[] a=new int[2*n+100];
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
}
int sum=0;//统计前缀和
add(sum+n+1,1);//前缀和为0也应该加入
long ans=0;//统计众数和
for(int i=1;i<=n;i++){
if(a[i]==1){//1看作-1;
sum-=1;
}else {//2看作1
sum+=1;
}
ans+=get(sum+n);//统计闭sum+n+1小的数，也就是为2的区间
add(sum+n+1,1);//修改对应位置的数
}
ans=ans+(long)n*(n+1)/2;//注意这里防止爆int
System.out.println(ans);
}
}
题目五
思路分析
- 思路一：利用归并求出每一个区间的逆序对，而后分别统计 [1,i-1],[i+1,n]和两个数分别位于两个区间的逆序对即可（考场思路）
树状数组
- 当 i 位置取反后
- 增加 i-1个逆序对
- 减少 的逆序对为 前边比a[i] 大的，后边比a[i]小大，所以我们用树状数组求出这两部分即可
import java.util.*;
class Main{
//维护的时x的左边有多少个数比他大
static int n;
static int[] tr;
static int lowbit(int x){
return -x&x;
}
static void add(int x,int k){
while(x<=n){
tr[x]+=k;
x=x+lowbit(x);
}
}
static int get(int x){
int sum=0;
while(x>0){
sum+=tr[x];
x=x-lowbit(x);
}
return sum;
}
public static void main(String[] args){
long tot=0;//逆序对数量
//统计右边比这个数小的数有多少
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
tr=new int[n+1];
int[] a=new int[n+1];
for(int i=1;i<=n;i++)a[i]=sc.nextInt();
int[] low=new int[n+1];//对应位置下标，有多少个数比他小
long[] ans=new long[n+1];
//统计左边比该数大的
int[] greater=new int[n+1];
for(int i=1;i<=n;i++){
int y=a[i];
greater[i]=get(n)-get(y);//比y大的数,
tot+=greater[i];
add(y,1);
}
Arrays.fill(tr,0);
for(int i=n;i>=1;i--){
int y=a[i];//坐标
low[i]=get(y);
add(y,1);
}
for(int i=1;i<=n;i++){
ans[i]=tot+i-1-low[i]-greater[i];
System.out.print(ans[i]+" ");
}
}
}
