企业网站建设与网页制作,李家沱网站建设,永倍达电商平台,协同办公软件下载数组字符串
合并两个有序数组
思路
类似于归并排序#xff0c;对两个有序数组进行合并即可#xff0c;但是空间复杂度是O(nm);
代码
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] ans new int[n m];int i 0, j 0;int cnt 0;…数组字符串
合并两个有序数组
思路
类似于归并排序对两个有序数组进行合并即可但是空间复杂度是O(nm);
代码
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] ans new int[n m];int i 0, j 0;int cnt 0;while (i m j n) {if (nums1[i] nums2[j]) {ans[cnt] nums1[i];} else {ans[cnt] nums2[j];}}while(i m) ans[cnt] nums1[i];while(j n) ans[cnt] nums2[j];for (int k 0; k cnt; k) {nums1[k] ans[k];}}
}优化有一点小优化吧可以从后往前合并装入nums1的后面这样不会影响nums1的元素同样也节省了nm的空间本题的数据量小所以看不出。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i m - 1;int j n - 1;int cnt n m - 1;while(i 0 j 0) {if (nums1[i] nums2[j]) {nums1[cnt--] nums2[j--];} else {nums1[cnt--] nums1[i--];}}while(i 0) nums1[cnt--] nums1[i--];while(j 0) nums1[cnt--] nums2[j--];}
}双指针
验证回文串
思路
用头指针和尾指针每次比较的时候必须满足两个指针指向的是数字或字符其他的符号都跳过。
代码
class Solution {public boolean isPalindrome(String s) {s s.toLowerCase();int len s.length();int i 0, j len - 1;char[] ch s.toCharArray();while(i j) {while(i len !check(ch[i])) i;while(j 0 !check(ch[j])) --j;//前面两句是过滤非字符或数字if (i j) {break;}if (ch[i] a) {ch[i] - 32;}if (ch[j] a) {ch[j] - 32;}// 如果是字符则统一转为小写if (ch[i] ! ch[j]) {return false;}i;--j;}return true;}private boolean check(char ch) {if (ch z ch a) {return true;}if (ch Z ch z) {return true;}if (ch 9 ch 0) {return true;}return false;}
}滑动窗口
长度最小的子数组
思路
由滑动窗口思想设两个指针尾指针一直走当满足某个条件时头指针也跟着走。 条件当子数组和大于target时不断缩小窗口找到最小的窗口。
代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int ans nums.length;int ind 0;int sum 0;for (int i 0; i nums.length; i) {sum nums[i];while (sum target) {sum - nums[ind];ans Math.min(ans, i - ind 1);ind;}}if (ind 0) { // sumtarget没有执行不存在子数组return 0;} return ans;}
}矩阵
有效的数独
思路
创建三个set数组分别是对存“行”“列”“区域”的数字如果对应的set中有值那么就不是有效的。否则就添加 这里最主要的是怎样判断是否为同一个区域。 可以先对9x9的表格通过i/3,j/3划分为9个3x3区域然后每个区域的值都是 (0, 0), (0, 1), (0, 2) (1, 0), (1, 1)… 再通过将二维数组变为一维数组的计算公式i * row j。就是9个区域。
代码
class Solution {public boolean isValidSudoku(char[][] board) {SetCharacter[] rows new HashSet[9];SetCharacter[] cols new HashSet[9];SetCharacter[] area new HashSet[9];for (int i 0; i 9; i) {rows[i] new HashSet();cols[i] new HashSet();area[i] new HashSet();}for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] 9 || board[i][j] 0) continue;if (rows[i].contains(board[i][j])) {return false;} else {rows[i].add(board[i][j]);}if (cols[j].contains(board[i][j])) {return false;} else {cols[j].add(board[i][j]);}int t i / 3 * 3 j / 3;//System.out.println(i j t);if (area[t].contains(board[i][j])) {return false;} else {area[t].add(board[i][j]);}}}return true;}
}哈希表
赎金信
思路
比较r和m的26个字符个数如果r的某个字符个数大于m的某个字符个数则r不能由m的字符组成。
代码
class Solution {public boolean canConstruct(String r, String m) {int[] rCnt new int[26];int[] mCnt new int[26];for (int i 0; i r.length(); i) {rCnt[r.charAt(i) - a];}for (int i 0; i m.length(); i) {mCnt[m.charAt(i) - a];}for (int i 0; i 26; i) {if (rCnt[i] mCnt[i]) {return false;}}return true;}
}区间
汇总区间
思路
简单模拟
代码
class Solution {public ListString summaryRanges(int[] nums) {ListString ans new ArrayList();int n nums.length;for (int i 0; i n;) {int j i;while(j n -1 nums[j] 1 nums[j 1]) j;if (j i) {ans.add( nums[i]);i;} else {ans.add(nums[i] - nums[j]);i j 1;}}return ans;}
}栈
有效括号
思路
如果能够匹配则删除栈顶元素如果不能匹配就进栈最后判断是否为空。
代码
class Solution {static final MapCharacter, Character map new HashMap() {{put((,));put({,});put([,]);}};public boolean isValid(String s) {char[] ch s.toCharArray();StackCharacter stack new Stack();for (char c : ch) {if (stack.isEmpty()) {stack.push(c);continue;}Character peek stack.peek();if (map.containsKey(peek) map.get(peek) c) {stack.pop();} else {stack.push(c);}}return stack.isEmpty();}
}链表
环形链表
思路
链表长度最长1e4头结点一直往后走如果次数超过链表长度必定有环投机取巧了
代码
public class Solution {public boolean hasCycle(ListNode head) {int cnt 0;while(head ! null) {head head.next;cnt;if (cnt 10005) {return true;}}return false;}
}正解快慢指针根据Floyd判圈法又称为龟兔赛跑算法乌龟每次走一格兔子每次走两格如果有环兔子提前进入环并且一直在环内运动而当乌龟进入环时兔子一定会追到乌龟。
public class Solution {public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false;}ListNode slow head;ListNode fast head.next;while(slow ! fast) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;}
}二叉树
二叉树的最大深度
思路
模拟走一遍二叉树同时记录层数。
代码
class Solution {int ans 0;public int maxDepth(TreeNode root) {dfs(root, 0);return ans;}public void dfs(TreeNode root, int level) {if (root null) {ans Math.max(ans, level);return;}dfs(root.left, level 1);dfs(root.right, level 1);}
}二叉树的遍历
二叉树的右视图
思路
二叉树的层序遍历取每层的最后一个节点即可。
代码
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger ans new ArrayList();if (root null) {return ans;}int cnt 0, lastVal 0;QueueTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {cnt queue.size();// 每层有多少个节点while(cnt-- 0) {TreeNode curNode queue.poll();if (curNode.left ! null) queue.add(curNode.left);if (curNode.right ! null) queue.add(curNode.right);lastVal curNode.val;}ans.add(lastVal);//每层的最后一个节点}return ans;}}二叉搜索树
二叉搜索树的最小绝对差
思路
二叉搜索树的中序遍历是升序而升序的相邻节点可以得到一个最小值即答案所求。
代码
class Solution {int ans Integer.MAX_VALUE;int pre -1; // 记录中序遍历的前一个节点,初始化为-1是还没找到中序遍历的第一个节点public int getMinimumDifference(TreeNode root) {dfs(root);return ans;}private void dfs(TreeNode root) {if (root null) {return;}dfs(root.left);if (pre -1) {pre root.val;} else {ans Math.min(ans, root.val - pre);pre root.val;}dfs(root.right);}
}图
岛屿数量
思路
dfs没走过的为1的格子
代码
class Solution {int N 305;static int[][] dir {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};boolean[][] vis new boolean[N][N];int n, m, ans;public int numIslands(char[][] grid) {m grid.length;n grid[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {if (vis[i][j] || grid[i][j] 0) continue;dfs(grid, i, j);//System.out.println(i - j);ans;}}return ans;}private void dfs(char[][] g, int x, int y) {vis[x][y] true;for (int i 0; i 4; i) {int curX x dir[i][0];int curY y dir[i][1];if (curX 0 || curY 0 || curX m || curY n || g[curX][curY] 0 || vis[curX][curY]) continue;dfs(g, curX, curY);}}
}图广度优先搜索
蛇梯棋
思路
题实在没读懂参考解析。 利用广度优先搜索先走格子如果遇到梯子或蛇就直接传送传送不花时间。
代码
class Solution {int n;int[] g;public int snakesAndLadders(int[][] board) {n board.length;boolean isR true;g new int[n * n 1];int ind 0;for (int i n - 1; i 0; --i) {for (int j (isR ? 0 : n - 1); isR ? j n : j 0; j isR ? 1 : -1) { // 经典的神龙摆尾g[ind] board[i][j];}isR !isR;}int ans bfs();return ans;}private int bfs() {QueueInteger queue new LinkedList(); // 当前到的点MapInteger, Integer m new HashMap(); // 用于存当前点和步数m.put(1, 0);queue.add(1);while(!queue.isEmpty()) {int cur queue.poll();int step m.get(cur);if (cur n * n) return step;for (int i 1; i 6; i) {int nxt cur i;if (nxt n * n) continue;if (g[nxt] ! -1) nxt g[nxt]; //直接传送if (m.containsKey(nxt)) continue; // 已经走过m.put(nxt, step 1);queue.add(nxt);}}return -1;}
}字典树
实现 Trie (前缀树)
思路
字典树模版题
代码
class Trie {static final int N (int) 1e5 9;static int[] cnt new int[N];static int[][] tree new int[N][26];static int ind 0;public Trie() {for (int i ind; i 0; --i) {Arrays.fill(tree[i], 0);}Arrays.fill(cnt, 0);ind 0;}public void insert(String word) {int p 0;for (int i 0; i word.length(); i) {int u word.charAt(i) - a;if (tree[p][u] 0) tree[p][u] ind;p tree[p][u];}cnt[p];}public boolean search(String word) {int p 0;for (int i 0; i word.length(); i) {int u word.charAt(i) - a;if (tree[p][u] 0) return false;p tree[p][u];}return cnt[p] ! 0;}public boolean startsWith(String prefix) {int p 0;for (int i 0; i prefix.length(); i) {int u prefix.charAt(i) - a;if (tree[p][u] 0) return false;p tree[p][u];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/回溯
电话号码的字母组合
思路
将每个键对应的字母存到String里然后dfs变量每一个键遍历到的键存到一个数组里指导存了digits.size()个。
代码
class Solution {private static final String[] MAPPING new String[]{, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};private final ListString ans new ArrayList();private char[] digits, path;public ListString letterCombinations(String digits) {int n digits.length();if (n 0) return List.of();this.digits digits.toCharArray();path new char[n];dfs(0);return ans;}private void dfs(int i) {if (i digits.length) { // 如果已经按完ans.add(new String(path));return;}for (char c : MAPPING[digits[i] - 0].toCharArray()) { // 枚举按每一个键path[i] c; // 考虑先后顺序先出现的和后出现的做匹配dfs(i 1);}}
}
