Joyce' Blog
0%

发表于

安装

其实是件很简单的事，就在控制台，先pip install ipython，再pip install jupyter，然后输入jupyter notebook就可以运行了。

但是在输入jupyter notebook之后报错：

1
2
3
4
5
6
7
ImportError: No module named 'pyrsistent'

    Jupyter notebook format depends on the jsonschema package:

        https://pypi.python.org/pypi/jsonschema

    Please install it first.

找不到，那就装嘛，pip install pyrsistent、pip install jsonschema都试过了，过程中也不报错，但就是装不上，让我一度想离线安装。

在C:\Users\asus\AppData\Local\Programs\Python\Python36\Lib\site-packages下面，发现只有pyrsistent-0.16.0-py3.6.egg-info文件夹，没有pyrsistent文件夹，也就是只有版本信息。把pyrsistent-0.16.0-py3.6.egg-info文件夹删掉，重新pip install pyrsistent，问题解决了。输入jupyter notebook，在浏览器<http://localhost:8888/tree>可以看到jupyter的页面。

配置Jupyter Notebook的默认开启目录

在命令行输入jupyter notebook --generate-config，可以得到 jupyter_notebook_config.py文件的路径，打开该文件，找到#c.NotebookApp.notebook_dir = '' ，将‘#’号删除，在后面输入需要的目录，如c.NotebookApp.notebook_dir = 'F:\\Python\Supyter'。一定注意盘符后面是双’\’

只是突然想起来些事情，想避免函数调用的开销，那你用内联函数啊，为什么要用宏去定义函数，那么麻烦，是不是傻。

内联函数有些类似于宏。内联函数的代码会被直接嵌入在它被调用的地方，调用几次就嵌入几次，没有使用call指令。这样省去了函数调用时的一些额外开销，比如保存和恢复函数返回地址等，可以加快速度。

发表于

题目描述

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题解

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
vector<vector<int>> levelOrderBottom(TreeNode* root) {
	vector<vector<int>> res;
	if (!root)return res;
	queue<TreeNode*> q, empt, tp;
	q.push(root);
	while (true)
	{
		vector<int> vec;
		while (!q.empty())
		{
			TreeNode* tmp = q.front();
			q.pop();
			vec.push_back(tmp->val);
			if (tmp->left)
				tp.push(tmp->left);
			if (tmp->right)
				tp.push(tmp->right);
		}
		res.insert(res.begin(),vec);
		if (tp.empty())return res;
		q = tp;
		tp = empt;
	}
	return res;
}

效率比较低，也是可以写个递归函数算深度，然后加到不同的vector里的，但是我现在不想改了。

发表于

题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

题解

和上一题基本一样了，只不过这次从后序数组的后面开始遍历，从中序数组中先构建右子树，再构建左子树。

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
TreeNode* subTree2(int& index, int left, int right, vector<int>& inorder, vector<int>& postorder)
{
	if (left == right)return NULL;
	if (right - left == 1)
	{
		index--;
		return new TreeNode(inorder[left]);
	}
	TreeNode* root = new TreeNode(postorder[index]);
	int i = left;
	for (; i < right; i++)
	{
		if (inorder[i] == postorder[index])
			break;
	}
	index--; 
	root->right = subTree(index, i + 1, right, inorder, postorder);
	root->left = subTree(index, left, i, inorder, postorder);
	return root;
}
TreeNode * buildTree(vector<int>& inorder, vector<int>& postorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1) return new TreeNode(inorder[0]);
	int i = vsize - 1;
	return subTree2(i, 0, vsize, inorder, postorder);
}

发表于

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

题解

关键就是用前序遍历的数，将中序遍历分成两份，即左子树和右子树。

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
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1)
	{
		preorder.erase(preorder.begin());
		return new TreeNode(inorder[0]);
	}
	TreeNode* root = new TreeNode(preorder[0]);
	vector<int>left, right;
	int i = 0;
	for (; i < vsize; i++)
	{
		if (inorder[i] == preorder[0])
			break;
		else
			left.push_back(inorder[i]);
	}
	for (int j = i + 1; j < vsize; j++)
	{
		right.push_back(inorder[j]);
	}
	preorder.erase(preorder.begin());
	root->left = buildTree(preorder, left);
	root->right = buildTree(preorder, right);
	return root;
}

