在本文中，我们将为您详细介绍101.SymmetricTree的相关知识，此外，我们还会提供一些关于1040LongestSymmetricString、19.3.2[LeetCode100]Symm
在本文中，我们将为您详细介绍101. Symmetric Tree的相关知识，此外，我们还会提供一些关于1040 Longest Symmetric String、19.3.2 [LeetCode 100] Symmetric Tree、2018 牛客多校第一场 B.Symmetric Matrix、codeforces1028F: Make Symmetrical的有用信息。
本文目录一览：- 101. Symmetric Tree
- 1040 Longest Symmetric String
- 19.3.2 [LeetCode 100] Symmetric Tree
- 2018 牛客多校第一场 B.Symmetric Matrix
- codeforces1028F: Make Symmetrical
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
public boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
return isSymmetric(root.left,root.right);
}
public boolean isSymmetric(TreeNode t1, TreeNode t2) {
if(t1==null&&t2==null)
return true;
if((t1==null&&t2!=null)||(t1!=null&&t2==null))
return false;
return t1.val==t2.val&&isSymmetric(t1.left,t2.right)&&isSymmetric(t2.left,t1.right);
}
1040 Longest Symmetric String
输入时用gets 读入空格，另外注意只有1个字符的特殊情况
#include <stdio.h>
#include <string.h>
char s[1000+5];
int main(){
freopen("in.txt","r",stdin);
gets(s);
int n = strlen(s);
int maxLen = 1;//maxLen=0就会有1个case 错误！因为对于长度为1 的输入，输出就应该为1
for(int j = 0; j < n-1; j++){//偶数
int left = j, right = j+1;
int len = 0;
while(left>=0 && right<n && s[left]==s[right]){
len+=2;
left--;
right++;
}
if(len > maxLen){
maxLen = len;
}
}
for(int j = 1; j < n-1; j++){//奇数
int left = j-1, right = j+1;
int len = 1;
while(left>=0 && right<n && s[left]==s[right]){
len+=2;
left--;
right++;
}
if(len > maxLen){
maxLen = len;
}
}
printf("%d",maxLen);
return 0;
}![19.3.2 [LeetCode 100] Symmetric Tree](http://www.gvkun.com/zb_users/upload/2025/02/e06e11c0-f23d-44cf-b05b-9bab7d702c191739666421687.jpg "19.3.2 [LeetCode 100] Symmetric Tree")
19.3.2 [LeetCode 100] Symmetric Tree
Given a binary tree,check whether it is a mirror of itself (ie,symmetric around its center).
For example,this binary tree [1,2,3,4,3] is symmetric:
1
/ 2 2
/ \ / 3 4 4 3
But the following [1,null,3] is not:
1
/ 2 2
\ 3 3
Note:
Bonus points if you Could solve it both recursively and iteratively.
1 class Solution { 2 public: 3 bool thesame(TreeNode*l,TreeNode*r){ 4 if(l==NULL&&r==NULL)return true; 5 else if(l==NULL||r==NULL)return false; 6 bool same=true; 7 same&=(l->val==r->val); 8 if(!same)return false; 9 same&=thesame(l->left,r->right); 10 if(!same)return false; 11 same&=thesame(l->right,r->left); 12 return same; 13 } 14 bool isSymmetric(TreeNode* root) { 15 if(root==NULL)return true; 16 return thesame(root->left,root->right); 17 } 18 };
2018 牛客多校第一场 B.Symmetric Matrix
题意：
构造一个 n*n 的矩阵，使得 Ai,i = 0，Ai,j = Aj,i，Ai,1+Ai,2+...+Ai,n = 2。求种类数。
题解：
把构造的矩阵当成邻接矩阵考虑。
那么所有点的度数都为 2，且存在重边但不存在自环。这种情况的图为多个环，即每个点都在且仅在一个环里。
考虑每次加一个点来递推 dp []。假设当前是第 n 个点，从前 n-1 个点中筛出（1~n-3）个点和第 n 个点形成环。
设 n-1 个点中保留 k 个点，即筛出 n-1-k 个点和第 n 个点形成环。
递推方程为：f (n) = (n-1) f (n-2)+sigma (k:2->n-3) C (n-1,k) f (k)(n-1-k)!/2;
其中 (n-1) f (n-2) 为从 n-1 个点中筛出 1 个点的情况。C (n-1,k) 为从 n-1 个点中筛出 k 个点的组合数（k 表示保留的个数）。(n-1-k)! 表示筛出的 n-1-k 个数与第 n 个数一共 n-k 个数构成环的种数。
/2 是因为去掉像 1 2 3 4 和 1 4 3 2 这种对称的情况。但是当 k=1 时就不用 / 2 所以就把 k=1 的情况先写出来。
然后就是化简递推方程。
C(n-1,k)f(k)(n-1-k)!/2 = f(k)(n-1)!/k!/2
f(n) = (n-1)f(n-2)+sigma(k:2->n-3)f(k)(n-1)!/k!/2
(n-1)f(n-1) = (n-1)(n-2)f(n-3)+sigma(k:2->n-4)f(k)(n-1)!/k!/2
减一下就变成：f (n) = (n-1) f (n-1)+(n-1) f (n-2)-(n-1)(n-2) f (n-3)/2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int n, m;
int dp[N];
int main() {
while(~scanf("%d%d", &n, &m)) {
dp[1] = 0; dp[2] = 1%m; dp[3] = 1%m;
for(int i = 4; i <= n; i++) dp[i] = ((1ll*(i-1)*dp[i-1]%m+1ll*(i-1)*dp[i-2]%m-1ll*(i-1)*(i-2)/2*dp[i-3]%m)%m+m)%m;
printf("%d\n", dp[n]);
}
}
codeforces1028F: Make Symmetrical
有个结论，一个以原点为圆心的圆，那么这个圆上的整点非常少。
然后我们就可以记录每个环上面的点，加入和删除的时候，就暴力的把答案都统计出来。
O (1) 进行询问。
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define M 200010
5 #define num(x, y) 1ll * x * x + 1ll * y * y
6 map<LL, int> mp;
7 int tot;
8 vector<pair<int, int> > a[M];
9 map<pair<int, int>, int> Ans;
10 inline int Get(LL p) {
11 if(mp.find(p) == mp.end()) {
12 mp[p] = ++ tot;
13 return tot;
14 }
15 return mp[p];
16 }
17 int main() {
18 int q;
19 scanf("%d", &q);
20 int cnt = 0;
21 while(q --) {
22 int op, x, y;
23 scanf("%d%d%d", &op, &x, &y);
24 int pos = Get(num(x, y));
25 if(op == 1) {
26 for(int i = 0; i < a[pos].size(); ++ i) {
27 int X = a[pos][i].first + x, Y = a[pos][i].second + y;
28 int GCD = __gcd(X, Y);
29 X /= GCD; Y /= GCD;
30 Ans[make_pair(X, Y)] += 2;
31 }
32 a[pos].push_back(make_pair(x, y));
33 int GCD = __gcd(x, y);
34 x /= GCD; y /= GCD;
35 Ans[make_pair(x, y)] ++;
36 ++ cnt;
37 }
38 else if(op == 2) {
39 vector<pair<int, int> > :: iterator it;
40 for(it = a[pos].begin(); it != a[pos].end(); ++ it) {
41 if(*it == make_pair(x, y)) {
42 a[pos].erase(it);
43 break;
44 }
45 }
46 for(int i = 0; i < a[pos].size(); ++ i) {
47 int X = a[pos][i].first + x, Y = a[pos][i].second + y;
48 int GCD = __gcd(X, Y);
49 X /= GCD; Y /= GCD;
50 Ans[make_pair(X, Y)] -= 2;
51 }
52 int GCD = __gcd(x, y);
53 x /= GCD; y /= GCD;
54 Ans[make_pair(x, y)] --;
55 -- cnt;
56 }
57 else {
58 int GCD = __gcd(x, y);
59 x /= GCD; y /= GCD;
60 printf("%d\n", cnt - Ans[make_pair(x, y)]);
61 }
62 }
63 }
今天关于101. Symmetric Tree的讲解已经结束，谢谢您的阅读，如果想了解更多关于1040 Longest Symmetric String、19.3.2 [LeetCode 100] Symmetric Tree、2018 牛客多校第一场 B.Symmetric Matrix、codeforces1028F: Make Symmetrical的相关知识，请在本站搜索。
本文标签：
