即日起，本网站将终止对博客的更新，后续更新博客将会在CSDN平台上进行。
  这是我在大一进入西安邮电大学大数据与人工智能实验室之后搭建的第一个个人博客网站，非常感谢实验室可以给我一个自我锻炼的机会，也非常感谢实验室的学长学姐们在我们遇到问题的时候悉心帮助和指导。未来我还将会在实验室的机器学习小组继续努力学习。
  我的CSDN博客链接为https://blog.csdn.net/qq_45554010。
  再见，Hexo。

任务需求

  上周我们对爬取到的数据做了一些简单的处理，本周的任务就是将其中的文本信息数字化表示。

Python源代码

  本周的任务，大部分数字化都可以通过字典来解决，只有租期一列比较特殊，有的房源数据的租期是以年为单位，有的是以月为单位，还有的是暂无数据。按照小组给出的需求，首先要取最低租期，把以年为单位的数据都转换成以月为单位，计算出均值，再进行二次处理，将暂无数据的信息替换成均值。这里可以使用正则表达式来解决。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import csv
import re


def LabelData(elem, labeled_col_list, label):
    """
    对大量数据自动编号
    :return: 元组，其中的元素为最终编号和下一待编号
    """
    if elem not in labeled_col_list:
        labeled_col_list.append(elem)
        ret = label
        label += 1
    else:
        ret = labeled_col_list.index(elem) + 1
    return ret, label


# 对所在区县、所在街道或地区、小区名称编号使用的变量
labeled_col_1, labeled_col_2, labeled_col_3 = [], [], []
label1, label2, label3 = 1, 1, 1
# 计算租期的均值所用的求和变量
total_term = 0
# 存储各行信息列表的列表
rows = []

with open('ProcessedTianjinRentHouseInfo.csv', 'r', newline='') as csv_in_file:
    with open('LabeledTianjinRentHouseInfo.csv', 'w', newline='') as csv_out_file:
        filereader = csv.reader(csv_in_file)
        filewriter = csv.writer(csv_out_file)

        # 读写标题行
        head = next(filereader)
        filewriter.writerow(head)

        # 第一次处理数据
        for row_list in filereader:
            # 所在城市
            row_list[0] = 1
            # 所在区县
            row_1_data = LabelData(row_list[1], labeled_col_1, label1)
            row_list[1] = row_1_data[0]
            label1 = row_1_data[1]
            # 所在街道或地区
            row_2_data = LabelData(row_list[2], labeled_col_2, label2)
            row_list[2] = row_2_data[0]
            label2 = row_2_data[1]
            # 小区名称
            row_3_data = LabelData(row_list[3], labeled_col_3, label3)
            row_list[3] = row_3_data[0]
            label3 = row_3_data[1]
            # 租赁方式
            if row_list[5] == '整租':
                row_list[5] = 1
            elif row_list[5] == '合租':
                row_list[5] = 2
            # 朝向
            aspect_dic = {
                '东': 1,
                '南': 2,
                '西': 3,
                '北': 4,
                '东南': 5,
                '东北': 6,
                '西南': 7,
                '西北': 8
            }
            row_list[6] = aspect_dic[row_list[6]]
            # 计费方式
            charge_mode_dic = {
                '月付价': 1,
                '季付价': 2,
                '半年付价': 3,
                '年付价': 4,
                'None': 5
            }
            row_list[8] = charge_mode_dic[row_list[8]]
            # 入住
            if row_list[12] == '随时入住':
                row_list[12] = 1
            # TODO 租期
            if row_list[13] != '暂无数据':
                if re.search(r'年', row_list[13]):
                    term = int(re.sub(r'(\D)', ' ', row_list[13]).split()[0]) * 12
                elif re.search(r'月', row_list[13]):
                    term = int(re.sub(r'(\D)', ' ', row_list[13]).split()[0])
                row_list[13] = term
                total_term += term
            # 看房
            see_house_dic = {
                '随时可看': 1,
                '需提前预约': 2,
                '一般下班后可看': 3
            }
            row_list[14] = see_house_dic[row_list[14]]
            # 所在楼层
            floor_dic = {
                '低楼层': 1,
                '中楼层': 2,
                '高楼层': 3
            }
            row_list[15] = floor_dic[row_list[15]]
            # 电梯
            lift_dic = {
                '有': 1,
                '无': 2,
                '暂无数据': 3
            }
            row_list[17] = lift_dic[row_list[17]]
            # 车位
            stall_dic = {
                '暂无数据': 1,
                '免费使用': 2,
                '租用车位': 3
            }
            row_list[18] = stall_dic[row_list[18]]
            # 用水
            water_dic = {
                '民水': 1,
                '商水': 2,
                '暂无数据': 3
            }
            row_list[19] = water_dic[row_list[19]]
            # 用电
            elec_dic = {
                '民电': 1,
                '商电': 2,
                '暂无数据': 3
            }
            row_list[20] = elec_dic[row_list[20]]
            # 燃气
            gas_dic = {
                '有': 1,
                '无': 2,
                '暂无数据': 3
            }
            row_list[21] = gas_dic[row_list[21]]
            # 采暖
            heating_dic = {
                '集中供暖': 1,
                '自采暖': 2,
                '暂无数据': 3
            }
            row_list[22] = heating_dic[row_list[22]]
            # 将第一次处理后的数据保存在rows列表中
            rows.append(row_list)

        # 第二次处理数据
        for row_list in rows:
            # 再次处理暂无数据的租期，将其更改为均值
            if row_list[13] == '暂无数据':
                row_list[13] = total_term // 1503
            # 将处理后的数据写入文件
            filewriter.writerow(row_list)
        print('写入成功')

