Leetcode刷题 2021.01.24
Leetcode674 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i 1] ，那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
今天的每日一题，加了连续的最长递增序列，变得简单不少。因为是连续，所以不需要用dp记录之前的状态了，直接双指针滑动窗口即可。
class Solution {public int findLengthOfLCIS(int[] nums) {if (nums.length == 0) return 0; int n = nums.length; int i = 0, j = 1, res = 1; while (j < n){//双指针，如果j大于j之前的数，就加1 while(j < n && nums[j] > nums[j - 1]){j ; } //更新最大值 if (j - i > res){res = j - i; } //更新i的位置 i = j; //j设置比i大1 j ; } return res; }}
Leetcode419 甲板上的战舰
给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X’表示，空位用 '.'表示。 你需要遵守以下规则：
给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。
力扣有些题的翻译真的是一言难尽，看了好半天和评论的解释才明白。这题因为战舰之间一定有间隔，而且战舰一定是长方形的。所以只要战舰的头部的左上方没有其他战舰就是一艘了。
class Solution {public int countBattleships(char[][] board) {int m = board.length, n = board[0].length; int res = 0; 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] == '.') && (j == 0 || board[i][j - 1] == '.')){res ; } } } return res; }}
Leetcode1014 最佳观光组合
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] A[j] i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
这题也没想用dp之类的做，想法比较简单。遍历数组的时候记录一下当前可以提供的最大值就好了，这里最大值不单单是元素大小，还要记录元素下标的大小，元素下标对于整体大小是有负作用的，所有记录的时候记录下标即可。代码就比较简单了。
class Solution {public int maxScoreSightseeingPair(int[] A) {int max = 0, res = 0; for(int i = 1; i < A.length; i ){//记录全局“最大”值的下标，这里最大值和元素大小以及元素下标有关 res = Math.max(res, A[max] A[i] max - i); //更新当前最大 if (A[max] max - i < A[i]){max = i; } } return res; }}
赞 (0)