leetcode 540. 有序数组中的单一元素

题目

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

点这里做题

1
2
3
4
5
6
7
示例一：
nums = [1,1,2,3,3,4,4,8,8]
输出：2

示例二：
nums = [3,3,7,7,10,11,11]
输出：10
  • 难度：Medium

思路

观察可以发现，在单一元素的前半段，偶数下标index和index+1、奇数下标index和index-1位置的元素相等，而在后半段则不然，可以根据此进行二分

这里对奇偶下标的处理，可以根据index^1得到，对于偶数就是+1，对于奇数就是-1

  • 技能点：二分

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while(left < right){
            int mid = left+((right-left)>>1);
            // mid为偶数时，判断nums[mid] nums[mid+1]
            // mid为奇数时，判断nums[mid] nums[mid-1]
            // 利用异或的性质 mid^1即为需要比较的
            if(nums[mid] == nums[mid^1]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return nums[left];
    }
};

展开全文 >>

查找

查找的基本概念

  1. 查找：在数据集合中寻找满足某种条件的数据元素的过程
  2. 查找表：用于查找的数据集合。一般进行操作有
    1. 查询某个特定元素是否在查找表中
    2. 检索满足条件的某个特定的数据元素的各种属性
    3. 在查找表中插入一个数据元素
    4. 从查找表中删除某个数据元素
  3. 静态查找表：查找表的操作只涉及上述1、2操作。对应的涉及3、4操作的为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有BST的查找、散列查找等
  4. 关键字：数据元素中唯一标识该元素的某个数据项的值。基于关键字的查找必须唯一
  5. 平均查找长度ASL：平均一次查找中需要比较的关键字次数。是衡量查找算法效率的主要因素

顺序查找和折半查找

顺序查找

又称线性查找，适用于顺序表和链表

一般线性表的顺序查找

基本思想：从线性表的一端开始，逐个检查关键字

王道考研书给出的代码实现，这个哨兵个人感觉有点脱裤子放屁

1
2
3
4
5
6
7
8
9
10
11
// 表的数据结构
typedef struct{
    ElemType *elem; // 元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen;   // 表的长度
}SSTable;
// 顺序查找
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0] = key;   // 哨兵
    for(int i=ST.TableLen; ST.elem[i]!=key; --i){}
    return i;
}

有序表的顺序查找

为了减少查找失败时的ASL

基本思想：查找到有元素小于key和有元素大于key，则根据有序，可以直接判定查找失败

折半查找

又称二分查找，仅适用于有序的顺序表

