美文网首页
笔试刷题-百度2018-06-20

笔试刷题-百度2018-06-20

作者: Dodo159753 | 来源:发表于2018-06-20 07:44 被阅读0次

题目描述:


/**
度度熊有一个N个数的数组,他想将数组从小到大 排好序,但是萌萌的度度熊只会下面这个操作:
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序?
输入描述:
首先输入一个正整数N,接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)


输出描述:
输出一个整数表示最少的操作次数。

输入例子1:
4
19 7 8 25

输出例子1:
2

4
4 3 2 1
*/

思路如下:

第一次把第二小放到最后
第二次把第三小放到最后
以此类推即可
先把Node按照val排序,若val相同按原来输入数据的idx排序即可
Node{val, idx}用idx模拟移动到最后即可
按val排序后就可顺序遍历模拟依次把逆序的第二小或第三小等移动到队尾

代码如下:


#include<stdio.h>
#include<iostream>
#include<algorithm>

#define MAX_N 55

using namespace std;

struct Node
{
    int val=-1, idx=-1;
    Node() {}
    Node(int val, int idx)
    {
        this->val=val;
        this->idx=idx;
    }
    Node(const Node& node)
    {
        this->val=node.val;
        this->idx=node.idx;
    }
    bool operator < (const Node&node) const
    {
        return this->val<node.val;
    }
};

Node nodes[MAX_N];

int main()
{
    int N, idxPtr, cnt=0;
    scanf("%d", &N);
    idxPtr=N;
    for(int i=0; i<N; i++)
    {
        int idx=i, val;
        scanf("%d", &val);
        nodes[i]=Node(val, idx);
    }
    sort(nodes, nodes+N);
    for(int i=1; i<N; i++)
    {
        if(nodes[i-1].idx>nodes[i].idx)
        {
            nodes[i].idx=idxPtr;
            idxPtr++;
            cnt++;
        }
    }
//判断最大的一个是否需要放到队尾
    if(nodes[N-1].idx==N-1 && idxPtr>N)
    {
        nodes[N-1].idx=idxPtr;
        idxPtr++;
        cnt++;
    }
    printf("%d", cnt);
    return 0;
}


相关文章

  • 笔试刷题-百度2018-06-20

    题目描述: 思路如下: 第一次把第二小放到最后第二次把第三小放到最后以此类推即可先把Node按照val排序,若va...

  • 笔试刷题笔记

    C++中运算符重载是多态性的一种表现 运算符重载是针对C++原有运算符进行的,不可能通过重载创造出新的运算符 除了...

  • 公考经验五

    第九篇 笔试阶段。总体说下,笔试备考主要是刷题和一直写申论。行测下载粉笔公考APP去刷题,界面很简洁,题目解释也很...

  • 笔试算法刷题

    原创:王稳钺资料来源:安老师 一、刷题方法与面\笔试能力突破技巧 平时刷题时,市面上大多数尤其以LeetCode为...

  • 腾讯市场策划与推广 笔试+面试

    腾讯笔试+面试 面试岗位 市场策划与推广 笔试篇 腾讯的笔试刷人不多。笔试会先找时间有一轮模拟笔试让你熟悉环境和题...

  • 笔试刷题-百度2018-06-04

    题目描述: 思路如下: 直接bf模拟 采用模拟的方式计数即可,没一个节点有一个idx val, 其实就是一旦发现 ...

  • 笔试刷题-百度2018-06-21

    题目描述: 思路如下: K个小于好把n给数分成了k+1个降序序列descSeq1 descSeq2 ... des...

  • 笔试刷题-百度2018-06-17

    题目描述: 思路如下: 维护3个指针即可 代码如下:

  • 笔试刷题-百度2018-06-24

    题目描述: 思路如下: 设pss为ss一分钟内能吊到鱼概率,根据题意由于其随机一个钓鱼,那么其吊到鱼概率为概率矩阵...

  • 笔试刷题-百度2018-06-25

    题目如下: 思路如下: 题目要求在当前方格只能往右边、下边这任意选择两个方向到达下一个方格若当前方格被阻挡,那么其...

网友评论

      本文标题:笔试刷题-百度2018-06-20

      本文链接:https://www.haomeiwen.com/subject/osltyftx.html