头像

王小强

中国-上海




离线:13分钟前



王小强
16分钟前

任何精妙的解法都离不开百次千次乃至万次的思考与练习!

#include <iostream>

using namespace std;
int n;

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n >> 1; ++i) {
    for (int j = 0; j < (n >> 1) - i; ++j) putchar(' ');
    for (int j = 0; j < (i << 1 | 1); ++j) putchar('*');
    for (int j = 0; j < (n >> 1) - i; ++j) putchar(' ');
    printf("\n");
  }
  for (int i = 0; i < n; ++i) printf("*");
  printf("\n");
  for (int i = 0; i < n >> 1; ++i) {
    for (int j = 0; j < i + 1; ++j)            putchar(' ');
    for (int j = 0; j < n - 2 - (i << 1); ++j) putchar('*');
    for (int j = 0; j < i + 1; ++j)            putchar(' ');
    printf("\n");
  }

  return 0;
}



王小强
1小时前

没有什么算法思想。。。计算的底功还是有的,算不出硬算!!

参照的数学解法 – 可以点击

#include <iostream>

using namespace std;
int n, i, j;

int main(void) {
  scanf("%d %d %d", &n, &i, &j);

  int left = j, right = n - j + 1, top = i, bottom = n - i + 1;
  int l = min(left, min(right, min(top, bottom)));

  int ans = 1, r = l, c = l;
  for (int i = 1; i < l; ++i) {
    ans += 4 * (n - 1); // 第l层左上角的第一个数为ans
    n -= 2; // 第l层的子矩阵大小减少2
  }

  // 接下来分四种情况讨论
  if (i == r) // 子矩阵第一行
    ans += j - c;
  else if (j == c + n - 1) // 子矩阵最后一列
    ans += n - 1 + i - r;
  else if (i == r + n - 1) // 子矩阵最后一行
    ans += 2 * (n - 1) + (n - 1 - (j - c));
  else if (j == c) // 子矩阵第一列
    ans += 3 * (n - 1) + (n - 1 - (i - r));

  printf("%d\n", ans);
}



王小强
5小时前

Binary Tree Traversal

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
int n;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

bool flag;

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
  unordered_map<int, int> indices;
  for (int i = 0; i < post.size(); ++i)
    indices[post[i]] = i;

  function<TreeNode*(int, int, int)> construct = [&](int i, int j, int n) {
    // base case
    if (n <= 0) return (TreeNode*) nullptr;
    auto root = new TreeNode(pre[i]);
    if (n == 1) return root;
    if (n == 2) flag = false;

    int k = indices[pre[i + 1]];
    int l = k - j + 1;

    root->left = construct(i + 1, j, l);
    root->right = construct(i + 1 + l, j + l, n - 1 - l);

    return root;
  };

  return construct(0, 0, pre.size());
}

void inOrder(TreeNode* root, vector<int>& ans) {
  if (!root) return;
  inOrder(root->left, ans);
  ans.emplace_back(root->val);
  inOrder(root->right, ans);
}

void printAnswer(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) printf(" ");
  }
  printf("\n");
} 

int main(void) {
  // initialize global variable
  flag = true; // 给定一组前序遍历和后序遍历能否唯一确定一颗树 (default: TRUE)

  cin >> n;
  vector<int> pre(n), post(n);
  for (int i = 0; i < n; ++i) cin >> pre[i];
  for (int i = 0; i < n; ++i) cin >> post[i];
  auto root = constructFromPrePost(pre, post);
  puts(flag ? "Yes" : "No");

  vector<int> ans;
  inOrder(root, ans);
  printAnswer(ans);
}



王小强
7小时前

代码练习

#include <iostream>

using namespace std;
int n, x;

bool isPrime(const int x) {
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}

int main(void) {
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &x);
    if (isPrime(x)) printf("%d is prime\n", x);
    else printf("%d is not prime\n", x);
  }
  return 0;
}



王小强
7小时前

各种二叉堆的操作。。。(应该还有一种堆叫“斐波那契堆”)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int m, n;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

TreeNode* buildTree(vector<int>& vals) {
  // corner case
  if (vals.empty()) return nullptr;

  auto root = new TreeNode(vals.front());
  queue<pair<TreeNode*, int>> q;
  q.emplace(root, 0);

  while (not q.empty()) {
    const auto [cur, idx] = q.front(); q.pop();

    const int l_idx = idx << 1 | 1;
    if (l_idx >= n) break;
    cur->left = new TreeNode(vals[l_idx]);
    q.emplace(cur->left, l_idx);

    const int r_idx = (idx << 1) + 2;
    if (r_idx >= n) break;
    cur->right = new TreeNode(vals[r_idx]);
    q.emplace(cur->right, r_idx);
  }

  return root;
}

