Posted on

石子合并

题目描述

设有 N 堆石子排成一排，其编号为 $1，2，3，…，N$。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 $4$ 堆石子分别为 1 3 5 2， 我们可以先合并 $1、2$ 堆，代价为 $4$，得到 4 5 2， 又合并 $1，2$ 堆，代价为 $9$，得到 9 2 ，再合并得到 $11$，总代价为 $4+9+11=24$；

如果第二步是先合并 $2，3$ 堆，则代价为 $7$，得到 4 7，最后一次合并代价为 $11$，总代价为 $4+7+11=22$。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 N 表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

$1≤N≤300$

输入样例：

1
2
4
1 3 5 2

输出样例：

1
22

思路

状态表示

  • 集合：f[i][j]表示所有将[i,j]中的石子合并成一堆的代价的集合
  • 属性：最小值

状态计算

1
2
for k in [i, j-1]:
  f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[i][j])

计算步骤：从小区间的状态推导出大区间的状态。位置可以是任意的，但长度一定是从小到大。所以必须先从小到大枚举长度。

代码

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
#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N]; // 前缀和

int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i-1];

    for(int len = 2; len <= n; len++)
        for(int i = 1; i + len - 1 <= n; i++){
            int j = i + len - 1;
            f[i][j] = 1e8;
            for(int k = i; k < j; k ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);
        }
    cout << f[1][n] << endl;
    return 0;
}

Posted on

蒙德里安的梦想

题目描述

求把 N*M 的棋盘分割成若干个 1*2 的的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

如下图所示：
291

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N 和 M。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$1≤N,M≤11$

输入样例：

1
2
3
4
5
6
7
8
9
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
2
3
4
5
6
7
8
1
0
1
2
3
5
144
51205

代码

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;
int n,m;
LL f[N][M];
//存储所有合法的状态 对于每个状态而言，能转移到它的合法状态有哪些
vector<int> state[M];
//判断某个状态能不能用竖着1x2小方格填满
bool st[M];

int main()
{
    while(cin >> n >> m, n || m)
    {
        //枚举每种 state 是否合法（能不能竖着填满）
        for(int i = 0; i < 1 << n; i++)
        {
            //cnt 记录每个0区间里连续的0的个数
            int cnt = 0;
            bool is_valid = true;
            //对于每个state，逐位枚举，判断从小往大下标为j的digit是不是1
            for(int j = 0; j < n; j++)
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            if(cnt&1)is_valid = false;
            st[i] = is_valid;
        }

        //可以合法转移的状态
        for(int i = 0; i < 1 << n; i++)
        {
            state[i].clear();
            for(int j = 0; j < 1 << n; j++)
                if((i&j) == 0 && st[i|j])
                    state[i].push_back(j);
        }

        memset(f,0,sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 0; j < 1 << n; j++)
                for(auto k : state[j])
                    f[i][j] += f[i-1][k];
        }
        //f[m][0] 代表下标为m-1前的列都已经摆好，且无小方块伸到下标为m的列的情况
        cout << f[m][0] << endl;
    }
    return 0;
}

最短 Hamilton 路径

题目描述

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。

接下来n行每行n个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

数据范围

$1≤n≤20$
$0≤a[i,j]≤10^7$

输入样例

1
2
3
4
5
6
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例

1
18

思路

状态表示

集合：f[i][j]代表从0走到j，并且走过的点以二进制记录在i的权重和
属性：最小值

状态计算

假设从k走到j
f[i][j] = f[i-{j}][k] + a(k,j)

代码

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
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20, M = 1 << N;

int n;
//邻接矩阵
int w[N][N];
//状态表示
int f[M][N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> w[i][j];

    memset(f,0x3f,sizeof f);
    //0走过了，所以idx:0为1
    f[1][0] = 0;
    for(int i = 0; i < 1<<n ; i++)
        for(int j = 0; j < n; j++)
            if(i>>j & 1)
                for(int k = 0; k < n; k++)
                    //(i-(1<<j)) 代表去掉 j 的路径
                    if( (i-(1<<j))>>k & 1 )
                        f[i][j] = min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

    cout<<f[(1<<n)-1][n-1]<<endl;

    return 0;
}

