首页 / 更多教程 / 笔试编程题总结

笔试编程题总结

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了笔试编程题总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11258字，纯文字阅读大概需要17分钟。

内容图文

滴滴

1、给定两个数R和n，输出R的n次方，其中0.0<R<99.999, 0<n<=25

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String r;
        int n;
        String s;
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            r = sc.next(); //用string来存储，因为double和float都是不能准确的表示小数的，只是以概数来表示
            n = sc.nextInt();
            BigDecimal d = new BigDecimal(r);
            BigDecimal ans = new BigDecimal(r);
            for(int i=1;i<n;i++){
                ans = ans.multiply(d);
            }
            s= ans.stripTrailingZeros().toPlainString(); // 去除不必要的零，转换为字符串，防止科学记数法
            System.out.println(s);
        }
    }
}

2、给定一个m行n列的二维地图, 初始化每个单元都是水.操作addLand 把单元格(row,col)变成陆地.岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.
二维地图的每条边界外侧假定都是水.

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            int k = sc.nextInt();
            int count = 0;
            int[][] island = new int[m][n];
            int[][] num = new int[k][2];
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < k; i++){
                num[i][0] = sc.nextInt();
                num[i][1] = sc.nextInt();
            }
            for(int i = 0; i < k; i++){
                int a = num[i][0];
                int b = num[i][1];
                if(a < 0 || b < 0 || a >= m || b >= n){
                    list.add(count);
                    continue;
                }
                if(island[a][b] == 1){
                    list.add(count);
                    continue;
                }
                island[a][b] = 1;
                if(a - 1 >= 0 && island[a - 1][b] == 1){
                    if(count != 0) count--;
                }
                if(a + 1 < m && island[a + 1][b] == 1){
                    if(count != 0) count--;
                }
                if(b - 1 >= 0 && island[a][b - 1] == 1){
                    if(count != 0) count--;
                }
                if(b + 1 > n && island[a][b + 1] == 1){
                    if(count != 0) count--;
                }
                count++;
                list.add(count);
            }
            for(int i = 0; i < list.size() - 1; i ++){
                System.out.print(list.get(i) + " ");
            }
            System.out.print(list.get(list.size() - 1));
            System.out.println();
        }
    }
}

3、给定一个非空字符串, 按照如下方式编码, 使得编码后长度最小, 返回编码后的长度:
编码规则为: k[encoding_string], 表示重复k次encoding_strng,
例如’abcdefabcdefabc’可表示为’2[abcdef]abc’, 但是’aaa’仅能编码成’aaa’,
因为len(‘3[a]’)>len(‘aaa’).
补充:

  1. k为正整数, []内的encoding_string不得含有空格不得为空;
  2. []内的encoding_string 本身可以为编码过的字符串, 例如’abcdabcdeabcdabcde’ 可以编码为 ‘2[abcdabcde]’(编码后长度从18减少到12), []内的’abcdabcde’又可以编码为 ‘2[abcd]e’, 最终编码为 ‘2[2[abcd]e]’, 编码后长度为11, 应返回11; 这个编码路径也能是: ‘abcdabcdeabcdabcde’ -> ‘2[abcd]e2[abcd]e’ -> ‘2[2[abcd]e]’;
  3. 输入字符串为全小写英文字母, 长度<=160;
  4. 如果编码后长度没有更小, 则保留原有字符串;
  #include <bits/stdc++.h>
    using namespace std;
        string encoding_string(string s)
        {
            if (s == "")return "";
            if (s.size() <= 4)return s;
            int len = s.size();
            int len2 = len / 2;    //重复子串的最大长度 可以分成的份数至少要2份
            int best_count = 0;//一次遍历得到的最优重复数
            int best_len = INT_MAX;//一次遍历得到的最优压缩到的长度
            string pre, cur, lat;//一次遍历得到的最优子串
           while (len2 >= 1)//重复子串长度最小为1
            {
                for (int k = 0; k <= len - len2; k++)//从第k个下标开始找重复子串
                {
                    int count = 1;
                    string s2 = s.substr(k, len2);
                    string s3, s4;
                    for (int j = 1; len2 * j + len2 <= len; j++)
                    {
                        s3 = s.substr(k + len2 * j, len2);
                        if (s2.compare(s3) == 0 && s2.size() == s3.size())
                            count++;
                        else
                            break;
                    }
                int newlen = (len - count * len2) + 3 + len2;//压缩后的字符串长度
                if (newlen < len && newlen < best_len && count > 1)//如果压缩有效
                {
                    best_len = newlen;
                    best_count = count;
                    pre = s.substr(0, k);
                    cur = s.substr(k, len2);
                    lat = s.substr(k + count * len2);
                }
            }
            len2--;//重复字符串长度缩短1
        }
        if (best_count == 0)
            return s;
        return encoding_string(pre) + to_string(best_count) + "[" + encoding_string(cur) + "]" + encoding_string(lat);
        }
        int main()
        {
        string s;
        cin >> s；
            string result = "";
            result = encoding_string(s)；
            cout << result.size() << endl;
            return 0;
        }

