Inplace Stable Partition

最小窗口包含最多颜色的问题

赵成 posted @ Apr 07, 2012 10:42:46 PM in 算法 , 1322 阅读

下面这个题是我在电话面试里被问到的,确实有一个很简单的解法,但是我觉得现场尤其是电话面试里给出线性时间解法基本就是不可能的,除非以前遇到过相似的问题。所以很难说这种题目考察出来的究竟是你编码的能力,还是说考察你有没有碰巧做过类似的题目。好了,吐槽完毕。

传说百度笔试题目:

有一串首尾相连的珠子,共有m个,每一个珠子有一种颜色,并且颜色的总数不超过n(n<=10),求连续的珠子的颜色总数为n时,长度最小的区间。可简述思路或者给出伪代码,并且给出时间和空间复杂度分析。

这个题目实际上和“字符串内寻找包含所有字符的最小子字符串”的问题是一样的,而且更简单,我的解法的思路来自这里

最不靠谱的解法就是通过下标来循环遍历,这类问题最好以窗口的方式思考,通过移动窗口的左右边来寻找最佳的答案。

假设窗口的左右边为begin和end,初始时都指向第一个元素,接着移动end,直到找到第一个符合要求的窗口(即包含所有颜色),然后移动begin,在保证窗口符合要求的情况下尽可能地减小窗口大小,减小到最少时我们就得到了一个可能的解。然后再移动endbegin,循环往复,直到end走到尽头。

这样最坏情况下begin和end都会移动n次,也就是时间复杂度O(n)

实现细节:

移动begin时如何保证满足窗口要求?

要求实际上就是每种颜色至少出现一次,移动end时可以记录下每种颜色出现的次数,接着begin所在的颜色只要数目大于1,就可以继续移动(要记得移动后减小颜色数目)

这个题目之前也有他人做过,在这里,答案有些太复杂了。

如果考虑到环的情况,可以用下面两种方法补充:

  1. 数组原样在后面接上一份,如ABC变为ABCABC
  2. 遍历时改为遍历到2n -1,写下标时取模,如end变为end%n

代码如下:

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

int minimum_interval(int *a, int n, int m, int *ob, int *oe)
{
    int found[m];
    bzero(found, m * sizeof(int));

    int count = 0;
    int min = INT_MAX;
    int begin, end;
    for (begin = end = 0; end < n; ++end) {
        if (!found[a[end]])
            ++count;
        ++found[a[end]];

        if (count == m) {
            while (found[a[begin]] > 1) {
                --found[a[begin]];
                ++begin;
            }

            if (end - begin < min) {
                *ob = begin;
                *oe = end;
                min = end - begin;
            }
        }
    }

    return count == m;
}

int main(int argc, char *argv[])
{
    int a[] = { 0, 1, 1, 0, 0, 0, 2, 3, 3, 4, 5, 6, 1 };
    int begin, end;
    minimum_interval(a, 13, 7, &begin, &end);
    printf("begin: %d, end: %d\n", begin, end);
    for (int i = begin; i <= end; i++) {
        printf("%d ", a[i]);
    }
    
    return 0;
}
seo service london 说:
Jan 16, 2024 07:12:32 PM

Thanks so much for the blog post.Really thank you! Much obliged

먹튀폴리스신고 说:
Feb 07, 2024 01:40:49 PM

One present why galore businesses opt for postcards is because they are overmuch cheaper to be prefab and this can forbear a lot of expenses on the lengthened run. 

온라인카지노추천 说:
Feb 07, 2024 02:05:34 PM

Thanks for the Evoy link. What he says makes sense to me: blogging is an ancillary or supplemental tool, not the primary method, of making money online. Everyone reading this post should click on the Evoy link Elizabeth provided in comment #1 above.

토토사이트 说:
Feb 07, 2024 02:12:18 PM

I believe the most important thing is to put passion in whatever you do. If you write a blog just to make a few bucks and you don’t add passion in the mix, it won’t last very long.

안전토토사이트 说:
Feb 07, 2024 02:23:58 PM

 I just tripped upon your blog and wanted to say that I have really enjoyed reading your blog stations. Thanks for sharing. It can be easily remembered by the people. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. It can be easily remembered by the people.

토토쿠 说:
Feb 07, 2024 02:28:41 PM

This is actually the kind of information I have been trying to find. I am really happy with the quality and presentation of the articles. Thanks for this amazing blog post this is very informative and helpful for us to keep updating. This post is very informative on this topic.

안전놀이터검증 说:
Feb 07, 2024 02:35:20 PM

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here!

먹튀사이트 说:
Feb 07, 2024 02:42:17 PM

That is the incredible mentality, in any case is simply not assist with making each sence at all proclaiming about that mather. Basically any strategy an abundance of thanks notwithstanding

메이저놀이터추천 说:
Feb 07, 2024 02:51:01 PM

I had attempt to advance your own article in to delicius all things considered it’s anything but a predicament utilizing your data destinations would you be able to please reverify the thought. much appreciated again

토토사이트 说:
Feb 07, 2024 03:00:32 PM

They also need to be good communicators, as they will often need to explain their ideas to clients and contractors. In addition, interior designers should have a good understanding of how different materials and finishes can impact a space. 

더킹카지노 说:
Feb 07, 2024 03:08:41 PM

This article was written by a real thinking writer without a doubt. I agree many of the with the solid points made by the writer. I’ll be back day in and day for further new updates.

