Item 2: 用 consts, enums 和 inlines 取代 #defines

使用define的缺陷:

  • 1 预处理器盲目多次拷贝替换宏名,导致产生更多的代码 -> 使用const常量解决
  • 2 宏函数的嵌套需要打上括号 -> 使用内连函数达到相同的性能解决

使用enum替换const的用例:

1
2
3
4
5
6
7
8
class GamePlayer {
private:
enum { NumTurns = 5 }; // "the enum hack" - makes
// NumTurns a symbolic name for
5
int scores[NumTurns]; // fine
...
};

优点有其二:

  • 1 避免常量的指针和引用被取走
    首先,the enum hack
    的行为在几个方面上更像一个 #define 而不是 const,而有时这正是你
    所需要的。例如:可以合法地取得一个 const 的 address(地址),
    但不能合法地取得一个 enum 的 address(地址),这正像同样不能
    合法地取得一个 #define 的 address(地址)。如果你不希望人们得
    到你的 integral constants(整型族常量)的 pointer(指针)或
    reference(引用),enum(枚举)就是强制约束这一点的好方法。
  • 2 被模板元编程大量使用,属于实用主义

总结:

a. 对于 simple constants(简单常量),用 const objects(const 对
象)或 enums(枚举)取代 #defines。

b. 对于 function-like macros(类似函数的宏),用 inline
functions(内联函数)取代 #defines

Item 3: 只要可能就用 const

1 const用于指针,迭代器:

  • 1 用于指针:
    如果 const 出现在星号左边,则指针 pointed to(指向)的内容为 constant(常量);
    如果 const 出现在星号右边,则 pointer itself(指针自身)为
    constant(常量);如果 const 出现在星号两边,则两者都为
    constant(常量)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    char greeting[] = "Hello";
    char *p = greeting; // non-const pointer,
    // non-const data
    const char *p = greeting; // non-const pointer,
    // const data
    char * const p = greeting; // const pointer,
    // non-const data
    const char * const p = greeting; // const pointer,
    // const data
    void f1(const Widget *pw); // f1 takes a pointer to a
    // constant Widget object
    void f2(Widget const *pw); // so does f2
  • 2 用于迭代器:
    声明一个iterator 为 const 就类似于声明一个 pointer(指针)为 const(也就是说,声明一个 T* const pointer(指针)):不能将这个 iterator 指向另外一件不同的东西,但是它所指向的东西本身可以变化。
    若需要iterator指向的东西不能变,使用const_iterator即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    std::vector<int> vec;
    ...
    const std::vector<int>::iterator iter = // iter acts like a T*
    const
    vec.begin();
    *iter = 10; // OK, changes what iter
    points to
    ++iter; // error! iter is const
    std::vector<int>::const_iterator cIter = // cIter acts like a
    const T*
    vec.begin();
    *cIter = 10; // error! *cIter is const
    ++cIter; // fine, changes cIter

    2 用于函数

  • 1 返回值和传参是const
    避免了=和==的错误

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Rational { ... };
    const Rational operator*(const Rational& lhs, const Rational& rhs);

    Rational a, b, c;
    ...
    (a * b) = c; // invoke operator= on the
    // result of a*b!

    if (a * b = c) ... // oops, meant to do a comparison!

    参数在不会被改变的时候就应该传入const

  • 2 const member functions(const 成员函数)
    有两个原因:

    • 2.1 它使一个 class(类)的 interface(接口)更容易被理
      解。知道哪个函数可以改变 object(对象)而哪个不可以是很重要
      的。
    • 2.2 它们可以和 const objects(对象)一起工作。因为,书写
      高效代码有一个很重要的方面,就像 Item 20 所解释的,提升一个
      C++ 程序的性能的基本方法就是 pass objects by reference-to const(以传引用给 const 的方式传递一个对象)。

具体看如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class TextBlock {
public:
...
const char& operator[](std::size_t position) const // operator[]
for
{ return text[position]; } // const objects

char& operator[](std::size_t position) // operator[]
for
{ return text[position]; } // non-const objects

private:
std::string text;
};
// ------------------- 1 -----------------------
TextBlock tb("Hello");
std::cout << tb[0]; // calls non-const
// TextBlock::operator[]
const TextBlock ctb("World");
std::cout << ctb[0]; // calls const
TextBlock::operator[]

// -------------------- 2 ----------------------
void print(const TextBlock& ctb) // in this function, ctb is
const
{
std::cout << ctb[0]; // calls const TextBlock::operator[]
...
}
// --------------------- 3 ---------------------
std::cout << tb[0]; // fine — reading a
// non-const TextBlock
tb[0] = 'x'; // fine — writing a
// non-const TextBlock
std::cout << ctb[0]; // fine — reading a
// const TextBlock
ctb[0] = 'x'; // error! — writing a
// const TextBlock

3 const的二进制常量性和逻辑常量性

bitwise(二进制位)const 派别坚持认为,一个 member function(成
员函数),当且仅当它不改变 object(对象)的任何 data
members(数据成员)(static(静态的)除外),也就是说如果不改
变 object(对象)内的任何 bits(二进制位),则这个 member
function(成员函数)就是 const。bitwise constness(二进制位常量
性)的一个好处是比较容易监测违例:编译器只需要寻找对 data
members(数据成员)的 assignments(赋值)。实际上,bitwise
constness(二进制位常量性)就是 C++ 对 constness(常量性)的
定义,一个 const member function(成员函数)不被允许改变调用它
的 object(对象)的任何 non-static data members(非静态数据成
员)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class CTextBlock {
public:
...
char& operator[](std::size_t position) const // inappropriate
(but bitwise
{ return pText[position]; } // const)
declaration of
// operator[]
private:
char *pText;
};
// ----------------------------------------------
const CTextBlock cctb("Hello"); // declare constant object
char *pc = &cctb[0]; // call the const operator[]to get a
// pointer to cctb's data
*pc = 'J'; // cctb now has the value "Jello"

上述过程中:你用一个 particular value(确定值)创建一个
constant object(常量对象),然后你只是用它调用了 const member
functions(成员函数),但是你还是改变了它的值!
这就引出了 logical constness(逻辑常量性)的概念。这一理论的信
徒认为:一个 const member function(成员函数)可能会改变调用它
的 object(对象)中的一些 bits(二进制位),但是只能用客户无法
察觉的方法。例如,你的 CTextBlock class(类)在需要的时候可以
储存文本块的长度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class CTextBlock {
public:
...
std::size_t length() const;
private:
char *pText;
// 可以解脱的代码
// mutable std::size_t textLength; // these data members may
// mutable bool lengthIsValid; // always be modified, even
in
std::size_t textLength; // last calculated length of
textblock
bool lengthIsValid; // whether length is currently
valid
};
std::size_t CTextBlock::length() const
{
if (!lengthIsValid) {
textLength = std::strlen(pText); // error! can't assign to textLength
lengthIsValid = true; // and lengthIsValid in a const
} // member function
return textLength;
}

上述代码会由于成员函数length()后面跟了一个const使得编译器保证了类的二进制常量性,那么想要修复这个问题,则只用mutable将其从中解脱。

4 const和non-const函数有相同实现的单向调用

为避免代码重复,则non版本调用const版本,具体例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TextBlock {
public:
...
const char& operator[](std::size_t position) const // same as
before
{
...
...
...
return text[position];
}
char& operator[](std::size_t position) // now just calls
const op[]
{
return
const_cast<char&>( // cast away const on
// op[]'s return type;
static_cast<const TextBlock&>(*this)[position] // add const to *this's type; // call const version of op[]
); }
...
};

cosnt_cast去掉const属性,然后用static_cast将this转为const去调用对应的const函数。
而不能用const成员函数去调用非const版本的是因为需要将cosnt的
this转为non-const的this,会导致值发生改变,这就导致const成员函数失去本身意义。

总结:

将某些东西声明为 const 有助于编译器发现使用错误。const 能
被用于任何 scope(范围)中的 object(对象),用于 function
parameters(函数参数)和 return types(返回类型),用于整
个 member functions(成员函数)。

编译器坚持 bitwise constness(二进制位常量性),但是你应该
用 conceptual constness(概念上的常量性)来编程。

当 const 和 non-const member functions(成员函数)具有本质
上相同的实现的时候,使用 non-const 版本调用 const 版本可以
避免 code duplication(代码重复)。

1 有序集合

泛指set, map, pirority_queue等能够按照key进行排序,然后使用lower_bound和upper_bound来进行log(n)复杂度查询的基础数据结构
(注意priority_queue仅能够在堆顶进行操作)
示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
        set<int, std::less<int>> spareServers;
<被作者省略>
// request distribute, find the server
int tarServer = -1;
auto itr = spareServers.lower_bound(arrivalIdx % k);
// cout << "trying to find: " << arrivalIdx % k << endl;
if(itr != spareServers.end()) {
tarServer = *itr;
// cout << "find tar1: " << tarServer << endl;
} else { // search from the start just like search like a cycle
tarServer = *spareServers.lower_bound(0);
// cout << "find tar2: " << tarServer << endl;
}

2 具体示例

0363maxSumSubMatrix 最大子区域和

1 题目:

https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/

2 解题思路:

  • 1 普通思路:一维前缀和,按行计算前缀和,使用m x n的矩阵存储,然后计算矩形区域,则只需要O(m)的计算复杂度
  • 2 优化:二维前缀和,pre[i][j]存储的是0,0到i,j处的矩形区域和,那么计算方式为:

    preMat2[i+1][j+1] = preMat2[i][j+1] + preMat2[i+1][j] - preMat2[i][j] + matrix[i][j];

  • 3 使用二位前缀和去计算子区域的和,搜索子区域的方式:
    • 3.1 对于每个子区域的上下边界搜索左右边界,上下左边界搜索复杂度为o(n^2), 而后搜索左右边界,对于每一个右边界O(n),搜索左边界,什么样的左边界?left满足sum(up, down, 0, right) - k <= sum(up, down, 0, left), 也就是在[0, right]的范围内找到最小的大于sum(up, down, 0, right) - k的left,在遍历的过程中使用set存所有的sum(up, down, 0, right), 在这个set里面找left,使用lower_bound函数,只需要log(n)复杂度,于是总复杂度为 o(m^2 * nlog(n))
    • 3.2 上述核心思想: 本来需要找right和left的对子,但是现在借助k,找left就变成在right的历史中搜索即可
      • 3.2.1 原来思想:sum(up, down, 0, right) - sum(up, down, 0, left) <= k
      • 3.2.2 新的思想:sum(up, down, 0, right) - k <= sum(up, down, 0, left)
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        class Solution {
        public:
        static constexpr int matLen = 102;
        vector<vector<int>> preMat; // 2d prefix sum
        int m = -1;
        int n = -1;
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        // cal 2d prefix sum
        m = matrix.size();
        n = matrix[0].size();
        preMat.resize(m+1, vector<int>(n+1, 0));
        for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
        preMat[i+1][j+1] = preMat[i][j+1] + preMat[i+1][j] - preMat[i][j] + matrix[i][j];
        // cout << preMat[i+1][j+1] << endl;
        }
        }

        // for each up and down, find max l,r
        int res = INT_MIN;
        for(int d = 0; d < m; ++d) {
        for(int u = d; u >= 0; --u) {
        set<int> lSet = {0};
        for(int r = 0; r < n; ++r) {
        int sumRight = sumRegion(u, d, 0, r);
        set<int>::iterator lbPtr = lSet.lower_bound(sumRight - k);
        lSet.insert(sumRight);
        if(lbPtr != lSet.end()) {
        res = max(res, sumRight - *lbPtr);
        }
        }
        }
        }

        return res;
        }

        int sumRegion(int up, int down, int left, int right) {
        return preMat[down+1][right+1] - preMat[down+1][left] - preMat[up][right+1] - preMat[up][left];
        }
        };

0699fallingSquares 掉落的方块

1 题目:

https://leetcode-cn.com/problems/falling-squares/

2 解题思路:

  • 1 普通思路:使用一维数组模拟每个位置方块高度,复杂度为o(N^2),由于N很大,所以会超时
  • 2 优化:使用坐标压缩,将所有方块的边界存储在2000以内(因为一共就1000个方块),然后更新高度就按照2000以内去更新即可
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    class Solution {
    public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
    // coordinate compression
    set<int, std::less<int>> coords;
    for(vector<int>& coord : positions) {
    coords.insert(coord[0]);
    coords.insert(coord[0] + coord[1] - 1);
    }

    unordered_map<int, int> borderToIdx;
    int t = 0;
    for(auto& i : coords) {
    borderToIdx[i] = t++;
    }

    // cal heights
    vector<int> heights(t);
    vector<int> res;
    int curHeightest = INT_MIN;
    for(vector<int>& square : positions) {
    int l = borderToIdx[square[0]];
    int r = borderToIdx[square[0] + square[1] - 1];
    int h = square[1];
    int updatedHeight = update(l, r, h, heights);
    curHeightest = max(curHeightest, updatedHeight);
    res.emplace_back(curHeightest);
    }
    return res;
    }

    // update and return updated height of [l, r]
    int update(int l, int r, int h, vector<int>& heights) {
    int oldHeight = INT_MIN;
    for(int i = l; i <= r; ++i) {
    oldHeight = max(oldHeight, heights[i]);
    }
    int newHeight = INT_MIN;
    for(int i = l; i <= r; ++i) {
    heights[i] = oldHeight + h;
    }
    return oldHeight + h;
    }
    };

0715 Range 模块 rangeModule

1 题目:

https://leetcode-cn.com/problems/range-module/

2 解题思路:

  • 1 普通思路:使用map记录这些离散的区间
    • 1.1 添加、删除: 遍历map,看map的每一个区间和当前区间的关系,这样处理最为合适
    • 1.2 查询:使用upper_bound查询到第一个(左侧)比目标的left小的区间,然后看目标的left和right是否在map对应的区间内部
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      class RangeModule {
      public:
      map<int, int, std::less<int>> intervals;
      RangeModule() {

      }

      void addRange(int left, int right) {
      if(intervals.size() == 0) {
      intervals[left] = right;
      print();
      return ;
      }
      for(auto it = intervals.begin(); it != intervals.end(); ++it) {
      if(it->first >= left) {
      if(it->first > right) {
      continue;
      }
      while(it != intervals.end() && it->second <= right) {
      it = intervals.erase(it);
      }
      if(it == intervals.end()){
      intervals[left] = right;

      } else {
      if(it->first <= right) {
      int newRight = it->second;
      intervals.erase(it);
      intervals[left] = newRight;
      }else {
      intervals[left] = right;
      }
      }
      print();
      return;
      } else { // it->first < left
      if(it->second < left) {
      continue;
      }
      int newLeft = it->first;
      while(it != intervals.end() && it->second <= right) {
      it = intervals.erase(it);
      }
      if(it == intervals.end()){
      intervals[newLeft] = right;
      } else {
      if(it->first <= right) {
      int newRight = it->second;
      intervals.erase(it);
      intervals[newLeft] = newRight;
      }else {
      intervals[newLeft] = right;
      }
      }
      print();
      return;
      }
      }
      intervals[left] = right;
      print();
      }

      bool queryRange(int left, int right) {
      if(intervals.empty()) {
      return false;
      }

      auto lBig = intervals.upper_bound(left);
      if(lBig != intervals.begin()) {
      --lBig;
      return lBig->second >= right;
      } else {
      return false;
      }
      return false;
      }

      void removeRange(int left, int right) {
      // for(auto it = intervals.begin(); it != intervals.end(); ++it) {
      // for(int i = 0)
      // }

      auto lBig = intervals.lower_bound(left);
      int newLeft = 0;
      if(lBig != intervals.begin()) {
      // cout << "d1.5" << endl;
      --lBig;
      if(right < lBig->second) {
      intervals[right] = lBig->second;
      intervals[lBig->first] = left;
      print();
      return ;
      } else {
      // cout << "d2" << endl;
      if(lBig->second > left) {
      // cout << "d2.5" << endl;
      intervals[lBig->first] = left;
      }
      }
      ++lBig;

      while (lBig != intervals.end() && lBig->second < right) {
      lBig = intervals.erase(lBig);
      }
      if(lBig != intervals.end()) {
      if(lBig->first < right) {
      int secondRight = lBig->second;
      intervals.erase(lBig);
      intervals[right] = secondRight;
      }
      }
      } else {
      while (lBig != intervals.end() && lBig->second < right) {
      lBig = intervals.erase(lBig);
      }
      if(lBig != intervals.end()) {
      if(lBig->first < right) {
      int secondRight = lBig->second;
      intervals.erase(lBig);
      intervals[right] = secondRight;
      }
      }
      }

      print();

      }

      void print() {
      // cout << "-----st-----" << endl;
      // for(auto it = intervals.begin(); it != intervals.end(); ++it) {
      // cout << it->first << " " << it->second << endl;
      // }
      // cout << "-----ed-----" << endl;
      }
      };

      /**
      * Your RangeModule object will be instantiated and called as such:
      * RangeModule* obj = new RangeModule();
      * obj->addRange(left,right);
      * bool param_2 = obj->queryRange(left,right);
      * obj->removeRange(left,right);
      */

0850. 矩形面积 II

1 题目:

https://leetcode-cn.com/problems/rectangle-area-ii/solution

