第一题:字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
示例 3:
输入: num1 = "498828660196", num2 = "840477629533"
输出: "419254329864656431168468"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来
public string Multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0")
return "0";
int len1 = num1.Length;
int len2 = num2.Length;
int len = len1 + len2;
int[] temp = new int[len];
for (int i = len2 - 1; i >= 0; i--)
{
int k = len2 - i;
int b = num2[i] - '0';
for (int j = len1 - 1; j >= 0; j--)
{
int a = num1[j] - '0';
int c = a*b;
temp[len - k] += c%10;
if (temp[len - k] >= 10)
{
temp[len - k] = temp[len - k]%10;
temp[len - k - 1]++;
}
temp[len - k - 1] += c/10;
if (temp[len - k - 1] >= 10)
{
temp[len - k - 1] = temp[len - k - 1]%10;
temp[len - k - 2]++;
}
k++;
}
}
StringBuilder sb = new StringBuilder();
int s = temp[0] == 0 ? 1 : 0;
while (s < len)
{
sb.Append(temp[s]);
s++;
}
return sb.ToString();
}
第二题:全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
public class Solution
{
private IList<IList<int>> _result;
private bool[] _used;
public IList<IList<int>> Permute(int[] nums)
{
_result = new List<IList<int>>();
if (nums == null || nums.Length == 0)
return _result;
_used = new bool[nums.Length];
FindPath(nums, 0, new List<int>());
return _result;
}
public void FindPath(int[] nums, int count, List<int> path)
{
if (count == nums.Length)
{
//递归终止条件
List<int> item = new List<int>();
item.AddRange(path);
//加入拷贝
_result.Add(item);
return;
}
for (int i = 0; i < nums.Length; i++)
{
if (_used[i] == false)
{
path.Add(nums[i]);
_used[i] = true;
FindPath(nums, count + 1, path);
path.RemoveAt(path.Count - 1);
_used[i] = false;
}
}
}
}
第三题：最大子序和
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2:
输入: [-2,1],
输出: 1
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
动态规划：
public class Solution {
public int MaxSubArray(int[] nums) {
int len = nums.Length;
if (len == 0)
return 0;
if (len == 1)
return nums[0];
int[] max = new int[len];
max[0] = nums[0];
int result = max[0];
for (int i = 1; i < len; i++)
{
if (max[i - 1] + nums[i] > nums[i])
{
max[i] = max[i - 1] + nums[i];
}
else
{
max[i] = nums[i];
}
if (max[i] > result)
{
result = max[i];
}
}
return result;
}
}