Posted on

ES6 的导出

sthexport.js

1
2
3
4
5
6
7
8
//ES6 中的顶级导出，与次级导出并行不悖
export default function myFunc(name,age){
  console.log('Name: '+name+'\n'+'Age: '+age+'\n');
}

var name = 'Tadokoro';
var age = 24
export {name,age}

ES6 的导入

sthimport.js

1
2
3
4
5
6
7
8
9
10
11
12
13
import saysth,{name,age} from './sthexport.js'
//Error
//import {myFunc,name,age} from './sthexport.js'

saysth(name,age);
//Error
/*
SyntaxError: The requested module './sthexport.js' does not provide an export named 'myFunc'
    at ModuleJob._instantiate (internal/modules/esm/module_job.js:96:21)
    at async ModuleJob.run (internal/modules/esm/module_job.js:134:20)
    at async Loader.import (internal/modules/esm/loader.js:179:24)
*/
//myFunc(name,age)

CommonJS 的导出

sthexport.js

1
2
3
4
5
6
7
8
//两个都可以
module.exports.age = 24;
exports.name = 'Tadokoro'

//Common JS 中的顶级导出，会覆盖前面的次级导出
//undefined
//undefined
//module.exports = {job:"Student"}

CommonJS 的导入

1
2
let i = require('./sthexport');
console.log('Name: '+ i.name + '\n' + 'Age: '+ i.age + '\n');

Posted on

19. Remove Nth Node From End of List

问题描述

Given a linked list, remove the n-th node from the end of list and return its head.
Example 

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。　　
Example　

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

思路

  • 用一趟扫描实现的话，需要用双指针
  • 先让第二个指针走 n 步，然后两个指针一起走
  • 第二个指针走到最后一个节点的时候，第一个指针在倒数第n+1个节点上
  • 把第一个指针的next指向next->next
  • 因为可能删掉第一个节点，需要用一个头节点

代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(-1, head);
        
        auto first = dummy, second = dummy;
        while(n--)first = first -> next;
        
        while(first->next)
        {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        
        return dummy->next;
    }
};

Delete Node in a Linked List

问题描述

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

desc

Note:

  • The linked list will have at least two elements.
  • All of the nodes’ values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.

提示：

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

思路

  • 题目只给了当前节点的指针，按一般办法删除是不行的
  • 所以需要骚操作，把当前节点的值改成下一节点的值，然后删掉下一节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

61. Rotate List

问题描述

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

思路

代码

1
2


Posted on

34. Find First and Last Position of Element in Sorted Array

二分查找的基础题，拿来练练手。

题目描述

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

思路

  • 排好序的数列搜索给定值。一道用二分法找左边界和右边界的题目。
  • 主要注意一下查找左右边界代码。找左边界check()用<，找右边界check()用>。
  • 还需要注意每次迭代mid转移的时候要不要加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
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        vector<int> res;
        //边界情况
        if(!nums.size())
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }            
        //find min
        while(l < r)
        {
            int mid =(l + (long long)r) >> 1;
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }
        //找不到目标值 直接返回
        if(nums[l] != target)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        res.push_back(l);
        //find max
        l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + (long long)r + 1) >> 1;
            if(nums[mid] > target)
                r = mid - 1;
            else
                l = mid;
        }   
        res.push_back(r);
        return res;
    }
};

35. Search Insert Position

题目描述

https://leetcode.com/problems/search-insert-position/

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

思路

  • 排好序的数列搜索给定值。用二分法。
  • 主要注意一下找不到给定值的情况。这题假设数组中无重复元素，所以每个值对应的下标是唯一的。如果小于等于目标值，就插入在最后返回的下标上，否则+1。
  • 注意每次迭代mid转移的时候要不要加1除以2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l < r)
        {
            int mid = l + (long long)r >> 1;
            int x = nums[mid];
            if(x >= target)
                r = mid;
            else
                l = mid + 1;
        }
        if(target > nums[r]) return r + 1;
        else return r;
    }
};

