首页 > 试题广场 >

牛牛的魔法卡

[编程题]牛牛的魔法卡
  • 热度指数:339 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
X轴上有n个点,每个点都对应有数值,你可以从任意点出发,求经过K个不同数值点的最小花费。
在两点移动的花费为两点间的距离。
如果无法经过K个不同数值点,输出 “-1”.

第一行输入两个整数 n,k, 
接下来有n行,每行两个数x,y 分别表示属于数值和坐标
示例1

输入

7,3,[[0,1],[0,2],[1,5],[1,1],[0,7],[2,8],[1,3]]

输出

3

说明

坐标点5出发,经过7、8两个点就经过了3个不同的数值。
所需代价 (7-5)+(8-7) = 3

备注:
其中 1<=n<=10^6, 1<=k<=50
0<=x<k, 0<=y<=1e9
#include <unordered_map>
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param card int整型vector<vector<>> 
     * @return int整型
     */
    int solve(int n, int k, vector<vector<int> >& card) {
        int r = INT_MAX;
        sort(card.begin(), card.end(), [](vector<int>& a, vector<int>& b){return a[1]<b[1];});
        unordered_map<int, int> M;
        for(int i=0,j=0;j<n;j++){
            M[card[j][0]]++;
            while(i<j && M.size()==k){
                r = min(r, card[j][1]-card[i][1]);
                if(--M[card[i][0]] == 0)
                    M.erase(card[i][0]);
                i++;
            }
        }
        return r==INT_MAX?-1:r;
    }
};

发表于 2020-07-25 23:28:12 回复(0)
先按照位置坐标对卡片排序,然后就从左到右找到一个区间,假设这个区间是[I,J],那么牛牛要走的路就是I~J。这个区间可能会有重复的卡片,所以,接下来从左到右缩短这个区间。
每缩短一张卡片,距离就会减少,但是前提是,这个区间还包含着k种卡片,所以一旦减少到不包含k张牌,区间右端点J就要向右移动,然后找到新的区间包括k种牌,然后重复上述过程。
综上所述,区间端点,I、J不断右移,只要记住所有满足“”包含k种牌”的区间的最小长度即可。
发表于 2020-07-21 09:54:30 回复(0)
tag是二分,但是想了一会儿感觉好像没啥好的二分的思路,二分答案貌似可行,不过这题滑窗的思路更简单,类似lc76滑就完事儿了
public int solve (int n, int k, int[][] card) {
    // write code here
    Arrays.sort(card, (c1,c2)->c1[1]-c2[1]);
    int INF = Integer.MAX_VALUE;
    int left = 0;
    int count = 0;
    int[] freq = new int[k+1];
    int res = INF;
    for (int right = 0; right < n; right++) {
        if (freq[card[right][0]] == 0) {
            count++;
        }
        freq[card[right][0]]++;
        while(left<=right && count == k){
            res = Math.min(res, card[right][1] - card[left][1]);
            freq[card[left][0]]--;
            if (freq[card[left][0]]==0) {
                count--;
            }
            left++;
        }
    }
    if (res == INF) {
        return -1;
    }
    return res;
}


发表于 2020-08-31 17:45:45 回复(0)
bool cmp(vector<int> & a, vector<int> & b){
	return a[1] < b[1];
}
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param card int整型vector<vector<>> 
     * @return int整型
     */
    int solve(int n, int k, vector<vector<int> >& card) {
        // write code here
		const int N = card.size();
		sort(card.begin(), card.end(), cmp);
		vector<int> cnt(k,0);
		int seem = 0;
		int left = 0;
		int ans = INT32_MAX;
		for( auto c : card){
			cnt[c[0]] ++;
			if(cnt[c[0]] == 1){
				seem++;
			}
			if(seem == k){
				ans = min(ans, c[1] - card[left][1]);
				while(left<N && cnt[card[left][0]] > 1){
					cnt[card[left][0]] --;
					left++;
					ans = min(ans, c[1] - card[left][1]);
				}
			}
		}
		return (seem == k? ans : -1);
    }
};

发表于 2020-07-23 21:38:26 回复(0)