分割排序(排序)- HDU 1106

Problem Description

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整数就是由若干个‘0’组成的,这时这个整数就是0)。

你的任务是:对这些分割得到的整数,依从小到大的顺序排序输出。

Input

输入包含多组测试用例,每组输入数据只有一行数字(数字之间没有空格),这行数字的长度不大于1000。

输入数据保证:分割得到的非负整数不会大于100000000;输入数据不可能全由‘5’组成。

Output

对于每个测试用例,输出分割得到的整数排序的结果,相邻的两个整数之间用一个空格分开,每组输出占一行。

Sample Input

0051231232050775

Sample Output

0 77 12312320

解题思路:

给定一串字符串数字,例如 513550067,从第一个数循环,然后判断是不是5,如果是,跳到下一个数字3,这时候就把3的下标记为一个假左,然后从3往之后找5(为了防止最后类似0067 找不到5的情况,我把字符串末尾手动加了个字符5)。

找到5 后,下标记为右,然后再把左右下标之间的字符串拿出来判断。

if 它全是由0组成

then 把0存入一个整型数组

else 更新左坐标

从左坐标判断,如果是0,左坐标+1,再判断左坐标,直到这个字符不是0(例如 最后取出的字符串 0067 的左下标对应的是0,右是7,更新左坐标后,左坐标对应的就变成了6,右不变),然后把67字符转换为10进制67存入数组。

最后将数组排序,输出。

源代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<math.h>
#include<string>
using namespace std;

//快速幂版本
int qpow(int  a, int  b) {
  long long  ans = 1;
  long long  k = a;
  while (b) {
    if (b & 1)ans = ans * k;
    k = k * k;
    b >>= 1;
  }
  return ans;
} 

int main()
{
  char str[1005];

  while (~scanf("%s", str))
  {
    //存储每个分隔出来的整数
    int a[1005];    
    //z,y分别为每个分隔出来的字符串的左右下标
    int i, j, l, z, y, i2; 
    //c表示a数组存储了多少整数
    int c = 0; 
    z = 0; y = 0;
    l = strlen(str);
    str[l] = '5';
    for (i = 0; i <= l - 1;)
    {
      if (str[i] != '5')
      {
        //找到了一个非5数,赋为左下标
        z = i; 
        for (i2 = z + 1; i2 <= l; i2++)
        {
          if (str[i2] == '5')
          {
            //从一个非5数,找到第一个字符5.赋为右下标
            y = i2 - 1; 
            //更新i
            i = i2 + 1; 
            break;
          }
        }
        int x, r = 1;
        for (x = z; x <= y; x++)
        {
          if (str[x] != '0')
          {r = 2; break;}
        }
        //判断这个字符串是不是全是0,若是 r为1,不是 r为2;
        if (r == 1)
        {
          //若r为1,a整型数组存入0
          a[c] = 0; 
          c++;
        }
        else
        {
          int xx;
          for (xx = z; xx <= y; xx++)
          {
            if (str[xx] != '0')
            {
              //更新左下标
              z = xx; 
              break;
            }
          }
          int w, w1;
          w = y - z + 1;
          // w,w1 为此字符串的位数
          w1 = w; 
          int sum = 0, i3, s;
          i3 = z;
          //将隔出来的字符串 转换为整数10进制赋给sum
          while (w--)
          {

            s = str[i3] - '0';
            sum = sum + (s * qpow(10, w1 - 1));
            i3++;
            w1--;
          }      
          //sum存入数组
          a[c] = sum; 
          c++;
        }
      }
      else
      {
        i++;
      }
    }
    //排序数组
    sort(a, a + c); 
    for (i = 0; i < c - 1; i++)
    {
      printf("%d ", a[i]);
    }
    //按格式输出
    printf("%d\n", a[c - 1]); 
  }
  return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-03-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

PHP面试题,PHP笔试题

题目一: <?php echo -10%3; ?> 答案:-1。 考查:优先级。 因为-的优先级比%求余的优先级低, 也就是-(10%3)。 题目二: prin...

99915
来自专栏mathor

波兰表达式

1884
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

1043
来自专栏智能算法

Python学习(四)---- 列表生成式、生成器、迭代器和内置函数

https://blog.csdn.net/fgf00/article/details/52061971

972
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day10 Java中的数组

  什么是数组?顾名思义,就是数据的组合,把一些相同类型的数放到一组里去。   那为什么要用数组呢?比如需要统计全班同学的成绩的时候,如果给班上50个同学的成绩...

2136
来自专栏GAN&CV

python lambda表达式的介绍和使用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_25737169/article/d...

3311
来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1898
来自专栏mathor

LeetCode164. 最大间距

 这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0...

1152
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

43210
来自专栏Python

Python 操作redis有序集合(sorted set)

Zadd 命令用于将一个或多个成员元素及其分数值加入到有序集当中。 如果某个成员已经是有序集的成员,那么更新这个成员的分数值,并通过重新插入这个成员元素,来保证...

7651

扫码关注云+社区

领取腾讯云代金券