数组题目：118. 杨辉三角 、 119. 杨辉三角 II 、661. 图片平滑器 、598. 范围求和 II 、 419. 甲板上的战舰 |
您所在的位置：网站首页 › 杨辉三角的图片 › 数组题目：118. 杨辉三角 、 119. 杨辉三角 II 、661. 图片平滑器 、598. 范围求和 II 、 419. 甲板上的战舰 |
数组题目：118. 杨辉三角 、 119. 杨辉三角 II 、661. 图片平滑器 、598. 范围求和 II 、 419. 甲板上的战舰
|
118. 杨辉三角
思路：
找规律，每一行的第一个元素和最后一个元素都是1，其中中间需要改变的数找对应的规律 比如第二行（从0开始）的2，是dp[1][0] + dp[1][1]。类似的找出对应的规律 代码： class Solution { public: vector generate(int numRows) { vector dp; for(int i = 0; i < numRows; i++) { vector line(i + 1); line[0] = line[i] = 1; for(int j = 1; j < i; j++) { line[j] = dp[i - 1][j - 1] + dp[i - 1][j]; } dp.push_back(line); } return dp; } }; 119. 杨辉三角 II
和上面一样，只是返回需要的那一行的数组 代码： class Solution { public List getRow(int rowIndex) { List ret = new ArrayList(); for(int i = 0; i {0,0} , {1, 0}, {-1,0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, 1}, {1, -1}}; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ int num = 0, sum = 0; for(int[] di : dis){ int next_m = i + di[0], next_n = j + di[1]; if(next_m < 0 || next_m = m || next_n < 0 || next_n = n){ continue; } sum += img[next_m][next_n]; num ++; } ret[i][j] += sum / num; } } return ret; } } 598. 范围求和 II
这个黄色的2，下面也包含了[3,3]，所以我们发现左上角的(0,0)肯定是累加之后最大的，所以我们需要找到右下角和(0,0)一样的情况，所以就看ops里面最小的数组。 代码： class Solution { public int maxCount(int m, int n, int[][] ops) { for(int[] op :ops){ m = Math.min(m, op[0]); n = Math.min(n, op[1]); } return m * n; } } 419. 甲板上的战舰
我们假定只看左上角，那么会有两个情况，当当前左边为'x'： 左边的索引和上边的索引小于0他的左边和上边都没有'X' 代码： class Solution { public int countBattleships(char[][] board) { int count = 0; int m = board.length, n = board[0].length; for(int i = 0; i < m;i ++){ for(int j = 0; j < n; j++){ if(board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 ||board[i][j - 1] != 'X')){ count ++; } } } return count; } } |
【本文地址】
今日新闻 |
推荐新闻 |