运行结果

LeetCode 3. 无重复字符的最长子串

难度 中等

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例1

1
2
3

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为3。

示例2

1
2
3

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为1。

示例3

1
2
3
4

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为3。
请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。

解法 滑动窗口
语言：C

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

int lengthOfLongestSubstring(char* s) {
    int i;
    int cnt = 0;
    int max = 0;
    int start = 0;                          /* 记录最长子串起点 */
    int flag[128] = {0};                    /* 标记数组 */
    for (i = 0; s[i] != '\0'; i++) {
        if (flag[s[i]] > start) {           /* 如果出现了重复字符 */
            cnt = i - start;                /* 记录当前子串的长度 */
            max = cnt > max ? cnt : max;    /* 刷新最长子串的长度 */
            start = flag[s[i]];             /* 重置起点 */
        }
        flag[s[i]] = i + 1;                 /* 刷新标记数组 */
    }
    cnt = i - start;                        /* 记录最后一子串的长度 */
    return cnt > max ? cnt : max;           /* 刷新最长子串的长度并返回结果 */
}

这道题采用滑动窗口的思想，大致思路如下图所示。对于给定的字符串s，对其进行遍历，找出以每个字符最长无重复字符子串长度，再取这些长度的最大值，即为本题所求。

那么，我们该如何找出以每个字符开头的最大子串呢？
引入标记数组flag，长度为128（因为ASCII码的十进制数范围为0-127），并将其所有元素初始化为0。初始化cnt变量为0，用于记录每个子串的长度。初始化max变量为0，每记录一个子串的长度，就刷新一次max，确保可以保留最长的子串长度。
遍历字符串s，找出以每个字符开头的最长无重复字符子串。首先判断子串中有没有出现重复字符，如果出现了重复字符，则必定有flag[s[i]] > start这一条件成立。如果没有出现重复字符，则刷新标记数组元素flag[s[i]] = i + 1；否则，记录当前子串的长度cnt = i - start，刷新max的值，并重置起点start为flag[s[i]]，最后刷新标记数组元素flag[s[i]] = i + 1。在遍历字符串的循环外，我们仍需记录最后一个子串的长度cnt并且刷新最长无重复字符子串长度max，再返回结果。
需要说明的一点是，当我们在遍历的过程中判断出子串中出现了重复字符时，寻找下一个字符开头的子串时并不需要再次从那个字符开始，而是可以从中断点处继续搜索，因为前面的那一部分子串必定不会包含重复元素。

LeetCode 66. 加一

难度 简单

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数0之外，这个整数不会以零开头。

示例1

1
2
3

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字123。

示例2

1
2
3

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字4321。

解法 数学
语言：C

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

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    for (int i = digitsSize - 1; i >= 0; i--) {
        if (digits[i] == 9) {
            digits[i] = 0;
        } else {
            digits[i]++;
            * returnSize = digitsSize;
            return digits;
        }
    }
    int* ret = (int*)malloc(sizeof(int) * (digitsSize + 1));
    memset(ret, 0, sizeof(int) * (digitsSize + 1));
    ret[0] = 1;
    * returnSize = digitsSize + 1;
    return ret;
}

