Posts

算法-topK

通常可以使用堆来解决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两指针

算法-链表

2. 两数相加 2. 两数相加给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 206. 反转链表 206. 反转链表给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 func reverseList(head *ListNode) *ListNode { // 双指针，pre和curr一前一后 var pre *ListNode curr := head for curr != nil { tmp := curr.Next curr.Next = pre pre = curr curr = tmp } return pre } func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } nhead := reverseList(head....