头像

suncloud


访客:1798

离线:1天前



suncloud
4个月前

DFS比BFS实现起来更简洁。

序列化格式:

    8
   / \
  12  2
     / \
    6   4
"8 12 null null 2 6 null null 4 null null"

DFS实现 - 先序遍历:

void ser(TreeNode *p, ostringstream &oss) {
  if (!p) {
    oss << "null ";
    return;
  }

  oss << p->val << " ";
  ser(p->left, oss);
  ser(p->right, oss);
}

void des(TreeNode **p, istringstream &iss) {
  string s;
  iss >> s;
  if (s == "null")
    return;

  *p = new TreeNode(atoi(s.c_str()));
  des(&((*p)->left), iss);
  des(&((*p)->right), iss);
}

class Solution {
public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    ostringstream oss;
    ser(root, oss);
    return oss.str();
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    TreeNode *root;
    istringstream iss(data);
    des(&root, iss);
    return root;
  }
};



suncloud
4个月前

序列化格式:

    8
   / \
  12  2
     / \
    6   4
"8 12 2 null null 6 4 null null null null"

BFS实现 - 层级遍历:

class Solution {
public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    if (!root) {
      return "null";
    }

    // bfs
    ostringstream oss;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
      TreeNode* p = que.front();
      que.pop();
      if (p) {
        oss << p->val << " ";
        que.push(p->left);
        que.push(p->right);
      } else {
        oss << "null" << " ";
      }
    }
    return oss.str();
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    istringstream iss(data);

    string s;
    iss >> s;
    if (s == "null")
      return NULL;

    // init root
    TreeNode *root = new TreeNode(atoi(s.c_str()));
    queue<TreeNode*> que;
    que.push(root);

    // bfs
    while (!que.empty()) {
      TreeNode* p = que.front();
      que.pop();

      string l, r;
      iss >> l >> r;
      if (l != "null") {
        p->left = new TreeNode(atoi(l.c_str()));
        que.push(p->left);
      }
      if (r != "null") {
        p->right = new TreeNode(atoi(r.c_str()));
        que.push(p->right);
      }
    }
    return root;
  }
};




suncloud
4个月前

核心思想acc为累加和,快指针(j)在前面扩展,慢指针(i)在后面收缩。
时间复杂度:$O(2n)$,即$O(n)$。

class Solution {
  public:
    vector<vector<int> > findContinuousSequence(int sum) {
      int i = 1, j = 0, acc = 0;
      vector<vector<int>> all_ans;
      while (j < sum / 2 + 1) {
        // extend
        do {
          ++j;
          acc += j;
        } while (acc < sum);

        // shrink
        while (acc > sum && i < j) {
          acc -= i;
          ++i;
        }

        // check ans
        if (acc == sum && j > i) {
          vector<int> v;
          for (int k = i; k <= j; ++k)
            v.push_back(k);
          all_ans.push_back(v);
        }
      } // j
      return all_ans;
    }
};




suncloud
5个月前

快排中partition有2中写法,一种是普遍用的Hoare写法,另一种是更易懂的Lumoto写法,但是为什么在100000的数据上会超时呢?

题目连接:https://www.acwing.com/problem/content/description/787/

p.s.
我试了在leetcode上 是可以过的

#include <iostream>

using namespace std;


const int MAX = 1e5 + 10;
int n;
int A[MAX];

// Lumoto's partition
int partition(int l, int r) {
  // A[l] is the pivot
  // loop invariant:
  //   A[l, i] <= pivot, A[i + 1, r] > pivot
  int i = l;
  for (int j = l + 1; j <= r; ++j) {
    if (A[j] <= A[l])
      swap(A[++i], A[j]);
  }
  swap(A[i], A[l]);
  return i;
}

void sort(int l, int r) {
  if (l >= r)
    return;

  int m = partition(l, r);
  sort(l, m - 1);
  sort(m + 1, r);
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> A[i];
  }
  sort(0, n - 1);
  for (int i = 0; i < n; ++i) {
    cout << A[i] << " ";
  }
  return 0;
}




suncloud
6个月前
#include <bits/stdc++.h>

using namespace std;

const int M = 1e4 + 10;
const int N = 1e5 + 10;
char w[M], s[N];
int m, n
int f[M] = {-1, 0};     // 初始化失配表
                        // f[j]表示:s[i]跟w[j]不匹配时应该从前面第几个重新开始对比
                        // 注意:f的长度为m+1

void build_table() {
  for (int i = 1; i < n; ++i) {
    // f[i] is known, compute f[i + 1]
    int j = f[i];
    while (j && w[j] != w[i]) j = f[j];
    if (w[j] == w[i]) f[i + 1] = j + 1;
  }
}

void search() {
  int j = 0;
  for (int i = 0; i < n; ++i) {
    while (j && w[j] != s[i]) j = f[j];
    if (w[j] == s[i]) ++j;
    if (j == m) {
      cout << i - m + 1 << " ";
      j = f[j];
    }
  }
}

int main() {
  cin >> m >> w >> n >> s;
  build_table();
  search();

  return 0;
}