2 解题思路:

  • 1 参考官方思路的扫描线:https://leetcode-cn.com/problems/rectangle-area-ii/solution/ju-xing-mian-ji-ii-by-leetcode/
  • 2 总结过程:
    • 2.1 将一个矩形看成x1,x2,y1,ST; x1,x2,y2,ED;的两条线
    • 2.2 而后用active记录还没有遇到ED的那些矩形的第一个扫描线集合,每回新来了一根线,则将active中的所有线和当前线计算对应面面积加起来
    • 2.3 当active中遇到了矩形的ED,则将active中对应的矩形的ST删除
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      class Solution {
      public:
      static constexpr long long bigPrime = 1000000007;
      int rectangleArea(vector<vector<int>>& rectangles) {
      // lines
      int ST = 0;
      int ED = 1;

      vector<vector<int>> lines;
      for(auto& vec : rectangles) {
      lines.emplace_back(vector<int>{vec[0], vec[2], vec[1], ST});
      lines.emplace_back(vector<int>{vec[0], vec[2], vec[3], ED});
      }

      // sort the lines by the y
      sort(lines.begin(), lines.end(),
      [](vector<int>& a, vector<int>& b) {
      return a[2] < b[2];
      });

      // scan the lines
      vector<vector<int>> actives;
      long long res = 0;
      int lastY = lines[0][2];
      for(auto& line : lines) {
      int curY = line[2], type = line[3], x1 = line[0], x2 = line[1];
      int width = 0;
      int actX = -1;

      // actives: those opend lines, sorted by y
      for(auto& act : actives) {
      // cout << "act: " << act[0] << " " << act[1] << endl;
      actX = max(actX, act[0]);
      width += max(act[1] - actX, 0);
      actX = max(actX, act[1]);
      }

      res += static_cast<long long>(width) * (curY - lastY) % bigPrime;
      // cout << "w: " << width << endl;

      // add new actives
      if(type == ST) {
      actives.emplace_back(vector<int>{x1, x2, curY, type});
      // cout << "insert x1,2: " << x1 << " " << x2 << endl;
      // sort the opend lines of the started points
      sort(actives.begin(), actives.end(),
      [](vector<int>& line1, vector<int>& line2) {
      return line1[0] < line2[0];
      });
      } else {
      // find the active and rm it
      for(int i = 0; i < actives.size(); ++i) {
      if(actives[i][0] == x1 && actives[i][1] == x2) {
      actives.erase(actives.begin() + i);
      // cout << "earse x1,2: " << x1 << " " << x2 << endl;
      break;
      }
      }
      }

      lastY = curY;
      }

      return res % bigPrime;

      }

      vector<vector<int>> getSkyLine(vector<vector<int>>& buildings) {
      function<bool(pair<int, int>&, pair<int, int>&)> cmp =
      [](pair<int, int>& a, pair<int, int>& b) {
      return a.second < b.second;
      };

      // <rightBound, height>
      priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(pair<int, int>&, pair<int, int>&)> > queue(cmp);

      vector<int> bounds;
      vector<vector<int>> res;
      int n = buildings.size();
      for(int i = 0; i < n; ++i) {
      bounds.emplace_back(buildings[i][0]);
      bounds.emplace_back(buildings[i][1]);
      }

      sort(bounds.begin(), bounds.end(), std::less<int>());
      // std::cout << "c1" << endl;

      int j = 0;
      for(auto& curBound : bounds) {
      // std::cout << "c " << j << endl;
      // push buildings lefter than curBound until one righter meet
      while(j < buildings.size() && curBound >= buildings[j][0]) {
      queue.push(make_pair(buildings[j][1], buildings[j][2]));
      ++j;
      }
      // std::cout << "c " << "adf" << endl;

      // pop out those rec unrelevant
      while(!queue.empty() && curBound >= queue.top().first) {
      queue.pop();
      }

      int curBoundHeight = queue.empty() ? 0 : queue.top().second;

      // if(res.size() == 0 || res.back()[1] != curBoundHeight) {
      // res.emplace_back(vector<int>{curBound, curBoundHeight});
      // }
      if(res.size() == 0 || res.back()[1] != curBoundHeight) {
      res.emplace_back(vector<int>{curBound, curBoundHeight});
      }
      }

      return res;
      }

      void print(vector<vector<int>>& vec) {
      for(auto& v : vec) {
      for(auto& i : v) {
      cout << i << " ";
      }
      cout << endl;
      }

      }
      };

0895maxFreqStack 最大频率栈

1 题目:

https://leetcode-cn.com/problems/maximum-frequency-stack/

2 解题思路:map/hash栈

  • 1 参考官方思路的扫描线:https://leetcode-cn.com/problems/maximum-frequency-stack/solution/zui-da-pin-lu-zhan-by-leetcode/
  • 2 总结过程:
    • 2.1 首先用map维持每一个变量的频率
      • 2.1.1 维持方法: push中对应的key加一,pop对应的key减一
    • 2.2 如何获得当前最大频率?
      • 2.2.1 在每个变量push和pop的时候我们可以获得对应的key的频率,那么所有的key的频率变动都是在push和pop执行完成之后,那么只需要用一个变量maxFreq维持最大频率即可
    • 2.3 知道最大频率,如何获得当前最大频率的变量?
      • 2.3.1 使用map<频率,频率对应的数的集合>来记录即可,然后用2.2中使用maxFreq获取最大频率对应的数字的集合,那如何从这个集合中获取在栈顶的数据呢?map<频率,频率对应的数的集合>中 频率对应的数的集合 使用stack去存就好了,因为stack的栈顶总是存着最新来的数据
    • 2.4 一个实例: 3,3,3都是push,那么在频率为1,2,3的栈中,很自然的都有一个3,自然体现在哪里呢?现在pop一下,频率为3对应的stack为空,然后最大频率变为2,然后2里面同样是3
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      class FreqStack {
      public:
      int opNum;
      map<int, int> opNumMap;
      map<int, int> freqMap;
      map<int, vector<int>*> groupByFreq;
      int maxFreq;
      FreqStack() {

      }

      void push(int val) {
      // cout << "pushing st: with max freq: " << maxFreq << endl;
      freqMap[val]++;
      if(groupByFreq[freqMap[val]] == nullptr) {
      groupByFreq[freqMap[val]] = new vector<int>();
      }
      groupByFreq[freqMap[val]]->emplace_back(val);
      maxFreq = max(maxFreq, freqMap[val]);
      // cout << "pushing done: " << val << "with maxFreq: " << maxFreq << endl;
      }

      int pop() {
      // cout << "pop st with maxFreq: " << maxFreq << endl;
      // find biggest frequency and most newly element to rm
      int popRes = groupByFreq[maxFreq]->back();
      groupByFreq[maxFreq]->pop_back();
      if(groupByFreq[maxFreq]->size() == 0) {
      delete groupByFreq[maxFreq];
      groupByFreq[maxFreq] = nullptr;
      --maxFreq;
      }
      // cout << "pop ed" << popRes << " with maxFreq: " << maxFreq << endl;
      freqMap[popRes]--;
      return popRes;
      }
      };

      /**
      * Your FreqStack object will be instantiated and called as such:
      * FreqStack* obj = new FreqStack();
      * obj->push(val);
      * int param_2 = obj->pop();
      */

1606busiestServers 找到处理最多请求的服务器

1 题目:

https://leetcode-cn.com/problems/find-servers-that-handled-most-number-of-requests/

2 解题思路:

  • 1 自然的思路:对于每一个到来的请求,我们将服务器分为两部分,一部分是空闲服务器,一部分是繁忙服务器
    • 1.1 如何快速找到空闲服务器?我们用set记录空闲服务器即可,两次使用lower_bound完成cycle查询
    • 1.2 如何记录繁忙服务器?在每一个请求到来以及处理完成,都可能出现繁忙服务器的改动和空闲服务器的改动,于是采用map<到期时间,相应服务器列表>来存储繁忙服务器
    • 1.3 如何处理请求处理完成时的服务器从繁忙变为空闲?
      • 1.3.1 采用小根堆存储当前所有繁忙服务器的到期时间,那么只需要在请求到来的时候,将所有比当前请求小的到期时间的繁忙服务器变为空闲即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
public:
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
// using small root heap to store the smallest avaliable server
// auto cmp = [](const int& a, const int b)
set<int, std::less<int>> spareServers;
map<int, vector<int>> busyServers;
priority_queue<int, vector<int>, std::greater<int>> dues;
vector<pair<int, int>> serverSumLoad;

for(int i = 0; i < k; ++i) {
spareServers.insert(i);
serverSumLoad.push_back(make_pair(i,0));
}

// deal request
int reqNum = arrival.size();
int arrivalIdx = 0;
for(int arrival : arrival) {
// cout << "req: " << arrival << "load: " << load[arrivalIdx] << endl;
// release servers
while(!dues.empty() && dues.top() <= arrival) {
int due = dues.top();
dues.pop();
vector<int>& toRelease = busyServers[due];
for(auto i : toRelease) {
spareServers.insert(i);
// cout << "releasing " << i << endl;
}
// busyServers.erase(due);
}

// abandon the request
if(spareServers.empty()) {
++ arrivalIdx;
// cout << "abandon!" << endl;
continue;
}

// request distribute, find the server
int tarServer = -1;
auto itr = spareServers.lower_bound(arrivalIdx % k);
// cout << "trying to find: " << arrivalIdx % k << endl;
if(itr != spareServers.end()) {
tarServer = *itr;
// cout << "find tar1: " << tarServer << endl;
} else { // search from the start just like search like a cycle
tarServer = *spareServers.lower_bound(0);
// cout << "find tar2: " << tarServer << endl;
}
spareServers.erase(tarServer);

// set the server to busy
int due = arrival + load[arrivalIdx];
if(busyServers.find(due) == busyServers.end()) {
vector<int> tmpVec = {tarServer};
busyServers[due] = tmpVec;
dues.push(due);
// cout << "init busy due : " << tarServer << " to " << due << endl;
} else {
busyServers[due].push_back(tarServer);
// cout << "add busy due : " << tarServer << " to " << due << endl;
}
serverSumLoad[tarServer].second ++;

++ arrivalIdx;
}

sort(serverSumLoad.begin(), serverSumLoad.end(),[](
const pair<int, int>& p1, const pair<int, int>& p2
) {
return p1.second > p2.second;
});

// for(int ed = 0; ed < serverSumLoad.size(); ++ed) {
// cout << "server: " << serverSumLoad[ed].first << " > " << serverSumLoad[ed].second << endl;
// }
int ed = 1;
vector<int> res = {serverSumLoad[0].first};


for(; ed < serverSumLoad.size(); ++ed) {
if(serverSumLoad[ed].second != serverSumLoad[0].second) {
break;
}
res.emplace_back(serverSumLoad[ed].first);
}

return res;
}
};

单调栈

其基本特性:

  • 1 单调栈的极值性质:单调递减栈的第一个字符为目前最大的元素,单调递增栈则相反; 关于目前的解释,由于单调栈是遍历整个数组出栈入栈的过程,假设目前遍历到节点i,则arr[:i]为目前单调栈遍历过的元素们,单调栈递增递减栈的第一个数字分别为arr[:i]的最大最小值
  • 2 单调栈的单调性:单调栈内的元素严格单调

1 单调栈写法

一下为求每个元素左侧最大值的一个示例:

1
2
3
4
5
6
7
8
9
10
vector<int> normalOrderMono;
int n = height.size();
vector<int> leftMax(n);
for(int i = 0; i < n; ++i){
while(!normalOrderMono.empty() && height[normalOrderMono.back()] <= height[i]) {
normalOrderMono.pop_back();
}
leftMax[i] = normalOrderMono.empty() ? height[i] : height[normalOrderMono[0]];
normalOrderMono.emplace_back(i);
}

示例

0000_interview_1712trapWater 接雨水

1 题目:

https://leetcode-cn.com/problems/volume-of-histogram-lcci/

2 解题思路:

  • 1 参照提示的一句话:

    每个长方形的顶部都有水,水的高度应与左侧最高长方形和右侧最高长方形的较小值相匹配,也就是说,water_on_top[i] = min(tallest_ bar(0->i), tallest_bar(i, n))。

  • 2 使用单调栈计算当前节点左侧(右侧)最大值
    • 2.1 很简单: 考虑单调栈的性质,单调递减栈的第一个字符为目前最大的元素,单调递增栈则相反,为最小元素
    • 2.2 关于目前的解释,由于单调栈是遍历整个数组出栈入栈的过程,遍历到节点i,则arr[:i]为目前单调栈遍历过的元素们,单调栈递增递减栈的第一个数字分别为arr[:i]的最大最小值
    • 2.3 由于需要统计右侧最大值,则我们只需要逆序遍历数组即可,最大值可以使用单调递减获得
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int trap(vector<int>& height) {
// using descending mono stack to find maxValue in left or right
vector<int> normalOrderMono;
vector<int> reverseOrderMono;
int n = height.size();
vector<int> leftMax(n);
vector<int> rightMax(n);
for(int i = n - 1; i >= 0; --i){
while(!reverseOrderMono.empty() && height[reverseOrderMono.back()] <= height[i]) {
reverseOrderMono.pop_back();
}
rightMax[i] = reverseOrderMono.empty() ? height[i] : height[reverseOrderMono[0]];
reverseOrderMono.emplace_back(i);
}

for(int i = 0; i < n; ++i){
while(!normalOrderMono.empty() && height[normalOrderMono.back()] <= height[i]) {
normalOrderMono.pop_back();
}
leftMax[i] = normalOrderMono.empty() ? height[i] : height[normalOrderMono[0]];
normalOrderMono.emplace_back(i);
}

int res = 0;
for(int i = 0; i < n; i++) {
res += max(min(leftMax[i], rightMax[i]) - height[i], 0);
}

return res;
}
};

2030. 含特定字母的最小子序列 smallestSubsequence

1 题目:

https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/

2 解题思路:

  • 1 考虑一个简单化的问题,选出长度为k的最小字典序的字符串,算法如下:
    • 1.1 采用单调栈维护一个递增栈,自然的保持了最小字典序
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      class Solution {
      public:
      string smallestSubsequence(string s, int k, char letter, int repetition) {
      // first, using monostack to get the min sub arr whose len = k
      // and check if there are rep's 'letter' in sub arr

      vector<int> mono; // abscending chars
      int n = s.size();
      int specialCharCnt = 0;
      int avaliableSpeChar = 0;
      for(auto c : s) {
      avaliableSpeChar += (c == letter);
      }


      for(int i = 0; i < n; ++i) {
      while(!mono.empty() && s[mono.back()] >= s[i] && mono.size() - 1 + n - i >= k) {
      specialCharCnt -= static_cast<int>(s[mono.back()] == letter);
      mono.pop_back();
      }

      mono.emplace_back(i);
      if(s[i] == letter) {
      --avaliableSpeChar;
      ++specialCharCnt;
      }
      }

      string res = "";
      for(auto i : mono){
      res += s[i];
      }

      return res;
      }
      };
  • 2 考虑另一个子问题,需要选出含有rep个特殊字符的子序列,可以使用一个队列存储特殊字符的下标,当队列长度达到rep个,则记为一个子序列
  • 3 将两个问题结合起来考虑就是是说:
    • 3.1 在递增栈构造的过程中,要保证当前位置后面剩余的特殊字符加上当前栈内的字符大于等于repetition,否则将不能出栈特殊字符(因为如果出栈则无法满足有repetition个特殊字符的要求
    • 3.2 经过3.1步骤,单调栈内含有我们的答案,但是一定有一些额外的字符存在,那么如下说明从栈内获得答案的方式:
      • 3.2.1 eg: 当aaabbbcccddd为输入,则单调栈为aaabbbcccddd,那么我们想要的结果为在至少有2个b的字符串,那么我们获得最终结果的方式为:在保证有大于repetition个letter的情况下,从尾部开始删除字符串直到单调栈内剩下k个字符即可
        1
        2
        3
        4
        "aaabbbcccddd"
        3
        "b"
        2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
// first, using monostack to get the min sub arr whose len = k
// and check if there are rep's 'letter' in sub arr

clock_t start,end;   //定义clock_t变量
start = clock();    //开始时间

string mono; // abscending chars
int n = s.size();
int specialCharCnt = 0;
int avaliableSpeChar = 0;
for(auto &c : s) {
avaliableSpeChar += (c == letter);
}


for(int i = 0; i < n; ++i) {
while(!mono.empty() && mono.back() > s[i] && mono.size() - 1 + n - i >= k) {
if(mono.back() == letter) {
// when not enough special letter, we do not pop special char
if(avaliableSpeChar <= repetition - specialCharCnt) {
break;
}
--specialCharCnt;
}
mono.pop_back();
}

mono.push_back(s[i]);
if(s[i] == letter) {
--avaliableSpeChar;
++specialCharCnt;
}
}

start = clock();    //开始时间
string res = "";
// eliminate some extra chars reversely
int delNum = mono.size() - k;
// cout << "letter Cnt: " << specialCharCnt << endl;
for(int i = mono.size() - 1; i >= 0; --i){
// make sure there are more than rep's 'letter'
if(delNum != 0 ) {
if(specialCharCnt > repetition) {
specialCharCnt -= (mono[i] == letter);
--delNum;
continue;
} else {
if(mono[i] != letter) {
--delNum;
continue;
}
}
}
// spend: 0.311s
// res = mono[i] + res; // this spend two much time, ocuppy nearly 100% time! so we change our policy
// spend: 0.000153s, 1000 times faster!
res.push_back(mono[i]);
}

reverse(res.begin(), res.end());
end = clock(); //结束时间
cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl; //输出
return res;
}
};


3 关于string的+和push_back

如果是一个字符一个字符的话,使用push_back会比+快1000倍!如上代码可以自己尝试统计

1
2
3
4
// spend: 0.311s
// res = mono[i] + res; // this spend two much time, ocuppy nearly 100% time! so we change our policy
// spend: 0.000153s, 1000 times faster!
res.push_back(mono[i]);

0321 拼接最大数

1 题目

https://leetcode-cn.com/problems/longest-duplicate-substring/

