Java算法笔记（三）

init：
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        arr[i][j] = scanner.nextInt();
        insert(i, j, i, j, arr[i][j]);
    }
}
//相邻的符号相反，有x2/y2的有+1。
insert：
d[x1][y1] += v;
d[x2+1][y1] -= v;
d[x1][y2+1] -= v;
d[x2+1][y2+1] += v;
// 计算二维差分的前缀和，即原二维数组 arr
sum：
arr[0][0] = d[0][0];
for (j = 1; j < m; j++){//第一行
      arr[0][j] = arr[0][j - 1] + d[0][j];//类比一维
  }
for (i = 1; i < n; i++){//第一列
    arr[i][0] = arr[i - 1][0] + d[i][0];//类比一维
  }
for (i = 1; i < n; i++){//其他
    for (j = 1; j < m; j++){
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + d[i][j];//类比前缀和构建
        }
    }

题目描述：
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1, y1, x2, y2, c，其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式：
第一行包含整数 n, m, q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1, y1, x2, y2, c，表示一个操作。
输出格式：
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围：
1 ≤ n, m ≤1000, 1 ≤ q ≤100000, 0 ≤ x1 ≤ x2 ≤ n - 1, 0 ≤ y1 ≤ y2 ≤ m - 1, −1000 ≤ c ≤ 1000, −1000 ≤ 矩阵内元素的值 ≤ 1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
0 0 1 1 1
0 2 1 2 2
2 0 2 3 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2

S[i, j] = 第i行j列格子左上部分所有元素的和
S[i, j] = S[i-1,j] + s[i,j-1] - S[i-1,j-1] + a[i,j](表示当前的数)（双重for循环构建）
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1-1,y2] - S[x2,y1-1] + S[x1-1,y1-1]
int matrix[M][N], prefix[M][N];        // M、N分别表示二维矩阵的高度和宽度
void CreatePrefix(int m, int n) {
 for(int i=1;i<=m;i++)                 // 二维矩阵的录入以及二维前缀和数组的构建 
   for(int j=1;j<=n;j++){
     cin>>matrix[i][j];
     prefix[i][j] = prefix[i-1][j]+ prefix[i][j-1]- prefix[i-1][j-1]+matrix[i][j];
  }
}
//在给定了两个序数对(x1, y1)、(x2, y2)后，
//通过二维前缀和数组求解指定子阵元素和的公式为：
S=prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 -1] + prefix[x1 -1][y1 -1]

public class demo79_前缀和_最大子段和 {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        //sum用于记录前缀和，max用于记录最大值，now用于记录当前输入的值
        int n, sum, max, now;   
        n = scanner.nextInt();  //将输入序列的第一个值作为sum
        scanner.nextLine();     //将sum的值作为max的初始值
        sum = scanner.nextInt();
        max = sum;
        while (--n > 0) {
            now = scanner.nextInt();
            sum = Math.max(sum, 0); //判断sum的正负以决定是否保留该序列
            sum += now;             //无论怎样，都加上当前输入的值以对比max
            max = Math.max(max,sum);
        }
        System.out.println(max);
    }
 }

public class demo79_前缀和数组_子矩阵的和 {
    static int N = 1005;
    static int n, m, q;
    static int[][] map = new int[N][N];
    static int[][] prefix = new int[N][N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        q = scanner.nextInt();
        scanner.nextLine();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                map[i][j] = scanner.nextInt();
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + map[i][j];
            }
        }
        int x1, y1, x2, y2;
        while (q-- > 0) {
            x1 = scanner.nextInt();
            y1 = scanner.nextInt();
            x2 = scanner.nextInt();
            y2 = scanner.nextInt();
            System.out.println(prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1]);
        }
    }
}

int f(int n){
        if(n == 1 || n == 2) return 1; // 递归出口
        return f(n-1) + f(n-2); // 递归式
}

public class Queue8Simple {
    static int max = 8;//定义一个max表示共有多少个皇后
    //定义数组array, 保存皇后放置位置的结果,比如
    //arr = {0 , 4, 7, 5, 2, 6, 1, 3} ----数字表示列
    static int[] array = new int[max];
    static int count = 0;//解法数目
    public static void main(String[] args) {
        dfs(0);
        System.out.printf("一共有%d解法", count);
    }
    //编写一个方法，放置第n个皇后
    //特别注意： dfs 是 每一次递归时，进入到dfs中都有 
    //for(int i = 0; i < max; i++)，因此会有回溯
    private static void dfs(int n) {
        if (n == max) {  //n = 8 , 其实8个皇后就既然放好
            return;
        }
        //依次放入皇后每一列(i)，并判断是否冲突
        //如果冲突，就继续循环，看下一列是否能成功放置皇后
        for (int i = 0; i < max; i++) {
            //i的值代表皇后在第几列
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            for (int j = 0; j < n; j++) {
                if (!(array[j] == array[n] || Math.abs(n - j) == Math.abs(array[n] - array[j]))) {
                    dfs(n + 1); 
                }
            }
        }
    }
}

