Joyce' Blog
0%

发表于 更新于

题目描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

提示：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

题解

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
if (!root)return root;
	//类似于层次遍历
	queue<Node*> q;
	Node* t = root;
	q.push(t);
	while (!q.empty())
	{
		t = q.front();
		q.pop();
		if (t->left&&t->right) {
			q.push(t->left);
			q.push(t->right);
		}
		if (!q.empty())
			t->next = q.front();
		else
			t->next = NULL;
	}
	t = root;
	while (t->right)
	{
		t->next = NULL;
		t = t->right;
	}
	return 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
Node* connect(Node* root) {
	if (!root)return root;
	//类似于层次遍历
	queue<Node*> q;
	Node* t = root;
	q.push(t);
	int level = 1;
	while (!q.empty())
	{
		t = q.front();
		q.pop();
		if (t->left&&t->right) {
			q.push(t->left);
			q.push(t->right);
		}
		if (q.empty()||q.size() == pow(2, level))
		{
			t->next = NULL;
			level++;
		}
		else
			t->next = q.front();
	}
	return root;
}

发表于

r.argsort() argsort()函数是将x中的元素从小到大排列，提取其对应的index(索引号)

[::-1] 顺序相反操作

[:100] 代表列表中的第1项到第100项

Python 借助第三方软件生成exe可执行文件，并集成相关依赖包

1
pip install PyInstaller

打开cmd进入到python项目所在文件夹，进行打包：

1
pyinstaller -F XXX.py

打包后会出现一个 dist 文件夹，里面的exe文件可以直接点击运行，其余的文件都可以按需删除.

如果exe文件打开一闪而过：打开cmd进入到exe所在文件夹，输入xxx.exe运行，查看报错并修改。

发表于 更新于

题目描述

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int numDistinct(string s, string t) {
	//列为s，行为t，dp[i][j]=dp[i][j-1]+(s[j]==t[i]?dp[i-1][j-1]:0)
	int ls = s.length();
	int lt = t.length();
	long **dp = new long*[lt + 1];
	for (int i = 0; i <= lt; i++)
		dp[i] = new long[ls + 1];
	for (int i = 0; i <= ls; i++)
		dp[0][i] = 1;
	for (int i = 1; i <= lt; i++)
		dp[i][0] = 0;
	for (int i = 1; i <= lt; i++)
		for (int j = 1; j <= ls; j++)
			dp[i][j] = dp[i][j - 1] + (s[j - 1] == t[i - 1] ? dp[i - 1][j - 1] : 0);
	return int(dp[lt][ls]);
}

注意可能会出现超过INT_MAX大小的中间结果。

难道要算出所有的子序列，然后在里面计数求和吗？

是不是傻，字符串，动态规划问题啊。

理解有误。没用的子函数放在下面的吧。晚安。

求全部子序列：

1
2
3
4
5
6
7
8
void getsubstring(string s, string base, set<string>& vec, int index)
{
	if (index == s.length())return;
	vec.insert(base);
	getsubstring(s, base, vec, index + 1);
	vec.insert(base + s[index]);
	getsubstring(s, base + s[index], vec, index + 1);
}

计数淄川出现的次数：

1
2
3
4
5
6
7
8
9
10
11
12
std::string str("abcabdabcdsdabcds");

auto occurrences = [&str](const std::string &dest) {
    size_t pos, pre = 0, count = 0;
    while ( (pos = str.find(dest, pre)) != std::string::npos ) {
        ++count;
        pre = pos + 1;
    }
    return count;
};

std::cout << occurrences("abc") << std::endl;

是真的菜。

发表于

decltype作为操作符，用于获取表达式的数据类型。C++11标准引入decltype，主要是为泛型编程而设计。

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
#include <iostream>
 
struct A { double x; };
const A* a;
 
decltype(a->x) y;       // y 的类型是 double（其声明类型）
decltype((a->x)) z = y; // z 的类型是 const double&（左值表达式）
 
template<typename T, typename U>
auto add(T t, U u) -> decltype(t + u) // 返回类型依赖于模板形参
{                                     // C++14 开始可以推导返回类型
    return t+u;
}
 
int main() 
{
    int i = 33;
    decltype(i) j = i * 2;
 
    std::cout << "i = " << i << ", "
              << "j = " << j << '\n';
 
    auto f = [](int a, int b) -> int
    {
        return a * b;
    };
 
    decltype(f) g = f; // lambda 的类型是独有且无名的
    i = f(2, 2);
    j = g(3, 3);
 
    std::cout << "i = " << i << ", "
              << "j = " << j << '\n';
}

发表于 更新于

题目描述

给定一个二叉树，原地将它展开为链表。

题解

永远都是两类：自顶向下和自底向上。

注意后面要把左子树赋值为NULL，不然递归还会进到左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void flatten(TreeNode* root) {
	if (!root)return;
	if (!root->left) {
		flatten(root->right);
		return;
	}
	flatten(root->left);
	flatten(root->right);
	TreeNode* t1 = root->left;
	while (t1->right)t1 = t1->right;
	t1->right = root->right;
	root->right = root->left;
	root->left = NULL;
}

发表于