74. Search a 2D Matrix

题目描述

https://leetcode.com/problems/search-a-2d-matrix/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

思路

先把所在行二分出来，再把所在列二分出来

代码

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
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        //处理边界
        if(m == 0 )return false;
        int n = matrix[0].size();
        if(n == 0 )return false;
        //找所在行
        int l = 0, r = m-1;
        while(l<r)
        {
            int mid = (l + (long long)r + 1) >> 1;
            if(matrix[mid][0] > target)
                r = mid - 1;
            else
                l = mid;
        }
        //记录所在行
        int tmp = l;
        //找所在列
        l = 0, r = n-1;
        while(l<r)
        {
            int mid = l + (long long)r + 1 >> 1;
            if(matrix[tmp][mid] > target)
                r = mid - 1;
            else
                l = mid;            
        }
        if(matrix[tmp][l] == target)return true;
        else return false;
    }
};

153. Find Minimum in Rotated Sorted Array

题目描述

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

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

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

请找出其中最小的元素。

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

思路

最初的想法

  • 这道题目其实涉及的是二分的本质，就是找一个点，whose 左边符合性质A，右边符合性质B
  • 这道题断点左边的值都大于nums[0]，右边断点的值都小于nums[0]，发现这个性质以后问题就迎刃而解了
  • 不过要考虑特殊的边界情况，就是断点在第一个点上（也可以说根本没断点），这时候直接输出nums[0]即可

改进

  • 不要和nums[0]比较，和nums[n-1]比较，就不用考虑特殊情况了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        //特殊情况：根本没有旋转
        if(nums[0]<nums[r])return nums[0];
        int a = nums[0];
        while(l < r)
        {
            int mid = (l + (long long)r) >> 1;
            //在断点or断点右边
            if(nums[mid] < a)
                r = mid;
            else
                l = mid + 1;
        }
        return nums[l];
    }
};

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        int a = nums[r];
        while(l < r)
        {
            int mid = (l + (long long)r) >> 1;
            //在断点or断点右边
            if(nums[mid] <= a)
                r = mid;
            else
                l = mid + 1;
        }
        return nums[l];
    }
};

33. Search in Rotated Sorted Array

题目描述

https://leetcode.com/problems/search-in-rotated-sorted-array/

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

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

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

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

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

你的算法时间复杂度必须是 O(log n) 级别。

思路

  • 先求出断点
  • 再判断是在左边二分还是右边二分

代码

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }

        if (target <= nums.back()) r = nums.size() - 1;
        else l = 0, r -- ;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[l] == target) return l;
        return -1;
    }
};

278. First Bad Version

模板级的二分查找题

问题描述

https://leetcode.com/problems/first-bad-version/

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 

1
2
3
4
5
6
7
Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例

1
2
3
4
5
6
7
给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (l + (long long)r) >> 1;
            //mid 及其以后的版本都是坏的
            if(isBadVersion(mid))
                r = mid;
            else l = mid+1;
        }
        return l;
    }
};

162. Find Peak Element

问题描述

https://leetcode.com/problems/find-peak-element/

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

思路

  • 这题一开始没想出做法，看了一下网上的解答，发现是没有充分利用起nums[-1] = nums[n] = -∞这个隐含的条件。
  • 因为左右两边都是-∞，所以如果阵列是单调递增的，那么极大点就在右端点，如果阵列式单调递减的，那么极大点就在左端点。如果两个都不是，极大点肯定就在中间。故峰值一定在区间中。
  • 可以用二分法进行搜索，找到一个中点nums[mid]，如果nums[mid+1]比它大，那么nums[mid+1]或它的右边必然有峰值。反之，nums[mid]或它的左边必然有峰值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + (long long)r ) >> 1;
            if(nums[mid] < nums[mid + 1])
                l = mid + 1;
            //nums[mid] > nums[mid + 1]
            else r = mid;
        }
        return l;
    }
};

