LeetCode 2 3 4 5 6 8 10 11 12 15

发表信息: July 12, 2019 by gc

文章分类:
LeetCode 6

2 Add Two Numbers
3 无重复字符的最长子串
4 寻找两个有序数组的中位数
5 最长回文子串
6 Z字形转换
8 字符转换成数字
10 正则表达式匹配
11 盛最多水的容器
12 整数转罗马数字
15 三数之和

2 Add Two Numbers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */


func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	return addTwoNumbersWithCarry(l1, l2, 0);
}

func addTwoNumbersWithCarry(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
	if (*l1).Next == nil && (*l2).Next == nil {
		sumBit := (*l1).Val + (*l2).Val + carry
		if sumBit > 9 {
			return &ListNode{sumBit % 10, addTwoNumbersWithCarry(&ListNode{0, nil}, &ListNode{0, nil}, 1)}
		}
		return &ListNode{sumBit, nil}
	}

	if (*l1).Next == nil {
		(*l1).Next = &ListNode{0, nil}
	}

	if (*l2).Next == nil {
		(*l2).Next = &ListNode{0, nil}
	}

	sumBit := (*l1).Val + (*l2).Val + carry
	if sumBit > 9 {
		return &ListNode{sumBit % 10, addTwoNumbersWithCarry((*l1).Next, (*l2).Next, 1)}
	} else {
		return &ListNode{sumBit, addTwoNumbersWithCarry((*l1).Next, (*l2).Next, 0)}
	}
}

这个题挺有意思的，要正向着去算，而不是递归逆向着来

3 无重复字符的最长子串

package prob

import "fmt"

type Set struct {
	m map[interface{}]int
}

func (s *Set) contain(i interface{}) bool {
	if _, ok := s.m[i]; ok {
		return true
	}

	return false
}

func (s *Set) add(i interface{}) bool {
	if (*s).m == nil {
		(*s).m = map[interface{}]int{}
	}

	if _, ok := s.m[i]; ok {
		return false
	}

	s.m[i] = 1

	return true
}

func (s *Set) clear() {
	(*s).m = map[interface{}]int{}
}

func (s *Set) size() int {
	return len((*s).m)
}

func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}

	maxLength := 0

	for i := 0; i < len(s); i++ {
		set := Set{}
		nowLength := 0
		for j := i; j < len(s); j++ {
			if set.contain(s[j]) {
				break
			}

			set.add(s[j])
			nowLength++

			if nowLength > maxLength {
				maxLength = nowLength
			}
		}
	}

	return maxLength
}

func Test3() {
	c := lengthOfLongestSubstring("avabc")

	fmt.Println(c)
}

这个题提交了四次，踩了几个坑 avabc和时间的坑，想了三个思路，第一个是abcab遇到与之前重复就清零, 第二个是0:av-1, 1:vabc, 2:abc, 3:bc, 4:c 但是时间没过去，on的复杂度, 第三个就是上面的代码，回溯法，遇到重复的就回溯

4 寻找两个有序数组的中位数

func sumAndFind(nums1 []int, nums2 []int) float64 {
	sum := make([]int, 0)
	if len(nums1) == 0 {
		sum = nums2
	} else if len(nums2) == 0 {
		sum = nums1
	} else {
		i, j := 0, 0
		for {
			if i == len(nums1) && j == len(nums2) {
				break
			}

			if i == len(nums1) {
				sum = append(sum, nums2[j])
				j++
			} else if j == len(nums2) {
				sum = append(sum, nums1[i])
				i++
			} else {
				if nums1[i] >= nums2[j] {
					sum = append(sum, nums2[j])
					j++
				} else {
					sum = append(sum, nums1[i])
					i++
				}
			}
		}
	}

	if len(sum)%2 == 0 {
		return float64(sum[len(sum)/2]+sum[len(sum)/2-1]) / 2.0
	} else {
		return float64(sum[len(sum)/2])
	}
}

