黑马程序员技术交流社区

标题: 百度2014校招笔试题目 [打印本页]
作者: 追影    时间: 2013-10-6 18:55
标题: 百度2014校招笔试题目
本帖最后由 追影 于 2013-10-6 19:55 编辑

最近博客里都在贴校招题,我看到几题挺有意思,先献上一题,大家有空可以做做,我先去做做看
二、算法与程序设计题  1、给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。（15分）

作者: 黑色海    时间: 2013-10-6 20:41
简单做了一下， 如果有BUG，还望告知
Console.WriteLine("请您输入一个数字");
            int number=Convert.ToInt32(Console.ReadLine())+1;
            bool flag=true;
            while (flag)
            {
                string strnumber = number.ToString();
                string[] array = { "00", "11", "22", "33", "44", "55", "66", "77", "88", "99" };
                string[] array1 = strnumber.Split(array,StringSplitOptions.None);  
                if (array1.Length > 1)  //如果此处大于1，则说明被分割了，不然就是没分割
                {
                    number++;
                }
                else
                {
                    flag=false;
                }
            }
            Console.WriteLine(number);
            Console.ReadKey();


作者: haxyek    时间: 2013-10-6 21:52
本帖最后由 haxyek 于 2013-10-6 21:56 编辑
黑色海 发表于 2013-10-6 20:41
简单做了一下， 如果有BUG，还望告知
Console.WriteLine("请您输入一个数字");
            int number=Con ...

想法一样。。

还可以用char数组，比较相邻两位是否相等。。
作者: 追影    时间: 2013-10-7 00:36
黑色海 发表于 2013-10-6 20:41
简单做了一下， 如果有BUG，还望告知
Console.WriteLine("请您输入一个数字");
            int number=Con ...

好方法,最直接清晰的思路,不过有一个问题,如果是高位相同的话,而且给定的整数又很大,一位一位的加,效率有些太低了,可不可以一开始就定位到哪里相同,有几个地方相同,低位加1后,还有没有相同的地方
作者: 追影    时间: 2013-10-7 00:38
haxyek 发表于 2013-10-6 21:52
想法一样。。

还可以用char数组，比较相邻两位是否相等。。

版主最近,光看也不加分么,人家这么好的代码
作者: 张慧    时间: 2013-10-7 02:38
本帖最后由 张慧 于 2013-10-7 11:17 编辑

  1. import java.util.regex.Matcher;
  2. import java.util.regex.Pattern;


  5. /**
  6. * 思路：不太会解释，拿个例子说吧。好比1223311：
  7. * 第一次查找,找到了22,就让1223311先变成1220000再加上10000，最后变为:1230000
  8. * 第二次查找，找到了00，就让1230000先变成1230000，在加上100，最后变为：1230100;
  9. * 第三次查找，找到00，就让1230100先变成1230100，在加入1，最后变为1230101；
  10. */
  11. public class Test1 {
  12. public static void main(String[] args) throws InterruptedException{

  14. String num = "1989";
  15. Pattern p = Pattern.compile("(\\d)\\1{1,}\\d*");
  16. Matcher m = p.matcher(num);

  18. int len = num.length();
  19. //添加一个标记，判断是否是第一次处理
  20. boolean flag = false;
  21. while(true){
  22. if(m.find()){
  23. //找到匹配的结尾下标
  24. int index = m.end(1);

  26. //得到下标之后的值，其实就是将相同的那一位加一，之后如果有位就变为0，避免一直加1.
  27. Integer value = (int)Math.pow(10, len-index-1);
  28. //获得末尾有多少个0
  29. String subStr0 = num.substring(0, index+1);
  30. //之前的字符串
  31. String subStr1 = value.toString().substring(1);
  32. //将两个串起来
  33. num = subStr0.concat(subStr1);
  34. //加值操作
  35. Integer sum = Integer.parseInt(num) + value;
  36. num = sum.toString();
  37. //重新匹配
  38. m = p.matcher(num);

  40. flag = true;
  41. //测试看每次打印的结果
  42. System.out.println(num);
  43. }else{
  44. if(!flag){
  45. Integer sum = Integer.parseInt(num) + 1;
  46. num = sum.toString();
  47. //重新匹配
  48. m = p.matcher(num);
  49. }else{
  50. break;
  51. }
  52. }
  53. }
  54. //最终结果
  55. System.out.println(num);
  56. }
  57. }
