多阶Hash算法

在分布式系统中,会经常用到K-V存储,一般实现的方式有红黑树或者哈希表,在Redis中还用到了跳表。都是通过一个确定的Key值,来查找Key附带的Value属性。本文会介绍一种高效的算法——多阶Hash。

1原理

多阶Hash的实现原理很简单,每个Hash桶数组算作一阶,如果有20阶的多阶Hash,那么就是一个二维数组,第一维是Hash桶的编号,第二维是每个Hash桶的每个槽的位置。实际开发中,可以申请一块连续的内存,由一维数组构造出二维数组。内存构造如下图所示,逻辑上是一个阶梯状,实际申请内存,是一块连续的内存结构,用每次层的阶数来标识出不同阶的分界。如下图所示:

14.2 多阶hash结构

通常每阶的槽的个数都是质数个,每阶的槽的个数依次递减。由于互质的特性,通常情况下会上面的阶数先被填满,然后再逐步填下面的阶数。在实际使用中,内存使用率可以达到90%以上。

查找和插入的时间复杂度都是O(h),h是阶数。

查找操作:对于一个待查找的Key,查找是否在某一阶有被存储,就用Key模除该阶的槽数M,得到Key在该阶存储的下标,然后判断该下标中存储的元素的key是否和待查找的Key相同。如果该阶没有匹配,再依次查找下一阶,如果找到则返回查找成功。如果遍历所有阶都没找到,则返回未找到。

插入操作:先进行查找操作,如果找到已经有存储过该Key,则修改对应位置的元素。如果没有找到该Key,则找到从第1阶到最后一阶中,第一个能存储Key但未分配的位置,把该Key值插入进去。

与教科书中的开链Hash对比,优缺点如下:

2优点

1、查找时间稳定

查找时间和阶数成正比,虽然不一定最高效,但是是可控的,最坏要多少次查找是能够控制的。如果是接链表解决冲突,冲突太多就退化成链表操作,耗时不可控。

2、实现简单

实现完全是数组操作,而且存储内容都是定长。与树形数据结构相比,实现简单很多。

3、方便序列化

由于底层是连续内存,能够通过内存迭代遍历全部元素,dump到外部文件。再通过dump文件重新插入实现恢复数据。

4、鲁棒性强

互联网业务大都是常驻进程,如果进程重启会导致栈或堆中的内存销毁。可以通过共享内存来达到重启后恢复内存数据。由于多阶Hash底层是数组结构,只需要知道起始位置和元素下标,就能够对内存元素进行操作。进程重启后重新挂载内存即可恢复操作,不需要重建索引。

3缺点

1、容量有限

由于阶数有限,如果最后一阶填满后,会导致Key值没有地方存储。不如链表的扩展性好。

在实际项目,要做好容量管理和监控。当发现使用率超过70%的时候,就要准备扩容,防止写满。

2、存储定长

存储的部分是二维数组的Hash桶的块,是一块定长的内存。如果存储的数据是变长的,就需要把内存块定义为最大Value的长度,会造成内存浪费。常见优化方法是在Hash块中存储一个索引,索引指向另外一块内存链表,变长数据被分别存储在多个内存链表中。一般设置每块内存链表的长度也需要计算。

多阶Hash适用于读多写少的互联网业务场景,通常是一个进程负责写操作,多个进程负责读操作。多个进程来提高整体的读的并发量,来弥补每次查找都需要O(h)的复杂度。

多阶Hash是一种在生产实践中总结的算法,从学术上看它并不完美。因为会出现元素存不下的情况,而且时间复杂度的常数系数比较大。但是在互联网读多写少的业务场景中,读速度可控,容量管理能监控,这些问题都能够被解决。同时还带来容易实现,鲁棒性强,内存使用率高的优点。

在实践中得到的这个算法,虽然不是十分优美,但是真的十分实用。

简单高效的排行榜算法——树状数组

0 问题场景

在互联网业务中,为了刺激玩家活跃度,通常都会制作榜单,让用户能够看到自己在榜单中的名次。用户要看到的内容是:新的分数排行是多少名,相比之前是前进了,还是后退了,具体前进后退的数值是多少。例如充值排行榜,游戏分排行榜,活跃度排行榜等。由于互联网用户基数大,有些平台参与排行的用户可以达到上千万。但是排行榜最重要的就是时效性,能够让用户越早看到排行更新越好。

对于庞大的榜单,每次其中一个元素更新,都要重新排序,即使用快速排序,对CPU运算的消耗都是巨大的,很容易造成卡顿。很多互联网业务都采用离线定时更新榜单的方案。例如每天凌晨4点的数据切片,离线排序更新,更新后展示最新的榜单。这种方案在程序性能和用户体验间做了折衷,既保证了每天更新,又不至于实时更新导致运算量太大,算不出来。

有没有更高的解决方案,可以实时查看用户排行变化呢?一个有序的排行榜,只是一个用户的数据发生变化,就要所有数据重新排序,能只做到部分排序吗?

对于这两个问题,可以利用一种高级的数据结构「树状数组」,再结合对排行榜的算法来实现。

1 排行榜实现及优化方案

我们先梳理下排行榜的通用实现方案,再查看下针对具体的步骤进行优化。
一个通用排行榜的实现方案步骤如下:

  1. 已经有一个排好序的排行榜;
  2. 当用户分数有更新时,保存用户老的排行榜名次和老的分数;
  3. 更新用户新的分数,并更新排行榜,获取新排行名次;
  4. 展示新老名次的差异,结束。

难点就在第二点,如何更新排行榜。最简单粗暴的想法是,更新排行榜中对应的分数,然后调用快速排序对数组再重新排序一次。快速排序时间复杂度是nlog(n)的,如果有1000万人参与,每次就要进行上亿次的比较。如果每秒有一千个玩家修改分数,要执行千亿次运算。对于排行榜系统的性能消耗是巨大的,做不到实时展示排行数据更新。

原先已经排好序的数组,只有一个元素的值发生了变化,其他元素的相对顺序是不用更改的。从这个角度来优化程序,能够做到快速实现排序优化。使用树状数组,能够做到修改和查询都是log(n),那么对于1000万人参与的榜单,比较次数最多只需要23次,一千个玩家每秒修改,只需要23000次比较。单进程都可以承受住。而且树状数组底层是构建在数组之上的,数据结构简单,容易持久化,能够方便地保存在共享内存中。当常驻进程重启时能够快速恢复。

说了树状数组这么多好处,这么适合排行榜业务的实现,下面我们来介绍下树状数组的原理,以及在排行榜业务中使用的方法。

2 树状数组实现排行榜

我们利用树状数组来实现排行榜功能,能够在Olog(N)的复杂度实现查询和修改功能。下面先介绍树状数组的原理,再介绍如何利用树状数组来实现排行榜。由于涉及到学习算法,还有应用。本节的两个内容需要对照查看才能理解,建议对下面两小节的内容,先概览熟悉基本概念,再逐渐研究细节。并没有严格的先后顺序之分。

2.1 树状数组原理

树状数组(Binary Indexed Tree),又以其发明者命名为Fenwick树。可以在O(logn)时间内得到数组任意前缀和,并能够在O(log(n))时间内支持动态单点的值的修改。空间复杂度是O(n)。

所有的正整数,都可以表示为2的幂和。 N=\sum_{i=1}^m2^{ki} ,ki为二进制表示时,为1位的位置。

例如34=2^1+2^6;12 = 2^2+2^3;

我们设一个整数数组元素个数为N,数组名为A,包含元素为A_{j}(1<=j<=N)

对于一个整数i,lowbit(i)表示i的二进制最后一个位置1,所代表的值。(例如lowbit(12)= 4,lowbit(34)=2)