H-Index II

问题描述

https://leetcode.com/problems/h-index-ii/

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”

思路

  • 设数组长度为n，先确定中点坐标mid和值 h =nums[mid]
  • 如果n-mid > nums[mid]，说明被引用了至少 h 次的论文数量多于 h 篇，不符合要求，要往右边找，缩小论文的数量，否则往左边找
  • 最后返回 h = n - nums[r]，但要注意边界情况，例如发表的所有论文都是0引用

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int hIndex(vector<int>& citations) {
        const int n = citations.size();
        if (n == 0) return 0;
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = (l + (long long)r) >> 1;
            
            if(n - mid > citations[mid])
                l = mid + 1;
            else
                r = mid;
        }
        if(citations[r]>0) return n-r;
        else return 0;
    }
};

Find the Duplicate Number

问题描述

https://leetcode.com/problems/find-the-duplicate-number/

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

思路

  • 这题也是一开始没想出做法，看了一下网上的解答，发现是没有充分利用起each integer is between 1 and n (inclusive)和there is only one duplicate number这个隐含的条件。
  • 也就是说数组里有n+1个数，数的范围是1~n。因为只有1个数重复，所以每一个值都会取到，其中有一个值被取到了两次
  • 抽屉原理。n+1个下标相当于苹果，n个值相当于抽屉。把值域（抽屉）分成左右两个半边，其中必有一个半边多了一个苹果。只要找到多了一个苹果的半边，不断二分就能定位出最后的抽屉。

代码

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 findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size()-1;
        while(l < r)
        {
            int cnt = 0;
            int mid = (l + (long long)r) >> 1;
            
            for(auto x : nums)
            {
                if(x >= l && x <= mid)
                    cnt++;
            }
            if(cnt > mid - l + 1)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};

Posted on
  • 背包问题
    • 0 1 背包：每件物品最多只用一次
    • 完全背包：每件物品有无限个
    • 多重背包
    • 分组背包： 每组最多只能选一个物品

0 1 背包

内容

  • N 个物品，总容量不能超过 V
  • 每个物品体积是vi，价值是wi
  • 每件物品至多只能用一次

思路

从两个方面来思考：

  • 状态表示 f(i,j)
    • 集合
      • 满足下列条件的所有选法
      • 条件
        • 只从前i个物品中选
        • 总体积不超过j
    • 属性
      • Max
      • Min
      • Cnt
  • 状态计算
    • f(i,j) 集合划分
      • 原则：不重、不漏
      • 不含 i 的放一边
        • f(i-1,j): 从1～i-1选，且总体积不超过j的选法
      • 含 i 的放一边
        • f(i,j): 从1～i选，且总体积不超过j的选法
        • 相当于 f(i-1,j-vi) + wi

代码

naive 版

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
//状态表示：
//集合：所有「只考虑前 i 个物品」，「并且总体积不超过 j」 的“选法”的集合 
//属性：价值的最大值
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int dp[N][N];

int n,v;


int main()
{
    cin >> n >> v;
    for(int i = 1; i <= n; i++)
    {
        int vi,wi;
        cin >> vi >> wi;
        for(int j = 0; j <=v; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j-vi>=0)
                dp[i][j] = max(dp[i-1][j-vi]+wi, dp[i-1][j]);
        }
    }
    int ans = 0;
    for(int k = 0; k <= v; k++) ans = max(dp[n][k],ans);
    cout<<ans<<endl;
    return 0;
}

优化成一维数组

原理：计算dp[i][j] = max(dp[i-1][j-vi]+wi, dp[i-1][j]) 的时候其实只用到了 i-1 一层，和第 i 层没关系

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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int dp[N];

int n,v;


