30天刷题训练（一）

目录

1.组队竞赛

2.删除公共字符

3.倒置字符串

4.排序子序列

---

1.组队竞赛

组队竞赛_牛客笔试题_牛客网组队竞赛 ，【2017】牛客模考（三模）编程题集合https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b?orderByHotValue=1&page=1&onlyReference=false

①题目及示例：

 ②方法解析：（本题涉及到的算法是贪心算法）

a.根据题意，涉及不能找最大，要退而求其次找第二大的数。那么我们通过关系得到，第二大的数的下标应该为array[array.length-(2*(i+1))];其中i为趟数。所以代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
        int n=sc.nextInt();
        int []array= new int[3*n];
        for(int i=0;i<(3*n);i++){
            array[i]=sc.nextInt();
        }
        Arrays.sort(array);
            long sum=0;
;        for(int i=0;i<n;i++){
            sum+=array[array.length-(2*(i+1))];
        }
        System.out.println(sum);
    }
    }
}

值得注意的几个地方：

（1）hasNext（）的用法：

没有输入时，会对其进行阻断。即阻塞

（2）题目中对a_i的数值要求是<10^6，但是int的大概取值范围是在10^6-10^7，所以这个地方仍然对其可以用int来进行修饰。

b.利用去掉每组数中最小的，然后对于剩余两值找其中的较小值进行累加即可。我们排序后直接可以去掉前n个数，因为必然前n个数是最小的，然后利用下标隔开找两数中较小值即可。代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
        int n=sc.nextInt();
        int []array= new int[3*n];
        for(int i=0;i<(3*n);i++){
            array[i]=sc.nextInt();
        }
        Arrays.sort(array);
            long sum=0;
        // 1、去掉前n个较小的数
        // 2、将剩下的 2*n 个数两两组合
        // 3、取每组中较小的数，求和
;        for(int i=n;i<array.length;i+=2){
            sum+=array[i];
        }
        System.out.println(sum);
    }
    }
}

2.删除公共字符

删除公共字符_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/f0db4c36573d459cae44ac90b90c6212?tpId=85&&tqId=29868&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

 ①题目及示例：

  ②方法解析：

反向思考法，针对要的输出。不考虑删除，因为删除意味着重新排序，反而增加了时间复杂度。我们可以把要去除的加以记录，然后在整体中没有涉及到记录的单词就额外存在于另一个字符串中。这个时候我们采用哈希map来完成这个操作。下面是涉及到的方法。

a.map.put(key,value);

b.map.get(key);用于拿到key所存在的次数

c.map.containsKey(i);布尔类型，用来判断是否存在该值

d.s.length()方法用于求字符串的长度

e.s.charAt（i）;缩减字符串s，并返回它的第i个字符

而下面两种方法的不同之处，在于是直接用字符串进行拼接还是构造一个StringBuffer对象，利用其append方法来进行解决。很显然，前者的开销更小，也是我们需要学到的东西。

（1）字符串拼接代码如下：

import java.util.*;
public class Main{
    public static void main(String[]args){
       Scanner sc=new Scanner(System.in);
        String m=sc.nextLine();
        String n=sc.nextLine();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<n.length();i++){
            if(map.get(n.charAt(i))==null){
            map.put(n.charAt(i),1);
            }else{
                map.put(n.charAt(i),map.get(n.charAt(i))+1);
            }
        }
        String sbu="";
        for(int i=0;i<m.length();i++){
            if(!map.containsKey(m.charAt(i))){
                sbu+=m.charAt(i);
            }
        }
        System.out.println(sbu);
    }
}

（2）利用StringBuilder/StringBuffer来创建对象解决：