构造树状数组 BIT_{i} = \sum_{j=i-lowbit(i)+1}^{i}A_{j}

BIT[i]=A[i-lowbit(i)+1] + A[i-lowbit(i)+2] + ... + A[i]

所表示的数学意义为,下标为i的树状数组元素,为原数组A[i]往前lowbit(i)个元素的和(包括A[i])。

对于树状数组元素BIT[i],可以画一棵树表示,树中的父节点表示的区间和,覆盖子节点表示的区间和。

下图为i=8时画出的树。

树状数组是在数组上建立的一种树形关系结构。

以上图为例,A数组是原始存储数据的数组,有8个元素。C数组是按照每个下标覆盖2次幂范围得到的新的子序列和的数组。

BIT1 = A1 (1的二进制表示为1,有0个0,覆盖1个元素)

BIT2 = A1 + A2(2的二进制表示为10,有1个0,覆盖2个元素)

BIT3 = A3(3的二进制表示为11,有0个0,覆盖1个元素)

BIT4 = A1 + A2 + A3 + A4(4的二进制表示为100,有2个0,覆盖4个元素)

BIT5 = A5(5的二进制表示为101,有0个0,覆盖1个元素)

BIT6 = A5 + A6(6的二进制表示为110,有1个0,覆盖2个元素)

BIT7 = A7(7的二进制表示为111,有0个0,覆盖1个元素)

BIT8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8(8的二进制表示为1000,有3个0,覆盖8个元素)

有了树状数组BIT[i],我们就可以实现求原数组A[i]的前缀和,还有A[i]中单个元素修改时快速更新BIT[i]数组的功能

一、求原数组A的前缀和

假设求原数组A的前i个元素的和Sum[i],对于整数区间[1,i],可以表示为两个区间[1, i-lowbit(i)],[1-lowbit(i), i]。

如果设j=i-lowbit(i),那么j<=i并且Sum[0] = 0,则Sum[i] = Sum[j] + BIT[i];之后再逐步求解Sum[j],直到递推到Sum[0] = 0,便计算出前缀和Sum[i]。

二、原数组某个元素A[i]修改,同步修改树状数组BIT

当某个元素A[i]修改时,所有包含A[i]的树状数组元素BIT[j]都要进行相应的修改。

对于A[i],BIT[i]肯定包含A[i]的和。再根据上面的树形结构,

BIT_{i_{k+1}} = BIT_{i_{k}} + lowbit(i_{k}) 其中 (i_{0}=i, i_{k+1}<=N)

2.2 代码实现

根据上一小节的分析,可以用代码实现树状数组。
对于求lowbit(n),可以用n&(n^(n-1))得到,由于在C++中用补码表示负数,可以写为n&(-n)。用函数封装为

int lowbit(int x)
{
    return x & (-x);
}

求数组A的前i项和为

int sum(int i)//求前i项和 
{ 
    int s=0; 
    while(i>0) 
    { 
        s+=BIT[i]; 
        i-=lowbit(i); 
    } 
    return s; 
}

修改原数组A[i]元素,增加val值

void add(int i,int val) 
{ 
    while(i<=n) 
    { 
        BIT[i]+=val; 
        i+=lowbit(i);  
    } 
}

2.3 树状数组优化排行榜

如何使用树状数组来实现排行榜的需求呢?要经过一些转化。

我们把要排行的分数划定一个区间范围。假设分数都是整数,最大值MAX_SCORE为1,000,000分。

则原始数组A[i]表示具有分数为i的值的用户数量,然后求出BIT[i]数组。假设一个人的分数为j,则排名为BIT[MAX_SCORE]-BIT[j-1]。

利用上小节的代码很容易就实现了。

排行榜封装的代码如下

const int MAX_SCORE = 1000000;
int BIT[MAX_SCORE + 1]={0};//初始时所有分数的人数都是0
while(true)
{
    int uid, newScore, oldScore;
    GetUserInfoReq(&uid, &newScore, &oldScore);//假设收到请求,获得uid用户的最新分数为newscore,上次更新分数为oldscore;
    int oldRank = sum(MAX_SCORE)-sum(oldScore)+1;//查询旧排名
    //更新为新排名
    add(oldScore, -1);//先给旧分数的人数减一
    add(newScore,  1);//再给新分数的人数加一
    int newRank = sum(MAX_SCORE)-sum(newScore)+1;
    //返回用户新排名newRank,和老排名oldRank供前端展示
    SetUserInfoRsp(uid, newScore, newRank, oldScore, oldRank);
}

可以把用户的分数数据存储在用户资料中,排行榜模块只存储树状数组用来排名。最开始初始化时,可以遍历所有用户资料,获取每个用户的score,然后调用add(score, 1)完成全部初始化。之后用上面的代码,在每次分数有更新的时候调用获取排名变化。

核心代码只有30几行,而且由于是存储在数组中,一块连续的内存,可以把树状数组放到共享内存中。即使进程重启,也能够马上恢复服务。

使用树状数组有前提条件:

1、就是不能存储分数为0的玩家的排名;

2、分数要都是整数;

3、要有上限,最大不能超过MAX_SCORE范围。

虽然有诸多限制,但都能通过业务逻辑处理。如果分数有小数,可以乘以相应的倍数,转换成整数。例如充值1.01元,可以把单位转换成分来存储101分。上限可以根据业务逻辑调整,即使正整数的最大表示2^32,log(n)也只需要32次处理,远远小于O(n)的处理。

如果要突破限制,需要在业务层面和实现逻辑上再做些转换,一般都可以很好解决。

3 小结

对于排行榜需求,通过树状数组,能够实现实时更新和展示实时变化。排行榜实时更新的瓶颈是单值修改,整体排序。树状数组能够做到单值修改,部分更新,优化掉了排行榜瓶颈。

在实际开发中,遇到问题,要先梳理问题的步骤,找到瓶颈。针对瓶颈进行学习研究,对于高级数据结构要有所了解,在实际开发中,合理运用,能够达到简化开发,提升项目稳定和效率好处。同时在使用的过程中注意边界条件,让一些产品设计在边界条件内,能够达到产品特性用户满意和程序实现复杂度降低的双赢局面。

Leetcode 第137场周赛解题报告

今天的比赛的题目相对来说比较「直白」,不像前几周都是一些特定的算法,如果你没学过不可能想出来。

做了这些周,对leetcode比赛的题目也发现了一些「规律」。 一般前两道题都很「简单」,只要有想法,直接敲代码就能解出来。更多考察的是结果是否正确,速度其次。

后两道题有些难度 ,不同场次难度不一样,也可能和不同人的水平感受不同。但是肯定比前两道要难。

一般在做后两道题的时候,只要复杂度是对的,一些细节也不用考虑太多。例如数组开的空间大小,一些线性的提前剪枝判断,写不写都可以过。最主要的是复杂度是同一个量级的。

相信leetcode这么设计是为了「人性化」,让选手更关注比赛题目核心,能够在一个半小时内完成比赛题目。

总之leetcode的比赛还是很人性化,很注重主要考点,不纠结于细节。利用这些特性,可以在比赛中排除一些错误想法。

下面是详细的题解和思考。


比赛的地址 Weekly Contest 137

https://leetcode-cn.com/contest/weekly-contest-137

1. 最后一块石头的重量

题目:

最后一块石头的重量(Last Stone Weight)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight/

题意:

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

思路:

一个数组,每次把最大的两个数拿出来相减,然后把绝对值放回原数组。一直重复到最后只剩下一个元素,输出即可。

典型的模拟题,按照题目的意思写即可。可以用堆来实现,每次拿堆顶的两个最大元素。

