考研数据结构算法题笔记
发表更新笔记21 分钟读完 (大约3107个字)

考研数据结构算法题笔记

一寸先が闇なら、二寸先は明るい未来

线性表

反向输出链表

递归

1
2
3
4
function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

对链表进行插入排序

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
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr) 
            return nullptr;
        ListNode *dummyHead = new ListNode(0, head);

        ListNode *lastSorted, *cur;
        lastSorted = head;
        cur = head->next;
        while (lastSorted->next != nullptr) {
            if (cur->val >= lastSorted->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *pre = dummyHead;
                while (cur->val >= pre->next->val) {
                    pre = pre->next;
                }
                lastSorted->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = lastSorted->next;
        }
        return dummyHead->next;
    }
};

单链表逆转

双指针

不是交换结点中的元素，而是把指针逆转。定义两个指针pre和cur，每次操作先让cur的next指向前驱节点，再令pre前进到cur的位置，然后cur再前进一位，最后pre会前进到尾结点，这时指针就全部逆转了。

1
2
3
4
5
6
7
8
9
10
11
12
13
List Reverse (List L)
{
    PtrToNode temp;  // 保存cur的下一个节点
    PtrToNode cur = L;
    PtrToNode pre = NULL;
    while (cur) {
        temp = cur -> Next;
        cur -> Next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

链式表的按序号查找

没啥好说的。

创建的指针cur一定要记得初始化cur = L，不然不知道指向哪。

1
2
3
4
5
6
7
8
9
ElementType FindKth (List L, int K) {
    List cur = L;
    int i;
    for (i = 1; cur != NULL && i < K; i ++) {
        cur = cur -> Next;
    }
    if (cur == NULL || i > K) return ERROR;
    else return cur -> Data;
}

两数相加

模拟

遍历两个链表，每次值相加后赋值给新链表的尾结点，记录下进位值留给下次运算。

注意两个链表长度不一定相等，以及如果最高位产生了进位，需要再新建一个结点用来存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while(l1 || l2) {
            int x = l1 ? l1->val : 0;
            int y = l2 ? l2->val : 0;
            int sum = x + y + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) tail->next = new ListNode(1);
        return head;
    }
};

350. 两个数组的交集 II

排序 + 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int n1 = nums1.size(), n2 = nums2.size();
        int i = 0, j = 0;
        vector<int> res;
        while (i < n1 && j < n2) {
            if (nums1[i] < nums2[j]) i ++;
            else if (nums2[j] < nums1[i]) j ++;
            if (i < n1 && j < n2 && nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                i ++, j ++;
            }
        }
        return res;
    }
};

严书2.11

设线性表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，保持该表的有序性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

void func(SqList &va, int x) {
    if (va.length == va.listsize)
    int i = 0;
    while (va[i] > x) {
        i ++;
    }
    for (int j = va.size(); j >= i; j --) {
        va[j + 1] = va[j]
    }
    va[i] = x;
    return;
}

严书2.14

在带头结点的单链表结构上实现线性表操作Length(L)

1
2
3
4
5
6
7
8
9
int Length(List &L) {
    int len = 0;
	ListNode cur = L;
    while (cur != NULL) {
        len ++;
        cur = cur->next;
    }
    return len;
}

严书2.15

已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的实践完成链接运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void func(List &ha, List &hb) {
    ListNode hc = new ListNode;
    ListNode p_short, p_long;
    ListNode h;
    if (m < n) {
        p_short = ha;
        p_long = hb;
        h = ha;
    } else {
        p_short = hb;
        h = hb;
        p_long = ha;
    }
    while (p_short->next != NULL) {
        p_short = p_short->next;
    }
    p_short->next = p_long->next;
    hc->next = h;
}

严书2.20

已知单链表中元素以递增有序排列，写一算法删除表中所有值相同的多余元素，同时释放被删除的结点空间

1
2
3
4
5
6
7
8
9
10
11
void func(LinkList L) {
    LinkList p1 = L, p2 = L->next;
    while (p2 != NULL) {
        if (p1->data == p2->data) {
            ListNode t = p2;
            p2 = p2->next;
            p1->next = p2;
            delete t;
        }
    }
}

严书 2.22

对单链表实现就地逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
// 双指针
void reverse(List L) {
    ListNode *temp;
    ListNode *cur = L;
    ListNode *pre = NULL;
    while (cur) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return;
}

严书2.31

假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点

1
2
3
4
5
6
7
8
9
10
void delete_node(ListNode &s) {
    ListNode *t = s;
    while (t->next->next != s) {
        t = t->next;
    }
    ListNode *p = t->next;
    t->next = p->next;
    delete p;
    return;
}

