Keen的博客

记录所思、所想、所遇

欢迎来到我的个人站~


leetcode算法题

字符串

无重复字符的最长子串

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1012/

解法1:暴力搜索

func inArray(e int32, s []int32) bool {
	for _, v := range s {
		if e == v {
			return true
		}
	}
	return false
}

func isRepeat(s string) bool {
	var tmp []int32
	for _, e := range s {
		if inArray(e, tmp) {
			return true
		} else {
			tmp = append(tmp, e)
		}
	}
	return false
}

func lengthOfLongestSubstring(s string) int {
	lenS := len(s)
	if lenS <= 1 {
		return lenS
	}

	maxLen := 0
	for i:=0; i<lenS; i++ {
		for j:=i+1; j<=lenS; j++ {
			substr := s[i:j]
			if isRepeat(substr) {
				break
			} else {
				subLen := len(substr)
				if subLen > maxLen {
					maxLen = subLen
				}
			}
		}
	}
	return maxLen
}

解法2:移动窗口

func inArrayPos(e int32, s []int32) int {
	for i, v := range s {
		if e == v {
			return i
		}
	}
	return -1
}

func lengthOfLongestSubstring(s string) int {
	maxLen := 0
	var tmp []int32
	j := 0
	for _, e := range s {
		pos := inArrayPos(e, tmp)
		tmp = append(tmp, e)
		if pos != -1 {
			j = pos+1
			// 移动窗口
			tmp = tmp[j:]
		} else {
			subLen := len(tmp)
			if subLen > maxLen {
				maxLen = subLen
			}
		}
	}
	return maxLen
}

最长公共前缀

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1014/

func longestCommonPrefix(strs []string) string {
	strCnt := len(strs)
	if strCnt == 0 {
		return ""
	}
	if strCnt == 1 {
		return strs[0]
	}

	// 计算遍历的最小长度,int默认为64位,可以这样设置成最大值
	// minLen := int(^uint(0)>>1)
	// fmt.Printf("%d", minLen)
	minLen := len(strs[0])
	for _, e := range strs[1:] {
		eLen := len(e)
		if eLen < minLen {
			minLen = eLen
		}
	}
	if minLen == 0 {
		return ""
	}
	for i:=1; i<=minLen; i++ {
		commonPrefix := strs[0][:i]
		for _, e:= range strs {
			if e[:i] != commonPrefix {
				if i == 1 {
					return ""
				}
				return strs[0][:i-1]
			}
		}
	}
	return strs[0][:minLen]
}

字符串的排列

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1016/

func checkInclusion(s1 string, s2 string) bool {
	// 不关心顺序,只关心排列是否命中,则只需要考虑在相同大小窗口内,每个字符的个数相同即可
	lenS1 := len(s1)
	lenS2 := len(s2)
	if lenS1 > lenS2 {
		return false
	}
	// 最终用26个字母的个数来看,c1为s1的26个字母个数情况,c2为s2滑动窗口内26个字母个数情况,只要满足c1=c2,即说明命中
	var c1 [26]int
	for _, v := range s1 {
		c1[v-'a']++
	}
	// lenS2-lenS1+1,为滑动窗口移动次数
	for i:=0; i<lenS2-lenS1+1; i++ {
		var c2 [26]int
		for _, v := range s2[i:i+lenS1] {
			c2[v-'a']++
		}
		if c1 == c2 {
			return true
		}
	}
	return false
}

字符串相乘

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1015/

func multiply(num1 string, num2 string) string {
	len1 := len(num1)
	len2 := len(num2)
	if len1 == 0 || len2 == 0 {
		return ""
	}
	if num1=="0" || num2=="0" {
		return "0"
	}

	result := make([]uint8, len1+len2)
	for i:=0; i<len1; i++ {
		for j:=0; j<len2; j++ {
			now := result[i+j]+(num1[len1-i-1]-'0')*(num2[len2-j-1]-'0')
			// 每计算一次,都即时进位。因为两个位数乘积,最多为2位
			result[i+j] = now%10
			result[i+j+1] = result[i+j+1] + now/10
		}
	}
	out := ""
	for i:=len1+len2-1; i>=0; i-- {
		if out != "" || result[i] != 0 {
			out = out + string(result[i]+'0')
		}
	}
	return out
}

