乖小鬼YQ

乖小鬼YQ 查看完整档案

北京编辑华北电力大学(北京)  |  软件工程 编辑阿里巴巴  |  前端 编辑填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

乖小鬼YQ 评论了文章 · 2018-12-11

html5 上传本地图片处理各种问题

原文还是在简书上: html5 上传本地图片处理各种问题

这是最近给公司写一个项目,项目要求大概是这样子:
1.上传手机本地图片,然后裁剪(后加的需求)
2.能够旋转图片,用于裁剪(后面加的需求)
3.填写各种文字,选择颜色,之后把文字和2个相关的图片,水印到裁剪的图片上,上传服务器生成一个图片地址,返回,分享出去。

功能就是大概上面这些,其他的也就是各种小功能,不提了,技术选型说下,整体上使用 Vue(包括 router,resource,webpack等等)

那么这几个需求怎么做呢:
1、 本地上传,使用 html5 的 File Api 拿到图片的base64编码,赋值给img的src(坑1,2),然后弹出一个图层,进行裁剪,最开始裁剪是在img的上面套一个div来进行坐标计算,计算完了使用canvas来截取图片,然后取值(坑3)。
2、这个功能就是使用canvas的旋转图片解决,需要注意的是,旋转的时候要保持横纵比,而且要注意宽高的大小(坑4)。
3、使用canvas来叠加水印和图片即可,主要是注意坐标。

那么说说坑:
1、拿到src的base64编码,看似没有问题,实际上有个巨大的问题,很多图片在手机上显示为竖屏,但是拿到的base64编码,直接赋值给img的src后,发现是横屏的。最开始发现这种情况,以为是个别现象,最后不断尝试之后,发现是个非常普遍的情况,特别是IPhone手机,而且还分你选择的图片文件夹,相册和照片流同一张图片,一个横屏,一个竖屏。导致我完全不能理解这是为什么???基本一个下午耗在这个问题上了。

直到晚上回去,问我一个朋友IOS开发的大神,@叶孤城__,他告诉我,因为现在IPhone的摄像头就是横着的,手机里显示竖屏的原因是ios自己做了处理,他们可以根据图片的一个拍摄角度数值来判断横竖问题,但是这个数值在我们web端确拿不到,很是尴尬。那么怎么解决这个问题呢?? ------- 我使用的方案:旋转图片,可以让用户自己去主动旋转图片,选取角度。 还有另外一种解决方案,在坑2也用到,后面讲。

2、除了这个横屏之外,android手机有的上传,选择了图片之后,没有任何反应,我开始一度认为原因是不支持html5的File Api,所以没有显示出上传的图片,后面就各种debugger,发现原因是没有触发Input标签的change事件,而且不管怎么样都没有办法触发,为了解决这个问题,查阅了各种官方文档和stackoverflow之后,发现可以给 type="file"的input添加两个属性来表示手机上传图片。

 <input type="file" name="image" class="file-choose" id="file" accept="image/*" v-on:change="chooseFileChange($event)" capture/>

这样添加了 accept 和 capture之后,有问题的android手机,在选择图片的时候,有好几个文件夹,可以选择了,其中有的可以上传,有的不行,经常仔细的测试发现,sd卡上的图片是拿不到的,也就不会触发change事件,因为没有root权限去拿文件数据。又是一个无解问题,因为你的web在浏览器里面,权限就是低啊,(不得不吐槽下web的权限问题,妈蛋)怎么解决问题呢??? 绕过去,也就是说如果你的页面是嵌套在你们公司自己App里面的,就让App帮你,那么我们项目是微信传播的,一定在微信浏览器里面,所以可以调用微信的JSSDK的选择图片接口,他是可以越过这些权限,而且还有一个好处,就是解决坑1的问题,他会处理横屏问题,就是把看着竖屏,实际横屏的上传时都处理为竖屏,但是代价也不小,你要选择图片,拿到一个key,然后继续调用sdk传到微信的服务器,拿到一个serverid,这个id传给自己的服务端,让他们通过这个id,去微信下载图片到自己的服务器,返回给你一个Url。过程很曲折,而且下载次数有限制(可以跟微信申请加载限制);

参考: 微信 js sdk 选择图片接口

3、我们继续说坑,以上问题,解决了之后,就是裁剪了,开始我使用的方案是这样子的,获取到base64之后,赋值给一个img,然后在这个img上进行框选移动,计算坐标然后裁剪,pc端完全没有任何问题,效率很高,但是放到微信上面测试,发现3个问题(妈蛋,手机端就是坑,一个功能,3个不同的问题),第一个问题,大家都知道现在手机像素高,图片不小,上传过来之后,base64也不小,放到img的src中其实就是内存中了,导致整个微信特别容易崩溃(就是崩溃,他就崩溃了,微信就崩溃了---三遍),第二个问题,使用vue的on来绑定touch事件,响应很慢,移动一点都不平滑,而且也会崩溃,没错,又崩溃了。第三个问题,旋转要使用canvas转化,先去图片数据,转完后,在给图片src赋值,很麻烦。

解决方案: 统一使用canvas,不要再用img,知道裁剪完成了,把img的base64拿到就行,而且导出的时候,使用jpeg不要是png,降低一些画质,我觉得完全没有影响,也就是图片的裁剪,旋转都是canvas,事件建议直接原生绑定。

4、旋转的坑,这个的问题是我们必须保存住原始图片的数据,进行canvas先旋转然后drawImage,要不没有旋转出来,canvas自己的imageData,貌似没有办法旋转,我试了矩阵的方式好像都不行(也可能是自己数学不好!!!如果有人知道,就demo)。

