网易笔试网易笔试题 0928

笔试时间：2024年09月28日秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

给一堆以空格分割的字符串，将这些字符串重新排列，在保证出现顺序的前提下字典序要尽可能的小。

输入描述

第一行输入一行以空格分割的字符串。

输出描述

输出去重后的字符串列表，在保证出现顺序的前提下字典序要尽可能的小。

样例输入

seo optimization seo tutorial seo tutorial

样例输出

optimization seo tutorial

解释：optimization出现在在seo的前面和后面，所以optimization在最终的答案中既可以出现在seo的前面，也可以在后面，而optimization的字典序要比seo小，所以optimization在前面是最优的方案。

参考题解

记录每个字符串出现的起始位置和结束位置，如果a没有出现在b之前，那么a在最终答案里一定不能出现在b的前面，如果a没有出现在b之后，那么a在最终答案里一定不能出现在b的后面。因此我们对字符串自定义排序，先根据位置进行排序，再根据字典序进行排序即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<string> arr;
    unordered_map<string, int> first, last;
    string str;
    int index = 0;

    while (ss >> str) {
        arr.push_back(str);
        if (first.find(str) == first.end()) {
            first[str] = index;
        }
        last[str] = index;
        index++;
    }

    sort(arr.begin(), arr.end(), [&](const string& s1, const string& s2) {
        int compare = s1.compare(s2);
        if (compare < 0) {
            return first[s1] < last[s2];
        } else if (compare == 0) {
            return false;
        } else {
            return last[s1] > last[s2];
        }
    });

    unordered_set<string> set;
    for (const string& str : arr) {
        if (set.find(str) == set.end()) {
            cout << str << " ";
            set.insert(str);
        }
    }
    cout << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] arr = line.split(" ");
        Map<String, Integer> first = new HashMap<>();
        Map<String, Integer> last = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            String str = arr[i];
            if (!first.containsKey(str)) {
                first.put(str, i);
            }
            last.put(str, i);
        }

        Arrays.sort(arr, (s1, s2) -> {
            Integer compare = s1.compareTo(s2);
            if (compare == -1) {
                if (first.get(s1) < last.get(s2)) {
                    return -1;
                }else {
                    return 1;
                }
            }else if (compare == 0) {
                return 0;
            }else {
                if (last.get(s1) > last.get(s2)) {
                    return 1;
                }else {
                    return -1;
                }
            }
        });

        Set<String> set = new HashSet<>();
        for (String str : arr) {
            if (!set.contains(str)) {
                System.out.print(str + " ");
                set.add(str);
            }
        }
        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

# Python 3 code equivalent

def main():
    line = input().strip()
    arr = line.split()
    first = {}
    last = {}

    for i, str_ in enumerate(arr):
        if str_ not in first:
            first[str_] = i
        last[str_] = i

    arr.sort(key=lambda s1: (s1, first[s1] < last[s1]))

    seen = set()
    for str_ in arr:
        if str_ not in seen:
            print(str_, end=" ")
            seen.add(str_)
    print()

if __name__ == "__main__":
    main()

第二题

题目

给一个字符串x代表一个数字，x的长度小于等于一百万。求一个最小的y（可能超过long的表示范围且y必须大于等于0），使得x加上y是回文串。

输入描述

第一行输入x。

输出描述

输出最小的y，使得x+y是回文串。

样例输入一

96

样例输出一

3

样例输入二

3

样例输出二

0

参考题解