2 解题思路

  • 1 首先分解问题:
    • 1.1 从长度为m和n(假设m <= n)中的字符串里选出k个,然后这个字串要求最大,遍历的思路:
      • 1.2 首先一共要选k个,自然想到从m和n中各挑选几个?那就是遍历了,m中的挑选长度的起点为: max(0, k - n),最少一个不挑,然后从m中挑的个数身下还有k - m个一定能够从n中挑出,所以起点是从0到k-n,(为什么区最大值?因为当n,m均大于k的时候,k-n为负数),挑选终点:自然是k,或者没有那么多可以调k个,则挑m个,则min(k, m)
      • 1.3 那么已经知道所有从m,n中挑选出k个字符串的方法,那么对于每一个方法,如何获取最大字符串呢?其实就是分别从该方法的m和n串中各选出他们的最大字串,然后合并即可,于是问题转化为:从m中如何选出某个长度记为l的最大字串?
        • 1.3.1 我们考虑一个使用单调递减栈,因为它的栈顶总是当前字符串最大的值,然后后面都是递减的,这正是我们需要的,比如 9 1 2 5 8 3选择3个的时候,使用单调栈可以直接获得9,8,3,但是有个问题,比如从 9 1 2 5 8,单调栈遍历完则为9 5,这3个没选够,所以何时停止从单调栈里弹出呢?遍历位置以及后面剩余的元素刚好够挑选长度的时候,就不再弹出了(即使单调栈内的元素已经不单调了)
      • 1.4 在下一个问题,对于一个挑选方法,m中挑选l个,n中挑选k-l个,分别得到一个最大字串,如何合并成最终字串呢?
        • 1.4.1 其实很简单,两个字符串分别维护一个head叫ha,hb吧,若ha比hb大,那么就把ha的值压入最终结果,直到ha < hb,同理移动b即可,但是需要考虑ha == hb的情况,直接比较ha,hb对应的尾串即可,参考如下测试样例即可:
          1
          2
          3
          4
          5
          6
          7
          8
          9
          eg1: 
          [2,5,6,4,4,0]
          [7,3,8,0,6,5,7,6,2]
          15

          eg2:
          [6,7]
          [6,0,4]
          5
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          22
          23
          24
          25
          26
          27
          28
          29
          30
          31
          32
          33
          34
          35
          36
          37
          38
          39
          40
          41
          42
          43
          44
          45
          46
          47
          48
          49
          50
          51
          52
          53
          54
          55
          56
          57
          58
          59
          60
          61
          62
          63
          64
          65
          66
          67
          68
          69
          70
          71
          72
          73
          74
          75
          76
          77
          78
          79
          80
          81
          class Solution {
          public:

          string getMaxConcat(vector<int>& longVec, vector<int>& shortVec, int lenInLonger, int lenInShorter) {
          string monoLong, monoShort;

          // choose biggest lenInLonger's subArr from longer vec
          for(int i = 0; i < longVec.size(); ++i) {
          while(monoLong.size() > 0 && monoLong.back() - '0' < longVec[i] && monoLong.size() + longVec.size() - i > lenInLonger) {
          // cout << "pop_long: " << monoLong.back() << " monoLong's std len: " << lenInLonger << " curback: " << monoLong.back() << endl;
          monoLong.pop_back();
          }
          if(monoLong.size() < lenInLonger) {
          // cout << "push_long: in " << static_cast<char>(longVec[i] + '0') << endl;
          monoLong.push_back(static_cast<char>(longVec[i] + '0'));
          }
          }
          for(int i = 0; i < shortVec.size(); ++i) {
          // while(monoLong.back() < longVec[i] && monoLong.size() <= lenInLonger && monoLong.size() + longVec.size() - i + 1 < lenInLonger) {
          while(!monoShort.empty() && monoShort.back() - '0' < shortVec[i] && monoShort.size() + shortVec.size() - i > lenInShorter) {
          // cout << "pop_short: " << monoShort.back() << " monoLong's std len: " << lenInShorter << " curback: " << monoShort.back() << endl;
          monoShort.pop_back();
          }
          if(monoShort.size() < lenInShorter) {
          // cout << "push_short: in " << static_cast<char>(longVec[i] + '0') << endl;
          monoShort.push_back(static_cast<char>(shortVec[i] + '0'));
          }
          }

          int j = 0;
          // merger the two biggest substr,
          string finalRes = "";
          // cout << "longMax and shortMax str: " << monoLong << " " << monoShort << endl;
          for(int i = 0; i < monoShort.size(); ++i) {
          while(j < monoLong.size() && monoLong[j] > monoShort[i]) {
          finalRes.push_back(monoLong[j++]);
          }
          // decided whether to use long str or short when the char compared is true
          if(monoLong[j] == monoShort[i]) {
          if(monoLong.substr(j) > monoShort.substr(i)) {
          finalRes.push_back(monoLong[j++]);
          i--;
          continue;
          }
          }
          finalRes.push_back(monoShort[i]);
          }
          finalRes += monoLong.substr(j);
          // cout << "finalRes string is: " << finalRes << endl;
          return finalRes;
          }

          vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
          int m = nums1.size();
          int n = nums2.size();
          // cout << "m/n" << m << " " << n << endl;

          // let k split into nums1 and nums2
          string maxStr(k, '0');
          if(m <= n) {
          for(int lenInShorter = max(0, k - n); lenInShorter <= min(m, k); ++lenInShorter) {
          int lenInLonger = k - lenInShorter;
          // cout << "lenInLong/short" << lenInLonger << " " << lenInShorter << endl;
          string curMax = getMaxConcat(nums2, nums1, lenInLonger, lenInShorter);
          maxStr = maxStr > curMax ? maxStr : curMax;
          }
          } else {
          for(int lenInShorter = max(0, k - m); lenInShorter <= min(n, k); ++lenInShorter) {
          int lenInLonger = k - lenInShorter;
          string curMax = getMaxConcat(nums1, nums2, lenInLonger, lenInShorter);
          maxStr = maxStr > curMax ? maxStr : curMax;
          }
          }

          vector<int> res;
          for(auto& c : maxStr) {
          res.emplace_back(c - '0');
          }
          return res;
          }
          };

0768 最多能完成排序的块 II maxChunksToSroted

1 题目

https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii

2 解题思路

  • 1 普通思路:

    • 1.1 利用已经排好序的数组,和当前数组进行比较,得到分块方式,也就是题目的提示:

      Each k for which some permutation of arr[:k] is equal to sorted(arr)[:k] is where we should cut each chunk.

    • 1.2 具体算法:
      • 记原数组为arr,然后其排序为sortArr,而后遍历arr,如何确定一个下标k是否为chunk的分割点呢?
      • 使用hashA记录arr[:k]子数组中每个元素的出现次数,使用diffCount记录arr[:k]和sortArr[:k](在两个数组里出现次数不同的)元素个数
      • 当diffCount为0,就找到一个k,最后返回所有diffCount为0的地方即可
    • 1.3 普通解法:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      class Solution {
      public:

      int maxChunksToSorted(vector<int>& arr) {
      // monoStack: every ele in mono represent: the biggest value in a chunk
      unordered_map<int, int> hash;

      // diffCnt, the size of those numbers whose cnt are not equal in arr[:k] and sortArr[:k]
      int ans = 0, n = arr.size(), diffCnt = 0;
      vector<int> sortArr(arr);
      sort(sortArr.begin(), sortArr.end(), std::less<int>());
      for(int k = 0; k < n; ++k) {
      ++ hash[arr[k]];
      if(hash[arr[k]] == 1) {
      diffCnt++;
      }
      if(hash[arr[k]] == 0){
      diffCnt--;
      }

      -- hash[sortArr[k]];
      if(hash[sortArr[k]] == 0) {
      diffCnt--;
      }
      if(hash[sortArr[k]] == -1) { // sortArr[k] is redundant
      diffCnt++;
      }

      ans += diffCnt == 0;
      }

      return ans;
      }
      };
  • 2 单调栈:

    • 2.1 考虑例子: 1 4 3 7 5,很容易发现,就三个分块,然后arr的单调增栈为1 4 7,刚好为每个分块的最大值,所以有这么一个单调栈定义:单调栈里存入的数字为每个分块的最大值
    • 2.2 当然这也有问题,会涉及到单调栈需要合并分块的情况: 1 4 3 7 5 2,当没检测到2的时候,单调栈为3个分块,最大值分别为1,4,7,当检测到2的时候,我们需要先弹出所有比2大的分块的最大值,因为2在这些分块后面意味着必须将2和这些分块合并,这样才能保证最终从小到大的排序,然后压入合并的这些分块里的最大值,也就是遇到2之前单调栈的栈顶 7,单调栈变成了1,7
    • 2.3 具体看代码:单调栈解法:可视化参考
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      class Solution {
      public:

      int maxChunksToSorted(vector<int>& arr) {
      // monoStack: every ele in mono represent: the biggest value in a chunk
      vector<int> mono = {INT_MIN}; // from small to bigger
      int n = arr.size();
      for(int i = 0; i < n; ++i) {
      if(arr[i] >= mono.back()) {
      mono.emplace_back(arr[i]);
      } else { // arr[i] < mono.back()
      // merge the chunk untill arr[i] > mono.back()
      int curChunkMax = mono.back();
      while(mono.back() > arr[i]) {
      mono.pop_back();
      }
      mono.emplace_back(curChunkMax);
      }
      }

      return mono.size() - 1;
      }
      };

1793 好子数组的最大分数 maximumScore

1 题目:

https://leetcode-cn.com/problems/maximum-score-of-a-good-subarray/

类似题目:

2 解题思路:

  • 1 单调栈:
    • 1.1 想法很简单,遍历上述的柱状图的一列,栈顶总是最大,栈底最小,一旦有小于等于前栈的值,那么栈里面那些小于等于当前栈顶的值都不可能再在遍历的后续位置发生作用了,因为已经有小于等于它的值出现了,所以我们把这些值弹出然后算弹出的这一部分的体积,那么栈里面剩下的就是任然能够为后续遍历的位置贡献面积的值,所以就是这样,具体的看代码吧。
    • 1.2 计算过程中,我们只有当矩形的两边分别位于k的两边才会更新结果
  • 2 强调单调栈的几个特性(以递增单调栈为例子)
    • 2.1 栈底一定是整个数组最小的
    • 2.2 弹出当前元素记其下标为j后,当前栈顶元素下标记为i,那么i是第一个下标满足: i < j && arr[i] <= arr[j]
    • 2.3 **TIPS: **注意单调栈会将所有元素都入栈,但并不会都出栈,很多时候我们要求arr中的每个元素都出栈,那么常见操作为在arr末尾加一个比所有元素都要小的值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
// k split nums into left and right
vector<int> lPart(nums.begin(), nums.begin() + k + 1);

// construct the monostack, abscending
vector<int> mono;

int res = nums[k];
nums.emplace_back(0); // make sure all the heights are used for nums
for(int r = 0; r < nums.size(); ++r) {
while(!mono.empty() && nums[mono.back()] >= nums[r]) {
int h = nums[mono.back()];
// cout << "h: " << h << endl;
mono.pop_back();
int l = mono.empty() ? -1 : mono.back();
int w = r - l - 1;
cout << "w/r/l/h: " << w << "/" << r << "/" << l << "/" << h << endl;
if(r - 1 >= k && l + 1 <= k) {
res = max(res, w * h);
}
}
mono.emplace_back(r);
}

return res;
}
}

1 字典树、前缀树、Trie

将一个单词列表使用words组装起来,实现如下:(仅含有小写的字典),可以在log(m)时间内查询一个单词是否在字典中。

1.1 可能的小技巧

  • 1 一些可以想到的优化:
    • 1.1 如果对一个长串反复查询,则使用一个node指针指向当前查询位于Trie里面的位置,避免反复查询相同的前缀
    • 1.2 如果对一个长串反复查询,尝试使用hash记录尾串的目标信息,避免对尾串反复查询
    • 1.3 逆序建树,构建后缀树等等,见本篇最后两个例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Trie {
public:
vector<Trie *>curLevel;
bool isEnd = false;

Trie() : curLevel(26) {

}

void insert(string word) {
Trie * curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
// check nextLevel
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
}

bool search(string word) {
Trie * curNode = this;
for(char c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return curNode->isEnd;
}

bool startsWith(string prefix) {
Trie * curNode = this;
for(char c : prefix) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return false;
}
curNode = curNode->curLevel[c];
}
return true;
}
};

2 例题

0212 单词搜索 II

1 题目

https://leetcode-cn.com/problems/word-search-ii

2 解题思路

  • 1 要搜索整个字母棋盘,很自然想到使用回溯
  • 2 要知道一个字符串是否在字典里,很自然想到trie
  • 3 具体解答方法
    • 3.1 如下代码的注释的backTrack函数很清晰的阐述啦思路,称之为old way
    • 3.2 old way的缺陷,对于tmpRes的前面的公共部分反复调用啦startWith函数重复计算啦,
    • 3.3 改进,使用curNode记录tmpRes在前缀树里面的位置,那么只需要根据curNode来判断tmpRes即将加入的新的字符是否为curNode的子节点就可以啦,提升了速度
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      162
      163
      164
      165
      166
      167
      168
      169
      170
      171
      172
      173
      174
      175
      176
      177
      178
      179
      180
      181
      182
      183
      184
      185
      186
      187
      188
      189
      190
      191
      192
      193
      194
      195
      196
      197
      198
      199
      200
      201
      202
      203
      204
      class Solution {
      public:
      class Trie {
      public:
      vector<Trie*> curLevel;
      bool isEnd = false;
      bool hasNext = true;
      Trie() : curLevel(26) {
      }

      void insert(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      curNode->curLevel[c] = new Trie();
      }
      curNode = curNode->curLevel[c];
      curNode->hasNext = true;
      }
      curNode->isEnd = true;
      }

      bool inTrie(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      return false;
      }
      curNode = curNode->curLevel[c];
      }
      return curNode->isEnd;
      }

      bool startWith(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      return false;
      }
      curNode = curNode->curLevel[c];
      }
      return true;
      }

      bool endWith(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      return false;
      }
      curNode = curNode->curLevel[c];
      }
      return !curNode->hasNext;
      }
      };


      vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
      int m = board.size();
      int n = board[0].size();



      // build trie in normal or reverse order
      // std::shared_ptr<Trie> treeNormal = make_shared<Trie>();
      Trie* treeNormal = new Trie();
      // std::unique_ptr<Trie> treeReverse = new Trie();
      for(auto w : words) {
      treeNormal->insert(w);
      // treeReverse.insert(reverse(w.begin(), w.end()));
      }

      int deltaX[] = {1, 0, -1, 0};
      int deltaY[] = {0, 1, 0, -1};
      // get the answer
      vector<string> res;
      unordered_set<string> hash;
      for(int i = 0; i < board.size(); ++i) {
      for(int j = 0; j < board[0].size(); ++j) {
      // std::cout << "check next st point!" << endl;
      string tmpRes = "";
      vector<vector<bool>> exploredFlag(m, vector<bool>(n, false));
      backTrack(i, j, board, tmpRes, res, treeNormal,
      deltaX, deltaY, exploredFlag, hash
      );
      }
      }
      return res;
      }


      /**
      [["o","a","a","n"],
      ["e","t","a","e"],
      ["i","h","k","r"],
      ["i","f","l","v"]]
      ["oath","pea","eat","rain","oathi","oathk","oathf","oate","oathii","oathfi","oathfii"]
      **/
      void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, Trie* curNode,
      const int* deltaX, const int* deltaY,
      vector<vector<bool>>& exploredFlag,
      unordered_set<string>& hash) {
      char ch = board[i][j];
      if(nullptr == curNode->curLevel[ch - 'a']) {
      return ;
      }

      // start from i, j
      tmpRes.push_back(board[i][j]);
      // Trie* lastNode = curNode;
      curNode = curNode->curLevel[ch - 'a'];
      if(nullptr == curNode) {
      cout << "a???" << endl;
      return ;
      }

      // cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
      // we check the tmpRes directly using the trie
      // if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
      // res.emplace_back(tmpRes);
      // hash.insert(tmpRes);
      // if(tree->endWith(tmpRes)) {
      // tmpRes.pop_back();
      // return;
      // }
      // }
      if(nullptr != curNode && curNode->isEnd == true && 0 == hash.count(tmpRes)) {
      // cout << "find! >>>>> " << tmpRes << endl;
      res.emplace_back(tmpRes);
      hash.insert(tmpRes);
      if(!curNode->hasNext) {
      tmpRes.pop_back();
      return;
      }
      }

      // cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
      exploredFlag[i][j] = true;
      if(nullptr != curNode) {
      // not null
      for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
      int nextX = i + deltaX[mvIdx];
      int nextY = j + deltaY[mvIdx];
      // cout << "tryStart: [x, y] :" << nextX << " " << nextY << endl;;
      if( nextX < board.size() && nextX >= 0 && nextY < board[0].size() && nextY >= 0 && \
      ! exploredFlag[nextX][nextY]) {
      backTrack(nextX, nextY, board, tmpRes, res, curNode,
      deltaX, deltaY, exploredFlag, hash
      );
      }
      // cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
      }
      }
      exploredFlag[i][j] = false;
      tmpRes.pop_back();
      }

      // OLD WAY TO DO, will exceed the time limitation
      // void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, unique_ptr<Trie>& tree,
      // const int* deltaX, const int* deltaY,
      // vector<vector<bool>>& exploredFlag,
      // unordered_set<string>& hash) {

      // // start from i, j
      // tmpRes.push_back(board[i][j]);

      // // cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
      // if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
      // res.emplace_back(tmpRes);
      // hash.insert(tmpRes);
      // if(tree->endWith(tmpRes)) {
      // tmpRes.pop_back();
      // return;
      // }
      // }


      // // cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
      // exploredFlag[i][j] = true;
      // if(tree->startWith(tmpRes)) {
      // for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
      // int nextX = i + deltaX[mvIdx];
      // int nextY = j + deltaY[mvIdx];
      // if( nextX < board.size() && \
      // nextX >= 0 && \
      // nextY < board[0].size() && \
      // nextY >= 0 && \
      // ! exploredFlag[nextX][nextY]) {
      // backTrack(nextX, nextY, board, tmpRes, res, tree,
      // deltaX, deltaY, exploredFlag, hash
      // );
      // }
      // // cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
      // }
      // }
      // exploredFlag[i][j] = false;
      // tmpRes.pop_back();
      // // cout << "current[i, j] : exit " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
      // }
      };

0336. 回文对

1 题目

https://leetcode-cn.com/problems/palindrome-pairs/

2 解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
int wordIdx = -1;
Trie() : curLevel(26), wordIdx(-1) {

}
void insert(string& word, int idx) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
curNode->wordIdx = idx;
}

int inTrie(string word) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}

