[左神面试指南] 其他题目[中]篇

CD66 并查集的实现

public class CD66_1
{
    public static class Solution
    {
        int[] f;

        public Solution(int n)
        {
            f = new int[n];
            Arrays.fill(f, -1);
        }

        private int find(int a)
        {
            if (f[a] == -1)
                return a;
            else
                return f[a] = find(f[a]);
        }

        public void union(int a, int b)
        {
            int fa = find(a);
            int fb = find(b);
            if (fa != fb)
                f[fb] = fa;
        }

        public boolean isSame(int a, int b)
        {
            return find(a) == find(b);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n, m, op, num1, num2;
        n = in.nextInt();
        m = in.nextInt();
        Solution solution = new Solution(n);
        while (m-- > 0)
        {
            op = in.nextInt();
            num1 = in.nextInt();
            num2 = in.nextInt();
            switch (op)
            {
                case 1:
                    out.println(solution.isSame(num1, num2) ? "Yes" : "No");
                    break;
                case 2:
                    solution.union(num1, num2);
                    break;
            }
        }
        out.flush();
    }
}

CDxxx 调整[0,x)区间上的数出现的概率

public double randXPowerK(int k) 
{
    if (k < 1) return 0;
    double res = -1;
    for (int i = 0; i != k; i++) 
    	res = Math.max(res, Math.random());
    return res;
}

CD67 路径数组变为统计数组

public class CD67_1
{
    public static void solution(int[] arr)
    {
        pathsToDistans(arr);
        distansToNums(arr);
    }