4、无类别域间路由（CIDR）是一个用于对IPV4地址进行分类表述的方法。CIDR 路由描述的IP地址组的子网mask长度是可变长度, 例如10.0.0.0/22 表示前22位和10.0.0.0相同的网络地址都被覆盖, 22包含了10.0这前两个字段(0-7位,8-15位)和第三个字段的前6位(16-21,即0b000000**), 涵盖了 10.0.0., 10.0.1., 10.0.2., 10.0.3. 四组ip地址. 在此前提下请实现IP网络中的一个常用的去重操作: 给定一系列 CIDR 路由地址, 其中没有完全等价的路由, 去掉被重复表示的 CIDR 路由, 即去掉已经被其他CIDR路由表示覆盖的路由地址. 例如 10.0.1.1/32 已经被 10.0.0.0/22覆盖了, 如果路由列表中已经有了后者, 就可以去掉前者.

   import java.io.*;
    import java.util.*;
    public class Main{
        static class Addr{
            String addrStr;
            int mask;
            int addr;
            public Addr(String addrStr, int mask, int addr){this.addrStr = addrStr; this.mask = mask; this.addr = addr;}
        }
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            LinkedList<Addr> list = new LinkedList<>();
            while(n-->0){
                String addrStr = br.readLine();
                String[] strs = addrStr.split("/");
                int mask = Integer.parseInt(strs[1]);
                strs = strs[0].split("\\.");
                int addr = (Integer.parseInt(strs[0])<<24) | (Integer.parseInt(strs[1])<<16) | (Integer.parseInt(strs[2])<<8) | Integer.parseInt(strs[3]);
                boolean flag = true;
                for(Iterator<Addr> it = list.iterator(); it.hasNext(); ){
                    Addr tmp = it.next();
                    if(mask < tmp.mask && ( (addr ^ tmp.addr) >>> (32-mask) == 0) ) it.remove();
                    if(mask >= tmp.mask && ( (addr ^ tmp.addr) >>> (32-tmp.mask) == 0) ){flag = false; break;}
                }
                if(flag) list.add(new Addr(addrStr,mask,addr));
            }
            System.out.println(list.size());
            for(Iterator<Addr> it = list.iterator(); it.hasNext(); ){
                    Addr tmp = it.next();
                    System.out.println(tmp.addrStr);
            }
        }
    }

5、把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            System.out.println(getTarget(n));
        }
    }
        public static int getTarget(int n){
        int[] arr = new int[n];
        arr[0] = 1;
        int t1 = 0;
        int t2 = 0;
        int t3 = 0;
       int nextNum = 1;
        while (nextNum < n){
            arr[nextNum] = Math.min((Math.min(arr[t1]*2,arr[t2]*3)),arr[t3]*5);
            if(arr[t1]*2 <= arr[nextNum])
                t1++;
            if(arr[t2]*3 <= arr[nextNum])
                t2++;
            if(arr[t3]*5 <= arr[nextNum])
                t3++;
            nextNum++;
        }
        return arr[n - 1];
    }
}

6、给出n个数字 a_1,…,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0。