翻转字符串里的单词

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1011/

func reverseWords(s string) string {
	wordEnd := len(s)-1
	word := ""
	for i:=len(s)-1; i>=0; i-- {
		if s[i] == ' ' {
			// 说明i到wordEnd为一个单词。如果i==wordEnd,说明wordEnd定位不准
			if i == wordEnd {
				wordEnd = i-1
			} else {
				if word == "" {
					word = s[i+1:wordEnd+1]
				} else {
					word = word + " " + s[i+1:wordEnd+1]
				}
				wordEnd = i - 1
			}
		} else if i == 0 {
			if word == "" {
				word = s[i:wordEnd+1]
			} else {
				word = word + " " + s[i:wordEnd+1]
			}
		}
	}
	return word
}

简化路径

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1013/

func simplifyPath(path string) string {
    // 如果最后位置没有/,添加一个
	if path[len(path)-1] != '/' {
		path += "/"
	}

	stack := []string{}
	j := 1
	subPath := ""
	for i:=1; i<len(path); i++ {
		if path[i] == '/' {
			if i == j {
				j += 1
			} else {
				subPath = path[j:i]
				if subPath == "." {
					// 当前路径,则什么都不变
				} else if subPath == ".." {
					// 上一层路径
					if len(stack) > 0 {
						stack = stack[0:len(stack)-1]
					}
				} else {
					stack = append(stack, subPath)
				}
				j = i+1
			}
		}
	}

	outPath := ""
	if len(stack) == 0 {
		outPath = "/"
	} else {
		for _, v := range stack {
			outPath += "/" + v
		}
	}
	return outPath
}

复原IP地址

题目:https://leetcode-cn.com/explore/featured/card/bytedance/242/string/1044/

import "strconv"

func restoreIpAddresses(s string) []string {
	out := []string{}
	lenS := len(s)
	tmp := make(map[string]bool)
	for i:=1; i<=3 && i<=lenS-3; i++ {
		if i==1 || (i>1 && s[0]!='0') {
			for j:=1; j<=3 && j<=lenS-2-i; j++ {
				if j==1 || (j>1 && s[i]!='0') {
					for k:=1; k<=3 && k<=lenS-1-i-j; k++ {
						if k==1 || (k>1 && s[i+j]!='0') {
							l := lenS-i-j-k
							if l==1 || (l>1 && s[i+j+k]!='0') {
								ip1, _ := strconv.Atoi(s[0:i])
								ip2, _ := strconv.Atoi(s[i:i+j])
								ip3, _ := strconv.Atoi(s[i+j:i+j+k])
								ip4, _ := strconv.Atoi(s[i+j+k:])
								if ip1<256 && ip2<256 && ip3<256 && ip4<256 {
									ip := s[0:i]+"."+s[i:i+j]+"."+s[i+j:i+j+k]+"."+s[i+j+k:]
									if _, ok := tmp[ip]; ok {
										//存在
									} else {
										out = append(out, ip)
										tmp[ip]=true
									}
								}
							}
						}
					}
				}
			}
		}
	}
	return out
}

数组与排序

三数之和

题目:https://leetcode-cn.com/explore/featured/card/bytedance/243/array-and-sorting/1020/

import "sort"

