leetcode组合拳(1)

一、数组
盛最多的水
解：
双指针做法：但是要证明双指针的正确性，这个题有点类似两数之和的做法。双指针的题容易敲代码，但是证明其合理性还是比较难的。
比如这个题，证明其合理性可以这样：
首先，肯定是在height[left]和height[right]中选出小的一个，因为res=min(height[left],height[right])*(right-left);所以理论上要控制变量法，控制距离或控制值差，但是这里距离变化和值差变化是同步的。因此需要考虑怎么变化才能得到最优的res，显然，我们必须通过减小距离来获取新的res，那么如果移动值较大的指针，并不影响res的变化，因为res取决于较小的值，因此需要移动会导致结果变化的指针，即指向大值的指针。
可以总结下：包括两数之和的题目，双指针，一定要明确指针移动的条件，原则是改变哪个指针会对结果产生我们想要的影响，即逼近我们要的结果，那么就怎样移动指针。
下面是代码：

int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1;
        int res=0;
        while(left<right){
        int   ans=min(height[left],height[right])*(right-left);
            if(height[left]<height[right])  
                ++left;
            else --right;
            res=max(res,ans);
        }
        return res;
}

二、链表
两两交换链表中的结点
解：
其实这个题不是很难，交换链表的next指针就好了。所以就不赘述了，直接上码：

    ListNode* swapPairs(ListNode* head) {
        if(!head||!head->next)  return head;
        ListNode *cur=head;
        head=head->next;
        while(cur&&cur->next){
            ListNode *tmp=cur->next->next;
            cur->next->next=cur;
            if(!tmp){
                cur->next=nullptr;
            }
            else if(!tmp->next){
                cur->next=tmp;  
            }
           else cur->next=tmp->next;
           cur=tmp;
        }
        return head;
    }

三、栈
简化路径
解：重点是要知道stringstream流的用法，可以通过getline(ss,cur,'/')指定结束符并把分段的字符串赋值给cur。
本来是写了一个了，谁知道没保存，裂开。

    string simplifyPath(string path) {
        stack<string> s;
        stringstream ss(path);string cur;string res="";
        while(getline(ss,cur,'/')){
            if(cur!=".."&&cur!=""&&cur!="."){
                s.push(cur);
            }
            else if(!s.empty()&&cur==".."){
                s.pop();
            }
        }
        while(!s.empty()){
            res.insert(0,s.top());
            res.insert(0,"/");
            s.pop();
        }
        return res.size()? res:"/";
    }

四、队列
第k个数
多指针的用法，用来合并多个线性表，很妙，这题可以认为是经典题。

    int getKthMagicNumber(int k) {
        //素因子也叫质因数，指的是一个数可以被分解为的质数的乘积
        //显然，不难发现，这些数都是由 3，5，7乘积得到
        //因此问题转换为求线性表的排序问题
        /*三指针法：分别指向在一组数中乘以3，5，7后的新序列*/
        int new_3=0,new_5=0,new_7=0;
        int *new_number=new int[k];
        new_number[0]=1;
        //int base_number={3,5,7}
        for(int i=1;i<k;++i){//从i=1开始，因为i=0已经初始化为1
            new_number[i]=min( min(new_number[new_3]*3,new_number[new_5]*5) ,new_number[new_7]*7);
            if(new_number[i]==new_number[new_3]*3){
                ++new_3;
            }
            if(new_number[i]==new_number[new_5]*5){
                ++new_5;
            }
            if(new_number[i]==new_number[new_7]*7)  ++new_7;
        }
        return new_number[k-1];

    }

