前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
贪心
- 六六力扣刷题贪心算法之基础和最大子序和
- 六六力扣刷题贪心算法之买卖股票的最佳时机
- 六六力扣刷题贪心算法之买卖股票的最佳时机2
- 六六力扣刷题贪心算法之买卖股票的最佳时机含手续费
- 六六力扣刷题贪心算法之跳跃游戏
- 六六力扣刷题贪心算法之分发饼干
- 六六力扣刷题贪心算法之K次取反后最大化的数组和-- 六六力扣刷题贪心算法之柠檬水找零
数组
链表
题目
给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。
输入： head = [1,2,3,4,5], n = 2 输出： [1,2,3,5]
解析
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 \textit{next}next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 LL。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1L−n+1 个节点时，它就是我们需要删除的节点。
我直接遍历
/** * 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) { ListNode dummy = new ListNode(0, head); int length = getLength(head); ListNode cur = dummy; for (int i = 1; i < length - n + 1; ++i) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = dummy.next; return ans; } public int getLength(ListNode head) { int length = 0; while (head != null) { ++length; head = head.next; } return length; } }
我们再来看看快慢指针
思路：新建dummy节点指向head，指针n1，n2指向head，循环n2指针到n的位置，然后在同时移动n1，n2，直到结尾，n1，n2的距离是n，此时n1的位置就是需要删除元素的位置 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(1)
public static ListNode1 removeNthFromEnd1(ListNode1 head, int n) { ListNode1 dummy = new ListNode1(0); dummy.next = head; ListNode1 n1 = dummy; ListNode1 n2 = dummy; //先移动n2 for (int i = 0; i <=n ; i++) { n2 = n2.next; } //然后再同时遍历 while (n2!=null){ n1=n1.next; n2=n2.next; } n1.next=n1.next.next; return dummy.next;
结束
做了几题链表，对应链表的题目，慢慢的有点感觉了，大家继续加油！