效率惨淡。主要因为每次递归前都重新创建了vector，再改改：

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
TreeNode* subTree(int& index, int left, int right, vector<int>& preorder, vector<int>& inorder)
{
	if (left == right)return NULL;
	if (right - left == 1)
	{
		index++;
		return new TreeNode(inorder[left]);
	}
	TreeNode* root = new TreeNode(preorder[index]);
	int i = left;
	for (; i < right; i++)
	{
		if (inorder[i] == preorder[index])
			break;
	}
	index++;
	root->left = subTree(index, left, i, preorder, inorder);
	root->right = subTree(index, i + 1, right, preorder, inorder);
	return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1) return new TreeNode(inorder[0]);
	int i = 0;
	return subTree(i,0,vsize,preorder,inorder);
}

我明天就不刷题了哈，最近多爬点数据好交差~~

发表于 更新于

（其实是一锅乱炖）

gcc命令的一般格式为：gcc[选项]要编译的文件[选项][目标文件]。

反汇编

objdump -t obj 输出目标文件的符号表()
objdump -h obj 输出目标文件的所有段概括()
objdump -j .text/.data -S obj 输出指定段的信息，大概就是反汇编源代码把
objdump -S obj C语言与汇编语言同时显示

记一些vimtutor里的小结

  1. 光标在屏幕文本中的移动既可以用箭头键，也可以使用 hjkl 字母键。

    h (左移)       j (下行)       k (上行)     l (右移)

  2. 欲进入 Vim 编辑器(从命令行提示符)，请输入：vim 文件名 <回车>

  3. 欲退出 Vim 编辑器，请输入 :q! <回车> 放弃所有改动。

    或者输入 <ESC>   :wq   <回车> 保存改动。

  4. 在正常模式下删除光标所在位置的字符，请按： x

  5. 欲插入或添加文本，请输入：

    i   输入欲插入文本   \<ESC>             在光标前插入文本
A   输入欲添加文本   \<ESC>             在一行后添加文本

1. 欲从当前光标删除至下一个单词，请输入：dw
2. 欲从当前光标删除至当前行末尾，请输入：d$
3. 欲删除整行，请输入：dd

4. 欲重复一个动作，请在它前面加上一个数字：2w
5. 在正常模式下修改命令的格式是：
         operator   [number]   motion
 其中：
   operator - 操作符，代表要做的事情，比如 d 代表删除
   [number] - 可以附加的数字，代表动作重复的次数
   motion   - 动作，代表在所操作的文本上的移动，例如 w 代表单词(word)，
              $ 代表行末等等。

6. 欲移动光标到行首，请按数字0键：0

7. 欲撤消以前的操作，请输入：u (小写的u)
 欲撤消在一行中所做的改动，请输入：U (大写的U)
 欲撤消以前的撤消命令，恢复以前的操作结果，请输入：CTRL-R

  1. 要重新置入已经删除的文本内容，请按小写字母 p 键。该操作可以将已删除
    的文本内容置于光标之后。如果最后一次删除的是一个整行，那么该行将置
    于当前光标所在行的下一行。

  2. 要替换光标所在位置的字符，请输入小写的 r 和要替换掉原位置字符的新字
    符即可。

  3. 更改类命令允许您改变从当前光标所在位置直到动作指示的位置中间的文本。
    比如输入 ce 可以替换当前光标到单词的末尾的内容；输入 c$ 可以替换当
    前光标到行末的内容。

  4. 更改类命令的格式是：

    c   [number]   motion

1. CTRL-G 用于显示当前光标所在位置和文件状态信息。
 G 用于将光标跳转至文件最后一行。
 先敲入一个行号然后输入大写 G 则是将光标移动至该行号代表的行。
 gg 用于将光标跳转至文件第一行。