    public static void distansToNums(int[] arr)
    {
        int curIdx, temp;
        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i] > 0) continue;
            curIdx = arr[i];
            arr[i] = 0;
            if (curIdx >= 0) arr[curIdx]++;
            else
            {
                while (curIdx < 0 && arr[-curIdx] < 0)
                {
                    temp = arr[-curIdx];
                    arr[-curIdx] = 1;
                    curIdx = temp;
                }
                arr[-curIdx]++;
            }
        }
    }

    public static void pathsToDistans(int[] arr)
    {
        int cap = -1, preIdx, curIdx, temp, cnt = 0;
        for (int i = 0; i < arr.length; i++)
        {
            if (arr[i] < 0) continue;
            if (arr[i] == i)
            {
                cap = i;
                continue;
            }
            preIdx = i;
            curIdx = arr[i];
            if (curIdx < 0 || curIdx == arr[curIdx]) arr[i] = arr[curIdx] == curIdx ? -1 : curIdx - 1;
            else
            {
                arr[i] = -1;
                while (arr[curIdx] >= 0 && arr[curIdx] != curIdx)
                {
                    temp = arr[curIdx];
                    arr[curIdx] = preIdx;
                    preIdx = curIdx;
                    curIdx = temp;
                }
                cnt = arr[curIdx] < 0 ? arr[curIdx] : 0;
                curIdx = preIdx;
                while (curIdx != -1)
                {
                    cnt--;
                    temp = arr[curIdx];
                    arr[curIdx] = cnt;
                    curIdx = temp;
                }
            }
        }
        arr[cap] = 0;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        solution(arr);
        System.out.println(Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CD68 正数数组的最小不可组成和⭐

/* 超时 */
public class CD68_1
{
    public static int solution(int[] arr)
    {
        int mmin = Integer.MAX_VALUE;
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr)
            mmin = Math.min(mmin, num);
        cal(arr, 0, 0, set);
        for (int ans = mmin + 1; ans <= Integer.MAX_VALUE; ans++)
            if (!set.contains(ans))
                return ans;
        return -1;
    }

    public static void cal(int[] arr, int idx, int sum, HashSet<Integer> set)
    {
        if (idx == arr.length)
        {
            set.add(sum);
            return;
        }
        cal(arr, idx + 1, sum + arr[idx], set);
        cal(arr, idx + 1, sum, set);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

/* ⭐DP背包⭐ */
public class CD68_2
{
    public static int solution(int[] arr)
    {
        if (arr == null || arr.length == 0) return 1;
        int sum = 0;
        int mmin = Integer.MAX_VALUE;
        for (int i = 0; i != arr.length; i++)
        {
            sum += arr[i];
            mmin = Math.min(mmin, arr[i]);
        }

        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i != arr.length; i++)
            for (int j = sum; j >= arr[i]; j--)
                dp[j] = dp[j - arr[i]] ? true : dp[j];

        for (int i = mmin; i != dp.length; i++)
            if (!dp[i])
                return i;
        return sum + 1;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD69 正数数组的最小不可组成和（进阶）

public class CD69_1
{
    public static long solution(int[] arr)
    {
        if (arr == null || arr.length == 0) return 0;
        Arrays.sort(arr);
        long range = 0;
        for (int i = 0; i != arr.length; i++)
        {
            if (arr[i] > range + 1)
                return range + 1;
            else
                range += arr[i];
        }
        return range + 1;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD70 累加出整个范围所有的数最少还需几个数⭐

/*⭐⭐*/
public class CD70_1
{
    public static int solution(int[] arr, int k)
    {
        Arrays.sort(arr);
        int ans = 0, can = 0;
        for (int i = 0; i < arr.length; i++)
        {
            while (can + 1 < arr[i])
            {
                ans++;
                can += can + 1;
                if (can >= k) return ans;
            }
            can += arr[i];
            if (can >= k) return ans;
        }
        while (k > can)
        {
            ans++;
            can += can + 1;
        }
        return ans;
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr, k));
    }
}

CD71 一种字符串和数字的对应关系

public class CD71_1
{
    private static String num2String(int num, String nSys)
    {
        HashMap<Integer, Character> map = new HashMap<>();
        for (int i = 0; i < nSys.length(); i++)
            map.put(i + 1, nSys.charAt(i));
        int len = nSys.length(), base = 1, cnt = 0;
        while (num >= base)
        {
            cnt++;
            num -= base;
            base *= len;
        }
        char[] ans = new char[cnt];
        for (int i = 0; i < ans.length; i++)
        {
            base /= len;
            ans[i] = map.get(num / base + 1);
            num %= base;
        }
        return String.valueOf(ans);
    }

    private static int String2num(String str, String nSys)
    {
        HashMap<Character, Integer> map = new HashMap<>();
        int ans = 0, base = 1, len = nSys.length();
        for (int i = 0; i < nSys.length(); i++)
            map.put(nSys.charAt(i), i + 1);
        for (int i = str.length() - 1; i >= 0; i--)
        {
            ans += map.get(str.charAt(i)) * base;
            base *= len;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int opt = in.nextInt(), base = in.nextInt();
        in.nextLine();
        String nSys;
        nSys = in.nextLine();
        if (opt == 1)
            System.out.println(num2String(in.nextInt(), nSys));
        else
            System.out.println(String2num(in.nextLine(), nSys));
    }
}

CD72 1 到 n 中 1 出现的次数⭐

public class CD72_1
{
    public static long solution(long num)
    {
        if (num < 1) return 0;
        long len = getLenOfNum(num);
        if (len == 1) return 1;
        long tmp1 = powerBaseOf10(len - 1);
        long first = num / tmp1;
        long firstOneNum = first == 1 ? num % tmp1 + 1 : tmp1;
        long otherOneNum = first * (len - 1) * (tmp1 / 10);
        return firstOneNum + otherOneNum + solution(num % tmp1);
    }

    public static long getLenOfNum(long num)
    {
        int len = 0;
        while (num != 0)
        {
            len++;
            num /= 10;
        }
        return len;
    }

    public static long powerBaseOf10(long base)
    {
        return (long) Math.pow(10, base);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        System.out.println(solution(n));
    }
}

CDxxx 从 N 个数中等概率打印 M 个数

public void printRandM(int[] arr, int m) 
{
	if (arr == null || arr.length == 0 || m < 0) return;
    m = Math.min(arr.length, m);
    int count = 0;
    int i = 0;
	while (count < m) 
    {
        i = (int) (Math.random() * (arr.length - count));
        System.out.println(arr[i]);
        swap(arr, arr.length - count++ - 1, i);
	}
}
public void swap(int[] arr, int index1, int index2) 
{
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
}

CD73 判断一个数是否是回文数

public class CD73_1
{
    public static boolean solution(int n)
    {
        n = n < 0 ? -n : n;
        int temp = 1;
        while (n >= temp * 10)
            temp *= 10;
        while (n != 0)
        {
            if (n / temp != n % 10) return false;
            n = (n % temp) / 10;
            temp /= 100;
        }
        return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solution(n) ? "Yes" : "No");
    }
}

CD74 在有序旋转数组中找到最小值❓

/*❓*/
public class CD74_1
{
    public static int solution(int[] arr)
    {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low < high)
        {
            if (low == high - 1) break;
            if (arr[low] < arr[high]) return arr[low];

            mid = (low + high) / 2;
            if (arr[low] > arr[mid])
            {
                high = mid;
                continue;
            }
            if (arr[mid] > arr[high])
            {
                low = mid;
                continue;
            }
            while (low < mid)
            {
                if (arr[low] == arr[mid])
                    low++;
                else if (arr[low] < arr[mid])
                    return arr[low];
                else
                {
                    high = mid;
                    break;
                }
            }
        }
        return Math.min(arr[low], arr[high]);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD75 在有序旋转数组中找到一个数❓

/*❓*/
public class CD75_1
{
    public static boolean solution(int[] arr, int num)
    {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (arr[mid] == num) return true;
            if (arr[low] == arr[mid] && arr[mid] == arr[high])
            {
                while (low != mid && arr[low] == arr[mid])
                    low++;
                if (low == mid)
                {
                    low = mid + 1;
                    continue;
                }
            }
            if (arr[low] != arr[mid])
            {
                if (arr[mid] > arr[low])
                {
                    if (num >= arr[low] && num < arr[mid])
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                else
                {
                    if (num > arr[mid] && num <= arr[high])
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
            }
            else
            {
                if (arr[mid] < arr[high])
                {
                    if (num > arr[mid] && num <= arr[high])
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
                else
                {
                    if (num >= arr[low] && num < arr[mid])
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
            }
        }
        return false;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr, k) ? "Yes" : "No");
    }
}

CD76 数字的英文表达和中文表达⭐

/*⭐*/
public class CD76_1
{
    public static void solution(int n)
    {
        System.out.println(getNumEngExp(n));
        System.out.println(getNumChiExp(n));
    }

    public static String chNum1To9(int num)
    {
        if (num < 1 || num > 9) return "";
        String[] names = {"一", "二", "三", "四", "五", "六", "七", "八", "九"};
        return names[num - 1];
    }

    public static String chNum1To99(int num, boolean hasBai)
    {
        if (num < 1 || num > 99) return "";
        if (num < 10) return chNum1To9(num);
        int shi = num / 10;
        if (shi == 1 && (!hasBai))
            return "十" + chNum1To9(num % 10);
        else
            return chNum1To9(shi) + "十" + chNum1To9(num % 10);
    }

    public static String chNum1To999(int num)
    {
        if (num < 1 || num > 999) return "";
        if (num < 100) return chNum1To99(num, false);
        String res = chNum1To9(num / 100) + "百";
        int rest = num % 100;
        if (rest == 0)
            return res;
        else if (rest >= 10)
            res += chNum1To99(rest, true);
        else
            res += "零" + chNum1To9(rest);
        return res;
    }

    public static String chNum1To9999(int num)
    {
        if (num < 1 || num > 9999) return "";
        if (num < 1000) return chNum1To999(num);
        String res = chNum1To9(num / 1000) + "千";
        int rest = num % 1000;
        if (rest == 0) return res;
        else if (rest >= 100)
            res += chNum1To999(rest);
        else
            res += "零" + chNum1To99(rest, false);
        return res;
    }

    public static String chNum1To99999999(int num)
    {
        if (num < 1 || num > 99999999) return "";
        int wan = num / 10000;
        int rest = num % 10000;
        if (wan == 0) return chNum1To9999(rest);
        String res = chNum1To9999(wan) + "万";
        if (rest == 0) return res;
        else
        {
            if (rest < 1000)
                return res + "零" + chNum1To999(rest);
            else
                return res + chNum1To9999(rest);
        }
    }

    public static String getNumChiExp(int num)
    {
        if (num == 0) return "零";
        String res = num < 0 ? "负" : "";
        int yi = Math.abs(num / 100000000);
        int rest = Math.abs((num % 100000000));
        if (yi == 0) return res + chNum1To99999999(rest);
        res += chNum1To9999(yi) + "亿";
        if (rest == 0) return res;
        else
        {
            if (rest < 10000000)
                return res + "零" + chNum1To99999999(rest);
            else
                return res + chNum1To99999999(rest);
        }
    }

    public static String enNum1To19(int num)
    {
        if (num < 1 || num > 19) return "";
        String[] names = {"One ", "Two ", "Three ", "Four ", "Five ", "Six ",
                "Seven ", "Eight ", "Nine ", "Ten ", "Eleven ", "Twelve ",
                "Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ",
                "Eighteen ", "Nineteen "};
        return names[num - 1];
    }

    public static String enNum1To99(int num)
    {
        if (num < 1 || num > 99) return "";
        if (num < 20) return enNum1To19(num);
        int high = num / 10;
        String[] tyNames = {"Twenty ", "Thirty ", "Forty ", "Fifty ",
                "Sixty ", "Seventy ", "Eighty ", "Ninety "};
        return tyNames[high - 2] + enNum1To19(num % 10);
    }

    public static String enNum1To999(int num)
    {
        if (num < 1 || num > 999) return "";
        if (num < 100) return enNum1To99(num);
        int high = num / 100;
        return enNum1To19(high) + "Hundred " + enNum1To99(num % 100);
    }

    public static String getNumEngExp(int num)
    {
        if (num == 0) return "Zero";
        String res = "";
        if (num < 0) res = "Negative, ";
        if (num == Integer.MIN_VALUE)
        {
            res += "Two Billion, ";
            num %= -2000000000;
        }
        num = Math.abs(num);
        int high = 1000000000;
        int highIndex = 0;
        String[] names = {"Billion", "Million", "Thousand", ""};
        while (num != 0)
        {
            int cur = num / high;
            num %= high;
            if (cur != 0)
            {
                res += enNum1To999(cur);
                res += names[highIndex] + (num == 0 ? " " : ", ");
            }
            high /= 1000;
            highIndex++;
        }
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        solution(n);
    }
}

CD77 分糖果问题

public class CD77_1
{
    public static int solution(int[] arr)
    {
        if (arr == null || arr.length == 0) return 0;
        int index = nextMinIndex1(arr, 0);
        int res = rightCands(arr, 0, index++);
        int lbase = 1;
        int next = 0;
        int rcands = 0;
        int rbase = 0;
        while (index != arr.length)
        {
            if (arr[index] > arr[index - 1])
            {
                res += ++lbase;
                index++;
            }
            else if (arr[index] < arr[index - 1])
            {
                next = nextMinIndex1(arr, index - 1);
                rcands = rightCands(arr, index - 1, next++);
                rbase = next - index + 1;
                res += rcands + (rbase > lbase ? -lbase : -rbase);
                lbase = 1;
                index = next;
            }
            else
            {
                res += 1;
                lbase = 1;
                index++;
            }
        }
        return res;
    }

    public static int nextMinIndex1(int[] arr, int start)
    {
        for (int i = start; i != arr.length - 1; i++)
            if (arr[i] <= arr[i + 1])
                return i;
        return arr.length - 1;
    }

    public static int rightCands(int[] arr, int left, int right)
    {
        int n = right - left + 1;
        return n * (n + 1) / 2;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

/* 贪心 */
public class CD77_2
{
    public static int solution(int[] arr)
    {
        int n = arr.length, ans = 0;
        int[] candy = new int[n];
        Arrays.fill(candy, 1);
        for (int i = 1; i < n; i++)
            if (arr[i] > arr[i - 1] && candy[i] <= candy[i - 1])
                candy[i] = candy[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--)
            if (arr[i] > arr[i + 1] && candy[i] <= candy[i + 1])
                candy[i] = candy[i + 1] + 1;
        for (int num : candy) ans += num;
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD78 分糖果问题（进阶）

public class CD78_1
{
    public static int solution(int[] arr)
    {
        if (arr == null || arr.length == 0) return 0;
        int index = nextMinIndex2(arr, 0);
        int[] data = rightCandsAndBase(arr, 0, index++);
        int res = data[0];
        int lbase = 1;
        int same = 1;
        int next = 0;
        while (index != arr.length)
        {
            if (arr[index] > arr[index - 1])
            {
                res += ++lbase;
                same = 1;
                index++;
            }
            else if (arr[index] < arr[index - 1])
            {
                next = nextMinIndex2(arr, index - 1);
                data = rightCandsAndBase(arr, index - 1, next++);
                if (data[1] <= lbase)
                    res += data[0] - data[1];
                else
                    res += -lbase * same + data[0] - data[1] + data[1] * same;
                index = next;
                lbase = 1;
                same = 1;
            }
            else
            {
                res += lbase;
                same++;
                index++;
            }
        }
        return res;
    }

    public static int nextMinIndex2(int[] arr, int start)
    {
        for (int i = start; i != arr.length - 1; i++)
            if (arr[i] < arr[i + 1])
                return i;
        return arr.length - 1;
    }

    public static int[] rightCandsAndBase(int[] arr, int left, int right)
    {
        int base = 1;
        int cands = 1;
        for (int i = right - 1; i >= left; i--)
        {
            if (arr[i] == arr[i + 1])
                cands += base;
            else
                cands += ++base;
        }
        return new int[]{cands, base};
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

/* 贪心 */
public class CD78_2
{
    public static int solution(int[] arr)
    {
        int n = arr.length, ans = 0;
        int[] candy = new int[n];
        Arrays.fill(candy, 1);
        for (int i = 1; i < n; i++)
            if (arr[i] > arr[i - 1] && candy[i] <= candy[i - 1])
                candy[i] = candy[i - 1] + 1;
            else if (arr[i] == arr[i - 1])
                candy[i] = candy[i - 1];

        for (int i = n - 2; i >= 0; i--)
            if (arr[i] > arr[i + 1] && candy[i] <= candy[i + 1])
                candy[i] = candy[i + 1] + 1;
            else if (arr[i] == arr[i + 1])
                candy[i] = candy[i + 1];

        for (int num : candy) ans += num;
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}