사설토토 说:
Feb 07, 2024 03:14:06 PM

Your blogs further more each else volume is so entertaining further serviceable It appoints me befall retreat encore. I will instantly grab your rss feed to stay informed of any updates.

먹튀검증사이트 说:
Feb 07, 2024 03:25:57 PM

Good website! I truly love how it is easy on my eyes it is. I am wondering how I might be notified whenever a new post has been made. I have subscribed to your RSS which may do the trick?

먹튀대피소 说:
Feb 07, 2024 03:32:35 PM

That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea.

안전놀이터 说:
Feb 07, 2024 03:39:43 PM

This unique in fact perhaps even a very good arrange that i believe it or not in fact really enjoyed looking into. It is not necessarily consequently routine that i range from the substitute for verify a precise detail.

메이저놀이터 说:
Feb 07, 2024 03:42:31 PM

Hey all, I recently identified your internet site each and every The major search engines tiny searching for just like sort of educative support furthermore kinds shed light on beholds unbelievably excellent i think.

온라인카지노순위 说:
Feb 07, 2024 03:45:55 PM

Hmm… As i fully grasp weblogs having a linked problem, all the same as i do not ended pictures web page. As i added in from the piece that can help populars moreover i’ll quite possibly possibly be people specific primer.

안전카지노사이트 说:
Feb 07, 2024 03:55:56 PM

Behind every enchanting moment is a meticulous planning process orchestrated by Purnima. From the choice of settings to the smallest details, her commitment to perfection ensures that each encounter surpasses expectations. It's not just companionship; it's a symphony of carefully orchestrated elements that culminate in an unforgettable experience.

토토하이 说:
Feb 07, 2024 04:01:39 PM

Celie body wave, deep wave, curly hair, loose wave, wet wavy, kinky straight and more charming sexy hairstyles always keep accompany with you on the way to beauty.

เว็บไซท์ แทงบอลออนไล 说:
Feb 07, 2024 04:10:04 PM

Love to read it,Waiting For More new Update and I Already Read your Recent Post its Great Thanks.

안전놀이터 说:
Feb 07, 2024 04:12:56 PM

I am jovial you take pride in what you write. It makes you stand way out from many other writers that can not push high-quality content like you.

안전토토사이트 说:
Feb 07, 2024 04:15:58 PM

One present why galore businesses opt for postcards is because they are overmuch cheaper to be prefab and this can forbear a lot of expenses on the lengthened run. 

토토사이트추천 说:
Feb 07, 2024 04:21:38 PM

Thanks for the Evoy link. What he says makes sense to me: blogging is an ancillary or supplemental tool, not the primary method, of making money online. Everyone reading this post should click on the Evoy link Elizabeth provided in comment #1 above.

메이저놀이터 说:
Feb 07, 2024 04:25:55 PM

I believe the most important thing is to put passion in whatever you do. If you write a blog just to make a few bucks and you don’t add passion in the mix, it won’t last very long.

먹튀신고 说:
Feb 07, 2024 04:32:32 PM

 I just tripped upon your blog and wanted to say that I have really enjoyed reading your blog stations. Thanks for sharing. It can be easily remembered by the people. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. It can be easily remembered by the people.

토토사이트검증 说:
Feb 07, 2024 04:35:38 PM

This is actually the kind of information I have been trying to find. I am really happy with the quality and presentation of the articles. Thanks for this amazing blog post this is very informative and helpful for us to keep updating. This post is very informative on this topic.

토토사이트 说:
Feb 07, 2024 04:38:32 PM

I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here!

먹튀신고 说:
Feb 07, 2024 04:46:40 PM

That is the incredible mentality, in any case is simply not assist with making each sence at all proclaiming about that mather. Basically any strategy an abundance of thanks notwithstanding

온라인카지노이용방법 说:
Feb 07, 2024 04:50:32 PM

I had attempt to advance your own article in to delicius all things considered it’s anything but a predicament utilizing your data destinations would you be able to please reverify the thought. much appreciated again

토토사이트 说:
Feb 07, 2024 04:55:17 PM

They also need to be good communicators, as they will often need to explain their ideas to clients and contractors. In addition, interior designers should have a good understanding of how different materials and finishes can impact a space. 

메이저안전놀이터 说:
Feb 07, 2024 05:00:37 PM

This article was written by a real thinking writer without a doubt. I agree many of the with the solid points made by the writer. I’ll be back day in and day for further new updates.

토토검증사이트 说:
Feb 07, 2024 05:56:05 PM

Your blogs further more each else volume is so entertaining further serviceable It appoints me befall retreat encore. I will instantly grab your rss feed to stay informed of any updates.

먹튀사이트조회 说:
Feb 07, 2024 06:06:10 PM

Good website! I truly love how it is easy on my eyes it is. I am wondering how I might be notified whenever a new post has been made. I have subscribed to your RSS which may do the trick?

메이저놀이터 说:
Feb 07, 2024 06:14:48 PM

That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea.

먹튀검증 说:
Feb 07, 2024 06:29:26 PM

This unique in fact perhaps even a very good arrange that i believe it or not in fact really enjoyed looking into. It is not necessarily consequently routine that i range from the substitute for verify a precise detail.

먹튀검증사이트 说:
Feb 07, 2024 06:35:22 PM

Hey all, I recently identified your internet site each and every The major search engines tiny searching for just like sort of educative support furthermore kinds shed light on beholds unbelievably excellent i think.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter