797. All Paths From Source to Target Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]). ...
![https://leetcode.com/problems/sort-colors/] Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Example 2: Input: nums = [2,0,1] Output: [0,1,2] Example 3: Input: nums = [0] Output: [0] Example 4: Input: nums = [1] Output: [1] Constraints: ...
![https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/] Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together. We repeatedly make k duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique. Example 1: Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete. Example 2: Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa" Example 3: Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps" Constraints: ...
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); dfs(root, result, 0); return result; } void dfs(TreeNode node, List<List<Integer>> result, int level) { if (node == null) { return; } checkSize(result, level); if (level % 2 == 1) { result.get(level).add(0, node.val); } else { result.get(level).add(node.val); } dfs(node.left, result, level + 1); dfs(node.right, result, level + 1); } void checkSize(List<List<Integer>> result, int level) { // 0 [ [] ] // 1 [[][]] // 2 [ [][] ] if (result.size() <= level) { result.add(new ArrayList<>()); } } } Solution 2021-11-18 DFS, DFS + Stack, BFS /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> q = new ArrayDeque<>(); if (root != null) { q.add(root); } int level = 0; while (q.size() > 0) { int size = q.size(); List<Integer> levelList = new ArrayList(); for (int i = 0; i < size; i++) { TreeNode node = q.poll(); if (level % 2 == 0) { levelList.add(node.val); } else { levelList.add(0, node.val); } if (node.left != null) { q.add(node.left); } if (node.right != null) { q.add(node.right); } } res.add(levelList); level++; } return res; } public List<List<Integer>> zigzagLevelOrderDfsStack(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Stack<Pair<TreeNode, Integer>> stack = new Stack<>(); if (root != null) { stack.push(new Pair<>(root, 0)); } while (stack.size() > 0) { Pair<TreeNode, Integer> curr = stack.pop(); TreeNode node = curr.getKey(); Integer level = curr.getValue(); if (res.size() == level) { res.add(new ArrayList<>()); } if (level % 2 == 0) { res.get(level).add(node.val); } else { res.get(level).add(0, node.val); } if (node.right != null) { stack.push(new Pair<>(node.right, level + 1)); } if (node.left != null) { stack.push(new Pair<>(node.left, level + 1)); } } return res; } public List<List<Integer>> zigzagLevelOrderDfsRecursive(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); dfs(root, 0, res); return res; } void dfs(TreeNode node, int level, List<List<Integer>> res) { if (node == null) return; if (res.size() == level) { res.add(new ArrayList<>()); } if (level % 2 == 0) { res.get(level).add(node.val); } else { res.get(level).add(0, node.val); } dfs(node.left, level + 1, res); dfs(node.right, level + 1, res); } }
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). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. ...
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Recursive Solution: class Solution { public int climbStairs(int n) { return climbStairs(0, n); } int climbStairs(int i, int n) { if (i > n) return 0; if (i == n) return 1; return climbStairs(i + 1, n) + climbStairs(i + 2, n); } } Recursive Solution with Memo class Solution { public int climbStairs(int n) { int[] memo = new int[n + 1]; return climbStairs(0, n, memo); } int climbStairs(int i, int n, int[] memo) { if (i > n) return 0; if (i == n) return 1; if (memo[i] > 0) { return memo[i]; } return memo[i] = climbStairs(i + 1, n, memo) + climbStairs(i + 2, n, memo); } }
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? ...
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements. Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? ...
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. Hints ...