算法

基于udp+http协议，在upnp中被使用到

面试流利说遇到了，做得磕磕绊绊

双向队列，跳表等

挺恶心的位运行

写在字节4面后

200. 岛屿数量 200. 岛屿数量 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 func numIslands(grid [][]byte) int { m, n := len(grid), len(grid[0]) bfs := func(i, j int) { // 从[i, j]位置开始扩散 q := [][]int{{i, j}} for len(q) != 0 { e := q[0] q = q[1:] x, y := e[0], e[1] if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' { grid[x][y] = '0' q = append(q, []int{x+1, y}) q = append(q, []int{x-1, y}) q = append(q, []int{x, y+1}) q = append(q, []int{x, y-1}) } } } cnt := 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '0' { continue } bfs(i, j) // 为什么找到了一块陆地就可以增加一个岛屿数呢， // 是因为在bfs方法中会将跟这块陆地相连的其他陆地染色，不会再次重复计算 cnt++ } } return cnt } 301....

22. 括号生成 22. 括号生成 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 func generateParenthesis(n int) []string { ans := []string{} var dfs func(lb, rb int, s string) dfs = func(lb, rb int, s string) { if lb > rb { return } if lb == 0 && rb == 0 { // 括号用完了，并且是合法的 if isValid(s) { ans = append(ans, s) } return } if lb != 0 { dfs(lb - 1, rb, s + "(") } if rb !...

hash表也算是刷题中的老常客了

经典面试题了属实是

通常可以使用堆来解决topK的问题

子串和子序列是一块难啃的骨头，但大多数时候可以通过动态规划来解决

461. 汉明距离 461. 汉明距离 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y，计算并返回它们之间的汉明距离。 func hammingDistance(x int, y int) int { s := x ^ y // 汉明距离即为s中1的数量 res := 0 for s > 0 { // 判断最低位是不是1 res += s & 1 s >>= 1 } return res } 397. 整数替换 397. 整数替换 给定一个正整数 n ，你可以做如下操作： 如果 n 是偶数，则用 n / 2替换 n 。 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。 返回 n 变为 1 所需的 最小替换次数 。...

前缀和也是常见的数组题的解法了吧

55. 跳跃游戏 55. 跳跃游戏 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 func canJump(nums []int) bool { l := len(nums) if l == 0 || l == 1 { return true } // 表示能不能到达第i位下标，true代表可以，false代表不可以 d := make([]bool, l) d[0] = true for i := 1; i < l; i++ { for j := i - 1; j >= 0; j-- { // 能找到一个j就好了 d[i] = d[j] && (j + nums[j]) >= i if d[i] { break } } if !...

子串和子序列是一块难啃的骨头，但大多数时候可以通过动态规划来解决

19. 删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 func removeNthFromEnd(head *ListNode, n int) *ListNode { // 快慢指针 dummy := &ListNode{} dummy.Next = head s, f := dummy, dummy // faster向前走n+1步，一会可以让slow停在想要删除的节点的前继节点上 for n >= 0 && f != nil { f = f.Next n-- } for f != nil { f = f.Next s = s.Next } s.Next = s.Next.Next return dummy.Next }

207. 课程表 207. 课程表 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 func canFinish(numCourses int, prerequisites [][]int) bool { // 入度 indeg := make([]int, numCourses) // 邻接表 g := make(map[int][]int) for _, q := range prerequisites { indeg[q[0]]++ g[q[1]] = append(g[q[1]], q[0]) } q := make([]int, 0, numCourses) // 无入度节点入队 for i := range indeg { if indeg[i] == 0 { q = append(q, i) } } resCount := 0 for len(q) > 0 { head := q[0] q = q[1:] resCount++ for _, i := range g[head] { indeg[i]-- if indeg[i] == 0 { q = append(q, i) } } } return resCount == numCourses }

20. 有效的括号 给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 function isValid(s: string): boolean { let stack = [] for (let c of s) { if (c == '(' || c == '{' || c == '[') { stack.push(c) } if (c == ')' || c == '}' || c == ']') { let e = stack.pop() if (c != rightof(e)) { return false } } } if (stack.length > 0) { return false } return true }; function rightof(c: string): string { if (c == "{") { return "}" } if (c == "[") { return "]" } if (c == "(") { return ")" } return "" }

与数组相关的算法题可以又各种骚操作

LR两指针