这道题总体来说类似于数学的竖式计算，需要分情况来讨论。
最简单的情况就是不涉及进位操作，这样只需要把个位上的数字加1。稍微复杂一点，个位上的数字是9，这时候就要考虑到进位的情况，即让个位数字变为0，十位数字加1。同样地，如果十位数字也是9的话，进位操作就要将十位数字变为0，百位数字加1。百位、千位、万位……数字也是9的情况以此类推。最极端的情况，这个整数的所有位都是9，那么将其所有位的数字都置为0，再从前面添上1即可得到答案。

创建和删除操作

touch

说明
创建文件或修改文件时间。
如果文件不存在，可以创建一个空白文件。
如果文件已经存在，可以修改文件的末次修改日期。

mkdir

说明
创建一个新的目录。
可选参数
-p：可以递归创建目录。
注意
新建目录的名称不能与当前目录中已有的目录或文件同名。

rm

说明
删除文件或目录。
注意
使用rm命令删除的文件或目录不可恢复。
rm常用选项

拷贝和移动文件

tree

说明
以树状图列出文件目录结构。
参数
-d：只显示目录。

cp

说明
复制文件或目录到另一个文件或目录中。
cp常用选项

mv

说明
移动文件或目录，也可以给文件或目录重命名。
参数
-i：覆盖文件前提示。

查看文件内容

cat

说明
cat命令可以用来查看文件内容、创建文件、文件合并、追加文件内容等功能。
cat会一次显示所有的内容，适合查看内容较少的文本文件。
cat常用选项

在Linux中，nl命令与cat -b的效果等价。

more

说明
more命令可以用于分屏显示文件内容，每次只显示一页内容。
more命令适合于查看内容较多的文本文件。
操作键

grep

说明
grep命令可以搜索文本文件内容。
grep允许对文本文件进行模式查找（正则表达式）。
grep常用选项

grep常用的两种模式查找

其他文件相关命令

echo

echo会在终端中显示参数指定的文字，通常会和重定向联合使用。

重定向>和>>

Linux允许将命令执行结果重定向到一个文件，将本应显示在终端上的内容输出或追加到指定文件中。
>表示输出，会覆盖文件原有的内容。
>>表示追加，会将内容追加到已有文件的末尾。

管道 |

Linux允许将一个命令的输出通过管道作为另一个命令的输入。
常用的管道命令有：more, grep等。

任务需求

  上周我们已经从贝壳租房网爬取了某个城市（我选择的是天津）的房源信息数据，并保存在了CSV文件中，如下图所示：

  本周的任务是对这个数据集进行一些处理，需求如下：
  1. 去除房源编号一列；
  2. 所在区县一列，只保留区县名，不保留“区”字样；
  3. 面积一列只保留数字，去除单位；
  4. 朝向一列只保留第一个方位；
  5. 月租一列只保留数字，去除单位；
  6. 室、厅、卫三列只保留数字，去除单位；
  7. 入住一列如果是具体日期，则修改为yyyymmdd格式，如2020-7-31应修改为20200731；
  8. 所在楼层一列如果是具体数字，则与总楼层比较之后修改为高楼层、中楼层或低楼层。
  9. 总楼层一列只保留数字，去除单位。

Python源代码

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import csv


with open('TianjinRentHouseInfo.csv', 'r', newline='') as csv_in_file:
    with open('ProcessedTianjinRentHouseInfo.csv', 'w', newline='') as csv_out_file:
        filereader = csv.reader(csv_in_file)
        filewriter = csv.writer(csv_out_file)
        header = next(filereader)
        new_header = ['所在城市', '所在区县', '所在街道或地区', '小区名称', '面积', '租赁方式', '朝向', '月租', '计费方式', '室',
                      '厅', '卫', '入住', '租期', '看房', '所在楼层', '总楼层', '电梯', '车位', '用水', '用电', '燃气', '采暖']
        filewriter.writerow(new_header)
        for row_list in filereader:
            if '新区' in row_list[2]:    # 统一所在区县格式
                row_list[2] = row_list[2].replace('新区', '')
            elif '区' in row_list[2]:
                row_list[2] = row_list[2].replace('区', '')
            row_list[5] = row_list[5][:-1]    # 去除面积的单位
            row_list[7] = row_list[7][0]    # 只保留朝向的第一个方位
            row_list[8] = row_list[8].replace('元/月', '')    # 去除月租的单位
            row_list[10] = row_list[10].replace('室', '')    # 去除室的单位
            row_list[11] = row_list[11].replace('厅', '')    # 去除厅的单位
            row_list[12] = row_list[12].replace('卫', '')    # 去除卫的单位
            if row_list[13] != '随时入住':    # 如果入住有具体时间，将其统一为yyyymmdd格式
                row_list[13] = row_list[13].replace('-', '')
            row_list[17] = row_list[17].replace('层', '')    # 去除总楼层的单位
            if row_list[16] != '高楼层' and row_list[16] != '中楼层' and row_list[16] != '低楼层':    # 统一所在楼层格式
                if int(row_list[16]) <= int(row_list[17]) / 3:
                    row_list[16] = '低楼层'
                elif int(row_list[17]) / 3 < int(row_list[16]) < int(row_list[17]) / 3 * 2:
                    row_list[16] = '中楼层'
                else:
                    row_list[16] = '高楼层'
            row_list.pop(0)    # 不保留房源编号
            filewriter.writerow(row_list)
    print('写入成功')

