算法练习-1

最近几天写算法写的挺开心的，为了以后保研面试啥的，继续准备算法学习工作，在家闲着也是闲着。

1.复杂链表的复制

1.1题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

来源：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

1.2思路分析

采用深度优先搜索：

  • 从头结点 head 开始拷贝；
  • 由于一个结点可能被多个指针指到，因此如果该结点已被拷贝，则不需要重复拷贝；
  • 如果还没拷贝该结点，则创建一个新的结点进行拷贝，并将拷贝过的结点保存在哈希表中；
  • 使用递归拷贝所有的 next 结点，再递归拷贝所有的 random 结点。

1.3代码

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
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        #递归遍历复制所有节点
        def dfs(head):
            if not head: 
                return None
            if head in visited:
                return visited[head]
            # 创建新结点
            copy = Node(head.val, None, None)
            visited[head] = copy
            copy.next = dfs(head.next)
            copy.random = dfs(head.random)
            return copy
        visited = {}
        return dfs(head)

1
2
3
4
5
6
7
8
9
10
11
12
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
#直接调用深度复制deepcopy函数即可
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        return copy.deepcopy(head)

2.对称二叉树

2.1题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/
2 2
/ \ /
3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1

/
2 2
\
3 3

来源：https://leetcode-cn.com/problems/symmetric-tree

2.2思路分析

首先第一眼就反应到应该用递归操作比较简单，递归结束的条件是探索到叶子节点。

如果左右叶子都为NULL，证明该节点为叶节点

对称树要求左边叶子值等于右半部分对应叶子右边的值，于是递归条件就是判断相应的值是不是相等，是否有对应的节点。

2.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isMirror(struct TreeNode* l,struct TreeNode* r){
    if(!l&&!r)//都为NULL
        return true;
    if(!l||!r)
        return false;
    return (l->val==r->val)&&isMirror(l->left,r->right)&&isMirror(l->right,r->left);
}
bool isSymmetric(struct TreeNode* root){
    return isMirror(root,root);
}

3.寻找旋转排序数组中的最小值

3.1 题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

来源：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array

3.2思路分析

这个题就是最简单的排序，但是我们要想办法找一个时间复杂度小的算法。

最简单的直接排序就不说了，有个想法就是找出来旋转的那个点，特征就是前面的数字比后面的数字大，那么后面那个数字一定是最小的。但是要注意边界问题，下面的注释有说明。

3.3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMin(int* nums, int numsSize){
    int i;
    if(numsSize <= 1){//判断数组长度是否为1，为1直接返回
        return nums[numsSize- 1]; 
    }
    for(i = 0;i<numsSize - 1;i++){//一般情况
        if(nums[i]>nums[i+1]){
            return nums[i+1];
        }
    }
    if(nums[numsSize-1] < nums[0]){//全反转情况
        return nums[numsSize - 1];
    }
    return nums[0];//未反转情况
}

4.二叉搜索树中第K小的元素

4.1题目描述

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/
1 4

2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 3

来源：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

4.2思路分析

最开始忘记了二叉搜索树的性质，所以还想着遍历之后再排序，后来发现二叉排序树是有性质的，采用中序遍历的结果就是从小到大排列的值。

于是我们可以递归采用中序遍历选出第k个值即可。

为了优化算法，我们在找到第k个值之后就结束，这样就可以减小搜索的时间复杂度。

4.3代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//因为是二叉查找树，所以节点比左孩子小，比右孩子大，
//使用递归的方法进行中序遍历，遍历的过程中将节点存入到队列中，队列中的元素即为从小到大排序好了，
//最后要第K小的元素，就从队列中出队好了
//遍历到第k个元素即可停止遍历
int findResult[100],counter;
void LDR(struct TreeNode * root,int k){//
    if (root == NULL || counter > k)
        return NULL;
    LDR(root->left,k);
    findResult[counter++] = root->val;
    LDR(root->right,k);
}
int kthSmallest(struct TreeNode* root, int k){
    counter = 0;
    LDR(root,k);
    return findResult[k-1];
}

4.4复习遍历算法

先序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

若二叉树为空则结束返回，否则：

  • 访问根节点
  • 前序遍历左子树
  • 前序遍历右子树

已知后序遍历和中序遍历，就能确定前序遍历。

中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：

  • 中序遍历左子树
  • 访问根结点
  • 中序遍历右子树

后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

若二叉树为空则结束返回，否则：

  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根节点

三种遍历算法采用递归最容易实现。

5.UTF8编码验证

5.1题目描述

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：

对于 1 字节的字符，字节的第一位设为0，后面7位为这个符号的unicode码。
对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的unicode码。

这是 UTF-8 编码的工作方式：

Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
——————————-+———————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

给定一个表示数据的整数数组，返回它是否为有效的 utf-8 编码。

注意:
输入是整数数组。只有每个整数的最低 8 个有效位用来存储数据。这意味着每个整数只表示 1 字节的数据。

来源：https://leetcode-cn.com/problems/utf-8-validation

5.2思路分析

最简单的思路就是不做什么进制转换，直接按照不同条件分支判断即可，然后判断后面的字符是否符合标准，如果有一个不符合就直接返回false。中间踩了一个坑，就是忘记了数字位数不够的问题，导致数组访问溢出的情况。

5.3代码

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
bool validUtf8(int* data, int dataSize){
    int i=0,j;
    while(i<dataSize){
        if(data[i]>=240&&data[i]<=247){//情形4
            if(dataSize<4){
                    return false;
                }
            for(j = 1;j < 4;j++){
                if(data[i+j]<128||data[i+j]>191){
                    return false;
                }
            }
            i = i+4;
        }
        else if(data[i]>=224&&data[i]<=239){//情形3
            for(j = 1;j < 3;j++){
                if(dataSize<3){
                    return false;
                }
                if(data[i+j]<128||data[i+j]>191){
                    return false;
                }
            }
            i = i+3;
        }
        else if(data[i]>=192&&data[i]<=223){//情形2
            if(dataSize<2){
                return false;
            }
            if(data[i+1]<128||data[i+1]>191){
                return false;
            }  
            i = i+2;
        }
        else if(data[i]<=127){//情形1
            i = i + 1;
        }
        else{
            return false;//不符合要求
        }
    }
    return true;
}

6.二叉树的最小深度

6.1题目描述

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7

返回它的最小深度 2.

来源：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree

6.2思路分析

第一思路就是使用递归遍历，遍历整棵树后即可获得树的最小深度。

递归算法一定要注意，当时我将depth初始化为0的时候会出错，因为后面有个取最小值的步骤，如果深度初始化为0，每次取最小值都取0，最后结果肯定是错误的。因此我们需要取一个最大的值，保证不会出问题。

6.3代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int min(int a,int b){
    if (a<=b){
        return a;
    }
    return b;
}

int minDepth(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    int depth = 65535;//不应该初始化为0，应该初始化为一个大的值
    if(root->left == NULL && root->right == NULL){
        return 1;
    }
    if(root->left != NULL){
        depth = min(minDepth(root->left),depth);
    }
    if(root->right != NULL){
        depth = min(minDepth(root->right),depth);
    }
    return depth+1;
}
#算法
算法练习-1
https://chujian521.github.io/blog/2020/02/25/算法练习-1/
作者
Encounter
发布于
2020年2月25日
许可协议