- 博客(24)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 number of islands
题目链接：https://leetcode.com/problems/number-of-islands/这是一道很经典的题，shopee也有考过。最常见的解法是DFS：本文要探讨的是它的第二种解法，基于并查集的。并查集的方法一旦掌握，就可以用于解决很多类似的问题。题目链接：https://www.lintcode.com/problem/434参考资料https://leetcode.com/problems/number-of-islands/discuss/56359/Very-conci
2022-06-12 16:55:07
121
原创 二分查找相关
文章目录最普通的find left most吃香蕉参考资料二分查找虽然简单，但是想做到bug free还是很难的。最普通的func search(nums []int, target int) int { low := 0 high := len(nums)-1 for low <= high { mid := low + (high - low) / 2 if nums[mid] == target { return mid } else if nums[mid]
2022-05-29 17:31:56
65
原创 booking——all_anagram_groups
题目Implement a function all_anagram_groups() that, given many input strings, will identify and group words that are anagrams of each other.An anagram is word that is just a re-arrangement of the characters of another word,like "reap" and "pear" and "a
2022-05-28 15:46:04
58
原创 booking——top score hotel
题目：Given a list of hotelId, parentHotelId and a scoreretrieve the top k root parentHotelIds with highest scoresInput: [{0, 1, 10}, {1, 2, 20}, {3, 4, 10}, {7, 8, 5}] K = 2Output: [[2, 30], [4,10]]我的解法如下：type Hotel struct { ID int Score int Paren
2022-05-28 12:20:38
121
原创 终于搞懂Dijkstra算法了
文章目录示例1示例2参考资料Dijkstra算法用来解决单源最短路径问题，思路如下将图中顶点分为2部分S：已经找到最短路径的顶点U：剩下的顶点假设初始顶点为v0， 那么S：{v0}， U：{剩下的顶点}从U中找到一个距离v0最近的一个顶点，假设为x，将x从U中移动到S。对于U中的任意顶点y，如果d[v0][x] + d[x][y] < d[v0][y]， 则d[v0][y] = d[v0][x] + d[x][y]。如此循环，直到处理完U中所有顶点。Dijkstra是按照路径长度递增
2022-05-04 15:47:10
994
原创 backtrack——组合问题
面试中遇到的一个问题// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。// 给出数字到字母的映射如下// "2": {"a", "b", "c"},// "3": {"d", "e", "f"},// "4": {"g", "h", "i"},// "5": {"j", "k", "l"},// "6": {"m", "n", "o"},// "7": {"p", "q", "r", "s"},// "8": {"t", "u", "v"},// "9": {"w"
2022-05-03 20:30:20
293
原创 Path Sum问题
文章目录Path SumPath Sum IIPath Sum III本文对PathSum类的问题，进行一个总结Path Sum链接：https://leetcode.com/problems/path-sum/这个直接看代码就好func hasPathSum(root *TreeNode, targetSum int) bool { if root == nil { return false } if root.Left == nil && root.Right
2022-02-20 17:07:40
256
原创 Trapping Rain Water
题目链接：https://leetcode.com/problems/trapping-rain-water/这是一道非常经典的面试题，虽然没有在面试中遇到，但是在很多面经中都看到过。乍一看很难有思路，思考之后，我先想出了基于面积的解法，结果运行超时了。再进一步思考，才成功AC。一个hint：计算每个柱子能接多少雨水。func trap(height []int) int { // find max max := math.MinInt32 maxIndex := 0 for i := 0
2022-02-12 22:17:43
513
原创 非递归遍历二叉树
文章目录preOrderinOrderpostOrder参考资料这是一个老话题了，这里仅仅做个记录。preOrderfunc preorderTraversal(root *TreeNode) []int { if root == nil { return nil } var res []int sk := &Stack{} sk.Push(root) for !sk.Empty() { top := sk.Pop() res = append(res, top.Val
2022-02-12 13:00:56
235
原创 House Robber的解法
题目链接：https://leetcode.com/problems/house-robber/答案自然是动态规划(Dynamic programming，简称DP)。代码func rob1(nums []int) int { lth := len(nums) if lth == 0 { return 0 } dp := make([]int, lth+1) dp[1] = nums[0] for i := 2; i < lth+1; i++ { dp[i] = int(ma
2022-02-08 22:46:21
221
原创 backtracking及其应用2
文章目录Subsets接上文：backtracking及其应用Subsets链接：https://leetcode.com/problems/subsets/如果没有接触过backtracking，这道题的常规解法应该是位操作func subsets(nums []int) [][]int { lth := len(nums) cnt := int(math.Pow(float64(2), float64(lth))) bits := getBits(cnt, lth) var res [
2022-01-26 11:41:26
670
原创 backtracking及其应用
文章目录应用场景八皇后问题数组的排列组合参考资料backtracking(回溯法)是一种算法，主要用来解决带限制条件的计算问题(CSP)。特点如下：和暴力匹配算法一样，会尝试所有的可能性。比暴力匹配算法好，会在尝试的过程中不断丢弃不正确的解。应用场景八皇后问题链接：https://leetcode.com/problems/n-queens/代码func solveNQueens(n int) [][]string { board := make([][]int, n) for i
2022-01-25 17:40:57
407
原创 golang中的slice
文章目录实现部分append部分使用部分引用的坑示例代码输出nil slice参考资料slice简单来说就是一个动态数组。但是有几个细节需要注意。实现部分append部分使用部分引用的坑示例代码package mainimport "fmt"func main() { s := []int{1,2,3,4,5} fmt.Printf("s: %v, len: %v, cap: %v\n", s, len(s), cap(s)) s1 := s[:2] fmt.Print
2022-01-24 12:37:40
271
原创 Copy List with Random Pointer
题目链接：https://leetcode.com/problems/copy-list-with-random-pointer/这道题目比较经典，头条等多个大厂都考过，《剑指offer》中也有。基础解法创建新链表，先拷贝基础信息，再拷贝random指针。func copyRandomList(head *Node) *Node { p := head var dummyHead Node pHead := &dummyHead // 存储新旧节点的映射 mp := make
2022-01-23 13:39:08
169
原创 golang实现stack
文章目录方案1：使用slice方案2：使用container.list应用场景参考资料golang没有提供stack的实现，只能自己搞一把了。方案1：使用slicetype IntStack struct { list []int}func (s *IntStack) Empty() bool { return len(s.list) == 0}func (s *IntStack) Push(item int) { s.list = append(s.list, item)}
2022-01-20 17:09:39
655
原创 Permutation in String
题目链接：https://leetcode.com/problems/permutation-in-string/给定字符串s1、s2，判断s2中是否存在一个子串，是s1的一个组合。提到字符串的组合，首先想到的就是map，key是字符，value是字符出现的次数。问题就转为在s2中寻找一个子串对应这个map。这是一种解题思路，但是代码会有点复杂。这里给出一个更简单的思路。首先，满足条件的子串，它的长度和s1一定是一样的。其次，就用上了抵消的思想。这个子串和s1是可以相互抵消的。看下代码f
2021-11-10 21:10:48
215
原创 Longest Substring Without Repeating Characters
题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/给定一个字符串s，计算不包含重复字符的最长子串的长度。一看到这种contiguous subarray问题，肯定是用滑动窗口了。直接上代码func lengthOfLongestSubstring(s string) int { lth := len(s) // key: s[i], value: i mp := make(map[
2021-10-23 13:11:00
50
原创 Sum of All Odd Length Subarrays
题目链接：https://leetcode.com/problems/sum-of-all-odd-length-subarrays/要求：计算所有奇数长度的子数组的和。提到子数组，自然先想到前缀和。尝试用前缀和来解答。数组记做A，长度为n，假设子数组长度为i(i=1、3、5、…)，则每个子数组的和就是A[0] + A[1] + … + A[i-1]A[1] + A[2] + … + A[i]…A[n-i] + A[n-i+1] + … + A[n-1]前缀和数组记做S，上述算式可以演
2021-10-16 21:47:59
164
原创 Subarray Sum Equals K
文章目录背景two-sumrunning-sum-of-1d-array解题思路参考资料背景题目链接：https://leetcode.com/problems/subarray-sum-equals-k/要求就是：找出 sum = k 的子数组的个数。在看这道题之前，先看两道简单的：https://leetcode.com/problems/two-sum/https://leetcode.com/problems/running-sum-of-1d-array/two-sum刷LeetC
2021-10-10 21:41:23
138
3
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人