Week1题目重刷

• 今天把week1的题目都重新刷了一遍，明天开始week2的内容~

704.二分查找

class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1, m;while (l <= r) {m = (l + r) >>> 1;if (nums[m] < target) {l = m + 1;} else if (nums[m] > target) {r = m - 1;} else {return m;}}return -1;}
}
class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length, m;while (l < r) {m = (l + r) >>> 1;if (nums[m] < target) {l = m + 1;} else if (nums[m] > target) {r = m;} else {return m;}}return -1;}
}

35.搜索插入位置

class Solution {public int searchInsert(int[] nums, int target) {int l = 0, r = nums.length - 1, m;while (l <= r) {m = (l + r) >>> 1;if (nums[m] < target) {l = m + 1;} else if (nums[m] > target) {r = m - 1;} else {return m;}}return l;}
}
class Solution {public int searchInsert(int[] nums, int target) {int l = 0, r = nums.length, m;while (l < r) {m = (l + r) >>> 1;if (nums[m] < target) {l = m + 1;} else if (nums[m] > target) {r = m;} else {return m;}}return l;}
}

27.移除元素

class Solution {public int removeElement(int[] nums, int val) {int s = 0;for (int f = 0; f < nums.length; f++) {if (nums[f] != val) {nums[s] = nums[f];s++;}}return s;}
}

26. 删除有序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {if (nums.length == 1) return 1;int s = 0;for (int f = 1; f < nums.length; f++) {if (nums[f] != nums[s]) {s++;nums[s] = nums[f];}}return ++s;}
}

283. 移动零

class Solution {public void moveZeroes(int[] nums) {int s = 0;for (int f = 0; f < nums.length; f++) {if (nums[f] != 0) {nums[s] = nums[f];s++;}}while (s < nums.length) {nums[s] = 0;s++;}}
}class Solution {public void moveZeroes(int[] nums) {int s = 0;for (int f = 0; f < nums.length; f++) {if (nums[f] != 0) {int t = nums[f];nums[f] = nums[s];nums[s] = t;s++;}}}
}

844. 比较含退格的字符串

class Solution {public boolean backspaceCompare(String s, String t) {return removeBackspace(s).equals(removeBackspace(t));}private String removeBackspace(String str) {Deque<Character> quene = new ArrayDeque();for (char c : str.toCharArray()) {if (c != '#') {quene.addFirst(c);} else {if (!quene.isEmpty()) quene.removeFirst();}}String res = new String();while (!quene.isEmpty()) {res += quene.removeLast();}return res;}
}class Solution {public boolean backspaceCompare(String s, String t) {int i = s.length() - 1, j = t.length() - 1, skipS = 0, skipT = 0;while (i >= 0 || j >= 0) { // 只有两个字符串都遍历结束，大循环才结束，长度不一样内部处理while (i >= 0) { // 对s进行循环if (s.charAt(i) == '#') { // 找到#，把skipS + 1skipS++;i--;}else if (skipS > 0) { // 不是# 但skipS > 0 这个字符应该被删除skipS--;i--;}else break; // 找到了一个要比较的字符} // 这个循环结束，要么找到了要比较的字符，要么 i < 0while (j >= 0) {if (t.charAt(j) == '#') {skipT++;j--;}else if (skipT > 0) {skipT--;j--;}else break;} // j 也一样if (i < 0 && j < 0) return true; // 如果都小于零，说明都变成了空串。返回trueif (i < 0 || j < 0) return false; // 有一个大于零，说明长度不一样，返回falseif (s.charAt(i) != t.charAt(j)) return false; // 都大于零，比较一下这两个字符i--; // 别忘了比较之后移动位置j--;}return true; // 大循环结束，说明两个字符串都遍历完了，长度一样，对应字符一样，返回true}
}

977.有序数组的平方

class Solution {public int[] sortedSquares(int[] nums) {int l = 0, r = nums.length - 1;int[] res = new int[nums.length];for (int i = nums.length - 1; i >= 0; i--) {if (nums[l] * nums[l] > nums[r] * nums[r]) {res[i] = nums[l] * nums[l];l++;} else {res[i] = nums[r] * nums[r];r--;}}return res;}
}

209. 长度最小的子数组

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0, j = 0, res = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {sum += nums[i];while (sum >= target) {res = Math.min(res, i - j + 1);sum -= nums[j];j++;}}return res == Integer.MAX_VALUE ? 0 : res;}
}

904. 水果成篮

