这篇博文用来记录我做过的leetcode的题目和当时的一些思路,太简单的题就不列出来了,持续更新…
#17.Letter Combinations of a Phone Number [Medium]
Description
Given a digit string, 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:
Although the above answer is in lexicographical order, your answer could be in any order you want.
Idea
用递归可以很快解决。
Solution
|
|
#136.Single Number [Easy]
Description
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Idea
这道题竟然是Easy,不敢相信,如果不知道“两个相同的数按位异或等于0”和“按位异或符合交换率”这两条性质,想破脑袋都想不出来,但是一旦知道,就几行代码搞定。
Solution
|
|
#226.Invert Binary Tree [Easy]
Description
nvert a binary tree.
|
|
to
|
|
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Idea
反转二叉树其实很简单,就是递归,但是因为Homebrew作者在谷歌面试的遭遇而引人关注。
Solution
|
|
#258.Add Digits [Easy]
Description
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
Idea
这道题用递归很简单,但是偏偏不让你用递归,我想了半天没明白还有什么办法,一看别人的解答发现原来是有规律的。
|
|
原来这个结果会在1-9循环,那我们对9取模就好了,不过要让9和9的倍数出的结果是9而且还要考虑0的情况。
Solution
|
|
#260.Single Number III [Medium]
Description
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Idea
这道题相比于#136要复杂一些,找两个single number的话用异或的方法只能求出这两个数有哪些位不同,我们可以通过这一点将原数组的分成两组,且这两个数分在不同组,这样的话我们再通过异或的方法分别找出这两个数。
Solution
|
|
#283.Move Zeroes [Easy]
Description
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Idea
两个指针,两个指针都先放在开头,然后第二个指针向后找非0的数,放到第一个指针处,第一个指针向后走,然后再把0填上。
Solution
|
|
#338.Counting Bits [Medium]
Description
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
Follow up:
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Idea
这道题找规律找了好久,找到了规律后编程又编了好久。只要是$2^n$的数,1的个数都是1个,以它们为分界线,中间数字的1的个数会出现“复现”规律。先把32以内的数的1的个数列出来观察一下就明白了。
1234567分界线2^n 1的个数0 01 12 1 24 1 2 2 38 1 2 2 3 2 3 3 416 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
看明白规律了么?就是每到一个新的分段,前一半是上一分段的复现,后一半是上一分段复现再加1。知道了规律就按照这个规律编程就行了,但是也不简单,挺恶心的。
Solution
|
|
#371.Sum of Two Integers [Easy]
Description
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
Idea
这道题看起来很简单,但是我并不觉得很好编程,尤其是在Python上。思路就是用位操作去做,相当于把它看作二进制数,然后通过异或操作^可以得到各个位上加法的结果,与操作&可以判断是否进位,让异或的结果和与操作并且移位的结果不停的相加直到没有进位了停止。在Python上int型变量并没有固定位数,只有通过对0x100000000取模来构造一个32位的int型整数了,挺恶心的。
Solution
|
|
#406.Queue Reconstruction by Height [Medium]
Description
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Example:
|
|
Idea
这道题看起来简单,我一开始通过最常规的解法一个个去判断排哪一个人符合题目要求,然后一个个去构造队伍,这样做解法超时了。然后看了大神的思路,真是强,完全没想到可以这么做。思路是先将这些人按照一定规则排序(感觉很多题目通过先排序就可以降低时间复杂度),规则是身高高的在前,如果身高一样就把人数少的放在前面。排好序之后,再逐个把人插入到这个队的第i个,i指的是后面那个人数,然后神奇的事情就发生了,队列就构造好了。Amazing!
Solution
|
|
#413.Arithmetic Slices [Medium]
Description
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
|
|
The following sequence is not arithmetic.
|
|
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
|
|
Idea
这道题就是先判断哪一段是等差数列,等差数列多长,然后再统计等差子数列个数。
Solution
|
|
#419.Battleships in a Board [Medium]
Description
Given an 2D board, count how many battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:
- You receive a valid board, made of only battleships or empty slots.
- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
- At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
|
|
In the above board there are 2 battleships.
Invalid Example:
|
|
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
Idea
我们可以从战舰的布局中找出计数的技巧,我们扫描一边棋盘,如果是战舰就判断它的下方和右方是否有战舰,如果有则先不计数,如果没有则计数加1,这样不会重复计数。只要稍加注意边界就行了,把边界当成空槽来处理。
Solution
|
|
#442.Find All Duplicates in an Array [Medium]
Description
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
|
|
Idea
这道题是微软实习生面试被问到的题目,思路见微软实习生面试小记第二轮的扩展题。
Solution
|
|
#461.Hamming Distance [Easy]
Desciprtion
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note: $0\leq x,y\leq2^{31}$.
Example:
|
|
Idea
按照定义去计算就行了,Python中可以通过bin
函数将十进制转换成二进制。
Solution
|
|
#462.Minimum Moves to Equal Array Elements II [Medium]
Description
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
You may assume the array’s length is at most 10,000.
Example:
|
|
Idea
这道题就是要先找到大家往哪个数字移动,当然往中位数移动总次数最少,因为无论往中位数加减1的数字移动,都会增加总次数,所以中位数就是我们要找的数,排序之后中位数就很好找了。
Solution
|
|
#463.Island Perimeter [Easy]
Description
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example:
|
|
Idea
这道题就是扫描一遍,将相邻方格如果是水就计数加1。
Solution
|
|
#466.Count The Repetitions [Hard]
Description
Define S = [s,n] as the string S which consists of n connected strings s. For example, [“abc”, 3] =”abcabcabc”.
On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.
You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers $0 ≤ n1 ≤ 10^6$ and $1 ≤ n2 ≤ 10^6$. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.
Example:
|
|
Idea
这是做的第一道Hard的题目,想了很久做的还是不对。最后找到这个discuss里的解答才明白该怎么做,结题思路还是挺复杂的,我就不复制粘贴了。
Solution
|
|
#476.Number Complement [Easy]
Description
Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Example:
|
|
Idea
按照定义来做就行了。
Solution
|
|
#500.Keyboard Row [Easy]
Description
Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.
Example:
|
|
Idea
这道题我把每个字母当作键放进一个字典,排数就是键值,然后对每个单词去逐个字母判断了,如果出现不同排的就跳过这个单词。
Solution
|
|
#508.Most Frequent Subtree Sum [Medium]
Description
Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.
Example 1:
input:
|
|
return [2, -3, 4], since all the values happen only once, return all of them in any order.
Example 2:
input:
|
|
return [2], since 2 happens twice, however -5 only occur once.
Idea
这道题就是通过递归去计算每个子树的和,然后再去统计频率。
Solution
|
|
#513.Find Bottom Left Tree Value [Medium]
Description
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
|
|
Example 2:
|
|
Idea
这道题要关注是不是最底层,而不光是最左。所以在遍历的时候要加一个层数作为参数,如果层数增加,由于是先遍历左子树,所以第一个增加层数的节点一定是最左的节点。
Solution
|
|
#526.Beautiful Arrangement [Medium]
Description
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the $i_{th}$ position (1 ? i ? N) in this array:
The number at the $i{th}$ position is divisible by i.
i is divisible by the number at the $i{th}$ position.
Now given N, how many beautiful arrangements can you construct?
Example:
|
|
Idea
这道题思路就是回溯法。通过visted这个数组来保存状态,记得再递归之后要恢复之前的状态。
Solution
|
|
#529.Minesweeper [Medium]
Description
Let’s play the minesweeper game!
You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:
- If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
- If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
- If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
- Return the board when no more squares will be revealed.
Example 1:
|
|
Explanation 1:
Example 2:
|
|
Explanation 2:
Note:
- The range of the input matrix’s height and width is [1,50].
- The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
- The input board won’t be a stage when game is over (some mines have been revealed).
- For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.
Idea
这道题其实不难,但是觉得很好玩。用递归就可以解决了。
Solution
|
|
#535.Encode and Decode TinyURL [Medium]
Desciprtion
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
Idea
对任何一个URL都随机生成一个6个字符的字符串作为短连接,然后把随机生成的短连接和原链接存进两个字典里用来编码和解码。
Solution
|
|
#537.Complex Number Multiplication [Medium]
Description
Given two strings representing two complex numbers.
You need to return a string representing their multiplication. Note $i^2 = -1$ according to the definition.
Idea
就是按照定义求。
Solution
|
|
#538.Convert BST to Greater Tree [Easy]
Description
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
|
|
Idea
这道题一开始想的很复杂,还是错的,忽略了二叉查找树的中序遍历(右->中->左)就是从大到小进行遍历,我们有一个全局的sum,然后不断累加节点的数值到sum中,遍历到的节点的值就是自己的值加上sum。
Solution
|
|
#540.Single Element in a Sorted Array [Medium]
Description
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Example 1:
|
|
Example 2
|
|
Note: Your solution should run in O(log n) time and O(1) space.
Idea
看到O(log n)那基本上就是二分法了。Single Element一定出在个数为奇数的那一半,不停的二分直到找到它。
Solution
|
|
#557.Reverse Words in a String III [Easy]
Description
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example:
|
|
Idea
这个在Python里写起来很简单。
Solution
|
|
#561.Array Partition I [Easy]
Description
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example:
|
|
Note:
- n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
Idea
要使题目中所说的和最大,那肯定要把所有小的两两组合求min,否则小的和大的组合会使各个项都比较小,所以先把数组排序,然后从最小开始两两组合求min,然后求和就行了。
Solution
1234567891011class Solution(object):def arrayPairSum(self, nums):""":type nums: List[int]:rtype: int"""sorted_nums = sorted(nums)sum = 0for i in range(len(nums)/2):sum += sorted_nums[2*i]return sum
#565.Array Nesting [Medium]
Description
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
Sets S[K] for 0 <= K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.
Sets S[K] are finite for each K and should NOT contain duplicates.
Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
Example:
|
|
Note:
- N is an integer within the range [1, 20,000].
- The elements of A are all distinct.
- Each element of array A is an integer within the range [0, N-1].
Idea
一开始的想法是把所有的集合都算出来比大小,但是超时了。后来想其实这个集合就是几组循环数字,无论从这个循环中的哪个数字开始,集合都是一样的。所以建立一个vistied集合,当所有元素都访问过了之后,所有可能的集合就出来了,就不用再往后求更多的集合啦,因为后面的集合会和前面的一样。这个时候结束循环返回结果就可以了。
Solution
|
|
#566.Reshape the Matrix [Easy]
Description
In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.
You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example:
|
|
Idea
先判断维数是否符合,符合的话就把原矩阵先变成一维数组,然后再按给定行列往里塞。
Solution
|
|
#575.Distribute Candies [Easy]
Description
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example:
|
|
Idea
这道题就是比较到底是糖的种类多还是糖总数的一半多,返回较小者。
Solution
|
|
#617.Merge Two Binary Trees [Easy]
Desciprtion
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example:
|
|
Note: The merging process must start from the root nodes of both trees.
Idea
二叉树就用递归的思想去做。
Solution
|
|
#637.Average of Levels in Binary Tree [Easy]
Description
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example:
|
|
Idea
先遍历二叉树,输出每一层的数字到一个字典中,然后再求均值。
Solution
|
|
#647.Palindromic Substrings [Medium]
Description
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
|
|
Example 2:
|
|
Idea
这道题一开始我根本搞不懂什么叫Palindromic String,后来才知道是正反都是一样的字符串,例如“abcdcba”这样。找别人的做法才知道应该用动态规划去做。用一个数组dp去表示从第i个字符到第j个字符的子字符串是不是Palindromic的。而如果dp[i-1][j-1]是Palindromic的,如果第i个字符与第j个字符相同,那么dp[i][j]也是Palindromic的。
Solution
|
|