2 weiwei niunuan weiwei_niunuan 于 2016.01.29 07:08 提问

IT公司面试题 用网上的dp代码 挂了 请问正确的dp该怎么写

面试官给我出了道老题, 我用了一亩三分地上的dp解答,来源如下
http://www.1point3acres.com/bbs/thread-145290-1-1.html

题目如下:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号,正号代表有两个前面的字符,负号代表有四个,也就是说s2其实是"aabbcccc",不考虑invalid。
在s1中,找出连续或者不连续的s2,也就是说从s1中找出"aa....bb.....cccc",abc顺序不能变,但是之间可以有零个或多个字符,返回共有多少个。在上面这个例子中,有四个。
结果测试sln.findMatches("aaaaaa", "a+a-") ,出来结果为0,不对,挂了
另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
不知道用dp正确的解答应该是什么?有人能给出正确的dp代码吗?

以下是从拷贝的测试用例不通过的代码:

 public class Solution {
        public int findMatches(String s1, String s2){
       int len1 = s1.length(), len2 = s2.length();
       if (len2 > len1) return 0;
       if (len2 == 0 || len2 %2 != 0) return 0;
       // DP matches each pattern
       // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
       int[][] dp = new int[len1 + 1][len2 / 2 + 1];
       // no match for dp[0][j]
       for (int i = 1; i < len1; i++){
           dp[i + 1][0] = 1;
           for (int j = 0; j < len2 / 2; j++){
               dp[i + 1][j + 1] = dp[i][j + 1];
               if (isMatch(s1, s2, i, j)){
                   if (s2.charAt(2*j + 1) == '+')
                       dp[i + 1][j + 1] += dp[i - 1][j];
                   else
                       dp[i + 1][j + 1] += dp[i - 3][j];
               }
           }
       }
       return dp[len1][len2 / 2];
  }

   boolean isMatch(String s1, String s2, int i, int j){
       char c = s2.charAt(j * 2);
       char p = s2.charAt(j * 2 + 1);
       int len = p == '+' ? 2 : 4;
       if (i - len < -1) return false;
       for (int h = i - len + 1; h <= i; h++){
           if (s1.charAt(h) != c) return false;
       }
       return true;
   }

   public static void main(String[] args){
           Solution sln = new Solution();

           System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));  // 4

           System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); // 5 ???  I think it should be 2
           System.out.println(sln.findMatches("aaaaaa", "a+a-"));//0  wrong!
   }
}

7个回答

caozhy
caozhy   Ds   Rxr 2016.01.29 08:05
已采纳

拿C#给你写了一个

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
            string s2 = "a+b+c-";
            List<string> list = new List<string>();
            for (int i = 0; i < s2.Length; i += 2)
            {
                list.Add(new string(s2[i], s2[i + 1] == '+' ? 2 : 4));
            }
            List<List<int>> idx = list.Select(x => new List<int>()).ToList();
            for (int i = 0; i < s1.Length; i++)
            {
                for (int j = 0; j < list.Count; j++)
                {
                    if (i <= s1.Length - list[j].Length && s1.Substring(i, list[j].Length) == list[j])
                    {
                        idx[j].Add(i);
                    }
                }
            }
            List<List<int>> result = idx[0].Select(x => new List<int>() { x }).ToList();
            for (int i = 1; i < idx.Count; i++)
            {
                result = result.SelectMany(x => idx[i].Where(y => y >= x.Last() + list[i - 1].Length).Select(y => x.Concat(new int[] { y }).ToList())).ToList();
            }
            foreach (var item in result) Console.WriteLine(string.Join(",", item));
            Console.WriteLine(result.Count);
        }
    }
}

caozhy
caozhy   Ds   Rxr 2016.01.29 07:42

太困了,代码不写了,觉得你的思路差不多,先找出所有的单个的匹配(开始的索引)放入数组,然后将它们排列组合,取得递增的组合。

caozhy
caozhy   Ds   Rxr 2016.01.29 08:06

10,20,28
10,20,64
10,56,64
41,56,64
4
Press any key to continue . . .

caozhy
caozhy   Ds   Rxr 2016.01.29 08:09

另外System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-")); 跑出来是5,感觉正确结果应该是2
就是5
(每个数字代表一个匹配的下标)

10,20,24,30
10,20,24,66
10,20,30,66
10,20,31,66
10,20,32,66
5
Press any key to continue . . .

caozhy
caozhy   Ds   Rxr 2016.01.29 08:29
        string s1 = "aaaaaa";
        string s2 = "a+a-";

输出
0,2
1
Press any key to continue . . .

WinsenJiansbomber
WinsenJiansbomber   2016.01.29 08:57

竟然不知DP为何物!