以上就是这次项目,遇到的各种大坑,其他都是小的地方,不过总体来说,完成了任务,并且使用了新的技术Vue.js。Vue的component还是非常好用的,注意父子关系,props的继承就没问题了。

欢迎大家交流相关技术, 如果对Vue感兴趣,可以加QQ群: 364912432,240319632。

查看原文

乖小鬼YQ 发布了文章 · 2018-03-12

2017--年度个人总结

17年的总结来的更晚一点,其实是一直在犹豫要不要写,主要感觉去年一年折腾的有点凶残,连续换工作以及地点,一路走来有纠结,有痛苦,有快乐,有兴奋,有迷茫,有得有失,所以想了很久,还是来记录下这一年的关键点。

离职 -- 新路线

16年的总结在这里16年总结,其实在发布这个文章之前,就已经跟阿里那边再谈新的offer,会以P7的级别入职阿里--闲鱼部门。这个offer也是犹豫了很久,毕竟要离开北京这个生活工作了很久的城市,换到杭州去,还是很纠结的。感觉吸不到那个熟悉好配方的雾霾还是会不习惯的。跟家里人商量了好几次,综合考虑了各个方面,最终决定接受这个offer,当时考虑的几个方面是:

  • 在罗辑思维我开始遇到上升的瓶颈,公司并不大,也不会存在各种评级的标准,那么我作为一个架构的上升通道就很窄,因为已经存在一个前端负责人,所以这种title就不会再有了,虽然Leader表示可以可以单独让我再拉起一个前端团队,但是我觉得这样并不好,因为整个前端团队人并不多,分散力量做事情没有必要。
  • 当时受到rank的文章影响,以及weex,RN的火爆,我自己判断未来三端融合的趋势会更加明显,所以我当时提出了要把三端团队整合在一起的想法,但是被Leader否决了,那么这条路线的上升通道也被锁死了。
  • 同时我也复盘了下自己的职业路径,发现一个问题就是,我没有BAT这种级别公司的工作经验,那么我可能还是需要去这种级别的公司看一看,学习一下。
  • 当时也考虑到去杭州定居的可能性了,也算是相应号召逃离北上广。
  • 很多人可能会觉得为啥不走技术深度路线,非要什么Title之类,一个原因是当时很难有业务场景来做研究支持。当然还有其他的原因就不提了。

基于以上的种种原因我选择接受了这个offer。

阿里

在元旦去马来西亚潜水之后,回家过完年,收拾了自己行李,来到了杭州,2月8号入职阿里--闲鱼部门。不得不说对于异地来杭州的入职人员,阿里这方面的安排还是很给力的,前两个周都可以免费住公司的协议酒店。附近有班车,基本有2周的冗余时间来找住的地方还是比较人性化的。

其他公司我不知道,但是阿里西溪园区还是非常漂亮的,设计的很精美。带logo

一角

从我这里俯视

请原谅我这渣渣辉的摄影技术,在阿里带的这段时间,总结下来自己主要做了2件事。

一、 产品思维思考

当时入职后,我的Leader对于闲鱼的鱼塘业务有更大的愿景,所以在我们做平常的业务的同时,想要做一些技术上能推动业务发展的探索,为此我们组了一个小的3人小Team来做这个业务探索。

后端的朋友选择了技术构架层面去做业务附能,数据的同学选择了数据分析层面来寻找方向和机会,而我比较尴尬,这两个方向都不行,于是挑选了产品方向(并不是黑PM)去探索新的业务形态(有点不自量力的感觉,转行了PM)。

相当长的时间,我在思考产品的东西,主要是社区类产品为啥没落了,比如贴吧,豆瓣社区等,原来很火的社区类产品逐渐不行了,大家不玩了。当然最终也没有特别牛逼的结论出来,只是有些想法,可以供大家讨论下。

  • 社区类产品中心化还是比较严重的,老人利益抱团,会排挤新人以及不守他们潜规则的人,这样新鲜血液就很少,基本没啥新的内容产出了。
  • 水贴过多,导致内容质量急速下降,劣币驱逐良币现象严重,没有优质内容更难吸引优质人才加入贡献。
  • 广告贴很难禁止,特别招人讨厌,管理成本很高,所以需要吧主这样的人工管理人员,但这些人员目前很多并不是因为兴趣,而且为了利益,有灰色收入才来做吧主的,大家懂得。
  • 初心变了,很多人或者组织都把这些社区当做渠道来使用,功利性很强,当初的很多氛围基本遗失殆尽,老人或者优质人员流失,格调沦陷。
  • 社会变革,大家变得急躁,碎片化时间变多,不愿意花大量时间来写内容,特别是没有利益的情况下。

上面是一些比较简单和浅薄的观点,欢迎随时指正。

二、Weex的探索

我们部门的前端比起淘宝、天猫来说,人数还是偏少的,但是业务还是要做,比如日常性的运营活动,产品页面等等。所以入职没多久,就有了一次关于技术选型的讨论,当时我的判断是如果后面我们会大力的主攻Weex方向,那么我们现在就应该在前端方面积累Vue的组件了,而不是继续用React(PS:这里有些人可能会提到Rax也可以,但当时还是Vue和Weex的结合更好点,官方也比较推荐)。

然而当时的讨论,由于大家对是否主攻Weex方向意见不统一,导致没有切Vue组件,还是继续用React写我们的业务场景,现在回想来还是不够强势以及太过顾虑别人的感受。