由于是第一题,每次都排序一遍,也能通过。不过在日常工程中,还是老老实实用堆来实现吧。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue< int > q;
        for(auto &stone : stones)
        {
            q.push(stone);
        }
        while(q.size()>1)
        {
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            int z = abs(x-y);
            q.push(z);
        }
        return q.top();
    }
};

2. 删除字符串中的所有相邻重复项

题目:

删除字符串中的所有相邻重复项(Remove All Adjacent Duplicates In String)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/remove-all-adjacent-duplicates-in-string/

题意:

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路:

类似于游戏「爱消除」,相同的两个字母抵消掉,形成的新字符串再接着抵消,直到稳定为止。

用栈来实现,遍历字符串的每个字符。如果栈为空,则插入字符,否则比较字符和栈顶元素,相同则弹出栈顶元素,不同则压栈。

最后输出栈内的字符串即可。

代码:

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(auto ch : S)
        {
            if(st.empty())
            {
                st.push(ch);
            }
            else
            {
                if(st.top()==ch)
                {
                    st.pop();
                }
                else
                {
                    st.push(ch);
                }
            }
        }
        string res;
        while(!st.empty())
        {
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

3. 最长字符串链

题目:

最长字符串链(Longest String Chain)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/longest-string-chain/

题意:

给出一个单词列表,其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1 是 word2 的前身。例如,”abc” 是 “abac” 的前身。

词链是单词 [word_1, word_2, …, word_k] 组成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此类推。

从给定单词列表 words 中选择单词组成词链,返回词链的最长可能长度。

思路:

这道题本质是图算法。

分两步解:

第一步先构造出每个单词之间的关系,判断任意两个单词是为前身后继关系。构造完关系就能画出了图。

第二步就是求解这个图中最长路径。由于是单向有向图,而且没有环。

构造一个集合,每次给集合放入新的点A,都判断集合中其他的点到该点的距离,取最大值为集合内部到新点A的最大距离L。下次再加入新的点A1,如果A和A1连通,则集合到A1的距离为L+1。

由于终点有多个,最后要遍历所有点的最长距离。

其实这道题的思想和Dijkstra算法是一样的。

代码:

class Solution {
public:
    bool canChange(string& s1, string& s2)
    {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1+1!=len2)
            return false;
        int i=0;
        int j=0;
        while(j<len2)
        {
            if(s1[i]==s2[j])
            {
                ++i;
                ++j;
            }
            else
            {
                ++j;
                if(j-i>1)
                {
                    return false;
                }        
            }
        }
        return true;
    }
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> g(n, vector<int>(n, 0));
        sort(words.begin(), words.end(), [](string& w1, string& w2)
             {
                 return w1.length()<w2.length();
             }
            );
        for(int i = 0; i < n; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                if(canChange(words[i], words[j]))
                {
                    g[i][j] = 1;
                }
            }
        }
        vector<int> lcnt(n, 1);
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(g[j][i])
                {
                    int tmp = lcnt[j]+1;
                    lcnt[i] = max(tmp, lcnt[i]);
                }
            }
        }
        return *max_element(lcnt.begin(), lcnt.end());
    }
};

4. 最后一块石头的重量 II

题目:

最后一块石头的重量 II(Last Stone Weight II)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight-ii/

题意:

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

思路:

和第一题的题意只有一句差别,就是每次拿石头是「任意」的。问最后能消掉剩余的最小值是多少。

一般最开始可能想到用贪心,但实际上没有这种算法的。

由于石头碎掉之后还能放回去,类似于把石头分成两堆来看。只要依次拿两堆的石头互相粉碎,最后剩下的就是最小整数。

最多有100个石头,每个石头最多300的重量。所以两个集合最大的差值不会超过30000。

用数组构造结果。

在加入第n个石头重量为m时,查找n-1个石头能够组成的两堆石头的差值的绝对值为diff。

该石头两个选择,放入多的堆,则差值更大,为diff+m;
放入小的堆,则差值为|diff-m|。这时更新n个石头能组成的所有重量。

最后输出最后一个石头能组成的最小重量即可。

代码:

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int diff[101][30001]={0};
        int sum = 0;
        int n = stones.size();
        for(int i=0;i<n;++i)
        {
            sum+=stones[i];
        }
        diff[0][stones[0]] = 1;
        for(int i=1;i<n;++i)
        {
            for(int j=0;j<=sum;++j)
            { 
                if(diff[i-1][j])
                {
                    diff[i][j+stones[i]] = 1;
                    diff[i][abs(j-stones[i])] = 1;
                }
            }
        }
        for(int i = 0; i <= sum; ++i)
        {
            if(diff[n-1][i])
            {
                return i;
            }
        }
        return 0;
    }
};

Leetcode 第136场周赛解题报告

周日的比赛的时候正在外面办事,没有参加。赛后看了下题目,几道题除了表面要考的内容,还是有些能发散扩展的地方。

做题目不是最终目的,通过做题发现知识盲区,去研究学习,才能不断提高。

理论和实际是有关系的,一些题目也都有现实意义。计算机的一些模拟操作,通过数学算法,能够大大减轻代码量和算法复杂度。

第一题是机器人在坐标系上直走和转弯,通过简单的模拟就能实现。但是仔细思考发现还能通过线性代数,坐标变换的方式做,这样在实际中计算更快。甚至还可以用复数来做。

实际扫地机器人可能就用到了类似的算法。让他能够不至于始终原地打转。

第四题是典型的后缀树、后缀数组应用,找字符串最长重复子串。在搜索引擎,或DNA检测中,都是有实际使用场景的。在70年代就已经有应用了,是一个很经典的算法。而且在90年代至今,一直有科学家提升创建后缀树和后缀数组的时间复杂度。这个算法也是在不断发展的。而且在2016年中国的李志泽,李建和霍红卫三位科学家提出了线性时间复杂度,常数空间的最优构造算法。是中国人对算法的贡献。

下面是详细的题解和思考。


比赛的地址 Weekly Contest 136

https://leetcode-cn.com/contest/weekly-contest-136

困于环中的机器人

题目:

困于环中的机器人(Robot Bounded In Circle)

地址:

https://leetcode-cn.com/contest/weekly-contest-136/problems/robot-bounded-in-circle/

题意:

在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。机器人可以接受下列三条指令之一:

“G”:直走 1 个单位
“L”:左转 90 度
“R”:右转 90 度

机器人按顺序执行指令 instructions,并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时,返回 true。否则,返回 false。

思路:

假设机器人重复走N次指令后,面朝北:

此时如果坐标在原点,则N次循环后就会重复从前的路径。

如果坐标不在原点,此时把当前位置当作原点,就会每N次移动远离一段和当前原点的距离。距离最初的(0,0)位置越来越远。就不存在循环会最原始原点的问题。

其实至多经过四次,机器人就会面朝北。

经过一次指令后,机器人面朝西或东,相当于逆时针或顺时针转了90度,则再经过三次,就面朝北了。

经过一次指令后,朝南则转了180度,共移动两次指令后朝北。

数学方法:

还可以把指令集先计算一遍,得出经过一个指令集后的相对移动位置和方向转角。用矩阵计算,就不用每次都运行一大堆指令模拟,加快运算速度;

还可以用复数来运算,复数对于转90度有简单的运算方法。

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0;
        int y = 0;
        int i = 0;
        int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        do
        {
            for(auto ch : instructions)
            {
            if(ch=='G')
            {
                x+=dir[i][0];
                y+=dir[i][1];
            }
            else if(ch=='R')
            {
                ++i;
                i%=4;
            }
            else
            {
                i+=4;
                i--;
                i%=4;
            }
            }   
        }while(i!=0);
        if(x==0&&y==0)
            return true;   
        return false;
    }
};

