爱喝茶的仙人掌

最近在学习吴恩达神经网络和深度网络相关内容，遇到一个问题，因为使用的是Jupyter Notebook进行编码，创建第三方环境后Jupyter默认调用的Kernel还是本地Python环境。

该问题已成功解决，本文总结一下解决方法。

背景

西南某985 软工专业 GPA 3.8，有一些计算机类竞赛获奖，一国三，两省二，初试成绩366，复试成绩92（专业第一？），成功上岸复旦 工程与应用技术研究院 计算机方向，我将从自己的考研经历开始介绍，希望能给诸位带来一些帮助。本文同步发布于我的个人博客和知乎及王道论坛，本人未参加任何考研辅导机构。

时间线

之前打算出国，因为突逢疫情，实际从6月份才开始了解考研（时间晚也完全来的及），数学只过了一遍，专业课两遍。2020春季学期在伯克利交流，5月底在大使馆帮助下回国，当时特别的纠结与迷茫，在隔离期间和学长学姐，还有同学不断交流，决定考研，在此也非常感谢他们的帮助和鼓励。

日期和ID的双射问题

Description：假设日期1969.01.01用0表示，请开发一个函数输出任意日期的整数表示（日期小于1969.01.01的用负数表示）。反过来，给定日期的整数表示，开发一个函数求日期对应的年月日。

HashMap在Java里是一种非常常用的数据结构，这次主要想从源码层面来进一步了解学习一下HashMap。

本文主要讨论的问题：

• HashMap的底层实现
• HashMap的扩容机制
• HashMap和HashTable的区别

HashMap的底层实现

首先我们需要理解动态语言和静态语言

1. 动态语言 是一类在运行时可以改变其结构的语言: 例如新的函数、对象、甚至新的代码可以被引进，已有的函数可以被删除或是发生其他结构上的变化。 通俗点说就是在运行时代码可以根据某些条件改变自身结构。 主要动态语言:Object-C，C#，JavaScript，PHP，Python，Erlang。
2. 静态语言 与动态语言相对应的，运行时结构不可变的语言就是静态语言。如Java（因为引入了反射机制，Java可以算是准动态语言）、C、C++。

反射机制允许程序在执行期间通过Reflection API取得任何类的内部信息，并能直接操作任意对象内部属性及方法。加载完类之后，在堆内存的方法区中就产生了一个Class类型的对象(一个类只有一个Class对象)，这个对象就包含了完整的类的结构信息。

本文主要讨论二叉树的四种遍历方式，以及对应线索二叉树的构造以及遍历过程。

先序遍历（PreOrder）

算法逻辑：（NLR）

1. 首先访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树。

由此可以简单写出对应递归算法：

1
2
3
4
5
6
7

void PreOrder(BinTree T) {
	if(T != null) {
    visit(T);
    PreOrder(T -> lchild);
    PreOrder(T -> rchild);
  }
}

因为每个节点都被访问一次，所以时间复杂度为\(O(n)\)，递归工作栈的深度恰好为树的深度，所以最坏情况是树为单链树时空间复杂度为\(O(n)\)。

接下来使用非递归方式实现二叉树的先序遍历：

利用一个栈实现以下递归函数的非递归计算：

\[ P_n(x)=\left\{ \begin{array}{aligned} 1, && n=0 \\ 2x, && n=1\\ 2xP_{n-1}(x)-2(n-1)P_{n-2}(x), && n>1 \end{array} \right. \]

首先我们定义栈的初始结构，栈应该要记录每次对应的n值，和函数值。

1
2
3
4
5

struct stack
{
    int n;
    double val;
} st[maxsize];

设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

void deleteRecursive(LNode &p, Elemtype x) {
  if (p == null) {
    return;
  }
  if (p->data == x) {
    LNode temp = p; 
    p = p->next; //在此处思考上层递归，会补链
    free(temp); 
    deleteRecursive(p, x);
  } else {
    deleteRecursive(p->next, x);
  }
}

从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

算法的代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Elemtype deleteMin(Sqlist &arr) { //可以考虑形参中引入 &min，
  if (arr.length == 0 && arr == null) {
    printf("The array is empty.");
    return 0;
  } else {
    Elemtype min = arr[0];
    int index = 0;
    for(int i = 1; i <= arr.length; i++) {
      if (arr[i] <= min) {
        min = arr[i];
        index = i;
      }
    }
    arr[index] = arr[arr.length - 1];
    arr.length--;
    return min;
  }
}