Math 题目总结

Math的题目，其实全是数学知识，没有什么太多的算法可言。

Sparse Matrix Multiplication (矩阵相乘就是所有的k，A(i,k) * B(k,j) = C(i,j) ，稀疏矩阵就是 有很多0，为了提高速度也就是如果 A(i,k) 或者B(k,j), k 从0到length，如果有0，那么这个计算就不进行了)

class Solution { public int[][] multiply(int[][] A, int[][] B) { int n = A.length; int m = B[0].length; int[][] res = new int[n][m]; // A[i, k] * B[k, j] = C[i, j] for(int i = 0; i < n; i++) { for(int k = 0; k < A[0].length; k++) { if(A[i][k] != 0) { for(int j = 0; j < m; j++) { if(B[k][j] != 0) { res[i][j] += A[i][k] * B[k][j]; } } } } } return res; } }

Spiral Matrix , 思路：用startX, endX, startY, endY来做决定，这个算法是最容易懂的；

class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<Integer>(); if(matrix == null || matrix.length == 0 || matrix[0].length == 0) { return list; } int n = matrix.length; int m = matrix[0].length; int startX = 0; int endX = n - 1; int startY = 0; int endY = m - 1; while(startX <= endX && startY <= endY) { // collect top; for(int j = startY; j <= endY; j++) { list.add(matrix[startX][j]); } if(++startX > endX) break; // collect right; for(int i = startX; i <= endX; i++) { list.add(matrix[i][endY]); } if(--endY < startY) break; // collect bottom; for(int j = endY; j >= startY; j--) { list.add(matrix[endX][j]); } if(--endX < startX) break; // collect left; for(int i = endX; i >= startX; i--) { list.add(matrix[i][startY]); } if(++startY > endY) break; } return list; } }

Spiral Matrix II 算法跟之前的 Sprial Matrix I，一模一样。

class Solution { public int[][] generateMatrix(int n) { int startX = 0; int endX = n - 1; int startY = 0; int endY = n - 1; int[][] res = new int[n][n]; int value = 1; while(startX <= endX && startY <= endY) { // top; for(int j = startY; j <= endY; j++) { res[startX][j] = value++; } if(++startX > endX) break; // right; for(int i = startX; i <= endX; i++) { res[i][endY] = value++; } if(--endY < startY) break; // bottom; for(int j = endY; j >= startY; j--) { res[endX][j] = value++; } if(--endX < startX) break; // left; for(int i = endX; i >= startX; i--) { res[i][startY] = value++; } if(++startY > endY) break; } return res; } }

Set Matrix Zero 思路：终极follow up是是否用O(1)space来做，思路就是，利用第一行和第一列还记录为0的信息，然后用两个变量hold住第一行和第一列是否需要变为0。然后扫描中间的matrix，如果对应行或者列，在第一行和第一列上是0，那么设置成0，然后再判断第一行和第一列是否需要清空；

class Solution { public void setZeroes(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) { return; } int n = matrix.length; int m = matrix[0].length; // 第一行和第一列，用来记录之后，还要清空，所以用变量记录一下状态，最后是要清空的； boolean firstrow = false; boolean firstcol = false; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 0) { if(i == 0) { firstrow = true; } if(j == 0) { firstcol = true; } matrix[0][j] = 0; matrix[i][0] = 0; } } } for(int i = 1; i < n; i++) { for(int j = 1; j < m; j++) { if(matrix[0][j] == 0 || matrix[i][0] == 0) { matrix[i][j] = 0; } } } if(firstrow) { for(int j = 0; j < m; j++) { matrix[0][j] = 0; } } if(firstcol) { for(int i = 0; i < n; i++) { matrix[i][0] = 0; } } } }

Second Max of Array 思路：打擂台算法；比最大的大，顺序挪动，比第二的大，就赋值第二大的；刚开始取最小的Integer.MIN_VALUE;

public class Solution { /** * @param nums: An integer array * @return: The second max number in the array. */ public int secondMax(int[] nums) { if(nums == null || nums.length == 0) { return -1; } int max = Integer.MIN_VALUE; int secondmax = Integer.MIN_VALUE; for(int i = 0; i < nums.length; i++) { if(nums[i] > max) { secondmax = max; max = nums[i]; } else if(nums[i] > secondmax) { secondmax = nums[i]; } } return secondmax; } }

Max Consecutive Ones 思路：扫一遍，遇见1就count++； 并且同时update res，遇见0就清零；

class Solution { public int findMaxConsecutiveOnes(int[] nums) { int count = 0; int maxcount = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] == 1) { count++; } else { count = 0; } maxcount = Math.max(maxcount, count); } return maxcount; } }

Find Winner on a Tic Tac Toe Game 思路：主要思想就是用rows, cols, diagonal, antidiagonal 去记录四种可能win的状态，antidiagonal 状态是： x + y = n - 1; A走 +1， B走-1； 

class Solution { public String tictactoe(int[][] moves) { int[] rows = new int[3]; int[] cols = new int[3]; int diagonal = 0; int antidiagonal = 0; // A add 1, B add -1; for(int i = 0; i < moves.length; i++) { int add = i % 2 == 0 ? 1 : -1; int x = moves[i][0]; int y = moves[i][1]; rows[x] += add; cols[y] += add; if(x == y) { diagonal += add; } if(x + y== 3 - 1) { antidiagonal += add; } } if(isAwin(rows, cols, diagonal, antidiagonal)) { return "A"; } if(isBwin(rows, cols, diagonal, antidiagonal)) { return "B"; } if(moves.length == 9) { return "Draw"; } return "Pending"; } private boolean isAwin(int[] rows, int[] cols, int diagonal, int antidiagonal) { for(int i = 0; i < 3; i++) { if(rows[i] == 3 || cols[i] == 3) { return true; } } return diagonal == 3 || antidiagonal == 3; } private boolean isBwin(int[] rows, int[] cols, int diagonal, int antidiagonal) { for(int i = 0; i < 3; i++) { if(rows[i] == -3 || cols[i] == -3) { return true; } } return diagonal == -3 || antidiagonal == -3; } }

Set Matrix Zeroes 思路：就是用1st row和1st col来记录0的i，j的信息，然后用两个变量记录是否需要把第一行和第一列清空；

​ class Solution { public void setZeroes(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) { return; } int n = matrix.length; int m = matrix[0].length; // 第一行和第一列，用来记录之后，还要清空，所以用变量记录一下状态，最后是要清空的； boolean firstrow = false; boolean firstcol = false; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 0) { if(i == 0) { firstrow = true; } if(j == 0) { firstcol = true; } matrix[0][j] = 0; matrix[i][0] = 0; } } } for(int i = 1; i < n; i++) { for(int j = 1; j < m; j++) { if(matrix[0][j] == 0 || matrix[i][0] == 0) { matrix[i][j] = 0; } } } if(firstrow) { for(int j = 0; j < m; j++) { matrix[0][j] = 0; } } if(firstcol) { for(int i = 0; i < n; i++) { matrix[i][0] = 0; } } } } ​

Minimum Area Rectangle 核心思想就是双层遍历，假设两个点分别是左上角(x1, y1)和右下角(x2, y2)，看能否找到(x2, y1), (x1, y2)，怎么找，那么就是同样的x下面有一系列点，那么就是HashMap<Integer, HashSet<Integer>>来找；注意遍历的时候，双层循环是points.length;

class Solution { public int minAreaRect(int[][] points) { if(points == null || points.length == 0 || points[0].length == 0) { return 0; } HashMap<Integer, HashSet<Integer>> hashmap = new HashMap<>(); for(int i = 0; i < points.length; i++) { int x = points[i][0]; int y = points[i][1]; hashmap.putIfAbsent(x, new HashSet<Integer>()); hashmap.get(x).add(y); } int minRec = Integer.MAX_VALUE; for(int i = 0; i < points.length; i++) { for(int j = i + 1; j < points.length; j++) { int x1 = points[i][0]; int y1 = points[i][1]; int x2 = points[j][0]; int y2 = points[j][1]; if(x1 == x2 || y1 == y2) { continue; } if(hashmap.get(x1).contains(y2) && hashmap.get(x2).contains(y1)) { minRec = Math.min(minRec, Math.abs(x1 - x2) * Math.abs(y1 - y2)); } } } return minRec == Integer.MAX_VALUE ? 0 : minRec; } }

Candy Crush

Rectangle Area

Find N Unique Integers Sum up to Zero

Maximum Length of Subarray With Positive Product

Increasing Triplet Subsequence