Roman to Integer
题目描述
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
思路：
- 题意：罗马数字最多只有一个“左边修饰”
- 有左边修饰进两位，默认进一位，计算值，并累加。
解：
package main
import "fmt"
func romanToInt(s string) int {
units := make(map[rune]int, 7)
units['I'] = 1
units['V'] = 5
units['X'] = 10
units['L'] = 50
units['C'] = 100
units['D'] = 500
units['M'] = 1000
res := 0
sSlice := []rune(s)
i :=0
for ; i < len(sSlice)-1; {
if units[sSlice[i]] < units[sSlice[i+1]] {
res += units[sSlice[i+1]] - units[sSlice[i]]
i = i+2
}else {
res += units[sSlice[i]]
i++
}
}
if i != len(sSlice){
res += units[sSlice[i]]
}
return res
}
func main() {
s := "III"
res := romanToInt(s)
fmt.Print(res)
}
Integer to Roman
题目描述
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
思路：
- 按面值求余。
解：
package main
import "fmt"
func intToRoman(num int) string {
//M CM D CD C XC L XL X IX V IV I
//1000 900 500 400 100 90 50 40 10 9 5 4 1
res := ""
for ; num >= 1000; {
num -= 1000
res += "M"
}
for ; num >= 900; {
num -= 900
res += "CM"
}
for ; num >= 500; {
num -= 500
res += "D"
}
for ; num >= 400; {
num -= 400
res += "CD"
}
for ; num >= 100; {
num -= 100
res += "C"
}
for ; num >= 90; {
num -= 90
res += "XC"
}
for ; num >= 50; {
num -= 50
res += "L"
}
for ; num >= 40; {
num -= 40
res += "XL"
}
for ; num >= 10; {
num -= 10
res += "X"
}
for ; num >= 9; {
num -= 9
res += "IX"
}
for ; num >= 5; {
num -= 5
res += "V"
}
for ; num >= 4; {
num -= 4
res += "IV"
}
for ; num >= 1; {
num -= 1
res += "I"
}
return res
}
func main() {
res := intToRoman(9)
fmt.Print(res)
}
Longest Substring Without Repeating Characters
题目描述
Given a string, find the length of the longest substring without repeating characters.
思路：
- 遍历，用哈希表判重，键为字符，值为字符位置。保存子串长和起始索引.
- 遍历字节切片。对于重复字符，1、将当前串长curLen更新到maxLen，再算新的curLen。2、计算新的起始索引（而不更新），再从哈希表中清除之前的元素。3、更新起始索引，并更新哈希中sSlice[i]的值。注意步1的两步有先后顺序，步2会清除哈希中sSlice[i]对应的数据，所以对于读取runeMap[sSlice[i]]的操作要先做。
- 遍历结束后，将最后一个串长更新到最大串长maxLen。
- 复杂度O(N)
解：
func lengthOfLongestSubstring(s string) int {
sSlice := []rune(s)
runeMap := make(map[rune]int,len(sSlice))
curLen := 0
maxLen := 0
maxLenIdxStart := 0
for i:=0;i<len(sSlice);i++{
if _,ok := runeMap[sSlice[i]];ok{
if curLen > maxLen {
maxLen = curLen
}
curLen = i - runeMap[sSlice[i]]
maxLenIdxStartNew := runeMap[sSlice[i]]+1
//下面的操作会修改runeMap[sSlice[i]]，要取值的操作先进行
for j:= maxLenIdxStart;j< maxLenIdxStartNew;j++{
delete(runeMap,sSlice[j])
}
maxLenIdxStart = maxLenIdxStartNew
runeMap[sSlice[i]] = i
}else {
curLen++
runeMap[sSlice[i]] = i
}
}
//update
if curLen > maxLen {
maxLen = curLen
}
return maxLen
}
下面是3个题，可构成回文串（贪心 Easy），回文序列（动规 Medium），回文子串（动规 Medium）
Longest Palindrome
题目描述
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
原串是回文的思路（理解错题了）：
- 递归所有子树，或者对子串的始终点动态规划。
- 判断dp[i][j]要用到原来的结果dp[i+1][j-1]，用动态规划。从下往上填，从左往右填。
- 填表顺序：并不是一般的先填边界，而是先填dp[i][i]和dp[i][i+1]。
解：
//原串是回文的写法
func longestPalindrome(s string) int {
sSlice := []rune(s)
dp := make([][]bool,len(s),len(s))
maxLen := 0
for idx,_ := range dp{
dp[idx] = make([]bool,len(s),len(s))
}
for i:=0;i<len(sSlice);i++{
dp[i][i] = true
maxLen = 1
}
if len(sSlice)>1{
for i:=0;i<len(sSlice)-1;i++{
if sSlice[i] == sSlice[i+1] {
dp[i][i+1] = true
maxLen = 2
}
}
}
if len(sSlice) >= 3{
for i:=len(sSlice)-3;i>=0;i--{
for j:=i+2;j< len(sSlice) ;j++ {
if sSlice[i] == sSlice[j] && dp[i+1][j-1] == true{
dp[i][j] = true
if j-i+1 > maxLen {
maxLen = j-i+1
}
}
}
}
}
return maxLen
}
可构成回文串的思路（原题意）：
- 贪心算法。统计字符出现次数。成对计数，再补一个奇数字符。
解：
func longestPalindrome(s string) int {
sSlice := []rune(s)
count := make([]int,128)
for _,elem := range sSlice{
count[elem]++
}
res := 0
for _,elem := range count{
res += elem/2*2
if res%2 == 0 && elem%2 == 1{
res++
}
}
return res
}
Longest Palindromic Subsequence
题目描述
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".
思路：
- 动态规划，子串长i，起始索引为j的字串。最大子序列问题，动态规划串长和起始索引。
- 由于是找序列，动规结果直接就是“子串的最大回文串长度”。
- 对于dp[i][j]，两边相等用则为2+dp[i-2][j+1]，否则取dp[i-1][j-1]和dp[i-1][j+1]的最大值。解释：两边成对可以用去掉两边的结果计算。如果两边不成对，无论中间为奇数或偶数，最多只能“补充”一个字符。所以在补充一个字符的结果中选最大的。
- 填充顺序，i从小大到填，逐行填充第i行。
- 最终结果dp[n][0]
解：
package main
import "fmt"
func longestPalindromeSubseq(s string) int {
sSlice := []rune(s)
dp := make([][]int,len(sSlice)+1)
for idx,_ := range dp{
dp[idx] = make([]int,len(sSlice))
}
for i:= 0;i< len(sSlice);i++{
dp[1][i] = 1
}
for i := 2; i<len(sSlice)+1;i++ {
for j := 0; j<(len(sSlice)-i+1);j++ {
if sSlice[j]== sSlice[i+j-1] {
dp[i][j] = dp[i-2][j+1]+2
}else {
switch dp[i-1][j] > dp[i-1][j+1] {
case true:
dp[i][j] = dp[i-1][j]
case false:
dp[i][j] = dp[i-1][j+1]
}
}
}
}
fmt.Println(dp)
return dp[len(sSlice)][0]
}
func main() {
s := "bbbab"
res := longestPalindromeSubseq(s)
fmt.Print(res)
}
ZigZag Conversion
题目描述
The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line:"PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3)should return"PAHNAPLSIIGYIR".
思路：
- 行数为rows，周期为2*rows-2。
- 遍历字串，打印各周期：行数以内赋给各行，行数内对round-rows行字串赋值。
解：
package main
import "fmt"
func convert(s string, numRows int) string {
if numRows == 1{
return s
}
sSlice := []rune(s)
rows := make([]string,numRows)
for idx,_ := range rows{
rows[idx] = ""
}
round := 2*len(rows)-2
for i:=0;i<len(sSlice);i++{
rem := i%round
if rem< len(rows) {
rows[rem] += string(sSlice[i])
}else {
rows[round-rem] += string(sSlice[i])
}
}
res := ""
for _,elem := range rows{
res += elem
}
return res
}
func main() {
//s := "PAYPALISHIRING"
res := convert("A",2)
fmt.Print(res)
}
思路2：
- Z型串打印，可以非递归实现，不用“尾递归”。
- rowsIdx和strIdx递增打印。打印到rowsIdx==len(rows)，再向上打印完这个周期（注意此过程打印完字串则程序结束）。
细节：
- 会用到HERE:跳转。
解：
import "fmt"
func convert(s string, numRows int) string {
if numRows == 1{
return s
}
sSlice := []rune(s)
rows := make([]string,numRows)
for idx,_ := range rows{
rows[idx] = ""
}
for i,ri:=0,0;i<len(sSlice);{
if ri == len(rows) {
for j := ri-2;j>0;j--{
rows[j] += string(sSlice[i])
i++
if i == len(sSlice){
goto HERE
}
}
ri = 0
}
rows[ri] += string(sSlice[i])
ri++
i++
}
HERE:
res := ""
for _,elem := range rows{
res += elem
}
return res
}
func main() {
s := "PAYPALISHIRING"
res := convert(s,3)
fmt.Print(res)
}
String to Integer (atoi) //TODO
题目描述
Regular Expression Matching
题目描述
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
思路：
- *匹配前面字符的重复。动态规划匹配串，和模式串索引。记录匹配串和模式串，所有从0开始的子串的匹配。总长度dp[s+1]][p+1]。最小问题为，从匹配0个字符开始填，第一行容易填。
- p[j]为.或匹配了s[i] 则dp[i][j] = dp[i-1][j-1]
- p[j]为*：
- a*空匹配，dp[i][j] = dp[i][j-2]
- 为.*或者匹配，以下3情况，有一种情况匹配，则匹配：
- 多匹配：dp[i][j] = d[i-1][j]。（只是去掉s中的一个匹配字符，并未清掉a*对应的所有匹配）
- 单匹配：dp[i][j] = dp[i-1][j-2]（或者是dp[i][j-1]）
- 由以上递推关系，需要先将i=0行填好，再补上。匹配一个字符，模式会有多个a*。
细节：
- 防止取j-1时数组越界。
- p[j]为*，且p[j-1]匹配或不匹配时，a*匹配0个字符并不是同一种情况，因而都会有dp[i+1][j-1]的选项。
解：
package main
import "fmt"
func isMatch(s string, p string) bool {
sSlice := []rune(s)
pSlice := []rune(p)
dp := make([][]bool,len(s)+1)
for idx,_ := range dp{
dp[idx] = make([]bool,len(p)+1)
}
dp[0][0] = true
for i:=0;i<len(p);i++ {
if pSlice[i] == '*' {
dp[0][i+1] = dp[0][i-1]
}
}
for i:=0;i<len(s);i++{
for j:=0;j<len(p);j++{
if pSlice[j] == '.' || pSlice[j] == sSlice[i]{
dp[i+1][j+1] = dp[i][j]
}
if pSlice[j] == '*'{
if pSlice[j-1] == '.' || pSlice[j-1] == sSlice[i]{
//a*匹配1个或多个
dp[i+1][j+1] = dp[i+1][j]|| dp[i][j+1]||dp[i+1][j-1]
}else if j>0 {
dp[i+1][j+1] = dp[i+1][j-1]
}
}
}
}
return dp[len(s)][len(p)]
}
func main() {
s := ""
p := ".*"
res := isMatch(s, p)
fmt.Print(res)
}
leetcode Top 100 questions
Two-sum
题目：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
思路：
- 考虑到相同的数，哈希表的值是个集合。
- //还可以有优化，只遍历<target/2的数，单独处理有两个target/2的情形。
解：
func twoSum(nums []int, target int) []int {
res := make([]int,2)
numberMap := make(map[int][]int)
for idx,elem := range nums{
numberMap[elem] = append(numberMap[elem],idx)
}
for idx,elem := range nums{
if _,ok := numberMap[target-elem];ok{
if numberMap[target-elem][0]!=idx {
res[0] = idx
res[1] = numberMap[target-elem][0]
return res
}else if len(numberMap[target-elem])>1 {
res[0] = idx
if numberMap[target-elem][0] == idx{
res[1] = numberMap[target-elem][1]
}else{
res[1] = numberMap[target-elem][0]
}
}
}
}
Add Two Numbers（熟题）
题目：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
错思路：
- 先用双指针走到尾的方法，再对齐位（边存结果）。（题目要求没有前导0，有则去掉）
- 相加并处理进位。
细节：
- 注意有的链表只有一个元素[0]的情况。
错解：
func main() {
l1 := &ListNode{Val:5}
l2 := &ListNode{Val:5}
res := addTwoNumbers(l1,l2)
fmt.Println(res)
}
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1.Val == 0 && l1.Next == nil{
return l2
}
if l2.Val == 0 && l2.Next == nil{
return l1
}
h1,h2 := l1,l2
for ; h1!=nil && h2!=nil; {
h1,h2 = h1.Next,h2.Next
}
hc1,hc2 := l1,l2
resPre := &ListNode{Val:0,Next:nil}
resCur := resPre
moreThan10 := false
if h1 == nil && h2 != nil{
for ; h2!=nil; {
//存结果
resCur.Next = &ListNode{Val:hc2.Val}
resCur = resCur.Next
hc2 = hc2.Next
h2 = h2.Next
}
}else if h2 == nil && h1 != nil{
for ; h1!=nil; {
//存结果
resCur.Next = &ListNode{Val:hc2.Val}
resCur = resCur.Next
hc1 = hc1.Next
h1 = h1.Next
}
}
for ; hc1!=nil; {
valSum := hc1.Val+hc2.Val
if moreThan10{
valSum++
}
if valSum>=10{
moreThan10 = true
valSum -=10
}else {
moreThan10 = false
}
resCur.Next = &ListNode{Val:valSum}
resCur = resCur.Next
hc1,hc2 = hc1.Next,hc2.Next
}
if moreThan10{
resCur.Next = &ListNode{Val:1}
resCur = resCur.Next
}
return resPre.Next
}
正确解：
//直接相加就可以了
//要处理一个剩余的链表，和最后的进位。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1.Val == 0 && l1.Next == nil {
return l2
}
if l2.Val == 0 && l2.Next == nil {
return l1
}
hc1, hc2 := l1, l2
resPre := &ListNode{Val: 0, Next: nil}
resCur := resPre
moreThan10 := false
for ; hc1 != nil && hc2 != nil; {
valSum := hc1.Val + hc2.Val
if moreThan10 {
valSum++
}
if valSum >= 10 {
moreThan10 = true
valSum -= 10
} else {
moreThan10 = false
}
resCur.Next = &ListNode{Val: valSum}
resCur = resCur.Next
hc1, hc2 = hc1.Next, hc2.Next
}
if hc1 != nil {
for ; hc1 != nil; hc1 = hc1.Next {
valSum := hc1.Val
if moreThan10 {
valSum++
}
if valSum >= 10 {
moreThan10 = true
valSum -= 10
} else {
moreThan10 = false
}
resCur.Next = &ListNode{Val: valSum}
resCur = resCur.Next
}
}
if hc2 != nil {
for ; hc2 != nil; hc2 = hc2.Next {
valSum := hc2.Val
if moreThan10 {
valSum++
}
if valSum >= 10 {
moreThan10 = true
valSum -= 10
} else {
moreThan10 = false
}
resCur.Next = &ListNode{Val: valSum}
resCur = resCur.Next
}
}
if moreThan10 {
resCur.Next = &ListNode{Val: 1}
resCur = resCur.Next
}
return resPre.Next
}
调试时间：38min，题意理解错了，几乎是重新写的。
Longest Substring Without Repeating Characters （熟题）
题目：
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
思路：
- 找最长子串题，不要动态规划 图算法，都不好解。是一道状态更新的题。
- 用键为字母，值为索引的哈希表记状态。保存子串长和起始索引。只保存一个，只换上不重复的值的新值的状态。
- 遍历。对于不重复的字符，加哈希加curLen。对于重复的字符，先更状态，再更哈希。
- 难上遇到重复字符时，处理不同数据的信赖顺序。curLen=i-val,start=val+1,清理start~val的哈希并更新start=val+1,val=i。
- 最后还要处理最后一组。算法复杂度O(N)
调试：
- 需要记录start，从start至val索引的都要从哈希中清掉。
- 调试时间12min。
解：
func main() {
s := "abba"
fmt.Print(lengthOfLongestSubstring(s))
}
func lengthOfLongestSubstring(s string) int {
if len(s) <= 1 {
return len(s)
}
sS := []rune(s)
curLen := 0
maxLen := 0
start := 0
runeMap := make(map[rune]int, len(sS))
for i := 0; i < len(sS); i++ {
if val, ok := runeMap[sS[i]]; ok {
if curLen > maxLen {
maxLen = curLen
}
curLen = i - val
for j:=start;j<val;j++{
delete(runeMap,sS[j])
}
start = val + 1
runeMap[sS[i]] = i
} else {
runeMap[sS[i]] = i
curLen++
}
}
if curLen>maxLen{
maxLen = curLen
}
return maxLen
}
Median of Two Sorted Arrays
题目：
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
思路：
- 题目条件数组均非空，不用检查。数组已排序，时间要求O(log (m+n))
- 直接调用标准库排序，sort.Ints(nums1)。
调试：
- 4min。
解：
func main() {
arr1 := []int{1,3}
arr2 := []int{2}
fmt.Print(findMedianSortedArrays(arr1,arr2))
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums1 = append(nums1,nums2...)
sort.Ints(nums1)//直接用切片修改形参，无返回值。底层是nlogn的快排实现。
l := len(nums1)
var res float64
if l%2 == 0{
res = float64(nums1[l/2-1]+nums1[l/2])/2.0
}else {
res = float64(nums1[l/2])
}
return res
}
思路2：
- 用桶排实现，线性的桶大小时间解决。
- 桶排要能处理负数。实测比快排快4ms。
package main
import (
"fmt"
"math"
)
const INT_MAX = int((^uint(0)) >>1)
const INT_MIN = ^INT_MAX
func main() {
arr1 := []int{1,2}
arr2 := []int{1,1}
fmt.Print(findMedianSortedArrays1(arr2,arr1))
}
func findMedianSortedArrays1(nums1 []int, nums2 []int) float64 {
sortedIntArr := bucketSort(nums1,nums2)
l := len(sortedIntArr)
if l%2 == 0{
return float64(sortedIntArr[l/2]+sortedIntArr[l/2-1])/2.0
}else {
return float64(sortedIntArr[l/2])
}
}
func bucketSort(arrs ...[]int) []int {
//支持负数排序
//支持重复元素，要多次装桶
maxVal := math.MinInt32
minVal := math.MaxInt32
for _,arr := range arrs{
for _,elem := range arr{
if elem>maxVal{
maxVal = elem
}
if elem<minVal{
minVal = elem
}
}
}
bucketCap := maxVal-minVal+1
bucket := make([]int,bucketCap)
for _,arr := range arrs{
for _,elem := range arr{
bucket[elem-minVal]++
}
}
sortedArr := make([]int,0)
for idx,elem := range bucket{
if elem>0{
for i:=0;i<elem;i++{
sortedArr = append(sortedArr,idx+minVal)
}
}
}
return sortedArr
}
Longest Palindromic Substring
题目：
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
BFS思路：
- 回文串要求相连。所有子串装入树。对于子节点遍历，前半串检查，后半串递归。BFS遍历，找最优解（状态以形参传入）。超时了，BFS能够找出所有解，但并不高效。如回文串分割的题用的是BFS，而只找出一个最长回文子串，用DP。
BFS解（超时）：
func longestPalindromeBfs(s string) string {
sS := []rune(s)
maxLen := 0
maxsubStr := make([]rune,len(sS))
dfs(sS,&maxLen,&maxsubStr)
return string(maxsubStr)
}
func dfs(sS []rune,maxLen *int,maxsubStr *[]rune) {
if len(sS)== 0{
return
}
for i:=0;i<len(sS);i++{
subStrS := sS[0:i+1]
if isPalindrome(subStrS){
if len(subStrS)>*maxLen{
*maxLen = len(subStrS)
*maxsubStr = subStrS[:]
}
}
dfs(sS[i+1:len(sS)],maxLen,maxsubStr)
}
}
func isPalindrome(sS []rune) bool {
lSemi := len(sS)
sum := len(sS)-1
for i:=0;i<lSemi;i++{
if sS[i]!=sS[sum-i]{
return false
}
}
return true
}
类似题目最大回文子序列的解，用DP：
- dp变量定义：子串长i，超始索引j，值为j+i子串的所有子串的最长回文串。变量这样定义是由，递推公式决定的。如果i,j定义为左右边界的索引，递推需要(i,j-1) (i+j,j)，不便填表
- 如此变量定义，使相同串长的子串，为dp中的一行，先填表。
dp递推公式：对于dp[i][j]，子串两边相等取2+dp[i-2][j+1]，否则取dp[i-1][j-1]和dp[i-1][j+1]的最大值 - 结果dp[n][0]
最大回文子序列的DP解：
func longestPalindromeSubsequence(s string) int {
if len(s)<2{
return s
}
sS := []rune(s)
dp := make([][]int,len(s)+1)
for idx,_ := range dp{
dp[idx] = make([]int,len(s))
}
for j:=0;j<len(s);j++{
dp[1][j] = 1
}
for i:=2;i<len(s)+1;i++{
for j:=0;j<len(s);j++{
if sS[j] == sS[j+i-1]{
dp[i][j] = 2+dp[i-2][j+1]
}else {
if dp[i-1][j-1]>dp[i-1][j+1]{
dp[i][j] = dp[i-1][j]
}else {
dp[i][j] = dp[i-1][j+1]
}
}
}
}
return dp[len(s)][0]
}
遍历思路（可以accept）：
- 从1或2个元素，扩充至最大回文串。复杂度稍长。
func longestPalindrome(s string) string {
sS := []rune(s)
var maxSubstr []rune
for i:=0;i<len(sS);i++{
findMaxPalindrome(sS,i,i,&maxSubstr)
findMaxPalindrome(sS,i,i+1,&maxSubstr)
}
return string(maxSubstr)
}
func findMaxPalindrome(sS []rune,i,j int,maxSubstr *[]rune) {
var substr []rune
for i>=0 && j< len(sS) && sS[i] == sS[j] {
substr = sS[i:j+1]
if len(substr) > len(*maxSubstr){
*maxSubstr = substr
}
i--
j++
}
}
Container With Most Water
题目：
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
思路：
- O(N^2)暴力应该是不行的。
- 题意是矩形面积，并不是木桶算最矮的板。
- 从两边往中间找，两边宽度最大，是较优的解。向中间，是为了抛弃短板，以获取更大的可能面积。
解：
func maxArea(height []int) int {
l := 0
r := len(height)-1
var maxArea float64
for l<r {
if height[l] < height[r]{
maxArea = math.Max(maxArea,float64(height[l]*(r-l)))
l++
}else {
maxArea = math.Max(maxArea,float64(height[r]*(r-l)))
r--
}
}
return int(maxArea)
}
3Sum
题目：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
思路：
- 先排序，遍历所有负数作为twosum问题的target，转化为两数和问题。
- 问题分为一正两负，一负两正分别处理，0当作正数。单独检测3个0的情况 。
- 细节：两数和问题去重，elem<target/2，有四种情况需要处理。三数和去重，不要用数组遍历，而是用正数或负数的map集合遍历。
解：
package main
import (
"fmt"
"sort"
)
func main() {
a := []int{-1,0,1,2,-1,-4}
res := threeSum(a)
fmt.Print(res)
}
func threeSum(nums []int) [][]int {
res := make([][]int,0)
sort.Ints(nums)
numberMapNegative := make(map[int]int,len(nums))
numberMap := make(map[int]int,len(nums))
zeroCount :=0
for _,elem := range nums{
if elem>0{
numberMap[elem]++
}else if elem<0{
numberMapNegative[elem]++
}else{
zeroCount++
numberMap[elem]++
}
}
if zeroCount>=3{
res = append(res,[]int{0,0,0})
}
//-++
for elem := range numberMapNegative{
if elem<0{
//twosum problem
twosumRes := twosum(numberMap,-elem)
for _,twosumResElem := range twosumRes{
resOne := []int{elem}
resOne = append(resOne,twosumResElem...)
res = append(res,resOne)
}
}
}
//+--
for elem := range numberMap{
if elem>=0{
//twosum problem
twosumRes := twosum(numberMapNegative,-elem)
for _,twosumResElem := range twosumRes{
resOne := []int{elem}
resOne = append(resOne,twosumResElem...)
res = append(res,resOne)
}
}
}
return res
}
func twosum(numberMap map[int]int,target int) [][]int {
res := make([][]int,0)
if target%2 == 0{
if elem,ok := numberMap[target/2];ok && elem>=2{
res = append(res,[]int{target/2,target/2})
}
}
var under int
switch {
case target%2 == 0:
under = target/2
case target>0 && target%2!=0:
under = target/2 +1
case target<0 && target%2!=0:
under = target/2
}
for key,_ := range numberMap{
if key < under{
if _,ok := numberMap[target-key];ok{
res = append(res,[]int{key,target-key})
}
}
}
return res
}
写两个方法占内存，改成一个方法。
解2:
package main
import (
"fmt"
"sort"
)
func main() {
a := []int{-2,2,-1,1,0,3}
res := threeSum(a)
fmt.Print(res)
}
func threeSum(nums []int) [][]int {
res := make([][]int,0)
sort.Ints(nums)
numberMapNegative := make(map[int]int,len(nums))
numberMap := make(map[int]int,len(nums))
zeroCount :=0
for _,elem := range nums{
if elem>0{
numberMap[elem]++
}else if elem<0{
numberMapNegative[elem]++
}else{
zeroCount++
numberMap[elem]++
}
}
if zeroCount>=3{
res = append(res,[]int{0,0,0})
}
//-++
for elem := range numberMapNegative{
if elem<0{
//twosum problem
target := -elem
if target%2 == 0{
if elemM,ok := numberMap[target/2];ok && elemM>=2{
res = append(res,[]int{elem,target/2,target/2})
}
}
var under int
switch {
case target%2 == 0:
under = target/2
case target>0 && target%2!=0:
under = target/2 +1
case target<0 && target%2!=0:
under = target/2
}
for key,_ := range numberMap{
if key < under{
if _,ok := numberMap[target-key];ok{
res = append(res,[]int{elem,key,target-key})
}
}
}
}
}
//+--
for elem := range numberMap{
if elem>=0{
//twosum problem
target := -elem
if target%2 == 0{
if elemM,ok := numberMapNegative[target/2];ok && elemM>=2{
res = append(res,[]int{elem,target/2,target/2})
}
}
var under int
switch {
case target%2 == 0:
under = target/2
case target>0 && target%2!=0:
under = target/2 +1
case target<0 && target%2!=0:
under = target/2
}
for key,_ := range numberMapNegative{
if key < under{
if _,ok := numberMapNegative[target-key];ok{
res = append(res,[]int{elem,key,target-key})
}
}
}
}
}
return res
}
Letter Combinations of a Phone Number
题目：
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
思路：
- 排列组合，每次增加字母都刷新集合。
- 这个题，每个解是无状态的。可以用非递归地添加结果集。如果有状态，就需要用回溯法了。
解：
func letterCombinations(digits string) []string {
wordMap := map[string]string{
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
res := make([]string,0)
for _,digit := range digits{
groupStr := make([]string,0)
words := wordMap[string(digit)]
for _,word := range words{
if len(res)>0{
for _,resStr := range res{
groupStr = append(groupStr,resStr+string(word))
}
}else {
groupStr = append(groupStr,string(word))
}
}
res = groupStr
}
return res
}
Remove Nth Node From End of List
题目：
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
思路：
- 两个指针一起走，一个先走n+1步。找到第倒数n+1个节点，考虑到头节点，要给headPre。
解：
func removeNthFromEnd(head *ListNode, n int) *ListNode {
headPre := ListNode{}
headPre.Next = head
h1 := &headPre
h2 := &headPre
for i:=0;i<n+1;i++{
h1 = h1.Next
}
for h1!=nil{
h1 = h1.Next
h2 = h2.Next
}
h2.Next = h2.Next.Next
return headPre.Next
}
Valid Parentheses
题目：
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
思路：
- 平衡符号问题，没有优先级。开括压栈，闭括出栈。不对应返false，空栈弹出返false，遍历完栈仍不空返false。
解：
func isValid(s string) bool {
stack := list.List{}
for _,sCh := range s{
if sCh == '(' || sCh == '{' || sCh == '['{
stack.PushBack(sCh)
}else if sCh == ')'{
if stack.Len() == 0{
return false
}else if stack.Back().Value!='('{
return false
}else {
stack.Remove(stack.Back())
}
}else if sCh == '}' {
if stack.Len() == 0{
return false
}else if stack.Back().Value!='{'{
return false
}else {
stack.Remove(stack.Back())
}
}else if sCh == ']'{
if stack.Len() == 0{
return false
}else if stack.Back().Value!='['{
return false
}else {
stack.Remove(stack.Back())
}
}
}
if stack.Len()!=0{
return false
}
return true
}
Merge Two Sorted Lists
题目：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
思路：
- 原理同归并排序递归之后的组合。
解：
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
resRoot := &ListNode{}
cur := resRoot
for l1!=nil&&l2!=nil {
if l1.Val>l2.Val{
cur.Next = &ListNode{Val:l2.Val}
cur = cur.Next
l2 = l2.Next
}else {
cur.Next = &ListNode{Val:l1.Val}
cur = cur.Next
l1 = l1.Next
}
}
if l1!=nil {
cur.Next = l1
}
if l2!=nil{
cur.Next = l2
}
return resRoot.Next
}
Generate Parentheses
题目：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路：
- 求出集合的所有情况，用回溯法（图BFS）。遍历整个结果集，将符合条件的输出。
- 条件为：符号是平衡的。
- 细节：结果集作为递归返回值，同时完成了结果集的添加和清理工作，精简了许多代码。
- 对于结果树的子节点，有如下几种情况：（细节，rPendingAdd的含义）
- 左括号任务和右括号任务，都不可能小于0。
- 都等于0，处理到了叶子结点。
- 有一个不是0就继续递归。
解：
func generateParenthesis(n int) []string {
return addBacktracking("",n,0)
}
func addBacktracking(str string,lPendingAdd,rPendingAdd int) (res []string) {
if lPendingAdd == 0 && rPendingAdd == 0{
return []string{str}
}
if lPendingAdd>0{
res = append(res,addBacktracking(str+"(",lPendingAdd-1,rPendingAdd+1)...)
}
if rPendingAdd>0{
res = append(res,addBacktracking(str+")",lPendingAdd,rPendingAdd-1)...)
}
return
}
Merge k Sorted Lists
题目：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
思路：
- 排序题，用合并两个链表写。或者将所有元素放进一个集合，调用排序算法。
解：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1{
return lists[0]
}
res := lists[0]
for i:=1;i<len(lists);i++{
res = mergeTwoLists(res,lists[i])
}
return res
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
resRoot := &ListNode{}
cur := resRoot
for l1!=nil&&l2!=nil {
if l1.Val>l2.Val{
cur.Next = &ListNode{Val:l2.Val}
cur = cur.Next
l2 = l2.Next
}else {
cur.Next = &ListNode{Val:l1.Val}
cur = cur.Next
l1 = l1.Next
}
}
if l1!=nil {
cur.Next = l1
}
if l2!=nil{
cur.Next = l2
}
return resRoot.Next
}
Longest Valid Parentheses
题目：
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
思路：
- 关键是使用压栈保存左开括号的索引，以便与闭括号弹栈配对后，用栈顶元素算出子串大小，并更新。
- 可以先压一个-1，只是记录起始索引，而不是左括号，代码会很简洁。这里不压，感觉更易懂些。
- go的list类型要当栈取栈顶元素，特别难用。l.Back().Value返回的是一个interface{}。要类型判断。本例就是这么写的，最好改成切片实现栈。
解：
func longestValidParentheses(s string) (maxLen int) {
left := -1
stack := list.New()
for i:=0;i<len(s);i++{
if s[i] == '('{
stack.PushBack(i)
}else {
if stack.Len() == 0{
//有无法配对的括号
left =i
}else {
stack.Remove(stack.Back())
if stack.Len() == 0{
//全部配对
if i-left > maxLen{
maxLen = i- left
}
}else {
//部分配对
var curLen int
switch stackPop := stack.Back().Value.(type) {
case int:
curLen = i-stackPop
default:
}
if curLen > maxLen{
maxLen = curLen
}
}
}
}
}
return
}
Search in Rotated Sorted Array
题目：
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).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路：
- 无重复数组，解决时间O(log n)
- 线性时间也能Accepted，虽然没看懂题。
解：
func search(nums []int, target int) int {
for idx,elem := range nums{
if elem == target {
return idx
}
}
return -1
}
Find First and Last Position of Element in Sorted Array
题目：
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路：
- 用二分查找。
解：
func searchRange(nums []int, target int) []int {
res := make([]int,2)
if len(nums) == 0{
res[0] = -1
res[1] = -1
return res
}
l := 0
r := len(nums)-1
var cur int
oneResCur := -1
for{
if l>r{
break
}
cur = (l+r)/2
if nums[cur] == target{
oneResCur = cur
break
}else if nums[cur] > target{
r = cur-1
}else {
l = cur+1
}
}
if oneResCur == -1{
res[0] = -1
res[1] = -1
return res
}
lIter := oneResCur
rIter := oneResCur
for lIter>0 && nums[lIter-1] == target{
lIter--
}
for rIter<len(nums)-1 && nums[rIter+1] == target {
rIter++
}
res[0] = lIter
res[1] = rIter
return res
}
Search Insert Position
题目：
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
思路：
- 给定无重升序数组。
- 用二分查找写。
解：
func searchInsert(nums []int, target int) int {
l:=0
r:=len(nums)-1
var cur int
pos := -1
for{
if l>r{
break
}
cur = (l+r)/2
if nums[cur] == target{
pos = cur
break
}else if nums[cur] > target{
r = cur-1
}else {
l = cur+1
}
}
if pos!=-1{
return pos
}else if nums[cur]>target{
return cur
}
return cur+1
}
网友评论