/// @brief 给出n个数字 a_1,...,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0
/// https://www.nowcoder.com/questionTerminal/7cffea0c097c4337821ab3ba25447c1c
///
/// @file maxNonOverlapSeg.cpp
/// @author cuichao
/// @date 2018-09-08
 
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
/// @brief find max num of non-overlap segments in array
///
/// find max segment num in array, such that xor of numbers in each segment
/// is zero
///
/// @param a Input array
/// @param maxSeg Recorded intermedia results, maxSeg[i] is max non-onverlap
/// segment num for array[i:end]
/// @param be Begin idx of subarray to search
/// @param n Lenght of input array
/// @return int Max num of non-overlap segments
int findMaxNonOverlapSeg(const int a[], int maxSeg[], int be, int n){
    if(be >= n) return 0;
    if(maxSeg[be] > 0) return maxSeg[be];
    int maxSegNum = 0, segNum = 0;
int j, re_xor;
for(int i=be; i<n; i++){
    j = i;
    re_xor = a[j++];
    while(j<n && re_xor!=0) re_xor ^= a[j++];

    if(re_xor == 0){
        segNum = 1 + findMaxNonOverlapSeg(a, maxSeg, j, n);
        maxSegNum = max(maxSegNum, segNum);
    }
}
maxSeg[be] = maxSegNum;
return maxSeg[be];
} 
int main(){
int N;
cin >> N;

int a[N];
int maxSeg[N];
for(int i=0; i<N; i++){
    cin >> a[i];
    maxSeg[i] = 0;
}

int maxSegNum = findMaxNonOverlapSeg(a, maxSeg, 0, N);
printf("%d\n", maxSegNum);
return 0;
}

携程

1、 有一批订单记录，数据有订单号，入店时间，离店时间；
输入一个时间值A，需要在这批记录中找到符合入离店时间范围（A大于等于入店时间，并且A小于等于离店时间）内的所有记录。 单次查询时间复杂度控制在O(logN)
※注意：订单号升序输出

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
           int x = in.nextInt();//记录数；
          int A = in.nextInt();//时间值；
          int[][] a = new int [x][3];//记录信息；
        for (int i = 0; i <x ; i++) {
            for (int j = 0; j <3 ; j++) {
                a[i][j] = in.nextInt();
            }
        }
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i <x ; i++) {
            for (int j = 0; j <3 ; j++) {
                if(a[i][1]<=A&&A<=a[i][2]){
                    set.add(a[i][0]);
                }
            }
        }
        if(set.size()==0)
            System.out.println("null");
        Iterator it = set.iterator();
        int k = 0;
        while(it.hasNext())//判断是否有下一个
        {
           k = (int) it.next();
            System.out.println(k);
        }
    }
}

2、设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。

限制：请在O(1)的时间复杂度内完成上述2个操作。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public clas***ain{
    private class Node {
        Node next, prev;
        int key, value;
        Node (){}
        Node(int key, int value) {
            this.value = value;
            this.key = key;
        }
    }
    private Node head, tail;
    private Map<Integer, Node> map;
    private int count, capacity;
    private void addNode(Node node) {
        Node old = head.next;
        head.next = node;
        node.prev = head;
        node.next = old;
        old.prev = node;
    }
    private void removeNode(Node node) {
        Node previous = node.prev;
        previous.next = node.next;
        node.next.prev = previous;
    }
    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }
    private Node popTail() {
        Node pre = tail.prev;
        removeNode(pre);
        return pre;
    }
    public Main(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            if (count == capacity) {
                map.remove(popTail().key);
                --count;
            }
            Node fresh = new Node(key, value);
            map.put(key, fresh);
            addNode(fresh);
            count++;
        } else {
            node.value = value;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int capacity = Integer.valueOf(scanner.nextLine().trim());
        Main instance = new Main(capacity);
        while (scanner.hasNextLine()) {
            String command = scanner.nextLine().trim();
            if (capacity >0 && command.charAt(0) == 'p') {
                int key = Integer.valueOf(command.substring(2, command.lastIndexOf(" ")));
                int value = Integer.valueOf(command.substring(command.lastIndexOf(" ")+1));
                instance.put(key, value);
            }else if(command.charAt(0) == 'g') {
                if (capacity <= 0) {
                    System.out.println(-1);
                }else {
                    int key = Integer.valueOf(command.substring(2));
                    System.out.println(instance.get(key));
                }
            }
        }
    }
}

3、输入一个long类型的数值, 求该数值的二进制表示中的1的个数 .

import java.util.Scanner;
public class Main1 {
    static int NumOf1(long l){
        int sum =0;
       String s =Long.toBinaryString(l);
        for (int i = 0; i <s.length() ; i++) {
            if(s.charAt(i)=='1'){
               sum=sum+1;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long x = in.nextLong();
        int res = NumOf1(x);
        System.out.println(res);
    }
}

内容总结

以上是互联网集市为您收集整理的笔试编程题总结全部内容，希望文章能够帮你解决笔试编程题总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/718376.html

来源：【匿名】