int main()
{
    cin >> n >> v;
    for(int i = 1; i <= n; i++)
    {
        int vi,wi;
        cin >> vi >> wi;
        for(int j = v; j >=vi; j--)
        {
            // 变成了恒等式 没意义
            //dp[j] = dp[j];
            //因为从大到小遍历，所以此时j & j - vi 必然还没有遍历过，等价于dp[i-1][j-vi] & dp[i-1][j]
            dp[j] = max(dp[j-vi]+wi, dp[j]);
        }
    }
    int ans = 0;
    for(int k = 0; k <= v; k++) ans = max(dp[k],ans);
    cout<<ans<<endl;
    return 0;
}

完全背包问题

内容

  • N 个物品，总容量不能超过 V
  • 每个物品体积是vi，价值是wi
  • 每件物品可以用无限次

思路

从两个方面来思考：

  • 状态表示 f(i,j)
    • 集合
      • 满足下列条件的所有选法
      • 条件
        • 只从前i个物品中选
        • 总体积不超过j
    • 属性
      • Max
      • Min
      • Cnt
  • 状态计算
    • f(i,j) 集合划分
      • 按照第i个物品选了几个来划分
      • 0 1 2 3 … k-1 k
    • 曲线救国
      • 去掉k个物品i
      • 求 Max(f[i-1,j-k*v[i]])
      • 再加回来 k 个物品 => f[i-1,j-k*v[i]] + w[i]

代码

naive 版

复杂度：O(n^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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int f[N][N];
int w[N],v[N];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k*v[i] <= j; k++)
                f[i][j] = max(f[i][j],f[i-1][j-k*v[i]] + k*w[i]);
    
    int res = 0;
    for(int j = 0; j <= m; j++)
        res = max(res, f[n][j]);
    
    cout<<res<<endl;
    
    return 0;
}

优化版

思路：

  • f[i,j] = Max(f[i-1,j], f[i-1,j-v]+w, f[i-1,j-2v]+2w, f[i-1, j-3v]+3w, ...)
  • f[i,j-v] = Max(f[i-1,j-v], f[i-1,j-2v]+w, f[i-1,j-3v]+2w, f[i-1, j-4v]+3w, ...)
  • f[i,j] = Max(f[i-1,j], f[i,j-v]+w)
  • 只需要枚举两个状态 
    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

    #include <iostream>
    #include <algorithm>

    using namespace std;

    const int N = 1010;

    int n, m;
    int v[N], w[N];
    int f[N][N];

    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
                {
                    f[i][j] = f[i-1][j];
                    if(j >= v[i])
                        f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
                }
        cout << f[n][m] << endl;

        return 0;
    }

优化成一维数组

思路：

  • 0 1 背包：从 i - 1 层转移过来
  • 完全背包： 第 i 层 
    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
    #include <iostream>
    #include <algorithm>

    using namespace std;

    const int N = 1010;

    int n, m;
    int v[N], w[N];
    int f[N];

    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

        for (int i = 1; i <= n; i ++ )
            for (int j = v[i]; j <= m; j ++ )
                {
                    //和 0 1 背包不一样
                    //从小到大遍历
                    //因为比较的是 Max(f[i-1,j], f[i,j-v]+w)
                    //也就是应该先遍历 j-v 后再到 j
                    f[j] = max(f[j],f[j-v[i]]+w[i]);
                }
        cout << f[m] << endl;

        return 0;
    }

    多重背包

    思路

  • 状态表示 f(i,j)
    • 集合
      • 满足下列条件的所有选法
      • 条件
        • 只从前i个物品中选
        • 总体积不超过j
    • 属性
      • Max
      • Min
      • Cnt
  • 状态计算
    • f(i,j) 集合划分
      • 按照第i个物品选了几个来划分
      • 0 1 2 3 … s[i]
      • f[i][j] = Max(f[i-1][j-v[i]*k]+w[i]*k), k = 0,1,2,3…s[i]

代码