不邻接植花

题目:

不邻接植花(Flower Planting With No Adjacent)

地址:

https://leetcode-cn.com/contest/weekly-contest-136/problems/flower-planting-with-no-adjacent/

题意:

在一个无向图中,每个点的出度都不超过3。有四种颜色,给每个点着色,要求有边相连的点颜色不同。

给出着色方案。

思路:

由于每个点出度不超过3,四个颜色,肯定可以有解。暴力枚举即可。由于图的点很多,边少。在寻找和点相连的点时,不要按点遍历,要按边遍历,否则会超时。

代码:

class Solution {
public:
    map<int, map<int, int>> mr;
    vector<int> res;
    int dfs(int index, int N)
    {
        if(index > N)
            return 0;
        for(int color=1;color<=4;++color)
        {
            res[index-1] = color;
            map<int, int> & tmp = mr[index];
            bool flag = false;
            for(auto it=tmp.begin();it!=tmp.end();++it)
            {
                if(res[it->first-1]==color)
                {
                    flag = true;
                    break;
                }
            }
            if(flag == true)
                continue;
            int ret = dfs(index+1, N);
            if(ret == 0)
                return 0;
        }
        return -1;
    }
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        res.resize(N, 0);
        for(int i=0; i<paths.size(); ++i)
        {
            int x = paths[i][0];
            int y = paths[i][1];
            mr[x][y] = 1;
            mr[y][x] = 1;
        }
        dfs(1, N);
        return res;
    }
};

分隔数组以得到最大和

题目:

分隔数组以得到最大和(Partition Array for Maximum Sum)

地址:

https://leetcode-cn.com/contest/weekly-contest-136/problems/partition-array-for-maximum-sum/

题意:

给出整数数组 A,将该数组分隔为长度最多为 K 的几个(连续)子数组。分隔完成后,每个子数组的中的值都会变为该子数组中的最大值。

返回给定数组完成分隔后的最大和。

思路:

该问题可以划分为子问题求解。

设数组有N个元素A[0]A[1]…A[N-1],sum(i)表示从A[i]~A[N]求解的最大和。

则sum(i) = max( max(A[i]-A[i+m-1])*m + sum(m) ) 其中i<=m<=k;

就是每个从i开始到数组结尾的最大和,等于前m个元素单独划分,再加上剩下元素的最大和。这k中划分方案最大的,就是从i开始到数组结尾最大和最大的。

依次计算到第0个位置结束。

为了计算统一,会用到sum(n),实际没有这个元素,初始化零计算即可。

代码:

class Solution {
public:
    int dp[501]={0};
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        int n = A.size();
            for(int i = n-1; i>=0; --i)
            {
                int ma = 0;
                int j;
                for(j=i;j<i+K && j < n ;++j)
                {
                    ma = max(ma, A[j]);
                    dp[i] = max(dp[i], ma*(j - i + 1) + dp[j + 1]);
                }
            }
        return dp[0];
    }
};

最长重复子串

题目:

最长重复子串(Longest Duplicate Substring)

地址:

https://leetcode-cn.com/contest/weekly-contest-136/problems/longest-duplicate-substring/

题意:

给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。

返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 “”。)

思路:

后缀数组教科书般的例题。

后缀数组是后缀树的一种变种,能够节省空间。构造的方法有「倍增算法」,「DC3算法」。

主要思想:

设字符串为S(1-n)由n个字符组成。则字符串有n个相同后缀的子串。分别为s(1-n),s(2-n),…,s(n-n)。

然后构建一个SA数组,每个数组存储这些后缀的子串,存储后进行字典序排序。

最后构造出一个height数组,表示SA数组每个元素和前一个元素相同前缀的字符个数。

那么,最长重复子串的长度就是height数组的最大值。

因为最长重复子串一定是两个不同后缀的公共前缀,而且这两个不同后缀的字典序排列后一定是相连的。否则一定有比他更长的。

所以height的最大值能够找到那两个后缀,然后提取公共前缀就找到答案。

代码:

namespace SA
{
bool cmp(int *r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int str[], int sa[], int rank[], int height[], int n, int m)
{
    n++;
    int i, j, p, *x = t1, *y = t2;
    for (i = 0; i < m; i++)
        c[i] = 0;
    for (i = 0; i < n; i++)
        c[x[i] = str[i]]++;
    for (i = 1; i < m; i++)
        c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--)
        sa[--c[x[i]]] = i;
    for (j = 1; j <= n; j <<= 1)
    {
        p = 0;
        for (i = n - j; i < n; i++)
            y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;
        for (i = 0; i < m; i++)
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[y[i]]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
    int k = 0;
    n--;
    for (i = 0; i <= n; i++)
        rank[sa[i]] = i;
    for (i = 0; i < n; i++)
    {
        if (k)
            k--;
        j = sa[rank[i] - 1];
        while (str[i + k] == str[j + k])
            k++;
        height[rank[i]] = k;
    }
}
int num_rank[MAXN], height[MAXN];
int num[MAXN];
int sa[MAXN];
} // namespace SA

class Solution
{
  public:
    string longestDupSubstring(string S)
    {
        using namespace SA;
        int pos = 0;
        int len = 0;
        int n = S.length();
        for (int i = 0; i <= n; ++i)
        {
            num[i] = S[i]&0x3f;
        }
        num[n] = 0;
        da(num, sa, num_rank, height, n, 256);
        for (int i = 2; i <= n; ++i)
        {
            if (height[i] > len)
            {
                pos = sa[i];
                len = height[i];
            }
        }
        return S.substr(pos, len);
    }
};

Leetcode 第135场周赛解题报告

这周比赛的题目很有特点。几道题都需要找到一定的技巧才能巧妙解决,和以往靠数据结构的题目不太一样。

就是如果懂原理,代码会很简单,如果暴力做,也能做出来,但是十分容易出错。

第四题还挺难想的,想了好久才想明白。这次先讲第四题,然后再讲其他的题目。

下面是详细的题解和思考。


比赛的地址 Weekly Contest 135

https://leetcode-cn.com/contest/weekly-contest-135

移动石子直到连续 II

题目:移动石子直到连续 II(Moving Stones Until Consecutive II)

地址:

https://leetcode-cn.com/contest/weekly-contest-135/problems/moving-stones-until-consecutive-ii/

题意:

在数轴上摆放了n个石子,石子位置都是整数,并且不能重叠。游戏规则是:每个回合,将一颗端点石子拿起并移动到一个未占用的位置,使得该石子不再是一颗端点石子。无法移动时游戏停止。

问最小和最大移动次数分别是多少。

思路:

题目是上周第一题的扩展,但是有点不同。

由题意可知,每进行一轮操作,石子的左右端点的距离会缩短,一轮一轮收敛。最后会石子都紧邻游戏结束。

举个例子:

初始时有8颗石子,在数轴上的有石子的刻度为:

4,6,8,9,15,16,19,20

最大值求解方法:

石子可以放置的空间,等于左右两端石子之间的未占用位置。在例子中,一共有20-4+1-8个位置。

石子覆盖的线段长度是20-4个,加上一个端点的位置即20-4+1,再减去已经占用的8个位置。

用公式表示为

s1=stones[n-1]-stones[0]+1-n

但是第一次移动的左端点或右端点的石子后,这个移动的石子和它相邻的那颗石子之间的空间,后面就不能被放置了,因为与他相邻的那个点变为端点,他们之间的位置不可以被放置了。

例如第一步移动了4,那么5这个位置就不可能放置石子了。所以要计算不能被访问的空间