func dichotomizeAndFind(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}

	sumLength := len(nums1) + len(nums2)
	for i, _ := range nums1 {
		j := sumLength / 2
		if nums2[j] > nums1[i] {
			continue
		}

		if sumLength%2 == 1 {
			return float64(nums2[j+1])
		} else {
			return (math.Max(float64(nums1[i]), float64(nums2[j])) + math.Min(float64(nums1[i+1]), float64(nums2[i+1]))) / 2.0
		}
	}

	return 0.0
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	result := sumAndFind(nums1, nums2)
	//if len(nums1) == 0 || len(nums2) == 0 || nums1[len(nums1)-1] <= nums2[0] || nums2[len(nums2)-1] <= nums1[0] {
	//	result = sumAndFind(nums1, nums2)
	//} else {
	//	result = dichotomizeAndFind(nums1, nums2)
	//}

	return result
}

这个lg(m+n) 复杂度的算法我是真的不会，看题解也没看懂，所以写了个on的

5 最长回文子串

func longestPalindrome(s string) string {
	sl := len(s)
	if sl <= 1 {
		return s
	}

	status := make([][]int, sl)
	for i, _ := range status {
		status[i] = make([]int, sl)
	}

	for i := 0; i < sl; i++ {
		for j := i; j < sl; j++ {
			fullStatus(&status, s, i, j)
		}
	}

	return findMaxStr(status, s)
}

func findMaxStr(status [][]int, s string) string {
	maxC := 0
	maxS := ""
	for i := 0; i < len(status); i++ {
		for j := i; j < len(status[i]); j++ {
			if status[i][j] == 1 && j-i+1 > maxC {
				maxC = j - i + 1
				maxS = s[i : j+1]
			}
		}
	}

	return maxS
}

func fullStatus(status *[][]int, s string, i int, j int) {
	if (*status)[i][j] > 0 {
		return
	}

	if j-i == 0 {
		(*status)[i][j] = 1
		return
	}

	if j-i == 1 {
		if s[i] == s[j] {
			(*status)[i][j] = 1
		} else {
			(*status)[i][j] = 2
		}

		return
	}

	fullStatus(status, s, i+1, j-1)
	if (*status)[i+1][j-1] == 1 && s[i] == s[j] {
		(*status)[i][j] = 1
	} else {
		(*status)[i][j] = 2
	}

	return
}

这个用动态规划定义状态和状态转移

6 Z字形转换

func convert(s string, numRows int) string {
	if numRows <= 1 {
		return s;
	}
	
	board := make([][]string, numRows)
	for i, _ := range board {
		board[i] = make([]string, len(s))
	}

	i, j := 0, 0
	down := true
	for _, c := range s {
		board[i][j] = string(c)

		if i < numRows-1 && down {
			i++
		} else if i > 0 {
			down = false
			j++
			i--
		} else {
			down = true
			i++
		}
	}

	result := ""
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if len(board[i][j]) > 0 {
				result += board[i][j]
			}
		}
	}
	return result
}

8 字符转换成数字

func myAtoi(str string) int {
	r := 0
	PNFlag := 0
	SNFlag := 0
	ENFlag := 0
	OverPIntFlag := 0
	OverNIntFlag := 0

	for _, c := range str {
		if c == 43 && PNFlag == 0 && SNFlag == 0 {
			PNFlag = 1
			continue
		}

		if c == 45 && PNFlag == 0  && SNFlag == 0{
			PNFlag = 2
			continue
		}

		if c == 32 && PNFlag == 0 && SNFlag == 0 {
			continue
		}

		if c >= 48 && c <= 57 {
			if SNFlag == 0 && ENFlag == 0 {
				SNFlag = 1
			}

			if ENFlag == 1 {
				continue
			}

			r = r*10 + int(c-48)
			if PNFlag <= 1 && r > math.MaxInt32 {
				OverPIntFlag = 1
				break
			}

			if PNFlag > 1 && -r < math.MinInt32 {
				OverNIntFlag = 1
				break
			}

		} else if ENFlag == 0 {
			ENFlag = 1
		}

		if SNFlag == 0 && c != 43 && c != 45 {
			break
		}
	}

	if PNFlag > 1 {
		r = -r
	}

	if OverPIntFlag == 1 {
		return math.MaxInt32
	}

	if OverNIntFlag == 1 {
		return math.MinInt32
	}

	return r
}

