Shawni's Blog

两个数组的交集两个数组的交集 1.数组解法创建一个数组存储出现过的数字，遍历两个数组，遇到值就 ++ 。 有重复的元素的值指向的值会 > 2 1234567891011121314151617181920212223242526272829303132class Solution { public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); //求出数组中最大值 int max = nums1[nums1.length-1] > nums2[nums2.length-1] ? nums1[nums1.length-1] : nums2[nums2.length-1]; int[] res = new int[max+10]; for(int i : nums1){ if(res[i] == 0) //避免重复元素出现 ...

有效的字母异位词有效的字母异位词 Hash 集合 数组 HashSet HashSet 是基于 HashMap 开发出来的集合，允许有 null 值，但不允许有重复元素存在。 HashMap HashMap 是一个散列表，存储结构为 key--value。 Hash 表的底层原理Hash 表存储结构，存储的是值用过 hash 算法算出来的 HashCode ，将 HashCode 值存储在Hash表中，所以hash表是无序的，查找时间消耗为O(1); Hash 碰撞当有两个元素要插入 hash表 同一位置时，此时称这种情况为 hash碰撞 解决方法： 拉链法：即设立 hash表 时，使表长度尽可能满足需求。 线性探测：当碰撞时，后者向下探寻到没有被使用的空间，存储在第一个寻找到的空间中。 题目解析此题就是验证两个字符串是不是由相同的字母根据不同顺序构成。使用一个判断数组即可。 12345678910111213141516171819202122232425class Solution { public boolean isAnagram(String s, Strin ...

螺旋矩阵螺旋矩阵 螺旋矩阵，此类题目考察的是对变化过程的模拟。 上层 由左往右到最后一格前 右层 从上往下 下层 由右往左 左层 由下往上 12345678910111213141516171819202122232425262728293031323334class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; int loop = 0; int start = 0; int num = 1; int i,j; while(loop++ < n/2){ // 模拟上层从左到右 for(j = start ; j< n-loop ; j++){ res[start][j] = num++; } //模拟右侧从上到下 for(i = ...

有序数组的平方有序数组的平方 此题目使用快慢指针法，一个指针指向数组开头，一个指针指向数组末尾。 因为是有序数组，最大值不是在左边，就是在右边，不会在中间。 使用快慢指针，可以得出 如果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; } ...