二叉树

翻转二叉树

第一眼就想到了层序遍历。不过递归也可以，而且代码更短，考试的时候还是写递归吧。

也是一个启示，树的题目基本上都可以往递归上面想。

  1. 层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> q;
        if (root != nullptr) q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i ++) {
                TreeNode* cur = q.front();
                q.pop();
                swap(cur -> left, cur -> right);  // 交换左右子树
                // 入队的顺序和层序遍历相反。这里是先右孩子入队，再左孩子入队。
                if (cur -> right != nullptr) q.push(cur -> right);
                if (cur -> left != nullptr) q.push(cur -> left);
            }
        }
        return root;
    }
};
  1. 递归

在前序遍历的基础上，把访问中间结点的操作改为交换左右子树。因为前序遍历是中左右的顺序，所以在原本访问中间结点的时候交换左右孩子，就能实现翻转二叉树。形象理解就是从上至下的递归。

后序遍历是左右中的顺序，所以同理，这里把swap放到后面，变成后序遍历也可以。形象理解就是从下至上的递归。

但是中序不行。有些结点会被翻转两遍。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;    // 终止条件
        swap(root -> left, root -> right);   // 每次递归，交换左右子树
        invertTree(root -> left);
        invertTree(root -> right);
        // swap语句放到这个位置也可以
        return root;
    }
};

在每个树行中找最大值

这种涉及到“行”的，当然很自然就想到层序遍历。直接默写板子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> q;
        if (root != nullptr) q.push(root);
        vector<int> res;
        while (!q.empty()) {
            int size = q.size();
            int maxVal = INT_MIN;
            for (int i = 0; i < size; i ++) {
                TreeNode* cur = q.front();
                maxVal = max(cur -> val, maxVal);
                q.pop();
                if (cur -> left != nullptr) q.push(cur -> left);
                if (cur -> right != nullptr) q.push(cur -> right);
            }
            res.push_back(maxVal);
        }
        return res;
    }
};

对称二叉树

递归，递归，还是递归！

判断一棵二叉树是否对称，我们先把这棵树从根结点分开，看作左右两颗树。将左树的左边结点、右树的右边结点称为“外”，左树的右边结点和右树的左边结点称为“内”。如果两边的内外结点互相相等，则两棵树对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isSymmetric(TreeNode *root)
    {
        if (root == nullptr)  // 如果是空树，对称
            return true;
        return compare(root->left, root->right);  // 从根结点的两颗子树开始由上至下判断
    }
    bool compare(TreeNode *p, TreeNode *q)
    {
        if (!p && !q)  // 如果两个结点都是空的，对称
            return true;
        else if (!p || !q)  // 如果两个结点只有一个是空的，不对称
            return false;
        else if (p->val != q->val)  // 如果两个结点都不空，比较它们的值，如果不等，则不对称
            return false;
        bool inside = compare(p->right, q->left);  // 比较内结点
        bool outside = compare(p->left, q->right); // 比较外结点
        return (inside && outside);  // 只有二者都为true时才对称
    }
}

二叉树的最大深度

模板题

  1. 层序遍历（迭代）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int height = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i ++) {
                if (q.front()->left != nullptr) q.push(q.front()->left);
                if (q.front()->right != nullptr) q.push(q.front()->right);
                q.pop();
            }
            height ++;
        }
        return height;
    }
}
  1. 先序遍历（递归）

首先确定这个递归函数是要干什么：求树的高度。所以返回值是int类型；

然后确定终止条件：root == null，空树，树高为0；

最后确定单层递归的逻辑：树的最大深度等于max(左子树深度，右子树深度) + 1。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int lheight = maxDepth(root->left);
        int rheight = maxDepth(root->right);
        return (max(lheight, rheight) + 1);
    }
};

二叉树的最小深度

和上一题类似，但是这一题要求的是“从根结点到最近叶子结点的最短路径”，所以如果一棵树的左/右结点为空，其最小深度不是1，而是“非空子树的最小深度+1”。如果沿用上一题的写法，那就会在这里出错。

以下给出递归解法。当然也可以层序遍历，这里就不写了。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int lheight = minDepth(root->left);
        int rheight = minDepth(root->right);
        if (!root->left && root->right) return rheight + 1;
        if (root->left && !root->right) return lheight + 1;
        return (min(lheight, rheight) + 1);
    }
};

平衡二叉树

和求二叉树最大深度那题类似。

递归三部曲：

  1. 确定参数和返回值类型

传入根结点，如果这棵树是平衡二叉树，则返回树高度；如果不是，则返回-1；所以返回值类型为int

  1. 确定终止条件

