【Day25】LeetCode算法刷题[19. 删除链表的倒数第 N 个结点 ] [870. 优势洗牌 ]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;                      //用于记录链表长度
        ListNode temp = head;             //指向链表第一个元素
        ListNode curr = new ListNode(0,head); //创建一个待头节点的链表，头节点指向链表的第一个元素
        while(temp != null){              //遍历链表
            temp = temp.next;             //从第一个元素开始遍历
            len++;                        //记录节点个数
        }
        temp = curr;                      //使用带头结点的链表遍历
        for(int i = 1;i < len-n+1 ;++i){  //从头节点0的下一个元素开始,遍历到倒数第n个数的前一个节点
            temp = temp.next;                 
        }
        temp.next = temp.next.next;       //删除倒数第n个节点
        return curr.next;                 //返回链表中第一个节点坐标

    }
}

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;            //获取数组的长度
        Integer[] idx1 = new Integer[n]; //创建包装类Integer数组，因为可以设置比较器
        Integer[] idx2 = new Integer[n];
        for (int i = 0; i < n; ++i) {    //记录两个数组的下标位置
            idx1[i] = i;
            idx2[i] = i;
        }
        //调用Arrays的sort()排序方法
        Arrays.sort(idx1, (i, j) -> nums1[i] - nums1[j]);//将数组由小到大排序
        Arrays.sort(idx2, (i, j) -> nums2[i] - nums2[j]);

        int[] ans = new int[n];           //创建数组，存放优势最大化数组
        int left = 0, right = n - 1;      //记录左右下标
        for (int i = 0; i < n; ++i) {     //遍历两个排序好的数组
        //只需要对比首个元素
            if (nums1[idx1[i]] > nums2[idx2[left]]) { // 如果nums1当前元素更大
            //代表后面的数字也会比nums2当前元素大，可以让优势最大化
                ans[idx2[left]] = nums1[idx1[i]];
                ++left;
            } else {//如果nums1元素较小，那就删除当前元素，向后移动
                ans[idx2[right]] = nums1[idx1[i]];//将删除的较小元素与nums2最大元素对照
                --right;                     
            }
        }
        return ans;    //返回优势最大化数组
    }
}