本文主要是介绍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[][] mat1, int[][] mat2) {// m * k , k * n = m * n;int m = mat1.length;int n = mat2[0].length;int[][] res = new int[m][n];for(int i = 0; i < m; i++) {for(int k = 0; k < mat1[0].length; k++) {if(mat1[i][k] != 0) {for(int j = 0; j < n; j++) {if(mat2[k][j] != 0) {// // m * k , k * n = m * n; // k是一个list，所以res是个加和的关系；res[i][j] += mat1[i][k] * mat2[k][j];}}}}}return res;}
}Spiral Matrix , 思路：用startX, endX, startY, endY来做决定，这个算法是最容易懂的；
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();int m = matrix.length;int n = matrix[0].length;int startX = 0; int endX = m - 1;int startY = 0; int endY = n - 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;}boolean firstrow = false;boolean firstcol = false;int m = matrix.length;int n = matrix[0].length;for(int i = 0; i < m; i++) {for(int j = 0; j < n; 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 < m; i++) {for(int j = 1; j < n; j++) {// 如果横竖，有0元素，这个[i,j] 就为0；if(matrix[0][j] == 0 || matrix[i][0] == 0) {matrix[i][j] = 0;}}}if(firstrow) {for(int j = 0; j < n; j++) {matrix[0][j] = 0;}}if(firstcol) {for(int i = 0; i < m; 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;}
}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[] point: points) {int x = point[0];int y = point[1];hashmap.putIfAbsent(x, new HashSet<Integer>());hashmap.get(x).add(y);}int res = 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];// 注意这里是或者，因为只要在一条直线上，area都是0；if(x1 == x2 || y1 == y2) {continue;}if(hashmap.get(x1).contains(y2) && hashmap.get(x2).contains(y1)) {res = Math.min(res, Math.abs(x2 - x1) * Math.abs(y2 - y1));}}}return res == Integer.MAX_VALUE ? 0 : res;}
}Candy Crush horizontal 和vertical比较之后，把相同的三个元素的值变成负数，那么每次比较的时候比较绝对值就可以了。改成负数之后，再做vertical的消去，怎么消去就是从低端开始，把不是负数的值挪到低端，最后上面的清零；然后循环，看有没有需要消去match的，如果没有了，就返回最终结果。O((m * n ) * (m * n);
class Solution {public int[][] candyCrush(int[][] board) {int m = board.length;int n = board[0].length;boolean shouldContinue = false;// match horizontal;for(int i = 0; i < m; i++) {for(int j = 0; j < n - 2; j++) {int v = Math.abs(board[i][j]);if(v > 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {shouldContinue = true;board[i][j] = board[i][j + 1] = board[i][j + 2] = -v;}}}// match vertical;for(int i = 0; i < m - 2; i++) {for(int j = 0; j < n; j++) {int v = Math.abs(board[i][j]);if(v > 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {shouldContinue = true;board[i][j] = board[i + 1][j] = board[i + 2][j] = -v;}}}// drop vertical;for(int j = 0; j < n; j++) {int r = m - 1;// drop;for(int k = r; k >= 0; k--) {if(board[k][j] > 0) {board[r--][j] = board[k][j];}}//set 0;for(int k = r; k >= 0; k--) {board[k][j] = 0;}}return shouldContinue ? candyCrush(board) : board;}
}Rectangle Area 两个面积之和，等于两个面积减去公共的overlap面积；求公共的面积，等于 右边一维的最小值，减去左边一维的最大值；同理求得 y轴的length；两者相乘就是overlap的面积；
class Solution {public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {int abcd = (C - A) * (D - B);int efgh = (G - E) * (H - F);int overlap = getOverlapLength(A, C, E, G) * getOverlapLength(B, D, F, H);return abcd + efgh - overlap;}private int getOverlapLength(int A, int C, int E, int G) {if(E > C || G < A) {return 0;}return Math.min(C, G) - Math.max(A, E);}
}Find N Unique Integers Sum up to Zero 前面继续加，最后一个数为-sum；
class Solution {public int[] sumZero(int n) {int[] res = new int[n];int sum = 0;for(int i = 0; i < n - 1; i++) {res[i] = i + 1;sum += i + 1;}res[n - 1] = -sum;return res;}
}Increasing Triplet Subsequence 找出当前的最小值和第二小的值，如果还有值比第二小的值大，那么就return true；否则return false；
class Solution {public boolean increasingTriplet(int[] nums) {if(nums == null || nums.length == 0 ) {return false;}int min = Integer.MAX_VALUE;int secondMin = Integer.MAX_VALUE;for(int num: nums) {if(num <= min) {min = num;} else if(num <= secondMin) {secondMin = num;} else if(num > secondMin) {return true;}}return false;}
}Maximum Length of Subarray With Positive Product
这个算法是目前为止最清晰的；
1.If we see a 0, we gotta start off things again
2.If we see a positive number :
2.1. Increase length of positive mutilpicative result till now.
2.2. Increase length of negative mutilpicative result till now, unless we had not encountered any negative before.
3. If we see a negative number:
3.1. It's time to swap positive and negative multiplicative results' lengths and do similar task as we did in above case.
4. In each iteration, use the length of positive mutilpicative result to compute answer.
class Solution {public int getMaxLen(int[] nums) {if(nums == null || nums.length == 0) {return 0;}int positive = 0; int negative = 0;int res = 0;for(int num: nums) {if(num == 0) {positive = 0;negative = 0;} else if(num > 0) {positive++;negative = negative == 0 ? 0 : negative+1;} else {// num < 0;int temp = positive;positive = negative == 0 ? 0 : negative + 1;negative = temp + 1;}res = Math.max(res, positive);}return res;}
}这篇关于Math 题目总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