这个我想复杂了，下面代码更简洁 max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

10 正则表达式匹配

func isMatch(s string, p string) bool {
	if len(p) == 0 {
		return len(s) == 0
	}

	firstMatch := len(s) != 0 && (s[0] == p[0] || string(p[0]) == ".")
	if len(p) >= 2 && string(p[1]) == "*" {
		return isMatch(s, p[2:]) || (firstMatch && isMatch(s[1:], p))
	} else {
		return firstMatch && isMatch(s[1:], p[1:])
	}
}

这个题我提交了9次，主要是出现*时候的判断，把*出现分成两种，一种是没有发挥作用，也就是代表0，一种是发挥一次作用，代表1 然后继续迭代

11 盛最多水的容器

func maxArea(height []int) int {
	maxC := 0.0
	for i := 0; i < len(height); i++ {
		for j := i; j < len(height); j++ {
			area := float64(j-i) * math.Min(float64(height[i]), float64(height[j]))
			if area > maxC {
				maxC = area
			}
		}
	}

	return int(maxC)
}

func maxArea2(height []int) int {
	maxC := 0.0
	i := 0
	j := len(height) - 1
	for {
		if i >= j {
			break
		}
		area := float64(j-i) * math.Min(float64(height[i]), float64(height[j]))
		if area > maxC {
			maxC = area
		}

		if height[i] >= height[j] {
			j--
		} else {
			i++
		}
	}
	return int(maxC)
}

一个o n2 一个 o n

12 整数转罗马数字

var numPool = map[int]string{
	1:    "I",
	2:    "II",
	3:    "III",
	4:    "IV",
	5:    "V",
	6:    "VI",
	7:    "VII",
	8:    "VIII",
	9:    "IX",
	10:   "X",
	20:   "XX",
	30:   "XXX",
	40:   "XL",
	50:   "L",
	60:   "LX",
	70:   "LXX",
	80:   "LXXX",
	90:   "XC",
	100:  "C",
	200:  "CC",
	300:  "CCC",
	400:  "CD",
	500:  "D",
	600:  "DC",
	700:  "DCC",
	800:  "DCCC",
	900:  "CM",
	1000: "M",
	2000: "MM",
	3000: "MMM",
}

func intToRoman(num int) string {
	result := ""

	result += numPool[num/1000*1000]
	num = num % 1000
	result += numPool[num/100*100]
	num = num % 100
	result += numPool[num/10*10]
	num = num % 10
	result += numPool[num]

	return result
}

哈哈哈暴力不

15 三数之和

func threeSum(nums []int) [][]int {
	result := make([][]int, 0)
	sort.Ints(nums)

	numFlag := map[int]int{}
	for i, v := range nums {
		numFlag[v] = i
	}

	if len(nums) >= 3 && len(numFlag) == 1 && nums[0] == 0 {
		result = append(result, []int{0, 0, 0})
		return result
	}

	fmt.Println(nums)

	complectFlag := map[string]int{}

	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if c, ok := numFlag[0-nums[i]-nums[j]]; ok && c > j {
				key := fmt.Sprintf("%d_%d_%d", nums[i], nums[j], 0-nums[i]-nums[j])
				if _, ok := complectFlag[key]; ok {
					continue
				} else {
					result = append(result, []int{nums[i], nums[j], 0 - nums[i] - nums[j]})
					complectFlag[key] = 1
				}
			}
			//for z := j + 1; z < len(nums); z++ {
			//	if nums[i]+nums[j]+nums[z] == 0 {
			//		key := fmt.Sprintf("%d_%d_%d", nums[i], nums[j], nums[z])
			//		if _, ok := complectFlag[key]; ok {
			//			continue
			//		} else {
			//			result = append(result, []int{nums[i], nums[j], nums[z]})
			//			complectFlag[key] = 1
			//		}
			//
			//	}
			//}
		}
	}

	return result
}

注释了三层循环的代码， 0n2其实有个case leetcode超时，就是全都是0，所以做了特殊的处理