int inTrie(string& word, int left, int right) {
Trie* curNode = this;
for(int i = right; i >= left; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
};

vector<vector<int>> palindromePairs(vector<string>& words) {
// travel all prefix and subfix of a word,
// find the palindrome and check the existence in the words of
// reverse of the other part
Trie* tree = new Trie();
// Trie* treeReverse = new Trie();
unordered_map<string, int> strToIdx;
// int idx = 0;
// for(auto word : words) {
// tree->insert(word);
// strToIdx[word] = idx++;
// }

// int ans = 0;
// vector<vector<int>> res = {};
// for(auto word : words) {
// deque<string> prefix;
// deque<string> subfix;
// int n = word.size();
// for(int st = 0; st <= n; ++st) {
// string pre = word.substr(0, st);
// string sub = word.substr(st);
// // cout << "p/s : " << pre << " / " << sub << endl;
// if(checkPalindrome(pre)) {
// reverse(sub.begin(), sub.end());
// if(tree->inTrie(sub)) {
// vector<int> resItem = {strToIdx[sub], strToIdx[word]};
// if(resItem[1] != resItem[0]) {
// // cout << "push: " << word + sub << endl;
// res.emplace_back(resItem);
// }
// }
// }
// if(checkPalindrome(sub) && pre.size() != n) {
// reverse(pre.begin(), pre.end());
// if(tree->inTrie(pre)) {
// vector<int> resItem = {strToIdx[word], strToIdx[pre]};
// if(resItem[1] != resItem[0]) {
// // cout << "push: " << pre + word << endl;
// res.emplace_back(vector<int>(resItem));
// }
// }
// }

// }
// }

int idx = 0;
for(auto word : words) {
// tree->insert(word, idx);
// reverse(word.begin(), word.end());
tree->insert(word, idx);
++idx;
}
int tmp = 0;

int ans = 0;
vector<vector<int>> res = {};

int curWordIdx = 0;
for(auto word : words) {
int n = word.size();
for(int st = 0; st <= n; ++st) {
string pre = word.substr(0, st);
string sub = word.substr(st);
// cout << "p/s : " << pre << " / " << sub << " curWordIdx : " << curWordIdx << endl;
// if(checkPalindrome(pre)) {
if(0 != st && checkPalindrome(word, 0, st-1)) {
// reverse(sub.begin(), sub.end());
int subIdx = tree->inTrie(word, st, n-1);
// cout << "subIdx = " << sub << "with idx = " << subIdx << endl;
if(subIdx != -1 && curWordIdx != subIdx) {
// cout << "curWordIdx / subIdx" << curWordIdx << "/" << subIdx << endl;
// cout << "push: " << sub << "+" << word << endl;
res.emplace_back(vector<int>({subIdx, curWordIdx}));
}
}
if(checkPalindrome(word, st, n-1)) {
// reverse(pre.begin(), pre.end());
int preIdx = tree->inTrie(word, 0, st-1);
if(preIdx != -1 && preIdx != curWordIdx) {
// cout << "curWordIdx / preIdx" << curWordIdx << "/" << preIdx << endl;
// cout << "push: " << pre << "+" + word << endl;
res.emplace_back(vector<int>({curWordIdx, preIdx}));
}
}

}
++curWordIdx;
}
return res;
}
// for (int i = 0; i < n; i++) {
// int m = words[i].size();
// for (int j = 0; j <= m; j++) {
// if (isPalindrome(words[i], j, m - 1)) {
// int left_id = findWord(words[i], 0, j - 1);
// if (left_id != -1 && left_id != i) {
// ret.push_back({i, left_id});
// }
// }
// if (j && isPalindrome(words[i], 0, j - 1)) {
// int right_id = findWord(words[i], j, m - 1);
// if (right_id != -1 && right_id != i) {
// ret.push_back({right_id, i});
// }
// }
// }
// }

bool checkPalindrome(string& s, int left, int right) {
int len = right - left + 1;
for(int i = 0; i < len / 2; ++i) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}


// bool checkPalindrome(string& s) {
// int n = s.size();
// for(int i = 0; i < n / 2; ++i) {
// if(s[i] != s[n - i - 1]) {
// return false;
// }
// }
// return true;
// }
};

3 使用hash表来查前后缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class Solution {
public:
class Trie {
public:
vector<Trie*> curLevel;
bool isEnd = false;
int wordIdx = -1;
Trie() : curLevel(26), wordIdx(-1) {

}
void insert(string& word, int idx) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}
curNode = curNode->curLevel[c];
}
curNode->isEnd = true;
curNode->wordIdx = idx;
}

int inTrie(string word) {
Trie* curNode = this;
for(auto c : word) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}

int inTrie(string& word, int left, int right) {
Trie* curNode = this;
for(int i = right; i >= left; --i) {
char c = word[i] - 'a';
if(nullptr == curNode->curLevel[c]) {
return -1;
}
curNode = curNode->curLevel[c];
}
return curNode->wordIdx;
}
};

vector<string> wordReverse;
unordered_map<string, int> strToIdx;

int findWord(string& s, int left, int right) {
string tmp = s.substr(left, right - left + 1);
auto it = strToIdx.find(tmp);
int res = it == strToIdx.end() ? -1 : it->second;
// cout << "finding: " << tmp << " with ans = " << res << endl;
return res;
}


vector<vector<int>> palindromePairs(vector<string>& words) {
// travel all prefix and subfix of a word,
// find the palindrome and check the existence in the words of
// reverse of the other part
int idx = 0;
for(auto word : words) {
reverse(word.begin(), word.end());
wordReverse.emplace_back(word);
strToIdx[word] = idx;
++idx;
}

vector<vector<int>> res = {};

int curWordIdx = 0;
for(auto word : words) {
int n = word.size();
for(int st = 0; st <= n; ++st) {
// cout << "p/s : " << " / " << " curWordIdx : " << curWordIdx << endl;
if(0 != st && checkPalindrome(word, 0, st-1)) {
int subIdx = findWord(word, st, n-1);
// cout << "subIdx = " << subIdx << endl;
if(subIdx != -1 && curWordIdx != subIdx) {
res.emplace_back(vector<int>({subIdx, curWordIdx}));
}
}
if(checkPalindrome(word, st, n-1)) {
int preIdx = findWord(word, 0, st-1);
if(preIdx != -1 && preIdx != curWordIdx) {
res.emplace_back(vector<int>({curWordIdx, preIdx}));
}
}

}
++curWordIdx;
}
return res;
}


bool checkPalindrome(string& s, int left, int right) {
int len = right - left + 1;
for(int i = 0; i < len / 2; ++i) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}

};

0140. 单词拆分 II

1 题目

https://leetcode-cn.com/problems/word-break-ii/

2 解题思路

  • 1 首先确定搜索思路:
    • 1.1 很显然这个问题的解答思路不会随着问题规模的减小而改变,于是采用递归/回溯方案
    • 1.2 由于需要确认当前子问题处于什么位置,于是采用回溯
    • 1.3 回溯方法
      • 1.3.1 每次在头部尝试字符串headWord,直到找到一个在字典里面的headWord
      • 1.3.2 将原来字符串去掉headWord,然后递归到下一层
      • 1.3.3 当前的headWord的所有可能尝试完毕,则回溯到尝试headWord之前,然后去尝试下一个headWord
    • 1.4 以上可以看出回溯和递归的区别,递归不带有当前搜索状态,而回溯需要维持搜索状态
  • 2 有了大体思路,那么如何解决: 找到一个在字典里面的headWord?
    • 2.1 采用字典前缀树即可快速获得该字符串是否在字典树里面,复杂度为O(m),m为字典树中的
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      class Solution {
      public:
      class Trie {
      public:
      vector<Trie*> curLevel;
      bool isEnd = false;

      Trie() : curLevel(26){}

      void insert(string word ) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      curNode->curLevel[c] = new Trie();
      }
      curNode = curNode->curLevel[c];
      }
      curNode->isEnd = true;
      }

      bool inTrie(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      return false;
      }
      curNode = curNode->curLevel[c];
      }
      return curNode->isEnd;
      }

      bool startWith(string word) {
      Trie* curNode = this;
      for(char c : word) {
      c -= 'a';
      if(nullptr == curNode->curLevel[c]) {
      return false;
      }
      curNode = curNode->curLevel[c];
      }
      return true;
      }
      };

      vector<string> wordBreak(string s, vector<string>& wordDict) {
      // implement a trie to sort the word Dict
      Trie* tree = new Solution::Trie();
      for(string s : wordDict) {
      tree->insert(s);
      }

      vector<string> tmpRes;
      vector<vector<string>> res;
      backTrack(s, tmpRes, res, tree);

      vector<string> finalRes;
      for(auto& strVec : res) {
      string resItem = "";
      for(auto& str : strVec) {
      resItem += (str + " ");
      }
      finalRes.emplace_back(resItem.substr(0, resItem.size() - 1));
      }
      return finalRes;
      }

      void backTrack(string s, vector<string> tmpRes, vector<vector<string>>& res, Trie* trie) {
      if(0 == s.size()) {
      res.emplace_back(tmpRes);
      }
      // try every possibility
      for(int i = 0; i < s.size(); ++i) {
      string headWord = s.substr(0, i + 1);
      tmpRes.emplace_back(headWord);
      // cout << "head -> " << headWord << endl;
      if(trie->inTrie(headWord)) {
      // cout << "in it!" << endl;
      backTrack(s.substr(i + 1), tmpRes, res, trie);
      }
      tmpRes.pop_back();
      }
      }
      };

0472. 连接词

1 题目

https://leetcode-cn.com/problems/concatenated-words/

2 解题思路

  • 1 首先很容易想到一点:
    • 1.1 由于需要快速定位一个单词是否在字典里,则采用字典树获取该信息
    • 1.2 对于一个单词,我们对于每个isEnd(也就是搜索前缀对应的单词在字典里)的位置,都从下一个字符从新开始在字典中匹配,然后每个isEnd位置后面的字符,需要继续匹配,eg:[cat, cats, catsdog, dog],对于catsdog,从sdog和dog分别重新匹配
    • 1.3 对于一个单词,它的构成成分比他小,于是将字符串排序,一边插入,一边找
  • 2 通过后缀记忆剪枝dfs, eg: 对于[“a”, “aa”, “aaaa”, “aaaakaa”]中的aaaakaa,运行代码会有如下日志:
    • 因为在第一次 a,a,a,a,k的时候记录了k位置往后的后缀无法成功匹配
    • 那么对于后面的 aa,a,a,k以及aaa,a,k等等搜索都会直接跳过k后缀的匹配
      1
      2
      3
      4
      when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!
      when checking : aaaakaa the sufix start from pos : 3 has been validated to be failure!
      when checking : aaaakaa the sufix start from pos : 2 has been validated to be failure!
      when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class Solution {
public:
class Trie{
public:
vector<Trie*> curLevel;
bool isEnd = false;
// bool hasNext = false;

Trie() : curLevel(26) {

}

void insert(string& s, int idx) {
// cout << "inserting : " << s << endl;
Trie* curNode = this;
for(auto c : s) {
c -= 'a';
if(nullptr == curNode->curLevel[c]) {
curNode->curLevel[c] = new Trie();
}

curNode = curNode->curLevel[c];
// curNode->hasNext = true;
}
curNode->isEnd = true;
}
};

vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
int n = words.size();
Trie* tree = new Trie();

// build trie
int idx = 0;

sort(words.begin(), words.end(), [](string& a, string& b){
return a.size() < b.size();
});

vector<string> ans;


for(auto w : words) {
// cout << "-------checking " << w << endl;
// bool ableToConnect = false;
// findMaxConnectedCnt(w, 0, tree, 0, ableToConnect);
// if(ableToConnect ) {
// ans.emplace_back(w);
// }
vector<bool> trap(w.size(), false);
if(dfsToCheck(w, 0, tree, 0, trap)) {
ans.emplace_back(w);
}
tree->insert(words[idx], idx);
++idx;
}

return ans;
}

// here we search all the possible ways, but we only need one possible way, so we need return early
void findMaxConnectedCnt(string& s, int pos, Trie* root, int curCnt, bool& ableToConnect) {

if(s.size() == pos) {
if(curCnt >= 2) {
ableToConnect = true;
}
// cout << "<<<<<< finish one!" << endl;
return ;
}

int curPos = pos;
Trie* curNode = root;
while(curPos < s.size()) { // serach all prefix
int ch = s[curPos] - 'a';
if(nullptr != curNode->curLevel[ch]) {
if(curNode->curLevel[ch]->isEnd) {
// cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
// using this or next end
findMaxConnectedCnt(s, curPos + 1, root, curCnt + 1, ableToConnect);
}
} else {
return;
}
// cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
curNode = curNode->curLevel[ch];
++curPos;
}
}

bool dfsToCheck(string& s, int pos, Trie* root, int curCnt, vector<bool>& trap) {

if(s.size() == pos) {
return curCnt >= 2;
}

if(trap[pos]) {
cout << "when checking : " << s << " the sufix start from pos : " << pos << " has been validated to be failure!" << endl;
return false;
}

int curPos = pos;
Trie* curNode = root;
while(curPos < s.size()) { // serach all prefix
int ch = s[curPos] - 'a';
if(nullptr != curNode) {
if(nullptr != curNode->curLevel[ch]) {
if(curNode->curLevel[ch]->isEnd) {
// cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
// using this or next end
if(dfsToCheck(s, curPos + 1, root, curCnt + 1, trap)) {
return true;
}
}
}
} else {
break;
}

// cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
curNode = curNode->curLevel[ch];
++curPos;
}

trap[pos] = true;
return false;
}

};

0745WordFilter 前缀和后缀搜索

1 题目

https://leetcode-cn.com/problems/prefix-and-suffix-search/

2 解题思路

  • 1 构建后缀拼接前缀树
    1.1 参考解释即可:

    For a word like “test”, consider “#test”, “t#test”, “st#test”, “est#test”, “test#test”. Then if we have a query like prefix = “te”, suffix = “t”, we can find it by searching for something we’ve inserted starting with “t#te”.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    class WordFilter {
    public:
    // containning suffix
    class Trie {
    public:
    vector<Trie*> curLevel;
    int idx = -1;
    Trie() : curLevel(27) {}

    void insert(string& word, int idx, int left, int right) {
    Trie* curNode = this;
    for(int i = left; i < right; ++i) {
    char c = word[i];
    c = (c == '#' ? 26 : c - 'a');
    if(nullptr == curNode->curLevel[c]) {
    curNode->curLevel[c] = new Trie();
    }
    curNode = curNode->curLevel[c];
    curNode->idx = idx;
    }
    curNode->idx = idx;
    }

    int startWith(string& word) {
    Trie* curNode = this;
    int lastIdx = -1;
    for(auto c : word) {
    // cout << "checking char: " << c << endl;
    c = (c == '#' ? 26 : c - 'a');
    if(nullptr == curNode->curLevel[c]) {
    return -1;
    }
    curNode = curNode->curLevel[c];
    }
    return curNode->idx;
    }
    };

    public:
    Trie* tree;


    WordFilter(vector<string>& words) {
    tree = new Trie();
    for(int wIdx = 0; wIdx < words.size(); ++wIdx) {
    int n = words[wIdx].size();
    string word = words[wIdx] + "#" + words[wIdx];
    for(int j = 0; j <= n - 1; ++j) {
    // string tmp = word.substr(j);
    // overwrite those who start with a same suffix and prefix
    // cout <<"insert : " << tmp << endl;
    tree->insert(word, wIdx, j, 2*n +1);
    }
    }
    }

    int f(string prefix, string suffix) {
    int ans = -1;
    string tmp = suffix + "#" + prefix;
    // cout << "target >> " << tmp << endl;
    return tree->startWith(tmp);

    }
    };

1032. 字符流 StreamChecke

1 题目

https://leetcode-cn.com/problems/stream-of-characters/

