算法库 - 图2

靠谱的车

题目

  1. 小明打车，出租车司机不喜欢4，改装计费表，任何出现数据4就跳过，其余功能正常
  2. 1. 23再多一块变25
  3. 2. 39再多一块变50
  4. 3. 399再多一块编程500
  6. 小明利用编程识别问题，给出计费表的表面读数，返回实际费用
  7. 输入描述：一个数据表示实际产生的费用
  8. 示例1：输入5，输出4

参考

  1. def charge(cost:String): Unit ={
  2.     var result:Int = 0
  3.     val len:Int = cost.length
  4.     for (i<- 0 until len){
  5.       val siteNum:Int = cost.substring(i,i+1).toInt
  6.       result += Math.pow(9,len-i-1).toInt*siteNum
  7.       if(siteNum>4){
  8.         result-=Math.pow(9,len-i-1).toInt
  9.       }
  10.     }
  11.     println(result)
  12.   }

寻找相同子串

题目

  1. 给你两个字符串t和p，要求从t中找到一个和p相同的连续子串，并输出改子串第一个字符的下标
  2. 输入：
  3. AVERDXIVYERDIAN
  4. RDXI
  5. 输出：
  6. 4

参考

  1. String str1 = "abc";
  2. String str2 = "123acbc456abc";
  3. int index = -1;
  4. for(int i = 0;i<=str2.length()-str1.length();i++) {
  5.     if(str2.substring(i, str1.length()+i).equals(str1)) {
  6.         index = i;
  7.         break;
  8.     }
  9. }
  10. System.out.println(str1+"在"+str2+"中第一次出现的位置是："+index);
  1. public class t {
  2.     private static int  find(char[] str1_sz, char[] str2_sz) {
  3.         int index = -1;
  4.         if (str1_sz.length <= str2_sz.length) {
  5.             for (int i = 0; i < str1_sz.length; i++) {
  6.                 for (int j = 0; j < str2_sz.length; j++) {
  7.                     if (str1_sz[i] == str2_sz[j]) {
  8.                         for (int k = 0; k < str1_sz.length; k++) {
  9.                             if (k + 1 == str1_sz.length) {
  10.                                 index = j + 1;
  11.                             }
  12.                         }
  13.                     }
  14.                     if (index != -1)
  15.                         break;
  16.                 }
  17.             }
  18.         }
  19.         return index;
  20.     }
  21.     public static void main(String[] args) {
  22.         String str1 = "abc";
  23.         String str2 = "123acbc456abc";
  24.         char[]  str1_sz=str1.toCharArray();
  25.         char[]  str2_sz=str2.toCharArray();
  26.         int index=0;
  27.         if (str1.length()<=str2.length())
  28.         {
  29.             index=find(str1_sz,str2_sz);
  30.         }else
  31.         {
  32.             index=find(str2_sz,str1_sz);
  33.         }
  34.         System.out.println(str1+"在"+str2+"中第一次出现的位置是："+index);
  35.     }
  36. }

找终点

题目

  1. 给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，锁使用最少的步骤数，要求：
  2.     1.第一步必须从第一个元素开始，切1<=第一步的步长<len/2
  3.     2.从第二步开始，只能以所有成员的数字走相应的步数，不能多不能少，如果目标不可达返回-1
  4.     3.只能向数组的尾部走，不能往回走
  5. 输入描述：由正整数组成的数据，以空格分割，数组长度小于100
  6. 输出描述：正整数，表示最少的步数，如果不存在输出-1
  7. 示例：
  8. 输入7 5 9 4 2 6 8 3 5 4 3 9
  9. 输出 2

参考

  1. public static void main(String[] args) {
  3.     int[] nums = {7,5,9,4,2,6,8,3,5,4,3,9};
  4.     // 记录最少步数
  5.     int minCount = -1;
  6.     for(int i = 1; i <= nums.length/2 ; i++){
  7.         // 不可达,返回-1
  8.         int len = test1( nums,i );
  9.         if( len != -1 ){
  10.             // 找最小
  11.             minCount = minCount == -1 ? len : Math.min(minCount, len);
  12.         }
  13.     }
  14.     System.out.println(minCount);
  15. }
  17. //
  18. public static int test1(int[] nums,int start){
  19.     int i = start;
  20.     int count = 0;
  21.     for (; i<= nums.length ; i+=nums[i]){
  22.         count++;
  23.         // 如果超过, 返回-1, 不可达 ( 因为从第一个开始,所需要走的长度-1 )
  24.         if( i>(nums.length-1) ) return -1;
  25.         // 如果正好等于, 返回步数 ( 因为从第一个开始,所需要走的长度-1 )
  26.         if( i==(nums.length-1) ) return count;
  27.     }
  28.     return -1;
  29. }

春游名单

题目

  1. 输入姓名+工号，英文逗号分割
  2. 输出工号中数字按照升序排序
  3. 示例：
  4. 输入：
  5. wr0068,lt01,qhy0027828,gh20425256,xj0033258,zmj00505562
  6. 输出：
  7. lt01,wr0068,qhy0027828,xj0033258,zmj00505562,gh20425256

