081 【字符统计及重排】
给出一个仅包含字母的字符串，不包含空格，统计字符串中各个字母（区分大小写）出现的次数，并按照字母出现次数从大到小的顺序输出各个字母及其出现次数。如果次数相同，按照自然顺序进行排序，且小写字母在大写字母之前。
输入描述:
输入一行，为一个仅包含字母的字符串。
输出描述:
按照字母出现次数从大到小的顺序输出各个字母和字母次数，用英文分号分隔，注意末尾的分号；字母和次数间用英文冒号分隔。
示例1
输入
xyxyXX
输出
x:2;y:2;X:2;
说明
每个字符出现的个数都是2，故x排在y之前，而小写字母x在X之前
示例2
输入
abababb
输出
b:4;a:3;
说明
b的出现个数比a多，故b排在a之前
public class ZT81 {
public static void main(String[] args) {
List<Word> list = new ArrayList<>();
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
//存
Map<Character,Integer> map = new HashMap<>();
int idx = 0;
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
Word word = new Word(1,ch);
if (map.containsKey(ch)) {
int index = map.get(ch);
list.get(index).count++;
}else {
map.put(ch,idx++);
list.add(word);
}
}
//取
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
Word word = list.get(i);
sb.append(word.ch).append(":").append(word.count).append(",");
}
sb.deleteCharAt(sb.length() -1).append(";");
System.out.println(sb);
}
private static class Word implements Comparable<Word>{
private int count;
private char ch;
public Word(int count, Character ch) {
this.count = count;
this.ch = ch;
}
@Override
public int compareTo(Word wo) {
char o1 = wo.ch;
char o2 = this.ch;
if (wo.count!= this.count){
return wo.count - this.count;
}
if ((o1 >= 'a' && o2>= 'a') || (o1 <= 'Z' && o2<= 'Z')){//相同时正序排
return o2 - o1;
}else {//逆序排
return o1 - o2;
}
}
@Override
public boolean equals(Object obj) {
Word wo = (Word) obj;
return this.ch == wo.ch;
}
}
}
082 【组成最大数】
小组中每位都有一张卡片，卡片上是6位内的正整数，将卡片连起来可以组成多种数字，计算组成的最大数字。
输入描述:
“,”号分割的多个正整数字符串，不需要考虑非数字异常情况，小组最多25个人
输出描述:
最大的数字字符串
示例1
输入
22,221
输出
22221
示例2
输入
4589,101,41425,9999，9
输出
9999458941425101
public class ZT82 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] split = sc.nextLine().split(",");
//首位排序后，在对次位进行排序
Map<Integer, List<String>> map = new HashMap<>();
for (int i = 0; i < split.length; i++) {
int ch = Integer.parseInt(String.valueOf(split[i].charAt(0)));
List<String> def = map.getOrDefault(ch, new ArrayList<>());
def.add(split[i]);
map.put(ch,def);
}
//到过来输出
StringBuilder sb = new StringBuilder();
for (int i = 9; i >0 ; i--) {
if (map.containsKey((Object) i )) {
List<String> strings = map.get(i);
sb.append(getChangeList(strings));
}
}
System.out.println(sb);
}
//9,99,91,98,991,905,9
//9,99,991,98,91,905
//思路转为拿出一个数，比较后面有没有比他大的数，有则当前数放到最后，没有则直接拼接
private static String getChangeList(List<String> list){
LinkedList<String> linkList = new LinkedList<>(list);
StringBuilder sb = new StringBuilder();
while (linkList.size() > 0){
String tem = linkList.get(0);
boolean flag = true;
if (tem.length() != 1){
for (int i = 1; i < linkList.size(); i++) {
if (compareMax(tem,linkList.get(i))){//tem不是当前最大值
linkList.remove(0);
linkList.addLast(tem);
flag = false;
break;
}
}
}//没有比当前值更大的，直接删掉当前值
if (flag){
sb.append(tem);
linkList.remove(0);
}
}
return sb.toString();
}
//98,99,901,902,998
private static boolean compareMax(String idx0,String idx1){
int idx1Length = idx0.length();
int idx2Length = idx1.length();
int length =Math.min(idx1Length,idx2Length);
for (int i = 1; i < length; i++) {
int i1 = Integer.parseInt(String.valueOf(idx0.charAt(i)));
int i2 = Integer.parseInt(String.valueOf(idx1.charAt(i)));
if (i1 != i2){
return i2 - i1 > 0;
}
}
return idx2Length == length;
}
}
083 【最大N个数与最小N个数的和】
给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和。你需要对数组进行去重。
说明：
*数组中数字范围[0, 1000]
*最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
*输入非法返回-1
输入描述:
第一行输入M， M标识数组大小
第二行输入M个数，标识数组内容
第三行输入N，N表达需要计算的最大、最小N个数
输出描述:
输出最大N个数与最小N个数的和。
示例1
输入
5
95 88 83 64 100
2
输出
342
说明
最大2个数[100,95],最小2个数[83,64], 输出为342
示例2
输入
5
3 2 3 4 2
2
输出
-1
说明
最大2个数[4,3],最小2个数[3,2], 有重叠输出为-1
public class ZT83 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = Integer.parseInt(sc.nextLine());
String[] input = sc.nextLine().split(" ");
int max = Integer.parseInt(sc.nextLine());
Set<Integer> set = new HashSet<>();
for (int i = 0; i < input.length; i++) {
set.add(Integer.parseInt(input[i]));
}
List<Integer> list = new ArrayList<>(set);
Collections.sort(list);
//找到最大N个数的最小值 ma < mi
//最小N个数的最大值 mi
List<Integer> listMin = list.subList(0,max);
List<Integer> listMax = list.subList(list.size() - max,list.size());
if (listMin.get(max-1) > listMax.get(0)){
System.out.println(-1);
}else {
int total = 0;
for (int i = 0; i < max; i++) {
total += listMin.get(i) + listMax.get(i);
}
System.out.println(total);
}
}
}
084 【最大花费金额】
双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金，现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
输入描述:
输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。
输入第二行为购买资金的额度R，R小于100000。
输出描述:
输出为满足上述条件的最大花费额度。
注意：如果不存在满足上述条件的商品，请返回-1。
示例1
输入
23,26,36,27
78
输出
76
说明
金额23、26和27相加得到76，而且最接近且小于输入金额78
示例2
输入
23,30,40
26
输出
-1
说明
因为输入的商品，无法组合出来满足三件之和小于26.故返回-1
备注:
输入格式是正确的，无需考虑格式错误的情况。
public class ZT84 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] split = sc.nextLine().split(",");
int max = Integer.parseInt(sc.nextLine());
int[] arr = new int[split.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(split[i]);
}
int total = -1;
for (int i = 0; i < split.length; i++) {
for (int j = i+1; j < split.length; j++) {
for (int k = j+1; k < split.length; k++) {
int tem = arr[i] + arr[j] + arr[k];
if (tem <= max){
total = Math.max(tem,total);
}
}
}
}
System.out.println(total);
}
}
085【最大矩阵和】
给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。
输入描述:
输入的第一行包含2个整数n, m(1 <= n, m <= 10)，表示一个n行m列的矩阵，下面有n行，每行有m个整数，同一行中，每2个数字之间有1个空格，最后一个数字后面没有空格，所有的数字的在[-1000, 1000]之间。
输出描述:
输出一行一个数字，表示选出的和最大子矩阵内所有的数字和。
示例1
输入
3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3
输出
20
说明
一个3*4的矩阵中，后面3列的子矩阵求和加起来等于20，和最大。
/**
* 最大矩阵和
*/
public class Main {
public static Map<Node04,Integer> usedMap = new HashMap<Node04, Integer>();
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
String[] nums = sc.nextLine().split(" ");
int n1 = Integer.parseInt(nums[0]);//行
int m1 = Integer.parseInt(nums[1]);//列
int[][] arr = new int[n1][m1];
for (int i = 0; i < n1; i++) {
String[] input = sc.nextLine().split(" ");
for (int j = 0; j < m1; j++) {
arr[i][j] = Integer.parseInt(input[j]);
}
}
System.out.println(calcMax(arr,0,n1,0,m1));
}
public static int calcMax(int[][] arr,int startX,int endX,int startY,int endY){
Node04 node = new Node04(startX,endX,startY,endY);
int max = 0;
if (usedMap.containsKey(node)) {
return usedMap.get(node);
}else {
//计算当前范围的node结果值
//分成4个方向 上下左右各切一刀
max = calcRes(arr,startX,endX,startY,endY);
if (startX + 1 <= endX){
int res1 = calcMax(arr, startX + 1, endX, startY, endY);
int res2 = calcMax(arr, startX, endX-1, startY, endY);
max = Math.max(max,Math.max(res1,res2));
}
if (startY+1 <= endY){
int res3 = calcMax(arr, startX , endX, startY+1, endY);
int res4 = calcMax(arr, startX, endX, startY, endY-1);
max = Math.max(max,Math.max(res3,res4));
}
Integer put = usedMap.put(node, max);
}
return max;
}
public static int calcRes(int[][] arr,int x1,int x2,int y1,int y2){
int total = 0;
for (int i = x1; i < x2; i++) {
for (int j = y1; j < y2; j++) {
total += arr[i][j];
}
}
return total;
}
public static class Node04{
private int startX;
private int endX;
private int startY;
private int endY;
public Node04(int startX, int endX, int startY, int endY) {
this.startX = startX;
this.endX = endX;
this.startY = startY;
this.endY = endY;
}
@Override
public boolean equals(Object obj) {
Node04 node = (Node04) obj;
return node.startX == this.startX && node.endX == this.endX &&
node.startY == this.startY && node.endY == this.endY;
}
}
}
086【最大括号深度】
现有一字符串仅由 ‘(’，’)’，’{’，’}’，’[’，’]'六种括号组成。
若字符串满足以下条件之一，则为无效字符串：
①任一类型的左右括号数量不相等；
②存在未按正确顺序（先左后右）闭合的括号。
输出括号的最大嵌套深度，若字符串无效则输出0。
0≤字符串长度≤100000
输入描述:
一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]'的字符串
输出描述:
一个整数，最大的括号深度
示例1
输入
[]
输出
1
说明
有效字符串，最大嵌套深度为1
示例2
输入
([]{()})
输出
3
说明
有效字符串，最大嵌套深度为3
示例3
输入
(]
输出
0
说明
无效字符串，有两种类型的左右括号数量不相等
示例4
输入
([)]
输出
0
说明
无效字符串，存在未按正确顺序闭合的括号
示例5
输入
)(
输出
0
说明
无效字符串，存在未按正确顺序闭合的括号
/**
* 栈分割括号
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
char[] chars = input.toCharArray();
MyStack<Character> stack = new MyStack<Character>(input.length());
Character pop;
int totalDeep = 0;
int maxDeep = 0;
for (char ch: chars) {
switch (ch){
case '{':
case '[':
case '(':
totalDeep++;
stack.pull(ch);
break;
case ']':
pop = stack.pop();
if (pop != null && pop == '['){
totalDeep--;
break;
}else {
System.out.println(0);
return;
}
case '}':
pop = stack.pop();
if (pop!= null && pop == '{'){
totalDeep--;
break;
}else {
System.out.println(0);
return;
}
case ')':
pop = stack.pop();
if (pop != null && pop == '('){
totalDeep--;
break;
}else {
System.out.println(0);
return;
}
default:
throw new IllegalStateException("Unexpected value: " + ch);
}
maxDeep = Math.max(maxDeep,totalDeep);
}
if (stack.isEmpty()) {
System.out.println(maxDeep);
}else {
System.out.println(0);
}
}
private static class MyStack<Item>{
public Item[] arr;
private int size;
public MyStack(int cap) {//由用户来初始化长度
arr = (Item[]) new Object[cap];
}
//弹出栈顶
public Item pop(){
if (isEmpty()) {
return null;
}
Item item = arr[--size];
arr[size] = null;
return item;
}
//入栈 长度由初始化保证，不考虑扩容
public void pull(Item item){
arr[size++] = item;
}
public boolean isEmpty(){
return size == 0;
}
}
}
//([]{()})
087【最远足迹】
某探险队负责对地下洞穴进行探险。探险队成员在进行探险任务时，随身携带的记录器会不定期地记录自身的坐标，但在记录的间隙中也会记录其他数据。探索工作结束后，探险队需要获取到某成员在探险过程中相对于探险队总部的最远的足迹位置。
仪器记录坐标时，坐标的数据格式为(x,y)，如(1,2)、(100,200)，其中0<x<1000，0<y<1000。同时存在非法坐标，如(01,1)、(1,01)，(0,100)属于非法坐标。
设定探险队总部的坐标为(0,0)，某位置相对总部的距离为：xx+yy。
若两个座标的相对总部的距离相同，则第一次到达的坐标为最远的足迹。
若记录仪中的坐标都不合法，输出总部坐标（0,0）。
备注：不需要考虑双层括号嵌套的情况，比如sfsdfsd((1,2))。
输入描述:
字符串，表示记录仪中的数据。
如：ferga13fdsf3(100,200)f2r3rfasf(300,400)
输出描述:
字符串，表示最远足迹到达的坐标。
如： (300,400)
示例1
输入
ferg(3,10)a13fdsf3(3,4)f2r3rfasf(5,10)
输出
(5,10)
说明
记录仪中的合法坐标有3个： (3,10)， (3,4)， (5,10)，其中(5,10)是相距总部最远的坐标， 输出(5,10)。
示例2
输入
asfefaweawfaw(0,1)fe
输出
(0,0)
说明
记录仪中的坐标都不合法，输出总部坐标（0,0）
/**
* 【最远足迹】
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
List<String> list = new ArrayList<>();
boolean flag = input.contains("(");
while (flag){
int i1 = input.indexOf("(");
int i2 = input.indexOf(")");
list.add(input.substring(i1+1,i2));
input = input.substring(i2+1);
flag = input.contains("(");
}
//分割数据
int xi = 0 ;
int yi = 0;
int maxi = 0;
for (int i = 0; i < list.size(); i++) {//0<x<1000，0<y<1000
//数据不能是开头
String[] split = list.get(i).split(",");
if (split[0].startsWith("0") || split[1].startsWith("0")){//数据忽略
continue;
}
int x1 = Integer.parseInt(split[0]);
int y1 = Integer.parseInt(split[1]);
if (x1 <= 0 || x1 >=1000 || y1 <= 0 || y1 >= 1000){
continue;
}
if (x1 * x1 + y1 * y1 > maxi){
maxi = x1 * x1 + y1 * y1;
xi = x1;
yi = y1;
}
}
System.out.println("("+ xi + "," +yi +")");
}
}
088【最长连续子序列】
有N个正整数组成的一个序列。给定整数sum，求长度最长的连续子序列，使他们的和等于sum，返回此子序列的长度，如果没有满足要求的序列，返回-1。
输入描述:
序列：1,2,3,4,2
sum：6
输出描述:
序列长度：3
输入描述:
序列：1,2,3,4,2
sum：6
输出描述:
序列长度：3
示例1
输入
1,2,3,4,2
6
输出
3
说明
解释：1,2,3和4,2两个序列均能满足要求，所以最长的连续序列为1,2,3，因此结果为3
示例2
输入
1,2,3,4,2
20
输出
-1
说明
解释：没有满足要求的子序列，返回-1
备注:
输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔；
序列长度：1 <= N <= 200；
输入序列不考虑异常情况，由题目保证输入序列满足要求。
/**
* 【最长连续子序列】
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] split = sc.nextLine().split(",");
int[] arr = new int[split.length];
int sum = Integer.parseInt(sc.nextLine());
int total = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(split[i]);
total += arr[i];
}
if (total< sum){
System.out.println(-1);
}else if (total == sum){
System.out.println(split.length);
}else {
//双指针
int left = 0;
int right = 0;
int temp = 0;
while (left < arr.length && right< arr.length){
if (temp < sum){
temp += arr[right];
right++;
}else if (temp != sum){
temp -= arr[left];
left++;
}
if (temp == sum) {
System.out.println(right - left);
left++;
right = left;
temp = 0;
}
}
}
}
}
089【最长元音子串的长度】
定义：当一个字符串只有元音字母（aeiouAEIOU）组成，称为元音字符串。
现给定一个字符串，请找出其中最长的元音字符子串，并返回其长度；如果找不到，则返回0。
子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。
输入描述:
一个字符串，其长度范围：0 < length <= 65535。
字符串仅由字符a-z和A-Z组成。
输出描述:
一个整数，表示最长的元音字符子串的长度。
示例1
输入
asdbuiodevauufgh
输出
3
说明
样例1解释：最长元音子串为 “uio” 或 “auu”，其长度都为3，因此输出3
/**
* 89 最长元音子串的长度
* 定义：当一个字符串只有元音字母（aeiouAEIOU）组成，称为元音字符串。
* 现给定一个字符串，请找出其中最长的元音字符子串，并返回其长度；如果找不到，则返回0。
*
* 子串：字符串中任意个连续的字符组成的子序列称为该字符串的子串。
*
* 输入描述:
* 一个字符串，其长度范围：0 < length <= 65535。
* 字符串仅由字符a-z和A-Z组成。
*
* 输出描述:
* 一个整数，表示最长的元音字符子串的长度。
*
* 示例1
* 输入
* asdbuiodevauufgh
* 输出
* 3
* 说明
* 样例1解释：最长元音子串为 “uio” 或 “auu”，其长度都为3，因此输出3
*/
public class Main {
public static void main(String[] args) {
char[] arr = {'a','e','i','o','u'};
List<Character> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
list.add(arr[i]);
}
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int idx = 0;
int max = 0;
int tem = 0;
while (idx < input.length()){
char ch = input.charAt(idx);
if (list.contains(ch)) {
tem++;
}else {
if (tem != 0) {
max = Math.max(max,tem);
tem = 0;
}
}
idx++;
}
System.out.println(max);
}
}
090【最长子字符串的长度】
给你一个字符串 s，字符串s首尾相连成一个环形 ，请你在环中找出 ‘o’ 字符出现了偶数次最长子字符串的长度。
输入描述:
输入是一串小写字母组成的字符串
输出描述:
输出是一个整数
示例1
输入
alolobo
输出
6
说明
最长子字符串之一是 “alolob”，它包含’o’ 2个。
示例2
输入
looxdolx
输出
7
说明
最长子字符串是 “oxdolxl”，由于是首尾连接在一起的，所以最后一个 ‘x’ 和开头的 ‘l’是连接在一起的，此字符串包含 2 个’o’ 。
示例3
输入
bcbcbc
输出
6
说明
这个示例中，字符串 “bcbcbc” 本身就是最长的，因为 ‘o’ 都出现了 0 次。
备注:
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。
/**
* 【最长子字符串的长度】
*/
public class ZT90 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
char[] chars = input.toCharArray();
int o1 = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == 'o') {
o1++;
}
}
if (o1 % 2 == 0){
System.out.println(input.length());
}else {
System.out.println(input.length() -1);
}
}
}
