编程题 | 小马智行题目

绝地灬酷狼 2023-07-24 02:59 6阅读 0赞

题目描述：

有N个石头，从第一个石头跳到第N个石头。每个石头的颜色为Ci，第i个石头往后跳只有两种跳法： 1. 往后跳一个； 2. 往后直接跳到相同颜色的石头上。 问： 从第一个石头跳到第N个石头，最少的步数是多少？

输入： 第一行为N，第二行表示各石头的颜色

1 2 4 1 4 2

输出：

2 （备注： 1->2->2）

--------------------

解答：

思路为递归函数，但是考虑到时间效率，需用循环结构从后往前实现。另外可用map<key, value>结构 计算第i个位置对应的下一相同颜色的位置，从而避免再用循环结构以提高效率。

//
    // Created by max on 2020/4/4.
    //
    #include <iostream>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <cstdio>
    #include <map>
    using namespace std;
    
    int main()
    {
        int N;
        scanf("%d",&N);
        vector<int> Vec(N,0);
        vector<int> index(N, 0);  // 第i个位置对应的下一相同颜色位置
        map<int, int> m;
        int a;
    
        for(int i=0; i<N; ++i)
        {
            cin >> a;
            Vec[i] = a;
            if(m.find(a) == m.end())
            {
                m[a] = i;
            } else
            {
                int b = m[a];
                index[b] = i;
                m[a] = i;
            }
        }
    
        vector<int> ans(N,0);  // ans为递归函数
        ans[N-1] = 0;
    
        int start = N-2;
        while( start >= 0 )
        {
            int k = index[start];
            if(k == start + 1 || k == 0)
            {
                ans[start] = 1 + ans[start+1];
            }
            else
            {
                ans[start] = min( 1+ ans[start+1], 1+ ans[k] );
            }
            start--;
        }
    
        cout << ans[0] << endl;
    
        return 0;
    }