如果为空树，返回0；如果左/右子树高度为-1（说明不是平衡二叉树），返回-1。

  1. 确定单层递归的目的

如果左右子树高度差大于1，返回-1，否则返回树高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int getHeight(TreeNode* root) {
        if (root == nullptr) return 0;
        int lheight = getHeight(root->left);
        if (lheight == -1) return -1; 
        int rheight = getHeight(root->right);
        if (rheight == -1) return -1;
        if (abs(lheight - rheight) > 1) return -1;
        else return(max(lheight, rheight) + 1);
    }
    bool isBalanced(TreeNode* root) {
        return (getHeight(root) >= 0);
    }
};

652. 寻找重复的子树

序列化

将每一棵子树都「序列化」成一个字符串，并且保证：

  • 相同的子树会被序列化成相同的子串；
  • 不同的子树会被序列化成不同的子串。

那么我们只要使用一个哈希表存储所有子树的序列化结果，如果某一个结果出现了超过一次，我们就发现了一类重复子树。

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
class Solution {
private:
    unordered_map<string, int> umap;
    vector<TreeNode*> ans; 
public:
    string dfs(TreeNode* root) {
        if (!root) return "";
        // 注意这一行两个dfs前的“ ”不能删掉
        string str = to_string(root->val) + " " + dfs(root->left) + " " + dfs(root->right);
        umap[str] ++;
        if (umap[str] == 2) ans.push_back(root);
        return str;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

/*
  1
 2 3
1   2
     1
考虑这样一棵树，当遍历到2时，如果没有" "用来分隔根和左右孩子的值的话，
左右两个以2为根的子树都会被序列化为"21"，但是这两棵树不是相同的。
而有" "进行分隔的话，左边就被序列化为"2 1 "，右边是"2  1"，二者不同。
*/

严书 6.36

T1与T2均为空，或者左右子树分别相似，则称T1与T2相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool similar(Tree T1, Tree T2) {
    if (T1 == NULL) {
        if (T2 == NULL)
            return true;
        else
            return false;
    } else {
        if (T2 == NULL)
            return false;
        else
            return (similar(T1->lchild, T2->rchild) && similar(T1->rchild, T2->rchild));
    }
    
}

严书 6.42

递归求二叉树中叶子结点的数目

1
2
3
4
5
6
7
int leaf_number(BiTree T) {
    if (T == NULL)
        return 0;
    if (!T->lchild && !T->rchild)
        return 1;
    return leaf_number(T->lchild) + leaf_number(T->rchild);
}

严书 6.45

删除以元素值为x的结点为根的子树

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
// levelOrder
void delete_x(BiTree &T, int x) {
    if (T == NULL)
        return;
    queue<TreeNode*> q;
    q.push(T);
    while(!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i ++) {
            TreeNode *t = q.front();
            if (t->val == x)
                delete t;
            else {
                if (t->lchild != NULL)
                    q.push(t->lchild);
                if (t->rchild != NULL)
                    q.push(t->rchild);
                q.pop();
            }
        }
    }
    return;
}

// recursion, preOrder delete
bool delete_x(BiTree &T, int x) {
    if (T->data == x) {
        delete_tree(T);
        T = NULL;
        return true;
    }
    delete_x(T->lchild, x);
    delete_x(T->rchild, x);
    return true;
}
bool delete_tree(BiTree &T) {
    if (T) {
        delete_tree(T->lchild);
        delete_tree(T->rchild);
        delete T;
        return true;
    }
    return false;
}

严书 6.46

递归算法复制一棵二叉树

1
2
3
4
5
6
7
8
void copy_tree(BiTree &T, BiTree &T1) {
    if (T == NULL)
        return;
    TreeNode t = new TreeNode;
    t->data = T->data;
    copy_tree(T->lchild, t->lchild);
    copy_tree(T->rchild, t->rchild);
 }

严书 6.55

为二叉链表结点增加DescNum域，表示结点的孩子个数

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct TreeNode {
    struct TreeNode *lchild;
    struct TreeNode *rchild;
    int data;
    int DescNum;
} TreeNode, *BiTree;

int add_descnum(BiTree &T) {
    if (!T)
        return 0;
    T->DescNum = add_descnum(T->lchild) + add_descnum(T->rchild);
    return T->DescNum + 1;
}

动态规划

考研数据结构算法题笔记

https://moonlight-noodles.cn/2022/07/14/DS-Kaoyan-algorithm/

作者

Moodles

发布于

2022-07-14

更新于

2022-12-22

许可协议

#
关注我

链接

归档

分类

最新文章

标签

三岛由纪夫1
图论1
字符串3
总结3
想法6
操作系统1
数据结构与算法6
日语2
考研3
读后感1
音乐1
×