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