富途09.09笔试算法题

T1：找出1~n之间丢失的某个正整数，已知条件是剩下的n-1个正整数异或和sum。

思路：根据异或运算的性质，假设1~n异或和为total，丢失的数 = total ^ sum。前n个正整数异或和是有规律的，可以在O(1)时间算出total

代码

public static void main(String[] args) {
//        int sum = 1;
//        int end = (int) Math.pow(2, 10);
//        for(int i=2; i<=end; i++) {
//            sum ^= i;
//            System.out.println("前"+i+"个数的异或和 = " + sum);
//        }
//        System.out.println(sum);
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int i=0; i<t; i++) {
            int n = in.nextInt();
            int sum = in.nextInt();
            int total;
            if(n % 4 == 0)
                total = n;
            else if(n % 4 == 1)
                total = 1;
            else if(n % 4 == 2)
                total = n+1;
            else
                total = 0;
            System.out.println(total ^ sum);
        }

T2：数轴上取糖果，坐标为i的位置上有|i|个糖果，到达位置会拿掉全部糖果。给一个只包含"L"和"R"字符串和一个整数K，初始位置在原点，"L"表示向左移动一个单位长度，"R"示向右移动一个单位长度，重复执行字符串中的操作k次，问拿到的糖果总数。

思路：计算出第一次执行字符串的移动范围以及结束时的位置cur，若结束时位置位于原点左边，那么剩下k-1次重复操作会将左边界拓展，每次拓展|cur|个单位长度；k次后从左边界到右边界遍历拿糖果即可

public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        String oprs = in.nextLine();
        long left_bound = 0;
        long right_bound = 0;
        long cur = 0;
        for(int i=0; i<n ;i++) {
            if(oprs.charAt(i) == 'L') {
                cur--;
                left_bound = Math.min(left_bound, cur);
            }
            else {
                cur++;
                right_bound = Math.max(right_bound, cur);
            }
        }
        if(cur < 0) {
            left_bound += (k - 1) * cur;
        } else {
            right_bound += (k-1) * cur;
        }
        long res = 0;
        for(int i = (int) left_bound; i<=right_bound; i++) {
            res += Math.abs(i);
        }

        System.out.println(res);
    }