Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: 1 2 3 4 5 6 7 Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: ...
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: 1 2 3 4 5 6 7 8 Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 Solution ...
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. ...
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: 1 2 3 Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: ...
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. ...
Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree. Example 1: 1 2 3 4 5 6 7 Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). Other valid sequences are: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0 Example 2: ...
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1: 1 2 Input: [5,7] Output: 4 Example 2: 1 2 Input: [0,1] Output: 0 Solution 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int rangeBitwiseAnd(int m, int n) { String left = Integer.toString(m, 2); String right = Integer.toString(n, 2); if (left.length() != right.length()) { return 0; } int i = 0; int counter = 1; StringBuilder sb = new StringBuilder(); while (i < left.length()) { if (left.charAt(i) == right.charAt(i)) { sb.append(left.charAt(i)); } else { while (i < left.length()) { sb.append('0'); i++; } } i++; } return Integer.parseInt(sb.toString(), 2); } } Solution 2 ...
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 ...
(This problem is an interactive problem.) A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1. You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface: ...
Return the root node of a binary search tree that matches the given preorder traversal. (Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.) Example 1: Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] ...