参考

  1. public static void test2(){
  2.     String str = "wr0068,lt01,qhy0027828,gh20425256,xj0033258,zmj00505562";
  3.     // 切分
  4.     String[] split = str.split(",");
  5.     // 冒泡排序
  6.     for(int i = 1 ;i<split.length ;i++) {
  7.         boolean flag = true;
  8.         for (int j = 0; j<split.length-i;j++) {
  9.             int i1 = Integer.parseInt(replaceAllNotNumber(split[j]));
  10.             int i2 = Integer.parseInt(replaceAllNotNumber(split[j+1]));
  11.             if( i1 > i2) {
  12.                 String zj= split[j];
  13.                 split[j]=split[j+1];
  14.                 split[j+1]=zj;
  15.                 flag = false;
  16.             }
  17.         }
  18.         if(flag)
  19.             break;
  20.     }
  21.     // 打印出来
  22.     for(int i = 0;i<split.length;i++){
  23.         System.out.println(split[i]);
  24.     }
  26. }
  28. public static String replaceAllNotNumber(String str){
  29.     StringBuffer result = new StringBuffer();
  30.     char[] chars = str.toCharArray();
  31.     for (char aChar : chars) {
  32.         // 0-9 的 ASCII
  33.         if(aChar >=48 && aChar <=57){
  34.             result.append(aChar);
  35.         }
  36.     }
  37.     return result.toString();
  38. }

最大连续1的个数

题目

  1. 输入: [1,1,0,1,1,1]
  2. 输出: 3
  3. 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
  5. 注意：
  6. 输入的数组只包含 0 和1。
  7. 输入数组的长度是正整数，且不超过 10,000。
  8. 思路

参考

  1. public static void main(String[] args) {
  3.     int[] nums =  {1,1,0,1,1,1};
  5.     int len = 0;
  6.     int maxLen = 0;
  8.     for (int num : nums) {
  9.         if (num == 1) len++; else len=0;
  10.         if(len > maxLen) maxLen = len;
  11.     }
  13.     System.out.println(maxLen);
  15. }

数大雁

题目

  1. 一群大雁往南 飞，给定一个字符串记录地面上的游客听到的大雁叫声，请给出叫声最少由几只大雁发出。
  2. 具体的:
  3. 1.大雁发出的完整叫声为"quack"，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个"quack"。
  4. 2.大雁会依次完整发出"quack"，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
  5. 3.如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。
  7. 输入：quackquack
  8. 输出：1

参考

  1. public static void test1(String str,String calls){
  3.     /*
  4.      * str : 所有叫声  "ququackkack"
  5.      * calls : 一只大雁叫声的顺序  "quack"
  6.      * */
  8.     // 默认0只
  9.     int len = 0;
  10.     // 第一个q出现位置, 作为开始位置, 前面的都没有q,不完整,忽略
  11.     int startIndex = str.indexOf(calls.substring(0,1));
  12.     // 最后一个k出现位置,作为结束位置, 后面的都没k,不完整,忽略
  13.     int endIndex = str.lastIndexOf(calls.substring(calls.length()-1));
  14.     // 取出要计算的字符串
  15.     char[] chars = str.substring(startIndex, endIndex+1).toCharArray();
  17.     List<String> goose = new ArrayList<>();
  18.     for (char aChar : chars) {
  19.         // 取出当前叫声
  20.         String call = String.valueOf(aChar);
  21.         // 取出叫声所在位置
  22.         int i = calls.indexOf(call);
  23.         // 如果出现不应该出现的声音, 跳过
  24.         if( i == -1 ) continue;
  25.         // 如果是第一声, 添加
  26.         if( i == 0 ) {
  27.             goose.remove(calls.substring(calls.length()-1));
  28.             goose.add(call);
  29.             continue;
  30.         }
  31.         // 如果是其他叫声
  32.         int count = goose.size();
  33.         goose.remove(calls.substring(i-1,i));
  34.         if (count-1 == goose.size()) goose.add(call);
  35.     }
  37.     // 统计有几只
  38.     for (String s : goose) {
  39.         if(s.equals(calls.substring(calls.length()-1))) len++;
  40.     }
  41.     System.out.println( len == 0 ? -1 : len);
  43. }
  1. int sta[5] = {};
  2.     int max = -1;
  3.     int curmax = 0;
  4.     int cur = 0;
  5.     int curmin = 0;
  6.     //string str = "acaacckquacquacquacquacquackkkkkquacquacquack";
  7.     //string str = "ququackkack";
  8.     string str = "quacquacquacquacquackkkquacquacquacquacquacquacquackkkkquacquacquack";
  9.     string calls = "quack";
  11.     for (string::iterator it = str.begin();it!=str.end();++it) {
  13.         switch (*it) {
  14.         case 'q': 
  15.             ++cur;
  16.             if (curmax < cur) {
  17.                 ++curmin;
  18.                 curmax = cur;
  19.             }
  20.             ++sta[1];
  21.             break;
  22.         case 'u':
  23.             if (sta[1] > 0) {
  24.                 --sta[1];
  25.                 ++sta[2];
  26.             }
  27.             break;
  28.         case 'a':
  29.             if (sta[2] > 0) {
  30.                 --sta[2];
  31.                 ++sta[3];
  32.             }
  33.             break;
  34.         case 'c':
  35.             if (sta[3] > 0) {
  36.                 --sta[3];
  37.                 ++sta[4];
  38.             }
  39.             break;
  40.         case 'k':
  41.             if (sta[4] > 0) {
  42.                 --sta[4];
  43.                 --cur;
  44.             }
  45.             if (curmin > cur) {
  46.                 curmin = cur;
  47.             }
  48.             break;
  49.         default:
  50.             break;
  51.         }
  53.     }
  55.     if (curmax == 0) {
  56.         max = -1;
  57.     }else {
  58.         max = curmax - curmin;
  59.     }
  62.     cout << max << endl;