vector<vector<int>> allPathsToLeafNode(TreeNode* root) {
  vector<vector<int>> ans;
  vector<int> cur;
  function<void(TreeNode*)> dfs = [&](TreeNode* r) {
    if (!r) return;
    cur.emplace_back(r->val);
    if (r->left == r->right) { // leaf node
      ans.emplace_back(cur);
      return;
    }
    for (const  auto& child : {r->left, r->right}) {
      if (!child) continue;
      dfs(child);
      cur.pop_back(); // backtracking ...
    }
  };
  dfs(root);
  return ans;
}

bool is_maximum_heap(vector<vector<int>>& allPaths) {
  for (const auto& p : allPaths)
    if (!is_sorted(rbegin(p), rend(p))) return  false;
  return true;
}

bool is_minimum_heap(vector<vector<int>>& allPaths) {
  for (const auto& p : allPaths)
    if (!is_sorted(begin(p), end(p))) return  false;
  return true;
}

void postOrder(TreeNode* root, vector<int>& ans) {
  if (!root) return;
  postOrder(root->left,  ans);
  postOrder(root->right, ans);
  ans.emplace_back(root->val);
}

void printAns(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) printf(" ");
  }
  printf("\n");
}

int main(void) {
  scanf("%d %d", &m, &n);
  while (m--) {
    vector<int> vals(n);
    for (int i = 0; i < n; ++i) cin >> vals[i];

    auto root = buildTree(vals);
    auto allPaths = allPathsToLeafNode(root);

    if (is_maximum_heap(allPaths)) puts("Max Heap");
    else if (is_minimum_heap(allPaths)) puts("Min Heap");
    else puts("Not Heap");

    vector<int> ans;
    postOrder(root, ans);
    printAns(ans);
  }
}



王小强
17小时前

代码

#include <iostream>
#include <algorithm>

using namespace std;
int n, d;

bool isPrime(int x) {
  if (x == 1) return false;
  for (int i = 2 ; i * i <= x; ++i)
    if (!(x % i)) return false;
  return true;
}

string convert(int n, int d) {
  string ans;
  while (n) {
    ans = to_string(n % d) + ans;
    n /= d;
  }
  return ans;
}

int main(void) {
  while (cin >> n >> d, n > 0) {
    string s = convert(n, d);
    reverse(begin(s), end(s));
    if (isPrime(n) && isPrime(stoi(s, 0, d))) puts("Yes");
    else puts("No");
  }
}



王小强
19小时前

堆的基本功

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int n;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  ~TreeNode() {};
};

TreeNode* buildTree(vector<int>& vals) {
  // corner case
  if (vals.empty()) return nullptr;

  auto root = new TreeNode(vals.front());
  queue<pair<TreeNode*, int>> q;
  q.emplace(root, 0);

  while (not q.empty()) {
    const auto [cur, idx] = q.front(); q.pop();
    const int l_idx = idx << 1 | 1;
    if (l_idx >= n) break;
    cur->left = new TreeNode(vals[l_idx]);
    q.emplace(cur->left, l_idx);

    const int r_idx = (idx << 1) + 2;
    if (r_idx >= n) break;
    cur->right = new TreeNode(vals[r_idx]);
    q.emplace(cur->right, r_idx);
  }

  return root;
}

vector<vector<int>> binaryTreePaths(TreeNode* root) {
  vector<vector<int>> ans;
  vector<int> cur;
  function<void(TreeNode*)> backtracking = [&](TreeNode* r) {
    if (!r) return;
    cur.emplace_back(r->val);
    if (r->left == r->right) {
      ans.emplace_back(cur);
      return;
    }
    for (const auto& child : {r->right, r->left}) {
      if (!child) continue;
      backtracking(child);
      cur.pop_back();
    }
  };

  backtracking(root);
  return ans;
}

void printPaths(vector<vector<int>>& paths) {
  for (const auto& p : paths) {
    for (int i = 0; i < p.size(); ++i) {
      printf("%d", p[i]);
      if (i < p.size() - 1) printf(" ");
    }
    printf("\n");
  }
}

