Java-拼多多 提前批 7月25日 四题AC答案及解题思路
第一题
给定若干条线段 {[a,b]} a、b表示端点，如果a1<=a2<=b2<=b1就说线段[a1,b1] 包含线段[a2, b2]。 判断线段集合中是否存在一条线段包含另一条线段。
解法：
-
将数组按照 线段左端点从小到大排序，如果左端点一样，按照右端点从小到大排序。
-
从左到右遍历，针对当前的线段，遍历后面的线段，判断有没有被当前线段包含的线段
-
如果有，则返回
-
否则外层循环遍历下一个元素
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] lines=new int[n][2];
for(int i = 0; i < n; i++){
lines[i][0]=sc.nextInt();
lines[i][1]=sc.nextInt();
}
Arrays.sort(lines, new Comparator() { @Override public int compare(int[] o1, int[] o2) {
int r1=o1[0]-o2[0];
int r2=o1[1]-o2[1];
if(r1==0) return r2;
else return r1;
}
});
for(int i=0;i<n-1;i++){
// int start=lines[i][0];
int end=lines[i][1];
for(int j=i+1;j<n;j++){
if(lines[j][1]<=end) {
System.out.println(true);
return;
}
}
}
System.out.println(false);
} 第二题
（模拟题）轮流放牌、收牌。需要注意的是，每次到一个人的回合，可能会有多个放牌、收牌的过程（即每次放牌，牌堆中都存在一张点数相同的牌）。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] chick=new int[n];
int[] duck=new int[n];
for(int i=0;i<n;i++) chick[i]=sc.nextInt();
for(int i=0;i<n;i++) duck[i]=sc.nextInt();
ArrayList buff=new ArrayList();
HashMap number2pos=new HashMap();
int chickNum=0,ci=0;
int duckNum=0, di=0;
while (ci!=n||di!=n){
if(ci<n){
while (buff.size()!=0&&ci<n){
int t = chick[ci];
if (number2pos.get(t) != null) {
int p = number2pos.get(t);
chickNum = chickNum + (buff.size() - p + 1);
ci++;
while (buff.size() != p) {
int rp = buff.get(p);
number2pos.remove(rp);
buff.remove(p);
}
}else break;
}
if(ci!=n) {
int t=chick[ci];
number2pos.put(t,buff.size());
buff.add(t);
ci++;
}
}
if(di<n){
while (buff.size()!=0&&di<n) {
int t = duck[di];
if (number2pos.get(t) != null) {
int p = number2pos.get(t);
duckNum = duckNum + (buff.size() - p + 1);
di++;
while (buff.size() != p) {
int rp = buff.get(p);
number2pos.remove(rp);
buff.remove(p);
}
}else break;
}
if(di!=n) {
int t=duck[di];
number2pos.put(t,buff.size());
buff.add(t);
di++;
}
}
}
for(int l=0;l<buff.size();l++){
if(buff.get(l)%2==0) duckNum++;
else chickNum++;
}
System.out.println(chickNum+" "+duckNum);
} 第三题
给定a,b,c 生成一个集合（范围是1-10^9），集合的生成规则为
-
初始集合为{a}
-
对于集合中的每个元素X，有X+B也属于该集合
-
对于集合中的每个元素，X*c也属于该集合
给定数字q，判定q是否在集合中。
解法：如果q在集合中，q=ac^k+mb k,m>=0且为整数. 只要找到符合条件的k、m，就表示q属于这个集合。 tips：计算过程中使用long，防止溢出
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int num=sc.nextInt();
for(int i=0;i<num;i++){
System.out.println(check(sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()));
}
}
public static int check(long a,long b,long c,long q){
long accu=1;
for(int k=0;k<32;k++){
long m=a*accu;
if(m>q) return 0;
long res=q-m;
if(res%b==0) return 1;
accu*=c;
}
return 0;
} 第四题
0-9 十个数字，每个数字给定若干个，要求把这些数字排列组成一个乘法算式；问如何排列，使得乘积最大。（贪心算法、大整数）
-
可以证明，组成a*b的形式得到的答案最大，而不是多个数相乘。针对两个数，将他们直接拼接到一块比相乘的结果要大，得证。
- 从最大的digit开始用，针对每个digit d, 判定是 concate(a,d)b大还是aconcate(b,d)大。选择较大的那种组合方式。
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
LinkedList<Integer> digit=new LinkedList<>();
for(int i=0;i<10;i++){
int num=sc.nextInt();
for(int j=0;j<num;j++){
digit.addFirst(i);
}
}
StringBuffer left=new StringBuffer(digit.peekFirst()+"");
BigInteger leftb=new BigInteger(left.toString());
digit.removeFirst();
StringBuffer right=new StringBuffer(digit.peekFirst()+"");
BigInteger rightb=new BigInteger(right.toString());
digit.removeFirst();
while (!digit.isEmpty()){
BigInteger tmpl=new BigInteger(left.toString()+digit.peekFirst());
BigInteger tmpr=new BigInteger(right.toString()+digit.peekFirst());
if(tmpl.multiply(rightb).compareTo(leftb.multiply(tmpr))==1){//left big
left.append(digit.peekFirst());
leftb=tmpl;
}else{
right.append(digit.peekFirst());
rightb=tmpr;
}
digit.removeFirst();
}
System.out.println(leftb.multiply(rightb));
} 
投递字节跳动等公司10个岗位 >
