Java工程师丨面试真题（7）

举报
陈橘又青 发表于 2022/08/29 22:16:02 2022/08/29
【摘要】 ​ 一、geohash编码描述geohash编码：geohash常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二步是base32转码。此题考察纬度的二进制编码：算法对纬度[-90, 90]通过二分法进行无限逼近（取决于所需精度，本题精度为6）。注意，本题进行二分法逼近过程中只保留整数部分而忽略掉小数部分（也即抹去小数部分）来进行二分，针对二分中间值属于右区间。算法...

​

 一、geohash编码

描述

geohash编码：geohash常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二步是base32转码。
此题考察纬度的二进制编码：算法对纬度[-90, 90]通过二分法进行无限逼近（取决于所需精度，本题精度为6）。注意，本题进行二分法逼近过程中只保留整数部分而忽略掉小数部分（也即抹去小数部分）来进行二分，针对二分中间值属于右区间。算法举例如下： 针对纬度为80进行二进制编码过程：
1) 区间[-90, 90]进行二分为[-90, 0),[0, 90]，成为左右区间，可以确定80为右区间，标记为1；
2) 针对上一步的右区间[0, 90]进行二分为[0, 45),[45, 90]，可以确定80是右区间，标记为1；
3) 针对[45, 90]进行二分为[45, 67),[67,90],可以确定80为右区间，标记为1；
4) 针对[67,90]进行二分为[67, 78),[78,90]，可以确定80为右区间，标记为1；
5) 针对[78, 90]进行二分为[78, 84),[84, 90]，可以确定80为左区间，标记为0；
6) 针对[78, 84)进行二分为[78, 81), [81, 84)，可以确定80为左区间，标记为0；

输入描述：

输入包括一个整数n,(-90 ≤ n ≤ 90)

输出描述：

输出二进制编码

示例1

输入：

80

输出：

111100

示例2

输入：

-66

输出：

001000

说明：

1) 区间[-90, 90]进行二分为[-90, 0),[0, 90]，成为左右区间，可以确定-66在左区间，标记为0；
2) 针对上一步的左区间[-90, 0)进行二分为[-90, -45),[-45, 0)，可以确定-66在左区间，标记为0；
3) 因(-90-45)/2=-135/2=-67.5，只取整数部分可得-67，所以针对[-90, -45)进行二分为[-90, -67),[-67,-45),可以确定-66在右区间，标记为1；
4) 针对[-67,-45)进行二分为[-67, -56),[-56,-45]，可以确定-66在左区间，标记为0；
5) 因(-67-56)/2=-123/2=-61.5，只取整数部分可得-61，所以针对[-67, -56)进行二分为[-67, -61),[-61, -56]，可以确定-66在左区间，标记为0；
6) 针对[-67, -61)进行二分为[-67, -64), [-64, -61)，可以确定-66在左区间，标记为0；

题解：

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while(input.hasNext()) {
			int n = input.nextInt();
			int low = -90;
			int high = 90;
			for(int i = 0; i < 6; i++) {
				if(n >= (low + high) / 2) {
					System.out.print("1");
					low = (low + high) / 2;
				}
				else {
					System.out.print("0");
					high = (low + high) / 2;
				}
			}
			System.out.println();
		}
		input.close();
	}
}

二、拼凑硬币

描述

小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^K的硬币，所以小Q拥有的硬币就是1,1,2,2,4,4,8,8,…。小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）。


输入描述：

输入包括一个整数n(1≤n≤10^18)，表示小Q需要支付多少钱。注意n的范围。

输出描述：

输出一个整数，表示小Q可以拼凑出n元钱放的方案数。

示例1

输入：

6

输出：

3

题解：

#include<iostream>
#include<map>
using namespace std;
map<long, long> m;

long solve(long n){  //记忆搜索法 
    if(m.count(n)) return m[n]; //如果已有直接返回
    long count = 0;
    if((n&1) != 1) count = solve(n>>1) + solve((n>>1)-1);  //n为偶数
    else count = solve(n>>1);  //n为奇数
    m[n] = count;
    return count;
}

int main(){
    m[0] = 1; m[1] = 1;  //初始值
    long n; cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

三、数字转换机

描述

小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：

当按下了红色按钮，两个数字同时加1。

当按下了蓝色按钮，两个数字同时乘2。

小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

输入描述：

输入包括一行，一行中有四个正整数a，b，A，B，（1≤a，b，A，B≤10^9）。

输出描述：

如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

示例1

输入：

100 1000 202 2002

输出：

2

题解：

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        int A = sc.nextInt(), B = sc.nextInt();
        StringBuilder button1 = new StringBuilder("");    //A变成a的按钮序列
        while(A > 0 && A != a){
            if(A%2 == 0){
                button1.append('B');
                A /= 2;
            }else{
                button1.append('R');
                A--;
            }
        }
        StringBuilder button2 = new StringBuilder("");    //B变成b的按钮序列
        while(B > 0 && B != b){
            if(B%2 == 0){
                button2.append('B');
                B /= 2;
            }else{
                button2.append('R');
                B--;
            }
        }
        if(button1.toString().equals(button2.toString())){
            System.out.println(button1.length());
        }else{
            int n = button1.length();
            int m = button2.length();
            if((a == 1 || b == 1)&&button1.toString().substring(0, n - 1).equals(button2.toString().substring(0, m - 1))){
                System.out.println(button1.length());
            }
            else System.out.println(-1);
        }
    }
}

