LeetCode第26/27题:Remove Duplicates from Sorted Array和Remove Element 总结

题目一

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], 阅读全文

LeetCode第21/23题:Merge Two Sorted Lists和Merge k Sorted Lists总结

题目一

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列表。
所以,具体用哪一种,要根据知己需求定。 阅读全文

LeetCode第20/32题:Valid Parentheses和Longest Valid Parentheses 总结

题目一:

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.

  • 大意:给定一个字符串,只包含”(){}[]”这些字符,判断字符串的括号是否都匹配。

思路

显然是用栈的思想做。 阅读全文

LeetCode第24/25题:Swap Nodes in Pairs和Reverse Nodes in k-Group总结

题目一

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. 阅读全文

LeetCode第42题:Trapping Rain Water总结

题目

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.
img

  • 大意: 有n个非负整数,代表地势图的高度,如图,计算下雨后这个地形能存多少雨水。

思路

这道题和第10题非常像,分别从最左边和最右边开始,定义两个游标,移动到过程中,记录左边的最大值和右边的最大值,然后用两个最大值中的小值减去地形高度,就是所积的雨水值(类似第10题思路)。 阅读全文

LeetCode第15,16,18题:3Sum, 3Sum Closest and 4Sum总结

这三道题明显是一家子,放到一起。。。

题目一 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 ≤ c)
The solution set must not contain duplicate triplets. 阅读全文

LeetCode第14题:Longest Common Prefix总结

题目

Write a function to find the longest common prefix string amongst an array of strings.

  • 大意: 写一个函数,找到一组字符串的公共最长前缀。

思路

我的:定义一个不断更新的变量,存储当前的最长前缀,循环时加以一定的优化,比如如果下一个字符串比当前的前缀还长,那么可以截断前缀后在进行比较。
参考的:这道题在discuss上看到了一些运用了python语法的解法,用到了zip,reduce,set等python特有的语法,顺便贴出。

代码

原创(Python):

阅读全文