Word Break II -- LeetCode - Code Ganker - 博客频道 - CSDN.NET
原题链接: http://oj.leetcode.com/problems/word-break-ii/
这道题目要求跟Word Break比较类似，不过返回的结果不仅要知道能不能break，如果可以还要返回所有合法结果。一般来说这种要求会让动态规划的效果减弱很多，因为我们要在过程中记录下所有的合法结果，中间的操作会使得算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面需要历史信息会取不到。所以这道题目我们介绍两种方法，一种是直接brute force用递归解，另一种是跟Word Break思路类似的动态规划。
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。代码如下：
- public ArrayList<String> wordBreak(String s, Set<String> dict) {
- ArrayList<String> res = new ArrayList<String>();
- if(s==null || s.length()==0)
- return res;
- helper(s,dict,0,"",res);
- return res;
- }
- private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)
- {
- if(start>=s.length())
- {
- res.add(item);
- return;
- }
- StringBuilder str = new StringBuilder();
- for(int i=start;i<s.length();i++)
- {
- str.append(s.charAt(i));
- if(dict.contains(str.toString()))
- {
- String newItem = item.length()>0?(item+" "+str.toString()):str.toString();
- helper(s,dict,i+1,newItem,res);
- }
- }
- }
接下来我们列出动态规划的解法，递推式跟Word Break是一样的，只是现在不只要保存true或者false，还需要保存true的时候所有合法的组合，以便在未来需要的时候可以得到。不过为了实现这点，代码量就增大很多，需要一个数据结构来进行存储，同时空间复杂度变得非常高，因为所有中间组合都要一直保存。时间上还是有提高的，就是当我们需要前面到某一个元素前的所有合法组合时，我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。代码如下：
- class Interval {
- int start;
- int end;
- public Interval(int start, int end) {
- this.start = start; this.end = end;
- }
- public Interval(Interval i) {
- start = i.start;
- end = i.end;
- }
- }
- ArrayList<ArrayList<Interval>> deepCopy(ArrayList<ArrayList<Interval>> paths) {
- if (paths==null) return null;
- ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>(paths.size());
- for (int i=0; i<paths.size(); i++) {
- ArrayList<Interval> path = paths.get(i);
- ArrayList<Interval> copy = new ArrayList<Interval>(path.size());
- for (int j=0; j<path.size(); j++) {
- copy.add(new Interval(path.get(j)));
- }
- res.add(copy);
- }
- return res;
- }
- public ArrayList<String> wordBreak(String s, Set<String> dict) {
- ArrayList<String> res = new ArrayList<String>();
- if (s==null || s.length()==0) return res;
- Map<Integer, ArrayList<ArrayList<Interval>>> dp = new HashMap<Integer, ArrayList<ArrayList<Interval>>>();
- dp.put(0, new ArrayList<ArrayList<Interval>>());
- dp.get(0).add(new ArrayList<Interval>());
- for (int i=1; i<=s.length(); i++) {
- for (int j=0; j<i; j++) {
- String cur = s.substring(j, i);
- ArrayList<ArrayList<Interval>> paths = null;
- if (dp.containsKey(j) && dict.contains(cur)) {
- paths = deepCopy(dp.get(j));
- Interval interval = new Interval(j, i);
- for (ArrayList<Interval> path:paths) {
- path.add(interval);
- }
- }
- if (paths != null) {
- if (!dp.containsKey(i)) {
- dp.put(i, paths);
- }
- else {
- dp.get(i).addAll(paths);
- }
- }
- }
- }
- if (!dp.containsKey(s.length())) {
- return res;
- }
- ArrayList<ArrayList<Interval>> paths = dp.get(s.length());
- for (int j=0; j<paths.size(); j++) {
- ArrayList<Interval> path = paths.get(j);
- StringBuilder str = new StringBuilder();
- for (int i=0; i<path.size(); i++) {
- if (i!=0) {str.append(" ");}
- int start = path.get(i).start;
- int end = path.get(i).end;
- str.append(s.substring(start, end));
- }
- res.add(str.toString());
- }
- return res;
- }
可以看出，用动态规划的代码复杂度要远远高于brute force的解法，而且本质来说并没有很大的提高，甚至空间上还是一个暴涨的情况。所以这道题来说并不是一定要用动态规划，有一个朋友在面Amazon时遇到这道题，面试官并没有要求动态规划，用brute force即可，不过两种方法时间上和空间上的优劣还是想清楚比较好，面试官可能想听听理解。实现的话可能主要是递归解法。
还有一点需要指出的是，上面的两个代码放到LeetCode中都会超时，原因是LeetCode中有一个非常tricky的测试case，其实是不能break的，但是又很长，出现大量的记录和回溯，因此一般通过这个的解法是把Word Break先跑一遍，判断是不是能break，如果可以再跑上面的代码。这样做法其实比较傻，但是为了过这个只能这样了，这一点我觉得LeetCode没必要把超时设得这么严格，实际意义不大，只是把AC率给拉了下来哈。
App Store排名算法和Google Play排名算法
App Store:
有下面这样一张图：
图片的意思是：
今天的排名＝今天的下载量x8 + 昨天的下载量x5 + 前天的下载量x5 + 大前天的下载量x2。 很明显，前3天的下载量是最重要的核心排名因素。
下载量永远都会是APP store算法的核心
想想sotre最容易得到的，最直观体现用户对APP喜爱程度的因素是什么——下载量。也许今天很多人认为几次算法更新后，下载量所占算法权重越来越低，但这个核心数据在算法中的比重绝对会是第一位的。
哪些因素可能被app store排名算法因素？
下面这些是我认为会影响第二天排名的一些因素，我以重要程度进行了排序：
1. 下载量：这个谁都懂；
2. 好评比例：今天有多少好评，好评占总评论量多少，这个也是可以当天获得的数据。
3. 当天卸载率：这个数据itunes官方也很容易得到。
4. 当天用户对该APP的使用时长。
5. 用户下载及好评用的IP地址：这会影响APP所在地区的排名。
用户活跃度因素不会是APP排名的重要因素
APPYING认为采集APP活跃度是需要一个时间段的过程，这样采集起来技术上绝对可行，但如果把这个作为app store排名的重要因素，那会更大的降低新APP获得好排名的机会。
Google Play：
指标A=“总安装/总下载”，即下载转安装的转换率；B=“评分/5”，即产品得分比上Market的满分；C=“留存安装/总安装”，即安装的留存率。不要急着问我a、b、c等于多少，准确数值只有Google知道、而且可以调，我只能告诉你它们加起来等于100，还有就是b>max(a,c)
「热门付费项目」、「热门免费项目」，是依照Google Play的新用户安装数来计算，而「最卖座排行榜」则是以依照实际营收来计算。至于「最新热门付费」、「最新热门免费」则是以Google Play旧用户的安装数为主，而且计算周期以「上架后30天内」为主。Ankit Jain说，上架日是以全球上架日(Global Publish Date)为主，因此在单一国家上架后，若逐步推展到其他国家，即便在某国一夕爆红，但是因为超过上架日30天的范围，所以并不会出现在「最新热门」之列。
另外，Ankit Jain也说，常有人问他「我的APP下载量明明比别一款APP多，为什么排名在它后面?」，这是因为Google Play其实不只看安装数，同时也会查看「卸载数」，并且计算两者的比例，当许多用户安装后却又移除，就会影响排名。
除了排行榜之外，Ankit Jain建议开发者可以留意Google Play几个推荐的方式，例如「热门应用程序」(Trending)指的是上架后成长率超过Google Play预期的，就会被列为热门。
分类相关、字词相关、功能相关的APP会被归类在一起呈现，举例来说当用户安装了一个时钟Widget，也许会另外安装其他的Widget。
BOSS系统_通信百科
目前国内还处在BOSS建设的初级阶段，首先能做到的是将业务流程中某个环节中的不同业务进行纵向整合，如帐务管理中的长话、市话、数据各部分的整合，以及服务不同业务的综合客服系统。因为中国移动业务比较单一，所以启动BOSS相对较早，中国联通也有类似的系统，但不叫BOSS，其他如中国网通、中国电信也将会有类似的系统，但建设起来会更加困难。今后的横向整合则使营业、帐务、客户关系以及针对管理层的决策支持各部分共同形成一个有机的整体，将会提高一个电信企业的运营效率。
一般把BOSS系统划分成四个部分：计费及结算系统、营业与账务系统、客户服务系统和决策支持系统。
boss是业务操作支撑系统的简称。BOSS的组成包括：
1.计费及结算系统
狭义的计费系统是指处理计费数据采集和批价两个过程的系统。计费数据采集工作包括计算机从电信基础网络（如交换机、网关等）上收集有关的原始基础数据和信息，进行相应的差错检验，格式转换等预处理，生成的结果只记录了用户使用网络（如通话）的情况，并不体现应向用户收取的费用。而批价的动作则是根据既定的原则和规则，对用户使用网络的情况计算费用。
结算系统是电信企业间的行为，它包括两种情况：一种称为漫游结算，另一种称为互联结算。当互联结算发生在两个甚至多个网络之间时，称为网间结算。结算的流程本身比较复杂，再加上数据量很大，出现得比较晚，使结算系统逐渐区别于传统的计费系统，成为业务运营支撑系统相对独立的组成部分。
2.营业、账务系统
营业系统通常完成的是受理和处理用户的业务请求，而帐务系统是将用户使用电信网络的情况汇总形成帐单。这两个过程在以往是比较单调的，但随着个性化服务的需求越来越强烈，要求系统实现功能的数量越来越多，越来越复杂，建设相对独立、灵活的营业系统和帐务系统的呼声也越来越高。
帐务系统要充分满足客户化的帐务要求。支持灵活，多途径的收费功能，满足客户个性化的帐单及其详细话单，并支持多样化的帐单分发方式；提供强大灵活的客户信用度的管理，完善恶意消费控制和欺诈控制；对市场变化做出迅速反映，方便地支持新品牌、新的资费套餐及其新的服务手段的推出。
3.客户服务系统
客户服务系统原来指的是企业的服务热线，如中国电信的"1000"和中国联通的"1001"等，但随着发展，客户服务系统有了全新的定义和功能。客户服务系统一方面能保证为客户提供快速方便的服务；另一方面保证在未来新业务开放的情况下，系统能及时提供相应的功能保证。从更高的角度来看，客户服务系统要实现多元化服务、个性化服务、交互式服务、异地服务的要求。
多元化服务即系统能为客户提供多种的接入渠道，多项的使用功能，多样的服务项目；个性化服务即能识别客户身份，根据不同客户的要求和系统数据，提供不同的服务和相应的营销，实现准确的服务；交互式服务主要是改变以往只有被动接受客户要求的状况，通过主动地调查市场，与客户联系，了解客户需求提供主动的服务和营销，同时增加系统的客户参与功能，鼓励客户进行自助服务。
这部分与CRM的概念接近。北京电信大客户部总经理赵恒礼认为，CRM是BOSS的一部分；中国移动的宁宇也表示，中国移动现在建的CRM正是基于其BOSS系统。对于电信运营商来说，如何有效地抓住大客户是必须面对的问题，在市场上，保住一个老客户的成本要远远低于新发展一个客户；而且新发展客户的成色怎样，对企业的贡献多大，并不好衡量，因此必须建立一套比较好的CRM。
4.决策支持系统
决策支持系统的主要任务是通过动态、有选择性地采集和更新数据源的有效信息及企业处部相关信息，进行智能化地分析、处理、预测、模拟等，最终向各级决策管理者或专业人员提供及时、科学、有效的分析报告，做好信息、智力支持工作。