四、魔法阵

描述

小Q搜寻了整个魔法世界找到了四块魔法石所在地，当4块魔法石正好能构成一个正方形的时候将启动魔法阵，小Q就可以借此实现一个愿望。

现在给出四块魔法石所在的坐标，小Q想知道他是否能启动魔法阵

输入描述：

输入的第一行包括一个整数（1≤T≤5）表示一共有T组数据

每组数据的第一行包括四个整数x[i](0≤x[i]≤10000)，即每块魔法石所在的横坐标

每组数据的第二行包括四个整数y[i](0≤y[i]≤10000),即每块魔法石所在的纵坐标

输出描述：

对于每组数据，如果能启动魔法阵输出“Yes”否则输出“No”。

示例1

输入：

3
0022
0202
0156
1605
0077
0303

输出：

Yes
Yes
No

题解：

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        for(int j = 0; j < T; ++j){
            String X = sc.nextLine(), Y = sc.nextLine();
            int[] x = new int[4], y = new int[4];
            for(int i = 0; i < 4; ++i){
                x[i] = X.charAt(i) - '0';
                y[i] = Y.charAt(i) - '0';
            }
            if(f(x, y)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
    static boolean f(int[] x, int[] y){
        for(int i = 0; i < 3; ++i){
            int a = (i + 1)%3, b = (i + 2)%3;    //除了3与i的另外两个下标
            if(x[3] + x[i] == x[a] + x[b] && y[3] + y[i] == y[a] + y[b]){    //对角线互相平分
                if((x[3] - x[i])*(x[a] - x[b]) + (y[3] - y[i])*(y[a] - y[b]) == 0){    //对角线互相垂直
                    int t1 = (x[3] - x[i])*(x[3] - x[i]) + (y[3] - y[i])*(y[3] - y[i]);
                    int t2 = (x[a] - x[b])*(x[a] - x[b]) + (y[a] - y[b])*(y[a] - y[b]);
                    if(t1 == t2){    //对角线长度相等
                        return true;
                    }
                }
            }
        }
        return  false;
    }
}

五、石子合并

描述

小Q和牛博士在玩一个石子合并的游戏，初始一共有n堆石子，每堆石子有w[i]个石子。小Q和牛博士他们需要对石子堆进行合并，每次他们可以任意选择两堆石子进行合并。一堆有x个石子的石子堆和一堆有y个石子的石子堆合并将得到一堆x+y个石子的石子堆，这次合并得分为x*y，当只剩下一堆石子的时候游戏结束。

、小Q和牛博士希望采取优秀的策略获得最大得分，希望你能来帮他们算算最大得分多少。

输入描述：

输入包括两行，第一行一个正整数n(2≤n≤100)。

第二行包括n个正整数w[i](1≤w[i]≤100)，即每堆石子的个数。

输出描述：

输出一个正整数，即小Q和牛博士最大得分是多少。

示例1

输入：

3
1 2 3

输出：

11

题解：

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n];
        for(int i = 0; i < n; ++i) v[i] = sc.nextInt();
        Arrays.sort(v);
        int pre = v[n - 1], sum = 0;
        for(int i = n - 2; i >= 0; --i){
            sum += pre*v[i];
            pre += v[i];
        }
        System.out.println(sum);
    }
}

六、小Q的排序

描述

小Q在学习许多排序算法之后灵机一动决定自己发明一种排序算法，小Q希望能将n个不同的数排序为升序。小Q发明的排序算法在每轮允许两种操作：

1、 将当前序列中前n-1个数排为升序

2、 将当前序列中后n-1个数排为升序

小Q可以任意次使用上述两种操作，小Q现在想考考你最少需要几次上述操作可以让序列变为升序。

输入描述：

输入包括两行，第一行包括一个正整数n(3≤n≤10^5)，表示数字的个数

第二行包括n个正整数a[i](1≤a[i]≤10^9)，即需要排序的数字，保证数字各不相同。

输出描述：

输出一个正整数，表示最少需要的操作次数

示例1

输入：

6
4 3 1 6 2 5

输出：

2

题解：

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> v = new ArrayList<>();
        int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
        for(int i = 0;  i < n; ++i){
            int a = sc.nextInt();
            if(mx < a) mx = a;
            if(mn > a) mn = a;
            v.add(a);
        }
        List<Integer> temp = new ArrayList<>(v);
        Collections.sort(temp);
        if(temp.equals(v)){      //本来就排好序的返回0
            System.out.println(0);
            return;
        }
        if(v.get(v.size() - 1) == mx || v.get(0) == mn){     //最大或最小归位的，1次
            System.out.println(1);
            return;
        }
        int r = 1;
        if(v.get(0) == mx) r++;      //最大值在首位，多挪动1次
        if(v.get(v.size() - 1) == mn) r++;      //最小值在末尾，多挪动1次
        if(v.get(0) != mn && v.get(v.size() - 1) != mx) r++;    //最大最小都在中间
        System.out.println(r);
    }
}

​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
Java
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入