[Leetcode]Top K问题总结

2021-03-06
阅读 1 分钟
4.8k
问题:找第 K 大的数在一个数组里在数据流中找最大的 K 个数在一个数组里在数据流中找出现频率最高的 K 个数在一个数组中在数据流中在文件中这种题适合各种follow up核实问题:是否需要精确的结果?数据是离线的(文件形式计算一次得到一个结果)还是在线的(数据流可无限次查询实时结果)?-问题1 - 找第 K 大的数:在一个...

[Design Pattern] 即学即用设计模式

2016-12-11
阅读 1 分钟
2.7k
工作之后代码都是业务逻辑,与算法题很不一样。在研究公司代码库时发现很多设计模式的应用,于是打算系统地学习Design Pattern。想要达到的目的是,给一个需求,能够迅速知道哪种设计模式可以应用,然后分析在这个情境中是否应该用这个设计模式,还是组合多个设计模式,抑或压根不用设计模式避免过度设计。达到这个目标...

[System Design] TinyURL 设计短网址系统

2016-08-02
阅读 5 分钟
26.3k
日活用户:100M每人每天使用:(写)长到短0.1,(读)短到长1日request:写10M,读100Mqps:写100,读1Kpeak qps: 写200,读2K(千级别的qps可以单台SSD MySQL搞定)

[System Design] 当你访问www.google.com的时候发生了什么?

2016-08-01
阅读 1 分钟
7.6k
www.google.com会自动补全为[链接]这是个url,他表示网络某个资源(resource)的位置, 一般格式为: protocol :// hostname[:port] / path / ;parameters#fragment

[Leetcode] Backtracking回溯法(又称DFS,递归)全解

2016-07-30
阅读 5 分钟
32.8k
用爬山来比喻回溯,好比从山脚下找一条爬上山顶的路,起初有好几条道可走,当选择一条道走到某处时,又有几条岔道可供选择,只能选择其中一条道往前走,若能这样子顺利爬上山顶则罢了,否则走到一条绝路上时或者这条路上有一坨屎,我们只好返回到最近的一个路口,重新选择另一条没走过的道往前走。如果该路口的所有路都走不通,只...

[设计题] 17道经典设计题串讲

2016-07-21
阅读 7 分钟
19.2k
最近正在面试uber,uber以频繁考察系统设计而著名,系统设计是一个没有标准答案的open-end问题,所以关键在于对于特定问题的设计选择,俗称trade-off,这个思维平时无处锻炼,故开启此文,记录学习和理解的过程。 本文全部题目和分析来自《Elements Of Programming Interviews》的 Design Problems 章节,我只是在他的基...

[Leetcode] Largest Number

2016-07-20
阅读 2 分钟
2.3k
Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is9534330. Note: The result may be very large, so you need to return a stringinstead of an integer.

[Leetcode] Permutation Sequence

2016-07-20
阅读 2 分钟
2.2k
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 thefollowing sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kthpermutation sequence. Note: Given n will be between 1 and 9 incl...

[Leetcode] First Missing Positive

2016-07-20
阅读 2 分钟
2.9k
Given an unsorted integer array, find the first missing positive integer. For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space.

[Leetcode] Design Tic-Tac-Toe 设计精子游戏

2016-07-14
阅读 2 分钟
5.1k
Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block.Once a winning condition is reached, no more moves is allowed.A player who succeeds in placing n of their marks in a h...

[Leetcode] Find Leaves of Binary Tree

2016-07-12
阅读 2 分钟
7.9k
Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty. Example:Given binary tree {代码...} Returns [4, 5, 3], [2], [1]. Explanation: Removing the leaves [4, 5, 3] would result in this tree: {代码...} 2 Now removing the...

[Leetcode] Largest Divisible Subset 最大整除集合

2016-07-10
阅读 2 分钟
7.3k
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: nums: [1,2,3]Result: [1,2] (of course, [1,3] will also be ok) E...

[Leetcode] Factor Combinations 因数组合