复制代码
想起没判断不匹配的了，又改了改
作者: haxyek    时间: 2013-10-7 03:07
未解决，不加分
作者: 黑色海    时间: 2013-10-7 11:36
追影 发表于 2013-10-7 00:36
好方法,最直接清晰的思路,不过有一个问题,如果是高位相同的话,而且给定的整数又很大,一位一位的加,效率有 ...


可以试一下用IndexOfAny加循环判断，判断出来坐标加（长度减坐标乘10）
PS：只是想法，还没测验过
作者: 大虾挂了    时间: 2013-10-8 12:39
追影 发表于 2013-10-7 00:36
好方法,最直接清晰的思路,不过有一个问题,如果是高位相同的话,而且给定的整数又很大,一位一位的加,效率有 ...

这个道理最简单的方法应该已经很高效了啊，n位数字，最多只需要比较n-1次就行了。前面那个字符串分割的方法，其实比这个慢很多吧。那个最坏的情况是不是要检测10*（n-1）次
作者: 大虾挂了    时间: 2013-10-8 12:43
追影 发表于 2013-10-7 00:36
好方法,最直接清晰的思路,不过有一个问题,如果是高位相同的话,而且给定的整数又很大,一位一位的加,效率有 ...

刚重新看了一下题，原来是要找到比输入数字大的最小不重复数，那确实可以优化算法的。
作者: 大虾挂了    时间: 2013-10-8 13:14
手头没有VS，说下我的想法。

直接把输入的数字变为char类型数组num处理。
数字的最高位刚好是数组的首位。
先写个循环从num[0]遍历检测两个相邻的字符是否相等，循环参数i（这个i要定义在循环外面）初值为0，条件是i<num.length-1，直到遇到num[i]==num[i+1]，break跳出循环。
分两种情况：
①、本身这个数字就是非重复数字，那么也就是循环没有被break，那么此时i==num.length-1
此时将num[num.length-1]自加1，检查此时的num[num.length-1]是否等于num[num.length-2]，若不相等，则得到的这个num就是所要的（比如：给12345，得12346）。如果相等，再把num[num.length-1]自加1，得到的num就是所要的（比如：给12343，得12345）。

②、本身这个数字是重复数字。那么上面那个循环被break掉，此时i+1记录的就是低位重复数字的下标。我们把num[i+1]自加1。
接着写一个循环，将后面改成01010.....即可。所以循环参量继续使用j。初值为0。循环条件为j<num.length-i-2。循环内容是：num[i+2+j]=j%2。

作者: 大虾挂了    时间: 2013-10-8 13:36
发现我上面说的有BUG ，比如12989这个数字就处理不对了。。。。。
而对于129890这个数字，更难处理了。
还有很多细节需要考虑啊
作者: 大虾挂了    时间: 2013-10-8 13:42
大虾挂了 发表于 2013-10-8 13:36
发现我上面说的有BUG ，比如12989这个数字就处理不对了。。。。。
而对于129890这个数字，更难处理了。
还 ...

第二行搞错，想说的是129898989各种89结尾的
作者: 张慧    时间: 2013-10-8 15:20
大虾挂了 发表于 2013-10-8 13:42
第二行搞错，想说的是129898989各种89结尾的

