景安网站备案的服务码,镇江网站建设价位,网站的落地页,政协机关网站建设文章目录第一天存在重复元素最大子数组和第二天两数之和合并两个有序数组第三天两个数组的交集买卖股票最佳时机第四天重塑矩阵杨辉三角第五天有效的数独矩阵置零第六天字符串中第一个唯一字符救赎金第七天判断链表是否有环合并两个有序链表移除链表元素第八天反转链表删除重复…
文章目录第一天存在重复元素最大子数组和第二天两数之和合并两个有序数组第三天两个数组的交集买卖股票最佳时机第四天重塑矩阵杨辉三角第五天有效的数独矩阵置零第六天字符串中第一个唯一字符救赎金第七天判断链表是否有环合并两个有序链表移除链表元素第八天反转链表删除重复元素第九天有效的括号匹配用栈实现队列第十天二叉树前序遍历(非递归)二叉树中序遍历(非递归)二叉树后序遍历(非递归)第十一天二叉树中序遍历二叉树最大深度对称二叉树第十二天反转二叉树路经总和第十三天二叉搜索树中的搜索二叉搜索树中的插入第十四天判断是否为二叉搜索树两数之和 IV最近公共祖先记录力扣数据结构入门OJ题 提示本人是正在努力进步的小菜鸟不喜勿喷~如有大佬发现某题有更妙的解法和思路欢迎提出讨论~
第一天
存在重复元素
OJ链接
利用 HashSet 可以去重的功能, new 一个hashSet , 遍历数组, 如果 hashSet 中不存在该数据, add; 如果存在, 返回 true;
class Solution {public boolean containsDuplicate(int[] nums) {SetInteger hashSet new HashSet();for(int x : nums) {if(!hashSet.contains(x)) {hashSet.add(x);}else {return true;}}return false;}
}时间复杂度: O(N) 需遍历数组长度 空间复杂度: O(N) 需创建数组长度为N的哈希表 最大子数组和
动态规划问题
class Solution {public int maxSubArray(int[] nums) {int ret nums[0];// 取列表中最大值for(int i 1; i nums.length; i) {// 前一个数据 0 时, 把前一个数据加到当前数据上, 返回列表中最大值if(nums[i - 1] 0) {nums[i] nums[i - 1];}ret Math.max(ret, nums[i]);}return ret;}
}时间复杂度: O(N) // 遍历数组 空间复杂度: O(1) 第二天
两数之和
OJ链接
哈希表
class Solution {public int[] twoSum(int[] nums, int target) {int[] ret new int[2];MapInteger, Integer hashMap new HashMap();for(int i 0; i nums.length; i){hashMap.put(i,nums[i]); // (下标, 值)}SetMap.EntryInteger,Integer set hashMap.entrySet();// 转化成Entryfor(Map.EntryInteger,Integer entry1 : set) {for(Map.EntryInteger,Integer entry2 : set) {// 遍历set, 保证两个entry的key值不同时,且value值相加得targetif(entry1.getValue() entry2.getValue() target (entry1.getKey() ! entry2.getKey())) { ret[0] entry1.getKey();ret[1] entry2.getKey();return ret;}}}return ret;}
}这个方法时间效率太低了, 时间复杂度是O(N^2) 空间复杂度是O(N), 优化后如下
class Solution {public static int[] twoSum(int[] nums, int target) {int[] ret new int[2];MapInteger, Integer treeMap new TreeMap();for(int i 0; i nums.length; i){// target和当前数据的差int difference target - nums[i];// 放入当前数据前查看map中是否存在插值, 存在就返回if (treeMap.containsKey(difference)) {// 找到了另一个数ret[0] treeMap.get(difference);ret[1] i;return ret;}// 把数据和下标放入map中treeMap.put(nums[i],i); // (值, 下标)}return ret;}
}时间复杂度: O(N) 空间复杂度: O(N) 合并两个有序数组
OJ链接
逆向双指针 从后往前放入nums1中(nums1后半部分是空的, 所以从后放不会覆盖前面的数据) 谁大谁放 结束条件为 j 把nums2遍历完 由于 i j 遍历的过程中一直在比较, 所以能够保证nums1中越靠后的数据越大
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i m-1;// nums1的指针int j n-1;// nums2的指针int k mn-1;while(j 0){// 从后往前放if(i 0 nums1[i] nums2[j] ) {nums1[k] nums1[i];i--;k--;}else{nums1[k] nums2[j];j--;k--;}}}
}时间复杂度:O(M N) // 双指针遍历数组 空间复杂度:O(1) 第三天
两个数组的交集
OJ链接
哈希表
public class Intersect {public int[] intersect(int[] nums1, int[] nums2) {int[] ret null;MapInteger, Integer hashMap new HashMap();ArrayListInteger list new ArrayList();for(int i 0; i nums1.length ; i) {if(hashMap.containsKey(nums1[i]) ) {// 如果已经存在这个值, 让它的value值1hashMap.put(nums1[i], hashMap.get(nums1[i]) 1);}else {// 如果不存在, 放入这个值hashMap.put(nums1[i], 1);}}for(int i 0; i nums2.length; i) {if(hashMap.containsKey(nums2[i]) hashMap.get(nums2[i]) 0) {// 如果nums1中存在当前值(value值 0视为存在)hashMap.put(nums2[i], hashMap.remove(nums2[i]) - 1);list.add(nums2[i]);}}// 转化成数组ret new int[list.size()];for(int i 0; i ret.length; i) {ret[i] list.get(i);}return ret;}
}买卖股票最佳时机
OJ链接
动态规划
public class MaxProfit {public int maxProfit(int[] prices) {int minPrices Integer.MAX_VALUE;int difference 0;for(int i 0; i prices.length; i) {if(prices[i] minPrices) {minPrices prices[i];}else {// 找到差值最大的情况difference Math.max(prices[i] - minPrices, difference);}}return difference;}
}第四天
重塑矩阵
OJ链接
核心思想: 遍历, 把数据的一维数组下标, 映射到二维数组中
题解如图:
class Solution {public int[][] matrixReshape(int[][] mat, int r, int c) {int[][] ret new int[r][c];int row mat.length; // 行数int column mat[0].length; // 列数if(mat null || row * column ! r * c) {return mat;}// 二维数组用一维表示for(int i 0; i row * column; i) {ret[i/c][i%c] mat[i/column][i%column];}return ret;}
}时间复杂度 : O(M*N) 空间复杂度 : O(1) 杨辉三角
OJ链接
class Solution {public ListListInteger generate(int numRows) {ListListInteger ret new ArrayList();ListInteger firstColumn new ArrayList();// 第一行firstColumn.add(1);ret.add(firstColumn);int i 1;while(i numRows) {// 第一个1ListInteger prev ret.get(i - 1);ListInteger column new ArrayList();column.add(1);// 中间数int j 1;while(j i) {column.add(prev.get(j -1) prev.get(j));j;}// 最后一个1column.add(1);ret.add(column);i;}return ret;}
}第五天
有效的数独
OJ链接 public boolean isValidSudoku(char[][] board) {int[][] row new int[9][9];int[][] column new int[9][9];int[][] Box new int[9][9];for(int i 0; i 9; i) {for(int j 0; j 9; j) {if(board[i][j] ! .) {int val board[i][j] - 0;if(row[i][val - 1] ! 0 || column[val - 1][j] ! 0) {// 说明这一行或这一列已经有过此数据,返回falsereturn false;}if(Box[(i/3) * 3 j/3][val - 1] ! 0) {// 说明九宫格内已经有过此数据, 返回falsereturn false;}row[i][val - 1] val;column[val - 1][j] val;Box[(i/3) * 3 j/3][val - 1] val;}}}return true;}矩阵置零
OJ链接 public void setZeroes(int[][] matrix) {int m matrix.length;int n matrix[0].length;QueueInteger queue new LinkedList();for(int i 0; i m; i) {for(int j 0; j n; j) {if(matrix[i][j] 0) {queue.offer(i * n j);}}}while(!queue.isEmpty()) {int num queue.poll();for(int i 0; i n; i) {matrix[num / n][i] 0;}for(int j 0; j m; j) {matrix[j][num % n] 0;}}}第六天
字符串中第一个唯一字符
OJ链接 public int firstUniqChar1(String s) {int len s.length();MapCharacter, Integer hashMap new HashMap();for(int i 0; i len; i) {char ch s.charAt(i);if(hashMap.containsKey(ch)) {int num hashMap.remove(ch);hashMap.put(ch, num 1);}else {hashMap.put(ch,1);}}for(int j 0; j len; j) {if(hashMap.get(s.charAt(j)) 1) {return j;}}return -1;}public int firstUniqChar2(String s) {int len s.length();for(int i 0; i len; i) {if(s.indexOf(s.charAt(i)) s.lastIndexOf(s.charAt(i))) {return i;}}return -1;}救赎金
OJ链接 public boolean canConstruct(String ransomNote, String magazine) {MapCharacter, Integer hashMap new HashMap();for(int i 0; i ransomNote.length(); i) {char ch ransomNote.charAt(i);hashMap.put(ch, hashMap.getOrDefault(ch, 0) 1);}for(int j 0; j magazine.length(); j) {char ch magazine.charAt(j);if( hashMap.containsKey(ch) hashMap.get(ch) 0) {hashMap.put(ch, hashMap.get(ch) - 1);if(hashMap.get(ch) 0 ) {hashMap.remove(ch);}if(hashMap.size() 0) {return true;}}}return false;}代码优化1: for (int i 0; i t.length(); i) {char ch t.charAt(i);table.put(ch, table.getOrDefault(ch, 0) - 1);if (table.get(ch) 0) {return false;}}代码优化2: public boolean isAnagram3(String s, String t) {if (s.length() ! t.length()) {return false;}char[] str1 s.toCharArray();char[] str2 t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}第七天
判断链表是否有环
哈希或者双指针
OJ链接 public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (fast slow) {return true;}}return false;}合并两个有序链表
OJ链接 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode pHead new ListNode(-1);ListNode prev pHead;while(list1 ! null list2 ! null) {if(list1.val list2.val) {prev.next list1;list1 list1.next;prev prev.next;}else {prev.next list2;list2 list2.next;prev prev.next;}}prev.next list1 null ? list2 : list1;return pHead.next;}移除链表元素
OJ链接 public ListNode removeElements(ListNode head, int val) {if(head null) {return null;}ListNode newHead head;ListNode cur head;ListNode curPrev null;while(cur ! null) {if(cur.val val) {if(cur newHead) {newHead newHead.next;}else {curPrev.next cur.next;cur curPrev.next;continue;}}curPrev cur;cur cur.next;}return newHead;}第八天
反转链表
遍历一次链表, 依次头插即可 public ListNode reverseList(ListNode head) {if(head null) {return null;}ListNode cur head;ListNode newHead cur;while(cur.next ! null) {ListNode curNext cur.next;cur.next curNext.next;curNext.next newHead;newHead curNext;}return newHead;}删除重复元素
注意: 重复数据连续出现的次数可能不止有两次, 所以删除重复数据操作需要while循环 public ListNode deleteDuplicates(ListNode head) {if(head null) {return null;}ListNode cur head;while(cur ! null cur.next ! null ) {ListNode curNext cur.next;while (curNext ! null cur.val curNext.val){cur.next curNext.next;curNext cur.next;}cur cur.next;}return head;}第九天
有效的括号匹配
OJ链接 // 有效的括号匹配public boolean isValid(String s) {DequeCharacter stack new ArrayDeque();// 遍历字符串for (int i 0; i s.length(); i) {char ch s.charAt(i);// 如果是左括号就压栈if (ch ( || ch [ || ch {) {stack.push(ch);}//如果是右括号if (ch ) || ch ] || ch }) {// 如果栈为空说明没有对应的左括号直接返回falseif (stack.isEmpty()) {return false;}// 栈不为空的情况char ch2 stack.peek();if ((ch ) ch2 () || (ch ] ch2 [)|| (ch } ch2 {)) {stack.pop();}else {// 不匹配返回falsereturn false;}}}return stack.isEmpty();}用栈实现队列
OJ链接 // 用栈实现队列DequeInteger stack1 ;DequeInteger stack2;public MyQueue() {stack1 new ArrayDeque();stack2 new ArrayDeque();}public void push(int x) {stack1.push(x);}public int pop() {// 必须保证第二个栈为空时才能入栈if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {// 必须保证第二个栈为空时才能入栈if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}第十天
二叉树前序遍历(非递归)
OJ链接 public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null) {return ret;}DequeTreeNode stack new ArrayDeque();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);ret.add(cur.val);cur cur.left;}cur stack.pop();cur cur.right;}return ret;}二叉树中序遍历(非递归)
OJ链接 public ListInteger inorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null) {return ret;}DequeTreeNode stack new ArrayDeque();TreeNode cur root;while (cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);cur cur.left;}cur stack.pop();ret.add(cur.val);cur cur.right;}return ret;}二叉树后序遍历(非递归)
OJ链接 public ListInteger postorderTraversal(TreeNode root) {ListInteger ret new ArrayList();if(root null) {return ret;}DequeTreeNode stack new ArrayDeque();TreeNode cur root;TreeNode tmp null;while (cur ! null || !stack.isEmpty()) {while(cur!null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();if(top.right null || top.right tmp) {ret.add(top.val);tmp stack.pop();}else {cur top.right;}}return ret;}第十一天
二叉树中序遍历
OJ链接 public ListListInteger levelOrder(TreeNode root) {ListListInteger list new ArrayList();if(root null) {return list;}QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger inList new ArrayList();int size queue.size();while (size 0) {TreeNode node queue.poll();inList.add(node.val);size--;if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}list.add(inList);}return list;}二叉树最大深度
OJ链接 public int maxDepth(TreeNode root) {if(root null) {return 0;}if(root.left null root.right null) {return 1;}int leftDepth maxDepth(root.left);int rightDepth maxDepth(root.right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;}对称二叉树
OJ链接 public boolean isSymmetric(TreeNode root) {if (root null ) {return true;}return isSymmetricChild(root.left, root.right);}public boolean isSymmetricChild(TreeNode leftRoot, TreeNode rightRoot) {if(leftRoot null rightRoot ! null ||leftRoot!null rightRoot null) {return false;}if(leftRoot null rightRoot null) {return true;}if(leftRoot.val ! rightRoot.val) {return false;}return isSymmetricChild(leftRoot.left, rightRoot.right)isSymmetricChild(leftRoot.right, rightRoot.left);}第十二天
反转二叉树
OJ链接 public TreeNode invertTree(TreeNode root) {if(root null ) {return null;}TreeNode tmp root.right;root.right root.left;root.left tmp;invertTree(root.left);invertTree(root.right);return root;}路经总和
OJ链接 public boolean hasPathSum(TreeNode root, int targetSum) {if(root null) {return false;}targetSum - root.val;// 走到头的情况, 判断sum是否等于0if(root.left null root.right null) {if(targetSum 0) {return true;}else {return false;}}boolean hasLeft hasPathSum(root.left, targetSum);boolean hasRight hasPathSum(root.right, targetSum);return hasLeft || hasRight;}第十三天
二叉搜索树中的搜索
OJ链接 public TreeNode searchBST(TreeNode root, int val) {if(root null) {return null;}TreeNode cur root;while(cur ! null) {if(val cur .val) {cur cur.right;}else if(val cur.val) {return cur;}else {cur cur.left;}}return null;}二叉搜索树中的插入
OJ链接 public TreeNode insertIntoBST(TreeNode root, int val) {if(root null) {return new TreeNode(val);}TreeNode cur root;TreeNode curParent null;while(cur ! null) {curParent cur;if(val cur.val) {cur curParent.right;}else {cur curParent.left;}}if(val curParent.val) {curParent.right new TreeNode(val);}if(val curParent.val){curParent.left new TreeNode(val);}return root;}第十四天
判断是否为二叉搜索树
OJ链接
中序遍历每一个结点, 放入list中, 然后再遍历list检查是否有序 public boolean isValidBST(TreeNode root) {ListInteger list new ArrayList();preOrder(root, list);return check(list);}public void preOrder(TreeNode root, ListInteger list) {if(root null) {return;}preOrder(root.left, list);list.add(root.val);preOrder(root.right, list);}public boolean check(ListInteger list) {for(int i 1; i list.size(); i) {if(list.get(i-1) list.get(i)) {return false;}}return true;}方法2, 利用LinkedList(底层是双向链表), 递归进行中序遍历, 每遍历到一个结点之前判断链表尾结点的val是否比当前结点的val值小 public boolean isValidBST(TreeNode root) {LinkedListInteger list new LinkedList();return inOrder(root, list);}public boolean inOrder(TreeNode root, LinkedListInteger list) {if(root null) {return true;}boolean bLeft inOrder(root.left, list);// 两种情况需要尾插// 1,第一次插入 2,到目前为止中序遍历序列有序// 否则直接返回falseif(list.isEmpty() || (bLeft list.getLast() root.val)) {list.add(root.val);}else {return false;}boolean bRight inOrder(root.right, list);return bLeft bRight;}两数之和 IV
OJ链接
class Solution {public boolean findTarget(TreeNode root, int k) {SetInteger hashSet new HashSet();return inOrder(root, k, hashSet);}public boolean inOrder(TreeNode root, int k, SetInteger hashSet) {if(root null) {return false;}boolean bLeft inOrder(root.left, k, hashSet);int ret k - root.val;if(hashSet.contains(ret) ) {return true;}hashSet.add(root.val);boolean bRight inOrder(root.right, k, hashSet);return bLeft || bRight;}最近公共祖先
OJ链接
左边找到返回该结点, 去右边找
三种情况 : 1, 左右只有一边不为空, 哪边不为空返回哪边 2, 左右都不为空, 返回当前结点 3, 左右都为空, 返回null public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) {return null;}if(root.val p.val || root.val q.val) {return root;}TreeNode leftRet lowestCommonAncestor(root.left, p,q);TreeNode rightRet lowestCommonAncestor(root.right,p,q);if(leftRet ! null rightRet null) {return leftRet;}else if(rightRet ! null leftRet null) {return rightRet;}else if(leftRet ! null rightRet ! null) {return root;}return null;}