s2=min(stones[n-1]-stones[n-2]-1, stones[1]-stones[0] -1)

最大值为s1-s2。因为在后面的步骤里,我们都可以做出策略,让每一轮左右端点的差值只减1。

最小值求解方法:

如果最后游戏结束,那么一定有n个连续坐标摆满了石子。如果我们要移动最少,必定要找一个石子序列,使得在n大小连续的坐标内,初始时有最多的石子。

设想有个尺子,上面有n个刻度点,我们用这个尺子在石子从最左边到最右边移动,每动一次都查看下在尺子范围内有m个石子,那么要使这个区间填满,就需要移动n-m次。

只要在尺子外部有石子,就有策略填满尺子内的。

这些次数中最小的就为虽少次数。

但是有一种特例:

1,2,3,4,7

这种1-4是最好的序列,但是7不能移动到端点,只能1先移动到6,然后7移动到5解决,这种情况要用2步。就是尺子内的石子都是连续的,中间没空洞,只在边上有空,要用2次。

代码:

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(),stones.end());
        int n = stones.size();
        int mx = stones[n - 1] - stones[0] + 1 - n;
        mx -= min(stones[n-1]-stones[n-2] - 1, stones[1]-stones[0] -1);
        int mi = mx;
        int i = 0;
        int j = 0;
        for(i = 0; i < n; ++i)
        {
            while(j + 1 < n && stones[j + 1] - stones[i] + 1 <= n)
                ++j;
            int cost = n - (j - i + 1);
            if(j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1)
                cost = 2;
            mi = min(mi, cost);
        }
        return vector<int>{mi, mx};
    }
};

有效的回旋镖

题目:有效的回旋镖(Valid Boomerang)

地址:

https://leetcode-cn.com/contest/weekly-contest-135/problems/valid-boomerang/

题意:

回旋镖定义为一组三个点,这些点各不相同且不在一条直线上。
给出平面上三个点组成的列表,判断这些点是否可以构成回旋镖。

思路:

题目说是回旋镖,其实就是三角形。只要能判断三点不共线就可以。

方法一:简单的想法可以用斜率和截距的方法,判断三点共线。

缺点:要用到除法,可能有精度问题,而且要考虑和坐标轴平行的特殊情况。

方法二:利用三角形变长的性质,两边之和大于第三边。

缺点:也存在用开方的操作,可能有精度问题。

方法三:最优的方法。利用向量叉积。因为a×b=|a|.|b|sinθ。如果共线sinθ为0。

向量叉积后还是的向量,这个向量的长度是两个向量所组成平行四边形的面积。如果共线,这个值为0。

具体可以参考维基百科:

https://zh.wikipedia.org/wiki/%E5%8F%89%E7%A7%AF

叉乘公式

代码:

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1=points[0][0],y1=points[0][1];
        int x2=points[1][0],y2=points[1][1];
        int x3=points[2][0],y3=points[2][1];

        int cross = (y3-y1)*(x2-x1) - (y2-y1)*(x3-x1);
        return cross != 0;
    }
};

从二叉搜索树到更大和树

题目:

从二叉搜索树到更大和树(Binary Search Tree to Greater Sum Tree)

地址:

https://leetcode-cn.com/contest/weekly-contest-135/problems/binary-search-tree-to-greater-sum-tree/

题意:

修改树的每个节点的值,为访问的所有节点的和,包括当前节点。
访问的次序是先访问右子树,再访问根节点,再访问左子树。

思路:

代码比较简单,递归实现。

代码:

class Solution {
public:
    int ans = 0;
    TreeNode* bstToGst(TreeNode* root) {
        if(root==nullptr)
            return root;
        bstToGst(root->right);
        ans+=root->val;
        root->val=ans;
        bstToGst(root->left);
        return root;
    }
};

多边形三角剖分的最低得分

题目:多边形三角剖分的最低得分(Minimum Score Triangulation of Polygon)

地址:

https://leetcode-cn.com/contest/weekly-contest-135/problems/minimum-score-triangulation-of-polygon/

题意:

想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], …, A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

思路:

选定凸多边形的一条边为底(A[0]A[N-1]组成的线段),和A[i]为顶点,可以把凸多边形分为三部分,左侧A[0]A[1]…A[i]组成的凸多边形,右侧A[i]A[i+1]…A[N-1]组成的凸多边形,还有A[0]A[i]A[N-1]组成的三角形。

两个凸多边形还可以再递归分解,最后比较出最优解。递归算过的形状不用重复计算,可以用记忆化搜索,记录中间结果。

如果凸多边形只有两个点,那么组成不了三角形,可以直接返回权值为0。

递推公式为:

设w(i,k,j)为i,j,k三个点组成的三角形的权值。

v[i][j]=0 (当i+1==j时)

v[i][j]=v[i][k]+v[k][j]+w(i,k,j)

(当i + 1 < j时, i < k < j)

代码:

class Solution {
public:
    int memo[51][51]={0};
    inline int w(int i, int j, int k, vector<int>& A)
    {
        return A[i]*A[j]*A[k];
    }
    int dfs(int i, int j, vector<int>& A)
    {
        if(i==j-1)
            return 0;

        if(memo[i][j]!=0)
            return memo[i][j];

        memo[i][j]=INT_MAX;
        for(int k = i+1; k < j; ++k)
        {
            int ans = dfs(i, k, A) + w(i, k, j, A) + dfs(k, j, A);
            memo[i][j] = min(ans, memo[i][j]);
        }
        return memo[i][j];
    }
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();

        return dfs(0, n-1, A);

    }
};

如何当好面试者

如何当好面试者

经过对一些面试者的观察,如果有些方面做的更好一点,会大大增加面试的效率,提升通过面试的概率。希望即将参加面试的同学,能够从以下这些点得到帮助。

明确的目标

在参加面试之前,要先思考好面试的目的。为什么去面试?即将参加的这场面试,如果通过之后,是否满足你的要求。

如果确定要去参加,要对面试的公司,面试的岗位做些功课。知己知彼百战不殆。了解多一分,过的可能性就大一分。

准备简历

简历要包括以下这些内容,而且顺序也依次排列:

  1. 姓名,联系方式,面试职位
  2. 学习经历和学习过程中获奖情况
  3. 工作经历和突出业绩
  4. 技术擅长点
  5. 其他

宗旨是,让面试官或简历筛选者,能够在几秒钟,就能发掘你,看到你的重点信息。简历最好控制在一页纸,突出重点内容。

内容短,不代表内容少。要精心准备,对自己的长处短板有充分的了解,对过往的工作有总结。把重要的内容,简洁地写上去。

无关主题就不要贴了,如果面试程序员,是否会做饭关系不大,还浪费两行字的空间。

面试准备

看书:一般面试都会有笔试,考一些专业知识。如果准备面试,要做些复习,对一些基础知识和概念要充分了解。

即使是从前做的项目,也要准备下,对细节,数据做些总结。在被问到时能够对答如流。如果吞吞吐吐,会让面试官怀疑真实性。

做好面试公司的功课,对公司的业务,规模有所了解。在互联网上,都是公开信息。

面试过程

面试过程中,要做好及时反馈,让面试过程顺利进行。

如果面试官出题,要先复述下对题目的理解,防止读错题意。在做题的过程中,先说思路,再写代码,或进入下一步解题。如果思路有错误,面试官会给予提示,节约面试时间,能够让面试官做到尽量全面考察。

如果题目没思路,尽早说想不起来,或者过一会再解答。不要一直卡在那里,白白浪费掉面试时间。也可以和面试官说自己擅长哪些方面,在简历里要交代清楚。有些面试者什么都写精通,但问又答不好。要让面试官不停地探测擅长哪些知识,如果探测不对,最后面试者很难通过。

