算法分析与设计第一周
第一周
第一周讲了分治,但是找不到分治的题目,所以随便找了两道题做了一下。
第一题:
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
分析:此题与算法没什么关系,主要看逻辑的严密性。有两个注意点:符号、溢出。其中溢出比较隐蔽,我用的是long来存数,并判断是否int溢出,然后转化为int输出。
代码:
class Solution {
public:
int myAtoi(string str) {
int i = 0;
int sign = 1;
long tempResult = 0;
int result;
while (str[i] == ' ')
++i;
if ( str[i] == '-' || str[i] == '+')
{
if (str[i] == '-')
sign = -1;
++i;
}
while ('0' <= str[i] && str[i] <= '9' && i < str.length())
{
tempResult = tempResult * 10 + (str[i] - '0');
if (tempResult * sign > INT_MAX)
return INT_MAX;
else if (tempResult * sign < INT_MIN)
return INT_MIN;
++i;
}
result = tempResult * sign;
return result;
}
};
第二题:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice
分析:方法一:暴力法,最简单的思路,即嵌套遍历数组,直到找到答案,这个算法复杂度为O(n^2),效率较差。
代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
int first;
int second;
for (first = 0; first < nums.size(); ++first)
{
for (second = first + 1; second != nums.size(); second++)
{
if (nums[first] + nums[second] == target)
{
result.push_back(first);
result.push_back(second);
return result;
}
}
}
}
};
方法二:只要选择了第一个元素,第二个元素是不需要顺序遍历找的,所以可以利用哈希表,因为哈希表查询平均时间是O(1),然后遍历查找第一个元素即可,将复杂的降为O(n)。
代码:
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target)
{
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++)
{
hash[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];
if (hash.find(numberToFind) != hash.end() && hash[numberToFind] != i) {
result.push_back(hash[numberToFind]);
result.push_back(i);
return result;
}
}
return result;
}
};
上一篇: 企业的低效会议,应该如何改善?
下一篇: SSH 项目中的问题记录