import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
public class HorseChessboard {
   private static int X; // 棋盘的列数
   private static int Y; // 棋盘的行数
   //创建一个数组，标记棋盘的各个位置是否被访问过
   private static boolean[] visited;
   //使用一个属性，标记是否棋盘的所有位置都被访问
   private static boolean finished; // 如果为true,表示成功
   public static void main(String[] args) {
      System.out.println("骑士周游算法，开始运行~~");
      //测试骑士周游算法是否正确
      X = 8;
      Y = 8;
      int row = 1; //马儿初始位置的行，从1开始编号
      int column = 1; //马儿初始位置的列，从1开始编号
      //创建棋盘
      int[][] chessboard = new int[X][Y];
      visited = new boolean[X * Y];//初始值都是false
      //测试一下耗时
      long start = System.currentTimeMillis();
      dfs(chessboard, row - 1, column - 1, 1);
      long end = System.currentTimeMillis();
      System.out.println("共耗时: " + (end - start) + " 毫秒");
      //输出棋盘的最后情况
      for(int[] rows : chessboard) {
         for(int step: rows) {
            System.out.print(step + "\t");
         }
         System.out.println();
      }
   }
   /**
    * 完成骑士周游问题的算法
    * @param chessboard 棋盘
    * @param row 马儿当前的位置的行 从0开始 
    * @param column 马儿当前的位置的列  从0开始
    * @param step 是第几步 ,初始位置就是第1步 
    */
   public static void dfs(int[][] chessboard, int row, int column, int step) {
      chessboard[row][column] = step;
      //这里是把二维数组降维为一维数组，通过加上前面的行数和当前的列数，得到现在是第几个元素
      visited[row * X + column] = true; //标记该位置已经访问
      //获取当前位置可以走的下一个位置的集合
//-----------不能把这个list写在外面！每次递归都需要一个单独的list对象，表示每层递归中下一次可以走的点的集合
      ArrayList<Point> ps = next(new Point(column, row));
      //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
//-----------下面这句话是贪心的体现,并且要注意：
// ---------------不要直接在这里面写比较器，因为每次创建并且执行这样的操作，也会花费时间，单独写一个方法来比较，用空间换时间
      sort(ps);
      //遍历 ps
      while(!ps.isEmpty()) {
         Point p = ps.remove(0);//取出下一个可以走的位置
         //判断该点是否已经访问过
//-----------这里把x 看成列，y 看成行，模拟坐标中的(x,y)
         if(!visited[p.y * X + p.x]) {//说明还没有访问过
            dfs(chessboard, p.y, p.x, step + 1);
         }
      }
      //判断马儿是否完成了任务，使用   step 和应该走的步数比较 ， 
      //如果没有达到数量，则表示没有完成任务，将整个棋盘置0
      //说明: step < X * Y  成立的情况有两种
      //1. 棋盘到目前位置,仍然没有走完
      //2. 棋盘处于一个回溯过程
//------这里是回溯的过程，从dfs的最深处开始回溯，如果没有走完，把状态重置，以免影响下一次的递归
      if(step < X * Y && !finished ) {
         chessboard[row][column] = 0;
         visited[row * X + column] = false;
      } else {
         finished = true;
      }
   }
   /**
    * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
    * @param curPoint
    * @return
    */
   public static ArrayList<Point> next(Point curPoint) {
      //创建一个ArrayList
      ArrayList<Point> ps = new ArrayList<>();
      //创建一个Point
      Point p1 = new Point();
      //表示马儿可以走5这个位置
      if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走6这个位置
      if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走7这个位置
      if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走0这个位置
      if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走1这个位置
      if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走2这个位置
      if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走3这个位置
      if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
         ps.add(new Point(p1));
      }
      //判断马儿可以走4这个位置
      if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
         ps.add(new Point(p1));
      }
      return ps;
   }
   //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
   public static void sort(ArrayList<Point> ps) {
      ps.sort(new Comparator<Point>() {
         @Override
         public int compare(Point o1, Point o2) {
            //获取到o1的下一步的所有位置个数
            int count1 = next(o1).size();
            //获取到o2的下一步的所有位置个数
            int count2 = next(o2).size();
            if(count1 < count2) {
               return -1;
            } else if (count1 == count2) {
               return 0;
            } else {
               return 1;
            }
         }
      });
   }
}

 public static void bfs(int x, int y){
    q.add(x, y);  //将起点入队
    vis[x][y] = 1; // 标记已经走过
    while(!q.isEmpty()){ // 当队列不空
            x = q.peek().x; //取出队头元素
            y = q.peek().y; 
            q.poll(); //删除队头元素
            if(x == n-1 && n == m-1) return; // 到达终点
            for(int i = 0; i < 4; i++){ // 当前点可以到达的下四个方向
                    int nx = x + dx[i]; // 下个点的坐标
                    int ny = y + dy[i]; 
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] == 1 ) continue; // 下个点不合法
                    else{
                        q.add(new pair(nx,ny));        //下个点合法，入队存储
                        vis[nx][ny] = 1; // 标记该点已经走过
                    }
            }
    }
}