面试者要能引导面试官,让面试官知道自己擅长哪些。在介绍项目的时候,也突出重点,做过的项目哪里做的最好,克服了哪些困难。

总之,要在短短的一个小时里,展示你的才能,让面试官知道你是要找的人才。

即使面试没通过,也要总结,为后面的面试打基础积累经验,也可以过半年之后,再重新回来面试。

总结

功夫在平时,面试的结果和平时的努力分不开。在平时要多刨根问底,探究问题的根本原因。多总结,定期总结工作要点内容。对基础知识要不断学习和强化,就像手艺人一样,这是安身立命的技能,不能丢。

如何当好面试官

今年面试的人比较多,加起来快一百人了。由于面试任务比较多,也有越来越多的小伙伴加入了面试官的行列。

总结一些面试相关的方法论,希望新晋面试官有些帮助,最终能高效面试。

必备思维

面试官的目标是为组织找到合适的人,一切行为都是围绕这个主体来运作的。我们现在的面试还是类似于考试,这是一种能够在短时间内高效选择到合格面试者的方法。

存在误杀:和高考一样,面试不合格的人,也可能做好招聘岗位的工作。存在可能性,但是我们要通过面试题的设计,让这种概率尽可能小。

面试是为了选人才,不是为了难住面试者。所有的问题都结合面试岗位的要求,如果判断能胜任即可,我们的目的不是考试难倒候选人。

为什么不是一台电脑或一张卷子直接评定面试者,还要一个面试官来面?因为现阶段的技术,评价一个人是否符合岗位要求,还有些主观考察,是电脑做不到的。要求面试官不是机械的问问题,要能主动发掘面试者的特点和能力。

在整个面试过程中,面试标准评价要客观,面试信息挖掘和引导要主观

模板

面试官准备面试,针对整个流程,都要有对应的模板。笔试模板,面试模板,评价模板。通过模板,能够节省时间,把面试的经验和教训积累起来。对不同的面试人,采用同一套模板体系,能够客观公证地评价面试者的成绩。让自己的状态对面试结果影响最小。

笔试模板

有多套笔试题,每套笔试题都有对应合格的分数。面试者分数应该是符合正态分布,能够区分出不同水平的人。

题目具有层次,一道题能够针对不同水平的人,增加更深入的问题。通过层层深入,评估出面试者的能力层级。

对漏题有对策,针对漏题有几种方式。

最简单的就是换题,增加新题目,看面试者是否能答出。

更好的是题目设计为开放性问题,没有标准答案,但是能够根据面试者的分析和解答过程,评价出面试者的能力。而且还可以延展问题,根据问题的回答,往不同方向延展,检测面试者是否真的又掌握这种知识。例如设计一个系统,设计一个类,并说明原因。这类素质不是靠背就能答出来的。需要经验的累积,这些不是短时间能突击出来的。

笔试题模板要有多种选项,每道题都有延展问题和细节扩充,能够应对不同水平的面试者。

问题要能层层递进,并且有区分度。

面试模板

笔试能够快速过滤掉能力不行的面试者。如果笔试通过,再通过面试来观察面试者是否符合进一步要求。这也是面试官的主要职责。

在面试前,针对要考察的素质(包括技术和非技术的)列好问题模板,在交流中要考察哪些点。提前查看简历,针对简历和问题进行合并,确定重点问的问题。

针对面试模板,最终输出一个表格,表格里有每项的权重,满分,时间是多少。面试时,填写面试者实际的分数,面试结束后综合打分。

面试节奏

面试官要把握面世节奏,高效面试。

一票否决:事先明确哪些面试者是和公司要求有冲突的,不能加入的。例如:人品有问题,某些习惯难以适应招聘岗位。

面试过程中可以给予提示,但是提示也是分层的,根据提示的信息,最终给的分数也不同。如果发现面试者没思路,尽早换题,或询问面试者擅长的地方,有效考察能力。

推动面试的进行,模板中的问题要都问到,不要在一项素质已经评定好,特别是认定通过后,还耗费时间。防止面试时间过长,或者面试结束后,还评定不出面试者的能力。

面试过程中要针对简历和不明确的地方充分核实。例如毕业年份和上班年份有偏差,工作年限中有空白期等。

运用STAR面试法(S情况、T任务、A行动、R结果)针对面试者的项目,了解这四方面。要明确,完整,从多角度考察。通知在交流过程中也能对面试的沟通,表达等其他素质进行评定。

面试结束

面试结束后就真的结束了吗?不是的。

面试结束后和面试者保持沟通,保证顺利进行下一轮面试,防止两轮面试间隔太久,让面试者焦急等待。

详细录入面试题目和评价,供下一面面试官参考。录入内容包括:出了哪些题目,擅长、不擅长哪些,题目答的情况……

同时总结模板中的优缺点,统计面试历史,根据实际情况对模板进行修订。

总结

如果要稳定、高效地面试,以上几点是必须要做到的。

制定合适的模板,定期总结修正。保证面试评定客观公正,在面试过程中合理引导,推动面试顺利进行。让面试结果受面试官的影响降到最小,不至于因为面试官自身的情况而影响到面试。

Leetcode 第133场周赛解题报告

今天参加了leetcode的周赛,算法比赛,要求速度比较快。有思路就立马启动,不会纠结是否有更好的方法或代码可读性。只要在算法复杂度数量级内,基本上是怎么实现快速就怎么来了。

比赛时先看的第二题,一看题就有了思路,直接用的广度优先搜索,写完提交正确。再一看有人都做了3道题了,应该是职业选手了,要多像他们看齐。

之后看第一题,发现直接用贪心就能做,写了个双重循环,一次过掉。

第三题求最优连续子数组和,想到是动态规划。然后在处理代码细节上花了很长时间,中间提交还错了一次,在十一点半左右提交通过。

再看第四题,能想到是trie树和ac自动机,但是我手上没有现成代码,到比赛完也没有完成。

本次比赛题目偏简单,及时第四题如果经常做竞赛也很容易写。以后要多做些训练,把常用的代码整理下,否则比赛会比较耗时间。另外要多训练算法思维,一是在比赛时能够思路快。二是算法在工作中也比较重要,虽然很多时候都有封装好的现成函数,但是知道其中的原理,能够更高效地解决问题,对于新问题的思考也更全面更准确。

下面是今天比赛的详细解题。


今天比赛的地址 Weekly Contest 133 https://leetcode-cn.com/contest/weekly-contest-133

1. 两地调度(Two City Scheduling)

题号:1029

题目:两地调度(Two City Scheduling)

题意:2*N个人去A、B两地,每个地方都只有N个人去,每个人去A、B两地的费用分别给出,求总计最小费用。

思路:

方法一:

有最优策略,先把2N个人随意分成A、B两个集合,每个集合N个人。A集合去A地,B集合去B地。然后对于A集合中每个人ai,到B集合中遍历每个人bj,看是否能互换位置,让整体费用更低。如果有则换位置,没有检查下一个。全部换完则是最优解。

换的条件是ai去A的费用+bj去B的费用,要大于ai去B的费用+bj去A的费用。这样bj与ai互换整体费用会最低。

时间复杂度O(n^2)

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        vector<int> va;
        vector<int> vb;
        for(int i=0;i<costs.size();++i)
        {
            if(i%2==0)
                va.push_back(i);
            else
                vb.push_back(i);
        }
        for(int i=0;i<va.size();++i)
        {
            for(int j=0; j<vb.size();++j)
            {
                int aindex=va[i];
                int bindex=vb[j];
                int acost = costs[aindex][0]+costs[bindex][1];
                int bcost = costs[aindex][1]+costs[bindex][0];
                if(acost>bcost)
                {
                    swap(va[i],vb[j]);
                }
            }
        }
        int sum = 0;
        for(auto i : va)
        {
            sum+=costs[i][0];
        }
        for(auto i : vb)
        {
            sum+=costs[i][1];
        }
        return sum;
    }
};

