拼多多笔试 8.31 A3.7题代码

第一题

大意：给你两个数组，两个数组中的两个数差值不大于k的可以匹配上，匹配上后要删除这两个数，问最多有多少匹配上的，1<=数组的值<=100
排序加两个指针
ac

package nowcoder;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main50 {
    public static void main(String[] args) {
        new Solve50().solve();
    }
}
class Solve50{
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int t=s.nextInt();
        for (int i = 0; i < t; i++) {
            int n=s.nextInt();
            int m=s.nextInt();
            int k=s.nextInt();
            int[] r=new int[n];
            int[] b=new int[m];
            for (int j = 0; j < n; j++) {
                r[j]=s.nextInt();
            }
            for (int j = 0; j < m; j++) {
                b[j]=s.nextInt();
            }
            System.out.println(getAns(r,b,k));
        }
    }
    private int getAns(int[] r,int[] b,int k){
        int[] rCount=new int[101];
        int[] bCount=new int[101];
        for(int i:r)rCount[i]++;
        for(int i:b)bCount[i]++;
        int p1=1,p2=1;
        int ans=0;
        while (p1<=100&&p2<=100){
            if (p2-p1>k){
                p1++;
                continue;
            }
            if (p1-p2>k){
                p2++;
                continue;
            }

            if (rCount[p1]>bCount[p2]){
                rCount[p1]-=bCount[p2];
                ans+=bCount[p2];
                p2++;
            }else{
                bCount[p2]-=rCount[p1];
                ans+=rCount[p1];
                p1++;
            }
        }
        return ans;
    }
}

第二题

大意：有一个特殊的字符串，对称位置可以互相交换，定义字符串A<字符串B：当A的一种形式的字典序小于B的所有形式的字典序
给你一堆字符串，让你按从小到大输出，相等的字符串按出现顺序排序。
思路：找出A B的最小字符串，然后比较最后排序
ac

package nowcoder;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main51 {
    public static void main(String[] args) {
        new Solve51().solve();
    }
}

class Solve51{
    private class Node{
        String str;
        int pos;

        public Node(String str, int pos) {
            this.str = str;
            this.pos = pos;
        }
    }
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int n=s.nextInt();
        s.nextLine();
        Node[] nodes=new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i]=new Node(s.nextLine(),i);
        }
        Arrays.sort(nodes,(x,y)->{
            String s1=getMin(x.str);
            String s2=getMin(y.str);
            int diff=s1.compareTo(s2);
            if (diff!=0)return diff;
            return x.pos-y.pos;
        });
        PrintWriter out=new PrintWriter(new BufferedOutputStream(System.out));
        for(Node node:nodes)out.println(node.str);
        out.flush();
    }

    private String getMin(String str){
        int len=str.length();
        char[] chars=str.toCharArray();
        for (int i = 0; i <len/2 ; i++) {
            if (chars[len-i-1]<chars[i]){
                char c=chars[i];
                chars[i]=chars[len-i-1];
                chars[len-i-1]=c;
            }
        }
        return new String(chars);
    }
}

第三题

大意：给你一个数n，代表n根火柴棍，问最多能拼多少个正方形
这题吧，首先是个贪心，你得先找出怎么拼正方形用的棍子最少，我的思路是先拼成一个平方的(即floor(sqrt(n))) n代表正方形个数，然后在拼下一行，下一行铺满了，在去竖着铺一列
对能拼多少个正方形进行二分
ac

package nowcoder;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main52 {
    public static void main(String[] args) {
        Solve s=new Solve();
        s.solve();
    }
}
class Solve{
//    final long MAX=(long)1e16;
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        int t=s.nextInt();
        for (int i = 0; i < t; i++) {
            long n=s.nextLong();
            long left=0,right=(long)1e16/2;
            long ans=0;
            while (left<=right){
                long mid=(left+right)/2;
                if (get(mid)<=n){
                    ans=mid;
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            System.out.println(ans);
        }
    }
    //建造n个需要多少木棍
    public long get(long n){
        long ans=0;
        long len= (long) Math.sqrt(n);
        long need=len*(4+(len-1)*2);
        ans=need;
        //还有多少个需要建造
        long left=n-len*len;
        if (left==0)return ans;
        if (left<=len){
            ans+=3+(left-1)*2;
        }else{
            ans+=3+(len-1)*2;
            left-=len;
            ans+=3+(left-1)*2;
        }
        return ans;
    }

}

第四题

不会，输出n过了70%，美滋滋，求大神给个解答。