第1题——找公共链表，AC

双指针，相等打印，谁大谁后移

import java.util.Scanner;
public class Code01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
//        System.out.println("n" + n);
        String[] line = scanner.nextLine().trim().split(" ");
//        System.out.println("line" + Arrays.toString(line));
        int[] arr1 = new int[n];
        for (int i = 0; i < line.length; i++) {
            arr1[i] = Integer.valueOf(line[i]);
        }
        int m = Integer.valueOf(scanner.nextLine());
        line = scanner.nextLine().trim().split(" ");
//        System.out.println("m" + m);
        int[] arr2 = new int[m];
//        System.out.println("line" + Arrays.toString(line));
        for (int i = 0; i < line.length; i++) {
            arr2[i] = Integer.valueOf(line[i]);
        }
        printCommon(arr1, arr2);
    }
    // 打印公共链表的值
    public static void printCommon(int[] arr1, int[] arr2) {
        int idx1 = 0;
        int idx2 = 0;
        while (idx1 < arr1.length && idx2 < arr2.length) {
            if (arr1[idx1] == arr2[idx2]) {
                System.out.print(arr1[idx1] + " ");
                idx1++;
                idx2++;
            } else if (arr1[idx1] > arr2[idx2]) {
                idx1++;
            } else {
                idx2++;
            }
        }
    }
}

应该用并查集，太久没写忘了，图结构也忘了

写了个从0开始暴力遍历的，AC了65%？

忽视了数组可能是无序，卡了好久

import java.util.Arrays;
import java.util.Scanner;
public class Code03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
//        System.out.println("n " + n);
        int[] arr = new int[n];
        int[] newArr = new int[n];
        String[] line = scanner.nextLine().trim().split(" ");
//        System.out.println(Arrays.toString(line));
        for (int i = 0; i < line.length; i++) {
            int val = Integer.valueOf(line[i]);
            arr[i] = val;
            newArr[i] = val;
        }
        Arrays.sort(newArr);
        printMeds(arr, newArr);
    }
    // 打印中位数数组
    public static void printMeds(int[] arr, int[] sortArr) {
        int n = arr.length;
        int left_val = sortArr[n / 2 - 1];
        int right_val = sortArr[n / 2];
        for (int i = 0; i < n; i++) {
            int idx = getIndex(sortArr, arr[i]);
            if (idx < n / 2) {
                System.out.println(right_val);
            } else {
                System.out.println(left_val);
            }
        }
    }
    public static int getIndex(int[] sortArr, int val) {
        int left = 0;
        int right = sortArr.length - 1;
        int mark = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (val == sortArr[mid]) {
                mark = mid;
                break;
            } else if (val < sortArr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return mark;
    }
}

当时看到输入很复杂了，先做后面的题目了，应该用大根堆求第K小，小根堆求第K大

第5题 红黑棋

这道题我想到解法了，Debug时间上差了一点，用了python两年，java算法三个月，还是没恢复熟练度。

贪心策略，从最终结果推过程
最终第一个位置肯定为红1或黑1，看红1和黑1的位置谁离位置0近，即进行领近交换；
假设交换后第一个位置为红1，那么第二个位置肯定为红2或黑1，看红1和黑1的位置谁离位置1近，即进行领近交换；
...
最终必定有效，且每次交换次数最少；
需要维护两个哈希表

• r_map:维护红棋编号及其数组中arr的索引；
• b_map:维护黑棋编号及其数组中arr的索引；

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Code05 {
    // id-index
    private static HashMap<Integer, Integer> r_map = new HashMap();
    private static HashMap<Integer, Integer> b_map = new HashMap();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        System.out.println("n" + n);
        char[] s = new char[2 * n];
        String line = scanner.nextLine().trim();
        System.out.println("line" + line);
        for (int i = 0; i < line.length(); i++) {
            s[i] = line.charAt(i);
        }
        int[] arr =new int[2 * n];
        String[] nums = scanner.nextLine().trim().split(" ");
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            arr[i] = Integer.valueOf(nums[i]);
            if (s[i] == 'R') {
                r_map.put(arr[i], i);
            } else {
                b_map.put(arr[i], i);
            }
        }
        System.out.println(remove(s, arr));
    }

    public static int remove(char[] s,int[] arr) {
        int count = 0;
        int r_id = 1;
        int b_id = 1;
        for (int i = 0; i < arr.length; i++) {
            if (s[i] == 'R' && arr[i] == r_id ) {
                r_id++;
            } else if (s[i] == 'B' && arr[i] == b_id) {
                b_id++;
            } else {
                int r_idx = r_map.get(r_id);
                int b_idx = b_map.get(b_id);
                if (r_idx < b_idx) {
                    bubble(s, arr, r_idx, i);
                    count += r_idx - i;
                    r_id++;
                } else {
                    bubble(s, arr, b_idx, i);
                    count += b_idx - i;
                    b_id++;
                }
            }
            System.out.println(count);
        }
        return count;
    }

    public static void bubble(char[] s, int[] arr, int end, int start) {
        for (int i = end; i > start; i--) {
            if (s[i - 1] == 'R') {
                r_map.put(arr[i - 1], i - 1);
            } else {
                b_map.put(arr[i - 1], i - 1);
            }
            int val = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = val;
            char tmp = s[i - 1];
            s[i - 1] = s[i];
            s[i] = tmp;
        }
        if (s[end] == 'R') {
            r_map.put(arr[end], start);
        } else {
            b_map.put(arr[end], start);
        }
    }
}