1、Two Sum
题目
此题第一解题思路，就是最常见的方法，两个指针嵌套遍历数组，依次判断当前指针所指向的值是否满足条件。代码如下;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int p1,p2;
const int size = nums.size();
for (p1 = ;p1<size;p1++)
{
for(p2 = p1+;p2<size;p2++)
if (target == nums[p1] + nums[p2])
{
break;
}
}
vector<int> res;
res.push_back(p1+);
res.push_back(p2+);
return res;
}
};
这种思路解决该问题的时间复杂度是O（n*n）,虽然时间复杂度比较高，但是该算法是最直接也最容易想到的解决办法，能够解决题目所提出的要求。
学过算法的同学都知道，几个比较常见的算法时间复杂度是O(n*n),O(nlogn),O(n),O(logn)。在现有算法的基础上进行算法优化也是一项比较好的能力，因此，我们还需要对之前的算法做一些优化，按照常规思路，我们猜想还有时间复杂度是O(nlogn)的算法能够解决该问题。看到时间复杂度为O(nlogn),第一反应就是“排序”，因为排序算法的时间复杂度是O(nlogn)，所以，我们可以先对数据排序，然后采用夹逼的方式找到满足条件的数据。如果要对数据进行排序，则打乱了数据的原始顺序，因此排序的同时要记录各个数据的原始位置，如果遇到面试官出这种题，也需要问清楚是否能够改变原数据的位置，问清楚之后再想办法。代码如下
struct node
{
int value;
int index;
};
bool Cmp( const node &v1, const node &v2)
{
return v1.value < v2.value;//升序排列
}
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int p1,p2;
const int size = nums.size(); vector<node> temp;
node t;
for (int i=;i<size;i++)
{
t.value = nums[i];
t.index = i;
temp.push_back(t);
} sort(temp.begin(),temp.end(),Cmp);
p1 = ;
p2 = size-;
while (p1 <= p2)
{
if(temp[p1].value + temp[p2].value > target)
p2--;
else if(temp[p1].value + temp[p2].value < target)
p1++;
else
break;
} //由于一定有解，因此不用判断解是否存在
vector<int> res;
int min = temp[p1].index > temp[p2].index ? temp[p2].index:temp[p1].index;
int max = temp[p1].index < temp[p2].index ? temp[p2].index:temp[p1].index; res.push_back(min );
res.push_back(max); return res;
}
};
该算法的时间复杂度为O（nlogn），其主要是先排序后操作。
到此我们可能回想还能不能对算法就行优化，使得算法的时间复杂度更低。比O（nlogn）复杂度更低的常规复杂度就是O（n），如果复杂度是O（n），意味着对数据只能进行多次访问遍历，不能有嵌套遍历这种方式，也就是遍历的时候需要做“记忆功能”，有记忆功能的结构，比如哈希,map等。因此可以采用如下的方法解决该问题：
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> result;
result.clear();
map<int,int> myMap;
int i,temp;
int length = numbers.size();
map<int,int>::iterator it;
myMap.insert(pair<int,int>(nums[],));
for (i=;i<length;i++)
{
temp = target - nums[i];
it = myMap.find(temp);
if (it!=myMap.end())
{
result.push_back(it->second+);
result.push_back(i+);
break;
}
myMap.insert(pair<int,int>(nums[i],i));
}
return result;
}
};
------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------------------
2 Add Two Numbers
题目
这道题主要考察指针的使用，灵活的使用指针是c++程序员必须的技能之一.代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if (NULL == l1)//算法的鲁棒性
{
return l2;
}
if (NULL == l2)
{
return l1;
} ListNode *head = new ListNode();//添加伪头部
ListNode *tail = head;
ListNode *p1 = l1;
ListNode *p2 = l2;
int c=,temp; while(NULL != p1 && NULL != p2)
{
temp = (p1->val + p2->val + c)%;
c = (p1->val + p2->val + c)/;
tail->next = new ListNode(temp);
tail = tail->next;
p1 = p1->next;
p2 = p2->next;
} while (NULL != p1)
{
temp = (p1->val + c)%;
c = (p1->val + c)/;
tail->next = new ListNode(temp);
tail = tail->next;
p1 = p1->next;
} while (NULL != p2)
{
temp = (p2->val + c)%;
c = (p2->val + c)/;
tail->next = new ListNode(temp);
tail = tail->next;
p2 = p2->next;
}
if (c!=)
{
tail->next = new ListNode(c);
tail = tail->next;
} head = head->next;
return head; }
};
-----------------------------------------------------------------------------------------分割线-----------------------------------------------------------------------------------------
3、Longest Substring Without Repeating Characters
题目
题目意思：不含重复字母的最长子串
字符串s[0,n-1]，其子串表示为s[i,j],其中0<=i<=j<=n-1，通过这种表示方法，解决该题的暴力算法就是先确定一个子串(i,j)，再判断该子串中是否有重复的字符，代码如下:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if("" == s)
return ;
set<char> myset;
int i,j;
int max = ;
int length = s.length();
for(i=;i<length;i++)
{
myset.clear();
for(j=i;j<length;j++)
{
if(myset.find(s[j])!=myset.end())
{
break;
}
else
{
myset.insert(s[j]);
}
}
if(j-i >max)
max = j-i;
}
return max;
}
};
算法时间复杂度很明显是O(n*n),因此这个算法让人不是很满意的，需要在此基础上优化，寻找是否存在O(nlogn)或者复杂度更低的算法。
O(nlogn),意味着要对字符串做排序工作，对字符串排序是比较少有的操作，因此排除这种算法。
在寻找不重复的最长子串时，通过在纸上画示意图可以得知，假设当前从下标[i]开始寻找,一直到下标[j]为止都还没有发现重复的字符，但是在下标[j+1]处，发现该字符与下标[k]（i<=k<=j）处的字符一样。因此在做下一轮寻找时，需要从[k+1]做为起始字符进行寻找，代码如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if("" == s)
return ;
set<char> myset;
int i,j;
int max = ;
int length = s.length();
i=;
j=;
myset.clear();
myset.insert(s[]);
for (;j<length;j++)
{
if(myset.end() == myset.find(s[j]))
myset.insert(s[j]);
else//删除k之前的所有字符
{
if(j-i > max)
max = j-i;
while(s[i] != s[j])
{
myset.erase(s[i]);
i++;
}
myset.erase(s[i]);
i++;
j--;
}
}
if(j-i>max)
max = j-i;
return max;
}
};
提交Accepted。
算法时间复杂度分析，for循环停止条件是j=length，每次从集合set中还要删除一部分元素，因此复杂度为O(2n)。
这种算法的思想和KMP算法的思想很类似。如果熟练了KMP算法，解决这道题就不在话下。
<(￣︶￣)>
------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------------------
231 Power of Two
题目很简单，直接上代码，主要是掌握bitset的使用。
class Solution {
public:
bool isPowerOfTwo(int n) {
bitset<> myset(n);
if (n<=)
{
return false;
}
if (==myset.count() || ==myset.count())
{
return true;
}
return false;
}
};