class Solution {public int totalFruit(int[] fruits) {int left = 0, res = 0;Map<Integer, Integer> map = new HashMap(); // 哈希表，记录元素出现次数for (int right = 0; right < fruits.length; right++) { // 快指针遍历数组map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1); // 每遍历一个元素，把它在map中的v+1while (map.size() > 2) { // 一旦size>2 说明种类超过了两个，应该开始从左边开始删除元素map.put(fruits[left], map.get(fruits[left]) - 1); // 从左边开始删除元素，这里一定能get到if (map.get(fruits[left]) == 0) { // 因为一旦元素v为0，就removemap.remove(fruits[left]);}left++; // 删除完别忘了移动慢指针}res = Math.max(res, right - left + 1); // 外层循环每进行一次，都要更新一下res}return res; // 最后返回res}
}

76. 最小覆盖子串

class Solution {public String minWindow(String s, String t) {int left = 0, res = Integer.MAX_VALUE, start = 0;int[] countS = new int[128]; // 创建两个数组作为哈希表int[] countT = new int[128];for (char c : t.toCharArray()) {countT[c]++; // 遍历T数组，得到哈希数组}for (int right = 0; right < s.length(); right++) {countS[s.charAt(right)]++; // 快指针走一步，数组更新一次while (check(countS, countT)) { // 一旦check成功，说明s这部分包含了t，可能要更新res，进入内层循环if (right - left + 1 < res) {res = right - left + 1;start = left; // 更新的时候记录start位置}countS[s.charAt(left)]--; // 更新完left指针移动left++;}}return res == Integer.MAX_VALUE ? "" : s.substring(start, start + res);}// check函数的逻辑，一旦发现countT某个位置元素比S大，就返回false，要么比你多要么你没有private boolean check(int[] countS, int[] countT) {for (int i = 0; i < 128; i++) {if (countS[i] < countT[i]) {return false;}}return true;}
}

59.螺旋矩阵II

class Solution {public int[][] generateMatrix(int n) {int l = 0, r = n - 1, b = 0, t = n - 1, num = 1;int[][] res = new int[n][n];while (num <= n * n) {for (int i = l; i <= r; i++) {res[b][i] = num++;}b++;for (int i = b; i <= t; i++) {res[i][r] = num++;}r--;for (int i = r; i >= l; i--) {res[t][i] = num++;}t--;for (int i = t; i >= b; i--) {res[i][l] = num++;}l++;}return res;}
}

203. 移除链表元素

class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) return null;ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;while (pre.next != null) {if (pre.next.val == val) {pre.next = pre.next.next;} else {pre = pre.next;}}return dummy.next;}
}
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) return null;head.next = removeElements(head.next, val);if (head.val == val) head = head.next;return head;}
}

707.设计链表

class MyLinkedList {private ListNode head;private int size;public MyLinkedList() {head = new ListNode(-1);size = 0;}public int get(int index) {if (index < 0 || index >= size) return -1;ListNode cur = head;while (index-- >= 0) {cur = cur.next;}return cur.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if (index > size) return;ListNode pre = head;while (index-- > 0) {pre = pre.next;}ListNode node = new ListNode(val, pre.next);pre.next = node;size++;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) return;ListNode pre = head;while (index-- > 0) {pre = pre.next;}pre.next = pre.next.next;size--;}
}class ListNode {int val;ListNode next;public ListNode(){};public ListNode(int val, ListNode next) {this.val = val;this.next = next;}public ListNode(int val) {this.val = val;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

206.反转链表

class Solution {public ListNode reverseList(ListNode head) {if (head == null) return head;ListNode pre = head;ListNode cur = pre.next;ListNode temp;while (cur != null) {temp = cur.next;cur.next = pre;if (pre == head) pre.next = null;pre = cur;cur = temp;}return pre;}
}
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

24.两两交换链表中的节点

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode reHead = swapPairs(head.next.next);ListNode res = head.next;head.next.next = head;head.next = reHead;return res;}
}
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode dummy = new ListNode(-1, head);ListNode pre = dummy;ListNode cur = head;ListNode temp;while (cur != null && cur.next != null) {temp = cur.next;pre.next = temp;cur.next = temp.next;temp.next = cur;pre = cur;cur = pre.next;}return dummy.next;}
}

19.删除链表的倒数第N个节点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1, head);ListNode temp = dummy;ListNode s = dummy;while (n-- > 0) {temp = temp.next;}while (temp.next != null) {temp = temp.next;s = s.next;}s.next = s.next.next;return dummy.next;}
}

面试题 02.07. 链表相交

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tA = headA;ListNode tB = headB;while (tA != tB) {tA = tA == null ? headB : tA.next;tB = tB == null ? headA : tB.next;}return tA;}
}

142.环形链表Ⅱ

public class Solution {public ListNode detectCycle(ListNode head) {ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;if (f == s) {f = head;while (f != s) {f = f.next;s = s.next;}return f;}}return null;}
}