代碼隨想錄算法訓練營第二天| 209.長度最小子數組 59.螺旋矩陣 區間和 開發商購買土地

209.長度最小子數組

• result最初為nums.length + 1 才能在最后判斷不存在的情況且不會遺漏與數組等長的情況
• 滑動窗口：右指針代表窗口起始位置，左指針代表窗口結束位置
• 時間復雜度 O(n) : 每個數據被操作兩次，進窗口一次，出窗口一次

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
    	//result比長度大一可以判斷出result是否不存在
        int result = nums.length + 1;
        int right = 0;
        int left = 0;
        int sum = 0;
        for(left = 0; left < nums.length; left++){
            sum += nums[left];
            while(sum >= target){
                int subL = left - right + 1;
                result = Math.min(result, subL);
                sum -= nums[right];
                right++;
            }
        }
        return result > nums.length ? 0 : result;
    }
}

59.螺旋矩陣

轉幾圈：n/2

class Solution {
    public int[][] generateMatrix(int n) {

        int[][] nums = new int[n][n];

        //nums[starti][startj]表示每圈起始位置
        int starti = 0, startj = 0;

        //loop表示第幾圈;n-loop為每圈最后一排/列下標
        int loop = 1; 

        //i,j循環變量表示填充位置
        int i = 0, j = 0;

        //count表示填入數
        int count = 1;

        //每一圈填四條邊，左閉右開
        while(loop <=  n / 2){
            //確定起始點
            i = starti;
            j = startj;

            //頂邊j變
            for(; j < n - loop; j++){
                nums[i][j] = count++;
            }
            //右邊i變
            for(; i < n - loop; i++){
                nums[i][j] = count++;
            }
            //底邊j變
            for(; j > startj; j--){
                nums[i][j] = count++;
            }
            //左邊i變
            for(; i > starti; i--){
                nums[i][j] = count++;
            }

            //改變起始位置
            starti++;
            startj++;
            //改變圈數
            loop++;
        }
        
        //單獨判定奇數情況
        if(n % 2 == 1){
            nums[starti][startj] = count;
        }

        return nums;
    }
}

區間和

前綴和思想: 提供預處理數組,求所有前綴和

import java.util.Scanner;

public class Main{
    public static void main(String[] args){

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] num = new int[n];
        int[] p = new int[n];
        int presum = 0;

        for(int i = 0; i < n; i++){
            num[i] = scanner.nextInt();
            presum += num[i];
            p[i] = presum;
        }

        while(scanner.hasNextInt()){
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int sum;
            if(a == 0){
                System.out.println(p[b]);
            }else{
                System.out.println(p[b] - p[a - 1]);
            }
        }

        scanner.close();
    }
}

開發商購買土地

前綴和思想: 分別求預處理數組,行和與列和,再進行比較

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
         Scanner scanner = new Scanner(System.in);

         int n = scanner.nextInt();
         int m = scanner.nextInt();
         int num[][] = new int[n][m];
         int sum = 0;

         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                num[i][j] = scanner.nextInt();
                sum += num[i][j];
            }
         }

         int[] horizontal = new int[n];
         for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                horizontal[i] += num[i][j];
            }
         }

         int[] vertical = new int[m];
         for(int j = 0; j < m; j++){
            for(int i = 0; i < n; i++){
                vertical[j] += num[i][j];
            }
         }

         int result = Integer.MAX_VALUE;

         int horizontalCut = 0;
         for(int i = 0; i < n; i++){
            horizontalCut += horizontal[i];
            result = Math.min(result, Math.abs(sum - 2 * horizontalCut));
         }

         int verticalCut = 0;
         for(int j = 0; j < m; j++){
            verticalCut += vertical[j];
            result = Math.min(result, Math.abs(sum - 2 * verticalCut));
         }

        System.out.println(result);
        scanner.close();
    }
}