2 解题思路

  • 1 倒序建立搜索树即可,因为可以观察到,总是从字符流的倒序开始查询
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    class StreamChecker {
    public:
    class Trie{
    public:
    vector<Trie*> curLevel;
    bool isEnd = false;

    Trie() : curLevel(26) {}

    void insert(string& word) {
    Trie* curNode = this;
    int n = word.size();
    for(int i = n-1; i >= 0; --i) {
    char c = word[i] - 'a';
    if(nullptr == curNode->curLevel[c]) {
    curNode->curLevel[c] = new Trie();
    }
    curNode = curNode->curLevel[c];
    }
    curNode->isEnd = true;
    }

    bool inTrie(string& word) {
    Trie* curNode = this;
    int n = word.size();
    for(int i = n-1; i >= 0; --i) {
    char c = word[i] - 'a';
    if(nullptr == curNode->curLevel[c]) {
    return false;
    }
    if(curNode->curLevel[c]->isEnd) {
    return true;
    }
    curNode = curNode->curLevel[c];
    }
    return curNode->isEnd;
    }

    };

    Trie* root;
    string curStr;

    StreamChecker(vector<string>& words) {
    root = new Trie();
    for(auto& w : words) {
    root->insert(w);
    }

    curStr = "";
    }

    bool query(char letter) {
    curStr += letter;
    return root->inTrie(curStr);
    }
    };

    /**
    * Your StreamChecker object will be instantiated and called as such:
    * StreamChecker* obj = new StreamChecker(words);
    * bool param_1 = obj->query(letter);
    *

0 拉宾-卡普算法

来自wiki
在计算机科学中,拉宾-卡普算法(英語:Rabin–Karp algorithm)或卡普-拉宾算法(Karp–Rabin algorithm),是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置,此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。

1 算法本身主要思想

  • 1 朴素匹配: text = “abcdefabc”长度为n,去匹配长度为m的模式串abc,
    • 具体做法则是找出所有长度为m的字串,然后为每一个m字串去匹配模式串abc,复杂度为O(nm)
  • 2 使用拉宾-卡普算法改进:
    • 2.1 找出了所有长度为m的字串,那么能不能在O(1)的时间内去判断两个长度为m的字串是否相等?
    • 2.2 很自然的想到hash,那么如何计算一个字串的hash?比如abc,使用26进制编码(因为text中只有小写字母)即可: hash(abc) = 26^2 * (‘a’ - ‘a’) + 26^1 * (‘b’ - ‘a’) + 26^0 * (‘c’ - ‘a’);
    • 2.3 很容易注意到上面,若字符串很长,比如100,那么hash值就有26^100,显然太大,需要取模,取模后带来问题,造成hash碰撞,则需要散列,常用的有拉宾指纹,我们可以使用两个不同模算出来一对hash值当做为一个整体hash,降低hash碰撞的概率
    • 2.4 那么计算hash明明需要读取模式串,复杂度为O(m)啊?
      • 那是因为对于text,我们只需要计算第一个长度为m的字串的hash,后面的字串hash都可以通过O(1)时间获取:
      • 直接看图:O(1) 计算 hash图片来源
      • 解释: ft_i为第i个字串的hash,在o(1)时间内得到ft_i+1的方案就如图所示,或者看如下例子的代码的check函数

例子

1044. 最长重复子串 longestDupSubstring

1 题目

https://leetcode-cn.com/problems/longest-duplicate-substring/

2 解题思路

  • 0 使用官方思路: rabin-karp + binarySearch
  • 1 这里需要使用rabin-karp算法,在长度为n的text中寻找长度为m的模式串,其复杂度为o(m),然后用二分法去确定最长字符串的长度,故整体复杂度为O(n logn),拉宾-卡普算法参考:https://xychen5.github.io/2021/12/28/rabinKarp/
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103

    typedef pair<long long, long long> pll;
    class Solution {
    public:
    static constexpr int big = 1000000006;
    // cal: a^m % mod, when m = 1000, a = 26, there will be overflow
    long long pow(int a, int m, int mod) {
    long long ans = 1;
    long long curNum = a;
    while(m > 0) {
    if(m % 2 == 1) {
    ans = ans * curNum % mod;
    // overflow
    if(ans < 0) {
    ans += mod;
    }
    }
    curNum = curNum * curNum % mod;
    // overflow
    if(curNum < 0) {
    curNum += mod;
    }
    m /= 2;
    }
    return ans;
    }

    // return st of substr with len = len
    int check(vector<int>& arr, int len, int a1, int a2, int mod1, int mod2) {
    int n = arr.size();
    long long powA1 = pow(a1, len, mod1);
    long long powA2 = pow(a2, len, mod2);
    long long hashA1 = 0, hashA2 = 0;

    // cout << "d2.5" << endl;
    // cal hash of the first substr
    // hashA1 = arr[0] * a1^(len-1) + arr[1] * a1^(len-2) + ... + arr[len-1]
    for(int i = 0; i < len; ++i) {
    hashA1 = (hashA1 * a1 % mod1 + arr[i]) % mod1;
    hashA2 = (hashA2 * a2 % mod2 + arr[i]) % mod2;
    hashA1 += hashA1 >= 0 ? 0 : mod1;
    hashA2 += hashA2 >= 0 ? 0 : mod2;
    }

    // cout << "d3" << endl;
    // calculate all substr's hash with len = len
    set<pll> seen;
    seen.emplace(hashA1, hashA2);
    for(int st = 1; st <= n - len; ++st) {
    // cout << "d4" << endl;
    // O(1) to cal next hash
    hashA1 = (hashA1 * a1 % mod1 - arr[st - 1] * powA1 % mod1 + arr[st + len - 1]) % mod1;
    hashA2 = (hashA2 * a2 % mod2 - arr[st - 1] * powA2 % mod2 + arr[st + len - 1]) % mod2;
    hashA1 += hashA1 >= 0 ? 0 : mod1;
    hashA2 += hashA2 >= 0 ? 0 : mod2;
    // before cursubstr, there is a same one
    if(seen.count(make_pair(hashA1, hashA2))) {
    return st;
    }
    seen.emplace(hashA1, hashA2);
    }

    return -1;
    }

    string longestDupSubstring(string s) {
    int n = s.size();

    // code the string
    vector<int> arr(n);
    for(int i = 0; i < n; ++i) {
    arr[i] = s[i] - 'a';
    }

    // two random base and mod
    srand((unsigned)time(NULL));
    int a1 = random()%75 + 26;
    int a2 = random()%75 + 26;
    int mod1 = random()%(INT_MAX - big) + big;
    int mod2 = random()%(INT_MAX - big) + big;

    // bin search the length of longest dup substr
    int l = 1, r = n - 1;
    int finalSt = -1, finalLen = -1;
    while(l <= r) {
    // m represents target len
    // int m = (l + r) / 2;
    int m = l + (r - l + 1) / 2;
    // cout << "d1" << endl;
    int st = check(arr, m, a1, a2, mod1, mod2);
    // cout << "d2" << endl;
    if(st != -1) {
    finalLen = m;
    l = m + 1;
    finalSt = st;
    } else {
    r = m - 1;
    }
    }
    return finalLen == -1 ? "" : s.substr(finalSt, finalLen);
    }
    }

1 线段树原理

1.1 数组实现

1.2 线段树树形实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class SegTree {
public:
struct SegNode {
long long leftBound = 0, rightBound = 0, curSum = 0;
SegNode* lChild = nullptr;
SegNode* rChild = nullptr;
SegNode(long long lb, long long rb) :
leftBound(lb),
rightBound(rb),
curSum(0),
lChild(nullptr),
rChild(nullptr) {
}
};

SegNode* root;

SegTree(long long left, long long right) {
root = build(left, right);
}

SegTree() {}

SegNode* build(long long l, long long r) {
SegNode* node = new SegNode(l, r);
if(l == r) {
return node;
}

long long mid = (l + r) / 2;
node->lChild = build(l, mid);
node->rChild = build(mid + 1, r);
return node;
}

void insert(SegNode* root, long long tarIdx, long long val) {
root->curSum += val;
if(root->leftBound == root->rightBound) {
return;
}
long long mid = (root->leftBound + root->rightBound) >> 1;
// long long mid = (root->leftBound + root->rightBound) / 2;
// there are identicial difference between them two:
// eg: when left == -1, right = 0;
// case1 => (left + right) / 2 == 0
// case1 => (left + right) >> 1 == -1
if(tarIdx <= mid) {
if (nullptr == root->lChild) {
root->lChild = new SegNode(root->leftBound, mid);
}
insert(root->lChild, tarIdx, val);
}
else{
if (nullptr == root->rChild) {
root->rChild = new SegNode(mid + 1, root->rightBound);
}
insert(root->rChild, tarIdx, val);
}
}

long long getSum(SegNode* root, long long left, long long right) const {
if(nullptr == root) {
return 0;
}
// 当前节点位于目标区间外
if(left > root->rightBound || right < root->leftBound) {
return 0;
}
// 当前节点位于目标区间内
if(left <= root->leftBound && right >= root->rightBound) {
return root->curSum;
}
return getSum(root->lChild, left, right) + getSum(root->rChild, left, right);
}
};

0327. 区间和的个数

1 题目

https://leetcode-cn.com/problems/count-of-range-sum/

题和逆序数对的计算方式相同:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
就是做了一个小改变而已,很多统计区间值的,st-ed < tar, 本来是让你找一个st,ed的对子的,那么就会转换思路为:
对于每一个ed找st,什么样的呢? st < ed + tar
然后找这样的st就有很多方法,比如hash,前缀和,bitree,priority_queue

2 解题思路

  • 1 求逆序对的思路:
    • 1.1 首先注意到:对于数组{5,5,2,3,6}而言,得到每个value的个数的统计:
      • index -> 1 2 3 4 5 6 7 8 9
      • value -> 0 1 1 0 2 1 0 0 0
    • 1.2 那么上述过程中,比如对于5,其贡献的逆序数对为5之前所有数字出现次数的和,也就是value数组中2之前的前缀和!
  • 2 那么如何快速获得前缀和呢?考虑使用BST来获取,参考:https://xychen5.github.io/2021/12/15/dataStructure-BinaryIndexedTree/
    • 2.1 整体思路如下:
      • a 使用数字在数组中的排名来代替数字(这不会对逆序数对的个数产生影响)
      • b 对数组nums中的元素nums[i]从右到左构建BITree(i 从 n-1 到 0),注意,BITree所对应的前缀和是数组里数字出现次数的和
        • 比如进行到nums[i],那么nums[i]右边的数字都已经统计了他们的出现次数,而后获取nums[i] - 1的前缀和,即可获取所有 < nums[i]的数字在nums[i:n]中的出现次数之和,也就是nums[i]贡献的逆序数对的个数
        • 之所以是逆序遍历构建BITree,是因为对于nums[i],它能够贡献的逆序数对的个数仅仅出现在它的右侧,所以需要在右侧进行
    • 2.2 额外说一下数组离散化,也就是不关系数字大小本身,只关心他们之间的相对排位
  • 3 使用线段树解题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Solution {
public:
class SegTree {
public:
struct SegNode {
long long leftBound = 0, rightBound = 0, curSum = 0;
SegNode* lChild = nullptr;
SegNode* rChild = nullptr;
SegNode(long long lb, long long rb) :
leftBound(lb),
rightBound(rb),
curSum(0),
lChild(nullptr),
rChild(nullptr) {
}
};

SegNode* root;


SegTree(long long left, long long right) {
root = build(left, right);
}

SegTree() {}

SegNode* build(long long l, long long r) {
SegNode* node = new SegNode(l, r);
if(l == r) {
return node;
}

long long mid = (l + r) / 2;
node->lChild = build(l, mid);
node->rChild = build(mid + 1, r);
return node;
}

void insert(SegNode* root, long long tarIdx, long long val) {
root->curSum += val;
if(root->leftBound == root->rightBound) {
return;
}
long long mid = (root->leftBound + root->rightBound) >> 1;

if(tarIdx <= mid) {
// cout << "d2" << endl;
if (nullptr == root->lChild) {
// cout << "d2.5" << endl;
root->lChild = new SegNode(root->leftBound, mid);
}
insert(root->lChild, tarIdx, val);
}
else{
// cout << "d3" << endl;
if (nullptr == root->rChild) {
root->rChild = new SegNode(mid + 1, root->rightBound);
}
insert(root->rChild, tarIdx, val);
}
}

long long getSum(SegNode* root, long long left, long long right) const {
if(nullptr == root) {
return 0;
}
// 当前节点位于目标区间外
if(left > root->rightBound || right < root->leftBound) {
return 0;
}
// 当前节点位于目标区间内
if(left <= root->leftBound && right >= root->rightBound) {
// cout << "left/right" << left << "/" << right << " => " << root->curSum << endl;
return root->curSum;
}
return getSum(root->lChild, left, right) + getSum(root->rChild, left, right);
}

};

int countRangeSum(vector<int>& nums, int lower, int upper) {
unordered_map<int, int> numToIdx;
set<long long> tmpNums;
vector<long long> prefixSum = {0};

for(int i = 0; i < nums.size(); ++i) {
prefixSum.emplace_back(nums[i] + prefixSum.back());
}

for(auto ps : prefixSum) {
tmpNums.insert(ps);
tmpNums.insert(ps - lower);
tmpNums.insert(ps - upper);
}

int i = 1;
for(auto num : tmpNums) {
numToIdx[num] = i++;
}

// for a valid s(i, j) we shall find:
// preSum[j] - ub <= preSum[i] <= preSum[j] - lb
// we just need to statistic those preSum[i] for each j
int n = tmpNums.size();
// BITree tree(n + 1);
long long ans = 0;

// we do not do the deserialization
long long minLeft = LLONG_MAX, maxRight = LLONG_MIN;
for(long long x : prefixSum) {
minLeft = min({minLeft, x, x - lower, x - upper});
maxRight = max({maxRight, x, x - lower, x - upper});
}

// cout << "minL, maxR" << minLeft << " " << maxRight <<endl;
SegTree tree;
tree.root = new SegTree::SegNode(minLeft, maxRight);
// reason why we insert the prefixSum of 0, because for the first ele:
// if it statisfy the interval, then it will be statisticed because the 0
for(long long x : prefixSum) {
ans += tree.getSum(tree.root, x - upper, x - lower);
// cout << "lb, rb = " << x - upper<< " " << x - lower << " ==> ans = " << ans << endl;
tree.insert(tree.root, x, 1);
// cout << "insert: " << x << "curRoot: " << tree.root->curSum << endl;
}


return ans;
}
}

5 可能发生的问题

注意其中很重要的一点:

对于线段树中插入一个节点时,需要对沿路所有节点的sum加上要插入的节点的值,找这个节点位置的时候,
需要找到root左右管辖范围的中间值mid,此时务必使用>>1去做,因为获得mid我们要求其为 floor(left + right),
(cpp和python对于移位和除法的逻辑是相同的),这里就显示出了2者的区别,
当然在数字都为正数的时候不会出错!

1
2
3
4
>>> int((-1 + 0) / 2)
0
>>> int((-1 + 0) >> 1)
-1

BITree 详解

1 Binary Indexed Tree(二元索引树)(树状数组)

  • 1 用途:以O(log n)时间复杂度得到任意区间和。同时支持在O(log n)时间内支持动态单点值的修改。空间复杂度O(n)。
  • 2 出处:Peter M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience. 1994, 24 (3): 327–336. doi:10.1002/spe.4380240306.
  • 3 原理:按照Peter M. Fenwick的说法,正如所有的整数都可以表示成2的幂和,我们也可以把一串序列表示成一系列子序列的和。采用这个想法,我们可将一个前缀和划分成多个子序列的和,而划分的方法与数的2的幂和具有极其相似的方式。一方面,子序列的个数是其二进制表示中1的个数,另一方面,子序列代表的f[i]的个数也是2的幂
    如下说明也很贴切:
    1
    2
    How does Binary Indexed Tree work? 
    The idea is based on the fact that all positive integers can be represented as the sum of powers of 2. For example 19 can be represented as 16 + 2 + 1. Every node of the BITree stores the sum of n elements where n is a power of 2. For example, in the first diagram above (the diagram for getSum()), the sum of the first 12 elements can be obtained by the sum of the last 4 elements (from 9 to 12) plus the sum of 8 elements (from 1 to 8). The number of set bits in the binary representation of a number n is O(Logn). Therefore, we traverse at-most O(Logn) nodes in both getSum() and update() operations. The time complexity of the construction is O(nLogn) as it calls update() for all n elements.

    2 直观解释

  • 1 C[i]表示f[1]…f[i]的和,而用tree[idx]表示某些子序列的和
  • 2 实际上tree[idx]是那些indexes from (idx - 2^r + 1) to idx的f[index]的和,其中r是idx最右边的那个非零位到右边末尾的0的个数,比如:
    • eg 2.0 当idx=8 decimal = 1000,有r=3,则,tree[8] = f[1] + … + f[8],
    • eg 2.1 当idx=11 decimal = 1011,有r=0,则,tree[11] = f[11],
    • eg 2.2 当idx=12 decimal = 1100,有r=2,则,tree[12] = f[9] + f[10] + f[11] + f[12],
    • eg 2.3 当idx=14 decimal = 1110,有r=1,则,tree[14] = f[13] + f[14]
  • 3 有了上面tree这个数组(也就是bit本体),我们可以得到: C[13] = tree[13] + tree[12] + tree[8]
    • 从上述例子可以得出一个重要结论:求前idx个和,也就是求C[idx]的时候,idx中1的个数即为构成C[idx]的子序列的个数,也就是有多少个tree中的元素加起来

      C1 = f1

      C2 = f1 + f2

      C3 = f3

      C4 = f1 + f2 + f3 + f4

      C5 = f5

      C6 = f5 + f6

      C7 = f7

      C8 = f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8



      C16 = f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 + f9 + f10 + f11 + f12 + f13 + f14 + f15 + f16

  • 4 有了3作为基础,求前缀和过程如下:4,5参考
    树状数组前缀和
    • 4.1 tree[y] 是 tree[x] 的父节点,当且仅当可以通过从 x 的二进制表示中去除最后一个设置位(即数位为1的位)来获得 y,即 y = x – (x & (-x))。
      • lowbit函数 就是 取最后一个设置位的函数,lowbit = [](int x) int {return (x & (-x));}
      • eg: tree[8]是tree[10]的父节点,因为 10 - (10&(-10)) == 8 为true
    • 4.2 节点 tree[y] 的子节点 tree[x] 存储了 y(inclusive) 和 x(exclusive) 之间元素的总和:arr[y,…,x)。
    • 4.3 实际例子:求C[11] = C[1011]:
      • 4.3.1 看下图即可,很显然我们需要沿着路径一直加到dummy node(tree[0]其值为0,方便运算而已)为止,从这里能够再一次看出,为何其前缀和的算法时间复杂度为O(log n),因为路径上的node个数就是C[1011]中的1的个数
      • C[1011] = C[11] = tree[11] + tree[10] + tree[8]
      • 4.3.2具体代码:
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        int getSum(int BITree[], int index)
        {
        int sum = 0; // Initialize result
        // index in BITree[] is 1 more than the index in arr[]
        index = index + 1;
        // Traverse ancestors of BITree[index]
        while (index>0)
        {
        // Add current element of BITree to sum
        sum += BITree[index];
        // Move index to parent node in getSum View
        index -= index & (-index);
        }
        return sum;
        }
  • 5 更新BITree
    • 5.1 类似4中的求和,更改一个节点需要更改所有被当前节点所影响的子节点
    • 5.2 子节点的获取: parent of idx = idx + (idx & (-idx));
    • 5.3 举个例子,如4中的图:对于idx = 2这个点,需要更新节点4,8
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void updateBIT(int BITree[], int n, int index, int val)
      {
      // index in BITree[] is 1 more than the index in arr[]
      index = index + 1;
      // Traverse all ancestors and add 'val'
      while (index <= n)
      {
      // Add 'val' to current node of BI Tree
      BITree[index] += val;
      // Update index to that of parent in update View
      index += index & (-index);
      }
      }

3 整体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// C++ code to demonstrate operations of Binary Index Tree
#include <iostream>

using namespace std;

/* n --> No. of elements present in input array.
BITree[0..n] --> Array that represents Binary Indexed Tree.
arr[0..n-1] --> Input array for which prefix sum is evaluated. */

// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
int sum = 0; // Initialize result

// index in BITree[] is 1 more than the index in arr[]
index = index + 1;

// Traverse ancestors of BITree[index]
while (index>0)
{
// Add current element of BITree to sum
sum += BITree[index];

// Move index to parent node in getSum View
index -= index & (-index);
}
return sum;
}

// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;

// Traverse all ancestors and add 'val'
while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;

// Update index to that of parent in update View
index += index & (-index);
}
}

// Constructs and returns a Binary Indexed Tree for given
// array of size n.
int *constructBITree(int arr[], int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;

// Store the actual values in BITree[] using update()
for (int i=0; i<n; i++)
updateBIT(BITree, n, i, arr[i]);

// Uncomment below lines to see contents of BITree[]
//for (int i=1; i<=n; i++)
// cout << BITree[i] << " ";

return BITree;
}


// Driver program to test above functions
int main()
{
int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(freq)/sizeof(freq[0]);
int *BITree = constructBITree(freq, n);
cout << "Sum of elements in arr[0..5] is "
<< getSum(BITree, 5);

// Let use test the update operation
freq[3] += 6;
updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[]

cout << "\nSum of elements in arr[0..5] after update is "
<< getSum(BITree, 5);

return 0;
}

实际例题

剑指 Offer 51. 数组中的逆序对

1 题目

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

2 解题思路

  • 1 思路:
    • 1.1 首先注意到:对于数组{5,5,2,3,6}而言,得到每个value的个数的统计:
      • index -> 1 2 3 4 5 6 7 8 9
      • value -> 0 1 1 0 2 1 0 0 0
    • 1.2 那么上述过程中,比如对于5,其贡献的逆序数对为5之前所有数字出现次数的和,也就是value数组中2之前的前缀和!
  • 2 那么如何快速获得前缀和呢?考虑使用BST来获取,参考:
    • 2.1 整体思路如下:
      • a 使用数字在数组中的排名来代替数字(这不会对逆序数对的个数产生影响)
      • b 对数组nums中的元素nums[i]从右到左构建BITree(i 从 n-1 到 0),注意,BITree所对应的前缀和是数组里数字出现次数的和
        • 比如进行到nums[i],那么nums[i]右边的数字都已经统计了他们的出现次数,而后获取nums[i] - 1的前缀和,即可获取所有 < nums[i]的数字在nums[i:n]中的出现次数之和,也就是nums[i]贡献的逆序数对的个数
        • 之所以是逆序遍历构建BITree,是因为对于nums[i],它能够贡献的逆序数对的个数仅仅出现在它的右侧,所以需要在右侧进行
    • 2.2 额外说一下数组离散化,也就是不关系数字大小本身,只关心他们之间的相对排位
      1
      2
      3
      4
      5
      sort(sortNoNums.begin(), sortNoNums.end(), std::less<int>());

      for(auto& num : nums) {
      num = lower_bound(sortNoNums.begin(), sortNoNums.end(), num) - sortNoNums.begin() + 1;
      }
      相似题目:
      https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
