题目 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. Input:Digit string “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. Note: Although the above answer is in lexicographical order, your answer could […]

题目 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. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 大意： 有n个非负整数，代表地势图的高度，如图，计算下雨后这个地形能存多少雨水。 思路 这道题和第10题非常像，分别从最左边和最右边开始，定义两个游标，移动到过程中，记录左边的最大值和右边的最大值，然后用两个最大值中的小值减去地形高度，就是所积的雨水值（类似第10题思路）。 关于两个游标怎么移动的问题，同第10题思路，还是移动当前最大值较小的边，比如：当前右边最大值right_max为10，左边最大值left_max为5，如果移动right_index，那么左边的最大值只能保持不变，不管right_max变不变，两个最大值的较小一个也还会是left_max，没有可能增加积水量，所以可能会存在错误。（详细可结合代码看） 代码 Python class Solution(object): def trap(self, height): “”” :type height: List[int] :rtype: int <!–more–> “”” if […]

题目 Determine whether an integer is a palindrome. Do this without extra space. 大意：判断一个整数是不是回文的。。 吐槽： 同第7题：用Python简直就是作弊啊。。。。。 代码 Python class Solution(object): def isPalindrome(self, x): “”” :type x: int :rtype: bool “”” x = str(x) x = x.strip() if x[::1] == x[::-1]: return True else: return False

题目： Implement atoi to convert a string to an integer. 大意：就是手动实现C语言里常用的atoi函数。。。 思路和吐槽： 我最讨厌这种了，完全的信息不对称。。要讨论的情况只有不断提交才知道出题人什么意思，我怎么知道你要求的是什么，况且这是算法题又不是工程题。。。。幸亏这道题比较简单，多试几次也不太费时。 代码 Python class Solution(object): def myAtoi(self, str): “”” :type str: str :rtype: int “”” str = str.strip() if not str: return 0 ans = [] neg = “-” pos = “+” ch = str[0] if ch == neg: c = -1 elif […]

题目 Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 大意：就是把数字倒过来。。。 思路和吐槽 只有吐槽：用Python做简直是太简单了，简直就是在作弊，，，如果我十天之内没用c++再做一遍，我肯定是白做了这道题 代码 Python class Solution(object): def reverse(self, x): “”” :type x: int :rtype: int “”” if x < 0: symbol = -1 else: symbol = 1 x = abs(x) str_x = str(x) ans_list = list(str_x) […]

题目 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) P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR” Write the […]

题目： Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 大意：就是找出字符串中最大的回文子字符串 吐槽： 这应该是一道经典的算法题，可是我还是没有什么好办法，可见我真的是太菜了。哎。。。用了一个O( n^2 )的解法，妥妥的超时了。。。后来看了网上的有关文章和discuss里面的代码，修改了版本。 暴力超时版Python代码： （肯定是我自己写的） class Solution(object): def longestPalindrome(self, s): longest_str = “” longest_len = 0 for i in range(len(s) – 1): […]

题目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). 大意 有两个排好序的数组nums1和nums2，分别长m和n.找出两个数列的中值，复杂度应该为O(log (m+n)). 思路 这道题虽然知道应该是分治的思路，我没有做出来，找了一下discuss里面的题解，看了一下，打算把有关的分治书上好好看过之后在回顾之后再更新下这道题。 这里贴出discuss的两个帖子链接，这两个是discuss里面顶的最多了两篇。第一篇思路比较正常，翻译了下。第二篇的思路更是很巧妙的避开了奇偶数的讨论，但不知道是否具有普适性。 Python: 我的错误代码如下：（仅作纪念） #错误代码 class Solution(object): def findMedianSortedArrays(self, nums1, nums2): “”” :type nums1: List[int] :type nums2: List[int] :rtype: […]

题目： Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. 大意：给出一个字符串，找出不包含重复字母的最长字串，输出字符串的长度。 这道题是一个字符串的题，好久不写明显手生，所以一些细节耗费了很多时间去调试，希望自己慢慢熟悉起来。 思路： 我的大概思路就是： * 对字符串进行一次遍历，用一个大小为256（ascii最多有256种字符）数组记录每个字母最后一次的下标。 * 当当前字符以前出现过时就覆盖原来的数组元素，并且更新start值。 * 每次循环时检查当前下标i-开始下标start和一个记录当前最大串长度的max变量的关系，将max保持或更新。 * 需要注意的是，我更新start和max是在检测到重复字母时进行的，而最后一个字符不一定和前边重复，所以循环外要附加一次更新max的操作。 […]

题目 You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> […]