每次加过后再检查一遍不就可以了。while（）
作者: 崔增阳    时间: 2013-10-8 16:10
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            bool flag = false;
            bool found = false;
            string input = Console.ReadLine();
            int num = int.Parse(input);

            while (!found)
            {
                flag = false;
                num = ++num;
                input = num.ToString();
                for (int i = 0; i < input.Length - 1 && !flag; i++)
                {
                    if (input[i] == input[i + 1])
                    {
                        flag = true;
                    }
                }
                if (!flag)
                {
                    found = true;
                }
            }
            Console.WriteLine(num);

            Console.ReadKey();
        }
    }
}

作者: 蒋元龙    时间: 2013-10-8 18:06
改了下就解决了，浪费表情
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;

  6. namespace ConsoleApplication8
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             
  13.             int red; //用户输入的数字
  14.             bool fuHao = true; //表示加
  15.             Console.Write("请输入一串数字：");
  16.             while (!Int32.TryParse(Console.ReadLine(), out red)) //得到整数
  17.             {
  18.                 Console.WriteLine("输入的不是整数！\n输入数字:");
  19.             }
  20.             Fined(red, "最大且最小不重复的数是：", fuHao);
  21.             Fined(red, "\n最小且最大不重复的数是：", fuHao=false);
  22.             Console.ReadKey();
  23.         }
  24.         #region 找到不重复的数
  25.         /// <summary>
  26.         /// 找到不重复的数
  27.         /// </summary>
  28.         /// <param name="red"></param>
  29.         /// <param name="st"></param>
  30.         /// <param name="fuHao"></param>
  31.         static void Fined(int red,string st,bool fuHao)
  32.         {
  33.             bool fined = true; //控制比对循环
  34.             while (fined)
  35.             {
  36.                 if (fuHao)
  37.                 {
  38.                     red = red + 1; //找最大数且最小的不重复娄
  39.                 }
  40.                 else
  41.                 {
  42.                     red -= 1; //找最小数且最大的不重复娄
  43.                 }
  44.                 int i = 1;//控制数字的位数
  45.                 while (true)
  46.                 {
  47.                     if (i > red.ToString().Length)//如果超出了输入的数的位数，表明找到了这个不重复数
  48.                     {
  49.                         Console.Write(st + red.ToString());
  50.                         fined = false;
  51.                         break;
  52.                     }

  54.                     string one = red.ToString().Substring(red.ToString().Length - i, 1); //得到需要找的数
  55.                     i++;
  56.                     if (i > red.ToString().Length) //如果超出了输入的数的位数，表明找到了这个不重复数
  57.                     {
  58.                         Console.Write(st + red.ToString());
  59.                         fined = false;
  60.                         break;
  61.                     }

  63.                     string two = red.ToString().Substring(red.ToString().Length - i, 2); //得到二位数，用来比对
  64.                     if (two.LastIndexOf(one) == 1 && two.IndexOf(one) == 0)// 如果这二个数是重复的
  65.                     {
  66.                         int sum = 1;
  67.                         for (int j = 2; j < i - 1; j++) //重复那个数在整个数中是第几位就循环几次
  68.                         {
  69.                             sum *= 10; //每循环一次位数加一
  70.                         }
  71.                         if (fuHao)
  72.                         {
  73.                             red += sum - 1; //给重复位上的数加一
  74.                         }
  75.                         else
  76.                         {
  77.                             red -= sum; //给重复位上的数减一
  78.                             red++;
  79.                         }
  80.                         break;
  81.                     }
  82.                 }

  84.             }
  85.         }
  86.         #endregion

  88.     }
  89. }
复制代码
作者: 大虾挂了    时间: 2013-10-9 08:51
本帖最后由 大虾挂了 于 2013-10-11 15:48 编辑

