Shawni's Blog

有序数组的平方有序数组的平方 此题目使用快慢指针法，一个指针指向数组开头，一个指针指向数组末尾。 因为是有序数组，最大值不是在左边，就是在右边，不会在中间。 使用快慢指针，可以得出 如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 1234567891011121314151617181920212223242526class Solution { public int[] sortedSquares(int[] nums) { if(nums.length == 1){ nums[0] = nums[0]*nums[0]; return nums; } int i=0; int j = nums.length-1; int k=nums.length-1; in ...

长度最小的子数组长度最小的子数组 滑动窗口法滑动窗口类似于双指针法，也是使用双指针，但是类似一个窗口根据不同条件在原数组上滑动。 滑动窗口的确定主要三点: 窗口内是什么？ 如何移动窗口的起始位置？ 如何移动窗口的结束位置？ 窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。 窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。 12345678910111213141516171819202122class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0; int right = 0; int sum = 0; int subLength = 0; int result = Integer.MAX_VALUE; for(;right< nums.length; ...

3. 移除元素移除数组中的元素 快慢指针法通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 使用两个指针，一个快指针用于寻找新数组元素，一个慢指针更新新数组下标位置 1234567891011class Solution { public int removeElement(int[] nums, int val) { int slowIndex = 0; for(int fastIndex = 0;fastIndex<nums.length ;fastIndex++) if(val != nums[fastIndex]) nums[slowIndex++] = nums[fastIndex]; return slowIndex; }}

环形链表环形链表 此题解题思路分为两部分 1. 判断链表中是否有环可以使用快慢指针法，slow 每次往前走一格，fast 每次往前走两格。这样每次 fast 会比 slow 多走一格，相当于往前去追 slow ，若存在环，则 slow 和 fast 一定会相遇，定义其相遇的节点为 相遇节点 index1。 可设距离如下图所示，则 slow 走过的距离为 $x+y$ , fast 走过的距离为 $x+y+n(y+z)$，而 fast 走过的距离应该是为 slow 的两倍，所以有 $2*(x+y) = x+y+n(y+z)$ 最后可得 $$x+y = n(y+z)$$ 要寻找的节点是起始节点，也就是要寻找 $x$ 的值，化简上述式子可得 $$x = (n-1)(y+z)+z$$ 当 $n=1$ 时，有 $x = z$，由此可得，我们寻找环起始节点的方法。 2. 寻找环起始节点判断链表存在环后，需要寻找环的起始节点。此处也是使用双指针法，一个从相遇节点处开始往前移动，一个从head处往前移动，这样到最后两指针相遇位置就会是环的起始节点

链表相交链表相交 1. O(n) 解法首先计算出两个链表的长度差，使最长的链表先移动到两链表相同长度之处，再同时往后移动，边移动边比较。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; ListNode curA = headA; ListNode curB = headB; int cntA =0, cntB=0; while(curA != null){ cntA++; curA=curA.next; } ...

删除链表的倒数第n个元素删除链表的倒数第n个元素 双指针的经典应用 fast指针先走 n+1 步（n+1 是使slow指针能指向删除节点的前一个节点），再使fast指针和slow指针同时往前走 直至 fast 指针为 null。(当fast指针为空时，即fast走到了链表末尾，此时两指针距离 n+1 ，即为倒数第n个元素的前一元素) 12345678910111213141516171819202122class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 创建一个虚拟头节点 ListNode cur = new ListNode(0); cur.next = head; ListNode slow = cur,fast=cur; // fast 先走 n+1 步 for(int i=0;i<=n;i++){ fast = fast.next; } ...

两两交换链表中的元素两两交换链表中的元素 采用模拟的方式，添加一个虚拟头节点，进行交换。 1234567891011121314151617181920212223class Solution { public ListNode swapPairs(ListNode head) { ListNode ans = new ListNode(0); ans.next = head; ListNode cur = ans; ListNode first,temp,second; while(cur != null && cur.next!=null && cur.next.next!=null){ first = cur.next; //存储第一个节点 second = cur.next.next; //存储第二个节点 temp = cur.next.next.next; // 存储第三个节点 ...

翻转链表翻转链表 此题难点在于怎么在原链表基础上，不使用额外空间将链表进行翻转。 解题思路： 采用两个指针，一个遍历数组，一个指向前一个指针的前一项，每次改变前一个指针的指向，用temp存储，以便遍历。 123456789101112class Solution { public ListNode reverseList(ListNode head) { ListNode pre=null , cur=head; while(cur!=null){ ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }}

设计链表设计链表 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465class Node { int val; Node next; Node(){} Node(int val){ this.val = val; }}class MyLinkedList { int size; //存储节点个数 Node head; public MyLinkedList() { size = 0; head = new Node(0); } public int get(int index) { if(index < 0 || index >= size) return -1; Node cur = head; for(int ...