Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. Example: Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6 Hint Height: 1 0 1 0 0 2 0 2 1 1 3 1 3 2 2 4 0 0 3 0 Left: 0 0 2 0 0 0 0 2 2 2 0 0 2 2 2 0 0 0 3 0 Right:
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police.
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|. Example: Input: 1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 Output: 6 ###Explanation: Given three people living at (0,0), (0,4), and (2,2): The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal.
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Solution (Dynamic Programming) class Solution { public int maxSubArray(int[] nums) { if (nums.
Given two arrays, write a function to compute their intersection. Example 1 Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2 Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Note Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm?
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1 Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2 Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7] Solution: class Solution { public List<Integer> spiralOrder(int[][] matrix) { if (matrix == null || matrix.
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1 Input: 121 Output: true Example 2 Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3 Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. Optimal Substructure: Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y.
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the shortest path from the root node down to the nearest 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 minimum depth = 3. Solution: recursion /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.