linux版网站开发,国外企业网页设计,舆情监测系统,营销软件开发我的算法刷题笔记#xff08;3.18-3.22#xff09; 1. 螺旋矩阵1. total是总共走的步数2. int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位3. visited[row][column] true;用于判断是否走完一圈 2. 生命游戏1. 使用额外的状态22. 再复制一份数组 3. 旋转图像观… 我的算法刷题笔记3.18-3.22 1. 螺旋矩阵1. total是总共走的步数2. int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位3. visited[row][column] true;用于判断是否走完一圈 2. 生命游戏1. 使用额外的状态22. 再复制一份数组 3. 旋转图像观察规律只需四分之一 4. 矩阵置零1. 用第一列存储状态但是需要从后往前 5. 有效的括号1. Map存储 put({,}); put([,]); put((,)); put(?,?) 6. 二叉树的中序遍历7. 移掉 K 位数字用12345 54321 15324 作为找规律 8. 去除重复字母先拼接到答案看后面逻辑是否回删如何遇到重复那么跳过即可 9. 字符串中的第一个唯一字符10. 最近的请求次数11. 数组中的第K个最大元素1. 小根堆创建前k个入队列然后与剩下的对比 12. 查找和最小的 K 对数字堆中的第一个元素一定是答案 13. 丑数Ⅱ14. 删除有序数组中的重复项15.下一个排列16. 合并两个有序数组17. 轮转数组18. 比较版本号19. 验证回文串20. 重复的DNA序列21. 找到 K 个最接近的元素22. 两数相加23. 旋转链表24. 删除排序链表中的重复元素 II25. 反转链表 II26. 两两交换链表中的节点27. 重排链表28. 相交链表29. 存在重复元素 II 1. 螺旋矩阵
原题链接
1. total是总共走的步数
2. int[][] directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};方位
3. visited[row][column] true;用于判断是否走完一圈
class Solution {public ListInteger spiralOrder(int[][] matrix) {ListInteger order new ArrayListInteger();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 MapCharacter,Character map new HashMapCharacter,Character(){{put({,}); put([,]); put((,)); }};public boolean isValid(String s) {if(s.length() 0 !map.containsKey(s.charAt(0))) return false;StackCharacter stack new StackCharacter(){};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 ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();inorder(root, res);return res;}public void inorder(TreeNode root, ListInteger 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) {DequeCharacter 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) {MapCharacter,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 {QueueInteger queue;public RecentCounter() {queue new ArrayDequeInteger();}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) {// 初始化小顶堆QueueInteger 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 ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {int n nums1.length, m nums2.length;var ans new ArrayListListInteger();var pq new PriorityQueueint[]((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};SetLong seen new HashSetLong();PriorityQueueLong heap new PriorityQueueLong();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 ListString findRepeatedDnaSequences(String s) {ListString ans new ArrayListString();MapString, Integer cnt new HashMapString, 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 ListInteger findClosestElements(int[] arr, int k, int x) {ListInteger 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;}ListListNode list new ArrayListListNode();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) {MapInteger, Integer map new HashMapInteger, 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;}
}
