题目 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()” 大意：给定n对括号，写一个函数来生成所有正确的配对串。 思路 生成所有的可能，然后注意检测是不是符合要求。 ##代码 (Python) class Solution(object): def isValid(self, s): “”” :type s: str <!–more–> :rtype: bool “”” l = [‘0’] for ch in […]

题目一 Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. × 大意： 给定一个链表，依次交换两个相邻节点，并返回头节点。 比如： 1->2->3->4 交换后应该为 2->1->4->3. 思路 […]

题目 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. […]

题目 Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most […]

这两道题明显是一对。。。放一起 题目一 Integer to Roman Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. 大意： 就是把一个1~3999的阿拉伯数字，变成罗马数字表示。 题目二 Roman to Integer Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. 大意： 就是把一个1~3999的罗马数字，表示成阿拉伯数字。 […]

题目 Write a function to find the longest common prefix string amongst an array of strings. 大意： 写一个函数，找到一组字符串的公共最长前缀。 思路 我的：定义一个不断更新的变量，存储当前的最长前缀，循环时加以一定的优化，比如如果下一个字符串比当前的前缀还长，那么可以截断前缀后在进行比较。 参考的：这道题在discuss上看到了一些运用了python语法的解法，用到了zip,reduce,set等python特有的语法，顺便贴出。 代码 原创(Python): class Solution(object): def longestCommonPrefix(self, strs): “”” :type strs: List[str] :rtype: str “”” if len(strs) == 0: return “” if len(strs) == 1: return strs[0] <!–more–> com_str = list(strs[0]) for i in range(1, […]

这三道题明显是一家子，放到一起。。。 题目一 3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b […]

题目 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 […]