运行结果

  运行后可得到一个CSV文件，其中共包含处理后的1503条房源数据。

本次学习过程使用的Linux发行版均为Ubuntu 20.04 LTS。

终端使用技巧

1.放大终端界面：Ctrl + Shift + =
2.缩小终端界面：Ctrl + -
3.自动补全：在输入文件、目录或命令的前一部分字母之后，按下Tab键，如果输入的内容没有歧义，则会自动补全；如果还存在其他文件、目录或命令，再按一下Tab键，系统会提示可能存在的命令。

常用命令介绍

)

Linux终端命令格式

终端命令格式

1

command [-options] [parameter]

说明
1.command：命令名，相应功能的英文单词或单词的缩写。
2.-options：选项，可用来对命令进行控制，也可以省略。
3.parameter：传给命令的参数，可以是零个、一个或者多个。
4.[]代表可选。

查阅命令帮助信息

1

command --help

说明：
显示command命令的帮助信息。

1

man command

说明
查阅command命令的使用手册。
man是manual的缩写，是Linux提供的一个手册，包含了绝大部分的命令、函数的详细使用说明。
操作键

目录相关命令

ls

说明
ls是英文单词list的简写，其功能为查看当前文件夹下的内容。
Linux文件和目录的特点
1.Linux文件或目录名称最长可以有256个字符。
2.以.开头的文件为隐藏文件，需要用-a参数才能显示。
3..代表当前目录。
4...代表上一级目录。
ls常用选项

注：ls -l -h也可以写成ls -lh。
))

ls通配符的使用

cd

说明
cd是英文词组change directory的简写，其功能为更改当前的工作目录。
注意
Linux所有的目录和文件名都是大小写敏感的。
命令

相对路径和绝对路径
相对路径：在输入路径时，最前面不是/或~，表示相对当前目录所在的目录位置。
绝对路径：在输入路径时，最前面是/或~，表示从根目录或home目录开始的具体目录位置。

LeetCode 628. 三个数的最大乘积

难度 简单

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例1

1
2

输入: [1,2,3]
输出: 6

示例2

1
2

输入: [1,2,3,4]
输出: 24

注意
1.给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
2.输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

解法 快速排序
语言：C

1
2
3
4
5
6
7
8
9

int* cmp(const void* a, const void* b) {        /* qsort函数的cmp参数，表示升序排序 */
    return *(int*)a - *(int*)b;
}

int maximumProduct(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);    /* 对整型数组进行升序快速排序 */
    return nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3] > nums[0] * nums[1] * nums[numsSize-1]?
           (nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3]) : (nums[0] * nums[1] * nums[numsSize-1]);
}

读完题后，我的第一想法就是对给出的数组进行排序，这样可以把数组中的整型元素按照从小到大的顺序清楚地排列出来，进而方便下一步找出最大乘积。为了尽可能提高排序的效率，这里我使用了stdlib.h头文件中的函数qsort()进行快速排序。在使用qsort()排序之前，我们还应当指定其中的一个参数cmp。具体实现过程请参考上面的代码。
排好顺序后，我们需要列举出所有可能出现的情况：找出的三个数
1.均为负数，乘积为负数；
2.两负一非负，乘积为非负数；
3.一负两非负，乘积为非正数；
4.均为非负数，乘积为非负数。
对于上述情况1和4，我们只需要找出最大的三个数令其相乘，得到的结果即为最大乘积；对于情况2，又会分为两种情况，即涉及最小的两个负数乘积与次大、次次大的两个非负数乘积的大小比较问题；对于情况3，如果真的出现这种情况的话，那么只有一种可能，即该数组的长度为3，最大乘积即为数组所有整型元素之积，也就是数组中最大的三个数的乘积。
经过上述分析，可以总结出，对于一个排好序的整型数组，其中三个元素的最大乘积就是下标为0, 1, numsSize-1对应元素的乘积与下标为numsSize-3, numsSize-2, numsSize-1对应元素的乘积的较大值。

