字符串
无重复字符的最长子串
题目：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
}
