刷题打卡，第 二十五 天
题目一、19. 删除链表的倒数第 N 个结点
题目二、870. 优势洗牌
题目一、19. 删除链表的倒数第 N 个结点
原题链接：19. 删除链表的倒数第 N 个结点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
/
示例 2：
输入：head = [1], n = 1
输出：[]
/
示例 3：
输入：head = [1,2], n = 1
输出：[1]
解题思路：
题目要求我们删除指定的倒数第n个节点，并且返回链表的头节点。
为了得到倒数第n个节点的位置，我们需要遍历整个链表，记录节点的数量，但是我们知道，链表是单向的，当我们遍历完整个链表，就没有办法再回到遍历过节点前的位置了。
为了解决这个问题，我们就需要额外创建新的链表，将其指向头节点，这么一来，当我们遍历完链表，就可以通过另外一个头节点操作链表，删除倒数第n个位置的节点。
当我们对链表完成删除操作，就相当于再一次遍历了链表，又找不回头节点了，所以还要提前建立一个链表，将头节点指向head，方便我们删除完节点后还能返回头节点。
总的来说，我们新创建了两个额外的头节点，方便返回头节点位置。
这么一来，我们就成功通过两次遍历完成需求，第一次遍历获取链表长度，第二次遍历完成了节点的删除…
提交代码：
/** * 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; //返回链表中第一个节点坐标 } }
提交结果：
题目二、870. 优势洗牌
原题链接：870. 优势洗牌
题目描述：
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
/
示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]
/
示例 2：
输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]
解题思路：
需要让优势最大化，我们首先记录下两个数组原始的下标位置，然后给两个数组排序，借此让优势最大化。
因为当我们排序后，比较nums1 与 nums2 的首元素，当nums1元素 大于 nums2 元素，就能形成优势，而这时候因为排序了的缘故，nums1后面的元素都是大于nums2首元素的，这让便于让优势最大化。
当我们的nums1首元素与nums2首元素比较发现较小而没有优势时，我们就能直接删除掉nums1元素，因为此元素依旧无法形成优势了，原因与上一段一样，我们可以将它与nums2中的尾部最大元素对应。同时nums2尾部元素也可以删除。
一直冲下去，到最后就能得到一个优势最大化的数组，直接返回即可。
提交代码：
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; //返回优势最大化数组 } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