接下来不久,客户端的同学自己发起了Weex接入,从而导致我们不得不开始跟进,虽然后面回顾,没有什么问题,而且运行的很好,但我心中还是有些遗憾的,如果早早的我们切Vue开始靠Weex的方向,后续的动作能提前快很多,而不是被别人牵着走。这里还是有点缺乏自信,没有坚持自己当时的观点。

关于Weex具体探索有很多文章,我推荐这个 飞猪的探索,他们走的很快,而且很坚定,我还在阿里的时候还请教过侑夕同学的。

抉择

到了7月份的时候,我选择了离开,继续又回北京,原因在于:

  1. 杭州我对气候很不适应,经常生病,太潮湿了,毕竟我是个北方汉子,也许是年龄大了吧,适应力降低了,不像年轻的时候。
  2. 没啥朋友,周末想找个人出来玩都找不到,这点很尴尬,没啥人说说话,也就有一些很强烈的孤独感吧。
  3. 做的事情可能没我想象的那么有趣。

所以我选择回到北京,回到熟悉的地方,这里朋友比较多,公司也多,选择比较广,能找到我更感兴趣的事情。最终我选了美团,主要是觉得氛围更好,做的事情更感兴趣,机会也多。

挺有意思的一件事情是,在阿里的时间里,我其实发现貌似这边的HR并不像脉脉或者知乎上说的那么无情呀,感觉还挺不错的呀。当然有可能是我沟通的比较少,就两三次,其中一次入职,一次离职,哈哈,比较尴尬。我还是觉得这些事情要理智的看待,并没有必要妖魔化HR或者贴上标签,毕竟看问题的角度还是有差异的,处理的方式自然有区别。

最后在这里,还是非常感谢我的Leader教会了我很多道理和处理事情的方式,每次和他聊天都收获满满,当然也感谢青页、玉缜、广延、归禾、扬羽、岚依、宗心、梁缘等等给我的帮助。
忽略我那凌乱的发型,谢谢

AOW

在离职前,我利用年假去了一趟巴厘岛,继续我年初的潜水之旅,拿下AOW,领略了巴厘岛图兰奔的水下风光。
沉船

断层30米

当然还有各种海滩风景,就不给大家展示了,大家就看看海底风光吧。计划今年继续潜水,地点还在思考。

美团

8月28号,入职新美大,金融平台,智能支付部门。这边智能支付业务发展速度很快,当时也比较看好这里的业务,入职之后,具体工作也变动了很多次,最开始负责消费金融和数据可视化的业务,后面拥抱变化,改成了基础技术服务。

这里大家不要八卦,不要问我,两家公司有什么区别,想搞事情,没门。我是不会回答你们的。
不要搞事情

之后,在基础技术服务,我们团队主要做各种基础设施的搭建,包括Web的离线化技术,Era的基础技术生态,以及我们做js文件diff比对的Stark服务。有些新名词可能各位没有听说过,不过没关系,今年这些都会陆续慢慢亮相到外界。关于离线化我们其实在今年的一月份的美团技术沙龙已经讲过,大家有兴趣的可以去看看。其他的两个服务还在优化和完善中,后续会慢慢给大家带来惊喜,尽请期待。

具体地址戳这里:Tech Salon 031:线下支付千万级订单服务——前后端架构实践, 请使用微信打开。

总所周知,我司在12月份调整了一次架构,具体如下:美团调整了组织架构。 跟我相关是如图:智能支付

在经过一段时间调整之后,我的Leader留在的金融平台,整合其他前端团队,而我会负责新到店的智能支付前端团队。

好的,那么重点来了。新的一年,千万订单量的业务场景,等待你的参加。
扫码加我微信

当然职位要求还是有的,如图:岗位JD

欢迎各位有志青年的加入,我司大门常打开。

结尾

希望18年能打造一个好的前端团队出来,让团队的成员在这一年都能有所收获和成长。
也希望自己完成一些小目标,比如 学车(已经提了N年了)、潜水、健身。
最后把别人送我的话也给大家,自勉下。
寄语

查看原文

赞 1 收藏 2 评论 1

乖小鬼YQ 赞了文章 · 2017-11-10

几个有趣的算法题目

本文首发 http://svtter.cn

最接近的数字

题目

一个K位的数N

$$ (K\leq2000,N\leq10^{20}) $$

找出一个比N大且最接近的数,这个数的每位之和与N相同,用代码实现之。

例如:0050 所求书数字为0104;112 所求数为121;

算法分析 算法思想

直接暴力求这个数字是不可以的,数字的量级太大,有K位的数字,不可能直接用int,或者float来表示,使用数组来存储。应该分析这个数字,step1,从右边开始的最小位数开始,分解最后一位数字,分解出1来拿给前面的一位。9和0比较特殊,因此从左往右扫描的开始,遇到0就跳过,遇到第一个非0的数字,就把这个数字-1,然后移到最后面去,然后,step2,开始找第一个非9的数字,如果遇到9,就把9放到最后面去,遇到非9,就+1,结束运算。

一个般的例子:

1999000 -> 1990008-> 2000899

要注意一个问题,就是如果是 999000 这种情况,在数字的最开头补1,结果是1000899

几个刁蛮的数据:29399 -> 29489

伪代码

