第一题 盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
public int MaxArea(int[] height) {
int max = int.MinValue;
for (int i = 0; i < height.Length - 1; i++)
{
for (int j = 1; j < height.Length; j++)
{
int temp = (j - i)*Math.Min(height[i], height[j]);
if (temp > max)
{
max = temp;
}
}
}
return max;
}
第二题 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z。
public string LongestCommonPrefix(string[] strs)
{
if (strs.Length == 0)
return string.Empty;
string result = strs[0];
for (int i = 1; i < strs.Length; i++)
{
result = Prefix(result, strs[i]);
if (string.IsNullOrEmpty(result))
break;
}
return result;
}
public string Prefix(string str1, string str2)
{
int len1 = str1.Length;
int len2 = str2.Length;
int len = Math.Min(len1, len2);
int i = 0;
for (; i < len; i++)
{
if (str1[i] != str2[i])
break;
}
return i == 0 ? string.Empty : str1.Substring(0, i);
}
第三题 三数之和
给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
public IList<IList<int>> ThreeSum(int[] nums)
{
IList<IList<int>> result = new List<IList<int>>();
nums = nums.OrderBy(a => a).ToArray();
int len = nums.Length;
for (int i = 0; i < len - 2; i++)
{
if (nums[i] > 0)
break; // 如果最小的数字大于0, 后面的操作已经没有意义
if (i > 0 && nums[i - 1] == nums[i])
continue; // 跳过三元组中第一个元素的重复数据
int l = i + 1;
int r = len - 1;
while (l < r)
{
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0)
{
l++;
}
else if (sum > 0)
{
r--;
}
else
{
result.Add(new List<int>() {nums[i], nums[l], nums[r]});
// 跳过三元组中第二个元素的重复数据
while (l < r && nums[l] == nums[l + 1])
{
l++;
}
// 跳过三元组中第三个元素的重复数据
while (l < r && nums[r - 1] == nums[r])
{
r--;
}
l++;
r--;
}
}
}
return result;
}