func threeSum(nums []int) [][]int {
	var outs[][]int
	// 超出时间限制,所以需要先排序,从中挑出负数、正数
	sort.Ints(nums)
	lenN := len(nums)
	for i:=0; i<lenN; i++ {
		if i>0 && nums[i]==nums[i-1] {
			continue
		}
		j := i+1
		k := lenN-1
		for ; j < k; {
			sum := nums[i]+nums[j]+nums[k]
			if sum==0 {
				out := []int{nums[i], nums[j], nums[k]}
				outs = append(outs, out)
				// 此时,应该j和k同时变化,寻中下一批值
				j += 1
				// 找不重复的值
				for ; j<k && nums[j]==nums[j-1]; {
					j += 1
				}
				k -= 1
				for ; j<k && nums[k]==nums[k+1]; {
					k -= 1
				}
			} else if sum>0 {
				// 此时,说明k的值偏大,需要小一点
				k -= 1
				for ; j<k && nums[k]==nums[k+1]; {
					k -= 1
				}
			} else {
				// 此时,说明j的值偏小,需要大一点
				j += 1
				for ; j<k && nums[j]==nums[j-1]; {
					j += 1
				}
			}
		}
	}
	return outs
}

岛屿最大面积

题目:https://leetcode-cn.com/explore/featured/card/bytedance/243/array-and-sorting/1034/

解法1:深度优先搜索遍历 - 递归

func dfs(x, y int, grid [][]int) int {
	if grid[x][y] == 0 {
		return 0
	}

	area := 1
	grid[x][y] = 0
	// 深度递归遍历每一个兄弟节点
	if x > 0 {
		area += dfs(x-1, y, grid)
	}
	if x < len(grid)-1 {
		area += dfs(x+1, y, grid)
	}
	if y > 0 {
		area += dfs(x, y-1, grid)
	}
	if y < len(grid[0])-1 {
		area += dfs(x, y+1, grid)
	}
	return area
}

func maxAreaOfIsland(grid [][]int) int {
	maxArea := 0
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[i]); j++ {
			area := dfs(i, j, grid)
			if area > maxArea {
				maxArea = area
			}
		}
	}
	return maxArea
}

解法2:深度优先搜索遍历 - 栈

var stack [][2]int

func dfs(x, y int, grid [][]int) int {
	if grid[x][y]==0 {
		return 0
	}

	area := 1
	grid[x][y]=0
	// 将兄弟节点入栈
	if x > 0 {
		stack = append(stack, [2]int{x-1,y})
	}
	if x < len(grid)-1 {
		stack = append(stack, [2]int{x+1,y})
	}
	if y > 0 {
		stack = append(stack, [2]int{x,y-1})
	}
	if y < len(grid[0])-1 {
		stack = append(stack, [2]int{x,y+1})
	}

	for ; len(stack)!=0; {
		x1 := stack[len(stack)-1][0]
		y1 := stack[len(stack)-1][1]
		stack = stack[0:len(stack)-1]
		area += dfs1(x1, y1, grid)
	}
	return area
}
func maxAreaOfIsland(grid [][]int) int {
	maxArea := 0
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[i]); j++ {
			area := dfs(i, j, grid)
			if area > maxArea {
				maxArea = area
			}
		}
	}
	return maxArea
}

解法3:广度优先搜索遍历 - 队列

var array [][2]int

func bfs(x, y int, grid [][]int) int {
	if grid[x][y]==0 {
		return 0
	}

	area := 1
	grid[x][y]=0
	// 将每一个兄弟节点,放入队列中
	if x > 0 {
		array = append(array, [2]int{x-1, y})
	}
	if x < len(grid)-1 {
		array = append(array, [2]int{x+1, y})
	}
	if y > 0 {
		array = append(array, [2]int{x, y-1})
	}
	if y < len(grid[0])-1 {
		array = append(array, [2]int{x, y+1})
	}

	// 始终取出第一个节点,继续进行遍历,直到耗尽array数组,也即把兄弟节点都遍历完,就继续下一轮都遍历
	for ;len(array)!=0; {
		x1 := array[0][0]
		y1 := array[0][1]
		array = array[1:]
		area += bfs(x1, y1, grid)
	}

	return area
}
func maxAreaOfIsland(grid [][]int) int {
	maxArea := 0
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[i]); j++ {
			area := bfs(i, j, grid)
			if area > maxArea {
				maxArea = area
			}
		}
	}
	return maxArea
}

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少