题目一

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

题目一:

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.

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

思路

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

题目

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

Note: You may not slant the container.

  • 大意:有n个非负的整数a1到an,ai每个代表i处的高度,(i,ai)和(i,0)是线段i的两个端点,所有任意两个线段i可以和x轴组成一个容器,找出能装最多水的容器。注意:不能倾斜容器。

思路

这道题所求的容积和容器下边长度(两个线段的横坐标距离)和侧边最小长度有关(类似木桶效应)。
所以容积 = abs(i2 – i1) * min(ai1, ai2),我们要找出的就是用那两条线段做边界时,这个容器最大,求出这个最大的容积。 阅读全文

题目

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题思路)。 阅读全文