naive 版

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
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;
int f[N][N];
int v[N],w[N],s[N];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k * v[i] <= m && k <= s[i]; k++)
            {
                //错的，如果 k-1 次迭代中f[i][j] 比 f[i-1][j] 大
                //这么写把值又变回去了
                //f[i][j] = f[i-1][j];
                if(j >= k*v[i])
                    f[i][j] = max(f[i][j], f[i-1][j - k*v[i]] + k*w[i]);
            }
    
    cout<< f[n][m]<<endl;
    return 0;
}

优化版

  1. 不能直接像完全背包一样优化多重背包
  2. 知道了 0 ～ s+1 的最大值，并不能因此推出 0 ~ s 的最大值
  3. 用二进制的方法 1,2,4,8,… 2^k, C(C<2^k+1)
  4. 从 0 到 s 的任意一个值都可以拼凑出来
  5. S -> logS
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
//思想：把每个物品按照二进制拆分成多个物品
//保证拆分后的物品可以任意组合
#include<iostream>
#include<algorithm>

using namespace std;
//N：一共有 1000 个物品，每个物品又可以拆成 log2000 个物品
//N >= 1000*11 = 11000
const int N = 25000, M = 2010;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k*=2;
        }
        if(s>0)
        {
            cnt ++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    
    n = cnt;
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    
    cout << f[m] <<endl;
    
    return 0;
}

分组背包

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

Posted on

  • 最小生成树

    • Prim 算法

      • 朴素版 Prim O(n^2)，适合稠密图
      • 堆优化版 Prim O(mlogn)，适合稀疏图

    • 克鲁斯卡尔算法 O(mlogm)，适合稀疏图，比堆优化版的 Prim 好用

  • 二分图

    • 染色法 O(m+n)
    • 匈牙利算法 O(mn)，实际运行时间一般远小于O(mn)

朴素 Prim 算法

和 Dijkstra 很像

思想

1
2
3
4
5
把每个 dist[i] 都初始化为正无穷
for(i = 0; i < n; i++):
    找到集合外距离最近的点t
    用t更新其他点到集合的距离
    st[t] = true

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
//稠密图，用邻接矩阵
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    //初始化：把距离都设成正无穷
    memset(dist, 0x3f, sizeof dist);
    //res 计算集合内距离的总和 最小生成树长度之和
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            //st 是否在生成树内
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        //当前图不联通
        if (i && dist[t] == INF) return INF;
        //只要不是第一个点，dist[t]就代表当前的点到生成树的最短距离
        //先加进去再更新，不然遇到自环会出问题
        if (i) res += dist[t];
        st[t] = true;
        //更新距离
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        //无向图 从a到b 从b到a
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

克鲁斯卡尔算法

并查集

思想

1
2
3
4
1. 将所有边按权重从小到大排序 O(mlogm)
2. 枚举每条边a,b 权重c： 
    if a,b 不连通:
        将这条边加入集合

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;

    //排序用
    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

染色法

一个图是二分图，当且仅当图中不含有奇数环

思想

1
2
3
for(i = 1; i <= n; i++):
    if i 未染色:
        dfs(i,1)#把 i 所在的联通块都染色一遍

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c)
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;//继续染色，如果有矛盾发生返回f
        }
        else if (color[j] == c) return false;//当前有矛盾发生
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if (flag) puts("Yes");
    else puts("No");

    return 0;
}

匈牙利算法

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++ ;
    }

    printf("%d\n", res);

    return 0;
}

Posted on

问题描述

刚建起来的 React 项目在 dev-server 上刚一运行，就显示报错：

1
2
3
4
5
6
7
8
9
10
11
/Users/***/Desktop/ts-react-app/node_modules/jest-diff/build/diffLines.d.ts
TypeScript error in /Users/***/Desktop/ts-react-app/node_modules/jest-diff/build/diffLines.d.ts(8,13):
'=' expected.  TS1005

     6 |  */
     7 | import { Diff } from './cleanupSemantic';
  >  8 | import type { DiffOptions } from './types';
       |             ^
     9 | export declare const diffLinesUnified: (aLines: Array<string>, bLines: Array<string>, options?: DiffOptions | undefined) => string;
    10 | export declare const diffLinesUnified2: (aLinesDisplay: Array<string>, bLinesDisplay: Array<string>, aLinesCompare: Array<string>, bLinesCompare: Array<string>, options?: DiffOptions | undefined) => string;
    11 | export declare const diffLinesRaw: (aLines: Array<string>, bLines: Array<string>) => Array<Diff>;

