算法题一年内至少刷三遍！！！
厚积薄发！
New Flag(20190828–): 看paper, 7:30左右起床看。
Round A 2019 – Kick Start 2019
|
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 |
#include<bits/stdc++.h> using namespace std; const int N = 100000, INF = 0x3f3f3f3f; int T, n, p; int a[N], sum[N + 1]; /** * sum[i] - sum[i - p] = a[i-p+1] + a[i-p+2] +...+ a[i] * p * a[i] - (sum[i] - sum[i - p])=(p-1)*a[i] - (a[i-p+1] + a[i-p+2] + ... + a[i-1]) * 假设p=3，i=5 * 那么有3*a[5]- (sum[5] - sum[2])=2 * a[5] - (a[3] + a[4]) = (a[5] - a[3]) + (a[5] - a[4]) * 即每次计算当前元素和前面p-1个元素的差的和，依次遍历取最小值,利用前缀和来优化 * */ int main() { cin >> T; int cnt = 1; while (T-- > 0) { cin >> n >> p; for (int i = 1; i < n + 1; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); int ans = INF; for (int i = 1; i < n + 1; i++) { sum[i] = sum[i - 1] + a[i]; } for (int i = p; i < n + 1; i++) { ans = min(ans, p * a[i] - (sum[i] - sum[i - p])); } printf("Case #%d: %d\n", cnt, ans); cnt++; } return 0; } |
分治：为运算表达式设计优先级
241. 为运算表达式设计优先级
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。 示例 1: 输入: "2-1-1" 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2 示例 2: 输入: "2*3-4*5" 输出: [-34, -14, -10, -10, 10] 解释: (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10 |
|
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 |
import java.util.ArrayList; import java.util.List; public class Twohundred_fortyOne { /** * 分治法 */ public List<Integer> diffWaysToCompute(String input) { if (input == null || input.length() == 0) return new ArrayList<>(); List<Integer> ans = new ArrayList<>(); for (int i = 0; i < input.length(); i++) { char opt = input.charAt(i); if (opt == '+' || opt == '-' || opt == '*') { List<Integer> left = diffWaysToCompute(input.substring(0, i)); List<Integer> right = diffWaysToCompute(input.substring(i + 1)); for (int l : left) { for (int r : right) { switch (opt) { case '+': ans.add(l + r); break; case '-': ans.add(l - r); break; case '*': ans.add(l * r); break; } } } } } if (ans.size() == 0) { ans.add(Integer.valueOf(input)); } return ans; } } |
ELECTRA: 超越BERT, 19年最佳NLP预训练模型
ref：wx
最长数对链
646. 最长数对链
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。 给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 示例 : 输入: [[1,2], [2,3], [3,4]] 输出: 2 解释: 最长的数对链是 [1,2] -> [3,4] 注意： 给出数对的个数在 [1, 1000] 范围内。 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; public class Sixhundred_fortySix { public int findLongestChain(int[][] pairs) { if (pairs == null || pairs.length == 0 || pairs[0].length == 0) return 0; Arrays.sort(pairs, new Comparator<int[]>() { public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); int ans = 1; int temp = pairs[0][1]; for (int i = 1; i < pairs.length; i++) { if (pairs[i][0] > temp) { ans += 1; temp = pairs[i][1]; } } return ans; } } |
信息抽取的几个challenges
- 模型层面：
- 一个字符一个标签的假定无法处理重叠或嵌套块（例如中国教育部部长，部长）
- 以词为基本单位的设定难以应用到无自然边界的语言（如汉语），而以字为基本单位有歧义
- 数据层面：
- 有监督学习依赖于高成本的人工标注数据
- 优化层面：
- 与分类任务不同，信息抽取任务的类别分布有显著差异：正例样本远远少于负例样本；错误和歧义通常集中于某几个特定的类别对之间