1
2
3
4
5
6
7
8
9
10
11
12
int Binary_Search(SeqList L, ElemType key){
    int left = 0, right = L.TableLen-1;
    while(left < right){
        int mid = left+((right-left)>>1);
        if(L.elem[mid] < key){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    return L.elem[left] == key ? left : -1;
}

时间复杂度：O(log(2, n))

折半查找不适用于链式存储结构

折半查找对应的判定树是一棵平衡二叉树

分块查找

又称索引顺序查找，结合了顺序查找和折半查找的优点

基本思想：将查找表分为若干子块，子块内可以无序，但子块间必须有序

展开全文 >>

leetcode 1189. 气球的最大数量

题目

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。

字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。

1
2
3
4
5
6
7
示例1：
输入：text = "nlaebolko"
输出：1

示例2:
输入：text = "loonbalxballpoon"
输出：2
  • 难度：EASY

思路

简单的模拟即可，扫描一遍text，记录b a l o n的数量

扫描完之后，根据这五个字母的数量，注意组成balloon需要两个l和o，因此需要/2，取最小值即为答案

  • 技能点：模拟

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxNumberOfBalloons(string text) {
        vector<int> cnt(5);
        for (auto & ch : text) {
            if (ch == 'b') {
                ++cnt[0];
            } else if (ch == 'a') {
                ++cnt[1];
            } else if (ch == 'l') {
                ++cnt[2];
            } else if (ch == 'o') {
                ++cnt[3];
            } else if (ch == 'n') {
                ++cnt[4];
            }
        }
        cnt[2] /= 2;        // l
        cnt[3] /= 2;        // o
        return *min_element(cnt.begin(), cnt.end());
    }
};

展开全文 >>

排序

基本概念

定义

重新排列表中的元素，使其满足元素按照关键字有序的过程

排序算法稳定性：假设待排序表中，两个元素R1和R2，对应关键字Key1==Key2，在使用某种排序算法后，仍保持原先的相对顺序，则该排序算法稳定；否则不稳定。（算法是否稳定并不衡量排序算法的优劣，只是描述性质

根据数据元素是否完全在内存中，可以将排序算法分为内部排序和外部排序

并非所有排序都要基于元素之间的比较，例如基数排序

例题

对n个数进行基于比较的排序，需要进行至少「log(2, n!) 次关键字之间的比较

插入排序

基本思想：将每一个待排序元素插入前面已排序好的子序列，直到排序完成。

可以引申出：直接插入排序、折半插入排序和希尔排序

直接插入排序

算法流程：

  1. 找出L(i)在L[1…i-1]中的插入位置
  2. 进行插入

代码：

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
// 逐个交换版本
void Insert_Sort1(int nums[], int len){
    for(int i=1;i<len;++i){
        // 将nums[i]插入前面排好的序列
        for(int j=i;j>0;--j){
            // 如果比前面的元素小，就前移
            if(nums[j-1]>nums[j]){
                std::swap(nums[j-1], nums[j]);
            }else{
                break;
            }
        }
    }
}
// 整体后挪版本
void Insert_Sort2(int nums[], int len){
    // 在nums[0]位置设置哨兵，存储当前处理的元素，在移动数组的过程中就不怕被覆盖
    for(int i=2;i<=len;++i){
        // 如果当前元素需要排序
        if(nums[i]<nums[i-1]){
            nums[0] = nums[i];  // 哨兵
        }
        // 插入位置后的序列往后面挪动
        int j=i-1;
        for(;nums[0]<nums[j];--j){
            nums[j+1] = nums[j];
        }
        nums[j+1] = nums[0];
    }
}

时间复杂度：O(n^2)

空间复杂度：O(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
void Insert_Sort3(int nums[], int len){
    // 在nums[0]位置设置哨兵，存储当前处理的元素，在移动数组的过程中就不怕被覆盖
    for(int i=2;i<=len;++i){
        if(nums[i]<nums[i-1]){
            // 找第一个大于等于nums[i]的元素
            nums[0] = nums[i];  // 哨兵
            int left = 1, right = i-1;
            // 左闭右开 向下取整
            while(left < right){
                int mid = left+((right-left)>>1);
                if(nums[mid] < nums[i]){
                    ++left;
                }else{
                    --right;
                }
            }
            // 整体右移
            for(int j=i-1;j>=left;--j){
                nums[j+1] = nums[j];
            }
            nums[left] = nums[0];
        }
    }
}

时间O(n^2)

空间O(1)

稳定

希尔排序

希尔排序，又称缩小增量排序。

把相隔d增量的元素记录为一个子表，在各组内进行直接插入排序。不断缩小步长，直到步长为1，此时直接插入排序。因为有较好的局部有序性，所有可以很快得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Shell_Sort(int nums[], int len){
    // nums[0]为暂存单元
    // dk为步长
    for(int dk=len/2;dk>0;dk/=2){
        for(int i=dk+1;i<=len;i++){
            // 如果需要排序
            if(nums[i]<nums[i-dk]){
                nums[0]=nums[i];
                int j=i-dk;
                // 寻找插入位置
                for(;j>0 && nums[0]<nums[j];j-=dk){
                    nums[j+dk] = nums[j];
                }
                nums[j+dk] = nums[0];
            }
        }
    }
}

时间复杂度：较难分析，n在某个特定区间内为O(n^1.3)，最坏时间复杂度为O(n^2)

空间复杂度：O(1)

不稳定

适用性：仅适用于线性表为顺序存储的情况

交换排序

包括冒泡排序和快速排序

冒泡排序

基本思想：从后往前（或者从前往后）两两比较相邻元素的值，若为逆序，则交换他们，知道序列比较完，称为一次冒泡，结果是最小的元素交换到待排序序列的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Bubble_Sort(int nums[], int len){
    for(int i=0;i<len-1;++i){
        bool flag = false;      // 记录是否发生过交换
        for(int j=len-1;j>i;--j){
            // 冒泡
            if(nums[j]<nums[j-1]){
                std::swap(nums[j-1], nums[j]);
                if(!flag)   flag = true;
            }
        }
        // 没有发生过swap，说明已经有序
        if(!flag)    return;
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定

快速排序

思想：基于分治。

  1. 在待排序表中任意选取一个元素pivot，通过一趟排序，将待排序表分为独立的两部分L和R，L中所有元素小于pivot，R中所有元素大于pivot，
  2. 此时pivot位于有序数组的最终位置上
  3. 递归处理L和R。直到每部分内都只有一个元素

Partition过程

Partition将待排序表划分。快速排序的性能主要取决于此。

此处以《数据结构》王蔚敏版本的做法，以表中第一个元素作为枢轴pivot，进行划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int partition(int nums[], int left, int right){
    int pivot = nums[left];
    while(left < right){
        // 将小于pivot的元素移到左边
        while(left<right && nums[right]>=pivot){
            --right;
        }
        nums[left] = nums[right];
        // 将大于pivot的元素移到右边
        while(left<right && nums[left]<=pivot){
            ++left;
        }
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

类似荷兰国旗问题的partition

1
2
3
4
5
6
7
8
9
10
11
int partition(int nums[], int left, int right){
    int pivot = nums[left];     // 选取第一个元素作为枢轴
    int leftBoard = left-1;     // 处理好的左半边的边界
    for(int i=left;i<=right;++i){
        if(nums[i]<=pivot){
            std::swap(nums[i], nums[++leftBoard]);
        }
    }
    std::swap(nums[left], nums[leftBoard]); // 枢轴放到正确的位置上
    return leftBoard;
}

递归处理部分

1
2
3
4
5
6
7
8
9
void QuickSort(int nums[], int left, int right){
    // 表长大于1时才需要快排
    if(left < right){
        int pivotPos = partition(nums, left, right);
        // 递归处理左右子表
        QuickSort(nums, left, pivotPos-1);
        QuickSort(nums, pivotPos+1, right);
    }
}

空间复杂度：O(log(2, n)) 递归需要用栈

时间复杂度：O(log(2, n))

稳定性：不稳定

习题

  • 2/ 编写双向冒泡排序算法，在正反两个方向交替进行扫描：即第一趟把最大的关键字放在序列最后，第二趟把最小的关键字放在最前，如此往复

思路：用一个times变量控制扫描方向

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
void _02_BiDirection_bubble_sort(int nums[], int len){
    int times = 1;
    // i j 记录待排序的序列两端
    int i = 0, j = len-1;
    while(i != j){
        // 正向冒泡
        if(times % 2 == 1){
            for(int k=i;k<j;++k){
                if(nums[k]>nums[k+1]){
                    std::swap(nums[k], nums[k+1]);
                }
            }
            --j;
        }
        // 反向冒泡
        else{
            for(int k=j;k>i;--k){
                if(nums[k]<nums[k-1]){
                    std::swap(nums[k], nums[k-1]);
                }
            }
            ++i;
        }
        ++ times;
    }
}
  • 3/ 线性表按顺序存储，每个元素是都不相同的整形，要求将所有奇数移动到所有偶数前面

思路：荷兰国旗问题的变种，将所有奇数移动就可以

1
2
3
4
5
6
7
8
void _03_func(int nums[], int len){
    int left = 0;   // 表示已经整理好的左边序列的末尾后一位
    for(int i=0;i<len;++i){
        if(nums[i] % 2 == 1){
            std::swap(nums[i], nums[left++]);
        }
    }
}
  • 5/ 在数组中找出第k小的元素

思路：先快排，然后直接取出

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
// partition
int partition(int nums[], int left, int right){
    int pivot = nums[left];
    while(left<right){
        while(left<right && nums[right]>=pivot){
            --right;
        }
        nums[left] = nums[right];
        while(left<right && nums[left]<=pivot){
            ++left;
        }
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}
// QuickSort
void QuickSort(int nums[], int left, int right){
    if(left<right){
        int pivotPos = partition(nums, left, right);
        QuickSort(nums, left, pivotPos-1);
        QuickSort(nums, pivotPos+1, right);
    }
}
// solution
int _05_find_k(int nums[], int len, int k){
    QuickSort(nums, 0, len-1);
    return nums[k];
}
  • 6/ 荷兰国旗问题：设有一个仅有红白蓝三种颜色的条块组成的序列，编写算法使序列按照红、白、蓝的顺序排好，即排成荷兰国旗图案

思路：

  1. 假设0代表红，1代表白，2代表蓝。
  2. 只要将0和2排到数组前面和后面，就完成题意
  3. 设置left表示左边排好序的边界，right表示右边的边界。进行一遍扫描，交换
1
2
3
4
5
6
7
8
9
10
11
12
13
void _05_Holland_Flag(int nums[], int len){
    int left = -1, right = len;     // 两个边界
    int index = 0;      // 扫描数组变量
    while(index < right){
        if(nums[index] == 0){
            std::swap(nums[index++], nums[++left]);
        }else if(nums[index] == 2){
            std::swap(nums[index], nums[--right]);
        }else{
            ++index;
        }
    }
}
  • 6/ （2016统考真题）已知n(n>=2)个正整数构成的集合A，将其划分为两个不相交子集A1和A2，元素个数为n1和n2，子集内元素和为S1和S2，设计一个高效的划分算法，满足|n1-n2|最小并且|S1-S2|最大

思路：贪心思想，|n1-n2|最小，要求平分；|S1-S2|最大，要求A1内元素都小，A2内元素都大。因此，类似快排，选取一个枢轴，他应当排序后位于数组中间

  1. 选取一个枢轴 将其放到正确位置
  2. 正确位置为len/2-1。
  3. 如果枢轴位置刚好等于len/2-1，那就计算答案
  4. 如果小于len/2-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
26
27
28
29
30
31
32
33
34
35
36
int _06_func(int nums[], int len){
    int left = 0, right =len-1, pos = len/2;
    bool flag = true;
    while(flag){
        int pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] >= pivot){
                -- right;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivot){
                ++ left;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        if(left == pos-1)   flag = false;       // 如果pivot位于pos，划分成功
        else{
            if(left < pos-1){
                left += 1;
                right = len-1;
            }else{
                right -= 1;
                left = 0;
            }
        }
    }
    int sum1 = 0, sum2 = 0;
    for(int i=0;i<pos;++i){
        sum1 += nums[i];
    }
    for(int i=pos;i<len;++i){
        sum2 += nums[i];
    }
    return sum2-sum1;
}

选择排序

基本思想：每一趟排序，在后面的待排序序列中找到一个最小值，放到排好序序列的后面。

简单选择排序

每一趟在L[i…n]中找到最小值，和L(i)进行交换

1
2
3
4
5
6
7
8
9
10
11
12
void Select_Sort(int nums[], int len){
    for(int i=0;i<len-1;++i){
        int minPos=i;   // 最小值所在的下标
        for(int j=i+1;j<len;++j){
            if(nums[j] < nums[minPos]){ // 更新最小值
                minPos = j;
            }
        }
        if(minPos != i)
            std::swap(nums[i], nums[minPos]);
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

堆排序

堆的定义

n个关键字序列L[1…n]满足以下条件可以成为堆

  1. L(i)>=L(2i) && L(i)>=L(2i+1) 或者
  2. L(i)<=L(2i) && L(i)<=L(2i+1)

满足条件1称为大根（顶）堆，满足条件2称为小根（顶）堆

堆可以视为一棵完全二叉树

以大顶堆实现为例，排序结果为从小到大。区别于王道考研书，这里数组下标从0开始计算

堆化

堆化是自上而下的

对于每一个节点，比较自己和孩子中较大的那个，不断下沉

1
2
3
4
5
6
7
8
9
10
11
12
13
void heapify(int nums[], int len, int k){
    for(int i=2*k+1;i<len;i=i*2+1){
        // 右孩子存在并且比左孩子大，则选取左孩子
        if(i+1 < len && nums[i+1] > nums[i]){
            i = i+1;
        }
        if(nums[k] > nums[i])   break;  //
        else{
            std::swap(nums[k], nums[i]);
            k = i;
        }
    }
}

建立堆

建立堆是自下而上的

对于每一个节点，比较自己和父节点，不满足堆的性质则进行交换

1
2
3
4
5
void BuildHeap(int nums[], int len){
    for(int i=(len-2)/2;i>=0;--i){
        heapify(nums, len, i);
    }
}

堆排序

堆排序则是：

  1. 建立堆
  2. 每次取出堆顶元素（待排序序列中的最大值），与后面排序完成的序列前一位进行交换。然后对新的堆顶元素堆化
  3. 当堆只有一个元素时，堆排序完成
1
2
3
4
5
6
7
void Heap_Sort(int nums[], int len){
    BuildHeap(nums, len);
    for(int i=len-1;i>0;--i){
        std::swap(nums[0], nums[i]);
        heapify(nums, i, 0);    // 调整新的堆顶
    }
}

时间复杂度：O(n*log(2, n))

空间复杂度：O(1)

稳定性：不稳定

堆排序适用于关键字较多的情况，例如10000个数据中取最小的100个，可以用大小为100的堆实现

归并排序和基数排序

归并排序

不同于之前的基于比较、选择等排序，归并排序的基本思想是：将两个或两个以上的有序表组合成一个新的有序表。

Merge 操作

Merge 将两个表合并成一个有序表，需要借助一个辅助数组来完成。双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Merge(int nums[], int left, int mid, int right){
    int helper[right-left+1];   // 辅助数组
    int index1 = left, index2 = mid+1, index3 = 0;  // 三指针
    while(index1 <= mid && index2 <=right){
        helper[index3++] = nums[index1]<nums[index2] ? nums[index1++] : nums[index2++];
    }
    // 剩余的表直接复制
    while(index1 <= mid)    helper[index3++] = nums[index1++];
    while(index2 <= right)    helper[index3++] = nums[index2++];
    // 辅助数组搬到原数组
    for(int i=0;i<right-left+1;++i){
        nums[left+i] = helper[i];
    }
}

MergeSort 操作

MergeSort递归做法，类似树的后序遍历。

1
2
3
4
5
6
7
8
void MergeSort(int nums[], int left, int right){
    if(left < right){
        int mid = left+((right-left)>>1);
        MergeSort(nums, left, mid);         // 让左边有序
        MergeSort(nums, mid+1, right);      // 让右边有序
        Merge(nums, left, mid, right);      // 合并成一个大的有序
    }
}

时间复杂度：O(n*log(2, n))

空间复杂度：O(n) 来自辅助数组和递归函数栈

稳定性：稳定

基数排序

展开全文 >>

链表

线性表的链式表示

单链表的定义

对于每个链表节点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针

1
2
3
4
typedef struct LNode{
    ElemType data;  // 数据域
    LNode *next;    // 指针域
}LNode, *LinkList;

单链表可以解决顺序表需要大量连续存储空间的缺点，但附加的指针域存在浪费空间的缺点，也无法随机存取

通常用头指针标识一个单链表

为了操作方便，在单链表前可以增加一个头节点，可以使空表和非空表的操作得到统一，链表第一个节点和其他节点的操作也得到统一

单链表上基础操作的实现

  • 头插法建立单链表

    新节点插入链表表头。最后读入数据的顺序和生成的链表的元素的顺序是相反的

1
2
3
4
5
6
void HeadInsert(LinkList &L){
    LNode* node = (LNode*) malloc(sizeof(LNode));
    // 关键
    node->next = L->next;
    L->next = node;
}

  • 尾插法建立单链表

    新节点插入链表表尾，最后读入数据的顺序和生成的链表的元素的顺序相同

1
2
3
4
5
6
7
8
9
void TailInsert(LinkList &L){
    LNode* node = new LNode;
    // tail为尾指针，指向链表L的最后一个元素
    node->data = /* you want */;
    node->next = nullptr;
    // 关键
    tail->next = ndoe;
    tail = node;
}

  • 按序号查找节点

    不断沿着next域找到第i个节点即可

1
2
3
4
5
6
7
8
9
LNode* GetElem(LinkList& L, int i){
    int j = 1;
    LNode p = L;
    while(j < i){
        if(!p)  return p;   // 链表长度小于i，返回nullptr
        p = p->next;
    }
    return p;
}

  • 按值查找节点

    从链表头开始查找，找到满足要求的节点值则返回

1
2
3
4
5
6
7
LNode* LocateElem(LinkList& L, ElemType e){
    LNode* p = L->next; // 假设带头节点
    while(p && p->data != e){
        p = p->next;
    }
    return p;
}

  • 插入节点

    假设将节点s插入p之后

    扩展：O(1)前插？

1
2
3
4
5
6
7
8
// 实现后插的代码
s->next = p->next;
p->next = s;

// 实现O(1)前插
s->next = p->next;
p->next = s;
swap(s->data, p->data); // 交换节点的值

  • 删除节点

    假设欲删除节点p的后继节点

    扩展：O(1)删除当前节点？

1
2
3
4
5
6
7
8
9
10
// 实现删除后继节点的代码
auto q = p->next;
p->next = q->next;
free(q);

// 删除当前节点的代码
auto q = p->next;
auto data = q->data;
p->next = q->next;
p->data = data; // 交换节点的值

展开全文 >>

leetcode 1020. 飞地的数量

题目

给一个大小为m*n的二进制矩阵grid，0表示海洋，1表示陆地

一次移动指：从一个陆地单元格上走到另一个相邻陆地单元格或者跨越grid的边界

返回网格中无法在任意次数移动中离开网格边界的陆地单元格的数量

思路

读题可以知道，要求的就是被0包围起来的1的数量。因此可以对四个边界上的1做BFS/DFS，将不满足要求（即可以跨越边界）的1变为0。再统计剩下的1的数量。

以下给出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
26
27
28
29
30
31
32
33
34
35
class Solution {
    // 深度优先遍历，将一整块1变为0
    int dx[4]{0, 0, -1, 1}, dy[4]{1, -1, 0, 0};
    void dfs(vector<vector<int>>& grid, int x, int y){
        int n=grid.size(), m=grid[0].size();
        grid[x][y]=0;
        for(int i=0;i<4;++i){
            int newx=x+dx[i], newy=y+dy[i];
            if(newx>=0 && newx<n && newy>=0 && newy<m && grid[newx][newy]==1){
                dfs(grid, newx, newy);
            }
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        // 处理边界的1
        for(int j=0;j<m;++j){
            if(grid[0][j]==1)   dfs(grid, 0, j);
            if(grid[n-1][j]==1) dfs(grid, n-1, j);
        }
        for(int i=1;i<n-1;++i){
            if(grid[i][0]==1)   dfs(grid, i, 0);
            if(grid[i][m-1]==1) dfs(grid, i, m-1);
        }
        // 统计答案
        int ans=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(grid[i][j]==1)   ++ans;
            }
        }
        return ans;
    }
};

展开全文 >>

树

树的基本概念

树是n个节点的有限集合，是一种递归的数据结构

树的根节点没有前驱，此外，所有节点有且仅有一个前驱

基本术语

  • 祖先节点：除自身外，根节点到该节点路径上的节点均为自身的祖先节点
  • 节点的度：节点的孩子数
  • 树的度：树中节点度数最大值
  • 分支节点：节点度>0
  • 叶子节点：节点度=0
  • 节点的深度：根节点为1，依次往下
  • 节点的高度：和深度相反，从下往上数
  • 路径长度：两节点之间边的数量
  • 森林：m(m>0)棵互不相交树的集合。森林和树可以转换

区分 度为n的树 和 n叉树

两者都满足所有节点的度<=n

前者必须至少有一个节点度为n，后者可以不必有

前者不可以为空树，后者可以是空树

树的一些性质

  1. 树中的节点数 = 所有节点度数之和 + 1（根节点）
  2. 度数为m的树中，第i层上至多有 $m^{(i-1)}$ 个节点
  3. 高度h的m叉树最多有 $\frac{(m^h-1)}{(m-1)}$ 个节点
    1
    2
    3
    4
    5
    6
    7
    证明：

    让所有非叶子节点度都为m，可以得到节点数最多的情况。进行一个等比数列求和

    1+m+m^2+...+m^(h-1) = 1*(1-m^h)/(1-m)

    证毕
  4. 具有n个节点的m叉树最小高度为 $\lceil \log_m{n(m-1)+1)} \rceil$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    证明：

    让所有非叶子节点的度都尽量为m，可以让树高度最小

    假设结果有h层，那么n>(h-1)层m叉树最大节点数，n<=h层m叉树最大节点数，即

    (m^(h-1)-1)/(m-1) < n < (m^h-1)/(m-1)

    同 *(m-1), 对m取log 即证得 h

例题

1
2
3
4
5
一棵度为4的树中，有20个节点度为4，10个度为3，1个度为2，10个度为1，问叶子节点个数

解答：利用性质1
n = n0+n1+n2+n3+n4 = 0*n0+1*n1+2*n2+3*n3+4*n4
解得 n0 = 82

二叉树

二叉树定义和主要特性

定义

二叉树是另一种树形结构，特点是每一个节点至多有两棵子树，即二叉树中不存在度大于2的节点，并且二叉树的子树有序

区别：度为2的有序树

特殊的二叉树

  • 满二叉树：高度为h，且节点数为 $2^h-1$ 的二叉树
  • 完全二叉树：懂得都懂｜堆结构就是完全二叉树
    • 最多只有一个度为1的节点（做题会用到
  • 二叉排序树（BST）：左子树的节点的关键字都小于根节点的关键字；右子树的节点的关键字都大于根节点的关键字；左右子树又各自是二叉排序树
  • 平衡二叉树：树上任意节点的左右子树的深度之差不超过1
    • 可以有更高的搜索效率

二叉树的性质

  • 非空二叉树的叶子节点数等于度为2的节点数加上1 即 $n_0=n_2+1$
    1
    2
    3
    4
    证明：
    n = n0 + n1 + n2
    n = n1 + 2*n2 +1
    两式相减即证
  • 非空二叉树第k层最多有 $2^{(k-1)}$ 个节点
  • 高度h的二叉树最多有 $2^h-1$ 个节点（等比数列求和得到
  • 具有n个节点的完全二叉树的高度h为 $\lceil log_2{(n+1)}\rceil$

常见考点：

  • 对于一个完全二叉树，可以由总节点数n推出n0、n1和n2
    • n1只能是0或1
    • n0 = n1+1 所以，n0+n2一定是奇数
    • 那么就可以推导出
      • 如果完全二叉树有2k个节点，那么 n1 = 1, n0 = k, n2 = k-1
      • 如果完全二叉树有2k-1个节点，那么 n1 = 0, n0 = k, n2 = k-1
  • 完全二叉树的节点i所在层次： $\lfloor log_2{i}\rfloor+1$

二叉树的存储结构

  • 顺序存储结构：利用数组，需要存储空节点（造成浪费

    可以利用下标信息得到孩子、父亲信息

    假设从下标1开始存储

    左孩子—2i 右孩子—2i+1 父亲— $\lfloor \frac{i}{2}\rfloor 2$

    实际上，只适用于存储完全二叉树

  • 链式存储结构：二叉链，设置data，lchild和rchild域

    1
    2
    3
    4
    struct BiTNode{
        ElemType data;
        BiTNode *lchild, *rchild;
    };

    n个节点的二叉链表共有n+1个空链域（可以构造线索二叉树

二叉树的遍历和线索二叉树

二叉树的遍历

根据根节点N，左子树L和右子树R的访问顺序，可以有三种遍历，均可递归或非递归实现

先序遍历 NLR

递归算法

1
2
3
4
5
6
7
void PreOrder(BiTree T){
    if(T){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

非递归算法

用一个栈模拟函数调用栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PreOrder2(const BiTree& T){
    std::stack<BiTree> stk;
    BiTree p = T;
    while(p || !stk.empty()){
        if(p){
            std::cout<<p->data<<' ';
            stk.push(p);
            p = p->lchild;
        }else{
            p = stk.top();
            stk.pop();
            p = p->rchild;
        }
    }
}

中序遍历 LNR

递归算法

1
2
3
4
5
6
7
void InOrder(BiTree T){
    if(T){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

非递归算法

和前序遍历的区别只在于访问节点的时机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InOrder2(const BiTree& T){
    std::stack<BiTree> stk;
    auto p = T;
    while(p || !stk.empty()){
        if(p){
            stk.push(p);
            p = p->lchild;
        }else{
            p = stk.top();
            std::cout<<p->data<<' ';
            stk.pop();
            p = p->rchild;
        }
    }
}

后序遍历 LRN

递归算法

1
2
3
4
5
6
7
void PostOrder(BiTree T){
    if(T){
        PostOrder(T->lchild);
        PostOrder(T->right);
        visit(T);
    }
}

非递归算法

  • 用两个栈（左神的做法，有点投机取巧了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void PostOrder2(const BiTree& T){
    std::stack<BiTree> stk1, stk2;
    stk1.push(T);
    while(!stk1.empty()){
        auto top = stk1.top();
        stk1.pop();
        stk2.push(top);
        if(top->lchild) stk1.push(top->lchild);
        if(top->rchild) stk1.push(top->rchild);
    }
    while(!stk2.empty()){
        auto top = stk2.top();
        stk2.pop();
        std::cout<<top->data<<' ';
    }
}
  • 用一个栈（这种比较正统 要认真理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PostOrder(const BiTree& T){
    std::stack<BiTree> stk;
    BiTree pre = nullptr;   // 用来保存上次遍历的节点
    while(T || !stk.empty()){
        // 先向左走到底
        while(T){
            stk.push(T);
            T = T->lchild;
        }
        T = stk.top();  // 取出栈顶进行处理
        stk.pop();
        if(T->rchild == nullptr || T->rchild == pre){   // 右子树为空或者已经遍历完，就该遍历当前节点，也就是根节点
            std::cout<<T->data<<' ';
            pre = T;    // 记录上一个节点
            T = nullptr;    // 跳过左走的代码，往上边回溯
        }else{
            stk.push(T);    // 右子树还没处理，根节点入栈，遍历完右子树再进行处理
            T = T->rchild;  // 去遍历右子树
        }
    }
}

层序遍历

从上到下一层一层遍历，每层都是从左到右。需要借助队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild){
            EnQueue(Q, p->lchild);
        }
        if(p->rchild){
            EnQueue(Q, p->rchild);
        }
    }
}

由遍历序列构建二叉树

中序 + 先序 / 后序 可以唯一确定一棵二叉树

先序 + 后序 则不可以

  • 前序遍历中，第一个节点为根节点
  • 后序遍历中，最后一个节点为根节点
  • 找到根节点后，在中序遍历中可以划分出左右子树。不断划分就可以还原出二叉树

线索二叉树

线索二叉树的基本概念

一棵树遍历得到序列后，每个节点（除了首尾）在序列中都有一个前驱和后继。传统二叉链表只能体现父子关系，不能直接得到遍历后序列中的前驱和后继信息

为了加快查找前驱和后继的速度，考虑将二叉链表中n+1个空链域利用起来

规定：如果没有左孩子，则存储前驱节点；如果没有右孩子，则存储后继节点

因此需要两个标志域表明指向的是孩子还是前驱后继

1
2
3
4
5
6
7
lchild
ltag = 0 指向左孩子
ltag = 1 指向前驱

rchild
rtag = 0 指向右孩子
ratg = 1 指向后继
1
2
3
4
5
6
// 线索二叉树节点的结构
typedef struct ThreadTNode{
    ElemType data = 0;
    ThreadTNode *lchild = nullptr, *rchild = nullptr;
    int ltag = 0, rtag = 0;
}ThreadTNode, *ThreadTree;

指向前驱和后继的指针，称为线索

建立线索二叉树

线索的信息只能在遍历的过程中得到，所以建立线索二叉树其实就是一个遍历的过程

建立中序线索二叉树的实现如下：需要借助一个pre指针指向遍历的前一个节点

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
// 中序遍历过程
void InOrder(ThreadTree& T, ThreadTree& pre){
    if(T){
        InOrder(T->lchild, pre);
        // 前驱线索
        if(T->lchild == nullptr ){
            T->ltag = 1;
            T->lchild = pre;
        }
        // 后继线索
        if(pre != nullptr && pre->rchild == nullptr){
            pre->rtag = 1;
            pre->rchild = T;
        }
        pre = T;
        InOrder(T->rchild, pre);
    }
}
// 建立中序线索二叉树
void creatInOrderThreadTree(ThreadTree& T){
    ThreadTree pre = nullptr;   // 最左边节点没有左孩子
    if(T){
        InOrder(T, pre);
        // 处理遍历序列的最后一个节点
        pre->rchild = nullptr;
        pre->rtag = 1;
    }
}

前序线索二叉树 需要避免环路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void preOrder(ThreadTree root, ThreadTree pre){
    if(root){
        // 前驱线索
        if(root->lchild == nullptr){
            root->lchild = pre;
            root->ltag = 1;
        }
        // 后继线索
        if(pre && pre->rchild == nullptr){
            pre->rchild = root;
            pre->rtag = 1;
        }
        pre = root;
        if(root->ltag == 0) // 避免环路
            preOrder(root->lchild, pre);
        preOrder(root->rchild, pre);
    }
}

后序线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void postOrder(ThreadTree root, ThreadTree pre){
    if(root){
        postOrder(root->lchild, pre);
        postOrder(root->rchild, pre);
        // 前驱线索
        if(root->lchild == nullptr){
            root->lchild = pre;
            root->ltag = 1;
        }
        // 后继线索
        if(pre && pre->rchild == nullptr){
            pre->rchild = root;
            pre->rtag = 1;
        }
        pre = root;
    }
}

利用线索二叉树实现遍历

  • 中序遍历

关键在于找到中序遍历第一个节点，以及每个节点的中序遍历后继

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 找到中序遍历的第一个节点
// 子树最左边的节点就是第一个
ThreadTree firstNode(ThreadTree root){
    while(root->ltag == 0)  root = root->lchild;
    return root;
}
// 找到中序遍历的后继节点
ThreadTree nextNode(ThreadTree node){
    if(node->rtag == 1)   return node->rchild;  // 有后继线索 直接返回后继节点
    // 有右子树，那么右子树的最左边就是后继节点
    return firstNode(node->rchild);
}
// 中序遍历
void InOrder2(ThreadTree root){
    for(auto p=firstNode(root);p;p=nextNode(p)){
        std::cout<<p->data<<' ';
    }
}
  • 找到中序遍历的最后一个节点

子树最右边的节点就是

1
2
3
4
ThreadTree lastNode(ThreadTree node){
    while(node->rtag == 0)  node = node->rchild;
    return node;
}
  • 找到中序遍历的前驱

左子树中最右边的节点 就是中序遍历的前驱

1
2
3
4
ThreadTree preNode(ThreadTree root){
    if(root->lchild == 1)   return root->lchild;    // 有前驱线索，直接返回前驱
    return lastNode(root->lchild);
}

树的存储结构

双亲表示法

孩子表示法

孩子兄弟表示法

涉及到树和二叉树的转换

森林和二叉树的转换也同理

孩子兄弟表示法 / 树转换为二叉树

森林转换为二叉树

树的遍历

对树的遍历和对二叉树的遍历类似。分为先序遍历和后序遍历，均可以用递归实现

先序遍历

先访问根节点，再依次对每棵子树进行先序遍历

伪代码

1
2
3
4
5
6
7
8
void PreOrder(TreeNode* R){
    if(R){
        visit(R);
        while(R还有未访问子树T){
            PreOrder(T);
        }
    }
}

后序遍历

先对每棵子树进行后序遍历，再访问根节点

伪代码

1
2
3
4
5
6
7
8
void PostOrder(TreeNode* R){
    if(R){
        while(R还有未访问的子树T){
            PostOrder(T);
        }
        visit(R);
    }
}

层序遍历（广度优先遍历

借助一个队列

  1. 若树非空，将根节点入队
  2. while队列非空时，出队队头并访问，同时将其所有孩子入队
  3. 重复2直到队空

森林的遍历

这里只需要的到最后结果即可

  • 先序遍历：等于依次对所有树先序遍历的结果
  • 中序遍历：等于对所有树后序遍历的结果 / 对二叉树中序遍历的结果

二叉排序树 BST

定义：

  1. 左子树上所有节点的关键字都小于根节点的关键字
  2. 右子树上所有节点的关键字都大于根节点的关键字
  3. 左子树和右子树右各是一棵BST

特性：中序遍历可以得到递增的序列

二叉排序树的查找

从根节点出发，比较给定值和节点关键字，如果相等，则查找成功；如果给定值更小，则往左子树查找；否则往右子树查找

可以递归和非递归实现 空间复杂度上，非递归更优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 非递归
BSTNode* BST_Search(BSTree T, int key){
    while(T && key != T->key){
        if(key < T->key){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}
// 递归
BSTNode* BST_Search(BSTree T, int key){
    if(!T)  return nullptr;
    if(key == T->key)   return T;
    else if(key < T->key)
        return BST_Search(T->lchild, key);
    else
        return BST_Search(T->rchild, key);
}

二叉排序树的插入

需要找到适合插入的位置。可以递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 递归
bool BST_Insert(BSTree& T, int k){
    if(!T){
        T = (BSTree) malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = nullptr;
        return true;
    }else if(k == T->key){
        return false;
    }else if(k > T->key){
        return BST_Insert(T->rchild, k);
    }else{
        return BST_Insert(T->lchild, k);
    }
}
// 非递归
bool BST_Insert2(BSTree T, int k){
    // 查找k
    // 找到k的话说明插入失败
    // 没找到k就构建一个k节点，链接一下即可
}

二叉排序树的构造

重要考点：给定一个序列，构造一棵二叉排序树

不同的序列得到的二叉排序树可能相等也可能不相等，查找的性能也有所差别。

平衡BST查找性能更好！

BST的删除

首先得找到节点Z

  • 如果Z是叶子节点 那么直接删除
  • 如果Z只有左子树或右子树，那么让孩子替代Z的位置就好
  • 如果Z有左右子树
    • 方案一：用Z的右子树中最小的节点Y替换Z的位置，再删除Y。因为Y位于右子树中最左，因此删除Y就是情况1或2
    • 方案二：用Z的左子树中最大的节点Y替换Z的位置，再删除Y。因为Y位于左子树中最右，因此删除Y就是情况1或2

BST查找效率

时间复杂度：O(log(2, h)) （对于AVL

所以h越小越好，即BST应该胖一点，那么就引出AVL（平衡二叉树）

平衡二叉树 AVL

定义

树上任意节点的左子树和右子树的高度之差不超过1

节点的平衡因子 = 左子树高 - 右子树高

对于AVL，所有节点的平衡因子只能取-1，0或1，绝对值都不会超过1

平衡二叉树的插入

一个重要的问题就是往平衡二叉树插入一个新节点后，如何保持平衡？

可以发现，插入一个新节点后，只需要向上找到第一个平衡因子不满足条件的节点，调整这棵子树就可以恢复平衡。这棵子树称为最小不平衡子树

分为四种情况

在A的左孩子的左子树插入新节点导致A不平衡

LL

代码实现思路

在A的右孩子的右子树插入新节点导致A不平衡

RR

代码实现思路

在A的左孩子的右子树插入新节点导致A不平衡

在A的右孩子的左子树插入新节点导致A不平衡

哈夫曼树

定义

  • 树的带权路径长度WPL：树中所有 叶子节点的权*根节点到叶子节点的路径长度 之和
  • 哈夫曼树：使WPL最小的二叉树。又称最优二叉树

哈夫曼树的特点：

  • 每个初始节点都成为叶子节点
  • 构造过程中生成了n-1个新节点，因此哈夫曼树的节点总数为2n-1
  • 哈夫曼树中不存在度为1的节点

构造哈夫曼树

考点：哈夫曼编码 其实就是构造哈夫曼树，然后左0右1

用哈夫曼树可以设计出总长度最短的二进制前缀编码

展开全文 >>

串模式匹配

Content

  • 串的模式匹配
  • BF算法
  • KMP算法

串的模式匹配

概念：在主串中找到与模式串相同的子串，返回其所在位置

BF算法

O(n^2)暴力扫描，思路简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int BF(const string& S, const string& T){
    auto m = S.length(), n = T.length();           // 长度
    auto index1 = 0, index2 = 0;
    while(index1 < m && index2 < n){
        if(S[index1] == T[index2]){
            ++index1;
            ++index2;
        }else{                                                              // 比较失败，从S上次起始的下一个字母开始匹配，T回到第一个
            index1 = index1-index2+1;
            index2 = 0;
        }
    }
    if(index2 == n)  return index1 - n;
    return -1;
}

KMP算法

思想：当两个字符失配时，可以得到信息：前面的所有字符都匹配成功。KMP算法就是利用这部分信息，让i不回溯，提高匹配效率

KMP算法具体解释，可以移步我的BiliBili视频 手撕KMP！｜理论+cpp实现

下面给出王道考研书的实现：字符串从数组的下标1处开始

求next数组—手动

  1. next[1] = 0
  2. 字符i的前缀：区间[1, i-1)范围内，必定包含[1]位置处字符的子串
  3. 字符i的后缀：区间(1, i-1]范围内，必定包含[i-1]位置处字符的子串
  4. next[i] = 字符i处，最大相等前后缀长度+1

求next数组—计算机

相当于模式串和自己KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_next(const String& T, int next[]){
    int i = 1, j = 0;
    next[1] = 0;    // 根据定义
    while(i < T.length){
        if(j ==0 || T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

KMP算法—index从1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int KMP(const String& S, const String& T, const int next[]){
    // i扫描文本串S，j扫描模式串T
    int i=1, j=1;
    while(i <= S.length && j <= T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    // 如果j扫描完T，说明匹配成功
    if(j > T.length)    return i-T.length;
    // 失败返回0
    return 0;
}

nextval数组—KMP算法优化

可以减少不必要的比较

  • 手动计算：
  1. nextval[1] = 0 定义
  2. 从左往右推。求出next[j]， 如果S[j] = S[next[j]]，则nextval[j] = nextval[nextval[j]]；反之nextval[j] = next[j]
  • 算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void get_nextval(const String& T, int nextval[]){
    int i=1, j=0;
    nextval[1] = 0;
    while(i < T.length){
        if(j == 0 || T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            if(T.ch[i] != T.ch[j])  nextval[i] = j;
            else    nextval[i] = nextval[j];
        }else{
            j = nextval[j];
        }
    }
}

KMP匹配过程则和原本一样

展开全文 >>

leetcode 1447. 最简分数

题目

给你一个整数n，请你返回所有0到1之间（不包括0和1）满足分母小于等于n的最简分数。分数可以以任意顺序返回。

1 < n < 100

1
2
3
4
示例：
n = 3

输出："1/2" "1/3" "2/3"

思路

  1. 暴力思路：O(n^2)搜索每一个分子分母搭配，因为数据量小，是可以通过的
  2. 那么如何验证最简分数呢？答案是分子分母的最大公约数为1。求两个数的最大公约数可以用欧几里得算法（辗转相除法）
  3. 欧几里得算法：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数
1
2
3
4
5
6
7
8
9
10
11
12
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：

1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
  1. 以下给出递归版本的实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    // 欧几里得算法
    int mygcd(int a, int b){
        if(a%b == 0)    return b;
        return b > a%b ? mygcd(b, a%b) : mygcd(a%b, b);
    }
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for(int i=2;i<=n;++i){
            for(int j=1;j<i;++j){
                if(mygcd(i, j)==1){
                    ans.emplace_back(to_string(j)+"/"+to_string(i));
                }
            }
        }
        return ans;
    }
};

展开全文 >>

Hi

hexo命令

  1. hexo s 可以预览博客

  2. hexo g 生成博客（修改博客后generate一下）

  3. hexo n + “文件名” 新建一篇文章

  4. hexo d 部署到github上 username + personnal access token

  5. hexo clean 清理

vim 命令

1.vim 文件名 vim编辑器打开文件

  1. 刚打开vim时是命令模式，输入i切换为编辑模式

  2. ESC切换回命令模式

  3. 命令模式下输入:（英文冒号）进入底线命令模式，可以用很多命令

    比如：q 退出程序 w 保存文件

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一定要赢