算法题一年内至少刷三遍！！！
厚积薄发！
New Flag(20190828–): 看paper, 7:30左右起床看。
Tmux简单使用教程
简单理解：不用挂后台，即使shell客户端关闭，命令继续执行。会话和窗口是独立的。
1.安装
|
1 2 3 4 5 6 7 8 |
# Mac $ brew install tmux # Ubuntu 或 Debian $ sudo apt-get install tmux # CentOS 或 Fedora $ sudo yum install tmux |
2.启动或退出
|
1 2 3 4 5 |
# 启动 tmux # 退出 exit |
3.新建会话
|
1 2 3 4 5 |
# 直接新建，默认编号0,1,... tmux # 自定义名称 tmux new -s <session-name> |
4.分离对话：不同于退出，这只是分离，后面还可以继续连接
|
1 |
tmux detach |
5.连接对话
|
1 2 3 4 5 |
# 使用会话编号 $ tmux attach -t 0 # 使用会话名称 $ tmux attach -t <session-name> |
6.杀死对话：等同于进入对话后然后exit
|
1 2 3 4 5 |
# 使用会话编号 $ tmux kill-session -t 0 # 使用会话名称 $ tmux kill-session -t <session-name> |
7.切换对话：进入对话后 然后切换
|
1 2 3 4 5 |
# 使用会话编号 $ tmux switch -t 0 # 使用会话名称 $ tmux switch -t <session-name> |
ref：Tmux 使用教程
另外get：防止Iterm/其他客户端不掉线
- 永久：在/etc/ssh/ssh_config增加ServerAliveInterval 60（每60s向服务器发一次心跳）；
- 暂时：ssh -o ServerAliveInterval=60 hostname@host
awk 简单操作
工作总结…
|
1 2 3 4 |
#实验文本 1^I2$ 3^I4$ 5^I6$ |
1、列操作
|
1 2 3 4 5 |
打印第一列 (base) B00000094065z:~ gongel$ cat a | awk '{print $1}' 1 3 5 |
|
1 2 3 4 5 |
打印最后一列 (base) B00000094065z:~ gongel$ cat a | awk '{print $NF}' 2 4 6 |
|
1 2 3 4 5 |
加一列 (base) B00000094065z:~ gongel$ cat a | awk '{print $0"\ta"}' 1 2 a 3 4 a 5 6 a |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
加一列(按行操作，多此一举) ''' shell脚本 cat $1 | while read line do echo $line | awk '{print $0"\ta"}'; done ''' (base) B00000094065z:~ gongel$ sh ts.sh a 1 2 a 3 4 a 5 6 a |
2、行操作
|
1 2 3 4 5 |
NR为当前处理行 (base) B00000094065z:~ gongel$ cat a | awk '{print NR":"$0}' 1:1 2 2:3 4 3:5 6 |
3、统计命令（BEGIN/END）
|
1 2 3 |
求和 (base) B00000094065z:~ gongel$ cat a|awk '{sum+=$1} END {print "Sum = ", sum}' Sum = 9 |
|
1 2 3 |
求平均 (base) B00000094065z:~ gongel$ cat a|awk '{sum+=$1} END {print "Average = ", sum/NR}' Average = 3 |
|
1 2 3 |
求最大值 (base) B00000094065z:~ gongel$ cat a|awk 'BEGIN {max = 0} {if ($1>max) max=$1 fi} END {print "Max=", max}' Max= 5 |
Round A two 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 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 |
#include <bits/stdc++.h> using namespace std; const int N = 100000, INF = 0x3f3f3f3f; char grid[N][N]; int dist[N][N]; int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int T, r, c; bool is_valid(int mid, int r, int c) { queue<pair<int, int>> queue; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { dist[i][j] = -1; if (grid[i][j] == '1') { queue.push(make_pair(i, j)); dist[i][j] = 0; } } } while (!queue.empty()) { pair<int, int> cur = queue.front(); for (auto &direction:directions) { int x = cur.first + direction[0]; int y = cur.second + direction[1]; if (x >= 0 && x < r && y >= 0 && y < c && dist[x][y] == -1) { dist[x][y] = dist[cur.first][cur.second] + 1; queue.push(make_pair(x, y)); } } } int max_sum = INT_MIN; int min_sum = INT_MAX; int max_sub = INT_MIN; int min_sub = INT_MAX; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (dist[i][j] > mid) { max_sum = max(max_sum, i + j); min_sum = min(min_sum, i + j); max_sub = max(max_sub, i - j); min_sub = min(min_sub, i - j); } } } if (min_sub == INT_MAX) return true; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (abs(max_sum - (i + j) <= mid && abs(min_sum - (i + j)) <= mid) && abs(max_sub - (i - j)) && abs(min_sub - (i - j)) <= mid) { return true; } } } return false; } int main() { cin >> T; int index = 1; while (T-- > 0) { cin >> r >> c; for (int i = 0; i < r; ++i) { cin >> grid[i]; } int low = 0; int high = r + c; while (low < high) { int mid = (high - low) / 2 + low; if (is_valid(mid, r, c)) high = mid; else low = mid + 1; } cout << "Case #" << index << ": " << low << endl; } return 0; } |
Round A one 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; } } |