笔试训练(4)

算法题1:倒置字符串倒置字符串__牛客网

输入

I like beijing.

输出

beijing. like I

第一种思路:

1)我们先是把一个完整的字符串给分割成一个字符串数组

2)将字符串数组进行逆置

3)进行拼接空格，进行拼接空格的个数就是分割出来的单词的个数

import java.util.*;
public class Main{
    public static void reverse(String[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            String temp=array[left];
            array[left]=array[right];
            array[right]=temp;
            left++;
            right--;
        }
    }
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        String str=scanner.nextLine();
        String[] strings=str.split(" ");
        int n=strings.length;
        reverse(strings);
        StringBuilder builder=new StringBuilder();
        for(int i=0;i<strings.length;i++){
            builder.append(strings[i]+" ");
        }
        System.out.println(builder);
    }
}

第二种思路:我们先将整体数据进行逆置，我们在将每一个单词进行逆置

1)现将字符串整体进行逆置:l like beijing-->gnijieb ekil l

2)我们再将每一个单词进行逆置，我们的[start,end]就是一个有效区间

3)举个例子假设一开始start和end指向str[0]为0号下标，然后我让end一直向后走，直到end遇到空格了，进行逆置这一个单词

4)当我们想要逆置下一个单词的时候，直接让start=end+1，因为此时end已经指向空格了，然后再让end=start，循环往复

import java.util.*;
public class Main{
    public static void reverse(char[] chars,int left,int right){
        while(left<right){
            char temp=chars[left];
            chars[left]=chars[right];
            chars[right]=temp;
            left++;
            right--;
        }
    }
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        String str=scanner.nextLine();
        char[] chars=str.toCharArray();
        //1.现将数组整体进行逆置
        reverse(chars,0,chars.length-1);
        //2.再进行逆置数组中的每一个单词
        int start=0;
        int end=0;
        int len=chars.length;
        while(start<len){
            end=start;
      //这个条件不能丢，否则end指向空格，start永远无法向前移动，就会导致死循环
            while(end<len&&chars[end]!=' '){
 //前面的判断条件是为了防止end走到最后一个单词一直想后走,防止数组越界
                end++;
            }
            //跳出循环有两种情况
            if(end<len){//这种情况是end走到了最后一个单词
                reverse(chars,start,end-1);
                start=end+1;
            }else{//这种情况是end走到了最后一个单词的末尾但是有空格
                reverse(chars,start,end-1);
                start=end;
            }
        }
        StringBuilder sb=new StringBuilder();
       for(char ch:chars){
           sb.append(ch);
       }
        System.out.println(sb);
    }
}

算法题2:排序子序列:排序子序列_牛客笔试题_牛客网

1)牛牛定义排序子序列为一个数组中连续的子序列，并且这段子序列是非递增或者是非递减的排序的，牛牛有一个长度为n的整数数组A，他现在有一个任务把数组A分成若干个子序列

2)如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

3)输出一个整数表示牛牛可以将A最少划分为多少段排序子序列

4)输入:6     1 2 3 2 2 1

   输出:2

 1 3 2 3 
 输出：2
 
// 输入： 
// 6 
// 3 2 1 1 2 3 
// 输出：2

在这里面我们先来弄清几个概念:

递增序列:1，2，3，4，5

递减序列:9，8，7，6，5

非递减序列:1，2，3，3，4，5，8，8

非递增序列:9，8，7，7，6，5，5，2，1

1)非递减就是array[i]<=array[i+1]，递减就是array[i]>array[i+1]

2)非递增就是array[i]>=array[i+1]，递减就是array[i]<array[i+1]

注意:

输入:4->1 1 2 2

输出:2

在这里程序有特殊的处理

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] array=new int[n];
        for(int i=0;i<n;i++){
            array[i]=scanner.nextInt();
        }
        int i=0;
        int count=0;
        while(i<array.length){
            if(i+1<array.length&&array[i]>array[i+1]){
                while(i+1<array.length&&array[i]>array[i+1]){
                    i++;
                }
                count++;
                i++;//我们在这里面是为了让i走到下一个子序列的开始位置
            }else if(i+1<array.length&&array[i]==array[i+1]){
                //肯定是走到升序序列或者是降序序列的某一个过程
                while(i+1<array.length&&array[i]==array[i+1]){
                    i++;//因为这里始终是一个自增或者是递减的子序列
                }
            }else{
                while(i+1<array.length&&array[i]<array[i+1]){
                    i++;
                }
              count++; 
                i++;//我们在这里面让i多走一步是为了让i走出当前这个子数组,走到下一个序列的子数组当中去
            }
            
        }
       System.out.println(count);
    }
}