我的算法刷题笔记（3.18-3.22）

1. 螺旋矩阵

原题链接

1. total是总共走的步数

2. int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位

3. visited[row][column] = true;用于判断是否走完一圈

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> order = new ArrayList<Integer>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return order;}int rows = matrix.length, columns = matrix[0].length;boolean[][] visited = new boolean[rows][columns];int total = rows * columns;int row = 0, column = 0;int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int directionIndex = 0;for (int i = 0; i < total; i++) {order.add(matrix[row][column]);visited[row][column] = true;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];column += directions[directionIndex][1];}return order;}
}

2. 生命游戏

原题链接

1. 使用额外的状态2

class Solution {public void gameOfLife(int[][] board) {int[] neighbors = {0, 1, -1};int rows = board.length;int cols = board[0].length;// 遍历面板每一个格子里的细胞for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {// 对于每一个细胞统计其八个相邻位置里的活细胞数量int liveNeighbors = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (!(neighbors[i] == 0 && neighbors[j] == 0)) {// 相邻位置的坐标int r = (row + neighbors[i]);int c = (col + neighbors[j]);// 查看相邻的细胞是否是活细胞if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {liveNeighbors += 1;}}}}// 规则 1 或规则 3 if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {// -1 代表这个细胞过去是活的现在死了board[row][col] = -1;}// 规则 4if (board[row][col] == 0 && liveNeighbors == 3) {// 2 代表这个细胞过去是死的现在活了board[row][col] = 2;}}}// 遍历 board 得到一次更新后的状态for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (board[row][col] > 0) {board[row][col] = 1;} else {board[row][col] = 0;}}}}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/game-of-life/solutions/179750/sheng-ming-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 再复制一份数组

class Solution {public void gameOfLife(int[][] board) {int[] neighbors = {0, 1, -1};int rows = board.length;int cols = board[0].length;// 创建复制数组 copyBoardint[][] copyBoard = new int[rows][cols];// 从原数组复制一份到 copyBoard 中for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {copyBoard[row][col] = board[row][col];}}// 遍历面板每一个格子里的细胞for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {// 对于每一个细胞统计其八个相邻位置里的活细胞数量int liveNeighbors = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (!(neighbors[i] == 0 && neighbors[j] == 0)) {int r = (row + neighbors[i]);int c = (col + neighbors[j]);// 查看相邻的细胞是否是活细胞if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {liveNeighbors += 1;}}}}// 规则 1 或规则 3      if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {board[row][col] = 0;}// 规则 4if (copyBoard[row][col] == 0 && liveNeighbors == 3) {board[row][col] = 1;}}}}
}

3. 旋转图像

原题链接

观察规律，只需四分之一

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < (n + 1) / 2; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
}

4. 矩阵置零

1. 用第一列存储状态，但是需要从后往前

原题链接

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean flagCol0 = false;for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {flagCol0 = true;}for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][0] = matrix[0][j] = 0;}}}for (int i = m - 1; i >= 0; i--) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}if (flagCol0) {matrix[i][0] = 0;}}}
}

5. 有效的括号

1. Map存储 put(‘{’,‘}’); put(‘[’,‘]’); put(‘(’,‘)’); put(‘?’,‘?’)

原题链接

class Solution {private static final Map<Character,Character> map = new HashMap<Character,Character>(){{put('{','}'); put('[',']'); put('(',')'); }};public boolean isValid(String s) {if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;Stack<Character> stack = new Stack<Character>(){};for(Character c : s.toCharArray()){if(map.containsKey(c)) stack.add(c);else if(stack.isEmpty() == true || map.get(stack.pop()) != c) return false;}return stack.size() == 0;}
}

6. 二叉树的中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}

7. 移掉 K 位数字

用12345 54321 15324 作为找规律

原题链接