我的方法
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 判断是不是重复数
{
    class Program
    {
        //该字段的意义：
        //temp[0]:
        //初始赋值为：输入数字+1（因为后面chuli()函数运作时第一个数字是可取的，而题干要求大于输入数字）
        //中间过程用于存储：从高位开始判断数字出现相邻重复现象时，重复数字（包括重复的2个）左边所有数字组成的数字
        //最终：当给定数字已经完全处理完毕时的数字。
        //temp[1];
        //初值为0，
        //中间过程用于存储：从高位开始判断数字出现相邻重复现象时，重复数字（不包括重复的2个）右边一共有多少位数字        //最终用于表示给定数字处理完后，temp[0]这个数字还差多少位。
        //temp[2]：用于记录chuli()函数是否检测到重复数字，0表示未检测到（处理完成），1表示检测到（处理未完成）
        public static int[] temp=new int[3];

        //用复杂例子说明这个算法的工作原理：
        //用户输入989898。
        //程序先将这个数加一，也就是从989899开始判断。
        //进入do-while循环
        //chuli()函数第一次运行，temp数组变为{989899,0,1}（原始temp[2]为0）
        //由于检测到最后两个9相邻,所以表示处理未完成，temp[0]要自加1，变为989900。
        //循环继续运行，第二次运行chuli()函数，temp数组变为{9899,2,1}
        //temp[0]继续自加1，变为9900
        //循环继续运行，第三次运行chuli()函数，temp数组变为{99,4,1}
        //temp[0]继续自加1，变为100
        //循环继续运行，第四次运行chuli()函数，temp数组变为{100,4,1}
        //temp[0]继续自加1，变为101
        //循环继续运行，第五次运行chuli()函数，无法检测到相邻的数
        //temp数组最终变为{101,4,0}，数组前两个数字是关键数字，
        //最终字符串是temp[0]+"0"+"1"+"0"+"1"。
        //后面的"0""1"部分只要建立一个循环，参数i初值为0，次数为temp[1],不断让字符串自加i%2即可
        static void Main(string[] args)
        {
            string num = "";
            Console.WriteLine("请输入一个数，我们将输出比这个数大的最小非重复数");
            temp[0]=Convert.ToInt32(Console.ReadLine ())+1;
            do
            {
                chuli();
                if(temp[2]==0)
                    break;
                else
                    temp[0]++;
            }while(true);

            num = temp[0].ToString();
            for (int i = 0; i < temp[1]; i++)
            {
                num += i % 2;
            }
            Console.WriteLine(num);

            Console.ReadKey();
        }

        //这个方法的作用：
        //对temp[0]这个数字进行处理，从高位检测，当遇到重复数字时，截取包括重复数字在内的左边所有数字
        //对于那些没有被截取到的数字，我们把它们一共的位数加到temp[1]中去
        //temp[2]表示是否检测到重复数字，0表示未检测到重复数字，1表示检测到重复数字
        
        //举例，当temp数字本身为{1234554321,0,0}时，运行chuli()函数，我们会截取123455给temp[0]
        //并且算不出后面还有四位数字，temp[1]自加4，检测到重复数字了，所以temp[2]赋值为1
        //这样temp数组就变为{123455,4,1}
        public static void chuli()
        {            
            int i=0;
            for (i = 0; i < temp[0].ToString().Length - 1; i++)
            {
                if (temp[0].ToString() == temp[0].ToString()[i + 1])
                    break;
            }
            if (i == temp[0].ToString().Length - 1)//此时表示num[0[本身就是一个无重复数字，无需处理
                temp[2] = 0;
            if (i < temp[0].ToString().Length - 1)//此时表示num[0]是个有相邻重复数字的数
            {
                temp[2] = 1;
                //注意下面不要把顺序写反num[0]的位数应该先用于计算num[1]，再对num[0]进行截取
                temp[1] += temp[0].ToString().Length - 2 - i;
                temp[0] = Convert.ToInt32(temp[0].ToString().Substring(0, i + 2));
            }
        }
    }
}

作者: 大虾挂了    时间: 2013-10-9 08:52
思路比较怪，所以注释写的略多。。。。。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2