解决方案

上网搜了一下，有人建议把 TS 版本改成3.8.0 以上，没有用。后来找到了 jest 项目下面的一个 Issue，发现是 jest 的 bug 造成的。在 25.2.3 中已被修复。把 jest 的版本改成 25.2.3 后再重装一遍依赖包，问题解决。

Posted on

框架

  • 最短路
    • 单源最短路
      • 所有边权值都是正数
        • 朴素 Dijkstra 算法 O(n^2) 稠密
        • 堆优化版的 Dijkstra 算法 O(mlog(n)) 稀疏
      • 存在负权边
        • Bellman-Ford O(nm)
        • SPFA 一般O(m),最坏O(nm)
    • 多源最短路
      • Floyd 算法 O(n^3)

朴素Dijkstra

trick: 稠密图用矩阵 稀疏图用链表

思路

1
2
3
4
5
6
设 S 代表当前已确定最短距离的点, V代表顶点集  
1. dis[1] = 0, 其他 = 正无穷
2. for v in V:
	找到不在 S 中的距离最近的点 t （总共 n^2次）
	把 t 加入 S （总共 n次）
	用 t 更新 S 所有点的距离（实际上是遍历了所有边，总共 m次）

代码

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
# include<cstring>
# include<iostream>
# include<algorithm>

using namespace std;
const int N = 510;

//n 代表顶点数 m 代表边数
int n,m;
//邻接矩阵存边，适合稠密图
int g[N][N];
int dist[N];
//st 是否已在集合 S 中
bool st[N];

int dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i++)
    {
        //每一次找出距离最短的点 做n次
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;

        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    if(dist[n] == 0x3f3f3f3f) return -1; 
    return dist[n];

}

int main()
{
    scanf("%d%d",&n,&m);
    memset(g, 0x3f, sizeof g);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b],c);
    }

    cout<<dij()<<endl;

    return 0;

}

堆优化版的 Dijkstra

堆的C++实现：优先队列

思想

1
2
3
4
5
6
设 S 代表当前已确定最短距离的点
1. dis[1] = 0, 其他 = 正无穷
2. for i in range(0, n):
	找到不在 S 中的距离最近的点 t （总共 n次）
	把 t 加入 S （总共 n次）
	用 t 更新 S 所有点的距离（总共 mlog(n)次）

代码

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
# include<cstring>
# include<iostream>
# include<algorithm>
# include<queue>

using namespace std;

typedef pair<int,int> PII;

const int N = 150010;

int n,m;
int h[N], e[N],w[N], ne[N],idx;
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool st[N];

int dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        
        //当前的点是个冗余备份
        //如果已经遍历过了
        if(st[ver])continue;
        st[ver] = true; 
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1; 
    return dist[n];

}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h, -1, sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        add(a,b,c);
    }

    cout<<dij()<<endl;

    return 0;

}

Bellman - Ford 算法

思想

hint: 如果有负权回路，最短路不一定存在
有边数限制的最短路 适合bf

1
2
3
4
for n 次
	备份
	for 所有边 a b w （表示存在一条从a走向b的边，权重是w）
		dist[b] = min(dist[b],dist[a]+w)

代码

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1e5+10;
//定义初值时要合理
int n, m, k;
int dist[N], backup[N];
//由于连锁关系，所以需要进行备份操作
//使用backup数组的目的是为了防止松弛的次数大于k
struct Edge {
    int a, b, w;
}edge[M];
//边是M个

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //初始化距离,0x3f而不要初始化成太小的

    //松弛k次
    for(int i = 0; i < k; i++) {
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j++) {
            auto x = edge[j]; 
            dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
                //类似Dijkstra算法中的更新距离
        }
    }
    if(dist[n] > 0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    int res = bellman_ford();
    if(res == -1) puts("impossible");
    else cout << res << endl;
    return 0;
}