class Solution {
class Solution {public String removeKdigits(String num, int k) {Deque<Character> stk = new ArrayDeque<>();for (char c : num.toCharArray()) {while (!stk.isEmpty() && c < stk.getLast() && k > 0) {stk.pollLast();k--;}stk.addLast(c);}String res = stk.stream().map(Object::toString).collect(Collectors.joining());res = res.substring(0, res.length() - k).replaceAll("^0+", "");return res.isEmpty() ? "0" : res;}
}

8. 去除重复字母

先拼接到答案，看后面逻辑是否回删

如何遇到重复，那么跳过即可

原题链接

class Solution {public String removeDuplicateLetters(String S) {char[] s = S.toCharArray();int[] left = new int[26];for (char c : s)left[c - 'a']++; // 统计每个字母的出现次数StringBuilder ans = new StringBuilder(26);boolean[] inAns = new boolean[26];for (char c : s) {left[c - 'a']--;if (inAns[c - 'a']) // ans 中不能有重复字母continue;// 设 x = ans.charAt(ans.length() - 1)，// 如果 c < x，且右边还有 x，那么可以把 x 去掉，因为后面可以重新把 x 加到 ans 中while (!ans.isEmpty() && c < ans.charAt(ans.length() - 1) && left[ans.charAt(ans.length() - 1) - 'a'] > 0) {inAns[ans.charAt(ans.length() - 1) - 'a'] = false; // 标记 x 不在 ans 中ans.deleteCharAt(ans.length() - 1);}ans.append(c); // 把 c 加到 ans 的末尾inAns[c - 'a'] = true; // 标记 c 在 ans 中}return ans.toString();}
}

9. 字符串中的第一个唯一字符

原题链接

class Solution {public int firstUniqChar(String s) {Map<Character,Integer> frequency = new HashMap<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);frequency.put(ch, frequency.getOrDefault(ch,0)+1);}for (int i = 0; i < s.length(); i++) {if (frequency.get(s.charAt(i)) == 1) {return i;}}return -1;}
}

10. 最近的请求次数

原题链接

class RecentCounter {Queue<Integer> queue;public RecentCounter() {queue = new ArrayDeque<Integer>();}public int ping(int t) {queue.offer(t);while (queue.peek() < t - 3000) {queue.poll();}return queue.size();}
}

11. 数组中的第K个最大元素

原题链接

1. 小根堆创建

前k个入队列，然后与剩下的对比

class Solution {public int findKthLargest(int[] nums, int k) {// 初始化小顶堆Queue<Integer> heap = new PriorityQueue<>((o1,o2) -> o2 - o1);// 将数组的前k个元素入堆for (int i = 0; i < nums.length; i++) {heap.offer(nums[i]);}// 从第k + 1个元素开始与堆顶元素比较// 若大于堆顶元素则将其入堆,并将当前堆顶元素出堆for (int i = 0; i < k-1; i++) {heap.poll();}return heap.peek();}
}

12. 查找和最小的 K 对数字

堆中的第一个元素一定是答案

原题链接

class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {int n = nums1.length, m = nums2.length;var ans = new ArrayList<List<Integer>>();var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);for (int i = 0; i < Math.min(n, k); i++) // 至多 k 个pq.add(new int[]{nums1[i] + nums2[0], i, 0});while (!pq.isEmpty() && ans.size() < k) {var p = pq.poll();int i = p[1], j = p[2];ans.add(List.of(nums1[i], nums2[j]));if (j + 1 < m)pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});}return ans;}
}

13. 丑数Ⅱ

原题链接

class Solution {public int nthUglyNumber(int n) {int[] factors = {2, 3, 5};Set<Long> seen = new HashSet<Long>();PriorityQueue<Long> heap = new PriorityQueue<Long>();seen.add(1L);heap.offer(1L);int ugly = 0;for (int i = 0; i < n; i++) {long curr = heap.poll();ugly = (int) curr;for (int factor : factors) {long next = curr * factor;if (seen.add(next)) {heap.offer(next);}}}return ugly;}
}

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

原题链接

class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int p = 0;int q = 1;while(q < nums.length){if(nums[p] != nums[q]){nums[p + 1] = nums[q];p++;}q++;}return p + 1;}
}

15.下一个排列

下一个排列

class Solution {public void nextPermutation(int[] nums) {if (nums == null || nums.length == 0) return;int firstIndex = -1;for (int i = nums.length - 2; i >= 0; i--) {if (nums[i] < nums[i + 1]) {firstIndex = i;break;}}if (firstIndex == -1) {reverse(nums, 0, nums.length - 1);return;}int secondIndex = -1;for (int i = nums.length - 1; i >= 0; i--) {if (nums[i] > nums[firstIndex]) {secondIndex = i;break;}}swap(nums, firstIndex, secondIndex);reverse(nums, firstIndex + 1, nums.length - 1);return;}private void reverse(int[] nums, int i, int j) {while (i < j) {swap(nums, i++, j--);}}private void swap(int[] nums, int i, int i1) {int tmp = nums[i];nums[i] = nums[i1];nums[i1] = tmp;}
}