LeetCode 817. 链表组件

难度 中等

给定链表头结点head，该链表上的每个结点都有一个唯一的整型值。
同时给定列表G，该列表是上述链表中整型值的一个子集。
返回列表G中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表G中）构成的集合。

示例1

1
2
3
4
5
6

输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释：
链表中，0和1是相连接的，且G中不包含2，所以[0, 1]是G的一个组件，同理[3]也是一个组件，故返回2。

示例2

1
2
3
4
5
6

输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中，0和1是相连接的，3和4是相连接的，所以[0, 1]和[3, 4]是两个组件，故返回2。

提示
1.如果N是给定链表head的长度，1 <= N <= 10000。
2.链表中每个结点的值所在范围为[0, N - 1]。
3.1 <= G.length <= 10000。
4.G是链表中所有结点的值的一个子集。

解法 数组标记法
语言：C

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int numComponents(struct ListNode* head, int* G, int GSize) {
    bool flag[10000] = {0};
    struct ListNode* node = head;
    int ret = 0;
    for (int i = 0; i < GSize; i++)
        flag[G[i]] = 1;
    while (node) {
        if (flag[node->val]) {
            ret++;
            while (node && flag[node->val])
                node = node->next;
        }
        if (node)
            node = node->next;
    }
    return ret;
}

这道题的思路和上周做过的LeetCode 697. 数组的度的思路非常相似，都是使用了标记数组。首先定义一个布尔型数组flag并且使其所有元素为0，作为标记数组，初始化指向结构体的指针变量node指向单链表头结点head，初始化返回值ret = 0。遍历给定数组G，对于G中的每个元素G[i]，令flag[G[i]] = 1。这样一来，凡是在数组G中出现的值，在标记数组flag中以其为下标的元素值均为1，其余元素值均为0。
遍历单链表，如果flag[node->val]的值为1，ret自加1，并且遍历至flag[node->val] = 0或单链表尾结点为止；如果flag[node->val]的值为0，令node = node->next，继续遍历。重复这个流程，直到单链表遍历结束，此时的ret即为所求结果。

采用布尔型数组而非整型数组作为标记数组，可以降低内存消耗。

LeetCode 378. 有序矩阵中第K小的元素

难度 中等

给定一个n × n矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个不同的元素。

示例

1
2
3
4
5
6
7
8

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

提示
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n²。

解法一 将矩阵转化为一维数组并排序
语言：Python 3

1
2
3
4
5

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        matrix = [i for j in matrix for i in j]
        matrix = sorted(matrix)
        return matrix[k - 1]

解法二 二分查找法
语言：C

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

