＜02.25＞Leetcode100

package Java_Input;

import java.io.*;
import java.util.*;
import java.text.*;
public class demo01 {
    public static void main(String[] args) throws IOException {
        //快读1
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //快读2
        StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
        //快写
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        
        st.nextToken();
        int m = (int) st.nval;
        st.nextToken();
        int n = (int) st.nval;
        int[][] arr = new int[m][n];
        for(int i=0;i<m;i++) {
        	for(int j=0;j<n;j++) {
        		st.nextToken();
        		arr[i][j] = (int) st.nval;
        	}
        }
        List<Integer> ans =new ArrayList<>();
        if(arr.length == 0)pw.println(ans);
        int l = 0, r = arr[0].length - 1, t = 0, b = arr.length - 1;
        while(true) {
        	for(int i=l;i<=r;i++)ans.add(arr[t][i]);//从左向右遍历
        	if(++t>b)break;//等于的时候是最后一行
        	for(int i=t;i<=b;i++)ans.add(arr[i][r]);//从上往下遍历
        	if(l>--r)break;
        	for(int i=r;i>=l;i--)ans.add(arr[b][i]);//从右向左遍历
        	if(t>--b)break;
        	for(int i=b;i>=t;i--)ans.add(arr[i][l]);//从下往上遍历
        	if(++l>r)break;
        }
        pw.println(ans);
      	//一定要记得关流
        pw.close();
        br.close();
	}
}

    public static void main(String[] args) throws IOException {
        //快读1
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //快读2
        StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in));
        //快写
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        
        st.nextToken();
        int n = (int) st.nval;
        int[][] arr = new int[n][n];
        for(int i=0;i<n;i++) {
        	for(int j=0;j<n;j++) {
        		st.nextToken();
        		arr[i][j] = (int) st.nval;
        	}
        }
        for(int i=0;i<n/2;i++) {
        	for(int j=0;j<(n+1)/2;j++){
        		int temp = arr[i][j];
        		arr[i][j] = arr[n-1-j][i];
        		arr[n-1-j][i] = arr[n-1-i][n-1-j];
        		arr[n-1-i][n-1-j] = arr[j][n-1-i];
        		arr[j][n-1-i] = temp;
        		
        	}
        }
      	//一定要记得关流
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)pw.print(arr[i][j]);
        pw.close();
        br.close();
	}

 行交换 并且对称 能实现顺时针90度 列交换并对称 能实现逆时针90度

class Solution {
   public void rotate(int[][] matrix){
        for(int i=0;i<matrix.length/2;i++){
            int[] temp =  matrix[i];
            matrix[i]=matrix[matrix.length-i-1];
            matrix[matrix.length-i-1]=temp;
        }

        for(int i=0;i<matrix.length;i++) {
            for (int j = 0; j < i; j++) {
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
    }
}

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

o表示true ,表示false 而v本身也要是true

如果我们的目标是下面这个v，那麽就必须使用模板 1

................vooooooooo

假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2

oooooooov...................

所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦

左加右减 减需要还 

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (matrix[i][mid] <= target) l = mid;
                else r = mid - 1;
            }
            if (matrix[i][r] == target) return true;
        }
        return false;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {//m行n列
        int m = matrix.length;
        int n= matrix[0].length;
        int i=0,j=n-1;
        while(i<=m-1&&j>=0){
            int temp = matrix[i][j];
            if(target>temp)i++;
            else if(target<temp)j--;
            else return true;
        }
        return false;
    }
}