文章 212
评论 0
浏览 119890
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 ....

Design - 146. LRU Cache

Design - 146. LRU Cache

LRU Cache Design and implement a data structure for Least Recently Used (LRU) 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 reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a positive capacity....

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....

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....

DFS&BFS - 200. Number of Islands

DFS&BFS - 200. Number of Islands

200. Number of Islands Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output: 1 Example 2: Input: 11000 11000 00100 00011 Output: 3 思路: 题目意思是在一个二维平面找出有多少个岛屿,可以使用dfs或者bfs做,这里使用dfs来做,每找到一个点是岛屿,就不断四个方向探索,把探索过的区域打上标记或者置为水域就可以。 代....

Backtracking - 93. Restore IP Addresses

Backtracking - 93. Restore IP Addresses

93. Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 思路: 题目意思是给一个只包含数字的字符串给出所有合法ip地址的组合。一看就是很典型使用回溯来枚举的题目,使用ip地址每一位值只能是[0, 255]之间的值来剪枝。同时每一位可能有1位或者两位或者三位数字,这样来分别dfs递归求解。 代码: go: func restoreIpAddresses(s string) []string { var res []string if s == "" || len(s) < 4 || len(s) > 12 { return res } dfs(&res, s, "", 0) return res } ....

Backtracking - 17. Letter Combinations of a Phone Number

Backtracking - 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 思....

Backtracking - 60. Permutation Sequence

Backtracking - 60. Permutation Sequence

60. Permutation Sequence The set [1,2,3,...,_n_] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the _k_th permutation sequence. Note: Given n will be between 1 and 9 inclusive. Given k will be between 1 and n! inclusive. Example 1: Input: n = 3, k = 3 Output: "2....

Backtracking - 47. Permutations II

Backtracking - 47. Permutations II

47. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 思路: 和46题差别在于数字有重复,需要返回unique的组合,组合问题,只要有重复,通解思路都是先先排序,剩下的就基本和46题一样,还需判断一个数是否被用过来剪枝。 代码: go: func permuteUnique(nums []int) [][]int { sort.Ints(nums) return permute(nums) } func permute(nums []int) [][]int { var res [][]int dfs(0, nums, &res) return res } func dfs(start int, nums []int, res *[][]int){ if....

Backtracking - 46. Permutations

Backtracking - 46. Permutations

46. Permutations Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 思路: 题目意思很简单就是求出一个数组的排列组合,思路就是使用回溯来做。 代码: go: func permute(nums []int) [][]int { var res [][]int dfs(0, nums, &res) return res } func dfs(start int, nums []int, res *[][]int){ if start == len(nums) { *res = append(*res, append([]int{}, nums...)) return } for i := start; i < len(nums); i++ { num....

Dynamic Programming - 377. Combination Sum IV

Dynamic Programming - 377. Combination Sum IV

377. Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: nums_ = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7. Follow up: What if negative numbers are allowed in the given array? How does it change....

Backtracking - 216. Combination Sum III

Backtracking - 216. Combination Sum III

216. Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] 思路: 这一题是组合系列的变形题,要求用k个1-9的数组组合出n值,采用回溯来做,使用组合的个数为k个和为n来剪....

Backtracking - 40. Combination Sum II

Backtracking - 40. Combination Sum II

40. Combination Sum II Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8,....

Backtracking - 39. Combination Sum

Backtracking - 39. Combination Sum

39. Combination Sum Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candida....

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