思杰2021批笔试题解

思杰2021批笔试题解

总结：Java废物踩了好多坑最后才AK…

T2

题目大意：给出一个01串，但此操作可以选择一个点x，将[x,n]的01序列全异或1，问得到目标串s的最小操作次数。
l e n ∣ S ∣ < = 1 e 6 len|S|<=1e6 len∣S∣<=1e6

当然一眼秒也是可以的（逃

说下套路：区间操作考虑差分序列。。。

设差分序列 b [ i ] = a [ i ] b[i]=a[i] b[i]=a[i] x o r xor xor a [ i − 1 ] a[i-1] a[i−1],那么区间异或 [ l , r ] [l,r] [l,r]即为 b [ l − 1 ] b[l-1] b[l−1]和 b [ r ] b[r] b[r]的单点操作.

那么只需要判断 a [ 1 ] a[1] a[1]为0/1，以及 a [ i ] a[i] a[i] x o r xor xor a [ i − 1 ] a[i-1] a[i−1]是否为1即可。

（难得见到正常笔试题…

import java.io.*;
import java.util.*;public class zbr01
{public static long mod=1000000007;public static int theFinalProblem(String target){char tmp=target.charAt(0); int ans=0;if(tmp=='1') ans++;for(int i=1;i<target.length();i++){char p=target.charAt(i),q=target.charAt(i-1);if(p!=q) ans++;}return ans;}public static void main(String[] args){String s="0011";System.out.println(theFinalProblem(s));}
}

T3

题目大意：如果在几个单词中，每个字母的出现次数都一样，则称为他们互为 a n a g r a m s anagrams anagrams。
所有 a n a g r a m s anagrams anagrams意思相同（就是如果有多个可用单词你可以随便挑一个用）
给出n个单词，m个句子。对每一个句子，问在已有的单词中，有几种能组成该句子的方案数。
n < = 1 e 6 n<=1e6 n<=1e6

怎么又是hash…对每个字符串的，每种字母出现次数进行hash，然后map判断即可。
（笔试题怎么天天看见hash…怎么每套题必有hash…

（以及强烈谴责毒瘤公司卡 m o d = 1 e 9 + 7 mod=1e9+7 mod=1e9+7！！！ 改成 m o d = 1 e 9 + 9 mod=1e9+9 mod=1e9+9才过hhh

剩下的就是没啥技术含量的大大大大大模拟了…人已经写吐了.jpg

import java.io.*;
import java.util.*;public class zbr01
{public static long mod=1000000009;public static List <Long> countSentences(List <String> wordSet,List <String> sentences){Map<Long,Long> mp = new HashMap<Long,Long>();List <Long> X=new ArrayList();int []cnt=new int [30];for(int i=0;i<wordSet.size();i++){for(int j=0;j<=25;j++) cnt[j]=0;String tmp&#(i);long p=0,ans=1;for(int j=0;j<tmp.length();j++){char q=tmp.charAt(j);cnt[q-'a']++;}for(int j=0;j<=25;j++) p=(p*233+cnt[j])%mod;boolean c&#ainsKey(p);if(c==false) mp.put(p,(long)1);else mp.put((p)+1);}for(int i=0;i<=25;i++) cnt[i]=0;for(int i=0;i<sentences.size();i++){String tmp&#(i);long ans=1;for(int k=0;k<=25;k++) cnt[k]=0;for(int j=0;j<tmp.length();j++){char q=tmp.charAt(j);if(q==' '){long p=0;for(int k=0;k<=25;k++) p=(p*233+cnt[k])%mod;boolean c&#ainsKey(p);if(c==false) ans=0;else{long x&#(p);ans*=x;}for(int k=0;k<=25;k++) cnt[k]=0; p=0;}else cnt[q-'a']++;}long p=0;for(int k=0;k<=25;k++) p=(p*233+cnt[k])%mod;boolean c&#ainsKey(p);if(c==false) ans=0;else{long x&#(p);ans*=x;}X.add(ans);System.out.println(ans);}return X;}public static void main(String[] args){List <String> s=new ArrayList();s.add("the"); s.add("bats"); s.add("tabs");s.add("in"); s.add("cat"); s.add("act");List <String> t=new ArrayList();t.add("cat the bats"); t.add("in the act"); t.add("act tabs in");countSentences(s,t);}
}

T1

日常由于毫无价值被扔到最后…

题目大意：Java hashmap的板子题…就略略略了…

以及我才知道Java的Float不能用==比较…人傻了.jpg

p = = q p==q p==q得写成 M a t h . a b s ( p − q ) < 0.00000001 Math.abs(p-q)<0.00000001 Math.abs(p−q)<0.00000001…Java太毒了…学到许多

（C++怎么好像很少考虑这种精度问题…Java你怎么回事

import java.io.*;
import java.util.*;public class zbr01
{public static int [][]R=new int[105][105];public static int priceCheck(List <String> products,List<Float> productPrices,List <String> productSold,List<Float> soldPrice){Map<String,Float> mp = new HashMap<String,Float>(); mp.clear();for(int i=0;i<products.size();i++){String tmp&#(i);Float q&#(i);mp.put(tmp,q);}int cnt=0;for(int i=0;i<productSold.size();i++){String tmp&#(i);Float p&#(tmp);Float q&#(i);if(Math.abs(p-q)>0.00000001) cnt++;}return cnt;}public static void main(String[] args){Map<String,Integer> mr = new HashMap<String,Integer>();}
}

END：我懂了，只要学好hash笔试题就能乱切了…每场笔试必有hash。各位快去学hash吧hhh（