int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k) {
    int left = matrix[0][0], right = matrix[matrixSize - 1][matrixSize - 1];
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(matrix, matrixSize, mid, k)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int check(int** matrix, int matrixSize, int mid, int k) {
    int num = 0;
    int i = matrixSize - 1, j = 0;
    while (i >= 0 && j < matrixSize) {
        if (matrix[i][j] <= mid) {
            j++;
            num += i + 1;
        } else {
            i--;
        }
        if (num >= k)
            return 0;
    }
    return 1;
}

依据题意，矩阵里的元素是自左上至右下递增的，即matrix[0][0]为最小值，记为left，matrix[n-1][n-1]为最大值，记为right。这样，所要查找的元素x必定满足left ≤ x ≤ right。
与此同时，我们可以发现，任取一个数mid，mid满足left ≤ mid ≤ right，都有如下性质：矩阵中不大于mid的数全部分布在矩阵的左上角，大于mid的数全部分布在矩阵的右下角。
下面借用一下LeetCode官方题解给出的图来帮助理解，取mid = 8，则矩阵被一条锯齿线分为左上和右下两个部分。

将起始位置设置为matrix[n-1][0]，初始化计数变量num = 0，设当前位置为matrix[i][j]。若matrix[i][j] ≤ mid，则将当前所在列的不大于mid的数的数量（即i + 1）累加到计数变量num中，并向右移动（即j自加1）；否则，向上移动（即i自减1）。这样，只需要自下而上地沿着锯齿线走一遍，即可统计出矩阵中有多少个数字不大于mid了。
计算矩阵中有多少数不大于mid，若数量不小于k，则所要查找的元素x不大于mid；若数量小于k，则所要查找的元素x大于mid。二分查找结束后，即可找出x。

LeetCode 697. 数组的度

难度 简单

给定一个非空且只包含非负数的整数数组nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与nums拥有相同大小的度的最短连续子数组，返回其长度。

示例1

1
2
3
4
5
6
7

输入: [1, 2, 2, 3, 1]
输出: 2
解释: 
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

示例2

1
2

输入: [1,2,2,3,1,4,2]
输出: 6

注意
nums.length在1到50,000区间范围内。
nums[i]是一个在0到49,999范围内的整数。

解法 HashMap
语言：C

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

int findShortestSubArray(int* nums, int numsSize) {
    int count[50000] = {0};
    int left[50000] = {0};
    int right[50000] = {0};
    int degree = 0;                             /* 初始化数组的度 */
    int min = numsSize;                         /* 初始化最短连续子数组的长度 */
    for (int i = 0; i < numsSize; i++) {
        count[nums[i]]++;
        if (count[nums[i]] == 1)                /* 首次出现记录左值 */
            left[nums[i]] = i;
        right[nums[i]] = i;                     /* 记录右值 */
        if (count[nums[i]] > degree)            /* 记录数组的度 */
            degree = count[nums[i]];
    }
    for (int i = 0; i < numsSize; i++)
        if (count[nums[i]] == degree)
            min = right[nums[i]] - left[nums[i]] + 1 < min ? (right[nums[i]] - left[nums[i]] + 1) : min;
    return min;
}

首先定义三个数组count, left, right。其中count的作用是计数，以给定数组nums的元素nums[i]作为下标，其对应的元素值即为nums[i]的值在数组nums中出现的次数。left和right分别记录nums[i]的值第一次出现和最后一次出现时所对应的下标i，我将其称之为元素nums[i]对应的的左值和右值。接下来初始化数组的度degree = 0，初始化最短连续子数组的长度min = numsSize。
对nums数组进行遍历，记录每个元素出现的次数和其对应的左右值。在记录左右值的时候要注意，如果某个元素是第一次记录，则要记录左值和右值；否则，只刷新右值即可，左值不需要更改。每遍历完一个元素，刷新一次数组的度，即如果count[nums[i]] > degree，令degree = count[nums[i]]。
最后，遍历count数组，如果count[nums[i]]与degree相等，则取right[nums[i]] - left[nums[i]] + 1和min的较小者赋值给min。这样，完全遍历count之后得到的min即为本题所求。

任务需求

  在贝壳租房网站（这里我选择的城市是天津）爬取50页房源信息，包括房源编号、所在城市、所在区县、所在街道或地区、小区名称、面积、朝向、月租、计费方式、室、厅、卫、入住、租期、看房、所在楼层、总楼层、电梯、车位、用水、用电、燃气、采暖等信息。将信息写入CSV文件保存，以备后续任务使用。

对任务需求的分析

  这是一个关于爬虫的任务，那么一些爬虫常用的模块（如requests, bs4等）是必不可少的。
  需求中有提到“爬取50页数据”，看到这里很自然地就会想到使用循环来解决。打开贝壳租房网，翻页观察URL的变化并寻找规律，如下图所示：


  不难发现，URL的“模板”是https://tj.zu.ke.com/zufang/pg[对应的页码]/#contentList。那么，爬取50页数据就可以使用for循环来解决，循环变量的范围设置为range(1, 51)，将其作为页码拼接到“模板”URL中，对这些URL分别发起请求爬取数据即可。
  接下来的问题是，如何找到某一个房源的具体信息呢？
  我们点击右键检查元素，进入网页的HTML源代码查看，会发现一个名为data-house_code的值。大胆猜测一下，它和房源具体信息页的URL存在一些关联。

  点击房源进入详情页，我们发现URL中恰好包含前面看到的data-house_code值。事实上，这个值正是与房源一一对应的唯一编号。

  最后就是对HTML代码抽丝剥茧找出所需要的数据并写入CSV文件了。这里可以使用bs4来解析HTML源代码，也可以使用正则表达式或者XPath解析。我使用的是bs4和正则表达式结合解析HTML的方法。详细的实现过程可以参考下面的Python代码。

Python源代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


import csv
import re

from bs4 import BeautifulSoup
import requests


head = ['房源编号', '所在城市', '所在区县', '所在街道或地区', '小区名称', '面积', '租赁方式', '朝向', '月租', '计费方式', '室', '厅',
        '卫', '入住', '租期', '看房', '所在楼层', '总楼层', '电梯', '车位', '用水', '用电', '燃气', '采暖']    # 写入文件的标题行
headers = {'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Firefox/78.0'}
with open('TianjinRentHouseInfo.csv', 'w', newline='') as csv_out_file:
    filewriter = csv.writer(csv_out_file)
    filewriter.writerow(head)
    for page in range(1, 51):
        url = 'https://tj.zu.ke.com/zufang/pg' + str(page) + '/#contentList'
        response = requests.get(url=url, headers=headers)
        page_text = response.text
        soup = BeautifulSoup(page_text, 'html.parser')
        div_list = soup.find_all(class_='content__list--item')
        codes = []  # 存储房源编号的列表
        areas = []  # 存储房源地区的列表
        for div in div_list:
            code = re.search(r'data-house_code="(.*?)" ', str(div)).group()[17:-2]
            codes.append(code)
        p_list = soup.find_all(class_='content__list--item--des')
        for p in p_list:
            a_list = p.find_all('a')
            area = []
            for i in range(len(a_list)):
                a_text = a_list[i].text
                area.append(a_text)
            areas.append(area)
        for i in range(len(codes)):
            info = []  # 存储房源信息的列表
            info.extend([codes[i], '天津'] + areas[i])
            url = 'https://tj.zu.ke.com/zufang/' + codes[i] + '.html'
            response = requests.get(url=url, headers=headers)
            page_text = response.text
            soup = BeautifulSoup(page_text, 'html.parser')
            ul_text = soup.find('ul', class_='content__aside__list').text
            div_text = soup.find('div', class_='content__aside--title').text
            S = re.search(r' (.*?)㎡', ul_text).group()[1:]    # 面积
            lease = re.search(r'租赁方式：(.*?)\n', ul_text).group()[5:-1]    # 租赁方式
            aspect = re.search(r'朝向楼层：(.*?) ', ul_text).group()[5:-1]    # 朝向
            price = re.search(r'([0-9]*?)元/月', div_text).group()    # 月租
            try:
                charge_mode = re.search(r'\((.*?)\)', div_text).group()[1:-1]    # 计费方式
            except AttributeError:
                charge_mode = 'None'
            room = re.search(r'([0-9*?])室', ul_text).group()    # 几室
            hall = re.search(r'([0-9*?])厅', ul_text).group()    # 几厅
            toilet = re.search(r'([0-9*?])卫', ul_text).group()    # 几卫
            info.extend([S, lease, aspect, price, charge_mode, room, hall, toilet])
            div = soup.find('div', class_='content__article__info')
            ul_list = div.find_all('ul')
            ul_text = ''
            for ul in ul_list:
                ul_text += ul.text
            check_in = re.search(r'入住：(.*?)\n', ul_text).group()[3:-1]    # 入住
            term = re.search(r'租期：(.*?)\n', ul_text).group()[3:-1]    # 租期
            see_house = re.search(r'看房：(.*?)\n', ul_text).group()[3:-1]    # 看房
            floor = re.search(r'楼层：(.*?)/', ul_text).group()[3:-1]    # 所在楼层
            total_floor = re.search(r'/(.*?)\n', ul_text).group()[1:-1]    # 总楼层
            lift = re.search(r'电梯：(.*?)\n', ul_text).group()[3:-1]    # 电梯
            stall = re.search(r'车位：(.*?)\n', ul_text).group()[3:-1]    # 车位
            water = re.search(r'用水：(.*?)\n', ul_text).group()[3:-1]    # 用水
            elec = re.search(r'用电：(.*?)\n', ul_text).group()[3:-1]    # 用电
            gas = re.search(r'燃气：(.*?)\n', ul_text).group()[3:-1]    # 燃气
            heating = re.search(r'采暖：(.*?)\n', ul_text).group()[3:-1]    # 采暖
            info.extend([check_in, term, see_house, floor, total_floor, lift, stall, water, elec, gas, heating])
            print(info[0], '写入成功')
            filewriter.writerow(info)

  在写代码的过程中我遇到了一个问题，在用正则表达式匹配“计费方式”的时候，会有匹配不到结果而报AttributeError错误的情况出现。经过排查，我发现有的房源详情页并不存在“计费方式”的字样，自然无法匹配。可以使用try-except结构来解决这个问题，详情请参考上述代码第50-53行。

运行结果

  运行后可得到一个CSV文件，其中共包含1503条房源数据。

前言

  相信有很多小伙伴跟我一样，觉得Windows的原生命令行工具具有很多缺点：传统的黑底白字（Windows PowerShell则是蓝底白字）极不美观，复制文本不方便，不支持多Tab页导致多窗口管理不便，不支持文字颜色区分等等。

  当我们看到网上其他人使用一些其他的命令行工具高效工作的时候，心里是否有一些小羡慕呢？接下来的教程，将带你手把手地打造一个属于自己的美观的命令行工具。
  在教程之前先来放一张效果图吧：

Step 1：安装Fluent Terminal

  这一步很简单。打开Microsoft Store搜索“Fluent Terminal”，点击安装即可。
  这里我已经安装过了，所以显示的是“启动”按钮。大家只要点击“获取”然后“安装”就可以啦。
  为了方便后续的使用，我建议把Fluent Terminal作为一个磁贴固定到“开始”屏幕。打开Fluent Terminal如下图所示：

  大家在安装好之后可以点击左上方的按钮进行界面的自定义设置，比如设置字体、字号、背景透明度等等。

Step 2：安装Cmder

  Cmder是一个功能强大的命令行工具，它相比原生的命令行工具具有很多优点（可能是因为原生的命令行工具压根没有什么优点）。举几个例子：Cmder支持多Tab页，方便多窗口的管理；把conemu，msysgit和clink打包在一起，让你无需配置就能使用一个真正干净的Linux终端；自带git-for-windows，可以使用常见的Unix命令等等。
  首先我们打开Cmder的官网，并找到Download。

  我们发现在Download里面有两个按钮，左边的Download Mini是不带git-for-windows的，所以文件大小会比右边的Download Full小很多。这里我下载的是右侧的。温馨提示，下载的速度会有一点点慢，需要耐心等候。
  下载之后我们把Cmder的压缩包解压到任意一个目录。这里需要注意的一点是：目录必须是纯英文的，不能带有特殊字符和空格。我把它解压到了D盘，大家可以根据自己的实际情况选择解压的位置。

  之后我们就可以双击Cmder.exe运行了。

Step 3：配置Cmder的环境变量

  首先设置CMDER_ROOT。右键此电脑，点击“属性”，再点击“高级系统设置”，选择“环境变量”。点击用户变量下方的“新建”，输入变量名为CMDER_ROOT，变量值为Cmder压缩包刚刚解压的路径。

  接下来，我们使用同样的方法新建用户变量ConEmuDir，如下图所示：

  下一步，双击用户变量中的Path，新建%CMDER_ROOT%。

  到此，我们的环境变量就全部配置完成了。

Step 4：添加Cmder到右键菜单

  以管理员身份运行Windows PowerShell，输入cmd，定位到Cmder.exe所在文件夹，再输入命令：Cmder.exe /REGISTER ALL。
  运行结束后，我们在任意文件夹下点击右键，如果发现有“Cmder Here”就成功了。

Step 5：解决中文乱码问题

  打开Cmder，点击右下角按钮，选择“Settings”。
  定位到Startup下的Environment标签，在框中输入以下内容：

1
2
3

set LANG=zh_CN.UTF-8
set LC_ALL=zh_CN.utf8
chcp utf-8

  输入之后如下图所示，点击右下角的“Save Settings”按钮保存设置。

Step 6：修改提示符符号

  Cmder的默认提示符为“λ”，据说可能导致某些bug。我们可以将其修改为自定义的符号，这里我将其修改为“$”。
  我们需要修改两个文件。第一个文件是%CMDER_ROOT%\vendor\clink.lua文件，我们找到local lambda = "λ"这一行，将其修改为local lambda = "$"。第二个文件是%CMDER_ROOT%\vendor\git-for-windows\etc\profile.d\git-prompt.sh文件，找到PS1="$PS1"'λ ' # prompt: always λ这一行，将其修改为PS1="$PS1"'$ '。

Step 7：将Fluent Terminal与Cmder结合

  打开Fluent Terminal，点击左上角的按钮，点击“设置”，进入设置页面。
  选择“配置文件”，点击“新建”，按照下图填写即可。

  将Cmder设为默认（这个选项在上图中的右上方），然后重新打开Fluent Terminal，可以看到已经生效了。

写在最后

  以上就是基于Fluent Terminal和Cmder打造一个美观的Windows命令行工具的教程了。大家还可以根据自己的喜好设置一下界面的主题，使其变得更加美观。
  另外需要说明的一点是，添加到右键菜单里的“Cmder Here”还是原来的Cmder界面，如果我们想使用上面配置好的界面，需要打开Fluent Terminal。