搜索到
17
篇与
的结果
-
leetcode|中等:11. 盛最多水的容器 1.题目给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1] 输出：1提示：n == height.length2 <= n <= 1050 <= height[i] <= 1042. 题解2.1 思路分析思路1：双指针 设两指针 i,j ，指向的水槽板高度分别为 h[i], h[j] ，此状态下水槽面积为 S(i,j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ： S(i, j) = min(h[i], h[j]) × (j - i) 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1 变短： 若向内移动短板，水槽的短板 min(h[i],h[j])可能变大，因此下个水槽的面积可能增大 若向内移动长板，水槽的短板 min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。2.2 代码实现public class Solution { public int maxArea(int[] height) { int max = 0; int left = 0,right = height.length-1; // 双指针 while (left<right){ int area = Math.min(height[left],height[right])*(right-left); max = Math.max(area,max); if(height[left]>height[right]){ right--; }else { left++; } } return max; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.maxArea(new int[]{1,8,6,2,5,4,8,3,7})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过4 ms51.6 MBJava2022/03/24 12:32添加备注参考资料https://leetcode-cn.com/problems/container-with-most-water/https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/ -
leetcode|中等:5. 最长回文子串 1.题目给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd" 输出："bb"提示：1 <= s.length <= 1000s 仅由数字和英文字母组成2. 题解2.1 思路分析思路1：暴力求解 从每个字符开始向右延伸探索可能构成的最长回文子串并记录最长子串的开始位置和长度2.2 代码实现public class Solution { //判断子串是否构成回文 public boolean isPalindrome(char[] sChars,int indexStart,int indexEnd){ int len = indexEnd-indexStart; if(len==1)return true; for (int i = 0; i < len/2; i++) { if(sChars[indexStart+i]!=sChars[indexEnd-1-i]){ return false; } } return true; } public String longestPalindrome(String s) { char[] sChars = s.toCharArray(); //转为字符数组 int sLen = s.length(); // 字符串长度 int indexStart = 0; //记录最长子串的开始位置 int maxLen = 1; //记录最大子串长度 for (int i = 0; i < sLen-maxLen; i++) { // 子串开始下标 for (int j = maxLen; j <= sLen-i; j++) { // 子串长度 if(isPalindrome(sChars,i,i+j)){ indexStart = i; maxLen = j; } } } return s.substring(indexStart,indexStart+maxLen); } public static void main(String[] args) { Solution solution = new Solution(); String in = "babad"; String res = solution.longestPalindrome(in); System.out.println(res); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过265 ms41.2 MBJava2022/03/23 17:11添加备注参考资料https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
