Java【数据结构入门OJ题33道】——力扣刷题记录1

记录力扣数据结构入门OJ题

---

提示：本人是正在努力进步的小菜鸟，不喜勿喷~，如有大佬发现某题有更妙的解法和思路欢迎提出讨论~

第一天

存在重复元素

OJ链接

利用 HashSet 可以去重的功能, new 一个hashSet , 遍历数组, 如果 hashSet 中不存在该数据, add; 如果存在, 返回 true;

class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> 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];Map<Integer, Integer> hashMap = new HashMap<>();for(int i = 0; i < nums.length; i++){hashMap.put(i,nums[i]); // (下标, 值)}Set<Map.Entry<Integer,Integer>> set = hashMap.entrySet();// 转化成Entryfor(Map.Entry<Integer,Integer> entry1 : set) {for(Map.Entry<Integer,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];Map<Integer, 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 = m+n-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;Map<Integer, Integer> hashMap = new HashMap<>();ArrayList<Integer> 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 List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> firstColumn = new ArrayList<>();// 第一行firstColumn.add(1);ret.add(firstColumn);int i = 1;while(i < numRows) {// 第一个1List<Integer> prev = ret.get(i - 1);List<Integer> 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;Queue<Integer> 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();Map<Character, 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) {Map<Character, 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) {Deque<Character> 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链接

    // 用栈实现队列Deque<Integer> stack1 ;Deque<Integer> 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 List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null) {return ret;}Deque<TreeNode> 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 List<Integer> inorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null) {return ret;}Deque<TreeNode> 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 List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null) {return ret;}Deque<TreeNode> 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 List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if(root == null) {return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> 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) {List<Integer> list = new ArrayList<>();preOrder(root, list);return check(list);}public void preOrder(TreeNode root, List<Integer> list) {if(root == null) {return;}preOrder(root.left, list);list.add(root.val);preOrder(root.right, list);}public boolean check(List<Integer> 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) {LinkedList<Integer> list = new LinkedList<>();return inOrder(root, list);}public boolean inOrder(TreeNode root, LinkedList<Integer> 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) {Set<Integer> hashSet = new HashSet<>();return inOrder(root, k, hashSet);}public boolean inOrder(TreeNode root, int k, Set<Integer> 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;}

---