2016-06-26
阅读 2 分钟
9.2k
Numbers can be regarded as product of its factors. For example, {代码...} Write a function that takes an integer n and return all possible combinations of its factors. Note: You may assume that n is always positive.Factors should be greater than 1 and less than n.

[Leetcode] Inorder Successor in BST 二叉搜索树中序遍历找后继

2016-06-25
阅读 3 分钟
4.6k
Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: If the given node has no in-order successor in the tree, return null.

[Leetcode] Different Ways to Add Parentheses 表达式加括号

2016-06-24
阅读 2 分钟
6.3k
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Example 1Input: "2-1-1". {代码...} Output: [0, 2] Example 2Input: "23-45" {代码...} Output: [-34, -14, -10, -10, 10]

[Leetcode] Binary Tree Upside Down 二叉树上下调个儿

2016-06-22
阅读 2 分钟
4.6k
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root. For example:Given a binary tree ...

[Leetcode] Maximum Size Subarray Sum Equals k 找和为k的最长子数组

2016-06-22
阅读 2 分钟
9.3k
Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead. Example 1:Given nums = [1, -1, 5, -2, 3], k = 3,return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest) Example 2:Given nums = [-2, -1, 2, 1],...

[Leetcode] Sort Transformed Array 抛物线排序

2016-06-22
阅读 2 分钟
7.1k
Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array. The returned array must be in sorted order. Expected time complexity: O(n) Example:nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,Result: [3, 9, 15, 33...

[Leetcode] Maximum Gap 相邻最大差值

2016-06-21
阅读 3 分钟
4.7k
Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integ...

[Leetcode] Binary Tree Traversal 二叉树三种非递归遍历

2016-06-21
阅读 4 分钟
2.9k
先写一个utility: pushAllLeft(root):把root(包含)一路向左通到底,路过的节点将其访问(加入到result),并压入栈,留作备用;此时栈顶的元素满足:他的左孩子以及他自己必已经被访问;栈顶元素都是下一个应该访问的子树的根,将其弹出,(不必访问,因为他进栈时已被访问),然后尝试访问它的右孩子;如果有右孩子,把右孩...

[Leetcode] Integer Break 分解整数最大乘积

2016-06-21
阅读 2 分钟
4.2k
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4). Note: you may assume that n is not less...

[Leetcode] Generalized Abbreviation 列举单词缩写

2016-06-20
阅读 2 分钟
5.3k
Write a function to generate the generalized abbreviations of a word. Example:Given word = "word", return the following list (order does not matter): {代码...}

[Leetcode] ZigZag Conversion 波浪形打印字符串

2016-06-19
阅读 3 分钟
6.6k
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) {代码...} And then read line by line: "PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given ...

[Leetcode] Bulls and Cows 猜数字

2016-06-18
阅读 2 分钟
4.3k
You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and posi...

[Leetcode] Paint Fence 栅栏涂色

2016-06-17
阅读 2 分钟
3.9k
There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence. Note:n and k are non-negative integers.

[Leetcode] Pascal's Triangle II 杨辉三角

2016-06-17
阅读 1 分钟
4.3k
Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3,Return [1,3,3,1].

[Leetcode] House Robber I & II & III 入室盗窃

2016-06-16
阅读 4 分钟
2.8k
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent hou...

[Leetcode] Intersection of Two Arrays II 找数组的交集

2016-06-15
阅读 2 分钟
4.2k
Intersection of Two Arrays II {代码...} 排序+双指针 复杂度 O(Min(N,M)) 时间 O(Min(N,M)) 空间 思路 先排序,用两个指针从头扫:小的那个肯定不行,指针往后相等的全都放到result里 注意 没有 代码 {代码...} Follow Up What if elements of nums2 are stored on disk, and the memory is limited such that you can...

[Leetcode] Merge Sorted Array 合并两个有序数组

2016-06-14
阅读 1 分钟
7.7k
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note:You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectiv...

[Leetcode] Word Search I&II 二维字符矩阵查找单词

2016-06-13
阅读 7 分钟
4.5k
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same >letter cell may not be used more than once. For example, Given board = {...