23年阿里淘天笔试题 | 卡码网模拟

第一题

144. 字典序最小的 01 字符串

解题思路：

模拟，统计遇到的连续的1的个数记为num，直到遇到0，如果k>=num，直接将第一个1置为0，将遇到的0置为1，否则将第一个1偏置num-k个位置置为0，遇到的0置为1。

原理是遇到的1，基本都要往后移。有多少个k就可以往后移多少个1，而字典序最小又要求我们优先移动前面的

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int num = 0;
    int start = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') continue;
        num = 0;
        start = i;
        num++;
        while (i + 1 < n && s[i+1] != '0') {
            num++; i++;
        }
        if (i + 1 >= n) break;
        if (k >= num) {
            s[start] = '0'; s[start + num] = '1';
            k -= num;
            i = start;
        }
        else {
            s[start + num - k] = '0'; s[start + num] = '1';
            k = 0; break;
        }
    }
    cout << s << endl;
}

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        char[] ch = str.toCharArray();
        
        int num = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (ch[i] == '0') continue;
            num = 0;
            start = i;
            num++;
            while (i + 1 < n && ch[i+1] != '0') {
                num++; i++;
            }
            if (i + 1 >= n) break;
            if (k >= num) {
                ch[start] = '0'; ch[start + num] = '1';
                k -= num;
                i = start;
            }
            else {
                ch[start + num - k] = '0'; ch[start + num] = '1';
                k = 0; break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) 
            sb = sb.append(ch[i]);

        System.out.println(sb.toString());
    }
}

第二题

145. 数组子序列的排列

解题思路：

先统计从1开始连续的数的个数和每个数在数组中出现的个数，只统计100000以下的数出现的个数，最后计算规律为n1 + n1n2 + n1n2n3 + … + n1n2…*nm

#include<iostream>
#include <vector>
using namespace std;

const long long mod = 1000000000 + 7;

int main() {
    int n;
    cin >> n;
    vector<long long> nums(n, 0);
    vector<long long> num(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        if (nums[i] < 100000)
            num[nums[i]-1]++;
    }
    int b = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] == 0) {
            b = i; break;
        }
    }
    long long sum = 0;
    for (int i = 0; i < b; i++) {
        long long sum_in = 1;
        for (int j = 0; j <= i; j++) {
            sum_in *= num[j];
            sum_in %= mod;
        }
        sum += sum_in;
        sum %= mod;
    }
    sum %= mod;
    cout << sum << endl;
}

import java.util.*;

class Main {
    public static void main(String[] args) {
        long mod = 1000000007L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        long[] nums = new long[n];
        long[] num = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();
            if (nums[i] < 100000)
                num[(int)nums[i]-1]++;
        }
        int b = 0;
        for (int i = 0; i < n; i++) {
            if (num[i] == 0) {
                b = i; break;
            }
        }
        long sum = 0;
        for (int i = 0; i < b; i++) {
            long sum_in = 1;
            for (int j = 0; j <= i; j++) {
                sum_in *= num[j];
                sum_in %= mod;
            }
            sum += sum_in;
            sum %= mod;
        }
        sum %= mod;
        System.out.println(sum);
    }
}

第三题

146. 传送树

解题思路

用dfs扫描一遍邻接表即可

#include <iostream>
#include <list>
#include <vector>
#include <climits>
using namespace std;

int dfs(vector<int>& ans, vector<list<int>>& tree, int index) {
    if (tree[index].size() == 0) {
        ans[index] = 1;
        return index;
    }
    int ret = INT_MAX;
    for (int t : tree[index]) ret = min(dfs(ans, tree, t), ret);
    ans[index] = ans[ret] + 1;
    return min(index, ret);
}

int main() {
    int n; 
    cin >> n;
    vector<list<int>> tree(n, list<int>(0));
    vector<int> ans(n, 0);
    int u, v;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        tree[u-1].push_back(v-1);
    }
    dfs(ans, tree, 0);
    for (int index = 0; index < n; index++) {
        cout << ans[index] << ' ';
    }
    cout << endl;
}

import java.util.*;

class Main {
    public static int dfs(int[] ans, List<Integer>[] tree, int index) {
        if (tree[index].size() == 0) {
            ans[index] = 1;
            return index;
        }
        int ret = Integer.MAX_VALUE;
        for (int t : tree[index]) ret = Math.min(dfs(ans, tree, t), ret);
        ans[index] = ans[ret] + 1;
        return Math.min(index, ret);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer>[] tree = new List[n];
        for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
        int[] ans = new int[n];
        int u, v;
        for (int i = 0; i < n - 1; i++) {
            u = sc.nextInt();
            v = sc.nextInt();
            tree[u-1].add(v-1);
        }
        dfs(ans, tree, 0);
        for (int index = 0; index < n; index++) {
            System.out.print(ans[index] + " ");
        }
         System.out.println();
    }
}