SPFA

正权图也可以用 SPFA，卡了换Dijkstra
用来判负环
构造网格图把 SPFA 卡成 mn?

思想

对 Bellman-Ford 优化。
B-F 的思想：

1
2
3
4
5
6
for n 次
	备份
    //遍历了所有边，但每一次迭代不一定会变更所有边
	for 所有边 a b w （表示存在一条从a走向b的边，权重是w）
        //只有 a 变小了 b 才可能变小
		dist[b] = min(dist[b],dist[a]+w)

SPFA 的思想：

1
2
3
4
5
第一个点入队
while queue 非空:
    1. 取出队头t 删掉队头
    2. 更新 t 的所有出边 t-w->b
    如果b不在队列里 入队

判断负环

1
2
3
4
5
6
7
8
9
dist[x] //最短路距离
cntx[x] //最短路经过的边数

dist[x] = dist[t] + w[i]
cnt[x] = cnt[t] + 1 //等于t的最短路边数+当前边

if(cnt[x]>=n)
    //说明经过了n条边，因此至少n+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
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
# include <cstring>
# include <iostream>
# include <algorithm>
# include <queue>

using namespace std;
const int N = 100010;

int n,m;
int h[N];
int e[N],ne[N],w[N],idx;
int dist[N];

bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    
    return;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; 
    
    queue<int> q;
    q.push(1);
    //st数组的目的：防止队列中存重复的点
    st[1] = true;
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        //更新t的所有邻边
        for(int i = h[t]; i!=-1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if(dist[n] > 0x3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
	scanf("%d%d",&n,&m);
	memset(h, -1, sizeof h);
	
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        add(a,b,c);
    }
    
    int res = spfa();
    if ( res == -1)
        cout<<"impossible"<<endl;
    else
        cout<<res<<endl;
    
    return 0;

}

判断负环

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
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

Floyd

思路

基于动态规划的思想

1
2
3
4
5
6
7
8
//构造邻接矩阵d[k,i,j]
//表示从 i 出发，经过点 1-k，到 j 的最短距离
//d[k,i,j] <-update- d[k-1,i,k] + d[k-1,k,j]
//第一维可以去掉
for(int k = 1; k<= n; k++)
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++)
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

代码

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
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;


int n,m,Q;
int d[N][N];

void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
            
    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        
        d[a][b] = min(d[a][b],w);
    }
    
    floyd();
    
    while(Q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b]>INF/2)printf("impossible\n");
        else printf("%d\n",d[a][b]);
    }
    
    return 0;
}

Posted on

问题概述

今天用 npm 自带的脚手架搭建 react 项目，一开始像往常一样一把梭： 

1
2
3
npx create-react-app my-app 
cd my-app
npm start

结果意外发现报错，仔细一看项目文件，只有package.json和node_modules/，像index.html这些文件全都没有。

再一看刚才第一条搭建项目的指令npx create-react-app my-app的控制台输出，发现有点问题： 

1
2
A template was not provided. This is likely because you're using an outdated version of create-react-app.
Please note that global installs of create-react-app are no longer supported.

看样子好像是自带的脚手架过期了，不给初始化模板。

上网搜了下解决方案，发现已经有人踩过同样的坑了。

解决方案

具体步骤如下：

1. 从全局删除 Create-React-App

1
npm uninstall -g create-react-app

然后检查一下是否删除成功 

1
which create-react-app

如果控制台仍然有输出路径，如/usr/local/bin/create-react-app，说明删除没有成功。这时只能强行删掉对应路径： 

1
rm -rf /usr/local/bin/create-react-app

2. 重新执行 NPX Create-React-App

1
npx create-react-app new-project

应该就成功了。

参考资料

https://upmostly.com/tutorials/template-not-provided-using-create-react-app