2. 输入 / 然后紧随一个字符串是在当前所编辑的文档中正向查找该字符串。
 输入 ? 然后紧随一个字符串则是在当前所编辑的文档中反向查找该字符串。
 完成一次查找之后按 n 键是重复上一次的命令，可在同一方向上查
 找下一个匹配字符串所在；或者按大写 N 向相反方向查找下一匹配字符串所在。
 CTRL-O 带您跳转回较旧的位置，CTRL-I 则带您到较新的位置。

3. 如果光标当前位置是括号(、)、[、]、{、}，按 % 会将光标移动到配对的括号上。

4. 在一行内替换头一个字符串 old 为新的字符串 new，请输入  :s/old/new
 在一行内替换所有的字符串 old 为新的字符串 new，请输入  :s/old/new/g
 在两行内替换所有的字符串 old 为新的字符串 new，请输入  :#,#s/old/new/g
 在文件内替换所有的字符串 old 为新的字符串 new，请输入  :%s/old/new/g
 进行全文替换时询问用户确认每个替换需添加 c 标志        :%s/old/new/gc

  1. :!command 用于执行一个外部命令 command。

    请看一些实际例子：
    ​ (MS-DOS) (Unix)
    ​ :!dir :!ls - 用于显示当前目录的内容。
    ​ :!del FILENAME :!rm FILENAME - 用于删除名为 FILENAME 的文件。

  2. :w FILENAME 可将当前 VIM 中正在编辑的文件保存到名为 FILENAME 的文
    件中。

  3. v motion :w FILENAME 可将当前编辑文件中可视模式下选中的内容保存到文件
    FILENAME 中。

  4. :r FILENAME 可提取磁盘文件 FILENAME 并将其插入到当前文件的光标位置
    后面。

  5. :r !dir 可以读取 dir 命令的输出并将其放置到当前文件的光标位置后面。

1. 输入小写的 o 可以在光标下方打开新的一行并进入插入模式。
 输入大写的 O 可以在光标上方打开新的一行。

2. 输入小写的 a 可以在光标所在位置之后插入文本。
 输入大写的 A 可以在光标所在行的行末之后插入文本。

3. e 命令可以使光标移动到单词末尾。

4. 操作符 y 复制文本，p 粘贴先前复制的文本。

5. 输入大写的 R 将进入替换模式，直至按\<ESC\> 键回到正常模式。

6. 输入 :set xxx 可以设置 xxx 选项。一些有用的选项如下：
    'ic' 'ignorecase'       查找时忽略字母大小写
    'is' 'incsearch'        查找短语时显示部分匹配
    'hls' 'hlsearch'        高亮显示所有的匹配短语
 选项名可以用完整版本，也可以用缩略版本。

7. 在选项前加上 no 可以关闭选项：  :set noic

1. 输入 :help 或者按 \<F1\> 键或\<Help\> 键可以打开帮助窗口。

2. 输入 :help cmd 可以找到关于 cmd 命令的帮助。

3. 输入 CTRL-W CTRL-W  可以使您在窗口之间跳转。

4. 输入 :q 以关闭帮助窗口

5. 您可以创建一个 vimrc 启动脚本文件用来保存您偏好的设置。

6. 当输入 : 命令时，按 CTRL-D 可以查看可能的补全结果。
 按\<TAB\> 可以使用一个补全。

linux 下cat命令的用法

1.一次显示整个文件。$ cat filename

2.从键盘创建一个文件。$ cat > filename

只能创建新文件,不能编辑已有文件.

3.将几个文件合并为一个文件： $cat file1 file2 > file

参数：

-n 或 –number 由 1 开始对所有输出的行数编号

-b 或 –number-nonblank 和 -n 相似，只不过对于空白行不编号

-s 或 –squeeze-blank 当遇到有连续两行以上的空白行，就代换为一行的空白行

-v 或 –show-nonprinting

小端存储

在SIB字节后面读出一个32位的displacement, 发现是00 e0 ff ff, 在小端存储方式下, 它被解释成-0x2000：

补码：1111 1111 1111 1111 1110 0000 0000 0000

原码：1000 0000 0000 0000 0010 0000 0000 0000

发表于 更新于

题目描述

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