将字符串分为左半部和右半部，然后将left反转。如果这个时候left等于right，那么代表不需要加。直接输出0.如果left > right，那么左边不需要进位，直接取left-right即可。否则左边需要进位，然后再减。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    auto sub = [&](string a, string b) -> string {
        int m = a.size();
        string ans;
        for (int i = m - 1; i >= 0; i--) {
            int d1 = a[i] - '0';
            int d2 = b[i] - '0';
            if (d1 < d2) {
                d1 = d1 + 10;
                a[i - 1]--;
            }
            ans += (char)(d1 - d2 + '0');
        }
        reverse(ans.begin(), ans.end());
        return ans;
    };

    auto add = [&](string a) -> string {
        int progress = 1;
        int m = a.size();
        for (int i = m - 1; i >= 0; i--) {
            int digit = a[i] - '0';
            digit += progress;
            progress = digit / 10;
            digit %= 10;
            a[i] = (char)(digit + '0');
        }
        if (progress == 1) {
            a = "1" + a;
        }
        return a;
    };

    string left = s.substr(0, n / 2);
    string right = s.substr(n - n / 2);
    reverse(left.begin(), left.end());
    if (left == right) {
        cout << 0 << "\n";
        return 0;
    }

    if (left < right) {
        left = s.substr(0, (n + 1) / 2);
        left = add(left);
        string right = left.substr(0, n / 2);
        reverse(right.begin(), right.end());
        string after = left + right;
        string ans = sub(after, s);
        int idx = 0;
        while (idx < ans.size() && ans[idx] == '0') {
            idx++;
        }
        cout << ans.substr(idx) << "\n";
    }else {
        string ans = sub(left, right);
        int idx = 0;
        while (idx < ans.size() && ans[idx] == '0') {
            idx++;
        }
        cout << ans.substr(idx) << "\n";
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        // 减法函数
        String sub(String a, String b) {
            int m = a.length();
            StringBuilder ans = new StringBuilder();
            for (int i = m - 1; i >= 0; i--) {
                int d1 = a.charAt(i) - '0';
                int d2 = b.charAt(i) - '0';
                if (d1 < d2) {
                    d1 = d1 + 10;
                    a = a.substring(0, i - 1) + (char) (a.charAt(i - 1) - 1) + a.substring(i);
                }
                ans.append((char) (d1 - d2 + '0'));
            }
            return ans.reverse().toString();
        }

        // 加法函数
        String add(String a) {
            int progress = 1;
            int m = a.length();
            StringBuilder sb = new StringBuilder(a);
            for (int i = m - 1; i >= 0; i--) {
                int digit = sb.charAt(i) - '0';
                digit += progress;
                progress = digit / 10;
                digit %= 10;
                sb.setCharAt(i, (char) (digit + '0'));
            }
            if (progress == 1) {
                sb.insert(0, "1");
            }
            return sb.toString();
        }

        String left = s.substring(0, n / 2);
        String right = s.substring(n - n / 2);
        StringBuilder leftRev = new StringBuilder(left).reverse();
        if (leftRev.toString().equals(right)) {
            System.out.println(0);
            return;
        }

        if (leftRev.toString().compareTo(right) < 0) {
            left = s.substring(0, (n + 1) / 2);
            left = add(left);
            right = left.substring(0, n / 2);
            StringBuilder rightRev = new StringBuilder(right).reverse();
            String after = left + rightRev;
            String ans = sub(after, s);
            int idx = 0;
            while (idx < ans.length() && ans.charAt(idx) == '0') {
                idx++;
            }
            System.out.println(ans.substring(idx));
        } else {
            String ans = sub(left, right);
            int idx = 0;
            while (idx < ans.length() && ans.charAt(idx) == '0') {
                idx++;
            }
            System.out.println(ans.substring(idx));
        }
    }

    // 用于执行 sub 和 add 的 helper 方法
}

Python：[此代码未进行大量数据的测试，仅供参考]

def sub(a, b):
    m = len(a)
    ans = []
    for i in range(m - 1, -1, -1):
        d1 = ord(a[i]) - ord('0')
        d2 = ord(b[i]) - ord('0')
        if d1 < d2:
            d1 += 10
            a = a[:i - 1] + chr(ord(a[i - 1]) - 1) + a[i:]
        ans.append(chr(d1 - d2 + ord('0')))
    return ''.join(ans[::-1])

def add(a):
    progress = 1
    m = len(a)
    a = list(a)
    for i in range(m - 1, -1, -1):
        digit = ord(a[i]) - ord('0')
        digit += progress
        progress = digit // 10
        digit %= 10
        a[i] = chr(digit + ord('0'))
    if progress == 1:
        a.insert(0, '1')
    return ''.join(a)

if __name__ == "__main__":
    s = input().strip()
    n = len(s)

    left = s[:n // 2]
    right = s[n - n // 2:]
    if left[::-1] == right:
        print(0)
    elif left[::-1] < right:
        left = s[:(n + 1) // 2]
        left = add(left)
        right = left[:n // 2]
        after = left + right[::-1]
        ans = sub(after, s)
        idx = 0
        while idx < len(ans) and ans[idx] == '0':
            idx += 1
        print(ans[idx:])
    else:
        ans = sub(left, right)
        idx = 0
        while idx < len(ans) and ans[idx] == '0':
            idx += 1
        print(ans[idx:])