Dynamic Programming Questions et reponses d'entretien
Question 26. Arithmetic Slices
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. Return the total number of arithmetic slices in the array.
Example:
Input: [1, 2, 3, 4], Output: 3 (three arithmetic slices: [1, 2, 3], [2, 3, 4], [1, 2, 3, 4])
Question 27. Maximal Square
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:
Matrix: [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]], Output: 4
Question 28. Word Ladder II
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequences from beginWord to endWord.
Example:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"], Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Question 29. Paint House
There are a row of n houses, each house can be painted with one of the three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
Example:
Costs: [[17, 2, 17], [16, 16, 5], [14, 3, 19]], Output: 10 (paint the first house blue, the second house green, and the third house blue)
Question 30. Number of Dice Rolls With Target Sum
You have d dice, and each die has f faces numbered 1 to f. Return the number of possible ways (out of f^d total ways) to roll the dice so the sum of the face-up numbers equals target.
Example:
d = 2, f = 6, target = 7, Output: 6 (possible rolls: [1,6], [2,5], [3,4], [4,3], [5,2], [6,1])
Les plus utiles selon les utilisateurs :