8.20网易开发笔试题目，算是做过的里面最难的几个了
第一题：给定两个数字a,b，每一次可以删除任意一位，求能使取余为0的最少删除次数？100%
典型的dfs剪枝或者状压dp，状压求稳dp[i][j]其中i是a删除的状态，j是b删除的状态
static int maxa,maxb;
static int[][] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
long l = System.currentTimeMillis();
maxa = (1<<s[0].length())-1;
maxb = (1<<s[1].length())-1;
dp = new int[maxa+1][maxb+1];
int dfs = dfs(0, 0, s[0], s[1]);
if(dfs>=Integer.MAX_VALUE>>1)
System.out.println(-1);
else
System.out.println(dfs);
System.out.println(System.currentTimeMillis()-l);
}
private static int dfs(int astatu, int bstatu, String s, String s1) {
if(astatu==maxa||bstatu==maxb)
return Integer.MAX_VALUE>>1;
if(dp[astatu][bstatu]!=0)
return dp[astatu][bstatu];
String a = "",b = "";
int sn = s.length(),s1n = s1.length();
for (int i = 0; i < sn; i++) {
if(((astatu>>i)&1)==0)
a+=s.charAt(i);
}
for (int i = 0; i < s1n; i++) {
if(((bstatu>>i)&1)==0)
b+=s1.charAt(i);
}
int a1 = Integer.parseInt(a),b1 = Integer.parseInt(b);
if(a1==0||b1==0)
return Integer.MAX_VALUE>>1;
if(a1%b1==0||b1%a1==0) {
dp[astatu][bstatu] = 0;
return 0;
}
int max = Integer.MAX_VALUE>>1;
for (int i = 0; i < sn; i++) {
if(((astatu>>i)&1)==1)continue;
max = Math.min(dfs(astatu|(1<<i),bstatu,s,s1)+1,max);
}
for (int i = 0; i < s1n; i++) {
if(((bstatu>>i)&1)==1)continue;
max = Math.min(dfs(astatu,bstatu|(1<<i),s,s1)+1,max);
}
dp[astatu][bstatu] = max;
return max;
} 第二题长城数组，两次遍历，分奇偶判断即可100%public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int oddMax = 0,newMax = 0;
long res = 0;
for (int i = 0; i < n; i++) {
if ((i & 1) == 0) {
oddMax = Math.max(oddMax, Integer.parseInt(s[i]));
} else {
newMax = Math.max(newMax, Integer.parseInt(s[i]));
}
}
for (int i = 0; i < n; i++) {
if ((i & 1) == 0) {
res += oddMax - Integer.parseInt(s[i]);
} else {
res += newMax - Integer.parseInt(s[i]);
}
}
if (oddMax == newMax) {
res += n>>1;
}
System.out.println(res);
} 第三题red得题，扫了一眼应该是贪心没时间看，没来及写时间都花在第四题上了，骗了30%的分
第四题，一开始一直基于map优化，发现怎么都降不下去，后续想了一下排序后用下标开线段树计算区间大小 100%
static segment[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
long res = 0;
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
arr[i][0] = Integer.parseInt(s[i]);
arr[i][1] = i;
}
dist = new segment[(n+1)*4];
Arrays.sort(arr,(o1, o2) -> {
if(o1[0]==o2[0])
return o1[1]-o2[1];
return o1[0]-o2[0];
});
update(0,n-1,arr[0][1],arr[0][1],0);
for (int i = 1; i < n; i++) {
if(arr[i][0]==arr[i-1][0]){
for (int j = i-1; j > -1&&arr[j][0]==arr[i][0]; j--) {
res+=query(0,n-1,arr[j][1]+1,arr[i][1]-1,0)-(i-j-1);//这里应该可以优化到o1的但是过了就没管
}
}
update(0,n-1,arr[i][1],arr[i][1],0);
}
System.out.println(res);
}
private static int query(int s, int e, int l, int r, int p) {
if(s>=l&&e<=r){
if(dist[p]==null)return 0;
return dist[p].sum;
}
int mid = (s+e)>>1;
int sum = 0;
if(l<=mid)
sum+=query(s,mid,l,r,(p<<1)+1);
if(r>mid)
sum+=query(mid+1,e,l,r,(p+1)<<1);
return sum;
}
private static void update(int s, int e, int l, int r, int p) {
if(dist[p]==null)
dist[p] = new segment();
if(s>=l&&e<=r){
dist[p].sum = 1;
return;
}
int mid = (s+e)>>1;
if(l<=mid)update(s,mid,l,r,(p<<1)+1);
if(r>mid)update(mid+1,e,l,r,(p+1)<<1);
if(dist[(p<<1)+1]==null)
dist[(p<<1)+1] = new segment();
if(dist[(p+1)<<1]==null)
dist[(p+1)<<1] = new segment();
dist[p].sum = dist[(p<<1)+1].sum+dist[(p+1)<<1].sum;
}
static class segment{
int sum;
}
类似资料：