leetcode中级算法

不一定按顺序的随心所欲记录。

数组和字符串

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

v[m][n]表示s[m,n]为一个回文串

string longestPalindrome(string s) {
    int n = s.size();
    int pos = 0, num = 0;
    vector<vector<bool>> v(n, vector<bool>(n, false));
    for (int i=0;i<n;i++){
        for (int j=0;j+i<n;j++){
            if ((i<2 || v[j+1][j+i-1]) && s[j] == s[j+i]){
                v[j][j+i] = true;
                if (i > num){
                    pos = j, num = i;
                }
            }
        }
    }
    return s.substr(pos, num+1);
}

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
因为原地算法，所以不能找到0就马上改变其他位置（未判断过的位置），这会影响后面的判断，所以必然要记录一下有哪些行列要置零。
一下子陷入僵局，这样就需要m+n的空间去记录。
注意这里的说法，“额外空间”，为什么不使用已有空间来做记录呢？
按序遍历二维数组，一个数字的所在的行列，总会有已经判断过的值，发现需要清零，这些位置可以直接改为零。

结论：用第一行和第一列作为清零的记录位，而这一行一列用两个bool变量去记录是否需要清零，这样就变成常数额外空间。

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    bool frow = false, fcol = false;
    for (int i=0;i<rows;i++)
        for (int j=0;j<cols;j++)
            if (matrix[i][j] == 0)
            {
                if (i == 0)
                    frow = true;
                if (j == 0)
                    fcol = true;
                if (i != 0 && j != 0)
                {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
    for (int i=1;i<rows;i++)
        if (matrix[i][0] == 0)
            for (int j=0;j<cols;j++)
                matrix[i][j] = 0;
    for (int j=1;j<cols;j++)
        if (matrix[0][j] == 0)
            for (int i=0;i<rows;i++)
                matrix[i][j] = 0;
    if (frow)
        for (int j=0;j<cols;j++)
                matrix[0][j] = 0;
    if (fcol)
        for (int i=0;i<rows;i++)
                matrix[i][0] = 0;
}

树和图

岛屿的个数

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

一开始想着顺序遍历，给’1’的位置赋一个标记，比如’2’，’3’，以此区分不同地区，同时将一个点周围的四个点改为相同的值。

// 无法通过的第一次尝试
int numIslands(vector<vector<char>>& grid) {
    int mark=1;
    int ans = 0;
    if (grid.empty() || grid[0].empty())
        return 0;
    int row = grid.size();
    int col = grid[0].size();
    vector<vector<int>> dic{{0,1},{1,0},{-1,0},{0,-1}};
    for (int i=0;i<row;i++){
        for (int j=0;j<col;j++){
            if (grid[i][j] == '1'){
                grid[i][j] += mark;
                mark++;
                ans++;
            }else if (grid[i][j] == '0')
                continue;
            for (auto c : dic){
                int i2 = i + c[0], j2 = j + c[1];
                if (i2 < 0 || i2 >= row || j2 < 0 || j2 >= col || grid[i2][j2] == '0')
                    continue;
                if (grid[i2][j2] !== '1')
                    ans--;
                grid[i2][j2] = grid[i][j];
            }
        }
    }
    return mark - 1;
}

遇上“工”字形状就会出问题，没办法还是得DFS。

在循环结构时，边界条件、相应+1-1可以借助构造一个包含01、10、0-1、-10二维数组将代码写的更好看，简洁。但是像DFS这样的递归结构，不便于构造辅助数组，会占用较多栈空间。

// 通过，DFS
void dfshelper(vector<vector<char>>& grid, int i, int j){
    if (i<0 || i>= grid.size() || j<0 || j>= grid[0].size() || grid[i][j] != '1')
        return;
    grid[i][j] = '2';
    dfshelper(grid, i, j+1);
    dfshelper(grid, i, j-1);
    dfshelper(grid, i+1, j);
    dfshelper(grid, i-1, j);
}

int numIslands(vector<vector<char>>& grid) {
    int mark=0;
    if (grid.empty() || grid[0].empty())
        return 0;
    int row = grid.size();
    int col = grid[0].size();
    for (int i=0;i<row;i++){
        for (int j=0;j<col;j++){
            if (grid[i][j] == '1'){
                mark++;
                dfshelper(grid, i, j);
            }
        }
    }
    return mark;
}

排序和搜索

合并区间

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

一开始没有想到排序，陷入一种递归的尴尬境地，排序后就可以保证前面定好的区间不会变动。

vector<Interval> merge(vector<Interval>& intervals) {
    int i=1,j=0,n=intervals.size();
    if (n<1) return {};
    sort(intervals.begin(), intervals.end(), cmp);
    vector<Interval> res;
    res.push_back(intervals[0]);
    for(i;i<n;i++){
        if (res[j].end < intervals[i].start){
            res.push_back(intervals[i]);
            j++;
        }else if (res[j].end <= intervals[i].end){
            res[j].end = intervals[i].end;
        }
    }
    return res;
}

相比起vector.erase，新建一个vector速度更快，也能避免修改原数组。
其实在很多时候（尤其链表、数组），想象成两个组，比较方便，实现起来也容易，“将正确的结果放入到一个新组”。（不一定是复制两份，比如链表，只需要一个新的头指针，然后往后加）

前k个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
c++中有一个pair对象，也是stl map默认的分配模式，因为map不是线性排列，不能应用sort，所以先转换成vector，同时为pair对象写一个compare方法。
用map记录各个元素出现次数。

c++11提供了lambda函数支持。（很酷炫）

vector<int> topKFrequent(vector<int>& nums, int k) {
    map<int, int> dic;
    for (auto i : nums){
        dic[i]++;
    }
    vector<pair<int, int>> vec(dic.begin(), dic.end());
    sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
    vector<int> r;
    for (int i=0;i<k;i++){
        r.push_back(vec[i].first);
    }
    return r;
}

数组中的第k个最大元素
- 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
- 对vector进行sort即可，但由于是引用传参，这样做就不是纯函数了。
- 与其对vector进行copy，不如用优先队列，也就是堆结构去存储。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  int findKthLargest(vector<int>& nums, int k) {
  priority_queue<int> q;
  for (auto &c : nums){
  q.push(c);
  }
  for (k;k>1;k--){
  q.pop();
  }
  return q.top();
  }

搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
首先应该确定用二分搜索，然后二分在于要选择左右段。
没有思路时可以把旋转后的几种情况列出，取中间数观察（然而一开始连旋转都没看懂）。
结论是：中间数的左右总有一段是有序的，不会都无序，找出有序的一段，比较首尾和目标，即可知道是选这一段还是另一段。
二分搜索要正确结束的确不容易，我个人更习惯left<right，然后在mid==left的时候break，循环外再检验一次right值。

后来我觉得这样写还是有点多余，在重新整理了二分查找的方法后，意识到left<=right，然后移动时多移一个位置，更简洁。

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

链表

奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

应当保持奇数节点和偶数节点的相对顺序。链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

ListNode* oddEvenList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* odd = head;
    ListNode* evenhead = head->next;
    ListNode* even = evenhead;
    while(even && even->next)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    odd->next = evenhead;
    return head;
}

