LeetCode初级算法题：子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零java多种解法
1 子数组最大平均数
题目描述
给一个整数数组，找出平均数最大且长度为 k 的下标连续的子数组，并输出该最大平均数。
滑动窗口：
6 2 7 5 8 4 3 1
6 2 7 5 8 4 3 1
窗口移动时，窗口内的和等于sum加上新加进来的值，减去出去的值
解题思路与代码
public double findMaxAverage(int[] nums, int k) { int sum = 0; int n = nums.length; for (int i = 0; i < k; i++) { sum += nums[i]; } int maxSum = sum; for (int i = k; i < n; i++) { sum = sum - nums[i - k] + nums[i]; maxSum = Math.max(maxSum, sum); } return 1.0 * maxSum / k; }
2 二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
解题思路与代码
解法一：深度优先
遍历整颗数，找到每一个叶子节点，从叶子节点往上开始计算，左右子节点都为空则记录深度为1
左右子节点只有一边，深度记录为子节点深度+1
左右两边都有子节点，则记录左右子节点的深度较小值+1
public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int min_depth = Integer.MAX_VALUE; if (root.left != null) { min_depth = Math.min(minDepth(root.left), min_depth); } if (root.right != null) { min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1; }
- 时间复杂度：O(N)
- 空间复杂度：O(logN) 取决于树的高度
解法二：广度优先
从上往下，找到一个节点时，标记这个节点的深度。查看该节点是否为叶子节点，如果是直接返回深度
如果不是叶子节点，将其子节点标记深度(在父节点深度的基础上加1)
class QueueNode { TreeNode node; int depth; public QueueNode(TreeNode node, int depth) { this.node = node; this.depth = depth; } } public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<QueueNode> queue = new LinkedList<QueueNode>(); queue.offer(new QueueNode(root, 1)); while (!queue.isEmpty()) { QueueNode nodeDepth = queue.poll(); TreeNode node = nodeDepth.node; int depth = nodeDepth.depth; if (node.left == null && node.right == null) { return depth; } if (node.left != null) { queue.offer(new QueueNode(node.left, depth + 1)); } if (node.right != null) { queue.offer(new QueueNode(node.right, depth + 1)); } } return 0; }
- 时间复杂度：O(N)
- 空间复杂度：O(N)
3 最长连续递增序列
题目描述
给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
序列的下标是连续的
解题思路与代码
贪心算法
从0开始寻找递增序列，并将长度记录，记录递增序列的最后一个下标，然后从该下标继续寻找，记录
长度，取长度最大的即可
public static int findLength(int[] nums) { int ans = 0; int start = 0; for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] <= nums[i - 1]) { start = i; } ans = Math.max(ans, i - start + 1); } return ans; }
4 柠檬水找零
题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。必须给每个顾客正确找零。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例
输入：[5,5,5,10,20]
输出：true
输入：[10,10]
输出：false
解题思路与代码
贪心算法
public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; for (int bill : bills) { if (bill == 5) { five++; } else if (bill == 10) { if (five == 0) { return false; } five--; ten++; } else { if (five > 0 && ten > 0) { five--; ten--; } else if (five >= 3) { five -= 3; } else { return false; } } } return true; }
