目录
Scanner输入
- 1.hasNextxxx()：判断输入是否为xxx类型
- 2.nextxxx()：获取xxx类型的输入；其中next()/nextLine()：获取输入的字符串
当需要输入多行数据时进入:
- whlie(scanner.hasNext())循环，输入多行整数数据，后面使用nextInt()处理输入;
- whlie(scanner.hasNextLine())循环，后面使用nextLine() 处理输入;
while（hasNext()）指的是
while（hasNextLine()）指的是输入多行数据，
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int a = scannner.nextInt(0);
//while(scanner .hasNextLine()){
while(scanner.hasNext()){ //进入循环，可输入多行数据
String str = scanner .nextLine();
System.out.println(str);
}
scanner.close();
}
}Integer. valueOf()可以将基本类型int转换为包装类型Integer，或者将String转换成Integer，String如果为Null或“”都会报错
一、基础概念
1.代码中Base有不带参构造方法、 带参构造方法， 二者构成重载关系
重写：子类调用父类的方法（方法名、返回值、参数列表相同），子类的访问修饰限定>=父类修饰限定
class Base {
public Base () { //无参构造方法
}
public Base (int a) { //有参构造方法
}
public void func(int b){
}
}
public class Child extends Base{
public void func(int b) { //重写父类的func方法 （子类访问修饰限定 >= 父类）
}
}2.面向对象的主要特征：继承、封装、多态、组合
3.结构化程序设计原则：模块化、自顶向下、逐步求精
4.成员变量未初始化，默认值为0或null
5.java中，整数默认是int型，小数默认double型
public void func() {
float f = 12.5f; //正确
float f = 12.5; //报错，因为Java中小数默认是double类型
}6.声明一个类，final修饰之后不能够被继承（类Base不能被继承）
final class Base { //final修饰后，Base不能被继承
public void func(int b){
}
}
7.静态方法可直接调用,如Base.method2()；类名不可直接调用方法名：Base.method()会报错
Base base = new Base();base是Base的一个实例
class Base { //final修饰后，Base不能被继承
public int i;
static String s;
void method1() {
}
static void method2() {
}
}
8. s1.toLowerCase()的用法，若s1本身就是小写则调用此方法不会新创建一个实例，而是继续返回s1自身；若s1带有大写字母，则会新创建一个小写的字符串
public class classDemo {
public static void main(String[] args) {
String s1 = "Abc";
String s2 = s1.toLowerCase(); //"abc"
System.out.println(s2 == s1); //false
String s4 = "abcd";
String s5 = s4.toLowerCase(); //"abcd"
System.out.println(s5 == s4); //true
}9.super() 、this()都必须放在子类构造方法的第一行，二者不可同时出现
10，子类继承父类默认存在一个不带参的构造方法，new Alpha()也会调用父类的无参构造方法
11.static只能定义成员变量，不能定义局部变量（普通方法内部不能出现static）
12.声明抽象方法不能用大括号{}, abstract不可修饰字段 构造方法可以有多个（带参、不带参），多个构造方法之间构成重载
13.使用interface接口时，只能用public修饰符
14.
15.实例方法可直接调用本类的类方法
二、[编程题]组队竞赛
链接：组队竞赛__牛客网
牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现要将这些选手进行组队,组成n个队伍,每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。如：
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。
如样例所示: 如果牛牛把6个队员划分到两个队伍
方案1: team1:{1,2,5}, team2:{5,5,8}, 这时候水平值总和为7.
方案2：team1:{2,5,8}, team2:{1,5,5}, 这时候水平值总和为10.
没有比总和为10更大的方案,所以输出10.
输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括3*n个整数a_i(1 ≤ a_i ≤ 10^9),表示每个参赛选手的水平值.
输出描述:
输出一个整数表示所有队伍的水平值总和最大值.
解题思路：
贪心算法：每次选值时都选当前能看到的局部最解忧，所以这里的贪心就是保证每组的第二个值取到能选择的最大值就可以，我们每次尽量取最大，但是最大的数不可能是中位数，所以退而求其次，取每组中第二大的
1.先对所有成员的水平值进行一个排序（升序）
2.一组三个人（取最后两个元素和第一个元素为一组，可以确保获取到第二大的水平数）
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()) {
int n = scanner.nextInt(); //输入的队伍数
int[] array = new int[3*n]; //输入数组，表示所有队员的水平值，数组长度是3*n
long sum = 0;
for(int i = 0; i< array.length;i++) {
array[i] = scanner.nextInt(); //遍历数组挨个读入数组元素
}
Arrays.sort(array); //对数组进行排序
//排序之后进行分组，第一个元素和最后两个元素为一组，以此类推
for(int i = 0; i < n; i++) { // 分组工作，循环进行，故i < n
//倒数第二个元素为：
int a = array[array.length - 2*(i+1)];
sum += a; //把每个队伍的最大值求和
// sum += array[array.length-2*(i+1)];
}
System.out.println(sum); //输出sum表示所有队伍的水平值总和最大值.
}
}
}三、[编程题] 删除公共字符
链接：删除公共字符__牛客网
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如：第一个字符串是”They are students.”，第二个字符串是”aeiou”。删除之后的第一个字符串变成”Thy r stdnts.”。保证两个字符串的长度均不超过100。
输入描述：
输入两行，每行一个字符串。
输出描述：
输出删除后的字符串。
解析：利用哈希映射的关系
方法1：查找
- 判断第一个串的字符是否在第二个串中，在再挪动字符删除这个字符的方式，效率为O(N^2)，效率太低，因此不采用。
方法2：
- 遍历str2字符串，将其映射到hashtable数组hash[]，哈希表存放字符出现的次数
- 遍历str1中的字符，判断其字符是否在str2中，不使用删除（效率低，涉及数据挪动），使用将不在字符添加到一个新字符串，最后返回新新字符串
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str1 = scanner.nextLine(); //nextLine表示读入一行数据，且遇到空格不会结束（读字符串用nextLine）
String str2 = scanner.nextLine();
HashMap<Character,Integer> map = new HashMap<>(); // 创建一个map用于存放映射关系
//1.遍历第二个字符串str2 将其放入哈希表
for(int i=0; i < str2.length();i++) {
if(map.get(str2.charAt(i)) == null) { //等于0说明之前不存在，则放入count为1
map.put(str2.charAt(i),1); //放入元素，对应的value为1
}else { //不等于0说明已经存在，则放入count++
map.put(str2.charAt(i),map.get(str2.charAt(i))+1); //value+1
}
}
String ret = ""; //ret用于接收字符串
//2.遍历第一个字符串str1
for(int i = 0;i < str1.length();i++) {
if(map.get(str1.charAt(i)) == null) {
ret += str1.charAt(i);
}
}
System.out.println(ret);
}
}四、[编程题]倒置字符串
链接：倒置字符串__牛客网
将一句话的单词进行倒置，标点不倒置。比如 “I like beijing.”，经过处理后变为：”beijing. like I”。
字符串长度不超过100。
输入描述：
输入一个仅包含小写字母、空格、’.’ 的字符串，长度不超过100。
‘.’ 只出现在最后一个单词的末尾。
输出描述：
依次输出倒置之后的字符串，以空格分割。
解析：
先将整个字符串逆置过来，再遍历字符串，找出每个单词，对单词逆置。
import java.util.*;
public class Main {
public static void reverse(char[] array,int start,int end) {
while(start < end) {
char tmp = array[start];
array[start] = array[end];
array[end] = tmp;
start++;
end--;
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
char[] ch = str.toCharArray(); // 把字符串变为字符数组
int len = ch.length;
reverse(ch,0,len-1);
int i =0;
while(i < len) {
int j = i;
while(j < len && ch[j] != ' ') {
j++;
}
reverse(ch,i,j-1); //遇到空格前所有字符进行拟置
i = j+1; //i走到了空格后面，也即是j+1的位置
}
String str1 = new String(ch);
System.out.println(str1);
}
}五、[编程题]排序子序列
排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增（）或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,最少可以把这个数组分为几段排序子序列. 样例所示：牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2
输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5) ；
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。
输出描述:
输出一个整数表示牛牛可以将A最少划分为多少段排序子序列
如，输入 4561556841325632——>456 1 5568 41 32 56 32(共7组)
解析：
非递增：整体递减，但存在相同的元素
非递减：整体递增，但存在相同的元素
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+1]; //避免数组越界，给容量+1
for(int i = 0; i < n;i++) {
array[i] = scanner.nextInt();
}
int i = 0;
int team_num = 0;
while(i < n) {
if(array[i] < array[i+1]) {
while(i < n && array[i] <= array[i+1]) {
i++;
}
team_num++; //非递减序列结束，则组数+1
i++; //继续向后遍历
}else if(array[i] == array[i+1]) {
i++;
}else {
while(i < n && array[i] >= array[i+1]) {
i++;
}
team_num++;//非递增序列结束，则组数+1
i++; //继续向后遍历
}
}
System.out.println(team_num);
}
}六、[编程题]字符串中找出连续最长的数字串
读入一个字符串str，输出字符串str中的连续最长的数字串
输入描述:
输入包含1个测试用例，一个字符串str，长度不超过255。
输出描述:
在一行内输出str中里连续最长的数字串。
示例：abcd12345ed125ss123456789—->123456789
解析：
1.引用两个字符串cur ret： cur用于存放连续的字符串 ，ret存放最大的连续的字符串
2.比较两个字符串的大小，若当前cur长度 >ret 长度，则 将cur的元素给ret，ret = cur；反之，cur置空cur = “”
3.当最长数字字符串在最末尾时，需单独考虑ret= cur;
import java.util.*;
public class Main{
public static void main(String[] args) { //String[] args用来接收命令行传入的参数。 string[]是声明args的数据类型，可以存储字符串数组
Scanner scanner = new Scanner(System.in); //System.in代表从键盘读入数据
String str = scanner.nextLine();
String cur = ""; //定义cur用于存放遍历时连续的数字
String ret = ""; //定义ret用于存放当前最多数字的连续的数字
int i =0;
for(;i < str.length();i++) {
char ch = str.charAt(i);
//判断数字字符 是字符 则放入cur字符串（使用拼接的方式 ）
if(ch >= '0' && ch <= '9') {
cur = cur + ch+""; // ch+""char类型拼接""表示这个整体变成了字符串
}else{ //走到非数字字符之后在开始判断两个字符串的大小，若cur大则，将其放入ret
if(cur.length() > ret.length()) { //
ret = cur;
}else{
cur = "";
}
}
}
if(i == str.length() && cur.length() > ret.length()) { //当最长数字序列在末尾时，需单独考虑
ret= cur;
}
System.out.println(ret);
}
}七、[编程题]找出现次数超过数组长度一半的数字
链接：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字_百度笔试题_牛客网
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
如：输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次—>输出2;
如果不存在则输出0。
解析1：排序后找中间值，若存在中间值一定超过数组长度一半，再次遍历，获取这个次数
解析2：定义map的映射关系<数字，次数>，统计每个字符出现的元素
解析3：众数（出现最多的次数）、非众数
1.定义两个变量result、count：比较数值，进行抵消，若存在众数，则最后剩下的一定的result
2.再次便利数组，查询最后得到的result出现次数是否超过数组长度的一半
方法1：
import java.sql.Time;
import java.util.Arrays;
/**
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
方法一：先排序，再找中间数字（中位数）出现的次数
* */
public class findNum {
//========================方法一 ：此方法时间复杂度较大===========================
public int findMoreCount(int[] array) {
if (array == null || array.length == 0) { //此处位置不可调换，否则会出现空指针异常的情况
return 0;
}
Arrays.sort(array); //对数组排序
int len = array.length;
int midNum = array[len/2]; //找到中间元素
int count = 0;
for (int i = 0; i < len; i++) {
if (array[i] == midNum) { //重新遍历数组，如果有元素等于midNum，进行计数
count++;
}
}
if (count > len/2){ //如果count超过数组长度的一半，则说明midNum是符合出现次数超过数组长度一般的
return midNum;
}
return 0; //如果count出现次数没有超过数组长度的一半，则说明没有，返回0
}
方法2：
import java.util.*;
public class Solution {
// map.keySet() 获取集合对象
// map.get(array[i]))获取的元素的键值（次数）
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0) return 0;
int midIndex = array.length/2;
Map<Integer,Integer> map = new HashMap<>(); //创建一个map用于存放键值对<元素，次数>
for(int i = 0;i < array.length;i++) {
if(!map.keySet().contains(array[i])) { //map里不包含元素，则放入，次数计1
map.put(array[i],1);
}else {
map.put(array[i],map.get(array[i]) + 1); //map里包含元素，则次数 +1
}
}
for(Integer key:map.keySet()) { //key为map里的每一个元素， map.keySet()获取map里的所有元素
if(map.get(key) > midIndex) { // 如果map.get(key)key出现的次数 > 数组长度一半，则返回key
return key;
}
}
return 0;
}
}方法3：
public int MoreFindNum(int[] array) {
if (array == null || array.length == 0) { //此处位置不可调换，否则会出现空指针异常的情况
return 0;
}
int result= array[0]; //将第一个元素定义为result结果，存放元素，
int count = 1; //记住result出现的次数count
for (int i = 1; i < array.length; i++) { //从第二个元素开始，遍历数组
if (count != 0) {
if (array[i] == result){ //如果后一个元素等于前一个元素，则count+1
++count; //
}else { //后一个元素！=前一个元素，则count-1
--count;
}
}else { //count=0，说明此时便利到的元素和前一个元素不等，已经相互抵消，计数为0了
result = array[i]; //遍历到此处，重新存储result为当前值，并计数
count = 1;
}
}
//以上遍历完数组，若存在众数，则可找到出现次数最多且超过len/2的那个元素
// 但若不存在众数（有多个元素出现次数相同或其他情况） ，需要再次遍历数组。查找此时有多少个数与result相同
count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == result) {
count++;
}
}
if (count > array.length/2) { // 若count > array.length/2 ，而说明是找的那个数
return result;
}
return 0; //否则，没找到，返回0
}