回溯算法

生成括号

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
即要求括号成对，左括号总是先于右括号出现一次。
假如想象成一个一个括号生成，则有如下两个情况：
1. 左括号数<n，可以添加左括号
2. 左括号数>右括号数，可以添加右括号

使用字典实现记录左括号数即可。

vector<string> generateParenthesis(int n) {
    unordered_map<string, int> temp1, temp2;
    temp1["("] = 1;
    for (int k=n*2-1;k>0;k--){
        for (auto i : temp1){
            if (i.second < n){
                temp2[i.first+"("] = i.second + 1;
            }
            if (n*2 - k - i.second*2 < 0){
                temp2[i.first+")"] = i.second;
            }
        }
        temp1.swap(temp2);
        temp2.clear();
    }
    vector<string> r;
    for (auto i : temp1){
        r.push_back(i.first);
    }
    return r;
}

也可以用递归，这时靠栈空间去记录左括号的数量和字符串。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。
2>abc, 3>def…
因为映射关系是符合字母顺序的（ascii码有序），可以只构造首字母，然后+1，进位，直至不能在增大，即所有结果都出现过。

比如”23”替换为”ad”->”ae”->”af”->”bd”->”be”->”bf”->”cd”->”ce”->”cf”->终止。

vector<string> letterCombinations(string digits) {
    vector<string> r;
    char left[9] = {'a','d','g','j','m','p','t','w','z'+1};
    int len = digits.size();
    if (len < 1)
        return {};
    string copy(digits);
    for (int i=0;i<len;i++)
        copy[i] = left[copy[i]-'2'];
    r.push_back(copy);
    while(1)
    {
        int p = len - 1;
        copy[p]++;
        while(copy[p] == left[digits[p]-'1'])
        {
            if (p == 0)
                return r;
            copy[p] = left[digits[p]-'2'];
            p--;
            copy[p]++;
        }
        r.push_back(copy);
    }
}