class BIT {
public:
vector<int> tree;
int n;
BIT(int _n): n(_n) , tree(_n + 1){cout << "init Done!" << endl;};

// find prefixSum with index x
int query(int x) {
int sum = 0;
while(x > 0) {
sum += tree[x];
x -= (x&(-x));
}
return sum;
}

// update x with delta val v
void update(int x, int v) {
cout << "d1"<< endl;
while(x <= n) {
tree[x] += v;
x += (x&(-x));
}
cout << "d2"<< endl;
}
};

int reversePairs(vector<int>& nums) {
// desrialization, using sort no to denote the value
vector<int> sortNoNums = nums;
sort(sortNoNums.begin(), sortNoNums.end(), std::less<int>());

for(auto& num : nums) {
num = lower_bound(sortNoNums.begin(), sortNoNums.end(), num) - sortNoNums.begin() + 1;
}

// using binary indexed tree to statistic the reversePair num
// start from the end of nums, so that the prefix in BIT means the reversePiar num
int ans = 0;
BIT bit(nums.size());
for(int i = nums.size() - 1; i >= 0; --i) {
ans += bit.query(nums[i] - 1); // cause only elements right than current num[i] will contribute to the ans
cout << ans << endl;
// statistic frequence of nums[i]
bit.update(nums[i], 1);
}

return ans;
}
};

0315. 计算右侧小于当前元素的个数

1 题目

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

题和逆序数对的计算方式相同:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

2 解题思路

  • 1 思路:
    • 1.1 首先注意到:对于数组{5,5,2,3,6}而言,得到每个value的个数的统计:
      • index -> 1 2 3 4 5 6 7 8 9
      • value -> 0 1 1 0 2 1 0 0 0
    • 1.2 那么上述过程中,比如对于5,其贡献的逆序数对为5之前所有数字出现次数的和,也就是value数组中2之前的前缀和!
  • 2 那么如何快速获得前缀和呢?考虑使用BST来获取,参考:https://xychen5.github.io/2021/12/15/dataStructure-BinaryIndexedTree/
    • 2.1 整体思路如下:
      • a 使用数字在数组中的排名来代替数字(这不会对逆序数对的个数产生影响)
      • b 对数组nums中的元素nums[i]从右到左构建BITree(i 从 n-1 到 0),注意,BITree所对应的前缀和是数组里数字出现次数的和
        • 比如进行到nums[i],那么nums[i]右边的数字都已经统计了他们的出现次数,而后获取nums[i] - 1的前缀和,即可获取所有 < nums[i]的数字在nums[i:n]中的出现次数之和,也就是nums[i]贡献的逆序数对的个数
        • 之所以是逆序遍历构建BITree,是因为对于nums[i],它能够贡献的逆序数对的个数仅仅出现在它的右侧,所以需要在右侧进行
    • 2.2 额外说一下数组离散化,也就是不关系数字大小本身,只关心他们之间的相对排位
      1
      2
      3
      4
      5
      sort(sortNoNums.begin(), sortNoNums.end(), std::less<int>());

      for(auto& num : nums) {
      num = lower_bound(sortNoNums.begin(), sortNoNums.end(), num) - sortNoNums.begin() + 1;
      }
      如下的过程并没有使用离散化,但是空间浪费也不是很多,超过百分之83吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
class BIT {
public:
vector<int> tree;
int n;
BIT(int _n): n(_n) , tree(_n + 1){cout << "init Done!" << endl;};

// find prefixSum with index x
int query(int x) {
int sum = 0;
while(x > 0) {
sum += tree[x];
x -= (x&(-x));
}
return sum;
}

// update x with delta val v
void update(int x, int v) {
cout << "d1"<< endl;
while(x <= n) {
tree[x] += v;
x += (x&(-x));
}
cout << "d2"<< endl;
}
};

int reversePairs(vector<int>& nums) {
// desrialization, using sort no to denote the value
vector<int> sortNoNums = nums;
sort(sortNoNums.begin(), sortNoNums.end(), std::less<int>());

for(auto& num : nums) {
num = lower_bound(sortNoNums.begin(), sortNoNums.end(), num) - sortNoNums.begin() + 1;
}

// using binary indexed tree to statistic the reversePair num
// start from the end of nums, so that the prefix in BIT means the reversePiar num
int ans = 0;
BIT bit(nums.size());
for(int i = nums.size() - 1; i >= 0; --i) {
ans += bit.query(nums[i] - 1); // cause only elements right than current num[i] will contribute to the ans
cout << ans << endl;
// statistic frequence of nums[i]
bit.update(nums[i], 1);
}

return ans;
}
};

0327. 区间和的个数

1 题目

https://leetcode-cn.com/problems/count-of-range-sum/

题和逆序数对的计算方式相同:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
就是做了一个小改变而已,很多统计区间值的,st-ed < tar, 本来是让你找一个st,ed的对子的,那么就会转换思路为:
对于每一个ed找st,什么样的呢? st < ed + tar
然后找这样的st就有很多方法,比如hash,前缀和,bitree,priority_queue

2 解题思路

  • 1 求逆序对的思路:
    • 1.1 首先注意到:对于数组{5,5,2,3,6}而言,得到每个value的个数的统计:
      • index -> 1 2 3 4 5 6 7 8 9
      • value -> 0 1 1 0 2 1 0 0 0
    • 1.2 那么上述过程中,比如对于5,其贡献的逆序数对为5之前所有数字出现次数的和,也就是value数组中2之前的前缀和!
  • 2 那么如何快速获得前缀和呢?考虑使用BST来获取,参考:https://xychen5.github.io/2021/12/15/dataStructure-BinaryIndexedTree/
    • 2.1 整体思路如下:
      • a 使用数字在数组中的排名来代替数字(这不会对逆序数对的个数产生影响)
      • b 对数组nums中的元素nums[i]从右到左构建BITree(i 从 n-1 到 0),注意,BITree所对应的前缀和是数组里数字出现次数的和
        • 比如进行到nums[i],那么nums[i]右边的数字都已经统计了他们的出现次数,而后获取nums[i] - 1的前缀和,即可获取所有 < nums[i]的数字在nums[i:n]中的出现次数之和,也就是nums[i]贡献的逆序数对的个数
        • 之所以是逆序遍历构建BITree,是因为对于nums[i],它能够贡献的逆序数对的个数仅仅出现在它的右侧,所以需要在右侧进行
    • 2.2 额外说一下数组离散化,也就是不关系数字大小本身,只关心他们之间的相对排位
  • 3 那么小改变在哪里呢?
    • 就是查一次查不出来了,要查两次做一个差
    • 还有一点就是,注意将所有要query和update的值,都用序号表示,这样避免tree过大
      1
      2
      3
      for a valid s(i, j) we shall find:
      preSum[j] - ub <= preSum[i] <= preSum[j] - lb
      we just need to statistic those preSum[i] for each j
      实现代码如下:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      class Solution {
      public:
      // when count the num, try to use BItree to count the appeared num, prefixSum to
      // get how many < curNum will be fast
      class BITree{
      public:
      int n;
      vector<int> tree;
      BITree (int _n) : n(_n), tree(_n + 1) {}

      int lowBit(int x) {
      return x & (-x);
      }

      int query(int x) {
      int sum = 0;
      while(x > 0) {
      sum += tree[x];
      x -= lowBit(x);
      }
      return sum;
      }

      void update(int x, int val) {
      while(x <= n) {
      // cout << "x and tree[x] " << x << "->" << tree[x] << endl;
      tree[x] += val;
      x += lowBit(x);
      }
      }
      };


      int countRangeSum(vector<int>& nums, int lower, int upper) {
      unordered_map<int, int> numToIdx;
      set<long long> tmpNums;
      vector<long long> prefixSum = {0};

      for(int i = 0; i < nums.size(); ++i) {
      prefixSum.emplace_back(nums[i] + prefixSum.back());
      }

      for(auto ps : prefixSum) {
      tmpNums.insert(ps);
      tmpNums.insert(ps - lower);
      tmpNums.insert(ps - upper);
      }

      int i = 1;
      for(auto num : tmpNums) {
      numToIdx[num] = i++;
      }

      // for a valid s(i, j) we shall find:
      // preSum[j] - ub <= preSum[i] <= preSum[j] - lb
      // we just need to statistic those preSum[i] for each j
      int n = tmpNums.size();
      BITree tree(n + 1);
      long long ans = 0;
      for(int j = 0; j < prefixSum.size(); ++j) {
      int leftBound = numToIdx[prefixSum[j] - upper];
      int rightBound = numToIdx[prefixSum[j] - lower];
      // cout << "lb, rb = " << leftBound << " " << rightBound << endl;
      ans += (tree.query(rightBound) - tree.query(leftBound - 1));
      // cout << "ans = " << ans << "preFixSumSize = " << prefixSum.size() << endl;
      tree.update(numToIdx[prefixSum[j]], 1); // avoid 0 to produce dead loop
      }
      return ans;
      }
      };

3 使用线段树解题

注意其中很重要的一点:
对于线段树中插入一个节点时,需要对沿路所有节点的sum加上要插入的节点的值,找这个节点位置的时候,
需要找到root左右管辖范围的中间值mid,此时务必使用>>1去做,因为获得mid我们要求其为 floor(left + right),
但是:(cpp和python对于移位和除法的逻辑是相同的),这里就显示出了2者的区别,
当然在数字都为正数的时候不会出错!

1
2
3
4
>>> int((-1 + 0) / 2)
0
>>> int((-1 + 0) >> 1)
-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
class Solution {
public:
class SegTree {
public:
struct SegNode {
long long leftBound = 0, rightBound = 0, curSum = 0;
SegNode* lChild = nullptr;
SegNode* rChild = nullptr;
SegNode(long long lb, long long rb) :
leftBound(lb),
rightBound(rb),
curSum(0),
lChild(nullptr),
rChild(nullptr) {
}
};

SegNode* root;


SegTree(long long left, long long right) {
root = build(left, right);
}

SegTree() {}

SegNode* build(long long l, long long r) {
SegNode* node = new SegNode(l, r);
if(l == r) {
return node;
}

long long mid = (l + r) / 2;
node->lChild = build(l, mid);
node->rChild = build(mid + 1, r);
return node;
}

void insert(SegNode* root, long long tarIdx, long long val) {
root->curSum += val;
if(root->leftBound == root->rightBound) {
return;
}
long long mid = (root->leftBound + root->rightBound) >> 1;
// long long mid = (root->leftBound + root->rightBound) / 2;
// there are identicial difference between them two:
// eg: when left == -1, right = 0;
// case1 => (left + right) / 2 == 0
// case1 => (left + right) >> 1 == -1
// cout << "d1 " << tarIdx << " mid: " << mid << " root:l/r: " << root->leftBound << "/" << root->rightBound << endl;
if(tarIdx <= mid) {
// cout << "d2" << endl;
if (nullptr == root->lChild) {
// cout << "d2.5" << endl;
root->lChild = new SegNode(root->leftBound, mid);
}
insert(root->lChild, tarIdx, val);
}
else{
// cout << "d3" << endl;
if (nullptr == root->rChild) {
root->rChild = new SegNode(mid + 1, root->rightBound);
}
insert(root->rChild, tarIdx, val);
}
}

long long getSum(SegNode* root, long long left, long long right) const {
if(nullptr == root) {
return 0;
}
// 当前节点位于目标区间外
if(left > root->rightBound || right < root->leftBound) {
return 0;
}
// 当前节点位于目标区间内
if(left <= root->leftBound && right >= root->rightBound) {
// cout << "left/right" << left << "/" << right << " => " << root->curSum << endl;
return root->curSum;
}
return getSum(root->lChild, left, right) + getSum(root->rChild, left, right);
}

};

int countRangeSum(vector<int>& nums, int lower, int upper) {
unordered_map<int, int> numToIdx;
set<long long> tmpNums;
vector<long long> prefixSum = {0};

for(int i = 0; i < nums.size(); ++i) {
prefixSum.emplace_back(nums[i] + prefixSum.back());
}

for(auto ps : prefixSum) {
tmpNums.insert(ps);
tmpNums.insert(ps - lower);
tmpNums.insert(ps - upper);
}

int i = 1;
for(auto num : tmpNums) {
numToIdx[num] = i++;
}

// for a valid s(i, j) we shall find:
// preSum[j] - ub <= preSum[i] <= preSum[j] - lb
// we just need to statistic those preSum[i] for each j
int n = tmpNums.size();
// BITree tree(n + 1);
long long ans = 0;
// for(int j = 0; j < prefixSum.size(); ++j) {
// int leftBound = numToIdx[prefixSum[j] - upper];
// int rightBound = numToIdx[prefixSum[j] - lower];
// // cout << "lb, rb = " << leftBound << " " << rightBound << endl;
// ans += (tree.query(rightBound) - tree.query(leftBound - 1));
// // cout << "ans = " << ans << "preFixSumSize = " << prefixSum.size() << endl;
// tree.update(numToIdx[prefixSum[j]], 1); // avoid 0 to produce dead loop
// }

// try to use segnode tree to sovle the problem, this will exceed the time limitation
// SegTree tree(0, n + 1);
// for(int j = 0; j < prefixSum.size(); ++j) {
// int left = numToIdx[prefixSum[j] - upper];
// int right = numToIdx[prefixSum[j] - lower];
// ans += tree.getSum(tree.root, left, right);
// // cout << "lb, rb = " << left<< " " << right<< " ==> " << ans << endl;
// tree.insert(tree.root, numToIdx[prefixSum[j]], 1);
// // cout << "insert: " << numToIdx[prefixSum[j]] << "curRoot: " << tree.root->curSum << endl;
// }

// we do not do the deserialization
long long minLeft = LLONG_MAX, maxRight = LLONG_MIN;
for(long long x : prefixSum) {
minLeft = min({minLeft, x, x - lower, x - upper});
maxRight = max({maxRight, x, x - lower, x - upper});
}

// cout << "minL, maxR" << minLeft << " " << maxRight <<endl;
SegTree tree;
tree.root = new SegTree::SegNode(minLeft, maxRight);
// reason why we insert the prefixSum of 0, because for the first ele:
// if it statisfy the interval, then it will be statisticed because the 0
for(long long x : prefixSum) {
ans += tree.getSum(tree.root, x - upper, x - lower);
// cout << "lb, rb = " << x - upper<< " " << x - lower << " ==> ans = " << ans << endl;
tree.insert(tree.root, x, 1);
// cout << "insert: " << x << "curRoot: " << tree.root->curSum << endl;
}

return ans;
}
}

0493 翻转对

1 题目

https://leetcode-cn.com/problems/reverse-pairs/

题和逆序数对的计算方式相同:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
就是做了一个小改变而已,很多统计区间值的,st-ed < tar, 本来是让你找一个st,ed的对子的,那么就会转换思路为:
对于每一个ed找st,什么样的呢? st < ed + tar
然后找这样的st就有很多方法,比如hash,前缀和,bitree,priority_queue

2 解题思路

  • 1 求逆序对的思路:
    • 1.1 首先注意到:对于数组{5,5,2,3,6}而言,得到每个value的个数的统计:
      • index -> 1 2 3 4 5 6 7 8 9
      • value -> 0 1 1 0 2 1 0 0 0
    • 1.2 那么上述过程中,比如对于5,其贡献的逆序数对为5之前所有数字出现次数的和,也就是value数组中2之前的前缀和!
  • 2 那么如何快速获得前缀和呢?考虑使用BST来获取,参考:https://xychen5.github.io/2021/12/15/dataStructure-BinaryIndexedTree/
    • 2.1 整体思路如下:
      • a 使用数字在数组中的排名来代替数字(这不会对逆序数对的个数产生影响)
      • b 对数组nums中的元素nums[i]从右到左构建BITree(i 从 n-1 到 0),注意,BITree所对应的前缀和是数组里数字出现次数的和
        • 比如进行到nums[i],那么nums[i]右边的数字都已经统计了他们的出现次数,而后获取nums[i] - 1的前缀和,即可获取所有 < nums[i]的数字在nums[i:n]中的出现次数之和,也就是nums[i]贡献的逆序数对的个数
        • 之所以是逆序遍历构建BITree,是因为对于nums[i],它能够贡献的逆序数对的个数仅仅出现在它的右侧,所以需要在右侧进行
    • 2.2 额外说一下数组离散化,也就是不关系数字大小本身,只关心他们之间的相对排位
  • 3 那么小改变在哪里呢?
    • 对于每个j,找位于它之前的数字,满足:nums[i] > 2*nums[j]
    • 找的方法为用总体减去目标的补集:用nums[j]之前所有的数字的个数,减去小于等于nums[j] * 2的数字就行

      for each j, find those nums[i]:
      which satisty: i < j && nums[i] > 2*nums[j]

      so, we can get this by: using all to sub those nums[i] <= nums[j] * 2 to get the res
      preSum[1 -> 2*n] - preSum[1 -> 2*nums[j]]

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:

class BITree {
public:
long long n;
vector<long long> tree;
BITree(long long _n) : n(_n), tree(_n + 1) {}

long long lowBit(long long x) {
return x & (-x);
}

long long query(long long x) {
long long sum = 0;
while(x > 0) {
sum += tree[x];
x -= lowBit(x);
}
return sum;
}

void update(long long x, long long val) {
while(x <= n) {
tree[x] += val;
x += lowBit(x);
}
}
};

int reversePairs(vector<int>& nums) {
// deserialization
vector<long long> tmpNums;
for(auto num : nums) {
tmpNums.emplace_back(num);
tmpNums.emplace_back(num * 2LL);
}
sort(tmpNums.begin(), tmpNums.end(), [](long a, long b) {
return a < b;
});

// for(auto& num : tmpNums) { cout << "tmp: " << num << endl;}

// for(auto& num : nums) {
// num = lower_bound(tmpNums.begin(), tmpNums.end(), num) - tmpNums.begin() + 1; // +1 to avoid update(0, 1) failure
// }

for(auto& num : nums) { cout << "num No: " << num << endl;}

// deserialization
int idx = 1;
unordered_map<long long,long long> numToIdx;
for(auto num : tmpNums) {
numToIdx[num] = idx ++;
}

int n = nums.size();
int ans = 0;
BITree tree(2 * n);
// for each j, find those nums[i]:
// which satisty: i < j && nums[i] > 2*nums[j]
//
// so, we can get this by: using all to sub those nums[i] <= nums[j] * 2 to get the res
// preSum[1 -> 2*n] - preSum[1 -> 2*nums[j]]
for(int i = 0; i < n; ++i) {
// cout << "counting: " << nums[i] << endl;
// attention the diff between 2LL and 2
ans += (tree.query( 2LL*n ) - tree.query(numToIdx[2LL * nums[i]]));
tree.update(numToIdx[nums[i]], 1);
}

return ans;
}
}