import java.util.*;
public class Main{
    public static void main(String[]args){
       Scanner sc=new Scanner(System.in);
        String m=sc.nextLine();
        String n=sc.nextLine();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<n.length();i++){
            if(map.get(n.charAt(i))==null){
            map.put(n.charAt(i),1);
            }else{
                map.put(n.charAt(i),map.get(n.charAt(i))+1);
            }
        }
        StringBuffer sbu=new StringBuffer();
        for(int i=0;i<m.length();i++){
            if(!map.containsKey(m.charAt(i))){
                sbu.append(m.charAt(i));
            }
        }
        System.out.println(sbu);
    }
}

3.倒置字符串

倒置字符串_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/ee5de2e7c45a46a090c1ced2fdc62355?tpId=85&&tqId=29867&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

 ①题目及示例：

 ②方法解析：

我们分析这个字符串的整体，只是每个单词这个整体进行了倒置，而实际每个单词内部并没有进行倒置，所以我们可以有以下两种思路来进行完成本题。

a.利用单词间是以“ ”相隔的，所以我们利用split函数，将其以单词分成整体形成一个数组，然后利用字符串拼接的方式来按照从后往前来拼接，每拼接一个单词后，加上“ ”；最后为了保证严谨，要去除句子前后的空格，使用trim方法来进行。

代码如下：

import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String ret=sc.nextLine();
    String []array=ret.split(" ");
    String str="";
    for(int i=0;i<array.length;i++){
        str+=array[array.length-1-i];
        str=str+" ";
    }
    //去除句子前后的空格，保留中间部分的空格
    String str1=str.toString().trim();
    System.out.println(str1);
     }
}

b.首先整体反置，再局部反置。利用双指针法来解决这个问题。注意局部逆置的时候两个变量i,j的变化位置。主要用到了一下方法。

（1）s.toCharArray();返回数据的副本给你需要的数组，其底层是一个数组。

 代码如下：

import java.util.Scanner;
import java.util.*;
public class Main{
      public static void reverse(char[]array,int left,int right){
            while(left<=right){
                char tmp=array[left];
                array[left]=array[right];
                array[right]=tmp;
                left++;
                right--;
 }
      }
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String ret=sc.nextLine();
    char[] ch=ret.toCharArray();
    reverse(ch,0,ch.length-1);
    int i=0;
    while(i<ch.length){
        int j=i;
        while(j<ch.length&&ch[j]!=' '){
            j++;
        }
        if(j<ch.length){
            reverse(ch,i,j-1);
            i=j+1;
            j++;   
        }else{
            reverse(ch,i,j-1);
            i=j;
        }
    }
    String str = new String(ch); 
    System.out.println(str);
    }
}

4.排序子序列

排序子序列_牛客笔试题_牛客网排序子序列 ，【2017】牛客模考（三模）编程题集合https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471?orderByHotValue=1&page=1&onlyReference=false

①题目及示例：

 ②方法解析：

本题主要在于对题意的理解。其中，非递增和非递减分别代表的是什么。然后就是灵活运用if和while所在的循环，值得注意的是，不满足一个条件时，是否还在另一个条件中走完才不满足，这个是很关键的点。

代码如下：

import java.util.*;
public class Main {
        public static void main(String[]args){
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int []array=new int[n+1];
            //对数组进行赋值
            for(int i=0;i<n;i++){
                array[i]=sc.nextInt();
            }
            int i=0;//用i来进行移动
            int count=0;//用count来进行计数
            while(i<n){
                //非递减
                if(array[i]<array[i+1]){
                    while(i<n&&array[i]<=array[i+1]){
                        i++;//当某个i不满足时，首先跳出当前循环，然后执行完该if
                        //中的语句后在进行之后的判断
                    }
                    count++;
                        i++;
                }//相等的情况是不会改变前后的结果的
                else if(array[i]==array[i+1]){
                    i++;
                }//非递增
                else if(array[i]>array[i+1]){
                    while(i<n&&array[i]>=array[i+1]){
                        i++;
                            
                    }
                    count++;
                    i++;
                }
            }
            System.out.println(count);
        }
}

坚持！！！！