方法二

把2N个人的费用排序,到B地比到A地超出差价大的人排在前面,最后让前N个人去,排在前面的人去A地更划算。整体费用最低。

时间复杂度O(nlogn)

方法三

动态规划,此题有最优子结构。用f[n][m]表示n个人,派m个人去A地,所花费的最小钱数。这时再来一个人,这个人有两种选择,一种是去A地,一种是去B地。
则更新
1. 如果去A地:f[n+1][m+1] = min(f[n+1][m+1], f[n][m]+costA);
2. 如果去B地:f[n+1][m] = min(f[n+1][m], f[n][m]+costB);

costA、costB表示这个人去A、B的花费。

2. 距离顺序排列矩阵单元格

题号:1030

题目:距离顺序排列矩阵单元格(Matrix Cells in Distance Order)

题意:给出矩阵的行列值,和一个坐标点r,输出所有矩阵坐标,按照每个点到r曼哈顿距离排序输出。

两个坐标点(r1,c1)(r2,c2)的曼哈顿距离是|r1 – r2| + |c1 – c2|。

思路:
方法一:直接求出每个点到给出坐标的距离,再排序,然后输出即可。

方法二:用广度优先搜索,每次搜索到的点依次输出即可。比方法一代码麻烦。

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        vector<vector<int>> res;
        vector<vector<int>> visited(R, vector<int>(C, 0));
        queue<pair<int, int>> q;
        q.push({r0,c0});
        while(!q.empty())
        {
            pair<int,int> p = q.front();
            q.pop();
            int i = p.first;
            int j = p.second;
            if(visited[i][j]==1)
                continue;
            visited[i][j] = 1;
            res.push_back({i,j});
            int dx[]={-1,1,0,0};
            int dy[]={0,0,-1,1};
            for(int k=0;k<4;++k)
            {
                int x = dx[k]+i;
                int y = dy[k]+j;
                if(x>=0&&x<R&&y>=0&&y<C)
                {
                    if(visited[x][y]==0)
                    {
                        q.push({x,y});
                    }
                }
            }
        }
        return res;
    }
};

3. 两个非重叠子数组的最大和

题号:1031

题目:两个非重叠子数组的最大和(Maximum Sum of Two Non-Overlapping Subarrays)

题意:

给出非负整数数组 A ,返回两个非重叠(连续)子数组中元素的最大和,子数组的长度分别为 L 和 M。(这里需要澄清的是,长为 L 的子数组可以出现在长为 M 的子数组之前或之后。)

从形式上看,返回最大的 V,而 V = (A[i] + A[i+1] + … + A[i+L-1]) + (A[j] + A[j+1] + … + A[j+M-1]) 并满足下列条件之一:

0 <= i < i + L – 1 < j < j + M – 1 < A.length, 或 0 <= j < j + M – 1 < i < i + L – 1 < A.length.

思路:

按照题目的思路,把A数组从元素i开始,分割成两部分,A[0…i],A[i+1…n]。求出A[0…i]中连续子数组中长度为L、M的和的最大值maxl1,maxm1,再求出A[i+1…n]中连续子数组中长度为L和M的和最大值maxl2,maxm2,在第i个元素分割时找到的最大值是maxi=max((maxl1+maxm2),(maxm1+maxl2))。

那如何计算长度为L或M的连续子数组的和呢?假设要求的sum区间是L[k+1,k+2,…,k+L],则这个区间的值,可以用L[0,…k+L]的和减去L[0,…,k+1]的区间和。

class Solution {
public:

    int getMaxSum(vector<int>& A, int len, vector<int>&v)
    {
        int i=0;
        int sum=0;
        int maxsum=0;
        for(i=0;i<len;++i)
            sum+=A[i];
        v[len-1]=sum;
        maxsum = sum;
        for(i=len;i<A.size();++i)
        {
            sum=sum-A[i-len]+A[i];
            maxsum=max(sum,maxsum);
            v[i]=maxsum;
        }
        return 0;
    }
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
        int n = A.size();
        vector<int> B = A;
        reverse(B.begin(),B.end());
        vector<int> L1(n,0);
        vector<int> L2(n,0);
        vector<int> M1(n,0);
        vector<int> M2(n,0);
        getMaxSum(A, L, L1);
        getMaxSum(B, M, M1);
        int sum1=0;
        for(int i = L-1;i<n-M;++i)
        {
            int x = i;
            int y = n-1-(i+1);
            sum1=max(sum1,L1[i]+M1[n-1-(i+1)]);
        }
        int sum2=0;
        int res = 0;
        getMaxSum(A, M, L2);
        getMaxSum(B, L, M2);
        for(int i = M-1;i<n-L;++i)
        {
            sum1=max(sum1,L2[i]+M2[n-1-(i+1)]);
        }
        res = max(sum1,sum2);
        return res;
    }
};

4. 字符流

题号:1032

题目:字符流(Stream of Characters)

题意:给定一个单词表words,然后每次输入一个字母,假设地k次输入字母为a[k]。则a[i],a[i+1]…a[k]组成的单词(i>=1且i<=k),在单词表words中出现,输出true,否则输出false。

思路:
题目比较好理解,主要是根据words建立字典,由于都是小写字母,而且涉及到前缀的查询,用trie树是最好的数据结构。

对于每次输入字母a[k],首先查询a[k]是否匹配某个单词。然后把之前输入的前缀能查到的单词,和a[k]结合,再查询是否能匹配某个单词。如果完全匹配,则返回结果为true。在返回前,要把所有能匹配单词表中单词,或词表前缀的单词留下来,留着下一轮输入字母时匹配备用。

但是这里是有方法优化的,如果每次都重头匹配单词,会超时。优化的方法有三种,

一、把上次匹配到前缀的trie树节点指针存储起来,下次只匹配一次字母即可。

二、使用ac自动机进行多模式匹配。

三、trie树中存储倒序的字符串,然后把每次输入的字母都按顺序保存起来。按照倒序匹配,如果匹配到一个完整的单词,返回true;如果匹配到不存在的单词,则返回false;如果匹配的是某个前缀,继续往下匹配。

class TrieNode{    
public:
    bool hasVal=false;
    vector<TrieNode*> children;
    TrieNode() : children(26,NULL){}
};
class TrieTree{
public:
    TrieNode* root;
    TrieTree()
    {
        root = new TrieNode();
    }
    int insert(string& word)
    {
        TrieNode* p = root;
        for(int i = 0; i < word.length(); ++i)
        {
            int n=word[i]-'a';
            if(p->children[n]==NULL){
                p->children[n]=new TrieNode();
            }
            p=p->children[n];
        }
        p->hasVal=true;
        return 0;
    }
    bool query_has_r_suffix(string& word)
    {
        TrieNode* p = root;
        for(int i=word.length()-1;i>=0;--i){
            char ch = word[i];
            int n=ch-'a';
            if(p->children[n]==NULL){
                return false;
            }
            p=p->children[n];
            if(p->hasVal) return true;
        }
        return false;
    }
};
class StreamChecker {
    TrieTree * tree =new TrieTree();
    string suf_str;
public:
    StreamChecker(vector<string>& words) {
         for(string w:words){
             reverse(w.begin(),w.end());
             tree->insert(w);
         }
    }

