发表于 | 分类于

复健，时间有限题解比较简陋

A. Middle of the Contest

将小时转成分钟，得到起止时间在一天中的分钟数，取平均值即可，复杂度O(1)。平均值转换会时间的时候注意前导0。

1
2
3
4
5
6
7
8
9
#include<cstdio>

int main() {
  int h0, m0, h1, m1, ans;
  scanf("%d:%d", &h0, &m0);
  scanf("%d:%d", &h1, &m1);
  ans = (h0 * 60 + m0 + h1 * 60 + m1) / 2;
  printf("%02d:%02d\n", ans/60, ans%60);
}

B. Preparation for International Women’s Day

要加起来能被k整除, 只需要看模k的余数即可。余数为i的与余数为k-i的互补可以被k整除，通过计数看有多少对能互补。需要注意的是，为余数为0和k/2（k为偶数）时，只能同余数的互补，此时计数是偶数个时都能配对，奇数个时能配对的数量是计数 - 1。复杂度O(n + 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
#include<iostream>
#include<cmath>
using namespace std;

int cnt[100];

int main() {
  int n, k, x;
  cin >> n >> k;
  while(n--) {
    cin >> x;
    ++cnt[x%k];
  }
  int ans = 0;
  if(cnt[0]) {
    ans += cnt[0] & -2;
  }
  for (int i = 1; i <= k/2; ++i) {
    if(i == k - i) {
      ans += cnt[i] & -2;
    } else {
      ans += min(cnt[i], cnt[k-i]) * 2;
    }
  }
  cout << ans << endl;
  return 0;
}
阅读全文 »

发表于 | 分类于

常见面试题(除了一些字符串匹配相关算法会用到似乎并没有什么实际用处?), 看似简单但却有很多谜一样的case.

最常见的解法就是将字符串切成数组, 再利用数组的reverse方法反转后再拼接起来, 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function reverse(str) {
  return Array.prototype.slice.call(str).reverse().join('');
}

reverse('abcde'); // "edcba"

reverse('我系渣渣辉'); // "辉渣渣系我"

/*
2018-05-15 更新

function reverse(str) {
  return str.split('').reverse().join('');
}

效果相同, 写起来更简洁
*/

这样的做法在遇到四字节字符时会出现问题, 因为在slice的时候一个四字节字符会被分成两个数组元素.

例如里面包含一个笑脸的emoji.

1
reverse('咕嘿嘿😃'); // "��嘿嘿咕"

甚至有些看起来会比较诡异.

1
reverse('是慌?还是慌?还是慌?'); // "?��是还?��是还?慌是"

上面三个”慌”字看上去好像是一样的, 但后面两个”慌”是四字节字符, 甚至这两个”慌”的字符编码也不一样.

那么这又要怎么解决呢?

阅读全文 »

发表于 | 分类于

YApi 是一个可本地部署的、打通前后端及QA的、可视化的接口管理平台

yapi的仓库地址: https://github.com/ymfe/yapi

本人在内网机器不允许访问外网的情况下在内网部署一套yapi, 这里记录下成功的流程.

所需准备的是一台能访问外网的机器(我这里是安装了一个ubuntu16.04的虚拟机, 内网机器操作系统是RedHat6.9), 通过这台外网机器完成所有需要网络的操作. 另外外网机器需要gcc 4.8+(因为在安装yapi依赖时需要build node-sass), 没有gcc或者版本较低需要自行安装升级.

阅读全文 »

发表于 | 分类于

最近基于Promises/A+规范自己实现了一个Promise, 通过了promises-aplus-tests, 并额外使用MutationObserver确保Promise中绑定的处理方法作为microtask执行, 本文用来记录个人实现的思路.
Github: https://github.com/STLighter/PromiseImpl

Promise是一个用来表示异步操作状态的对象, 通过Promise可以将传统回调式的异步操作变成链式的操作, 使代码更加简洁和易读. 关于Promise的具体用法可以参考MDN. 这里主要讲实现, 具体的用法这里不再赘述.

这里的实现主要分以下几步:

  1. 实现构造函数和.then的绑定操作;
  2. 实现.then的链式调用;
  3. 处理外部操作返回Promise对象和thenable对象的情况;
  4. 引入microtask;
  5. 实现catch, finally和静态方法;
  6. 打包以及测试.

其中前4项是核心部分.

阅读全文 »

发表于 | 分类于

上班摸鱼除草…
因为题解代码不是一起写的, 所以代码的逻辑和题解不完全一样, 但基本思路一致…

A. Splitting in Teams

有n个小组, 每组有1人或2人, 现在要将他们组成3人组, 且保证原来的2人组的人还在一起, 问最多能组成几个3人组.

乱搞题, 只有一个1人组和一个2人组或者三个1人组能组成一个3人组, 只用给每个2人组配一个1人组, 多余的1人组3人一组就行了(一个潜在条件是优先组1人组 + 2人组比直接3个1人组组队更优).

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
int main() {
    int n, x, cnt1 = 0, cnt2 = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &x);
        if(x == 1) ++cnt1;
        else ++cnt2;
    }
    int ans = cnt2 <= cnt1 ? cnt2 + (cnt1 - cnt2) / 3 : cnt1;
    printf("%d\n", ans);
    return  0;
}
阅读全文 »