五、字符串
最长字符串
解：由于官方题解给的答案有三种，一种动态规划，一种中心扩展法，一种是Manacher算法(了解)，前两种复杂度都是O(n^2)，所以不如直接用双指针做好了。
可是，测试时却显示超出了时间限制，哦吼。那就先这样吧。卡了很久，从下午1点左右卡到3点半，卡了两个半小时，主要实现同一一下奇数长度回文串和偶数长度回文串统一方法，但一直是顾此失彼，所以绕了很久。最后只能是分开讨论了。以后如果有想到统一的方法，再过来改进吧。

    string longestPalindrome(string s) {
        //过滤一些特例
        if (s.size() < 2)  return s;
        //双指针做法
        int n = s.size(); int len = 0, start = 0;
        unsigned int jishu_len = 0; int jishu_start = 0;
        unsigned int oushu_len = 0; int oushu_start = 0;
        //i是遍历每一个可能的回文中心：[1...n-1]
        for (int i = 0; i < n; ++i) {
            //left为左端指针，right为右端指针
            int left = i - 1, right = i + 1; unsigned int ans = 1;
            while (left >= 0 && right <= n - 1 && s[left] == s[right]) {
                ans += 2; --left; ++right;
            }
            if (ans > jishu_len) {
                jishu_len = ans;
                jishu_start = left + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            //left为左端指针，right为右端指针
            int left = i, right = i + 1; unsigned int ans = 0;
            while (left >= 0 && right <= n - 1 && s[left] == s[right]) {
                ans += 2; --left; ++right;
            }
            if (ans > oushu_len) {
                oushu_len = ans;
                oushu_start = left + 1;
            }
        }
        start = jishu_len > oushu_len ? jishu_start : oushu_start;
        len = jishu_len > oushu_len ? jishu_len : oushu_len;
        return s.substr(start, len);
    }

六、树
二叉树的遍历
解：可以递归实现也可以非递归实现。两种都尝试写下。

    vector<int> inorderTraversal(TreeNode* root) {
        //递归实现---居然可以执行用时 0ms,击败100%的用户
        /*vector<int> res;
        midTraversal(root,res);
        return res;*/
        //非递归实现：利用栈---居然也是100%
        stack<TreeNode*>s;vector<int>res;
        //不断的搜索左树，直到不存在左节点
        while(root){
            s.push(root);
            root=root->left;
        }
        while(!s.empty()){
            root=s.top();
            res.push_back(root->val);s.pop();
            //如果此时该结点有右结点
            if(root->right){
                //放入右节点
                s.push(root->right);
                //更新root
                root=s.top();
                //不断的搜索左树，直到不存在左节点
                root=root->left;
                while(root){
                    s.push(root);
                    root=root->left;
                }
            }
        }
        return res;   
    }
    //先构造递归函数
    //函数作用是递归遍历二叉树，并把结点放入向量中
    void midTraversal(TreeNode *root,vector<int> &res){
        //base case
        if(!root)   return;
        //先遍历左节点
        midTraversal(root->left,res);
        //在该结点的操作
        res.push_back(root->val);
        //最后是遍历右节点
        midTraversal(root->right,res);
    }

七、图
克隆图
解：这个题和在剑指offer上刷到的拷贝随机链表的题很像。当时是用两个哈希表来编码和译码来实现随机链表随机指针的指向的。
很复杂，想了很久，由于时间问题，先溜了...
回来了：这个题后来看了题解，发现又是dfs和bfs问题。
其实不需要两个哈希表，一个就够了。只要存旧新结点的对应关系就行了。这个题，用bfs比dfs好很多，原因是dfs递归很耗时间。

 Node* cloneGraph(Node* node) {
        //深度优先搜索DFS:把所有先走一遍，不顾细节
        //return dfs(node);
        //广度优先搜索BFS：先把每一个仔细找完，再找下一个
        return bfs(node);
    } 
   /* unordered_map<Node *,Node*>hashTable;
    Node * dfs(Node *node){
        //base case 1
        if(!node) return nullptr;
        //base case 2
        if(hashTable.count(node))   return hashTable[node];
        //operations 1: write down 
        Node *clonenode=new Node(node->val);
        hashTable[node]=clonenode;
        //operation 2: connect and return
        for(auto &neighbor:node->neighbors){
            clonenode->neighbors.push_back(dfs(neighbor));
        }
        return clonenode;
    } */

    Node *bfs(Node *node){
        //consider some exceptions
        if(!node) return nullptr;
        //normal situation
        unordered_map<Node *,Node*>hashTable;
        queue<Node *>q;q.push(node);
        Node *clonenode=new Node(node->val);
        hashTable[node]=clonenode;
        while(!q.empty()){
            //get the first node cur
            Node* cur=q.front();
            //connect the new nodes
            for(auto &neighbor:cur->neighbors){
                //if not have,write down and push the new node 
                if(!hashTable.count(neighbor)){
                    Node *connectnode=new Node(neighbor->val);
                    hashTable[neighbor]=connectnode;
                    q.push(neighbor);
                }    
                hashTable[cur]->neighbors.push_back(hashTable[neighbor]);
            }
            //pop the first node cur
            q.pop();
        }
        return clonenode;
    }

总结：关于图的很多知识还没看完，因此先抓紧时间把图看完，再继续刷。
八、排序
排序数组
解：目前就学到了8种排序方法，如下：

    vector<int> sortArray(vector<int>& nums) {
       // 1.bubbleSort(nums);
       // 2.selectSort(nums);
        //3.insertSort(nums);
       // 4.shellSort(nums);
       //5.quickSort(nums,0,nums.size()-1);
      //6. heapSort(nums);
      /*7.vector<int> tmp(nums.size());
      mergeSort(nums,tmp,0,nums.size()-1);*/
      //8.countingSort(nums);
        return nums;
    }
    //catch this chance,pratice all methods to sort
    //1.bubbleSort
    void bubbleSort(vector<int>& nums){
        int n=nums.size();
        for(int i=0;i<n-1;++i){
            bool changed=0;
            for(int j=0;j<n-1-i;++j){
                if(nums[j+1]<nums[j]){
                    changed=1;
                    swap(nums[j],nums[j+1]);
                }
            }
            if(!changed)    break;
        }
    }
    //2. selectSort
    void selectSort(vector<int>&nums){
        int n=nums.size();
        for(int i=n-1;i>=0;--i){
            int maxindex=i;
            for(int j=0;j<i;++j){
                if(nums[j]>nums[maxindex])
                    maxindex=j;
            }
            swap(nums[maxindex],nums[i]);
        }
    }
    //3. insertSort
    void insertSort(vector<int>&nums){
        int n=nums.size();
        for(int i=1;i<n;++i){//must from the head to the tail
            //find the right position and move other numbers
            for(int j=i;j>0&&nums[j-1]>nums[j];--j){
                swap(nums[j],nums[j-1]);                
            }
        }
    }
    //4. shellSort：kunth
    void shellSort(vector<int>& nums) {
        int n = nums.size(); int h = 1;
        while (h <= n / 3) {
            h = h * 3 + 1;//kunth
        }
        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {//counts of skipping methods
            for (int i = gap; i < n; ++i) {//because 2*gap maybe max than n, so limited by n is the best choice
                for (int j = i; j > gap - 1; j -= gap) {//why j is limited by gap-1: j-gap>=0 ===>  j>=gap  ==> j>gap-1
                    //find the right position
                    if (nums[j] < nums[j - gap])
                        swap(nums[j - gap], nums[j]);
                }
            }
        }
    }
    //5. quickSort ---pass
    void quickSort(vector<int>& nums,int left,int right){
        /*recursion*/
        //base case
        if(left>=right) return;
        //operations
        int mid=get_mid(nums,left,right);
        quickSort(nums,left,mid-1);
        quickSort(nums,mid+1,right);
    }
    //need a get_mid function
    int get_mid(vector<int>&nums,int left,int right){
        int mid_num=nums[left];
        //two methods to get  the mid
        //first one : three whiles
        while(left<right){
            while(left<right&&nums[right]>=mid_num) --right;
            nums[left]=nums[right];
            while(left<right&&nums[left]<=mid_num)  ++left;
            nums[right]=nums[left];
        }
        nums[left]=mid_num;
        return left;
        //second one: two points
        /*int j=left;
        for(int i=left;i<=right;++i){
            if(nums[i]<=mid_num)    swap(nums[i],nums[j++]);
        }
        swap(nums[left],nums[j-1]);
        return j-1;*/
    }

    //6. heapSort---pass
    void heapSort(vector<int>&nums){
        buildHeap(nums);
        for(int i=nums.size()-1;i>0;--i){
            swap(nums[i],nums[0]);
            maxheapify(nums,0,i);
        }
    }
    //nead a heapify function
    void maxheapify(vector<int>&nums,int node,int len){
        //get the temp largest number
        int largest=node;
        //get the child of the node
        int l_child=(node<<1)+1,r_child=l_child+1;
        if(l_child<len&&nums[l_child]>nums[largest])    largest=l_child;
        if(r_child<len&&nums[r_child]>nums[largest])    largest=r_child;
        if(largest!=node){
            swap(nums[node],nums[largest]);
            maxheapify(nums,largest,len);
        }
    }
    //and need a buildHeap function
    void buildHeap(vector<int>&nums){
        int len=nums.size();
        for(int i=( (len-1)>>1 );i>=0;--i){
            maxheapify(nums,i,nums.size());
        }
    }

    //7. mergeSort--pass
    void mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right) {
        /*recursion*/
        //base case
        if (left >= right) return;
        //operations
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, tmp, left, mid);
        mergeSort(nums, tmp, mid + 1, right);
        merge(nums, tmp, left, mid, right);
    }
    //need a merge function to merge two arrays
    void merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) tmp[k++] = nums[i++];
            else    tmp[k++] = nums[j++];
        }
        while (i <= mid)    tmp[k++] = nums[i++];
        while (j <= right)   tmp[k++] = nums[j++];
        //copy tmp to nums
        for (int i = left,j=0; j < k; ++i,++j)    nums[i] = tmp[j];
        //notice the numbers in tmp is from 0 to k-1, 
        //but nums need to store numbers which are from left to left+k-1
    }
        //8. countingSort
    void countingSort(vector<int>& nums) {
    //1.create a enough space to store all nums
    //find the max and min
    int maxnum = nums[0], minnum = nums[0];
    for (int i = 0; i < nums.size(); ++i) {
        if (maxnum < nums[i]) maxnum = nums[i];
        if (minnum> nums[i])  minnum = nums[i];
    }
    vector<int>res(maxnum-minnum + 1);
    //2. write down the number of nums
    for (int i = 0; i < nums.size(); ++i)
        ++res[nums[i] - minnum];
    //sort
   for (int i = 0,k=0; i < res.size(); ++i) {
        while (res[i]--) {
            nums[k++] =i+ minnum;
        }  
    }

九、递归
递归乘法
解：用的快速幂：

/*递归实现快速幂*/
int fastpower(int a, int b) {
    //base case
    if (a == 0 || b == 0)  return 1;
    //operation 1:devide b to binary
    return (b & 1 ? a : 1) * (b > 1 ? fastpower(a * a, b >> 1) : 1);
}

    int multiply(int A, int B) {
        //fast power
        //recursion
        //base case
        if(A==0||B==0)  return 0;
        //operations
        return (B&1 ? A:0)+(B>1? multiply(A+A,B>>1):0);

    }

十、动态规划
丑数
解：其实这个题算多指针的问题，与第k个数类似，但也算是动态规划了,所以就不说太多了。

    int nthUglyNumber(int n) {
        //多指针
        int i2 = 0, i3 = 0, i5 = 0;
        vector<int>nums(n); nums[0] = 1;
        for (int k = 1; k < n; ++k) {
            nums[k] = min(min(2 * nums[i2], 3 * nums[i3]), 5 * nums[i5]);
            if (nums[k] == 2 * nums[i2]) ++i2;
            if (nums[k] == 3 * nums[i3]) ++i3;
            if(nums[k]==5*nums[i5])  ++i5;
        }
        return nums[n - 1];
    }