用友技术笔试-友新星实习项目-Java-01卷（2024.5.26 15:00-17:00）

第1题

public class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int[] diff = new int[n];
        long totalIncrease = 0, totalDecrease = 0;
        for (int i = 0; i < n; i++) {
            diff[i] = nums2[i] - nums1[i];
            if (diff[i] % k != 0) {
                return -1;
            }
            if (diff[i] > 0) {
                totalIncrease += diff[i] / k;
            } else if (diff[i] < 0) {
                totalDecrease += -diff[i] / k;
            }
        }
        if (totalIncrease != totalDecrease) {
            return -1;
        }
        return totalIncrease;
    }
}

第2题

解法1

public class Solution {
    public ArrayList<Integer> findAllPerson(int n, int[][] meetings, int firstPerson) {
        ArrayList<Integer> ans = new ArrayList<>();
        ans.add(0);
        ans.add(firstPerson);
        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int[] meeting : meetings) {
            if (ans.contains(meeting[0]) && !ans.contains(meeting[1])) {
                ans.add(meeting[1]);
            }
            if (ans.contains(meeting[1]) && !ans.contains(meeting[0])) {
                ans.add(meeting[0]);
            }
        }
        Collections.sort(ans);
        return ans;
    }
}

解法2

使用TreeSet去重并排序

public class Solution {
    public ArrayList<Integer> findAllPerson(int n, int[][] meetings, int firstPerson) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);
        set.add(firstPerson);
        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int[] meeting : meetings) {
            if (set.contains(meeting[0])) {
                set.add(meeting[1]);
            }
            if (set.contains(meeting[1])) {
                set.add(meeting[0]);
            }
        }
        return new ArrayList<>(set);
    }
}

第3题

解法1（不符合题目要求的不能更改节点的value）

public class Solution {
    public ListNode groupSort(ListNode head, int n) {
        if (head == null || n <= 1) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode preEnd = dummyHead;
        while (head != null) {
            ListNode start = head;
            ListNode end = head;
            int count = 1;
            while (count < n && end.next != null) {
                end = end.next;
                count++;
            }
            if (count < n) {
                break;
            }
            ListNode nextStart = end.next;
            end.next = null;
            ListNode sortedHead = sort(start);
            preEnd.next = sortedHead;
            while (preEnd.next != null) {
                preEnd = preEnd.next;
            }
            preEnd.next = nextStart;
            head = nextStart;
        }
        return dummyHead.next;
    }

    public ListNode sort(ListNode head) {
        List<Integer> values = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            values.add(cur.val);
            cur = cur.next;
        }
        Collections.sort(values, Collections.reverseOrder());
        cur = head;
        for (Integer value : values) {
            cur.val = value;
            cur = cur.next;
        }
        return head;
    }
}

解法2（符合题目要求）

public class Solution {
    public ListNode groupSort(ListNode head, int n) {
        if (head == null || n <= 1) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode preEnd = dummyHead;
        while (head != null) {
            ListNode start = head;
            ListNode end = head;
            int count = 1;
            while (count < n && end.next != null) {
                end = end.next;
                count++;
            }
            if (count < n) {
                break;
            }
            ListNode nextStart = end.next;
            end.next = null;
            ListNode sortedHead = sort(preEnd);
            preEnd.next = sortedHead;
            while (preEnd.next != null) {
                preEnd = preEnd.next;
            }
            preEnd.next = nextStart;
            head = nextStart;
        }
        return dummyHead.next;
    }

    public ListNode sort(ListNode preEnd) {
        ListNode cur = preEnd.next;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o2.val - o1.val;
            }
        });
        while (cur != null) {
            pq.add(cur);
            cur = cur.next;
        }
        cur = preEnd;
        while (!pq.isEmpty()) {
            cur.next = pq.poll();
            cur = cur.next;
        }
        cur.next = null;
        return preEnd.next;
    }
}

第4题

public class Solution {
    public int[][] interviews;

    public int maxValue(int[][] interviews, int k) {
        if (k < 1) {
            return 0;
        }
        Arrays.sort(interviews, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        this.interviews = interviews;
        int[][] dp = new int[interviews.length + 1][k + 1];
        for (int i = 1; i <= interviews.length; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
                int p = find(i - 1);
                if (p != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[p + 1][j - 1] + interviews[i - 1][2]);
                } else {
                    dp[i][j] = Math.max(dp[i][j], interviews[i - 1][2]);
                }
            }
        }
        return dp[interviews.length][k];
    }

    public int find(int i) {
        int low = 0, high = i - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (interviews[mid][1] < interviews[i][0]) {
                if (mid + 1 <= i - 1 && interviews[mid + 1][1] < interviews[i][0]) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}