16. 合并两个有序数组

合并两个有序数组

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}}
}

17. 轮转数组

轮转数组

class Solution {public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}
}

18. 比较版本号

比较版本号

class Solution {public int compareVersion(String version1, String version2) {String[] v1 = version1.split("\\.");String[] v2 = version2.split("\\.");for (int i = 0; i < v1.length || i < v2.length; ++i) {int x = 0, y = 0;if (i < v1.length) {x = Integer.parseInt(v1[i]);}if (i < v2.length) {y = Integer.parseInt(v2[i]);}if (x > y) {return 1;}if (x < y) {return -1;}}return 0;}
}

19. 验证回文串

验证回文串

class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}
}

20. 重复的DNA序列

原题链接

class Solution {static final int L = 10;public List<String> findRepeatedDnaSequences(String s) {List<String> ans = new ArrayList<String>();Map<String, Integer> cnt = new HashMap<String, Integer>();int n = s.length();for (int i = 0; i <= n - L; ++i) {String sub = s.substring(i, i + L);cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);if (cnt.get(sub) == 2) {ans.add(sub);}}return ans;}
}

21. 找到 K 个最接近的元素

找到 K 个最接近的元素

class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {List<Integer> list = new ArrayList<>();int n = arr.length;int left = 0;int right = 0; int sum = 0;int res = Integer.MAX_VALUE;int idx = 0;while (right < n) {sum += Math.abs(arr[right] - x);if (right - left + 1 == k) { //固定窗口大小为kif (sum < res) {res = sum;idx = left;}sum -= Math.abs(arr[left] - x);left++;}right++;}for (int i = idx; i < idx + k; i++) {list.add(arr[i]);}return list;  }
}

22. 两数相加

原题链接

/*** 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; }* }*/
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre = new ListNode(0);ListNode cur = pre;int carry = 0;while(l1 != null || l2 != null) {int x = l1 == null ? 0 : l1.val;int y = l2 == null ? 0 : l2.val;int sum = x + y + carry;carry = sum / 10;sum = sum % 10;cur.next = new ListNode(sum);cur = cur.next;if(l1 != null)l1 = l1.next;if(l2 != null)l2 = l2.next;}if(carry == 1) {cur.next = new ListNode(carry);}return pre.next;}
}

23. 旋转链表

原题链接

 * 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 rotateRight(ListNode head, int k) {if (k == 0 || head == null || head.next == null) {return head;}int n = 1;ListNode iter = head;while (iter.next != null) {iter = iter.next;n++;}int add = n - k % n;if (add == n) {return head;}iter.next = head;while (add-- > 0) {iter = iter.next;}ListNode ret = iter.next;iter.next = null;return ret;}
}

24. 删除排序链表中的重复元素 II

原题链接

class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null) {return head;}ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {if (cur.next.val == cur.next.next.val) {int x = cur.next.val;while (cur.next != null && cur.next.val == x) {cur.next = cur.next.next;}} else {cur = cur.next;}}return dummy.next;}
}

25. 反转链表 II

原题链接

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0, head), p0 = dummy;for (int i = 0; i < left - 1; ++i)p0 = p0.next;ListNode pre = null, cur = p0.next;for (int i = 0; i < right - left + 1; ++i) {ListNode nxt = cur.next;cur.next = pre; // 每次循环只修改一个 next，方便大家理解pre = cur;cur = nxt;}// 见视频p0.next.next = cur;p0.next = pre;return dummy.next;}
}

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

原题链接

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;}
}

27. 重排链表

重排链表

class Solution {public void reorderList(ListNode head) {if (head == null) {return;}List<ListNode> list = new ArrayList<ListNode>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;if (i == j) {break;}list.get(j).next = list.get(i);j--;}list.get(i).next = null;}
}

28. 相交链表

原题链接

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;
}}

29. 存在重复元素 II

原题链接

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();int length = nums.length;for (int i = 0; i < length; i++) {int num = nums[i];if (map.containsKey(num) && i - map.get(num) <= k) {return true;}map.put(num, i);}return false;}
}