2019-06-13

Algorithm(5) Two pointers and hash table (Part B)(By solution)

这一篇主要还是围绕 two pointer 相关的题目进行整理。

Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.
大致思路
这个一开始容易把人蒙住，其实是一个蛮简单的问题。就是在数轴上有好多列，找两个列，要求和x轴组成的面积最大，这个两指针是从两边开始向中间靠拢，每次计算成绩之后再更新最大值，每次保留y轴上最大的那个列，剩下的那个,若v[i]<v[j],i++否则j–。大致就是，每次x轴长度总减1,那么y周肯定要保留更长的，来使得面积最大。

class Solution {
public:
    int maxArea(vector<int> &height) {
		int len=height.size();
		int l=0,r=len-1;
		int max=0;
		int tempv;
		int temph;
		int templ;
		while(l<r){
			temph=height[l]<height[r]?height[l]:height[r];
			templ=r-l;
			tempv=temph*templ;
			if(tempv>max){
				max=tempv;
			}
            //keep the bigger one
			if(height[l]<height[r]){
				l++;
			
			}else{
				r--;
			}
		}
        return max;
    }
};

Implement strStr()

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

这个题目在解决方式上应该属于两指针的类型，具体的问题背景属于string的类型。其实还是蛮引人深思的一个题目，就是在一个串中，找子串出现的位置。最好的方法当然是用现成的KMP算法了。可是除非背了模板，要不然能熟练写出来，还是要花很多工夫，提前要准备得很好。

之后那种brute force 的方法，就是两个指遍历，发现不行的时候就往后移动一个元素，再重新比较。有一个很长的用例，aa…a 以及 aa…b 总是超时，这个时候采用的策略是，当发现第一个元素相同的时候，直接比较最后一个元素，要是不match 直接跳过，有点取巧的感觉。也算是一种折衷吧。在实际项目中，可能并不会总是那么“理想”，比如缓存什么的，都是先挡掉一部分再说了。

还有一个启发，就是所谓的“事前”异常处理，比如needle为 “” 的时候，直接返回0，比如len(haystack)<len(needle)的时候，直接返回-1 ,要是无法看到没有通过的测试用例，说实话，自己是很难考虑到这些测试情况的，能看到没有通过的测试用例，感觉就还是蛮幸福的。

class Solution {
public:
    int strStr(string haystack, string needle) {
		int index_h=0;
		int index_n=0;
		int start=-1;
		int len_h=haystack.size();
		int len_n=needle.size();
		if (needle.size()==0){
			return 0;
		}
		if (len_n>len_h){
			return -1;
		}
		while(index_h<len_h){
		    // 剩余长度不够就跳过了
			if (len_h-index_n+1<len_n){
				break;
			}
			
            if (haystack[index_h]==needle[0]){
             // 首先检查一下最后几个字符 要是不可以就直接跳过 比较取巧的方法
				if (haystack[index_h+len_n-1]!=needle[len_n-1]){
						index_h++;
						index_n=0;
						start=-1;
						continue;
				}
				start=index_h;
				while(index_n<len_n){
					if(haystack[index_h]==needle[index_n]){
						index_h++;
						index_n++;
						continue;
					}else{
						index_h=start+1;
						index_n=0;
						start=-1;
						break;
					}		
				}	
				if (start!=-1){
					return start;
				}	
			}
			else{	
				index_h++;
			}
		}
		return start;  
    }
};

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

这个貌似是之前考研时候的真题了。思路上就是比较简单的，判断一个linkedlist是否有环，采用追赶的方式来进行，指针都是从头开始，一个指针每次往后跳一下，另一个指针每次往后跳两下。之后如果两个结点可以重合，说明就有环，否则没环，需要注意的是先前的一些判断条件：比如链表是否为空，以及只有一个结点的情况下怎么处理。第二个链表的指针往后跳的时候是否变为空，等等。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *h1=head;
        ListNode *h2=head;
       bool cycle=false;
        if (head==NULL){
            return false;
        }
        if (h1->next==h1){
            return true;
        }
        if (h1->next==NULL){
            return false;
        }
        while(h1!=NULL&&h2!=NULL){
            h1=h1->next;
            if(h2->next!=NULL){
                h2=h2->next->next;
            }else{
                break;
            }
            if(h1==h2){
                cycle=true;
                break;
            }
        }
        return cycle;        
    }
};

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

其实这个题目挺好的，有一定的考察性，如果我出面试题的话，相比于上一个题目的话，会出这个，因为可以体现一定的区分度，虽然还是参考网上的答案的。虽然实现起来比较容易，首先按照上cycle问题的解法，一个指针一次跳一步，一个指针一次跳两步，若是有相遇，则让第一个指针回到起点的位置，但多少还是要绕几个弯：两个指针一起向后遍历，直到再次相遇的时候，这个节点就是循环开始的那个结点。

比如以下面这个图为例

TODO

可以看到，整个listnode的长度为a+b，其中循环部分的长度为b，假设从start节点(即循环开始的节点)到meet节点(即两个指针相遇的节点)的长度d为c。假设两个指针分别都跳了t步，之后相遇。

s1=t=a+nb+c

s2=2t=a+mb+c

则s2-s1=t=(m-n)b=a+nb+c

则 a=(m-2n)b-c