array = get_array() # number to char array
array.reverse()
step1 = true
step2 = false
zero = 0, cnt = 0;
for i : 1 - lengthof(array)
    if step1:
        if array[i] is 0:
            zero ++
        else:
            array[i] = array[i] - 1
            if zero > 0:
                array[0] = array[i]
                array[i] = 0
            step1 = false
            step2 = true
    else if step2:
        if array[i] is 9:
            if zero == 0:
                array[cnt+1] = array[cnt]
                array[cnt] = 9
                cnt++
                if (i != cnt):
                    array[i] = array[i-1]
            else:
                array[cnt + 1] = array[cnt]
                array[cnt] = 9
                cnt++
                array[i] = 0
        else:
            i = i+1
            step2 = false
            break
            
            
if not step2:
    array[lengthof(array)] = 1

array.reverse()
disp(array)

分析时间复杂度O

因为reverse操作,2K,加上最后整理最小数到最前面,最坏情况接近K,3K,在循环中的操作看运气,但是最糟糕的情况也只有5K,所以时间复杂度为

$$ O(3K) \approx O(K) $$

源代码

#include <stdio.h>
#include <string.h>

const int MAXN = 3000;
char array[MAXN];
int length_of_number;
void get_array()
{
    int i;
    char null;
    scanf("%d", &length_of_number);
    scanf("%c", &null);
    for (i = 0; i < length_of_number; i++)
    {
        scanf("%c", &array[i]);
    }
    scanf("%c", &null);
}

void reverse()
{
    int i ;
    char temp;
    for (i = 0; i < length_of_number/2; i++)
    {
        // _swap
        temp = array[i];
        array[i] = array[length_of_number - 1 - i];
        array[length_of_number-1-i] = temp;
    }
}

void run()
{
    reverse();
    int step1 = 1,
        step2 = 0,
        i = 0,
        zero = 0,
        cnt = 0;
    for (i = 0; i < length_of_number; i++)
    {
        if (step1)
        {
            if (array[i] == '0')
            {
                zero++;
            }
            else
            {
                array[i] = array[i] - 1;
                if (zero > 0)
                {
                    array[cnt] = array[i];
                    array[i] = '0';
                }
                step1 = 0, step2 = 1;
            }
        }
        else if (step2)
        {
            if (array[i] == '9')
            {
                if (zero == 0)
                {
                    array[cnt + 1] = array[cnt];
                    array[cnt] = '9';
                    cnt++;
                    if (i != cnt)
                    {
                        array[i] = array[i-1];
                    }
                }
                else
                {
                    array[cnt + 1] = array[cnt];
                    array[cnt] = '9';
                    cnt++;
                    array[i] = '0';
                }
            }
            else
            {
                array[i] ++;
                step2 = 0;
                break;
            }
        }
    }
    if (step2)
    {
        array[length_of_number] = '1';
        length_of_number ++;
    }
}

void output()
{
    int i;
    reverse();
    for(i = 0; i < length_of_number; i++)
    {
        printf("%c", array[i]);
    }
    printf("\n");
}

int main()
{
    memset(array, 0, sizeof(array));
    freopen("input", "r", stdin);
    get_array();
    run();
    output();
    return 0;
}

测试结果

使用python生成测试数据进行测试:

"""
最接近的数字
"""
import random
import os

def test():
    """
    sample test
    """
    num = random.randint(0, 10000000)
    sum_of_num = 0
    for i in str(num):
        sum_of_num += int(i)

    length = len(str(num))
    temp_num = num + 1

    while(True):
        sum_temp = 0
        for i in str(temp_num):
            sum_temp += int(i)
        if sum_temp == sum_of_num:
            break
        temp_num += 1

    with open('input', 'w') as f:
        f.write(str(length) + '\n')
        f.write(str(num))

    res = os.popen('./ex2').read()
    if temp_num == int(res):
        return [True]
    else:
        return [False, num, temp_num, int(res)]


all = True
for i in range(1000):
    res = test()
    if res[0] is False:
        all = False
        print(res)

if all:
    print('Pass testing!')

存在错误的情况:

通过:

后期改善优化的地方

  1. reverse 是为了编程方便进行的处理,但是如果数字太大,速度肯定会受影响,这个时候就不要使用reverse了。

  2. 用链表来做可以简化代码,减少分析的,更加节省时间

  3. 处理移位的时候考虑几个问题

寻找发帖水王

题目

如果“水王”没有了,但有三个发帖很多的ID,发帖的数目都超过了帖子做数的1/4,又如何快速找出他们的ID。

算法分析 算法思想

从0-n扫描ID数组,记录3个数字的个数,如果出现第四个数字,就把三个数字的个数减少1,如果有一个数字的个数减少到0,那么把新来的数字作为原本三个数字之一进行记录。

如此一来,扫描完ID数组之后,剩下记录的3个数字的个数便是需要求的三个数字。

伪代码

array = get_array()
count = empty_set()
for i in array:
    if count.full:
        if i in count:
            count.i.num ++
        else:
            for j in count:
                count.j.num--
    else
        count.add(i)
disp(count)

分析时间复杂度O

数列的大小为N,记录数字的数组大小为3,每次判断记录数组count是否存在0,以及找到已存在的数字++,都会花费3个单位时间,因此其时间复杂度为

$$ O(3n) \approx O(n) $$

源代码

#include <stdio.h>
#include <string.h>

#define MAXN 5000
int idarray[MAXN];

int cur[3]; // 记录当前元素
int pos[3]; // 记录当前元素个数

// 检查是否在数组内,如果不在数组内,添加进入数组
void checkin(int no)
{
    int i;

    // 检查是否有空位置
    for (i = 0; i < 3; i++)
    {
        if (pos[i] == 0)
        {
            cur[i] = no;
            pos[i] ++;
            return;
        }
    }

    // 寻找指定数字++
    for (i = 0; i < 3; i++)
    {
        if (cur[i] == no)
        {
            pos[i] ++;
            return;
        }
    }

    // 没有找到重复数字,全部--
    for (i = 0; i < 3; i++)
        pos[i] --;
}

