Leetcode

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1: Input: [5,7] Output: 4 Example 2: Input: [0,1] Output: 0 Solution 1 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] ...

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Notes: Firstly, we find the index where the numbers start growing, than do basic binary search. ...

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. class Solution { public int minPathSum(int[][] grid) { if (grid.length == 0) { return 0; } int[][] dp = new int[grid.length][grid[0].length]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { dp[i][j] = grid[i][j]; // We omit first row and first column if (i > 0 && j > 0) { dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]); } else if (i > 0) { dp[i][j] += dp[i - 1][j]; } else if (j > 0) { dp[i][j] += dp[i][j - 1]; } } } return dp[dp.length - 1][dp[0].length - 1]; } }

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output: 1 ```txt Example 2: Input: 11000 11000 00100 00011 Output: 3 class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j] == '1') { count++; bfs(grid, i, j); } } } return count; } void bfs(char[][] grid, int i, int j) { if (i < 0 || i >= grid.length) { return; } if (j < 0 || j >= grid[i].length) { return; } if (grid[i][j] == '0') { return; } grid[i][j] = '0'; bfs(grid, i + 1, j); // up bfs(grid, i, j + 1); // right bfs(grid, i - 1, j); // down bfs(grid, i, j - 1); //left } } Solution 2021-10-23 class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { dfs(i, j, grid); count++; } } } return count; } int[][] DIRS = new int[][] { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, }; void dfs(int i, int j, char[][] grid) { if (i < 0 || j < 0 || i == grid.length || j == grid[0].length) { return; } if (grid[i][j] != '1') { return; } grid[i][j] = '0'; for (int[] dir: DIRS) { int x = i + dir[0]; int y = j + dir[1]; dfs(x, y, grid); } } }

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Example: Input: [1,2,3,4] Output: [24,12,8,6] Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer. Note: Please solve it without division and in O(n). ...

Given a string containing only three types of characters: ‘(’, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis ‘(’ must have a corresponding right parenthesis ‘)’. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(’. Left parenthesis ‘(’ must go before the corresponding right parenthesis ‘)’. ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string. An empty string is also valid. Example 1: ...

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]: direction can be 0 (for left shift) or 1 (for right shift). amount is the amount by which string s is to be shifted. A left shift by 1 means remove the first character of s and append it to the end. Similarly, a right shift by 1 means remove the last character of s and add it to the beginning. Return the final string after all operations. ...