leetcode解题思路分析（二十二）148

排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

归并排序三部曲：
fast-slow找中点：直到快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段
将链表分成两部分
合并两个有序链表

class Solution { 
public:
    ListNode* sortList(ListNode* head) { 
        return mergesort(head);
    }
    ListNode* mergesort(ListNode* node)
    { 
        if(!node || !node->next) return node;
        ListNode *fast=node;//快指针走两步
        ListNode *slow=node;//慢指针走一步
        ListNode *brek=node;//断点
        while(fast && fast->next)
        { 
            fast=fast->next->next;
            brek=slow;
            slow=slow->next;
        }
        brek->next=nullptr;
        ListNode *l1=mergesort(node);
        ListNode *l2=mergesort(slow);
        return merge(l1,l2);
    }
    ListNode* merge(ListNode* l1,ListNode* l2)
    { 
        if(l1==NULL)
        { 
            return l2;
        }
        if(l2==NULL)
        { 
            return l1;
        }
        if(l1->val < l2->val)
        { 
            l1->next=merge(l1->next,l2);
            return l1;
        }
        else
        { 
            l2->next=merge(l2->next,l1);
            return l2;
        }
    }
};

直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

分类讨论：
1.使用一个变量dup记录重复的点；
2.使用Map，构造一个pair来记录：前者为斜率值，后者为计数（注意讨论斜率不存在的情况否则会造成除法异常）
但本题难在高精度斜率的计算，样例中有一个数据会使你的long double的精度都失效。所以这时候如果仍然采用传统的斜率判别法则需要运用高精度除法算法。
所以，基于此需要对Map的元素进行改变，构造pair此时使用字符串来保存斜率（代码中精度我取了小数点后20位）

class Solution { 
public:
   string Slope(int a, int b) { 
    string s = "";
    char c;
    int p;
    stringstream ss;  //使用字符流将整数部分直接转换成字符串。
    p = a / b;
    ss << p;
    ss >> s;
    s += '.';
    for (int i = 0; i < 20; i++)  //小数点后模拟除法过程，此时精度为20位。
    { 
        a = a % b * 10;
        c = (char)(a / b + 48);
        s += c;
    }
    return s;
}
int maxPoints(vector<vector<int>>& points) { 
    map<string, int>Dic;   //构造映射表，string类型存储斜率，int类型存储相应的点数。
    int i, j, x1, x2, y1, y2, ans, res = 2, temp, dup;
    string k;
    if (points.size() <= 2)
        return points.size();
    for (i = 0; i < points.size(); i++) { 
        dup = 0;
        ans = 0;
        for (j = i + 1; j < points.size(); j++) { 
            x1 = points[i][0];
            x2 = points[j][0];
            y1 = points[i][1];
            y2 = points[j][1];
            if (x1 == x2 && y1 == y2)   //情况一：重复的点。
                dup++;
            else if (x1 == x2 && y1 != y2) {   //情况二：斜率不存在的点。
                if (Dic.find(" ") == Dic.end())
                    Dic.insert(pair<string, int>(" ", 2));
                else
                    Dic[" "]++;
                ans = max(Dic[" "], ans);
            }
            else {    //情况三：斜率存在的点。
                k = Slope(y1 - y2, x1 - x2);
                if (Dic.find(k) == Dic.end())
                    Dic.insert(pair<string, int>(k, 2));
                else
                    Dic[k]++;
                ans = max(Dic[k], ans);
            }
        }
        if (ans == 0)   //注意，若遍历完只有重复的点，则需要加一，因为dup是从0开始计数的。
            res = max(res, dup + 1);
        else
            res = max(res, ans + dup);
        Dic.clear();
        k = "";
    }
    return res;
}
};

逆波兰表达式求值
根据逆波兰表示法，求表达式的值。

很无聊的一道题，知道什么事波兰表达式，用一个堆栈就可以了

