分类 算法 下的文章

最近微软的How-Old刷爆了朋友圈,这是一次学术研究与日常生活的结合。实际上还有许多研究与我们密切相关,比如我的研究方向——图像运动复原,可以将该技术应用于相机抖动图像的恢复。然而PC端软件日趋衰落,移动端使用量逐步增长,由于手机处理能力有限,而图像恢复技术需要很大的CPU与内存资源,将该算法部署在云端,所有处理都在云端进行,手机负责传输图像,那么该问题轻松解决。

实施方案:
(1)核心算法:C/C++实现,支持GPU加速,性能指标:10s内处理5000*5000分辨率图像;
(2)交互设计:WEB方式,接收、返回处理结果,实施技术JSP或Python

项目架构:
(1)WEB(Python OR JSP)作为前台访问,底层使用C/C++实现核心算法;
(2)考虑到移动设备处理能力有限,软件维护的代价,以web/host方式较为合理;
(3)后期考虑开发API接口;

技术细节:
(1)流量成本:移动端图像高质量压缩,再减少流量传输同时,尽量保存图像细节;
(2)项目部署:云端

Given a string s and a dictionary of words dict, determine if s can be
segmented into a space-separated sequence of one or more dictionary
words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

题目来自Leeocode:https://oj.leetcode.com/problems/word-break/

最容易想到的方法是递归算法,先判断字符串前部分是否构成单词,若构成再按照同样方法判断后半部分,写成数学形式更易理解(自顶而上):
(1)设f[1,n]表示字符串1~n位置是否能构成单词,f[1,n]即为最终解;
(2)f[1,n]可以分解为f[1,i]&f[i+1,n],1<=i<n,即f[1,n]=f[1,i]&f[i+1,n];

一、递归算法(深搜)
递归算法每次判别f[1,i]是否输入unodered_set(dict),一旦判断为单词,分解为小规模问题f[i+1,n]。但是递归算法效率很低,提交时Time Limited

bool isWord(int k,string s,unordered_set<string> &dict)
{
    if(k==s.length())
        return true;
    for(int i=k;i<s.length();i++)
    {
        string str;
        for(int j=k;j<=i;j++)
            str.push_back(s[j]);

        if(dict.find(str)!=dict.end())
            if(isWord(i+1,s,dict))
                return true;
    }
    return false;
}

bool wordBreak1(string s, unordered_set<string> &dict) 
{
    for(int i=0;i<s.length();i++)
    {
        string str;
        for(int j=0;j<=i;j++)
            str.push_back(s[j]);

        if(dict.find(str)!=dict.end())
            if(isWord(i+1,s,dict))
                return true;
    }
    return false;
}

- 阅读剩余部分 -

1、Single Number:Given an array of integers, every element appears twice except for one. Find that single one.
异或,不仅能处理两次的情况,只要出现偶数次,都可以清零。

int singleNumber(int A[], int n) 
{
    // 数字范围不清楚,bitmap失败
    int x=0;
    for(size_t i=0;i<n;++i)
        x^=A[i];
    return x;
}

- 阅读剩余部分 -

字符串匹配:有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

一、strstr()函数
strstr() 函数搜索一个字符串在另一个字符串中的第一次出现。找到所搜索的字符串,则该函数返回第一次匹配的字符串的地址;如果未找到所搜索的字符串,则返回NULL。
strstr(const char *s1,const char *s2)函数从串s1首部开始逐个比较s2,并判断是否为s1的子串,算法复杂度为O(mn)。

一种实现方式:

char* substr(const char *str,const char *substr)
{
    int m=strlen(str);
    int n=strlen(substr);
    if(m<n)
        return NULL;
    else
    {
        for(int i=0;i<=m-n;i++)
        {
            int k=i,j=0;
            while(str[k++]==substr[j++] && k<m && j<n);
            if(j==n)
                return (char*)(str+i);
        }
        return NULL;
    }
}

- 阅读剩余部分 -

动态规划和贪心算法是常见的分治策略,将问题分解成若干规模较小的相同问题,通过合并求解相对容易的子问题得到原问题的解。

一、最长公共子序列(LCS)
给定两个字符序列,不要求所求的字符序列在所给的字符串中是连续的,求解最大公共序列。
设序列X=<x0,x1,x2,...xm>和Y=<y0,y1,y2,...yn>,最长子序列为Z=<z0,z1,z2,...,zk>
(1)xm==yn,必然有xm==yn==zk,<z0,z1,z2,...,zk-1>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn-1>的子序列;
(2)xm!=yn且xm!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn>的子序列;
(3)xm!=yn且ym!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm>和<y0,y1,y2,...yn-1>的子序列;
即:
LCS(Xm,Yn)=LCS(Xm-1,Yn-1),当xm==yn;
LCS(Xm,Yn)=max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)},当xm!=yn;
转化为递推式:
3.jpg

- 阅读剩余部分 -