搜狗2019校园招聘笔试-智能图像识别图像研究员

　

搜狗识图

注：图片来源网络。

双指针。参见Minimum Window substring。

#include<iOStream>
#include<vector>
#include<string>
#include<algorithm>
#include <set>
#include <map>
using namespace std;

int minWinSize(const vector<int>& nums, vector<int>& start) {
    set<int> st(nums.begin(), nums.end());
    map<int, int> mp;
    int n = nums.size();
    int res = n;
    int i = 0, j = 0;
    int cnt = st.size();

    while(j < n){
        while (j < n && cnt > 0) {
            if (++mp[nums[j++]] == 1)
                --cnt;
        }

        while (i < j && cnt <= 0) {
            int len = j - i;
            if (len < res) {
                start.clear();
                res = len;
                start.push_back(i);
            }
            else if (len == res) {
                start.push_back(i);
            }

            if (--mp[nums[i++]] <= 0)
                ++cnt;
        }
    }
    return res;
}


int main()
{
    int n; cin >> n;
    vector<int> test(n);
    for (int i = 0; i < n; ++i)
        cin >> test[i];
    vector<int> start;
    int minsize = minWinSize(test, start);
    cout << minsize << " " << start.size() << endl;
    for (auto i : start) {
        printf("[%d,%d] ", i+1, i + minsize);
    }
    cout << endl;
    return 0;
}

以下为旧代码： 

# -*- coding: utf-8 -*-
"""
# @Time    : 2018/9/14 20:17
# @Author  : shen
# @FileName: sogou2018.py
"""

import sys

print("输入数据个数：")
in_num = int(sys.stdin.readline().strip('\n'))
line = []
for i in range(in_num):
    s1 = sys.stdin.readline().strip('\n')
    line.APPend(s1)

line_unique = list(set(line))  # 该数据序列中独特的数据，去重
line_unique_num = line_unique.__len__()

max_len = min(in_num, 10000)  # 最小区间长度的最大值


find_number = 0  # 查找到最小子串的个数
start_index = []  # 查找到最小子串的起始位置
# 循环可能的最小区间长度
for i in range(line_unique_num, max_len+1):
    min_length = i
    for j in range(0, in_num):
        sub_line = line[j: j + i]  # Python有自动的溢出保护，不用边界判断
        sub_line_unique = list(set(sub_line))  # 子串数据去重

        # 子串数据去重后的长度 等于 整个数据序列去重的长度， 则找到最小区间长度
        if sub_line_unique.__len__() == line_unique_num:
            find_number += 1
            start_index.append(j+1)  # 因为数字序列的编号从1开始

    if find_number != 0:
        break

print(min_length, find_number)
for i in start_index:
    print('[%d,%d]' % (i, i + min_length - 1), end=' ')

"""
# 测试1
10
1
1
3
4
6
6
5
1
3
3

6 3
[2,7] [3,8] [4,9]
"""

"""
# 测试2
输入数据个数：
3
1
2
3

3 1
[1,3]
"""

相关阅读

计算机网络常见笔试面试题（一）

本博客内容 一、OSI、TCP/IP、五层协议的体系结构、以及各层协议作用 二、TCP三次握手、四次挥手全过程 三、TCP的三次握手过程？为

京东2018校招产品笔试题：如何用 0.01 元买到一瓶可乐？

昨晚结束了京东今年秋招的专业笔试，产品岗的第一道主观题「如何用 0.01 元买到一瓶可乐？」引起了众多人的讨论，这里初入互联网江湖的

科大讯飞2019校招 笔试

修改成绩 时间限制：C/C++语言 1000MS；其他语言 3000MS 内存限制：C/C++语言 65536KB；其他语言 589824KB 题目描述： 华老师的n个学生参

华为笔试题 Java 2018

华为笔试题 Java 2018 搞到一份题，分享一下，如果你和我一样看不懂，就立下 flag，一起学习 Java， ✈✈✈ 第一题 题目描述 输入任意

滴滴2019校招产品经理笔试题

滴滴2019校招产品经理笔试题题目一题目一 对于一个50层的商业型物业楼，1-10层为百货大楼，11-50层为写字楼。 请规划楼层的经营内容