1859. Sorting the Sentence A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters. A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence. For example, the sentence “This is a sentence” can be shuffled as “sentence4 a3 is2 This1” or “is2 sentence4 This1 a3”....
1861. Rotating the Box You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following: A stone ‘#’ A stationary obstacle ‘*’ Empty ‘.’ The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box....
198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police....
746. Min Cost Climbing Stairs You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor. 1 2 3 4 5 6 7 8 9 10 11 Example 1: Input: cost = [10,15,20] Output: 15 Explanation: Cheapest is: start on cost[1], pay that cost, and go to the top....
72. Edit Distance Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character 1 2 3 4 5 6 7 8 Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') 1 2 3 4 5 6 7 8 9 10 Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') Constraints:...
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 1 2 3 4 5 6 [ [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....
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. 1 2 3 4 5 Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. 1 2 3 4 5 Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. Solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i < dp....
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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top....
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?...
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2....