一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 749|回复: 17
收起左侧

[动态规划] 发一道碰到的数组题

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
Neroldy 发表于 2019-6-15 15:48:06 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
题目大概是这样的:
给你一个由'.'和'S'组成的长度为N的数组A,你可以最多做K次操作,每次操作选择一个数组中的位置,把相应位置连同左右邻居都变成'.'。
问K次操作之后,数组中最多可以有多少个'.'。
输入:
N K
A
输出
数组A中'.'的个数。

Constraint
1 <= N <= 1000
1 <= K <= 1000

然后我贴几个测试数据
格式:
N K
A
Answer

67 4
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S
48

29 2
.S.....SSSSS.SSSS...SS.SSS.SS
18

79 6
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.
47

743 69
S..S..S.S.S.SS..S...S..S.S.SS...SSS.S...S.S..S.S.SS.SSSSS.SS..SS.SS....SSS.S.S.S..SSS.....S.S.S.S.S..S.SSS..S.SSSSS...SSSSSS..S...S...S.SS.SS.....SS.......S.S.SSS.SSSSSS.S..S...SS.S...SS.SSSSSS.S.S..S..S..S.SS...SS..S..SS.SS.S..SS.S.SS..SSS.S.S.SSS..SS..SSS..S....S..S.S.SSSSSSSSSSSS..S.S.SSS....
563

458 83
..SSSSSS.SSS...SS.S.S..S...S.S..S.....SS.S.S..SSSSSS.SSSS..S.....S.....S.S...S...S....S...S....S.S.SSS....SSS....SSSS.S.........SSSS.S...SS..SS....S.SS..SS.SS.S..SS..SS..SS..SS..S.SS.SSSSSS.S.S....S..S...SS....SS........SS.S....S.S..S.SSSS.S..SSSSSSS.S..S....S.S.SS.SS.SSS.S.....S...S....S..SS...
431

401 72
SSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.S.SSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSS.SSSSSSSSSS.SSSS.SSSSSSS...
238

276 23
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.
100

480 75
SSSS.SSSSSSSSSS.S.SS.SSSSSSSSSSS.SSS.SSSSSSS.SSSS.SSSSSS.SSS.SSSSSSSSSSSS.SSSS.S.SSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSS.SSSSS.SSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSS..SSSSSS.SS.SSSSSSSSSSSS.SSSSSSS.SSSSSSSSSSSS.SSSSSSSSS...
276

试了几个用模板扫的想法总是被一些case卡到,想想了也不知道怎么dp。dfs可以做但是O(2^N)的。


补充内容 (2019-6-17 14:05):
别的大数据有问题,请使用前3个和倒数第2个。抱歉。

补充内容 (2019-6-18 09:29):
再补充一个数据
6 2
S.SSSS
6

评分

参与人数 1大米 +15 收起 理由
14417335 + 15

查看全部评分


上一篇:在leetcode面经上发现一道有意思的题目,大家可以一起讨论一下
下一篇:求Leetcode 最新题库公司分类
我的人缘0
seeker丶 发表于 2019-6-15 21:57:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A,每次贪心地从左到右看是否有连续三个S。如果有则都变成.,然后在链表里删除这三个S;如果没有则看是否连续三个里有两个S,有则都变成.,然后在链表里删除这三个字符;以此类推。这样重复K次。

这是我的证明(不一定对?)
先证明一个引理,第一次选中的三个字符一定出现在K次答案的最优解中。反证,如若不然,则任意一个最优解中都不包含这三个字符:
1. 最优解和这三个字符完全没有重叠:把最优解随便一次变换改成变换这三个字符,则解更优,否则与这三个字符是第一次最优的矛盾。
2. 最优解和这三个字符有一个位置重叠:把最优解包含了重叠字符的变换改成变换这三个字符,则解不比原先差,否则与这三个字符是第一次最优的矛盾。
3. 最优解和这三个字符有两个位置重叠:
3.1 重叠位置在最左或者最右:同理2得把包含重叠部分改成这三个字符不会更差。
3.2 重叠位置是左边一个右边一个:比如a b c d e f g,第一次选择了cde,但最优解包含abc和efg。
现在讨论abc中S的数量,显然abc中S的数量不能多于cde,否则与cde是第一次最优的矛盾。
3.2.1 abc中S的数量等于def中S的数量: 则我们的贪心法由于是从左到右的(关键),会选择abc而不是cde,矛盾;(这里为了排除a-g是S.S.S.S的情况)
3.2.2 abc中S的数量少于def中S的数量:所以abc中S的数量少于等于bcd中S的数量,将abc改成bcd,不会使解更差。

这样就证明了,任意一个最优解,都是包含第一次我们选择的三个字符的,这样我们在链表里删掉这三个字符,就把问题的规模变成了N-3,K-1的一样问题,因此复杂度是O(NK)
我用这个算法试了67 29 79 276这4个case都是没问题的(别的好像数据有点问题)
如果有帮助还请加点大米~ 现在有好多东西都看不到呀

补充内容 (2019-6-15 22:02):
3.2.1 和3.2.2中 应该都是abc中S的数量等于(少于)cde(不是def)中S的数量,笔误~

评分