caozhy
caozhy 回复Jimbo: 一字能差么?我说你很精神,我是夸你。我说你是神经,我就是骂你了。
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 嘿嘿,這個叫做一字之差麼
2 年多之前 回复
caozhy
caozhy 回复Jimbo: Dynamic Programming
2 年多之前 回复
WinsenJiansbomber
WinsenJiansbomber 明白 Dynamic Process
2 年多之前 回复
caozhy
caozhy dp就是动态规划。
2 年多之前 回复
caozhy
caozhy dp就是动态规划。
2 年多之前 回复
91program
91program   Ds   Rxr 2016.01.29 09:15

直接用一亩三分地上的dp解答来解答,挂了估计是考官在你之前已经看过你给的答案

91program
91program 回复caozhy: 我只是说明了一种可能,和 LZ 说的清楚不清楚有什么关系呢?
2 年多之前 回复
91program
91program 回复caozhy: 这又能说明什么!难道能说明考官就没有看过?
2 年多之前 回复
caozhy
caozhy 那个程序是错的,没有通过最后一个测试用例。lz说的很清楚。
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
高效面试之动态规划DP
解题关键: 理解结构特征,抽象出状态,写成状态转移方程。 题目索引 1.三角形找一条从顶到底的最小路径 分析 设状态为 f (i; j ),表示从从位置 (i; j ) 出发,路径的最小和,则状态转移方程为 f(i,j)=min{f(i+1,j),f(i+1,j+1)}+(i,j)   2.最大子数组和 设状态为 f[j],表示以 S[j] 结尾的最大
DP合集
1. 一个100层的大厦,你手中有两个相同的玻璃球。从这个大厦的某一层扔下围棋 子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面
状态压缩与动态规划(DP)---编程之美---瓷砖覆盖地板---POJ2411
一、状态压缩 从状态压缩的特点来看,这个算法适用的题目符合以下的条件: 1.解法需要保存一定的状态数据(表示一种状态的一个数据值) ,每个状态数据通常情况下是可以通过 2 进制来表示的。这就要求状态数据的每个单元只有两种状态,比如说棋盘上的格子,放棋子或者不放,或者是硬币的正反两面。这样用 0 或者 1 来表示状态数据的每个单元,而整个状态数据就是一个一串 0 和 1 组成的二进制数。
代码中得到dp值
final int pageMargin = (int) TypedValue.applyDimension(TypedValue.COMPLEX_UNIT_DIP, 4, getResources()                 .getDisplayMetrics());
不写代码,快速实现px转换成dp
有很多朋友在实际的工作中,会遇到设计同事给了一张设计图,上面只有px标注的距离和尺寸。产品看到设计稿后,就拿给iOS和Android的开发,说就按这个做。iOS开发可能还好,虽然也有9种屏幕,但那毕竟是两只手数的来的。但是Android开发可能是心中无数只草泥马奔腾 + 一脸懵逼。。其实我们只要把px转换成dp就可以了,两步走:第1步:确认设计稿中的屏幕dpi是多少 第2步:根据dpi,将px值转
dp转化为px的原因
为什么要进行Dp转化为PX 在xml布局文件中,我们既可以设置px,也可以设置dp(或者dip)。一般情况下,我们都会选择使用dp,这样可以保证不同屏幕分辨率的机器上布局一致。但是在代码中,如何处理呢?很多控件的方法中都只提供了设置px的方法,例如setPadding,并没有提供设置dp的方法。这个时候,如果需要设置dp的话,就要将dp转换成px了。 以下是一个应用类,方便进行px和dp之间的转
ANdroid 代码中设置与布局文件一样的dp高度的引用方法
300dp 这是dimen文件中300dp高度的设置 代码中引入形式为:getResources().getDimensionPixelOffset(R.dimen.popupwindow_width_dingyue)
dp入门———列基本的状态和状态方程
1;了解一下DP的基本原理 我们要找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。 入门网站;http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml;其中的入门题; 硬币问题;如果我们有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够n元;我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们
Android代码获取xml中定义的dp\sp值的方法
android并没有在java代码中直接获取xml中定义的dp\sp的值的API,只有getDimension()、getDimensionPixelOffset()和getDimensionPixelSize()三个函数获取绝对尺寸,关于这三个函数的区别可以参见我的上一个帖子。 为什么不提供获取dp/sp值的函数?可能是因为google认为没有必要,API里的setWidth、setHei
android 中在代码中设置dp单位的组件高度
原文地址:http://write.blog.csdn.net/postedit DisplayMetrics metrics = new DisplayMetrics() getWindowManager().getDefaultDisplay().getMetrics(metrics); int heighDP = Utils. getDPI(height