单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
使用DFS。
防止重复使用，可以在代码中递归部分的前后，加上修改当前判断值和还原当前值的两行，此处因为是char类型，使用了异或操作，其他类型用局部变量存储也可。
要注意边界条件。

获取vector size的方法，也没有想象中那么慢，不用太在意。

bool exist(vector<vector<char>>& board, string word) {
    int row=board.size(), len=word.size();
    if (row <= 0 || len <= 0){
        return false;
    }
    int col=board[0].size();
    for (int i=0;i<row;i++){
        for (int j=0;j<col;j++){
            if (board[i][j] == word[0] && helper(board, word, i, j, 0)){
                return true;
            }
        }
    }
    return false;
}
bool helper(vector<vector<char>>& board, string & word, int i, int j, int pos){
    if (pos == word.size())
        return true;
    else if (i<0 || i>= board.size() || j<0 || j>=board[0].size() || board[i][j] != word[pos])
        return false;
    board[i][j] ^= 255;
    bool result = (helper(board, word, i+1, j, pos+1)
                  || helper(board, word, i, j+1, pos+1)
                  || helper(board, word, i, j-1, pos+1)
                  || helper(board, word, i-1, j, pos+1));
    board[i][j] ^= 255;
    return result;
}

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

生成法。

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    res.push_back({});
    for (int & num : nums){
        int size = res.size();
        for (int i=0;i<size;i++){
            vector<int> temp = res[i];
            temp.push_back(num);
            res.push_back(temp);
        }
    }
    return res;
}

排序和搜索

寻找峰值

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。
你的解法应该是 O(logN) 时间复杂度的。

因为数组两端是负无穷，则峰值一定存在，每次取数组中间的数，和它左右的数比较。假设三个数为a,b,c，如果a（c）大于b，则左（右）区间一定有峰值。

int findPeakElement(vector<int>& nums) {
    int l=0,r=nums.size()-1;
    while(r-l>1)
    {
        int mid = (l+r)/2;
        if (nums[mid] < nums[mid-1])
            r=mid-1;
        else if (nums[mid] < nums[mid+1])
            l=mid+1;
        else
            return mid;
    }
    if (l==r)
        return l;
    else if (nums[r] > nums[l])
        return r;
    else
        return l;

探索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

从左下角或者右上角开始就很简单。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty())
      return false;  
    int row=0;  
    int col=matrix[0].size()-1;  
    while(row<matrix.size() && col>-1){  
        if(matrix[row][col] > target)
            col--;  
        else if (matrix[row][col] < target)
            row++;  
        else 
            return true;
    }
    return false;
}

数学

x的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
用二分搜索，找到两个相邻数的平方值区间包含目标数x。
(right-left)/2+left的写法可以避免溢出。

x/mid而不是mid**2也是为了避免溢出。

int mySqrt(int x) {
    if(x<=1) return x;
    int left=0,right=x;
    while(left<right){
        int mid=left+(right-left)/2;
        if(x/mid>=mid) left=mid+1;
        else right=mid;
    }
    return right-1;
}