参与人数 2大米 +12 收起 理由
14417335 + 10
Neroldy + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
zjck1995 发表于 2019-6-16 23:15:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (46)
 
 
0% (0)    👎
[Java] 纯文本查看 复制代码
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Main solver = new Main();
        solver.solve(1, in, out);
        out.close();
    }

    static class Main {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            String s = in.next();
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = s.charAt(i - 1) == '.' ? 1 : 0;
            }
            int[][] dp = new int[n + 1][k + 1];
            for (int i = 1; i <= n; i++) {
                dp[i][0] = dp[i - 1][0] + a[i];
                for (int j = 1; j <= k; j++) {
                    dp[i][j] = dp[i - 1][j] + a[i];
                    if (i >= 3) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 3][j - 1] + 3);
                    }
                }
            }
            int res = 0;
            for (int j = 0; j <= k; j++) {
                res = Math.max(res, dp[n][j]);
            }
            out.println(res);
        }

    }
}

评分

参与人数 2大米 +12 收起 理由
14417335 + 10 没亲测。但是看了两个forloop(N, K)应该不.
Neroldy + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

我的人缘0
seeker丶 发表于 2019-6-18 09:47:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
来贴代码了,昨天睡觉的时候优化到了O(n),其实证明链表里每次断裂后不会产生新的连续3个S(或者1,2个s,如果当前在检查相应的长度)即可,每遍都从前往后扫一遍就可以啦。

[C++] 纯文本查看 复制代码
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <list>
using namespace std;

int solve(string s,int n,int k)
{
    list<int> l;
    int res = 0;
    for(auto i:s){
        if(i=='.') // . converts to 1 and S converts to 0
        {
            res++;
            l.push_back(0);
        }else
            l.push_back(1);
    }
    for(int curCheck = 3; curCheck>=1 && k>0; curCheck--)
    {
        if(l.size()<3)
            break;
        auto i=l.begin(), j=i;
        int windowSum = *(i++);
        windowSum += *(i++);
        while(i!=l.end())
        {
            windowSum += *(i++);
            if(windowSum == curCheck)
            {
                res += curCheck;
                k--;
                if(k == 0)
                    break;
                l.erase(j++);
                l.erase(j++);
                l.erase(j++);
                windowSum =0;
                if(i == l.end())
                    break;
                windowSum += *(i++);
                if(i == l.end())
                    break;
                windowSum += *(i++);
                continue;
            }
            windowSum -= *(j++);
        }
    }
    
    return res;
}

int main(int argc, const char * argv[]) {
    cout<<solve("SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S",67,4)<<endl;
    cout<<solve(".S.....SSSSS.SSSS...SS.SSS.SS",29,2)<<endl;
    cout<<solve(".S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.",79,6)<<endl;
    cout<<solve("SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.",276,23)<<endl;
    return 0;
}

评分

参与人数 1大米 +2 收起 理由
Neroldy + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| Neroldy 发表于 2019-6-15 23:48:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
seeker丶 发表于 2019-6-15 21:57
分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A,每次贪心地从左到右看是否有连续三个S。如果有则都 ...

感谢讨论,干货满满。
我需要再思考一下。
同学说可以用dp做,复杂度差不多也是O(NK),没想到还可以用链表做,学习了。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
Neroldy 发表于 2019/06/15 23:48:22


感谢讨论,干货满满。
我需要再思考一下。
同学说可以用dp做,复杂度差不多也是O(NK),没想到还可以用链表做,学习了。

如果知道了dp的做法麻烦分享一下!

评分

参与人数 1大米 +2 收起 理由
Neroldy + 2 老哥能不能分享一下你链表的代码?

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| Neroldy 发表于 2019-6-17 13:36:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
zjck1995 发表于 2019-6-16 23:15
[mw_shl_code=java,true]public class Main {
    public static void main(String[] args) {
        In ...

不过兄弟这个代码不对吧?

补充内容 (2019-6-17 13:57):
妹的,我智障了,几个大数据有点问题。还请忽略。
回复

使用道具 举报

我的人缘0
 楼主| Neroldy 发表于 2019-6-17 13:58:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
seeker丶 发表于 2019-6-16 10:22
如果知道了dp的做法麻烦分享一下!

我的锅,大数据你会发现字符串没有N那么长,复制的时候出了问题。
dp解法你看楼下兄弟的,比我同学的那个还简洁。
回复

使用道具 举报

我的人缘0
 楼主| Neroldy 发表于 2019-6-17 14:05:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
seeker丶 发表于 2019-6-15 21:57
分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A,每次贪心地从左到右看是否有连续三个S。如果有则都 ...

别的case因为太长,复制的时候出了错,所以只有你测的4个case是争取的。抱歉。
回复

使用道具 举报

我的人缘0
337845818 发表于 2019-6-18 00:41:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   75% (237)
 
 
24% (78)    👎
https://leetcode.com/problems/max-consecutive-ones-iii/

补充内容 (2019-6-18 00:45):
类似的想法, 找at most k 'S'. 但是你这里可以一下改1, 2, 3个S. 所以如果是[1 - 3]个S连一块算一个S. O[n]的解法了

补充内容 (2019-6-18 00:52):
看了看题似乎理解错了.. 只是单纯的找最多的点吗..? 容我测一下

补充内容 (2019-6-18 01:09):
https://paste.ubuntu.com/p/SDkjFnqM8S/
能过你说的前三个跟倒数第二个测试.. 这题是谁理解错了

评分

参与人数 1大米 +2 收起 理由
Neroldy + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-19 04:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表