描述

https://leetcode.com/problems/word-ladder/

给定两个单词 beginWord ，endWord 和一组单词列表，求从 beginWord 到 endWord 的最短转换序列的长度，其中转换规则如下：

1. 每次只能转换一个字母
2. 每次转换后的单词都必须在给定的单词列表中

分析

如下案例,

1
2
3
4
5
6
7
8
9

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

首先使用（给定的单词和单词列表中的）每个单词作为一个顶点，构建连通图，如果两个顶点之间只相差一个字母，则两点之间可达。作图如下，

显然，问题的本质在于图的搜索，即从 beginWord 起始搜索 endWord，如果找到，返回最小路径，否则返回 0。那么问题分两部：

1. 构建无向图
2. 搜索

求解

1. 列表构建无向图，使用二维 map。其中两个顶点的连通性有他们之间的字母差异数决定，当且仅当两顶点的单词相差 1 个字母时连通。

   1 2 3 4 5 6 7

   grahp = [] wordList.append(beginWord) for x in wordList: if x not in graph: grahp[x] = {} for y in wordList: grahp[x][y] = acessiable(x, y)

   其中 accessiable 函数如下定义：

   1 2 3 4 5 6 7 8 9 10

   def acessiable(a, b): if len(a) != len(b): return False i, diff = 0, 0 while i < len(a): if a[i] != b[i]: diff += 1 i += 1 return diff == 1

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2

Input: "cbbd"
Output: "bb"

Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

分析

给定一个数组代表每天的气温，查找多少天之后天气比今天更暖和。首先，想到了暴力算法，如下，

1. 遍历 T
2. 对于第 i 个元素，另 j = i，从 i 开始往后寻找比 T[i] 大的元素，如果找到则 j - i 为第 i 号元素的目标值
3. 重复步骤 2 直到最后一位

给定数组为降序排列时，暴力算法复杂度为 O(n^2)，数组的长度在 [1, 30000]，暴力算法可能会超时。迫于没有想到更好的解题思路，只能对暴力算法先做优化，如果数组是升序的，算法复杂都是 O(n)，所以很乐观，主要考虑优化降序的部分。

考虑如下情况，数组先增后降，

下降转折点到末尾数组元素单调递减，因此每个元素后面都不会有大于他们的元素

如果单调递减后有转折点，那么单调递减的部分元素可能会存在

Description

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Description

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Description

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Description

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Description

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Description

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.