Dmitrii Volyx

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). 1 2 3 4 Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 1 2 3 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. 1 2 3 4 5 6 7 8 9 10 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Example 1: Input: 11110 11010 11000 00000 Output: 1 ```txt Example 2: Input: 11000 11000 00100 00011 Output: 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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]. 1 2 3 4 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. ...

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. ...

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: 1 2 3 4 5 6 7 8 9 Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: ```txt Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note: The length of the given binary array will not exceed 50,000. ...

We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.) ...

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree 1 2 3 4 5 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. ...

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. 1 2 3 4 5 6 7 8 9 10 Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class MinStack { private LinkedList<Node> stack = new LinkedList<>(); /* value, min -3, -3 0, -2 -2, -2 */ /** initialize your data structure here. */ public MinStack() { } public void push(int x) { Node node; if (stack.isEmpty()) { node = new Node(x, x); } else { int min = Math.min(x, stack.peekFirst().min); node = new Node(x, min); } stack.push(node); System.out.printf("val %d min %d\n", node.value, node.min); } public void pop() { Node pop = stack.pop(); System.out.printf("pop val %d min %d\n", pop.value, pop.min); } public int top() { return stack.peekFirst().value; } public int getMin() { Node first = stack.peekFirst(); System.out.printf("getMin val %d min %d\n", first.value, first.min); return first.min; } class Node { Node(int value, int min) { this.value= value; this.min = min; } int value; int min; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */