25-MaximumProductSubarray

2022-07-18

25-MaximumProductSubarray 一. 问题描述 * Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. * * Example 1: * * Input: [2,3,-2,4] * Output: 6 * Explanation: [2,3] has the largest product 6. * Example 2: * * Input: [-2,0,-1] * Output: 0 * Explanation: The result cannot be 2, because [-2,-1] is not a subarray. * * 给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。 * leetcode 152 具体思路见视频录制 二. 解决方案(java版) 2.1 暴力破解一 /** * ....

18-Sqrt

2022-07-18

18-Sqrt 一. 问题描述 Implement int sqrt(int x). * * Compute and return the square root of x, where x is guaranteed to be a non-negative integer. * * Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. * * 求一个非负整数的平方根,小数部分被舍去 * * leetcode 69 / 二. 解决方案(java版) 2.1 二分法 /* * 求精确值 * @param x * @return */ public double mySqrt2(int x){ double begin = 0; double end = x; double mid = (begin + end) / 2; while (true){ if (mid * mid == x) ....

19-Sudoku

2022-07-18

19-Sudoku 一. 问题描述 * Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: * * Each row must contain the digits 1-9 without repetition. * Each column must contain the digits 1-9 without repetition. * Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. * * A partially filled sudoku which is valid. * * The Sudoku board could be partially filled, where empty cells are filled with the character '.'. *....

21-NumberOf1Bits

2022-07-18

21-NumberOf1Bits 一. 问题描述 Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight). * * Input: 00000000000000000000000000001011 * Output: 3 * Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. * 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 二. 解决方案(java版) 2.1 解法一 public int hammingWeight(int n) { int count = 0; while (n != 0){ if ((n & 1) == 1) count ++; n = n >>....

15-MaximumDepthOfBinaryTree

2022-07-18

15-MaximumDepthOfBinaryTree 一. 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. leetcode 104,111 即求二叉树的最大深度 同理。求二叉树的最小深度 二. 解决方案(java版) 2.1 递归 public int maxDepth2(TreeNode root) { if (root == null) return 0; int left = maxDepth2(root.left); in....

14-BinaryTreeLevelOrderTraversal

2022-07-18

14-BinaryTreeLevelOrderTraversal 一. 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] 将二叉树分层遍历,即广度优先遍历 二. 解决方案(java版) 2.1 广度优先遍历算法 public List<List<Integer>> levelOrder(TreeNode root) { //定义一个嵌套list,用于存储结果 List<List<Integer>> result = new ArrayList<>(); if ....

23-Subsets

2022-07-18

23-Subsets 一. 问题描述 * Given a set of distinct integers, nums, return all possible subsets (the power set). * * Note: The solution set must not contain duplicate subsets. * * Example: * * Input: nums = [1,2,3] * Output: * [ * [3], * [1], * [2], * [1,2,3], * [1,3], * [2,3], * [1,2], * [] * ] * * 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 * * leetcode 78 二. 解决方案(java版) 2.1 迭代解决 public List<List<Integer>> subsets3(int[] nums) { List<List<Integer>> result = new ArrayList<>()....

17-NQueues

2022-07-18

17-NQueues 一. 问题描述 The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanat....

22-CountingBits

2022-07-18

22-CountingBits 一. 问题描述 * Given a non negative integer number num. * For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation * and return them as an array. * Example 1: * * Input: 2 * Output: [0,1,1] * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。 * leetcode 338 二. 解决方案(java版) 2.1 笨办法 /** * 挨个统计每个数字中包含1的个数 * @param num * @return */ public int[] countBits(int num) { //遍历0->num int[] result = new int[num + 1]; for (int i = 0;....

10-TwoThreeSum

2022-07-18

10-TwoThreeSum 一. 问题描述 twoSum Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 返回数组中满足两数之和为指定数字的数组下标的集合 threeSum Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique ....

05-ImplementQueueUsingStack

2022-07-18

05-ImplementQueueUsingStack 一. 问题描述 使用栈实现队列的数据结构 二. 解决方案(java版) package stack_queue; import java.util.Stack; /** * @Author: M˚Haonan * @Date: 2019-04-22 20:44 * @Description: 用队列实现栈的数据结构 */ public class ImplementQueueUsingStacks { public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); queue.push(1); queue.push(2); queue.push(3); queue.push(4); queue.push(5); System.out.println(queue.pop()); System.out.println(queue.size()); System.out.println(queue.peek()....

07-KthLargestElementInStream

2022-07-18

07-KthLargestElementInStream 一. 问题描述 Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. You may assume that nums' length ≥ k-1 and k ≥ 1. 求一个数字流中的第k个最大的数 二. 解决方案(java版) 2.1 纯数组 package priority_queue; import java.util.Arrays; /** * @Author: M˚Haonan * @Date: 2019-04-23 11:54 * @Description: 求一个流式数据中的第k个最大值(自己的笨办法) */ public class KthLargestElementInStream { private int k; private int [] nums; p....

02-SwapNodesinPairs

2022-07-18

02-SwapNodesinPairs 一. 问题描述 Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. 二. 解决方案(java版) 2.1 递归 package array_linked; public class SwapNodesInPairs { public static ListNode swapPairs(ListNode head) { if (head == null || head.next == null){ return head; } ListNode next = head.next; ListNode nextTwp = ....

12-POW

2022-07-18

12-POW 一. 题目描述 计算x的n次方 二. 解决方案(java版) 2.1 递归 public static double myPow3(double x, int n) { if (n < 0){ return 1/myPow3(x, -n); } if (n == 0) return 1; if (n == 1) return x; return (n % 2) == 0 ? myPow3(x * x, n / 2) : x * myPow3(x*x, n / 2); } 2.2 迭代 /** * 利用位运算, 如果n为奇数,先乘一次再x,然后再x^2,n减半,因为n直接除以2会消灭掉一个x * @param x * @param n * @return */ public static double myPow4(double x, int n) { if (n == 0) return 1; if (n < 0 ){ x = 1 / x; n = - n; } double pow = 1; while (n > 0){ ///如果n为奇数 if ....

04-Valid Parentheses

2022-07-18

04-Valid Parentheses 一. 问题描述 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. 即判断括号是否合法 二. 解决方案(java版) 2.1 使用栈 package stack_queue; import java.util.HashMap; import java.util.Map; import java.util.Queue; import java.util.Stack; /** * @A....

08-SlidingWindowMaximum

2022-07-18

08-SlidingWindowMaximum 一. 问题描述 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5....

24-Triangle

2022-07-18

24-Triangle 一. 问题描述 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 求一个三角形序列中从上往下累加的最小值,上一层的元素只能和下一层相邻的元素加 * * leetcode 120 二. 解决方案(java版) 2.1 从上往下思考 /** * 从上往下考虑 * 所有的元素分为4种,(0,0)的元素 * 左斜边的元素,右斜边的元素,中间的元素 * 根据格子的递推公式求出对应的值 * @param triangle * @return */ public int mi....

03-LinkedListCycle

2022-07-18

03-LinkedListCycle 一. 问题描述 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. 即判断一个链表是否有环 二. 解决方案(java版) 2.1 使用set数据结构 /** * 使用set数据结构来判重,时间复杂度为o(n*1) * 空间复杂度为o(n) * @param head * @return */ public static boolean hasCycle(ListNode head) { Set<ListNode> set = new HashSet<&....

13-MajorityElement

2022-07-18

13-MajorityElement 一. 题目描述 Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. * You may assume that the array is non-empty and the majority element always exist in the array. * leetcode 169 求一个数组中出现次数大于n/2的元素 二. 解决方案(java版) 2.1 map统计 /** * 利用map统计数量 * @param nums * @return */ public int majorityElement1(int[] nums) { //创建一个map,数字和数量的对应关系 Map<Integer, Integer> map = new HashMap<>(); //遍历数组 for (int num : nu....

04-树结构

2022-07-18

04-树结构 第一部分 树结构 一. 二叉树 1.1 概念 任何一个节点的子节点数量不超过2的树叫做二叉树 二叉树的子节点分左节点和右节点 满二叉树 所有叶子节点都在最后一层,而且节点的总数为: $$ 2^n-1 $$ n为树的高度 完全二叉树 (1)所有的叶子节点都出现在K或者K-1层,而且从1到K-1层必须达到最大节点数。 (2)第K层可以不是满的,但是第K层的所有节点必须集中在最左边。 完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干节点. 1.2 链式存储的二叉树 利用链表实现的二叉树 每个节点分3部分,左边指向左子节点,中间存储数据(权),右边指向右子节点 遍历方式 前序遍历 自己->左->右 中序遍历 左-> 自己->右 后序遍历 左->右->自己 1.3 顺序存储的二叉树 利用数组实现的二叉树 顺序存储的二叉树通常只考虑完全二叉树 性质 第n个元素的左子节点位置为:2n + 1 第n个元素的右子节点位置为:2n + 2 第n....