RominYue’s Blog

A lifeway of coders

Leetcode Problem 11-15

| Comments

源代码push到了github上,戳这里

Problem 11: Container With Most Water

题目描述:给定一数组,在数组中挑两个数,他们与X轴组成的水池面积最大.
解法: O(n2)解法很自然,枚举起点终点即可. 下面介绍O(n)的解法.其实题目所求即为:

area = min(height[start], height[end])*(end - start)的最大值

显然一开始start = 0, end = n - 1. 那么如果 height[start] < height[end],是start指针向右移动,还是end 指针向左移动? 因为(end - start)是在逐步变小的,为了是area尽可能的变大,必须移动指针.所以如果start指针不动,那么显然以下不等式成立:

(end - 1 - start) * min(height[start],height[end - 1]) <= height[start] * (end - 1 - start) <= min(height[start], height[end])*(end - start)

所以当 height[start] < height[end] 时, 当前最优策略就是 start ++;
反之当 height[start] > height[end] 时, 当前最优策略就是 end - -.

Problem 12: Integer to Roman

题目描述: 整数转成罗马数字. 没什么难度,熟悉以下罗马数字体系即可.
罗马数字体系可以参考这里
解法:可以直接把表打出来,因为罗马数字几千,几百,几十都是固定的.

Problem 13: Roman to Integer

题目描述: 罗马数字转整数
解法: 将字符串从右向左扫描,如果当前字符比上一个字符代表的数字小,减之,否则叠加在结果上.

Problem 14: Longest Common Prefix

题目描述: 给定字符串数组,寻找他们的最长公共前缀
解法: 假设共有n个字符串,字符串中长度最小的长度记为m,则时间复杂度位O(n*m)
遍历长度最小的字符串,看看其他字符串是否和他的一样,从此找出最长前缀.

Problem 15: Remove Nth Node From End of List

题目描述: 给定一个链表,指定删除倒数第n个节点.
要求: 一趟完成,n合法,不必检查
难点; 如何确定倒数第n个节点的位置
解法: 两个指针fast,slow都指向head.先让fast指针走n个节点,这样,fast相对slow偏移n个节点,两者同时向后移动,间距始终保持不变,直到链表的末尾.此时slow指向的是要删除节点的前一节点(画画图就知道了).需要注意的就是链表本身只有n个节点的情况.

Comments