0 递归和bst

1 构建bst 0108. 将有序数组转换为二叉搜索树

1 题目

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

2 解题思路

  • 1 AVL tree最主要的特性在于,任何子树的左子树和右子树的高度差不超过1,所以方法为:
    • 1.1 每次找到数组中间的值作为root,然后两边分别作为左右子树,左边都比root小,右边都大,刚好满足AVL要求
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      /**
      * Definition for a binary tree node.
      * struct TreeNode {
      * int val;
      * TreeNode *left;
      * TreeNode *right;
      * TreeNode() : val(0), left(nullptr), right(nullptr) {}
      * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
      * };
      */
      class Solution {
      public:
      TreeNode* sortedArrayToBST(vector<int>& nums) {
      // find root whose left size and right size shall equal
      int n = nums.size();
      if(n <= 0) {
      return nullptr;
      }
      vector<int> left(nums.begin(), nums.begin() + n / 2);
      vector<int> right(nums.begin() + n / 2 + 1, nums.end());
      TreeNode* root = new TreeNode(
      nums[n/2]
      sortedArrayToBST(left),
      sortedArrayToBST(right)
      );
      return root;
      }
      };

2 select k from n: C(n, k)

1
2
3
4
5
6
7
8
9
10
11
void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
if(k == 0) {
res.emplace_back(tmpRes);
return;
}
for(int i = st; i < nums.size() - k + 1; ++i) {
tmpRes.emplace_back(nums[i]);
selectKFromN(i + 1, k - 1, res, nums, tmpRes);
tmpRes.pop_back();
}
}

1 递归

0025 最大因数联通分量大小

1 题目

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

2 解题思路

  • 1 个人思路:
    • 首先很明显能够发现子问题的痕迹,子问题就是翻转长度为k的链表
    • 翻转用长度为k的栈去模拟即可
  • 2 优化: 使用常数空间:
    • 使用三个指针,a->b->c的链表的话,那么就是说(三个指针相当于滑动窗口的感觉):
    • 记录下a,b,c的指针,然后把a<-b<-c,然后移动这三个指针即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/** 
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// return headK -> reverse(afterHeadK, k);
return reverse(head, k);
}

ListNode* reverse(ListNode* head, int k ) {
ListNode* tmp = head;
vector<ListNode*> vec = {};
for(int i = 0; i < k; ++i) {
if(tmp != nullptr) {
vec.emplace_back(tmp);
tmp = tmp -> next;
}
}

if(vec.size() != k) {
return head;
}

ListNode* nextHead = vec.back()->next;

for(int i = k-1; i >= 1; --i) {
// cout << i << "**" << endl;
vec[i]->next = vec[i-1];
// cout << vec[i]->val << " -> " << vec[i-1]->val << endl;
}
vec[0]->next = reverse(nextHead, k);

// cout << "asdf**" << endl;
return vec.back();
}
};

1.1

0761 makeLargestSpecial 特殊的二进制序列

1 题目

https://leetcode-cn.com/problems/special-binary-string

2 解题思路

  • 1 个人思路:
    • 首先这个特殊子序列,采用合理的括号串去理解特殊子序列就好了
    • 然后大致的递归思路:
      • 1.1 首先找到原来串里所有特殊的子序列
      • 1.2 将这些子序列按照字典序排序
      • 1.3 排序后加起来得到结果
      • 1.4 eg: 10 1100 111000,这个串可以分成三个特殊子序列:那么最大字典序显然就是 111000 1100 10
    • 上面的还有其他问题,若子串一开始不能分为特殊子序列呢?
      • eg:1 10 1100 0, 那么首先剥去外壳,然后再递归进去,对10 1100采用上述子序列方法
    • 递归返回?当子序列长度小于等于2,就直接返回字符串北盛即可
    • 有个很容易出错误的示例需要注意:

      we shall reArrange first and then sort,
      because when we reArrage, we my produce bigger subStr,
      if we sort first and reArrange all subpart we could get false res: eg:
      input: “11100011010101100100”
      false Result: “111000 11100101010100” // part2 is bigger subStr, so we shall reArrange all sub first and then sort
      std result: “11100101010100 111000”

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      class Solution {
      public:
      string makeLargestSpecial(string s) {
      string res = reArrange(s);
      // string lastRes = "";
      // while(res != reArrange(res)){
      // res = reArrange(res);
      // };
      return res;
      }

      string reArrange(string s) {
      // cout << "c1->" << s << endl;
      int n = s.size();
      if(s.size() <= 2) {
      // cout << "less than 2: " << s << endl;
      return s;
      }

      // firstly, get all special subStr and sort as the lexical order
      vector<string> subStr;

      int st = 0;
      int cntRedundantNumberOne = 1;
      for(int i = st + 1; i < n; ++i) {
      cntRedundantNumberOne += (s[i] == '1' ? 1 : -1);
      if(0 == cntRedundantNumberOne) {
      subStr.emplace_back(s.substr(st, i - st + 1));
      st = i + 1;
      cntRedundantNumberOne = 0;
      }
      }

      if(1 == subStr.size()) {

      return s.substr(0, 1) + reArrange(s.substr(1, n-2)) + s.substr(n-2, 1);
      }

      // for(auto i : subStr) {
      // cout << i << endl;
      // }


      // secondly, sort all sub part and sum up
      // cout << "a" << endl;
      for(int i = 0; i < subStr.size(); ++i) {
      subStr[i] = reArrange(subStr[i]);
      }
      // we shall reArrange first and then sort,
      // because when we reArrage, we my produce bigger subStr,
      // if we sort first and reArrange all subpart we could get false res: eg:
      // input: "11100011010101100100"
      // false Result: "111000 11100101010100" // part2 is bigger subStr, so we shall reArrange all sub first and then sort
      // std result: "11100101010100 111000"
      sort(subStr.begin(), subStr.end(), std::greater<string>());

      string res = "";
      for(auto s : subStr) {
      res += s;
      }

      // cout << "c2" << endl;
      return res;
      }
      };

0010 isMatch 正则表达式匹配

1 题目

https://leetcode-cn.com/problems/regular-expression-matching

2 解题思路

  • 0 心得:
    • 递归适用于减小规模后问题的处理方式不会发生改变的场景
    • 对于递归,得明白当层递归处理会如何将问题规模减小
  • 1 个人思路:
    • 首先这个字符串匹配,需要理解每一次能够用p去匹配什么?然后怎么匹配
    • 1.1 首先每次递归,p的规模减小肯定是在p的头部: 对于p的匹配类型,有3种:
      • 1.1.1 s = ab, p = ab, 那么就用p的第一个字母去匹配
      • 1.1.2 s = a, p = ., 同样需要用p的第一个字幕去匹配
      • 1.1.3 带*的,这个需要将p的头两个拿去和s匹配:
        • s = a, p1 = .*, p2 = a*,这两种情况,都是满足需要的
        • s = a, p1 = c*.*,那么第一个c*是不匹配的,同样的还有.*是否需要匹配的问题
    • 然后大致的递归思路:
      • 1.1 首先从p的头部分析是哪种子模式
      • 1.2 按照该种子模式匹配
      • 1.3 递归到下层的p和s,这样p和s都因为1.1~1.2的过程中变小了,完成了使用递归解决问题的思路
    • 递归返回?
      • 1.1 s的长度为0?
      • 1.2 p的长度为0?
    • 对于上述过程不清楚的请以下面两个结果作为例子:
      1
      2
      3
      4
      5
      6
      7
      "bcabac"
      "a*a*.*b*b*"
      return: true

      "a"
      ".*..a*"
      return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
public:
bool isMatch(string s, string p) {
return greadyMatch(s, p);
}

bool greadyMatch(string s, string p) {
int sLen = s.size();
int pLen = p.size();
// cout << "sLen & pLen => " << sLen << " " << pLen << s << " " << p << endl;
if(pLen == 2 && p[0] == '.' && p[1] == '*') {
return true;
}

if(pLen == 1) {
if(sLen != 1) {
return false;
}
return p[0] == '.' ? true : p[0] == s[0];
}

if(sLen == 0) {
if(pLen == 0) {
return true;
}
if(pLen == 2) {
if(p[1] == '*') {
return true;
}else {
return false;
}
} else {
if(p[1] == '*') {
return greadyMatch(s, p.substr(2));
} else {
return false;
}
}
}

if(pLen == 0) {
return sLen == 0;
}

// match as much as possible
char head0 = p[0];
char head1 = p[1];
bool res = false;

if(p[0] == '.') {
if(p[1] == '*') {
// match any len >= 1 of s, when len == 0, then not match
for(int len = 0; len <= sLen; ++len) {
res = res || greadyMatch(s.substr(len), p.substr(2));
// cout << "tried: " << s.substr(len) << " " << p.substr(2) << endl;
}
return res;
} else {
return greadyMatch(s.substr(1), p.substr(1));
}
} else {
// p[0] = a~z
if(p[0] != s[0]) {
if(p[1] == '*') {
// cout << p.substr(2) << "\nculled!" <<endl;
return greadyMatch(s, p.substr(2));
} else {
return false;
}
} else {

if(p[1] == '*') {
int sameLen = s.find_first_not_of(p[0]);
if(sameLen == -1) {
sameLen = sLen;
}
// cout << "sameLen2 -> " << sameLen << s.substr(1) << p.substr(2) << endl;
// when len = 0, not use this * to match
for(int len = 0; len <= sameLen; ++len) {
res = res || greadyMatch(s.substr(len), p.substr(2));
}
return res;
} else {
return greadyMatch(s.substr(1), p.substr(1));
}
}

}

// never be executed
return res;
}
};

2 二叉搜索树(平衡意味着任意两个子树高度差不应该大于1)

1373 maxSumBST 二叉搜索子树的最大键值和

1 题目

https://leetcode-cn.com/problems/maximum-sum-bst-in-binary-tree/

2 解题思路

  • 1 采用后续遍历,(前中后遍历的前中后是针对root节点的访问时期和左右子树的比较)
  • 2 对于每个节点,维持该节点的4个值:
    • int sum = 0; // 子树的所有和
    • int isBST = false; // 该节点为root的子树是否为BST
    • int maxVal = INT_MIN; // 该节点对应子树最大值
    • int minVal = INT_MAX; // 该节点对应子树最小值
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      /**
      * Definition for a binary tree node.
      * struct TreeNode {
      * int val;
      * TreeNode *left;
      * TreeNode *right;
      * TreeNode() : val(0), left(nullptr), right(nullptr) {}
      * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
      * };
      */
      class Solution {
      public:
      struct entry {
      int sum = 0;
      int isBST = false;
      int maxVal = INT_MIN;
      int minVal = INT_MAX;
      entry() {};
      };
      map<void*, entry> bstRec;

      void dfs(TreeNode* root, int& res) {
      if(nullptr == root) {
      return;
      }
      dfs(root->left, res);
      dfs(root->right, res);

      // curRoot
      entry tmp;
      if(nullptr != root->left && nullptr != root->right) {
      tmp.sum = root->val + bstRec[root->right].sum + bstRec[root->left].sum;
      tmp.isBST = bstRec[root->right].isBST && \
      root->val < bstRec[root->right].minVal && \
      root->val > bstRec[root->left].maxVal;
      tmp.maxVal = max(root->val, bstRec[root->left].maxVal);
      tmp.maxVal = max(tmp.maxVal, bstRec[root->right].maxVal);
      tmp.minVal = min(root->val, bstRec[root->left].minVal);
      tmp.minVal = min(tmp.minVal, bstRec[root->right].minVal);
      } else if(nullptr == root->left && nullptr != root->right) {
      tmp.sum = root->val + bstRec[root->right].sum;
      tmp.isBST = bstRec[root->right].isBST && root->val < bstRec[root->right].minVal;
      tmp.maxVal = max(root->val, bstRec[root->right].maxVal);
      tmp.minVal = min(root->val, bstRec[root->right].minVal);
      } else if(nullptr != root->left && nullptr == root->right) {
      tmp.sum = root->val + bstRec[root->left].sum;
      tmp.isBST = bstRec[root->left].isBST && root->val > bstRec[root->left].maxVal;
      tmp.maxVal = max(root->val, bstRec[root->left].maxVal);
      tmp.minVal = min(root->val, bstRec[root->left].minVal);
      } else {
      tmp.sum = root->val;
      tmp.isBST = true;
      tmp.maxVal = root->val;
      tmp.minVal = root->val;
      }
      if(tmp.isBST) {
      res = max(res, tmp.sum);
      }
      // cout << root->val << " -> " << tmp.sum << endl;;
      bstRec[root] = tmp;

      }

      int maxSumBST(TreeNode* root) {
      int res = 0;
      dfs(root, res);
      return res;
      }
      };

1569. 将子数组重新排序得到同一个二叉查找树的方案数

1 题目

https://leetcode-cn.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

2 解题思路

  • 1 阅读提示即可,大致思路如下:
    • 1.1 首先,意识到第一个数必然为二叉树的root,那么找出左边的节点和右边的节点分别记为lt,和rt
    • 1.2 首先假设我们知道了以lt和rt的不改变子树结构的重排序方案数字为findWays(lt), findWays(rt)
    • 1.3 那么我们只需要思考,如何利用1.2的结果来获得当前root的结果:
      • 很显然,我们只需要确定lt和rt在root对应的整个序列(长度记录为n)中放置方法有多少种方案?进一步分析:在不改变lt序列内部相对顺序的情况下,找出有多少繁殖lt序列的方法?那么不就是n-1中选出lt长度记为k个位置的方法数字吗?
      • 上述答案显而易见: c(n-1, k) = (n-1)!/(n-1-k)!/(k)!;
  • 2 接着就是大数问题:由于n最大为1000,它的阶乘显然溢出,于是上面的直接计算阶乘的方案就失效,采用动动态规划的方法去算阶乘:
    • c(n, k) = c(n-1, k) + c(n-1, k-1)
    • 直观上来看假设原来只有n-1个物品选择k个,现在多加了一个物品,还是选择k个,那么方案数增加了:从 n 个物品中选择 k 个的方案数,等于从前 n-1 个物品中选择 k 个的方案数,加上从前 n-1 个物品中选择 k-1个(再选上第 nn 个物品)的方案数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
static constexpr long long largePrime = 1000000007;

vector<long long> factorial;

vector<vector<int>> c;

int numOfWays(vector<int>& nums) {
long long ans = 0;
int n = nums.size();
factorial.resize(1000, 1);
// for(long long i = 1; i < 1000; ++i) {
// factorial[i] = i * (factorial[i-1] % largePrime);
// // cout << i << "->" << factorial[i] << endl;
// factorial[i] %= largePrime;
// }

c.assign(n, vector<int>(n));
c[0][0] = 1;
// cal c(n, m) = c(n-1, m) + c(n-1, m-1);
for(int i = 1; i < n; ++i) {
c[i][0] = 1;
for(int j = 1; j < n; ++j) {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % largePrime;
}
}

ans = findWays(nums);

return ans - 1;
}

long long findWays(vector<int>& nums) {
int n = nums.size();
if(n <= 2) {
return 1;
}

int root = nums[0];
vector<int> left;
vector<int> right;
for(int i = 1; i < nums.size(); ++i) {
if(nums[i] < root) {
left.emplace_back(nums[i]);
} else {
right.emplace_back(nums[i]);
}
}

// that means:
// for the left tree, all nodes shall seat in the other places(and not change the relative order)
// except root pos find the way out(the way shall equal:
// pick nodes size seat from all seats, that is c(n, m-1);
// ) and mutiply the two subTree arrange way num
int seats = n - 1;
int nodesToSeat = left.size();
// cout << "c(n, k) " << seats << " -> " << nodesToSeat << " = " << c[seats][nodesToSeat] << endl;
// cout << "l r : " << findWays(left) << " " << findWays(right) << endl;
// return ((findWays(left) % largePrime )* (findWays(right) % largePrime)) * (getWaysForCurLevel(seats, nodesToSeat) % largePrime);
return findWays(left) % largePrime * findWays(right) % largePrime * c[seats][nodesToSeat] % largePrime;
}

long long getWaysForCurLevel(int seats, int nodesToSeat) {
cout << "c(n, k)2 :" << factorial[seats] << " " << factorial[nodesToSeat] << " " << factorial[seats - nodesToSeat] << endl;;
return factorial[seats] / factorial[nodesToSeat] / factorial[seats - nodesToSeat];
}
};

0095. 不同的二叉搜索树 II

1 题目

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

2 解题思路

  • 1 首先明确一点,递归的主体为,从nums的数组中返回对应的所有可能的bst树
    • 1.1 输入: vector
    • 1.2 返回: vector<treeNode*>
  • 2 于是递归思路的想法就来了:
    • 2.1 对于一个node如何生成其所有可能的二叉树呢?我们只考虑第1层到第2层的(因为其他所有层的递归都是一样的逻辑,除非返回层不太一样)
      • 2.1.1 从nums中选择一个作为root,左边的numsLeft和右边的numsRight分别获取root的所有左右子树
      • 2.1.2 递归调用函数从numsLeft得到leftTrees,相应的得到rightTrees
      • 2.1.3 得到leftTrees和rightTrees以后,采用2层for循环和root拼装,得到最后的树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<int> nodes;
for(int i = 0; i < n; ++i) {
nodes.emplace_back(i+1);
}
vector<TreeNode*> res;
return getTreesFromArray(nodes);
}

vector<TreeNode*> getTreesFromArray(vector<int>& nodes) {
int n = nodes.size();
vector<TreeNode*> tmpRes;
if(0 == n) {
return {nullptr};
}
for(int i = 0; i < n; ++i) {
int rootVal = nodes[i];
vector<int> tmpLeft(nodes.begin(), nodes.begin() + i);
vector<int> tmpRight(nodes.begin() + i + 1, nodes.end());
vector<TreeNode*> left = getTreesFromArray(tmpLeft);
vector<TreeNode*> right = getTreesFromArray(tmpRight);
for(int m = 0; m < left.size(); ++m) {
for(int n = 0; n < right.size(); ++n) {
TreeNode* root = new TreeNode(rootVal, left[m], right[n]);
tmpRes.emplace_back(root);
}
}
}
return tmpRes;
}
}

