LeetCode 87. Scramble String

Description Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great": great / \ gr eat / \ / \ g r e at / \ a t To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr"

LeetCode 91. Decode Ways

Description A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as

LeetCode 718. Maximum Length of Repeated Subarray

Description Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays. Example 1: Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1]. Note: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 Solutions 动态规划 问题定义: dp[i][j

LeetCode 494. Target Sum

Description You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3.

LeetCode 464. Can I Win

Description In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100. Given

Leetcode Weekly Contest 80

819. Most Common Word Description Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words.  It is guaranteed there is at least one word that isn't banned, and that the answer is unique. Words in the list of banned words are given in lowercase, and free of punctuation.  Words in the paragraph are not case sensitive.  The answer is in lowercase.

LeetCode 62. Unique Paths

62. Unique Path 动态规划 初始状态: dp[i][0] = 1 dp[0][i] = 1 递推公式: dp[i][j]=dp[i-1][j]+dp[i][j-1] 返回: dp[-1][-1] 代码: class Solution: def uniquePaths(self, m, n): dp = [[0]*n for _ in range(m)] for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 for i in range(1, m): for j in range(1, n): dp[i][j] =

Leetcode Weekly Contest 79

812. Largest Triangle Area 直接三层循环用海伦公式计算即可 from math import sqrt class Solution: def largestTriangleArea(self, points): dist = {} def d(p1, p2): return sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2) N = len(points) for i in range(N): for j in range(i+1, N): if i not in dist: dist[i] = {} dist[i][j] = d(points[i], points[j]) ret = 0 for i in range(N): for j in

LeetCode 322. Coin Change

动态规划 dp[i]为构成i的最少硬币数目 初始状态: dp[0] = 0 dp[i] = sys.maxsize for i!=0 递推公式: dp[i+c] = min(dp[i+c], dp[i]+1) for c in coins 返回: dp[amount] if dp[amount]!=sys.maxsize else -1 代码: class Solution: def coinChange(self, coins, amount): dp = [sys.maxsize]*(amount+1) dp[0] = 0 for