    bool query(char letter) {
        suf_str.push_back(letter);
        return tree->query_has_r_suffix(suf_str);
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

一些微信功能的观察与想法

微信这个国民级APP,有些产品特性还是很有特点的。把之前的发现记录一些,可以参考下背后的哲学和道理。

PC版去掉帮忙删空格功能

在之前的某个微信PC版本,热心地帮用户把消息前后的空格给删除掉。但是在后来的版本迭代中,又给去掉了。

用户有时真的就要在消息前面发空格,帮用户删掉很热心,但用户可能也不买账。

发现tab中可以删掉所有功能

记得从前「朋友圈」和「玩一玩」是删不掉的,现在的版本是都能删掉的。给用户更多的选择,不需要的用户自然就不需要,不要限制他强用某个功能。

这个设置,只能设置开关,不能设置位置上调和下降。如果能上下调位置,当然对某些人是刚需,而且以微信的研发实力做这个功能也不难,但为什么没做呢?


看一看只保留七天内容

控制只看七天内容,能让数据都存在内存,超过七天的删掉。少了做数据落地,切换读取数据源等的操作。如果要做多少天都能看,实现难度就相当于一个小微博。而且也会花费更多的存储资源。

实际要看七天前看一看的用户应该非常少,只要设置好上限,系统复杂度会大大降低,也不会影响用户体验。数据有时效性,不用为永久存储,永久备份做太多事情。

看一看内部的搜索中隐藏着其他入口

在看一看的搜索里,可以看到「个人中心」,还有其他「特色专栏」。

这里应该是还没想好怎么和用户推广,一些还在孵化的功能,入口很深,有兴趣的用户进来观看,不感兴趣的或不知道的用户,也不会被打扰到。

微信加群方式与众不同

加群只有两种方法:1、被群里的人拉进去。2、扫描一个有时效性的二维码。

这么做的好处是让进群的人要么是群里认识的人,要么是在短期推广时加入的人。可以让新进群的人和群里的人有更多话题,能够引起互动。不至于让群很快死掉。

微信的群更像一个临时讨论组。不提供主动的保存通信录功能。有生命力的群就能留下,没有生命力的自然就消失掉,落到最近联系人最下端了。

总结

微信不强制用户使用某个功能;

微信提供有边界的服务;

微信的新功能让用户自己去发现。

尽量让一个功能复杂的APP在表现侧简单,让开发在表现层功能逻辑尽量简单,去打磨内功。

附:脑动大开

如果初级的产品经理去做微信,肯定会发现好多块新大陆。有好多功能都能做,而且理由十足,都能满足用户的需求。做完了数据也会不错。几个例子。

1、给小程序做个商店,再加上各种榜单,推荐。简直就是个小型App store。

2、微信消息支持超级链接,支持修改字体颜色,支持富文本。

3、群支持搜索群号,永久二维码,推荐群。

4、公众号编辑器更强大,手机公众号APP也对齐PC端。

5、发现tab里,可以调节「朋友圈」的上下位置。

6、微信头像更新后,好友马上能看到最新头像。

7、阅读公众号切换到聊天窗口可以悬浮多个文章列表。

…………

上面这些肯定有很多人给微信提过,张小龙不是说全国有几亿人教他怎么做产品吗?但微信为什么没做呢?微信在功能上做了很多坚持和取舍。

那微信的产品经理和开发都在做什么呢,是不是没事可做?

做一个功能不难,更难的是考虑要不要做,以及未来的发展方向和趋势。好多产品都是做了轰轰烈烈,到后面想下又下不掉,带了很多包袱。微信的功能表面看没有什么,但是有很多内功。例如语音识别,就是微信自己做的,在表面没有入口变化,用户也没什么感知,但是实实在在地大家都在用。

这里需要产品经理有长远的打算,和对产品愿景的制定。

人人都要effective

人人都要effective

最近发现,几本不同领域的书,看中文翻译后的书名也都没什么联系,但是英文书名都有一个词——effective。公司也在倡导高效会议、提高工作效率。
原来我们一直在学习的内容,和追求的目标,用一个单词符号就可以概括——effective。

《高效能人士的七个习惯-The 7 Habits of Highly Effective People》

曾经有一位老大哥说过,不用掌握七个习惯,看这本书只要把一个习惯做好,就能够超过大多数人。该书是美国的畅销书,在全球总共发行超过一亿册。甚至还有漫画版和缩略版供人学习。也有专业机构讲授的课程,一节课几万块。

七个习惯分别是:积极主动、以终为始、要事第一、双赢思维、知彼知己、统合综效、不断更新。这里effective的意思是高效,意思是做事情有效率,效率高,也预示着结果是好的,有好的结果。

《卓有成效的管理者-The Effective Executive》

这本书在管理学的地位很高,是德鲁克在上世纪六十年代写的,直到今天还经久不衰。在脑力劳动逐渐替换体力劳动的时代,构建了现代管理学的思想,教知识工作者如何做好管理。不一定是有职位的人才是管理者,任何一个知识工作者,靠脑力劳动产出的人,都是管理者。书中也有介绍时间管理,如何发挥人的长处,决策的要素和如何有效决策。是现代知识工作者必读书目之一。

从中文的翻译卓有成效,意思侧重于做事的效果是有效的,能够达到预期目标的。但看了英文的翻译The Effective Executive,非常简单。除了表示结果有效以外,也和《高效能人士的七个习惯一样》,有效率高的意思。

《Effective C++》

没有翻译成中文的书名,直接用的英文。一般技术书籍都很少翻译成中文单词,是为了保持原汁原味吧。这本书是任何一个C++程序员都应该读的书。介绍了一些写C++的原则。C++是一门复杂的语言,很多编写C++有十几年经验的程序员,写的越多,越不敢说精通C++。因为C++既兼顾了底层性能兼容C,支持模板,又有抽象能力加入类,多重继承。如果能把这些用好,简直如虎添翼,如果用不好,那就是灾难。有时为了项目可控,防止程序员对C++理解不一致,而不得不控制一些C++代码的特性使用。

还有一方面也能看出C++复杂。要学习C语言,一本《C程序设计语言》就够了,中译本258页。入门C++,无论是《C++ Primer》还是《C++程序设计语言》,两本教材都在一千页左右。学完再看《Effective C++》才能说你都知道了,至于工程实现不出问题,还要经过许久的练习。

书名中的Effective是高效率,写程序又快又好,还有代码执行效率高的意思,和前面介绍的两本书要表达的意思也是有相通之处。

PS:如果读完《Effective C++》还想提高,还有《more Effective C++》。

总结

通过上面的发现有几点启示:

尽量阅读英文原版书。

翻译之后反推不出最初的意思,不同语言间语义并非完全等价。还有译者侧重不同,看到的意思不一定全面。

高效是互联网行业必备素质。

在互联网行业,技术发展非常快。要快速跟上节奏,无非两条路。一、增加资源:雇佣更多的人,增加更多的上班时长……;二、提高效率:人员更熟练,工具更完善,流程更合理。在项目初期,用第一种方法见效最快,当项目稳定时,用第二种方法更有效。无论管理方法、技术方法和生活习惯,原来我们要追求的高效、卓有成效、有效等等,都是一个单词符号——Effective。只要记住一个词根,或一个基本概念,就能了解目标是什么。

要善于发现事务之间的联系,看清本质。

很多不同的事物、学科虽然表面不同,但是底层的道理都是相通的。有些人能够在多个领域都取得成就,也是因为一通百通,快速弄明白多个跨界的知识,弄清楚了事务最根本的原则。通过英文找相同单词是一种简单的方法。更厉害的人会通过融会贯通,独立思考,自己总结出来不同事物的基本道理。最终做到一通百通,举一反三,高效学习。