Kohei Arai LeetCode 1292 Maximum Side Length of a Square with Sum Less than or Equal to Threshold
No License Java
2019年12月15日
Copy
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
		if (mat == null || mat.length == 0 || mat[0].length == 0) {
			return 0;
		}
		
		int M = mat.length;
		int N = mat[0].length;
		
		// Precompute the sum
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				mat[i][j] = getAt(mat, i, j) + getAt(mat, i - 1, j) + getAt(mat, i, j - 1) - getAt(mat, i - 1, j - 1);
			}
		}
		
		int ans = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 1; i + k < M && j + k < N; k++) {
					int area = getAt(mat, i + k, j + k) - getAt(mat, i + k, j - 1) - getAt(mat, i - 1, j + k) + getAt(mat, i - 1, j - 1);
					if (area <= threshold) {
						ans = Math.max(ans, k + 1);
					}
				}
			}
		}
		
		return ans;
    }

	public int getAt(int[][] mat, int i, int j) {
		if (i < 0 || j < 0) return 0;
		return mat[i][j];
	}

}
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
		if (mat == null || mat.length == 0 || mat[0].length == 0) {
			return 0;
		}
		
		int M = mat.length;
		int N = mat[0].length;
		
		// Precompute the sum
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				mat[i][j] = getAt(mat, i, j) + getAt(mat, i - 1, j) + getAt(mat, i, j - 1) - getAt(mat, i - 1, j - 1);
			}
		}
		
		int ans = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 1; i + k < M && j + k < N; k++) {
					int area = getAt(mat, i + k, j + k) - getAt(mat, i + k, j - 1) - getAt(mat, i - 1, j + k) + getAt(mat, i - 1, j - 1);
					if (area <= threshold) {
						ans = Math.max(ans, k + 1);
					}
				}
			}
		}
		
		return ans;
    }

	public int getAt(int[][] mat, int i, int j) {
		if (i < 0 || j < 0) return 0;
		return mat[i][j];
	}

}
https://leetcode.com/contest/weekly-contest-167/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/ 解答例

年末年始は機械学習・深層学習を勉強しませんか?
No one still commented. Please first comment.
年末年始は機械学習・深層学習を勉強しませんか?
広告
未経験から最短でエンジニアへの転職を目指すなら