// 输出最后结果
void output()
{
    printf("%d %d %d\n", cur[0], cur[1], cur[2]);
}

// 主程序
int numberOfArray;
void run()
{
    int i;
    for (i = 0; i < numberOfArray; i++)
    {
        checkin(idarray[i]);
    }

    output();
}

void input()
{
    int i;
    scanf("%d", &numberOfArray);
    for(i = 0; i < numberOfArray; i++)
    {
        scanf("%d", &idarray[i]);
    }

}

int main()
{
    freopen("input", "r", stdin);
    int groupOfTest;
    scanf("%d", &groupOfTest);
    while(groupOfTest--)
    {
        memset(cur, 0, sizeof(cur));
        memset(pos, 0, sizeof(pos));
        memset(idarray, 0, sizeof(idarray));
        input();
        puts("Test running...");
        run();
    }
    return 0;
}

测试结果

本测试数据采用Python自动生成。

"""
寻找发帖水王
"""

import random

N = 4000
a, b = (int(N/4), int(N/3))
three_id = random.sample(range(1, 100), 3)
three_id_num = {}
sum_rand = 0
for i in three_id:
    temp = random.randint(a, b)
    sum_rand += temp
    three_id_num[i] = three_id_num.get(i, 0) + temp

id_array = [random.randint(1, 100) for i in range(N-sum_rand)]
for i in three_id:
    id_array = id_array + [i for j in range(three_id_num[i])]

random.shuffle(id_array)

print('Most three id:', three_id)
print('Three id num: ', three_id_num)
print('Sum of three_id num: ', sum_rand)
print('---------------')
# print(id_array)

with open('input', 'w') as f:
    f.write('1\n')
    f.write(str(N) + '\n')
    for i in id_array:
        f.write(str(i) + ' ')

后期改善优化的地方

  1. 对于N比较小的情况可以在内存中进行查找,但是一旦涉及到更大的数据,这个方法可能就没有那么简单了,不能在内部建立数组,需要一部分一部分的从磁盘中读数;

  2. 如果需要查找的id数量变多,那么需要的临时保存的数列可能更大;

  3. 这个实现没有使用STL中的map,如果使用map,还能进一步使得代码见解易懂,map使用hash来做内部实现,可以使得面对数据量更大的数据的时候,加快查找数据的速度。

山西煤老板

题目

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车只能装1000吨煤,且能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板,你会怎么运送才能运最多的煤到集市?

算法分析 算法思想

从动态规划的角度求最优解:
假设起始运送货物量为t,终点路程为s,火车容量为c,可以运抵终点的最多货物量为函数 F(t, s)。
3种基本情况:
(1)t < s:货物量不足以运送到此距离,所以F(t, s) = 0;
(2)s < t < c:火车一次就可以装完货物,所以F(t, s) = t - s;
(3)2s < c 使得火车一次无法运完,但可以采用往返的方式多次运输,这种情况下最有的方式就是减少总共往返的次数,也就是直接运到终点而不在中间卸货,所以

$$ F(t, s) = (t / c - 1) * (c - 2s) + (c - s) $$

可得递归式:

$$ F(t, s) = max\{ F( F(t, i), s - i)\} (1 <= i < s) $$

分析了一下这个方程是有问题的,比如F(1750, 250)会计算出1125;

所以正确的结果应该对t/c进行处理,也就是说,起点剩余的燃料不足运输到终点,直接舍弃。第三阶段的方程式应该是

