文章 212
评论 0
浏览 119901
Tree - 450. Delete Node in a BST

Tree - 450. Delete Node in a BST

450. Delete Node in a BST Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node. Note: Time complexity should be O(height of tree). Example: root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and de....

Tree - 145. Binary Tree Postorder Traversal

Tree - 145. Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [3,2,1] Follow up: Recursive solution is trivial, could you do it iteratively? 思路: 二叉树后序遍历,递归和迭代来做,迭代也是使用list容器来充当栈,后序遍历和前序后序遍历主要特点在于父节点会被访问两次,所以使用一个辅助指针preVisited来记录是否是第二次访问这个节点。 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /* ....

Tree - 94. Binary Tree Inorder Traversal

Tree - 94. Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 思路: 二叉树的中序遍历,先访问左子树然后中间节点然后右子树。迭代也是使用list容器来充当栈 代码: go : /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // recursive /*func inorderTraversal(root *TreeNode) []int { var res [....

Tree - 144. Binary Tree Preorder Traversal

Tree - 144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Follow up: Recursive solution is trivial, could you do it iteratively? 思路: 二叉树的先序遍历,递归求解和迭代,迭代使用list容器的链表代替栈来做 代码: go: /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // recursive /*func preorderTraversal(root *TreeNode) []int { var ....

Array - 42. Trapping Rain Water Hard

Array - 42. Trapping Rain Water Hard

42. Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 思路: 题目意思是给定一个数组,数值代表了高度,求解可以装多少水,仔细分析可以发现,对于任意一位能存储多少水是取....

Tree - 687. Longest Univalue Path

Tree - 687. Longest Univalue Path

687. Longest Univalue Path Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. The length of path between two nodes is represented by the number of edges between them.   Example 1: Input: 5 / \ 4 5 / \ \ 1 1 5 Output: 2   Example 2: Input: 1 / \ 4 5 / \ \ 4 4 5 Output: 2   Note: The given binary tree has not more than 10000 nodes. The height of the tree is n....

DFS - 980. Unique Paths III

DFS - 980. Unique Paths III

980. Unique Paths III On a 2-dimensional grid, there are 4 types of squares: 1 represents the starting square.  There is exactly one starting square. 2 represents the ending square.  There is exactly one ending square. 0 represents empty squares we can walk over. -1 represents obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square ....

Dynamic Programming - 375. Guess Number Higher or Lower II

Dynamic Programming - 375. Guess Number Higher or Lower II

375. Guess Number Higher or Lower II We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower. However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked. Example: n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay ....

grpc调用主要流程分析(一)

grpc调用主要流程分析(一)

grpc调用主要流程分析 客户端 0. 客户端调用 以github官网上的example为例跟踪调用的逻辑,总的调用过程基本就是分为三步: 创建connection 创建业务客户端实例 调用rpc接口 { ... // 创建connection conn, err := grpc.Dial(address, grpc.WithInsecure()) if err != nil { log.Fatalf("did not connect: %v", err) } defer conn.Close() // 创建client c := pb.NewGreeterClient(conn) // 调用RPC接口 name := defaultName r, err := c.SayHello(context.TODO(), &pb.HelloRequest{Name: name}) if err != nil { log.Fatalf("could not greet: %v", err) } ... } 1. 创建connection 通过grpc.Dial()接口创建了一个C....

DFS&BFS - 52. N-Queens II

DFS&BFS - 52. N-Queens II

52. N-Queens II The n-queens puzzle is the problem of placing n queens on an n_×_n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. Example: Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [  [".Q..",  // Solution 1   "...Q",   "Q...",   "..Q."],  ["..Q.",  // Solution 2 &n....

go语言的原生map引发的一个坑

go语言的原生map引发的一个坑

go语言原生map引发的一个坑 总所周知,go语言原生的map并不是并发安全的,所以为了保证map的并发安全,最简单的方式就是给map加一个锁。 年初写项目的时候,刚接触go语言,冒冒失失的就写出了类似下面这样的代码: package problem import (     "fmt"     "sync" ) type dict struct {     m    map[int]string     lock sync.RWMutex } func NewDict() *dict {     return &dict{m: map[int]string{}} } func (d dict) Set(....

Design - 460. LFU Cache

Design - 460. LFU Cache

460. LFU Cache Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. F....

Binary Search - 33. Search in Rotated Sorted Array

Binary Search - 33. Search in Rotated Sorted Array

33. Search in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: ....

Binary Search - 35. Search Insert Position

Binary Search - 35. Search Insert Position

35. Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 思路: 题目意思是给定一个有序数组,和一个target,找出target在数组中的下标,或者应该插入的位置。使用binary search来做。 代码: go: func searchInsert(n....

Binary Search - 278. First Bad Version

Binary Search - 278. First Bad Version

278. First Bad Version You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(vers....

Design - 381. Insert Delete GetRandom O(1) - Duplicates allowed

Design - 381. Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed. insert(val): Inserts an item val to the collection. remove(val): Removes an item val from the collection if present. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the co....

Design - 380. Insert Delete GetRandom O(1)

Design - 380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1) Design a data structure that supports all following operations in average O(1) time. insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned. Example: // Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to ....

DFS&BFS - 51. N-Queens

DFS&BFS - 51. N-Queens

51. N-Queens The n-queens puzzle is the problem of placing n queens on an n_×_n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively. Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q....

maze - dfs

maze - dfs

走迷宫可以用dfs或者dfs来做,当求最小路径的时候用bfs最方便。这里使用bfs来找迷宫的最短路径。做法就是先用bfs记录走到终点的过程中每一格的步数,这样从终点往回走就能走到最小路径。 输入的迷宫文件maze_file.in,0代表可以走的路: 6 5 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 代码: go: package main import ( "fmt" "os" ) type point struct { i, j int val int } func (p point) add(next point) point { return point{i: p.i + next.i, j: p.j + next.j} } // 判断点是否出界 func (p point) at(grid [][]int) (int, bool) { if p.i < 0 || p.i >= len(grid) || p.j < 0 || p.j >= len(grid[0]) { retu....

DFS&BFS - 130. Surrounded Regions

DFS&BFS - 130. Surrounded Regions

130. Surrounded Regions Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation: Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped....

Nothing just happens, it's all part of a plan.