题解

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
void dfs2(TreeNode* root,int depth, vector<vector<int>>& res)
{
	if (!root)return;
	if (res.size() <= depth)
		res.push_back({ root->val });
	else
	{
		if (depth % 2)
		{//由右向左扫描，从首部压入
			res[depth].insert(res[depth].begin(), root->val);
		}
		else
		{//由左向右扫描，从尾部加入
			res[depth].push_back(root->val);
		}
	}
	dfs2(root->left, depth + 1, res);
	dfs2(root->right, depth + 1, res);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
	if (!root)return {};
	vector<vector<int>> res = {};
	dfs2(root, 0, res);
	return res;
}

执行用时 :4 ms, 在所有 C++ 提交中击败了81.94%的用户

内存消耗 :12.1 MB, 在所有 C++ 提交中击败了100.00%的用户

附加一个小虾米

1
2
3
4
int maxDepth(TreeNode* root) {
	if (!root)return 0;
	return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

发表于

题目描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

题解

本来一个队列就能解决的，但现在还要区分层次的话，那就得两个队列吧？

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
vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> res;
	if (!root)return res;
	queue<TreeNode*> q,empt,tp;
	q.push(root);
	while (true)
	{
		vector<int> vec;
		while (!q.empty())
		{
			TreeNode* tmp = q.front();
			q.pop();
			vec.push_back(tmp->val);
			if (tmp->left)
				tp.push(tmp->left);
			if (tmp->right)
				tp.push(tmp->right);
		}
		res.push_back(vec);
		if (tp.empty())return res;
		q = tp;
		tp = empt;
	}
	return res;
}

发表于

题目描述

给定一个二叉树，检查它是否是镜像对称的。运用递归和迭代两种方法解决这个问题。

题解

递归：

1
2
3
4
5
6
7
8
9
10
bool compare(TreeNode* tree1, TreeNode* tree2)
{
	if (tree1 == NULL && tree2 == NULL) return true;
    if (tree1 == NULL || tree2 == NULL) return false;
	return tree1->val == tree2->val && compare(tree1->left, tree2->right) && compare(tree1->right, tree2->left);
}
bool isSymmetric(TreeNode* root) {
	if (!root)return true;
	return compare(root->left, root->right);
}

执行用时 :4 ms, 在所有 C++ 提交中击败了92.79%的用户

内存消耗 :14.3 MB, 在所有 C++ 提交中击败了100.00%的用户

既然递归这么省事，为什么还要写迭代。

迭代：

用到了队列的结构，注意一下左右子树压入的顺序就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isSymmetric2(TreeNode* root)
{
	if (!root)return true;
	TreeNode* left = root->left;
	TreeNode* right = root->right;
	queue<TreeNode*> q;
	q.push(left);
	q.push(right);
	while (!q.empty())
	{
		left = q.front();
		q.pop();
		right = q.front();
		q.pop();
		if (left == NULL && right == NULL)continue;
		if (left == NULL || right == NULL)return false;
		if (left->val != right->val)return false;
		q.push(left->left);
		q.push(right->right);
		q.push(left->right);
		q.push(right->left);
	}
	return true;
}

发表于

题目描述

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗？

题解

中序遍历，结果中如果有一个降序对，说明该两个node需交换；若有两个降序对，说明第一对的前一个node和第二对的后一个node需要交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void midtravel2(TreeNode* root,vector<TreeNode*>& v)
{
	if (root == NULL)return;
	midtravel2(root->left,v);
	if (!v.empty())
		if (v[v.size()-1]->val<root->val)
			v.pop_back();
		else
			v.push_back(root);
	v.push_back(root);
	midtravel2(root->right,v);
}
void recoverTree(TreeNode* root) {
	vector<TreeNode*> v;
	midtravel2(root,v);
	int vs = v.size();
	if (v[vs - 1]->val > v[vs - 2]->val) {
		v.pop_back(); vs--;
	}

	int t1 = v[0]->val;
	v[0]->val = v[vs- 1]->val;
	v[vs - 1]->val = t1;
}

执行用时 :44 ms, 在所有 C++ 提交中击败了16.36%的用户

内存消耗 :17.7 MB, 在所有 C++ 提交中击败了63.97%的用户