我们进行的第二步的操作的也是根据这个关系来的。两个指针的步长都会变为1，一起向后移动。对于左边部分，a的长度正好是从链表的开头到start节点的长度，（m-2n）b-c从meet节点开始往后算，正好是又循环了多圈之后再从meet节点往后退c的长度，正好也到了start节点的位置，之后两个指针就相遇了，这个节点也恰好是起始点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *h1=head;
        ListNode *h2=head;
        bool cycle=false;
        int flag=0;
        if (head==NULL){
            cycle = false;
            flag=1;
        }
        if (h1!=NULL&&h1->next==h1){
            cycle =true;
            flag=1;
        }
        if (h1!=NULL&&h1->next==NULL){
            cycle = false;
            flag=1;
        }
        while(h1!=NULL&&h2!=NULL&&flag==0){
            h1=h1->next;
            if(h2->next!=NULL){
                h2=h2->next->next;
            }else{
                break;
            }
            if(h1==h2){
                cycle=true;
                break;
            }
        }  
        if(cycle==false){
            return NULL; 
        }else{
            h1=head;
            while(h1!=h2){
                h1=h1->next;
                h2=h2->next;
            }
        }
        return h1;
    }
};

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:
You must not modify the array (assume the array is read only).【说明不能对数组进行排序】

You must use only constant, O(1) extra space.【说明不能采用时间换空间的方法建立一个map 或者是新的数组来记录是否这个元素被访问过】

Your runtime complexity should be less than O(n2).【说明不能采用两层循环的那种遍历方式】

There is only one duplicate number in the array, but it could be repeated more than once.【说明不能采用所有数字再相加之后再减去 1+2+3+..+n 这种方式因为可能某个数字重复出现多次】

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

这个题目采用map的方式是直接可以过的，利用map的特性会很简单：

 class Solution {
 public:
     int findDuplicate(vector& nums) {
         if(nums.empty()) return 0; 
         map m;
         for(int i = 0; i < nums.size(); i++){
             if(m.find(nums[i]) == m.end())
                 m[nums[i]] = i;
             else return nums[i];
         }
     }
};

但是显然这个不是考察的目的，看tag可以使用two pointer也可以使用binary search具体链接放在下面了。感觉比较好的一个值使用two pointer的方式，相当于是一种伪链表的表示方式，用下标表示当前的结点的id用其中的值表示所指向的下一个元素。由于有重复出现的元素，这个伪链表肯定是有环的，最后就转换成了上一个问题，寻找循环开始时候的那个节点。这个转换过程的思路还是挺好的。还有一个要注意的地方就是起始点的位置因为空间是多了一个的所以最后一个元素是不能指向自己的所以从最后一个元素开始遍历链表这样实现的时候会简单一些不用处理第一个元素就指向的是本身的这种情况因为实际上又可能是多个链表的比如 1 2 3 4 5 5 这种每个元素都指向自己有5个单独的链表组成但是重复的那个元素肯定会出现在最后的节点所在的链表上面

class Solution {
 public:
     int findDuplicate(vector& nums) {
         int low=nums.size()-1;
         int fast=low;
         //find the meet point attention to the start position
         while(1){
              low=nums[low]-1;
              fast=nums[nums[fast]-1]-1;
              if(low==fast){
                  break;
              }
         }
         //low pointer back to the start position
         low=nums.size()-1;
         while(1){
            low=nums[low]-1;
            fast=nums[fast]-1;
            if(low==fast){
                break;
            }
         }
         return low+1;
     }
};

可以看到，虽然思路还是需要绕一些弯的，但实际上，代码量是很少的，就那么几行，可见提前准备好是有多重要，面试的时候要是这种题准备过，那就是分分钟出结果了。

参考：

http://blog.csdn.net/u010232171/article/details/48832149
http://blog.csdn.net/u011860731/article/details/48825223
采用unorded_map??
http://www.bubuko.com/infodetail-1123239.html 直接采用map也是ok的

Merge Sorted Array

这个应该是算比较基础一类题了，注意一些细节，这种题最好能够无错地写出，注意每次index的后移操作。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		int p=0;
		int q=0;
		int count=0;
		vector<int> result;
		int len1=m;
		int len2=n;
		
		while (p<len1&&q<len2){
			if(nums1[p]<nums2[q]){
				result.push_back(nums1[p]);
					p++;
				
			}else{
				result.push_back(nums2[q]);
				q++;
			}
		}
		
		while(p<len1){
			result.push_back(nums1[p]);
			p++;
		}
		
		while(q<len2){
			result.push_back(nums2[q]);
			q++;
		}
		nums1=result;
        
    }
};

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

其实这个有了之前的Longest Substring Without Repeating Characters在这一篇的基础，就显得容易多了，同样是窗口滑动的思想，两个指针开始处于同一个位置，之后根据sum的不同分别向后移动，在移动的过程中，更新最小序列的长度，比较典型吧，由于都是正整数。

sum > s 的时候，想要值更小一点，就更新左边的指针
sum < s 的时候，想让值变得更大一点，就更新右边的指针

需要注意的是：边界条件的判定，特别是输入数组为空的时候，否则直接让sum=nums[l]就会可能发生运行时错误，还有再最后的时候，要是没有符合要求的结果，就返回0，这两点自己第一次都没有看出来，事实上这也是判断程序员是否有经验的一个重要方面，面试的时候现场写程序，可能就跪了，边界检查这种东西，真是要时刻牢牢记在心里，要是不提示输入示例的话，还真是不太容易看出来。。。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
		int l=0,r=0;
		int sum=0;
		int len=nums.size();
		int tempcount=1;
		int maxcount=99999999;
		if (len==0){
		    return 0;
		}
		sum=nums[l];
		while(l<=r&&r<len){
			if(sum>=s){
				if(maxcount>tempcount){
					maxcount=tempcount;
				}
				sum=sum-nums[l];
				l++;
				tempcount=tempcount-1;
				
			}else{
				r++;
				sum=sum+nums[r];
				tempcount++;
			}
			
			
		}
		if (l==0&&r==len){
                maxcount=0;
		}
		
		return maxcount;
        
    }
};

AverageMind