class Solution { 
public:
    int evalRPN(vector<string>& tokens) { 
        if(tokens.empty()) return 0;
        stack<int> numst;
        stringstream ss;
        for(int i = 0;i<tokens.size();++i)
        { 
            string c = tokens[i] ;
            if(c == "+"||c == "-"||c == "*"||c == "/" ) 
            { 
                int temp1 = numst.top(); numst.pop();
                int temp2 = numst.top(); numst.pop();
                int temp3 = 0;
                if(c == "+") { temp3 = temp1+temp2; numst.push(temp3);}
                else if(c == "-") { temp3 = temp2-temp1; numst.push(temp3);}
                else if(c == "*") { temp3 = temp1*temp2; numst.push(temp3);}
                else{ temp3 = temp2/temp1; numst.push(temp3);}
            }
            else
            { 
            int number;
            ss.clear();
            ss<<c;
            ss>>number;
            numst.push(number);
            }
        }
        return numst.top();
    }
};

翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。

如果追求时间，则比较好的方法是额外建一个栈存储，之后依次读出即可。如果追求空间，则原地转换更佳，方法是先将整个字符串反转，然后判断每个单词再局部反转

class Solution { 
public:
    string reverseWords(string s) { 
        reverse(s.begin(), s.end());
        int size = (int)s.size();
        int start = 0; //单词开始
        int end = 0;   //单词末尾
        int index = 0; 
        for (; start < size; start++) { 
            if (s[start] == ' ') continue;
            if (index != 0){ 
                //第二个单词开始 开头需要插一个空格
                s[index++] = ' ';
            }
            end = start;
            //替换原来的s 一直到空格为止
            while (end < size && s[end] != ' ') { 
                s[index++] = s[end++];
            }
            //index指向了单词末尾的 下一个字符
            //一个单词的长度
            int len = end - start;
            //index - len就是单词开始的地方
            //s.begin() + index - len 单词开始的位置
            //s.begin() + index 单词结束的位置
            reverse(s.begin() + index - len, s.begin() + index);
            //更新下一个单词的开始位置 start正好指向了空格的位置
            start = end;
            //这一轮循环结束 之后 start++
            //如果只有一个空格 start正好 指向了下一个单词的开始位置
            //如果有多个空格，则指向了下一个空格 下次循环开头会跳过
        }
        //去除末尾的空格和没有用的字符
        s.erase(s.begin() + index, s.end());
        return s;
    }
};

乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

本题重点在于需要维护一个Min和一个max，因为负数的乘法很可能使得最大最小瞬间颠倒，采取动态规划思想遍历一遍即可

class Solution { 
public:
    int maxProduct(vector<int>& nums) { 
        int n = nums.size();
        if(n == 0){ 
            return 0;
        } else if(n == 1) { 
            return nums[0];
        }
        int p = nums[0];
        int maxP = nums[0];
        int minP = nums[0];
        for(int i = 1; i < n; i++) { 
            int t = maxP;
            maxP = max(max(maxP * nums[i], nums[i]), minP *nums[i]);
            minP = min(min(t * nums[i], nums[i]), minP * nums[i]);
            p = max(maxP, p);
        }
        return p;
    }
};

寻找旋转排序数组中的最小值

二分查找

class Solution { 
public:
    int findMin(vector<int>& nums) 
    { 
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) 
        { 
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) 
            {           
                left = mid + 1;
            } 
            else 
            {                                
                right = mid;
            }
        }
        return nums[left];
    }
};

寻找旋转排序数组中的最小值2

class Solution {
public:

int findMin(vector<int>& nums) { 
    int left = 0, right = nums.size() - 1;
    while(left < right){ 
        if(nums[left] < nums[right])
            return nums[left];
        int mid = (left + right) / 2;
        if(nums[mid] == nums[left] && nums[mid] == nums[right])
            right--;
        else if(nums[left] <= nums[mid])    //[left, mid]连续
            left = mid + 1;
        else                            //[mid, right]连续
            right = mid;    
    }
    return nums[left];
}