菜鸟之路Day07
作者：blue
时间：2025.1.25
0.概述
文章内容学习至，黑马程序员：BV17F411T7Ao
今天视频刚好看到算法，结果晚上打了一把Atcoder成功写笑自己
1.排序算法温习
很久没有手写排序，一般都是调用sort方法，借此机会，写写排序。
1.1冒泡排序
要点：两两比较大的往上冒，所以一轮比较过后最大的数，会处于最末尾。
public class sort1 {
public static void main(String[] args) {
//冒泡
int[] arr = {
34,54,67,23,12,56,78,90,1,5,0};
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for (int j : arr) {
System.out.print(j + " ");
}
}
}
1.2选择排序
最前面的数依次与其后面的数相比，小的数交换到前面，故而一轮之后最小的数在最前面。
public class sort2 {
public static void main(String[] args) {
//选择
int[] arr = {
34,54,67,23,12,56,78,90,1,5,0};
for(int i=0;i< arr.length-1;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for (int j : arr) {
System.out.print(j + " ");
}
}
}
1.3插入排序
将数组看成两部分，前一部分是有序的，后一部分是无序的，每次取一个无序的数，在顺序的数组里，倒序遍历，找其应该摆放的位置。
public class sort3 {
public static void main(String[] args) {
//插入
int[] arr = {
34,54,67,23,12,56,78,90,1,5,0};
for(int i=1;i<arr.length;i++){
int index = i;
for(int j=i-1;j>=0;j--){
if(arr[index]<arr[j]){
int temp = arr[index];
arr[index]=arr[j];
arr[j]=temp;
index=j;
}
else break;
}
}
for (int j : arr) {
System.out.print(j + " ");
}
}
}
1.4快速排序
①将排序范围中的第一个数字作为基准数，再定义两个变量start，end
②start从前往后找比基准数大的，end从后往前找比基准数小的。
③找到之后交换start和end指向元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应该存入的位置，再让基准数归位
④归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大
public class sort4 {
public static void main(String[] args) {
int[] arr = {
34,54,67,23,12,56,78,90,1,5,0};
qksort(arr,0,arr.length-1);
for (int j : arr) {
System.out.print(j + " ");
}
}
public static void qksort(int[] arr,int i,int j)
{
int start = i;
int end = j;
if(end<start) return;
while(end!=start)
{
while(end>=start&&arr[i]<arr[end]) end--;
while(end>=start&&arr[i]>arr[start]) start++;
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
int temp = arr[i];
arr[i] = arr[end];
arr[end] = temp;
qksort(arr,i,end-1);
qksort(arr,end+1,j);
}
}
2.工具类Arrays
package Arrays;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
int[] arr = {
34, 54, 67, 23, 12, 56, 78, 90, 1, 5, 0};
int[] arr2 = {
0, 1, 5, 12, 23, 34, 54, 56, 67, 78, 90};
//1.public static String toString(数组) 把数组拼接成一个字符串
String res1 = Arrays.toString(arr);
System.out.println("toString:" + res1);
//2.public static int binarySearch(数组，查找的元素) 二分查找法查找元素
//注意二分查找的数组必须是有序的
int res2 = Arrays.binarySearch(arr2, 0);
System.out.println("binarySearch:" + res2);
//3.public static int[] copyOf(原数组，新数组长度) 拷贝数组(从头开始截取指定长度)
int[] res3 = Arrays.copyOf(arr2, 3);
System.out.println(Arrays.toString(res3));
//4.public static int[] copyOfRange(原数组，起始索引，结束索引) 拷贝数组(指定范围，包左不包右)
int[] res4 = Arrays.copyOfRange(arr2,2,5);
System.out.println(Arrays.toString(res4));
//5.public static void fill(数组，元素) 填充数组
Arrays.fill(arr2,88);
System.out.println(Arrays.toString(arr2));
//6.public static void sort(数组) 排序(默认升序)
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
//7.public static void sort(数组，排序规则) 按照指定规则排序
/*
细节：
只能给引用数据类型的数组进行排序
如果数组是基本数据类型，需要变成其对应的包装类
*/
Integer[] arr3 = {
34, 54, 67, 23, 12, 56, 78, 90, 1, 5, 0};
Arrays.sort(arr3,new Comparator<Integer>(){
//匿名内部类
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1; //o1-o2升序；o2-o1降序
}
});
System.out.println(Arrays.toString(arr3));
}
}
3.Lambda表达式
Lambda表达式是JDK8开始后的一种新的语法形式
注意：①Lambda表达式可以用来简化匿名内部类的书写
②Lambda表达式只能简化函数式接口的匿名内部类的写法
③函数式接口：有且仅有一个抽象方法的接口叫做函数式接口，接口上方可以加@Functionallnterface注解
() -> {
}
//() 对应着方法的形参
//-> 固定格式
//{}对应着方法体
用Lambda表达式改写排序的匿名内部类
Integer[] arr3 = {
34, 54, 67, 23, 12, 56, 78, 90, 1, 5, 0};
Arrays.sort(arr3,(Integer o1,Integer o2)->{
return o2-o1;
});
System.out.println(Arrays.toString(arr3));
还有更省略的写法，但是个人认为，那样写可阅读性不高，这样的Lambda已经挺好的了
4.AtcoderABC390
今天是周六，刚好今天也是练习到算法，就又去打了把周赛，哈哈哈，一月没写算法，把自己写笑了。不知为什么算法题还是更习惯用C++来写，虽然用java应该也大差不差，但是第一想法还是码C++。先说结果吧，作为一个苟蒻，还是只切出来ABC三题，第四题一直突破不了（又笨又不认真........罢了罢了）
B - Geometric Sequence (atcoder.jp)
A题就不说了，首先是B题，哈哈哈，和我一个段位的不都得Wa个10发8发的。
题目大意：给一个数组，判断它是不是等比数列
一开始写了个用double的，wa了一发，就开始觉得是精度问题，结果精度试1e-9错4发。。。。
试到1e-32还是错1发。。。。
最后才想出来可以用乘法，来避免除法小数精度的问题。不过这个题在这里给大家使绊子，今晚也是坑死不少人
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[105];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (n == 2) {
cout << "Yes";
return 0;
}
for (int i = 0; i < n - 2; i++) {
if ((long long)a[i] * a[i + 2] != (long long)a[i + 1] * a[i + 1]) {
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}
C - Paint to make a rectangle (atcoder.jp)
然后是C题
本题给定一个由字符构成的网格，要求判断是否可以通过对未涂色的单元格进行涂色（涂成黑色或白色），使得网格中所有黑色单元格构成一个矩形。以下是详细信息：
网格描述
网格具有
H行和W列。使用(i, j)来表示从顶部起第i行（1 ≤ i ≤ H）、从左侧起第j列（1 ≤ j ≤ W）的单元格。网格的状态由H个长度为W的字符串S1, S2, ..., SH
来表示，每个字符串对应网格的一行，字符串中的每个字符代表该行对应列的单元格状态：
- 若
Si的第j个字符为#，则单元格(i, j)已被涂成黑色。 - 若
Si的第j个字符为.，则单元格(i, j)已被涂成白色。 - 若
Si的第j个字符为?，则单元格(i, j)尚未涂色。
- 若
约束条件
H和W的取值范围是1 ≤ H, W ≤ 1000，且H和W均为整数。- 每个字符串
Si由字符#、.和?组成，长度为W。 - 网格中至少存在一个已经被涂成黑色的单元格。
目标要求
高桥想要将所有尚未涂色的单元格涂成白色或黑色，使得所有黑色单元格构成一个矩形。更准确地说，需要存在一组整数 (a, b, c, d)（1 ≤ a ≤ b ≤ H，1 ≤ c ≤ d ≤ W）满足以下条件：
- 对于每个单元格
(i, j)（1 ≤ i ≤ H，1 ≤ j ≤ W），若a ≤ i ≤ b且c ≤ j ≤ d，则该单元格为黑色； - 否则，该单元格为白色。
我的想法：
我们可以找‘#’的（a,b,c,d）如图，然后遍历这个区域，只要在这个区域内没有‘.’，即可构成矩形
（这题我很快就相出解法，但是，我一开始把a，b，c，d全部初始化为-1，然后以为最先遇到的那个‘#’就一定是colstart，和rowstart，wa了4发，又是40个样例，只错1个，成功气笑，还以为是不是有‘#’不出现的情况，调了半天看到There is at least one cell that is already painted black.沉默且破防，最后把这个图倒过来看，才想出来。。。。。）
//ACcode:
#include <iostream>
using namespace std;
char grid[1010][1010];
int main()
{
int h,w;
int a=9999,b=-1,c=9999,d=-1;
cin>>h>>w;
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
cin>>grid[i][j];
if(grid[i][j]=='#')//找'#'的a,b,c,d
{
if(i<a) a=i;//rowstart
if(i>b) b=i;//rowend
if(j<c) c=j;//colstart
if(j>d) d=j;//colend;
}
}
}
for(int i=a;i<=b;i++){
for(int j=c;j<=d;j++){
if(grid[i][j]=='.'){
cout<<"No";
return 0;
}
}
}
cout<<"Yes";
return 0;
}