发表于 | 分类于

之前在学校的Win8下面按照官方文档一路顺风顺水, 自己Win10的电脑装起来就磕磕绊绊, Windows系统对开发还是不友好呢.
以及安装的时候尽量全程不要有中文路径, 避免奇怪的bug.

安装Python

从python官网下载合适的版本安装(我这里下的是python 2.7.13 amd64 for windows).
安装的时候选择自动加入环境变量, 或者装完后手动将下面的路径加到环境变量Path中:

C:\Python27\;C:\Python27\Scripts\;

安装成功后可以在控制台查看python版本.

python --version

阅读全文 »

发表于 | 分类于

摸鱼多日, 来随便更一更. 最近JS写的比较多, 所以以后题解的代码就以JS为主了. 这篇题解写了好久, 主要是后面两题搞得有点复杂, 加上各种学校的事情, 拖着写了个把月QAQ.

21. Merge Two Sorted Lists

合并两个有序链表, 链表中数据是从小到大排序的.
这有点像归并排序中归并的过程, 只是这个要在链表上进行归并, 思路还是一样的.
对两个链表头中的值相互比较, 取值较小的那个作为新链的下一个节点, 并将取出的链表头向后移动一位, 并继续这一个过程直到两个链表都被遍历.
复杂度O(N+M), N和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
var mergeTwoLists = function(l1, l2) {
    let head = new ListNode(0); // 空的头节点
    let tmp = head; // 标记链表尾, 方便直接在尾添加
    // 循环直到两个链表都清空
    while(l1||l2) {
        let target; //新链表的下一个节点值
        // 如果两个节点都存在, 获取其中值小的一个
        if(l1&&l2) {
            if(l1.val<l2.val) {
                target = l1.val;
                l1 = l1.next;   // 下一个取l1的头, 下一次将比较l1的下一个节点与l2的头的大小
            } else {
                target = l2.val;
                l2 = l2.next;
            }
        } else {
            // 两个链表中有一个已经遍历完, 其值为null
            if(l1){  
                target = l1.val;
                l1 = l1.next;
            } else {
                target = l2.val;
                l2 = l2.next;
            }
        }
        // 将新值加入新链表尾部
        tmp.next = new ListNode(target);
        tmp = tmp.next;
    }
    return head.next;
};
阅读全文 »

发表于 | 分类于

Round D都要开始了, Round C还没搞定的我(D题不会搞)…另外300+名次也能拿到面试资格呢, 然而做的人却越来越少了.

Problem A. Monster Path

neta某手游…给个R*C的矩形地图, 上面用.和A标注, 走到A上有P的概率抓到妖怪, 走到.上有Q的概率抓到妖怪. 当在一个位置抓过妖怪, 下次经过就抓不到了, 给定起点坐标Rs和Cs, 需要走一条路线使得走S步获得妖怪数的期望最大, 求这个期望.

