本文共 10771 字，大约阅读时间需要 35 分钟。

鸡鸭分类（类双指针）

题目描述：

农场有n只鸡鸭排为一个队伍，鸡用“C”表示，鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整，使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻，需要调整队形两次。

输入描述:

输入一个长度为N，且只包含C和D的非空字符串。 输出描述: 使得最后仅有一对鸡鸭相邻，最少的交换次数。

思路：

交换最后得到的结果只有两种，鸡左鸭右，鸭左鸡右

在代码中可以把‘C’都全移到左边或者把‘D’全移到左边，去最小者即可

#include 
   
    #include 
    
      using namespace std; int main(){
       string s;    cin >> s;    int count = 0;    int sumC = 0;    int sumD = 0;    // 把C往左移    for(int i = 0; i
    
   

其中count计数这是第几个c/d（从0开始）i-count为第i个字符需要移动的个数

输入：cin>>“CCDCC” C左移： i=0,s[1]=c,sumc=0+0-0; i=1,s[1]=c,sumc=0+1-1; i=2,s[2]=d; i=3,s[3]=c,sumc=0+3-2; i=4,s[4]=c,sumc=1+4-3=2; D左移： i=0,s[1]=c; i=1,s[1]=c; i=2,s[2]=d,sumd=0+2-0=2; i=3,s[3]=c; i=4,s[4]=c; 输出：cout<<2

比特币最佳买卖时间

题目描述：

给定一个正整数数组，它的第 i 个元素是比特币第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一次），设计一个算法来计算你所能获取的最大利润。注意你不能在买入比特币前卖出。

输入描述:

正整数数组，为以空格分隔的n个正整数 输出描述: 最大利润

#include
   
    using namespace std; int main() {
       int n, mi = INT_MAX, maxProfit = 0;    while(cin >> n) {
    //*****        maxProfit = max(n - mi, maxProfit);        mi = min(n, mi);    }    cout << maxProfit;    return 0;}
   

import java.util.Scanner;import java.util.ArrayList;public class Main{
       public static void main(String[] args){
           Scanner in = new Scanner(System.in);        ArrayList
   
     coin=new ArrayList<>();        while(in.hasNextInt()){
               coin.add(in.nextInt());        }        Integer[] co=new Integer[coin.size()];        coin.toArray(co);        int profit=0;        for(int i=co.length-1;i>=0;i--)            for(int j=0;j
   

爱吃喵粮的小猫（贪心）

题目描述：

小招喵喜欢吃喵粮。这里有 N 堆喵粮，第 i 堆中有 p[i] 粒喵粮。喵主人离开了，将在 H 小时后回来。 小招喵可以决定她吃喵粮的速度 K （单位：粒/小时）。每个小时，她将会选择一堆喵粮，从中吃掉 K 粒。如果这堆喵粮少于 K 粒，她将吃掉这堆的所有喵粮，然后这一小时内不会再吃更多的喵粮。

小招喵喜欢慢慢吃，但仍然想在喵主人回来前吃掉所有的喵粮。返回她可以在 H 小时内吃掉所有喵粮的最小速度 K（K 为整数）。

输入描述:

第一行输入为喵粮数组，以空格分隔的N个整数 第二行输入为H小时数 输出描述: 最小速度K

贪心 + 二分查找

理论最小进食速度： 所有喵粮求和 / 给定的小时数

理论最大进食速度：最大堆的喵粮数

在这两个之间二分查找最小实际可行进食速度即可

注：这是一个lower_bound的二分问题，即求最左边满足条件的值 需要相应修改二分查找

#include 
   
    using namespace std; vector
    
      arr;int H, tmp, sum = 0, res, mmax = 0, mmin;  bool solve(int x, int H) {
   //x为速度    int res = 0;//吃完所有猫粮所需时间    for(int i = 0; i < arr.size(); i++) {
           res += (arr[i] % x == 0) ? arr[i] / x: arr[i] / x + 1;    }    return res <= H;} int main() {
       string line; getline(cin, line);    istringstream iss(line);    while(iss >> tmp) {
           arr.push_back(tmp);        mmax = max(mmax, tmp);        sum += tmp;    }    scanf("\n%d", &H);        mmin = (sum % H == 0) ? sum / H : sum / H + 1; //理论min        while(mmin < mmax) {
     //二分查找终止条件        res = (mmin + mmax) / 2;        if(solve(res, H)) mmax = res;//满足条件时 将右边届设为中间值        else mmin = res + 1;        if(solve(mmin, H)) break;//左边界满足时 终止    }    cout<
     
      <
     
    
   

#include 
   
    using namespace std; int main(){
       int x,h;    vector
    
      p;    while(cin>>x)        p.push_back(x);    int n = p.size()-1;    h = p[n];   //****关于输入的处理        int k = 1, t;    do{
           t = 0;        for(int i=0;i
     
      h);    cout<
      
       <
      
     
    
   

x游戏

题目描述：

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

输入描述:

输入正整数N 输出描述: 输出1到N中好数个数

#include 
   
    using namespace std;bool isGood(int i){
       string s = to_string(i);    string rotate;/****    for(int j=0;j
    
     >n;    for(int i=1;i<=n;i++){
           if(isGood(i)){
               count++;        }    }    cout<
     
      <
     
    
   

跳格子游戏

题目描述：

假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要 跳完n 个格子你才能抵达终点。 每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？ 注意：给定 n 是一个正整数。

输入描述:格子数n

输出描述:跳完n个格子到达终点的方法

状态转移公式：

当前阶梯可以由前一级阶梯跳一级到达，也可由前两级阶梯跳两级到达。

#include 
   
    using namespace std;int main(){
       int n;    cin>>n;    int dp[n] = {
   0};    dp[0] = 1;    dp[1] = 2;    for(int i=2;i
   

糖果分配（动态规划）

题目描述：

假设你是一位很有爱的幼儿园老师，想要给幼儿园的小朋友们一些小糖果。但是，每个孩子最多只能给一块糖果。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的糖果的最小尺寸；并且每块糖果 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个糖果 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 注意： 你可以假设胃口值为正。 一个小朋友最多只能拥有一块糖果。

输入描述:

第一行输入每个孩子的胃口值 第二行输入每个糖果的尺寸 孩子数和糖果数不超过1000 输出描述: 能满足孩子数量的最大值

#include 
   
    using namespace std; int main(){
       string S;    vector
    
      g,s;    getline(cin, S);    stringstream ss1(S);    int x, cnt=0;    while(ss1>>x)        g.push_back(x);    getline(cin, S);    stringstream ss2(S);    while(ss2>>x)        s.push_back(x);            sort(g.begin(), g.end());    sort(s.begin(), s.end());    for(int i=0,j=0;i
    
   

#include
   
    #include
    
     #include
     
      using namespace std;int main(){
       int num;    vector
      
        g;    vector
       
         s;    while(cin>>num)    {
           g.push_back(num);        if(getchar()=='\n')  //*****            break;    }    while(cin>>num)    {
           s.push_back(num);        if(getchar()=='\n')            break;    }    sort(g.begin(),g.end());//****    sort(s.begin(),s.end());    int sum=0;    for(int i=0,j=0;j
        
         =g.size()) break; if(s[j]>=g[i]) { sum++; i++; } } cout<
        
       
      
     
    
   

员工考勤记录（斐波那契）

题目描述：

给定一个字符串来代表一个员工的考勤纪录，这个纪录仅包含以下两个字符： ‘A’ : Absent，缺勤 ‘P’ : Present，到场 如果一个员工的考勤纪录中不超过两个’A’(缺勤),那么这个员工会被奖赏。 如果你作为一个员工，想在连续N天的考勤周期中获得奖赏，请问有多少种考勤的组合能够满足要求

输入描述:

考勤周期的天数N（正整数） 输出描述: 这N天里能获得奖赏的考勤组合数

#include 
   
    using namespace std; int cal(int n){
       if(n==2){
           return 1;    }    else{
           return (cal(n-1)+n-1);    }}int main(){
       int n,count;    cin>>n;    count = n + 1 + cal(n);    cout<
    
     <
    
   

总结目前牛客问题 ：

第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 , 第四 中间插入多余空行问题 …

解码方法（**动态规划）

题目描述：

一条包含字母 A-Z 的消息通过以下方式进行了编码： ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。

输入描述:

12可以解码成“AB”，“L”这两种 输出描述: 解码方法的总数

#include 
   
    using namespace std;int main(void){
       string s;    int len;    cin>>s;    len = s.length();    int *dp = new int[len+1]{
   };    dp[0] = 1;    for(int i = 1; i <= len; ++i){
           if(s[i-1] != '0')            dp[i] += dp[i-1];        if(i >= 2 && s[i-2] == '1' || s[i-2] == '2' && s[i-1] < '7')            dp[i] += dp[i-2];    }    cout<
    
     <
    
   

s = input()n = len(s)x_1 = 1for i in range(n):  if i == 0:    x_2 = 1  else:    if int(s[i - 1: i + 1]) <= 26:      x_1, x_2 = x_2, x_1 + x_2    else:      x_1 = x_2print(x_2)

漂流船问题（双指针）

题目描述：

公司组织团建活动，到某漂流圣地漂流，现有如下情况： 员工各自体重不一，第 i 个人的体重为 people[i]，每艘漂流船可以承载的最大重量为 limit。 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。 为节省开支，麻烦帮忙计算出载到每一个人所需的最小船只数(保证每个人都能被船载)。

输入描述:

第一行输入参与漂流的人员对应的体重数组， 第二行输入漂流船承载的最大重量 输出描述: 所需最小船只数

#include 
   
    #include
    
     #include
     
      using namespace std;int main(){
       int num,limit;    vector
      
        people;    while(cin>>num){
           people.push_back(num);        if(getchar() == '\n'){
               break;        }    }    cin>>limit;    sort(people.begin(),people.end());        int boat = 0;    int i = 0;    int j = people.size()-1;    while(i
      
     
    
   

**推倒吧骨牌

题目描述：

输入描述: 输入为一个长度不超过1000的，仅包含‘L’，‘R’，‘.’的字符串 输出描述: 根据输入，输出一个仅由‘L’，‘R’，‘.’组成的结果字符串

思路：

从这往右遍历，用flag记录之前是否有右倾；用pos记录上次右倾位置；

遍历无非两种情况：

当前是左倾：1.在最左侧，直接往左边倒完。2.前面存在右倾：相拥而倒；

当前是右倾：1.前面有右倾：处理前面的右倾，更新pos;2:前面无右倾，设置flag和pos；

遍历结束后再处理是否有最后残留的那个flag；

#include
   
    #include
    
     using namespace std;int main(){
       string data;    while(cin>>data)    {
           int rflag=0;        int pos;        int len=data.size();        for(int i=0;i
     
      =0&&data[cur]=='.')                    {
                           data[cur]='L';cur--;                    }                }                else                {
                       int l=pos+1;                    while(cur>l)                    {
                           data[cur]='L';                        data[l]='R';                        l++;cur--;                    }                    rflag=0;                }            }            if(data[i]=='R')            {
                   if(rflag==0)                {
                       rflag=1;                    pos=i;                }                else{
                       pos=i;                    int cur=i-1;                    while(cur>=0&&data[cur]=='.')                    {
                           data[cur]='R';cur--;                    }                }            }        }        if(rflag)        {
               int cur=pos+1;            while(cur
     
    
   

import java.util.*; public class Main {
       public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);        char[] chs = scanner.next().toCharArray();        int len = chs.length;        int[] values = new int[len];         // 第一遍从左往右遍历，遇到R就赋值length，接下来如果是.则递减，直到遇到L清零        int value = 0;        for (int i = 0; i < len; i++) {
               if (chs[i] == 'R') {
                   value = len;            } else if (chs[i] == 'L') {
                   value = 0;            } else {
                   // 保证L之后遇到.仍旧赋值0而不是负数                value = Math.max(value - 1, 0);            }            // values数组加上value值            values[i] += value;        }         // 第二遍从右往左遍历，遇到L就赋值length，接下来如果是.则递减，直到遇到R清零        value = 0;        for (int i = len - 1; i >= 0; --i) {
               if (chs[i] == 'L') {
                   value = len;            } else if (chs[i] == 'R') {
                   value = 0;            } else {
                   // 保证R之后遇到.仍旧赋值0而不是负数                value = Math.max(value - 1, 0);            }            // values数组减去value值            values[i] -= value;        }         StringBuilder result = new StringBuilder();        // values值大于0则为R，小于0则为L，等于0则为.        for (int i : values) {
               result.append(i > 0 ? 'R' : i < 0 ? 'L' : '.');        }        System.out.println(result);    }}

"""LR匹配问题，记录之前方向，分4类讨论LL/RL/RR/LR"""import math if __name__ == "__main__":    s = list(input().strip())    ans = s[:]    t = pl = pr = 0    flag = '0'    while t < len(s):        while t < len(s) and s[t] == '.': t += 1        if t >= len(s): break        if s[t] == 'L':            if flag == '0' or flag == 'L':                for i in range(pl, t):                    ans[i] = 'L'            else:                pl = t                for i in range(pr, math.ceil((pr + pl) / 2)):                    ans[i] = 'R'                for i in range(math.floor((pr + pl) / 2) + 1, pl):                    ans[i] = 'L'            flag = 'L'        elif s[t] == 'R':            if flag == 'R':                for i in range(pr + 1, t):                    ans[i] = 'R'            pr = t            flag = 'R'        t += 1    if pr > pl:        for i in range(pr, len(s)):            ans[i] = 'R'    print(''.join(ans))

转载地址：http://vbqen.baihongyu.com/