suncloud
7个月前

头结点直接含到node里,更简洁一丢丢~

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

const int MAX = 1e5 + 10;

int node[MAX], next[MAX] = {-1}; // 0位置为head
int idx = 1;

void show() {
  for (int i = 0; i != -1; i = next[i]) {
    if (i > 0)
        cout << node[i] << " ";
  }
  cout << endl;
}

void insert(int k, int x) {
  // add new node
  node[idx] = x;
  next[idx] = next[k];
  // point to new node
  next[k] = idx;
  ++idx;  
}

void remove(int k) {
  next[k] = next[next[k]];  
}

int main() {
  int n, k, x;

  cin >> n;
  char c;
  while (n--) {
    cin >> c;
    switch (c) {
      case 'H':
        cin >> x;
        insert(0, x);
        break;
      case 'I':
        cin >> k >> x;
        insert(k, x);
        break;
      case 'D':
        cin >> k;
        remove(k);
        break;      
    }
  }
  show();

  return 0;
}



suncloud
7个月前

时间复杂度

离散化:$O(n)$
累加:$O(n\log n)$
前缀和:$O(n)$
查询:$O(m\log n)$

#include <bits/stdc++.h>

using namespace std;
const int MAX = 1e5 + 10;
int a[MAX], b[MAX];
vector<int> xs; // 存储离散化值

// 二分查最后一个<=x的坐标
int findx(int x) {
  if (xs.size() == 0 || x < xs[0])
    return -1;
  if (x > xs[xs.size() - 1])
    return xs.size() - 1;

  // 循环不变式: [L, l] < x, [r, R] > x
  int l = -1, r = xs.size();
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (xs[m] == x)
      return m;
    if (xs[m] < x)
      l = m;
    if (xs[m] > x)
      r = m;
  }
  return l;
}

int main() {
  int n, m;
  cin >> n >> m;

  // 输入
  int x, c;
  vector<array<int, 2>> ins;
  for (int i = 0; i < n; ++i) {
    cin >> x >> c;
    xs.push_back(x);
    ins.push_back({x, c});
  }

  // 离散化
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  // 累加
  int j = 0;
  for (int i = 0; i < n; ++i) {
    x = ins[i][0];
    c = ins[i][1];
    j = findx(x) + 1;
    a[j] += c;
  }

  // 前缀和
  for (int i = 1; i <= n; ++i) {
    b[i] = b[i - 1] + a[i];
  }

  // 查询
  int l, r;
  while (m--) {
    cin >> l >> r;
    cout << b[findx(r) + 1] - b[findx(l - 1) + 1] << endl;
  }

  return 0;
}



suncloud
7个月前

时间复杂度:$O(n)$,即看j使用的次数,小于$2n$

算法:i慢指针,j快指针

#include <iostream>

using namespace std;
const int MAX = 1e5 + 10;
int a[MAX], b[MAX]; // b 记录出现过的数字

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];

  int j = 0, l = 0;
  for (int i = 0; i < n; ++i) {
    // 无重复元素的区间[i, j)
    for (; j < n && b[a[j]] == 0; ++j)
      ++b[a[j]];
    l = max(l, j - i);
    if (j == n)
      break;
    --b[a[i]];
  }

  cout << l;
  return 0;
}



suncloud
7个月前
#include <iostream>

using namespace std;
const int MAX = 1e5 + 10;
int a[MAX];

int search_last(int n, int k) {
  // loop invariant: [L, l] <= k, [r, R] > k
  int l = -1, r = n;
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] <= k)
      l = m;
    else
      r = m;
  }
  // l + 1 == r
  if (l > -1 && a[l] == k)
    return l;
  return -1;
}

int search_first(int n, int k) {
  // loop invariant: [L, l] < k, [r, R] >= k
  int l = -1, r = n;
  while (l + 1 < r) {
    int m = l + (r - l) / 2;
    if (a[m] < k)
      l = m;
    else
      r = m;
  }
  // l + 1 == r
  if (r < n && a[r] == k)
    return r;
  return -1;
}

int main() {
  int n, q, k;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i];

  while (q--) {
    cin >> k;
    cout << search_first(n, k) << ' ' << search_last(n, k) << '\n';
  }
  return 0;
}



suncloud
7个月前

时间复杂度: $O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int MAX = 1e5 + 10;
int a[MAX];

int partition(int a[], int l, int r) {
  // lomuto版分割法
  int m = l;
  int p = a[l];
  for (int i = l + 1; i <= r; ++i) {
    if (a[i] <= p && ++m != i)
      swap(a[i], a[m]);
  }
  swap(a[l], a[m]);
  return m;
}

void find_k(int a[], int l, int r, int k) {
  if (l >= r) return;
  int m = partition(a, l, r);
  // 这时 [l, m] <= p, [m+1, r] > p

  if (m > k)
    find_k(a, l, m - 1, k);
  else if (m < k)
    find_k(a, m + 1, r, k);
}

int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> a[i];
  // 第k个数的index是k-1
  find_k(a, 0, n - 1, k - 1);
  cout << a[k - 1] << endl;
  return 0;
}