0000 面试题 04.09. 二叉搜索树序列

1 题目

https://leetcode-cn.com/problems/bst-sequences-lcci/

2 解题思路

  • 1 首先明确一点,递归的主体为,从root对应的tree中获取所有可能的bst子树序列
    • 1.1 输入: treeNode*
    • 1.2 返回: vector<vector>
  • 2 于是递归思路的想法就来了:
    • 2.1 对于一个root如何生成其所有可能的二叉树序列呢?我们只考虑第1层到第2层的(因为其他所有层的递归都是一样的逻辑,除非返回层不太一样)

经典写法:

1
2
3
4
5
6
7
8
9
10
11
void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
if(k == 0) {
res.emplace_back(tmpRes);
return;
}
for(int i = st; i < nums.size() - k + 1; ++i) {
tmpRes.emplace_back(nums[i]);
selectKFromN(i + 1, k - 1, res, nums, tmpRes);
tmpRes.pop_back();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> BSTSequences(TreeNode* root) {
return getSequencesFromRoot(root);
}

vector<vector<int>> getSequencesFromRoot(TreeNode* root) {
if(nullptr == root) {
return {{}};
}

vector<vector<int>> sequences;
// for(auto seq : s) {
// s.emplace_back(root->val);
// }
// get left sequences and right
vector<vector<int>> lSeqs = getSequencesFromRoot(root->left);
vector<vector<int>> rSeqs = getSequencesFromRoot(root->right);
int lSize = lSeqs[0].size();
int rSize = rSeqs[0].size();

// cout << "d0" << endl;
// select lSize's positions in lSize + rSize + 1 's vector
vector<vector<int>> res;
vector<int> nums;
for(int i = 0; i < lSize + rSize; ++i) {
nums.emplace_back(i+1);
}
vector<int> tmpRes;
// cout << "d1" << endl;
selectKFromN(0, lSize, res, nums, tmpRes);

int seqLen = lSeqs[0].size() + rSeqs[0].size() + 1;
// cout << "d2 " << lSize << "@" << rSize << "=" << seqLen << endl;

for(auto & lSeq : lSeqs) {
for(auto & rSeq : rSeqs) {

// cout << "d3" << endl;
vector<int> tmpSeq(seqLen);
tmpSeq[0] = root->val;

for(auto & idxVecForLeft : res) {
int curLeft = 0;
int curRight = 0;
int lastLeft = 1;
vector<bool> forRight(seqLen, true);

// cout << "d4" << endl;
for(auto lIdx : idxVecForLeft) {
tmpSeq[lIdx] = lSeq[curLeft++];
forRight[lIdx] = false;
}
for(int i = 1; i < seqLen; ++i) {
if(forRight[i]) {
tmpSeq[i] = rSeq[curRight++];
}
}
sequences.emplace_back(tmpSeq);
}
}
}

return sequences;
}

void selectKFromN(int st, int k, vector<vector<int>>& res, vector<int>& nums, vector<int>& tmpRes) {
if(k == 0) {
res.emplace_back(tmpRes);
return;
}
for(int i = st; i < nums.size() - k + 1; ++i) {
tmpRes.emplace_back(nums[i]);
selectKFromN(i + 1, k - 1, res, nums, tmpRes);
tmpRes.pop_back();
}
}
}

1 并查集

关键理解: 并:是通过一条边将两个没有公共子集的集合合并,查:每个子集的所有子项对应的root是相同的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class DSU{
public:
vector<int> parent;
vector<int> subTreeSize;

DSU(int n) {
parent.resize(n);
subTreeSize.resize(n);
for(int i = 0; i < n; ++i) {
parent[i] = i;
subTreeSize[i] = 1;
}
}

int find(int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

bool unionMerge(int x, int y) {
int findX = find(x);
int findY = find(y);
if(findX != findY) {
parent[findX] = findY;
subTreeSize[findY] += subTreeSize[findX];
return true;
}
return false;
}

int maxComponentSize() {
return *max(subTreeSize.begin(), subTreeSize.end());
}
};

0952 最大因数联通分量大小

1 题目

https://leetcode-cn.com/problems/largest-component-size-by-common-factor

2 解题思路

个人体悟: 当需要判断两个节点是否位于同一个连通子图时,首选并查集

  • 1 普通思路:
    • 1.1 很简单,暴力的去检测两两节点之间的连接性,然后构建并查集,求解最大的分量值即可;
  • 2 优化思路:
    • 1 中需要o(n^2)的复杂度去计算结点之间的链接性,我们不去计算节点的连接性,改为计算他们质数因子的连接性
    • 2 对于每个数字提取出质因子列表,然后因为这个数的存在,可以将这些质因子联系起来,将所有数字的质因子计作L
    • 3 而后我们统计每个数字,他对应的属于哪个质因子的联通分量,然后对该联通分量的root计数加1即可,最后找出所有的质因子联通分量最大的计数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
class Solution {
public:
class DSU{
public:
vector<int> parent;
vector<int> subTreeSize;

DSU(int n) {
parent.resize(n);
subTreeSize.resize(n);
for(int i = 0; i < n; ++i) {
parent[i] = i;
subTreeSize[i] = 1;
}
}

int find(int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

bool unionMerge(int x, int y) {
int findX = find(x);
int findY = find(y);
if(findX != findY) {
parent[findX] = findY;
subTreeSize[findY] += subTreeSize[findX];
return true;
}
return false;
}

int maxComponentSize() {
return *max(subTreeSize.begin(), subTreeSize.end());
}
};

int getGreatestCommonDivisor(int x, int y) {
int res = 0;
int mod = 0;
do {
mod = x % y;
x = y;
y = mod;

} while(mod != 0);
// cout << y << endl;
return x;
}

int largestComponentSize(vector<int>& nums) {
int n = nums.size();
int maxComponentSize = INT_MIN;

// DSU* dsu = new DSU(n);
// travel all pairs and construct the dsu, o(n ** 2), too slow
// for(int i = 0; i < n; ++i) {
// for(int j = i; j < n; ++j) {
// if(getGreatestCommonDivisor(nums[i], nums[j]) != 1) {
// dsu->unionMerge(i, j);
// }
// }
// }
//
// return *max_element(dsu->subTreeSize.begin(), dsu->subTreeSize.end());

// we shall understand the fact that:
// union: union by edeg, but edge denote two set

// find a number's prime factors:
map<int, vector<int>> numberToPrimes;
for(auto num : nums) {
vector<int> primes;
int x = num;

int d = 2;
while(d * d <= num) {
if(num % d == 0) {
// cull out all d
while(num % d == 0) {
num = num / d;
}
primes.emplace_back(d);
}
++d;
}
if(num > 1 || primes.empty()) {
primes.emplace_back(num);
}
numberToPrimes[x] = primes;
}

// form all the factors and numbers into nodes
unordered_set<int> factors;
for(auto& p : numberToPrimes) {
for(auto& fac : p.second) {
factors.insert(fac);
}
}

unordered_map<int, int> facToNode;
int i = 0;
for(auto fac : factors) {
facToNode[fac] = i++;
}

DSU* dsu = new DSU(factors.size());
// union those numbers by factors
for(auto p : numberToPrimes) {
vector<int> primes = p.second;
// union a number's all factors, we need union action: primes.size() times
for(auto prime : primes) {
// cout << p.first << "->" << prime << endl;
dsu->unionMerge(facToNode[primes[0]], facToNode[prime]);
}

}

// for each number, find the union root of this number
// all numbers who are connected will share the same root
vector<int> cnt(factors.size());
for(auto p : numberToPrimes) {
cnt[dsu->find(facToNode[p.second[0]])]++;
}

return *max_element(cnt.begin(), cnt.end());
// return *max_element(dsu->subTreeSize.begin(), dsu->subTreeSize.end());
// return dsu->maxComponentSize();
}
};

0928 minMalwareSpread 最少病毒传播

1 题目

https://leetcode-cn.com/problems/minimize-malware-spread-ii/

2 解题思路

个人体悟: 当需要判断两个节点是否位于同一个连通子图时,首选并查集

  • 1 普通思路1
    • 1.1 使用dfs,对于每个initial,则计算仅仅由他能传播到的节点有多少
  • 2 使用并查集:
    • 明确目标:对于每个initial,则计算仅仅由他能传播到的节点有多少
    • 那么就首先构造不含initial的一个图G
    • 遍历initial中的每个顶点,那么G中每个root都可以知道会被哪些initial所影响
    • 于是每个initial的贡献为仅仅被自己所连接的root(也就是仅由自己才能传播过去)(换句话说,若G中的一个连通子图,会被好几个initial传播,那么只删除一个initial是没办法改变这个联通子图会被传播的下场)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Solution {
public:
int find(vector<int>& parent, int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

bool unionMerge(vector<int>& parent, vector<int>& subTreeSize, int x, int y) {
int findX = find(parent, x);
int findY = find(parent, y);
if(findX != findY) {
parent[findX] = findY;
subTreeSize[findY] += subTreeSize[findX];
return true;
}
return false;
}


int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
// 对于每个initial计数的方式发生了改变,考虑一个不含有inital 的图,initial的得分应该是单独被他影响的子集
int n = graph.size();
vector<int> parent(n);
for(int i = 0; i < n; ++i) {
parent[i] = i;
}

vector<bool> isInitial(n, false);
for(auto& i : initial) {
isInitial[i] = true;
}

vector<int> subTreeSize(n, 1);
// 构造union find set
for(int i = 0; i < n; ++i) {
if(isInitial[i]) {
continue;
}
for(int j = 0; j < n; ++j) {
if(1 == graph[i][j] && !isInitial[j]) {
unionMerge(parent, subTreeSize, i, j);
}
}
}

// for(int i = 0; i < n; ++i) {
// cout << "root " << i << " -> size " << subTreeSize[i] << endl;
// }

// find componets infected by a initial
unordered_map<int, unordered_set<int>> initialToComponents;
unordered_map<int, int> rootToInitial;
for(auto& i : initial) {
unordered_set<int> components;
for(int v = 0; v < n; ++v) {
if(!isInitial[v]) {
if(graph[i][v] == 1) {
int root = find(parent, v);
components.insert(root);
// cout << " ||| " << i << " >> " << root << endl;
// no occupied by single initial
if(rootToInitial.find(root) != rootToInitial.end() && \
rootToInitial[root] != i) {
rootToInitial[root] = -1;
continue;
}
rootToInitial[root] = i;
}
}
}
initialToComponents[i] = components;
}


// cal scores for each initial
int resInit = INT_MAX;
int maxScore = INT_MIN;
for(auto& p : initialToComponents) {
int curInit = p.first;
unordered_set<int> components = p.second;
int score = 0;
for(auto& root : components) {
// std::cout << curInit << " -> " << score << " with com: " << root << endl;
if(rootToInitial[root] != -1) {
score += subTreeSize[root];
// cout << "added!" << endl;
}
}
if(score > maxScore || (score == maxScore && curInit < resInit)) {
maxScore = score;
resInit = curInit;
}
}

return resInit;
}
};

0924 minMalwareSpread 最少病毒传播

1 题目

https://leetcode-cn.com/problems/minimize-malware-spread/

2 解题思路

个人体悟: 当需要判断两个节点是否位于同一个连通子图时,首选并查集

  • 1 普通思路1
    • 1.1 考虑每个候选移除顶点,bfs看它能传播多少,如果传播的过程中遇到任何其他候选点,这说明减少该候选点和其位于同一个子图的候选点都是无法减少病毒传播的
    • 1.2 之后我们得到那些候选移除顶点,他们各自的连通子图中就没有其他候选点,我们看连通子图大小,找出子图最大的那个候选点,作为结果输出。
    • 1.3 若没有1.2中的候选点,则根本无法减少传播,于是直接输出所有候选点中的最小值即可。
  • 2 使用并查集或者bfs来上色

    同 方法一 一样,也得找出图中所有的连通分量,不同的是这一步用并查集来做。

    在并查集中会额外计算连通分量的大小,当合并两个连通分量的时候,会把它们的大小进行累加。

    借助并查集,可以用 方法一 中一样的思路处理:对于 initial 中每个颜色唯一的节点,都去计算连通分量的大小,从中找到最优解。如果 initial 中没有颜色唯一的节点,直接返回 min(initial)。

    简洁起见,实现的并查集没有根据 rank 合并,这会让渐进复杂度变大一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
public:
int find(vector<int>& parent, int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

bool unionMerge(vector<int>& parent, vector<int>& subTreeSize, int x, int y) {
int findX = find(parent, x);
int findY = find(parent, y);

if(findX != findY) {
parent[findX] = findY;
subTreeSize[findY] += subTreeSize[findX];
return true;
}
return false;
}

int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<int> parent(n);
vector<int> subTreeSize(n);

for(int i = 0; i < n; ++i) {
parent[i] = i;
subTreeSize[i] = 1;
}

map<int, int> connectSizeToInitial;
// cal each connected component's size, attach initial with a component's "color"
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(graph[i][j] == 1) {
unionMerge(parent, subTreeSize, i, j);
}
}
}

map<int, int> rootToInit;

// if two initial number in same connected component, then remove one of them
// will cause the same malware spread result
// each color pick a smallest idx as res candidate in initial, finally pick the max connect size
// find max connected size
int maxConnectSize = INT_MIN;
for(auto& i : initial) {
int curRoot = find(parent, i);
// cout << i << " ->> " << curRoot << endl;
if(rootToInit.find(curRoot) != rootToInit.end()) {
rootToInit[curRoot] = -1;
continue;
}
rootToInit[curRoot] = i;
}

bool hasLonelyInitial = false;
for(auto& i : initial) {
// those initial who do not share root
if(rootToInit[find(parent, i)] != -1) {
// cout << "valid!" << endl;
hasLonelyInitial = true;
int curSubSize = subTreeSize[find(parent, i)];
if(connectSizeToInitial.find(curSubSize) != connectSizeToInitial.end()) {
connectSizeToInitial[curSubSize] = min(connectSizeToInitial[curSubSize], i);
continue;
}
connectSizeToInitial[curSubSize] = i;
maxConnectSize = max(maxConnectSize, curSubSize);
// cout << maxConnectSize << endl;
}
}


// for(auto& p : connectSizeToInitial) {
// cout << p.first << " -<<> " << p.second << endl;
// }

// for(auto& p : rootToInit) {
// cout << p.first << " -> " << p.second << endl;
// }

if(hasLonelyInitial) {
return connectSizeToInitial[maxConnectSize];
}
return *min_element(initial.begin(), initial.end());
}
}

0778 泳池游泳上升泳池

1 题目

https://leetcode-cn.com/problems/swim-in-rising-water/

2 解题思路

  • 1 普通思路1
    • 对于每一个水位,采用bfs算法看是否能够到达,那么对于水位可以用二分法加速o(logn),bfs要o(n^2),所以o(n^2logn)
  • 2 普通思路2
    • 仔细理解改题目,问的是a和b什么时候能够连通的问题?那么自然就想到并查集,反复说一句哈:并查集并的子树,查的是子树的root
    • 对于水位从低到高遍历,每次更新和当前水位相同高度的格子(注意,题目说的非常清除,所有的格子的值在0到n^2,且不同)和周围联通情况
    • 每次更新完连通情况我们看一下是否能够使得左上角和右下角的两个节点相互连通即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
int find(vector<int>& parent, int x) {
while(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}

return x;
}

bool unionMerge(vector<int>& parent, int x, int y) {
int findX = find(parent, x);
int findY = find(parent, y);
if(findX != findY) {
parent[findX] = findY
return true;
}
return false;
}

int swimInWater(vector<vector<int>>& grid) {
// for each threshold, maintain a unionFind
// everytime increase thres, we modify the connection of unionFind
int n = grid.size();

if(n == 1) {
return 0;
}

vector<int> parent(n * n);
for(int i = 0; i < n * n; ++i) {
parent[i] = i;
}

// Each value grid[i][j] is unique.
vector<vector<int>> elevationToIdx(n * n, vector<int>(n));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
elevationToIdx[grid[i][j]][0] = i;
elevationToIdx[grid[i][j]][1] = j;
}
}

vector<vector<int>> moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for(int thres = 0; thres < n * n; ++thres) {
// when the rain rise, process the exact the same height grid
int tarX = elevationToIdx[thres][0];
int tarY = elevationToIdx[thres][1];
for(auto deltaXY : moves) {
int newX = tarX + deltaXY[0];
int newY = tarY + deltaXY[1];
if(newX >= 0 && newY >= 0 && newX < n && newY < n && grid[newX][newY] <= thres) {
// cout << newX << " " << newY << " ->" << thres <<endl;
unionMerge(parent, grid[newX][newY], grid[tarX][tarY]);
if(find(parent, grid[0][0]) == find(parent, grid[n - 1][n - 1])) {
return thres;
}
}
}
}
return n*n;
}
}

1 dijstra算法

wiki:
Dijkstra 算法
对于没有任何优化的戴克斯特拉算法,实际上等价于每次遍历了整个图的所有结点来找到Q(为图的点集)中满足条件的元素(即寻找最小的頂點是${\displaystyle O(|V|)}$的,此外实际上还需要遍历所有的边一遍,因此算法的复杂度是${\displaystyle O(|V|^{2}+|E|)}$
一个基于堆优化的实现:https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h> 
using namespace std;
# define INF 0x3f3f3f3f

// iPair ==> Integer Pair(整数对)
typedef pair<int, int> iPair;

// 加边
void addEdge(vector <pair<int, int> > adj[], int u,
int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}


// 计算最短路
void shortestPath(vector<pair<int,int> > adj[], int V, int src)
{
// 关于stl中的优先队列如何实现,参考下方网址:
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

// 距离置为正无穷大
vector<int> dist(V, INF);
vector<bool> visited(V, false);

// 插入源点,距离为0
pq.push(make_pair(0, src));
dist[src] = 0;

/* 循环直到优先队列为空 */
while (!pq.empty())
{
// 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
// 遍历所有边
for (auto x : adj[u])
{
// 得到顶点边号以及边权
int v = x.first;
int weight = x.second;

//可以松弛
if (dist[v] > dist[u] + weight)
{
// 松弛
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}

// 打印最短路
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
int main()
{
int V = 9;
vector<iPair > adj[V];
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);

shortestPath(adj, V, 0);

return 0;
}

2 Floyd算法

空间o(n^2),时间o(n^3):
wiki

1
2
3
4
5
6
7
8
9
10
11
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u,v)
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if