这效率也太垃圾了。

要求O(1)空间，采用 Morris遍历。学吧。

今天不太想写。复制代码了。https://www.jianshu.com/p/484f587c967c

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

public class MorrisTraval {
    private TreeNode root = null;
    public MorrisTraval(TreeNode r) {
        this.root = r;
    }
    
    public void travel() {
        TreeNode n = this.root;
        
        while (n != null) {
            if (n.left == null) {
                System.out.print(n.vaule + " ");
                n = n.right;
            } else {
                TreeNode pre = getPredecessor(n);
                
                if (pre.right == null) {
                    pre.right = n;
                    n = n.left;
                }else if (pre.right == n) {
                    pre.right = null;
                    System.out.print(n.vaule + " ");
                    n = n.right;
                }
                
            }
        }
    }
    
    private TreeNode getPredecessor(TreeNode n) {
        TreeNode pre = n;
        if (n.left != null) {
            pre = pre.left;
            while (pre.right != null && pre.right != n) {
                pre = pre.right;
            }
        }
        
        return pre;
    }
    
}

getPredecessor 作用是获得给定节点的前序节点，travel 接口做的就是前面描述的算法步骤，在while循环中，进入一个节点时，先判断节点是否有左孩子，没有的话就把节点值打印出来，有的话，先获得前序节点，然后判断前序节点的右孩子指针是否指向自己，是的话把自己的值打印出来，进入右孩子，前序孩子的右孩子指针是空的话，就把右孩子指针指向自己，然后进入左孩子。

Morris遍历，由于要把前缀节点的右指针指向自己，所以暂时会改变二叉树的结构，但在从前缀节点返回到自身时，算法会把前缀节点的右指针重新设置为空，所以二叉树在结构改变后，又会更改回来。

在遍历过程中，每个节点最多会被访问两次，一次是从父节点到当前节点，第二次是从前缀节点的右孩子指针返回当前节点，所以Morris遍历算法的复杂度是O(n)。在遍历过程中，没有申请新内存，因此算法的空间复杂度是O(1).

发表于 更新于

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

题解

这不就，递归吗？有快一点的方法吗……

注意不能相等哦。还要注意左边的最大值小于右边的最小值。

第一版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int getMax(TreeNode* root)
{
	if (!root->right)
		return root->val;
	return getMax(root->right);
}
int getMin(TreeNode* root)
{
	if (!root->left)
		return root->val;
	return getMax(root->left);
}
bool isValidBST(TreeNode* root) {
	if (root == NULL || (root->left == NULL && root->right == NULL))
		return true;
	if ((root->left&&root->val<=getMax(root->left)) || (root->right&&root->val>=getMin(root->right)))
		return false;
	return isValidBST(root->left) && isValidBST(root->right);
}

执行用时 :24 ms, 在所有 C++ 提交中击败了27.46%的用户

内存消耗 :20.1 MB, 在所有 C++ 提交中击败了100.00%的用户

做了很多重复的工作，所以时间效率很低。再改改。

我真是傻逼。中序遍历啊！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool midtravel(TreeNode* root,stack<int>& s)
{
	if (root == NULL)
		return true;
	if (root->left)
		if(!midtravel(root->left,s))return false;
	if (!s.empty() && s.top() >= root->val)return false;
	s.push(root->val);
	if (root->right)
		if (!midtravel(root->right, s))return false;
	return true;
}
bool isValidBST(TreeNode* root) {
	if (root == NULL || (root->left == NULL && root->right == NULL))
		return true;
	stack<int> s;
	return midtravel(root, s);
}

执行用时 :16 ms, 在所有 C++ 提交中击败了76.37%的用户

内存消耗 :20.3 MB, 在所有 C++ 提交中击败了97.25%的用户

再来个下酒菜

1
2
3
4
5
6
7
8
9
10
11
12
bool isSameTree(TreeNode* p, TreeNode* q) {
	if (p == NULL)
	{
		if (q == NULL)
			return true;
		else
			return false;
	}
	if (q == NULL)return false;
	if (p->val != q->val)return false;
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}