文章 217
评论 6
浏览 143930
Array - 16. 3Sum Closest

Array - 16. 3Sum Closest

16. 3Sum Closest Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 思路: 给定一个数组,找出三个数的和最接近target,和15题很像,做法类似,都是对于每一位元素,用双指针找出另外两个数,更新出一个最小的结果就可以。 代码: go: f....

Array - 15. 3Sum

Array - 15. 3Sum

15. 3Sum Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 思路: 找出数组中三数和的所有组合,解决思路是首先做一个排序,然后对于每一位元素,去找出剩下数组中找出两个数和当前元素三个数和为0就可以,主要要留意重复元素就不用了计算....

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

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

Design - 146. LRU Cache

Design - 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

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

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

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