因为S最大只有9, 直接乱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
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
//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}
int r,c,x,y,s;
double p,q;
bool grid[22][22];
double pro[22][22];
int step[4][2] = {0,1,1,0,0,-1,-1,0};
double ans;
void dfs(int x, int y, int st, double cnt) {
    int tx,ty;
    double tp, tmp;
    if(st!=s) {
        tp = grid[x][y]?pro[x][y]*p:pro[x][y]*q;
    } else {
        tp = 0;
    }
    if(!st) {
        ans = max(ans, cnt+tp);
        return;
    }
    for(int i=0;i<4;++i) {
        tx = x + step[i][0];
        ty = y + step[i][1];
        if(tx>=0&&tx<r&&ty>=0&&ty<c) {
            pro[x][y] -= tp;
            dfs(tx, ty, st - 1, cnt+tp);
            pro[x][y] += tp;
        }
    }
}
void gao(){
    scanf("%d%d%d%d%d",&r,&c,&x,&y,&s);
    scanf("%lf%lf",&p,&q);
    char a,b;
    scanf("%c", &b);
    for(int i=0;i<r;++i) {
        for(int j=0;j<c;++j) {
            scanf("%c%c",&a,&b);
            if(a=='A')
                grid[i][j] = 1;
            else
                grid[i][j] = 0;
            pro[i][j] = 1;
        }

    }
    ans = 0;
    dfs(x,y,s,0);
    printf("%.7f\n", ans);
}
int main()
{
    useFile("A-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}
阅读全文 »

发表于 | 分类于

11. Container With Most Water

如果直接枚举任意两个位置取最大蓄水量, 整体复杂度O(N^2), 将会超时.
考虑如果已知height[i]为短板, 则最优值应选不比height[i]小的最远处的板.
假设短板在右侧, 我们可以枚举每个位置作为短板, 在其左侧找最远的长板.
长板有单调性条件:
如果左侧的两块板中更靠右的板高度却不更高, 则取更靠左的作为长板一定更优.
因此我们可以维护一个单调队列, 从左往右加入, 高度单调递增, 距离单调递减, 在其中二分查找最远的长板.

综合来看, 只需要从左往右枚举每个高度, 对每个高度, 在单调队列中查找不比他矮且离他最远的那个高度, 计算其蓄水量, 然后尝试插入当前高度, 更新队列.

如果短板在左侧, 只需要从右往左维护队列即可.
复杂度O(Nlog(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
class Solution {
public:
    int bs(int i, vector<int>& a, vector<int>& h) {
        int l = 0, r = a.size()-1, mid;
        if(h[a[l]] >= h[i])
            return a[0];
        if(h[a[r]] < h[i])
            return i;
        while(l+1 < r) {
            mid = (l + r)/2;
            if(h[a[mid]] < h[i])
                l = mid;
            else if(h[a[mid]] > h[i])
                r = mid;
            else
                return a[mid];
        }
        return a[r];
    }
    int maxArea(vector<int>& height) {
        vector<int> monotone;
        int l = height.size();
        int ret = 0;
        monotone.push_back(0);
        for(int i=1;i<l;++i) {
            ret = max(ret,height[i]*(i - bs(i, monotone, height)));
            if(height[i]>height[monotone[monotone.size()-1]])
                monotone.push_back(i);
        }
        
        monotone.clear();
        monotone.push_back(l-1);
        for(int i=l-2;i>=0;--i) {
            ret = max(ret,height[i]*(bs(i, monotone, height) - i));
            if(height[i]>height[monotone[monotone.size()-1]])
                monotone.push_back(i);
        }
        
        return ret;
    }
};
阅读全文 »

发表于 | 分类于

发现目前博客的流量基本来自APAC的题解, 就来更一发Round B, 依然是D题Large不会的惯例(什么SB惯例).
感觉这套题难度比Round A大, 练习的时候我一直拍挂small(大概我最近状态不好吧).

A. Sherlock and Parentheses

告诉你L和R, 你要用L个左括号和R个右括号, 组成一个字符串. 问组成的字符串最多有多少个子串是”平衡”的(也就是满足括号匹配的).
比如L = 3, R = 2可以组成字符串()()(, 其中子串1-4, 1-2和3-4都是”平衡”的, 而且其他组合方式最多也只有3个平衡子串, 因此答案是3.

其实就全部组成()的样式排在一起, 多余的放在后面就是最优的匹配方法, 因为(())的形式不会比()()更优(前者只有2组平衡, 后者有3组). 将一个()看作一个位置, 起点终点的取法数就是答案.

复杂度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
//省略头文件
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}
ll l, r;
void gao(){
    scanf("%lld%lld",&l,&r);
    l = l<r?l:r;
    printf("%lld\n", l*(l+1)/2);
}
int main()
{
    useFile("A-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}
阅读全文 »