题目一 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array nums = [1,1,2], Your function should return length = 2, with […]
题目一 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 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 […]
题目一 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 大意：合并两个列表，返回一个新的列表，新的列表要把前边给定的两个列表链接起来。 思路： 其实就是把两个有序列表变成一个有序列表，只要维护两个指针，分别将当前最小的数复制到第三个列表中，然后将相应指针后移即可。道理很简单。 需要注意到是，python中，如果一个变量等于一个列表(比如，list1为一个列表，定义a1 = list1)，则这个变量(a1)其实类似c中的指针的概念(a1和list1等价，都是“指针”)，并不是拷贝了这个列表(如要实现拷贝复制，可以写a1 = list1[:])。 对于本题，这样的语法其实产生了两种写法，（见下边小节)。对于本题，两种写法都对，第一种写法比较简洁，但是却改变了原来的l1和l2列表，因为p3指针赋值的时候，直接用了l1或者l2的节点，那么下一次赋值的时候，便改变了这个节点的next指针。第二种写法采用了oj所定义的ListNode类的构造函数，直接用符合要求的l1或者l2的节点的val值创建一个新的node链接在l3后边，所以不改变原先的l1和l2列表。 所以，具体用哪一种，要根据知己需求定。 代码1(python) # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = […]
题目一: Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not. 大意：给定一个字符串，只包含”(){}[]”这些字符，判断字符串的括号是否都匹配。 思路 显然是用栈的思想做。 代码 (Python) class Solution(object): def isValid(self, s): “”” :type s: […]
题目 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. […]
这两道题明显是一对。。。放一起 题目一 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的罗马数字，表示成阿拉伯数字。 […]
题目 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 […]
题目 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 […]