leetcode-1

algorithm

预推免了，来刷一点算法题，ctf我对不起你
其实回想学习CTF的这一年半，最快乐的时候还是学习新知识，刚接触heap的那会，还会去学angr和Z3，学逆向，学misc，到现在glibc2.35上来之后逐渐对传统heap chall不感兴趣了。也不知道后面会不会继续打CTF。但是无论如何，他给我的收获都是课堂上知识无法比拟的。
下面的算法题主要来自于leetcode。

1339. 分裂二叉树的最大乘积

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

image-20220914135619305

这道题一上来我就愣住了，对于边的删减，一般的二叉树不是对于node的操作吗，该怎么表示边呢？但是仔细想一下就会发现，其实我们只需要计算从每个node开始往后的子树节点之和就可以了，之后用总的节点和减掉上面的结果，就能得到两部分和，乘起来就是最终结果。

但是我发现，我也不会写dfs的代码了(呜呜

后面是参考的网上的代码，理解了。在dfs()中，就是递归的计算从每个节点开始的和(好像这个非常基础)把他存到数组里面，之后其实就不难了。其实计算每个节点的子树和才是这道题的关键。

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
/**
 * 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) {}
 * };
 */

#include<vector>
class Solution {
public:
    vector<long> s;
    long maxv = 0; // value for root only
    long dfs(TreeNode* root) // 计算子树和
    {
        long max = 0;
        if(root)
        {
            long left = dfs(root->left);
            long right = dfs(root->right);
            max = left+right+root->val;
            if(max > maxv)
            {
                maxv = max; //root node cnt 
            }
            s.push_back(max);
            return max;
        }
        return 0;

    }

    int maxProduct(TreeNode* root) // 计算最大乘积
    {
        dfs(root); // get s
        int i = 0;
        long long max = 0;
        long long res = 0;
        long long mod = 1e9+7;
        for(i=0;i<s.size();i++)
        {
            long res = (maxv - s[i])*s[i];
            if(res>max)
            {
                max = res;
            }
        }
        return max%mod;
    }

};

其实想想这个图挺有意思的，想起来了CFG。

image-20220914140549154

例2

对于N 个考生，给出了考生间排名高低的M个关系（即>、=、<），求根据 这些信息能否确定考生的排行榜。如果不能，判断无法确定的原因是因为信息不完全还是因为信息包含冲突。

image-20220914142318732

image-20220914142327223

(这道题第一眼我是想用z3的…)

其实这道题是一个图的基本题目，所谓的大于小于，如果我们就把他看成箭头，那么只要判断图中是否有环就能确保能够比较所有数据。有环说明数据产生冲突。如果存在孤立点那么说明数据不完整。反之数据是完整的。

因此我们可以用二维数组表示图结构。使用数组寻找环时，可以观察数组对称性，如果对称就说明有环(需要去除a=b时的环的情况)寻找是否有最长路径覆盖，即有向图中的最长路径。可以用拓扑排序来解决。回忆一下拓扑排序，如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //b[]为每个点的入度
for(i=1;i<=n;i++){
   for(j=1;j<=n;j++){
      if(b[j]==0){   //找到一个入度为0的点
        ans=j;
        vis[cnt++]=j;
        b[j]--;
        break;
       }
    }
    for(j=1;j<=n;j++)
        if(a[ans][j]) b[j]--; //与入度为0的点相连的点的入度减一
}
    printf("%d",vis[0]);
    for(i=1;i<cnt;i++) printf(" %d",vis[i]);
    printf("\n");

image-20220914170158840

还可以用另一种笨一点的方法。源码如下。

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
#include<iostream>
constexpr auto MAXNODE = 100;;
short graph[MAXNODE][MAXNODE];
short mark[MAXNODE]; // mark表示自己是否是一个节点的下属
int flag = 0;
using namespace std;


int dfs(int start, int count,int father)
{
	// 遍历,start表示开始的下标，count是目前已经有多少节点
	// 返回：最大路径长度
	int i = 0;
	int max = count;
	for (i = 0; i < MAXNODE; i++)
	{

		if (i == father)
		{
			continue;
		}
		if (graph[start][i] == 1)
		{
			// 说明这里是reachable的
			// 接下来检查是不是以前就是后继
			if (mark[i] == true)
			{
				flag = true; // flag = true说明不合法
				return count;
			}
			// 到这里，这个节点是合法的
			mark[i] = 1;
		
			// 之后dfs这个节点如果发现途中有mark=1的说明出错了
			count = dfs(i, count + 1,start);
			mark[i] = 0;
			if (max < count)
			{
				max = count;
			}
		}
	}
	return max;
}



int main()
{
	int node_cnt = 0;
	int cons_cnt = 0;
	cin >> node_cnt >> cons_cnt;
	int i = 0;
	int left = 0;
	int right = 0;
	char op;
	// 创建图
	for (i = 0; i < cons_cnt; i++)
	{
		cin >> left >> op >> right;
		if (op == '<')
		{
			graph[right][left] = 1;
		}
		else if (op == '>')
		{
			graph[left][right] = 1;
		}
		else // op is =
		{
			graph[right][left] = 1; // 等号是2
			graph[left][right] = 1;
		}
	}

	//从第一个节点开始遍历，检查是否有环，以及是否能all reach
	int count = 0;
	int tmp_count = 0;
	int max = 0;
	for (i = 0; i < MAXNODE; i++)
	{
		count = dfs(i, tmp_count,i);
		if (max < count)
		{
			max = count;
		}
	}
	if (flag)
	{
		cout << "信息包含冲突" << endl;
		return 0;
	}

	if (max == node_cnt)
	{
		cout << "能确定" << endl;
	}
	else
	{
		cout << "信息不完全" << endl;
	}

}

主要就是dfs()，原理是从每一个结点开始寻找和他相邻的节点，并且在找到和他相邻的节点之后，标记一下这个节点被寻找过(mark数组)，并且从这个结点开始递归。如果碰到两次mark说明出现环。这样全部遍历之后可以得到所有节点开始的有向图的路径。从而和所有节点个数比较，就能得到结果。

这道题目因为没有benckmark所以只是对于测试的数据通过了测试。

例3

这道题其实是之前动态规划练习里面的。leetcode第91题，解码方法。

总结

今天收获还是不小的，复习了一下树和图的基本算法和数据结构(真 忘得一干二净)，尤其是代码怎么写。明天继续刷题。

本文标题:leetcode-1

文章作者:

发布时间:2022-09-14, 13:47:17

最后更新:2022-09-14, 21:38:58

原始链接:https://nicholas-wei.github.io/2022/09/14/leetcode-1/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 1339. 分裂二叉树的最大乘积
  2. 2. 例2
  3. 3. 例3
  4. 4. 总结
|