Pow(x,n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
x**(a+b) = (x**a) * (x**b)

而任何一个整数都可以被分解为2的幂次和

double myPow(double x, int n) {
    if (x == 0)
        return 0;
    else if (n < 0)
        x = 1 / x;
    double res = 1;
    while (n != 0){
        if (n % 2)
            res *= x;
        n /= 2;
        x *= x;
    }
    return res;
}

分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。
INT_MIN / -1 是执行出错，属于未定义错误。
除了溢出，还要考虑正负号，如果将被除数和除数取绝对值，又有abs(INT_MIN)的风险。
直接将被除数和除数都扩展为long long类型比较暴力。

因为要判断是否加负号，加小数点，所以第一次除，单独算在循环体前面。

string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0)
        return "0";
    string r;
    if ((numerator >> 31) != (denominator >> 31))
        r = "-";
    long t = numerator, d = denominator;
    t = abs(t), d = abs(d);
    unordered_map<long, int> m;
    m[t] = r.size();
    r = to_string(t / d);
    t = (t % d) * 10;
    r += t == 0 ? "" : ".";
    while (t != 0){
        if (m.count(t) == 1){
            r.insert(m[t], "(");
            r += ")";
            break;
        }
        m[t] = r.size();
        r += to_string(t / d);
        t = (t % d) * 10;
    }
    return r;
}

两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。

从最大的2幂次开始，逐个减掉。

int divide(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1)
        return INT_MAX;
    long dd = abs((long)dividend), dr = abs((long) divisor);
    long res = 0;
    while (dd >= dr){
        long a = dr, count = 1;
        while (a<<1 < dd){a<<=1;count<<=1;}
        res+= count;
        dd-=a;
    }
    if ((dividend ^ divisor)>>31){
        return -res;
    }
    return res;
}

阶乘后的零
- 给定一个整数 n，返回 n! 结果尾数中零的数量。
- 实际上只有2*5才会产生0，由于2一定多于5，统计总共有多少个5就可以。
  1
  2
  3
  4
  5
  6
  7
  int trailingZeroes(int n) {
  int r = 0;
  while (n>=5){
  r += (n /= 5);
  }
  return r;
  }

动态规划

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
现实中的硬币面值组合，是可以组成任意数字的，所以只要从大到小算就可以了。
题目的意思显然还会有凑不出来的情况，也就是说，这里不应关心硬币的面值组合和顺序，而是当作整体。

这样一来，和限定每次能走几步，能否走到某个点上的位置，是一样的问题。

int coinChange(vector<int>& coins, int amount) {
    if (amount < 1)
        return 0;
    vector<int> step(amount+1, INT_MAX);
    for (auto & c : coins){
        if (c > 0 && c <= amount)
            step[c] = 1;
    }
    for (int i=1;i<=amount;i++){
        for (auto & c : coins){
            if (i-c > 0 && step[i-c] != INT_MAX){
                step[i] = min(step[i], step[i-c]+1);
            }
        }
    }
    if (step[amount] == INT_MAX)
        return -1;
    else
        return step[amount];
}

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

这题首先考虑用动态规划做，n2比较容易达到，考虑data[i]表示从nums[0]到nums[i]，并且以i结尾的上升子序列的长度。

int lengthOfLIS(vector<int>& nums) {
    int re = 1;
    if (nums.size() < 1)
        return 0;
    vector<int> data(nums.size(), 1);
    for (int i=1;i<nums.size();i++){
        for (int j=i-1;j>=0;j--){
            if (nums[j] < nums[i]){
                data[i] = max(data[i], data[j] + 1);
                re = max(re, data[i]);
            }
        }
    }
    return re;
}

O(nlogn)的一个办法，贪心+二分搜索。维护一个数组low，low[i]表示LIS长度为i时的最小结尾元素。

只需要遍历一遍，如果新元素比LIS结尾还大，就添加到low数组末尾，如果不能直接添加，则更新中间的某个位置。

int lengthOfLIS(vector<int>& nums) {
    int n=nums.size(), r=0;
    vector<int> low(n, 0);
    for (int x : nums) {
        int i = 0, j = r;
        while (i < j) {
            int mid = (i+j)/2;
            if (low[mid] < x)
                i = mid + 1;
            else
                j = mid;
        }
        low[i] = x;
        if (i == r)
            r++;
    }
    return r;
}