$$ F(t, s) = (t // c - 1) * (c - 2s) + (c - s) + (t \% c - 2 s), if (t\%c > 2s) $$

伪代码

begin:
    if t < s:
        f[t][s] = 0
    elif s < t < c:
        f[t][s] = t - s
    elif 2*s < c:
        f[t][s] = int((t//c-1)*(c-2*s) + (c-s))
        if t % c > 2*s:
            f[t][s] += int(t % c-2*s)
    else:
        pre = -2
        for i in range(1, s):
            pre = int(max(F(F(t, i), s-i), pre))
        f[t][s] = pre
end
disp(f[3000][1000])

分析时间复杂度O

时间复杂度为

$$ O(3000*3000) $$

因为每个数字都要计算一遍。

源代码

"""
山西煤老板
"""
c = 1000
f = [[-1 for k in range(4000)] for j in range(4000)]
for j in range(4000):
    for k in range(4000):
        if j < k:
            f[j][k] = 0
count = 1000
cnt = 0


def F(t, s):
    """
    dp
    """
    global count
    global c
    global f
    # count -= 1
    # if count == 0:
        # count = int(input())

    t = int(t)
    s = int(s)
    if f[t][s] != -1:
        return f[t][s]
    if t < s:
        f[t][s] = 0
    elif s < t < c:
        f[t][s] = t - s
    elif 2*s < c:
        f[t][s] = int((t//c-1)*(c-2*s) + (c-s))
        if t % c > 2*s:
            f[t][s] += int(t % c-2*s)
    else:
        pre = -2
        for i in range(1, s):
            pre = int(max(F(F(t, i), s-i), pre))
        f[t][s] = pre
    print(t, s, f[t][s])
    return f[t][s]


print(F(3000, 500))

测试结果

后期改善优化的地方

  1. 去除了一下数据进行加速

  2. 保存f减少重复运算值

  3. 应该有更加简单的方法,类似这种,但是不好解释。

  4. $$ 3y=1000\\ 5x=1000\\ 解得x+y=200+333=533,因此使得最后一辆火车抵达时节省了533吨煤\\ $$

Facebook

题目

Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is concatenation of each word in L exactly once and without intervening characters. This substring will occur exactly once in S.

算法分析 算法思想

使用hashmap来保存word的hash值,来加快查找速度。(旧)

直接用hash函数求字符串的hash值,最后求得结果。

依据公式

$$ hash(w_1) + hash(w_2) = hash(w_2) + hash(w_1) $$

伪代码

hash_word_list = list(map(hash, words))
hash_sum = reduce(lambda x, y: x + y, hash_word_list)

for i in range(len(sentence)):
    wl = word_len
    wlist = [sentence[i+j*wl:i+j*wl+wl] for j in range(words_len)]
    temp_sum = 0
    for k in wlist:
        temp_sum += hash(k)
    if temp_sum == hash_sum:
        print(i)
        break

分析时间复杂度O

就是字符串长度

$$ O(lengthOfS) $$

源代码

#!/usr/bin/env python3
"""
facebook

"""
from functools import reduce

while True:
    words = input()
    # words = "fooo barr wing ding wing"
    words = words.split(' ')
    word_len = len(words[0])
    words_len = len(words)

    hash_word_list = list(map(hash, words))
    hash_sum = reduce(lambda x, y: x + y, hash_word_list)

    sentence = input()
    # sentence = """lingmindraboofooowingdin\
    # gbarrwingfooomonkeypoundcakewingdingbarrwingfooowing"""

    # print(words, words_len, word_len, sentence)

    for i in range(len(sentence)):
        wl = word_len
        wlist = [sentence[i+j*wl:i+j*wl+wl] for j in range(words_len)]
        # print(wlist)
        temp_sum = 0
        for k in wlist:
            temp_sum += hash(k)
        if temp_sum == hash_sum:
            print(i)
            break

测试结果

测试数据生成意义不是很大,

后期改善优化的地方

  1. hash尽管在速度上非常优秀,但是在准确度方面,如果出现hash冲突,那么值可能不准确。此时可以利用hashmap来解决这个问题,不过会多出重置hashmap的相关时间。

For n -m - problems

Problemset

Assume we have a sequence that contains N numbers of type long. And we know for sure that among this sequence each number does occur exactly n times except for the one number that occurs exactly m times (0 < m < n). How do we find that number with O(N) operations and O(1) additional memory?

Algorithm

^ is the add operation without carry.
默认one,two都是0, 即任何数字都不存在
数字a第一次来的时候, one标记a存在, two不变
数字a第二次来的时候, one标记a不存在, two标记a存在
数字a第三次来的时候, one不变, two标记a不存在

构造这样一种运算,通过异或将数据保存在one和two里面。

Pseudocode

def solve2(array):
    one = 0, two = 0
  for i in range(array):
      one = (one ^ array[i]) & ~two
    two = (two ^ array[i]) & ~one
  return one, two

array = input()
_, res = solve2(array)

### Source code

#!/usr/bin/env python

def solve(array):
   one, two = 0, 0
   for i in array:
       one = (one ^ i) & ~two
       two = (two ^ i) & ~one
   return one, two


if __name__ == '__main__':
   array = input()
   array = array.split(' ')
   array = list(map(lambda x: int(x), array))
   # print(array)
   _, res = solve(array)
   print(res)

Test

#!/usr/bin/env python3
import random

def test():
    """
    测试
    """
    array = []
    n, m = 3, 2
    numberofNum = random.randint(100, 1000)

    record = {}
    for _ in range(numberofNum):
        temp = random.randint(10, 10000)
        while temp in record:
            temp = random.randint(10, 10000)
        record[temp] = 1
        for _ in range(3):
            array.append(temp)

    temp = random.randint(10, 1000)
    while temp in record:
        temp = random.randint(10, 1000)

    array.append(temp)
    array.append(temp)

    from run import solve
    _, res = solve(array)
    if res != temp:
        print('ERROR')
        print(array, temp)
        input()
    else:
        print('Pass: res: ', res, 'temp:', temp)

for i in range(50):
    test()

Use python generate data to test.

Discussion and improve

如果n不是3,那么需要构造更多的临时变量。

很长的数组

题目

一个很长很长的short型数组A,将它分成m个长为L的子数组B1,B2,…,Bm,其中每个数组排序后都是递增的等差数列,求最大的L值。

$$ 例如,A = \{-1, 3, 6, 1, 8, 10\} 可以分成B_1 = \{-1, 1, 3\}, B_2 = \{6, 8, 10\},\; L = 3 即为所求。 $$

算法分析

首先进行排序,然后开始分三步走。

  1. 统计元素个数 O(n)

  2. 排序 O(nlog(n))

第一步用来枚举L和m的大小,由题目可知,L * m = 数组的长度。从m为1开始枚举,保证得到的L为最大值。

第二步搜索为深搜,确定当前子数组的起点和初始步长,使用pos记录当前数组选定的元素。

第三步枚举,根据起点给定的初始步长,开始枚举步长,如果枚举的步长可以在数组中找到足够的元素,即数字为L,那么记录这种分法,开始枚举下一个起点。如果枚举的步长和起点无法满足条件,回溯到上一个节点,把上一个节点记录的步长+1再一次搜索。当枚举的起点数达到m,即满足要求输出。

大白话来讲,就是从头开始分原始数组到m个数组中去,排序过后,在前面的每一个节点未被分配的元素,都是子数组起点。如果使用广度优先搜索,即每次都给一个子数组分配一个满足子数组步长要求的数,会导致在最后才发现分配的元素数不满足要求,从而浪费大量时间。

其中,深度优先搜索还有几个剪枝的技巧:

  1. 当前步长*(L-1)如果超过了数组的最大元素,可以不继续搜索

  2. 如果在给定步长的情况下, 下一个数字的大小超过之前的数字+步长,那么可以不必继续搜索。

    因为数组已经排好序。

  3. 还有其他的剪枝技巧,体现在代码中了。

时间复杂度

n为数组长度,排序的时间为 O(nlogn),枚举m时间为n,枚举step时间为65536【short跨度】,枚举全部元素时间为n,因此算法的时间上界为

$$ O(65536n^2) $$

实际情况下,由于剪枝等操作的存在,应优于这个时间。

伪代码

leng = len(Array)
for m=1 to n:
    if n % m != 0:
        continue
    L = n // m
    # deep search
    res, record = findArray(L, m)

def findArray(L, m):
    group = 0
    pos = np.ones(leng)
    record = []
    record_start = []
    while group != m:
        step = 0
        start = getStart(pos)
        res, step = 寻找合适的步长(start, step, pos, record, L)
        if res:
            找到了计数
        while res is False:
            没找到弹出栈,往回找
        if 弹出栈为空:
            不用找了找不到了
   return False, None

源代码

#!/usr/bin/env python3
# coding: utf-8
"""
arrays
"""

from __future__ import print_function
import numpy as np

array = [-1, 3, 6, 1, 8, 10]
# array = [1, 5, 9, 2, 6, 10]
# array = [1, 2, 4, 5, 8, 9, 13, 14]
# array = [1, 2, 4, 7, 11]
array = sorted(array)
print(array)
leng = len(array)
maxn = array[leng-1]
enable = 1
disable = 0


def findJ(j, step, pos, record, L):
    """
    寻找以J为开始,以步长step为开始的数列
    """
    class StepError(Exception):
        pass

    class MaxException(Exception):
        pass

    if pos[j] == disable:
        return False
    start = array[j]
    pre = start
    record_temp = []

    # remember zero
    try:
        for step in range(step, 40000):
            # 把第一个数字记录
            record_temp.append(j)
            pos[j] = disable
            pre = start

            if start + step * (L - 1) > maxn:
                raise MaxException

            try:
                cnt = 1
                if cnt == L:
                    record.append(record_temp)
                    return True, step

                for k in range(j, leng):

                    if pos[k] == disable:
                        continue
                    elif pos[k] == enable and array[k] == pre + step:
                        record_temp.append(k)
                        pre = array[k]
                        cnt += 1
                        pos[k] = disable
                    elif pos[k] == enable and array[k] > pre + step:
                        raise StepError

                    if cnt == L:
                        record.append(record_temp)
                        return True, step

            except StepError:
                # 重置标记
                for r in record_temp:
                    pos[r] = enable
                record_temp = []

    except MaxException:
        # 没有合适的step
        return False, None


def findArray(L, m):
    """
    寻找数组
    """

    pos = np.ones(leng)
    record = []
    record_start = []
    group = 0

    while group != m:
        start = 0
        while pos[start] == disable:
            start += 1

        step = 0
        res, step = findJ(start, step, pos, record, L)
        if res:
            group += 1
            record_start.append((start, step))
        while res is False:
            try:
                start, step = record_start.pop()
                for r in record.pop():
                    pos[r] = enable
                group -= 1
                res, step = findJ(start, step+1, pos, record, L)
            except IndexError:
                return False, None
    return True, record


def divideArray():
    """
    分离数组
    m 是分离的数组的个数
    L 是分离的数组的长度
    """
    for m in range(1, leng+1):
        if leng % m != 0:
            continue

        L = leng // m
        res, record = findArray(L, m)

        def trans(x):
            return array[x]

        if res:
            print('lenth: ', L)
            for r in record:
                temp = map(trans, r)
                print(list(temp))
            return

    print('No result.')


if __name__ == '__main__':
    divideArray()

测试

测试样例生成结果未必准确,找了部分的测试样例,可以通过修改代码中array来提现。

讨论

  1. 在记录了起点和步长,应该可以利用这两点推出当前使用了哪些元素,如果空间大小不够使用,可以不适用record记录,如果下一层不满足条件回溯的时候,可以利用起点和步长回推已经使用的元素。

查看原文

赞 7 收藏 28 评论 0

乖小鬼YQ 回答了问题 · 2017-10-27

解决前端CSS求助:请帮我看下这个demo是怎么回事?

看这篇文章了解下吧
CSS float浮动的深入研究、详解及拓展(一)

以及后续 二

关注 4 回答 3

乖小鬼YQ 回答了问题 · 2017-10-27

解决JS数组排序中sort内置的排序方法是什么

V8 引擎 sort 函数只给出了两种排序 InsertionSort 和 QuickSort,数量小于10的数组使用 InsertionSort,比10大的数组则使用 QuickSort。

V8的array源码 710行 InnerArraySort func

关注 3 回答 3

乖小鬼YQ 发布了文章 · 2017-10-20

硬广一波 -- 招人帖

美团金融孵化前端团队又开始招人了!我们的团队有多靠谱?目前来过这里的小伙伴就没有想走的!美团金融孵化目前正在经历爆发式的业务增长,现在进入团队将有机会见证美团又一个日订单百万级业务的发展,目前业务日交易已经过亿!并且以大前端为核心的系统正在经历着一轮又一轮新的挑战;
 
此外团队正在向一个业内一流的前端团队方向发展,无论是业务还是技术都会给大家带来足够多的挑战。团队从 1 年前的 2 人快速发展到 30 人规模,后续还有着更大想象空间等你来实现。 (团队多数同学来自 985 院校校招和百度,腾讯,小米,金山等知名公司社招,保证你的队友 100%不会坑到你!)
团队业务涉及 C 端, B 端, M 端,跨越 PC ,移动端,智能设备, NodeJS 服务接入层等,总有一款适合你的定位和职业发展规划。
 

[我们是谁?]

我们正在寻找一群可以一起打造新美大金融平台航母的前端小伙伴,我们可以提供给大家最专业的前端成长环境。我们对能力没有硬素质要求,因为我相信不拘一格的人才的能力是远远超过职位要求中的条件。但是我会希望:
 
1.你有一定年限前端领域工作经验(实话实说,目前通过团队面试的同学 90%以上具备前端领域 2 年以上工作经验);熟悉前端领域常见的技术。
NodeJS 工程师,希望你至少有过业余的 NodeJS 线上项目经验。
如果高级工程师方向,希望你有独立的项目经验,小规模的团队开发组织能力。(需要 3 年以上方向工作经验)
如果架构师方向,希望你有一定的想象力和成功的技术架构实施经验。(需要 3 年以上前端方向工作经验)

2.了解基本的服务器开发, Java , php , NodeJS 皆可,因为我们的小伙伴都是全面发展的好同学。
3.喜欢挑战各种不可能,我鼓励大家干各种疯狂但合理的事情,例如 Node 接管服务端中间层, RN 接管客户端开发等,只要敢于尝试没有什么不可能。

具体一点的技术点

1.熟练掌握各种 Web 前端技术和跨浏览器、跨终端的开发

2.深刻理解 Web 标准,对前端性能、可访问性、可维护性等相关知识有实际的了解和实践经验

3.了解前端构建工具原理及相关配置(Webpack/Rollup 等)

4.热爱前端,对新鲜事物充满好奇心,熟练使用至少一种现代前端框架(如:React/Vue/Angular/Cycle )

5.熟练使用 Nodejs Web 应用程序框架,了解一门后端语言( Python/Go/PHP 等),了解 RESTful API

6.熟悉 ES6+,代码规范,使用 ESLint
 

[我们在干什么?]

1.在新美大平台上构建金融类的应用开发,为业务线的起飞提供有力的技术保障;这听起来好装逼是不是?其实说白了就是搬砖嘛,作为一个在商业公司能存活的团队,搬的一手好砖还是很重要的。
 
2.在尝试各种一体化,前端,后端,客户端统统都是大前端。在这个过程中我们踩坑无数,也在不断填坑,为后人铺平了技术道路。。。
 

[我们能提供啥?]

顶配 MPB ?那是必须的。 15.5 个月 X {正无穷>base>15K } 将是你拿到的现金。。。对于薪资和级别没有上限,至于能拿到多少就看你可以 PK 我们多少轮了。但是对于真正的人才我们的原则还是待遇第一,友谊第二。架构师方向基本上不会提供低于 50w 的 base 。
 
如果对此 JD 有任何疑虑或者想了解的细节,欢迎微信骚扰!
联系方式:
微信 mysoulyourbeat
邮箱 yuqiu@meituan.com

查看原文

赞 4 收藏 2 评论 16

乖小鬼YQ 回答了问题 · 2017-08-31

解决为什么这里的vue.js渲染不出来呢?请问哪里写错了?谢谢。

你需要 https://github.com/vuejs/vue-...

这个来查看你的data里面各个属性的当前值,这样你就能比较好的确定到底是哪里的代码问题。

放在你的这个例子来看,是你没有给你 content2 赋值成功,

return content2没有意义 是不会赋值。 要修改的是 this.content2 = this.content

关注 3 回答 2

乖小鬼YQ 回答了问题 · 2017-08-29

vue v-model值不变的问题

注意看文档, https://vuejs.org/v2/guide/fo...

v-model will ignore the initial value, checked or selected attributes found on any form elements. It will always treat the Vue instance data as the source of truth. You should declare the initial value on the JavaScript side, inside the data option of your component.

For languages that require an IME (Chinese, Japanese, Korean etc.), you’ll notice that v-model doesn’t get updated during IME composition. If you want to cater for these updates as well, use input event instead.

就是说 v-model就是监听的change,而不是input,在pc上面这两个是有区别。

关注 2 回答 1

乖小鬼YQ 回答了问题 · 2017-08-02

解决事件绑定时,用console.log有效,用alert失效

因为你弹完这个alert之后,浏览器就阻塞了,然后你是不是要去点确定,这个时候就不会触发接下来的mouseup 和 click。

假如你把 mousedown这个监听删除掉,或者改成 console.log, 就会发现后面的都会触发。

关注 8 回答 7

乖小鬼YQ 回答了问题 · 2017-08-01

解决vue2.x如何实现事件冒泡绑定?

没有想到哪里需要用这种模式,来解决问题,而且 你这里明显会报错,item 在ul的作用域不存在。

还是说说你的需求比较好。

关注 5 回答 4

认证与成就

  • 获得 222 次点赞
  • 获得 6 枚徽章 获得 1 枚金徽章, 获得 1 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2014-05-14
个人主页被 3.1k 人浏览