题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isPath(TreeNode* root, int sum, vector<int>& tmp, vector<vector<int>>& res) {
	if (!root) {
		return false;
	}
	if (!root->left && !root->right&&root->val == sum) {
		tmp.push_back(root->val);
		res.push_back(tmp);
		tmp.pop_back();
		return true;
	}
	tmp.push_back(root->val);
	bool f1 = isPath(root->left, sum - root->val, tmp, res);
	bool f2 = isPath(root->right, sum - root->val, tmp, res);
	tmp.pop_back();
	return f1 || f2;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
	vector<vector<int>> res;
	vector<int> tmp;
	isPath(root, sum, tmp, res);
	return res;
}

效率还不错。注意什么时候压入，什么时候需要弹出。

发表于

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

题解

注意只有一棵子树的情况。

1
2
3
4
5
6
7
int minDepth(TreeNode* root) {
	if (!root)return 0;
	if (!root->right && !root->left)return 1;
	if (!root->left)return 1 + minDepth(root->right);
	if(!root->right)return 1 + minDepth(root->left);
	return 1 + min(minDepth(root->left), minDepth(root->right));
}

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

题解

1
2
3
4
5
bool hasPathSum(TreeNode* root, int sum) {
	if (!root)return false;
	if (!root->left && !root->right&&root->val == sum)return true;
	return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

发表于

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

题解

两种思路：自底向上和自顶向下。自底向上计算，每个子树的高度只会计算一次。可以递归先计算当前节点的子节点高度，然后再通过子节点高度判断当前节点是否平衡，从而消除冗余。首先判断子树是否平衡，然后比较子树高度判断父节点是否平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool f1(TreeNode* root, int& height){
	if (!root) {
		height = 0;
		return true;
	}
	int left, right;
	if (f1(root->left, left) && f1(root->right, right) && abs(left - right) < 2)
	{
		height = max(left, right) + 1;
		return true;
	}
	return false;
}
bool isBalanced(TreeNode* root) {
	if (!root)return true;
	int h;
	return f1(root, h);
}

通过函数参数取出计算的结果。

发表于 更新于

题目描述

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

题解

链表，相比于上一题的数组，有什么区别呢？不好找节点了啊……

用两个指针，一块一慢，快的每次走两步，慢的每次走一步，这样当快指针遍历结束时，慢指针指向的也就是链表的中间位置。这时候把中间位置的结点的值作为二叉搜索树当前结点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* ListToBST(ListNode* head, ListNode* tail){
	if (head==tail)return NULL;
	if (head->next==tail)return new TreeNode(head->val);
	ListNode *p, *q;
	p = head; q = head;
	while (q != tail) {
		if (q->next == tail)break;
		p = p->next;
		q = q->next->next;
	}
	TreeNode* root = new TreeNode(p->val);
	root->left = ListToBST(head, p);
	root->right = ListToBST(p->next, tail);
	return root;
}
TreeNode* sortedListToBST(ListNode* head) {
	if (!head)return NULL;
	if (!head->next)return new TreeNode(head->val);
	return ListToBST(head, NULL);
}

要学会用双指针。改的好看点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* ListToBST(ListNode* head, ListNode* tail)
{
	if (head==tail)return NULL;
	ListNode *p, *q;
	p = head; q = head;
	while (q!=tail&&q->next!=tail){
		p = p->next;
		q = q->next->next;
	}
	TreeNode* root = new TreeNode(p->val);
	root->left = ListToBST(head, p);
	root->right = ListToBST(p->next, tail);
	return root;
}
TreeNode* sortedListToBST(ListNode* head) {
	return ListToBST(head, NULL); 
}

不过上面的代码效率也太低了，去学个好的来。空间换时间？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* sortedListToBST(ListNode* head) {
    vector<int> v;
    while(head != nullptr){
        v.push_back(head->val);
        head = head->next;
    }
    return buildTree(v, 0, v.size());
}
TreeNode * buildTree(vector<int> & v, int begin, int end){
    if(begin == end) return nullptr;
    int middle = (begin+end)/2;
    TreeNode * root = new TreeNode(v[middle]);
    root->left = buildTree(v, begin, middle);
    root->right = buildTree(v, middle+1, end);
    return root;
}

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/c-2chong-jie-fa-bu-yong-duan-kai-lian-biao-by-alex/

还是慢。那就不是我的问题了。

偷懒了好几天实在抱歉，从今天开始继续吧。

发表于

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

题解

转化的结果是不唯一的。不过代码写好了转换出来就是唯一的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode* ArrayToBST(vector<int>& nums,int left,int right) {
	if (left == right)return NULL;
	if (left == right - 1)return new TreeNode(nums[left]);
	int mid = (left + right) / 2;
	TreeNode* root= new TreeNode(nums[mid]);
	root->left = ArrayToBST(nums, left, mid);
	root->right = ArrayToBST(nums, mid+1, right);
	return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
	int vsize = nums.size();
	if (!vsize)return NULL;
	if(vsize==1)return new TreeNode(nums[0]);
	return ArrayToBST(nums, 0, vsize);
}

最近写的效率都太低了。大概是因为我只会用递归来解决树的问题。

还有static inline这种要学着用啊。会的东西还是太少了。