bool is_maximum_heap(vector<vector<int>>& paths) {
  for (const auto& p : paths) 
    if (!is_sorted(rbegin(p), rend(p))) return false;

  return true;
}

bool is_minimum_heap(vector<vector<int>>& paths) {
  for (const auto& p : paths) 
    if (!is_sorted(begin(p), end(p))) return false;

  return true;
}
int main(void) {
  cin >> n;
  vector<int> vals(n);
  for (int i = 0; i < n; ++i) cin >> vals[i];
  auto paths = binaryTreePaths(buildTree(vals));
  printPaths(paths);

  if (is_maximum_heap(paths)) puts("Max Heap");
  else if (is_minimum_heap(paths)) puts("Min Heap");
  else puts("Not Heap");
}



王小强
22小时前

代码

#include <iostream>

using namespace std;
int n;

int main(void) {
  scanf("%d", &n);
  for (int i = 1; i <= 1e4; ++i)
    if (i % n == 0b10) printf("%d\n", i);

  return 0;
}



王小强
22小时前

算法1:

#pragma GCC optimize(2)// 吸口氧气
#pragma GCC optimize(3)// 吸口臭氧

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int n, u, v;

void dfs(vector<vector<int>>& g, int cur, int* seen) {
  if (seen[cur]++) return;
  for (const auto& nxt : g[cur]) dfs(g, nxt, seen);
}

int maxDepth(vector<vector<int>>& g, int cur, int* seen) {
  if (seen[cur]++) return 0;
  int d = 0;
  for (const auto& nxt : g[cur])
    d = max(d, maxDepth(g, nxt, seen));
  return 1 + d;
}

int main(void) {
  cin >> n;
  // build the undirected graph
  vector<vector<int>> g(n + 1);
  int seen[n + 1];
  memset(seen, 0, sizeof seen);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  int ccs = 0; // 图中连通分量的个数
  for (int i = 1; i <= n; ++i) {
    if (seen[i]) continue;
    dfs(g, i, seen);
    ++ccs;
  }

  if (ccs != 1)
    return printf("Error: %d components\n", ccs), 0;

  vector<int> ans;
  int max_depth = 0;
  for (int i = 1; i <= n; ++i) {
    //int seen[n + 1];
    memset(seen, 0, sizeof seen);
    const int d = maxDepth(g, i, seen);
    if (d > max_depth) {
      max_depth = d;
      ans.clear();
      ans.emplace_back(i);
    } else if (d == max_depth) {
      ans.emplace_back(i);
    }
  }

  sort(begin(ans), end(ans));
  for (const auto& x : ans) printf("%d\n", x);
}

算法2

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1E4 + 10;
int n, u, v;

int p[N];

// Path Compression
int Find(int x) {
  return p[x] ^ x ? p[x] = Find(p[x]) : x;
}

// Ignore Union By Rank
bool Union(const int u, const int v) {
  const int pu = Find(u);
  const int pv = Find(v);
  if (pu == pv) return false;
  p[pu] = pv;
  return true;
}

int maxDepth(vector<vector<int>>& g, int cur, int parent) {
  int d = 0;
  for (const auto& nxt : g[cur]) {
    if (nxt == parent) continue; // 不走回头路... 勇往直前(DFS)齐头并进(BFS)
    d = max(d, maxDepth(g, nxt, cur));
  }
  return 1 + d;
}

int main(void) {
  // initialize
  iota(begin(p), end(p), 0);

  cin >> n;
  int ccs = n;
  // build the undirected graph
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    if (Union(u, v)) --ccs;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  if (ccs != 1)
    return printf("Error: %d components\n", ccs), 0;

  vector<int> ans;
  int max_depth = 0;
  for (int i = 1; i <= n; ++i) {
    const int d = maxDepth(g, i, i);
    if (d > max_depth) {
      max_depth = d;
      ans.clear();
      ans.emplace_back(i);
    } else if (d == max_depth) {
      ans.emplace_back(i);
    }
  }

  sort(begin(ans), end(ans));
  for (const auto& x : ans) printf("%d\n", x);
}



代码练习

#include <iostream>
#include <vector>

using namespace std;
int n;

int main(void) {
  scanf("%d", &n);
  if (n == 1) return puts("0"), 0;

  vector<int> nums(n);
  nums[1] = 1;
  for (int i = 2; i < n; ++i)
    nums[i] = nums[i - 1] + nums[i - 2];

  for (int i = 0; i < n; ++i)
    printf("%d ", nums[i]);

  return 0;
}