每日刷题记录 (三十一)

转x33g5p2x  于2022-07-26 转载在 其他  
字(4.8k)|赞(0)|评价(0)|浏览(561)

第一题: 419. 甲板上的战舰

LeetCode: 419. 甲板上的战舰

描述:
给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 ‘X’ 或者是一个空位 ‘.’ ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

解题思路:

  1. 这里首先去判断左上角, 如果是左上角就进行计数.
  2. 判断是否是左上角, 那么上方, 或者左方就不能为X
  3. 这样省去了判断右方和下方的方法.

代码实现:

  1. class Solution {
  2.     public int countBattleships(char[][] board) {
  3.         int res = 0;
  4.         for(int i = 0; i < board.length; i++) {
  5.             for(int j = 0; j < board[0].length; j++) {
  6.                 if((board[i][j] == 'X') && (i == 0 || board[i-1][j]=='.') && (j == 0 || board[i][j-1]=='.')){
  7.                     res++;
  8.                 }
  9.             }
  10.         }
  11.         return res;
  12.     }
  13. }

第二题: 443. 压缩字符串

LeetCode: 443. 压缩字符串

描述:
给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

  • 如果这一组长度为 1 ，则将字符追加到 s 中。
  • 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

解题思路:

  1. 双指针解题.
  2. 如果当前right和left字符相同, right++.
  3. 如果当前right不是left的右侧, 那么不记录出现次数, 如果是右侧, 就记录次数. (例如 chars = [“a”] , 不需要记录次数)
  4. 以字符串拼接的形式, 记录字符以及次数.

代码实现:

  1. class Solution {
  2.     public int compress(char[] chars) {
  3.         StringBuilder sb = new StringBuilder();
  4.         int left = 0;
  5.         int right = 0;
  6.         while(right < chars.length) {
  7.             right++;
  8.             while(right < chars.length && chars[left] == chars[right]) {
  9.                 right++;
  10.             }
  11.             sb.append(chars[left]);
  12.             if(right - left > 1) {
  13.                 sb.append(right - left);
  14.             }
  15.             left = right;
  16.         }
  17.         for(int i = 0; i < sb.length(); i++) {
  18.             chars[i] = sb.charAt(i);
  19.         }
  20.         return sb.length();
  21.     }
  22. }

第三题: 501. 二叉搜索树中的众数

LeetCode: 501. 二叉搜索树中的众数

描述:
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

解题思路:

  1. 这里使用中序遍历的方式去记录相同val值的次数.
  2. 在记录最大次数, 如果当前次数和最大次数相等就添加结果集中.
  3. 如果当前次数比最大次数大, 那么清空结果集, 重新添加.

代码实现:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     List<Integer> list = new ArrayList<>();
  18.     int maxCount = 0;
  19.     int count = 0;
  20.     TreeNode pre = null;
  21.     public int[] findMode(TreeNode root) {
  22.         inorder(root);
  23.         int[] res = new int[list.size()];
  24.         for(int i = 0; i < list.size(); i++) {
  25.             res[i] = list.get(i);
  26.         }
  27.         return res;
  28.     }
  29.     public void inorder(TreeNode root) {
  30.         if(root == null) return;
  31.         inorder(root.left);
  32.         if(pre == null) {
  33.             count = 1;
  34.         }else if(pre.val == root.val) {
  35.             count++;
  36.         }else{
  37.             count = 1;
  38.         }
  39.         pre = root;
  40.         if(maxCount == count) {
  41.             list.add(root.val);
  42.         }
  43.         if(maxCount < count) {
  44.             maxCount = count;
  45.             list.clear();
  46.             list.add(root.val);            
  47.         }
  48.         inorder(root.right);
  49.     }
  50. }

第四题: 503. 下一个更大元素 II

LeetCode: 503. 下一个更大元素 II

描述:
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

解题思路:

  1. 这里使用一个栈来记录当前最大元素.
  2. 这里使用二次遍历的方法. 类似于循环遍历.
  3. 首先将结果数组都赋值为 -1
  4. 如果当前元素大于栈顶元素, 就出栈. 同时对当前出栈下标进行赋值.(如果没有出栈, 就会自动为-1)
  5. 第一次遍历. 入栈下标.

代码实现:

  1. class Solution {
  2.     public int[] nextGreaterElements(int[] nums) {
  3.         int[] res = new int[nums.length];
  4.         Arrays.fill(res,-1);
  5.         Stack<Integer> stack = new Stack<>();
  6.         for (int i = 0; i < nums.length * 2; i++) {
  7.             int val = nums[i % nums.length];
  8.             while(!stack.isEmpty() && val > nums[stack.peek()]){
  9.                 res[stack.pop()] = val;
  10.             }
  11.             if(i < nums.length) stack.add(i);
  12.         }
  13.         return res;
  14.     }
  15. }

第五题: 508. 出现次数最多的子树元素和

LeetCode: 508. 出现次数最多的子树元素和

描述:
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）

解题思路:

  1. 这里直接记录每个节点的值, 以及该节点与子树节点的值. 使用哈希表记录. 并记录这些值出现的次数.
  2. 并且要记录出现的最大次数.
  3. 遍历哈希表, 查看value为最大次数的key, 添加到 List
  4. 并且遍历结果数组, 数组元素和List一样.

代码实现:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     Map<Integer,Integer> map = new HashMap<>();
  18.     int maxCount = 0;
  19.     public int[] findFrequentTreeSum(TreeNode root) {
  20.         if(root == null) return new int[0];
  21.         inorder(root);
  22.         List<Integer> list = new ArrayList<>();
  23.         int i = 0;
  24.         for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
  25.             if(maxCount == entry.getValue()) list.add(entry.getKey());
  26.         }
  27.         int[] res = new int[list.size()];
  28.         for(int j = 0; j < list.size(); j++) {
  29.             res[j] = list.get(j);
  30.         }
  31.         return res;
  32.     }
  33.     public int inorder(TreeNode root) {
  34.         if(root == null) return 0;
  35.         int left = inorder(root.left);
  36.         int right = inorder(root.right);
  37.         int sum = left + right + root.val;
  38.         map.put(sum,map.getOrDefault(sum,0)+1);
  39.         maxCount = Math.max(maxCount,map.get(sum));
  40.         return sum;
  41.     }
  42. }

第六题: 537. 复数乘法

LeetCode: 537. 复数乘法

描述:

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

  • 实部 是一个整数，取值范围是 [-100, 100]
  • 虚部 也是一个整数，取值范围是 [-100, 100]
  • i^2 == -1
    给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

解题思路:

  1. 这里首先对 nums1 和 nums2 进行字符串拆分
  2. 这里 nums1 的实部为 a1, nums1 的虚部为 a2
  3. 这里 nums2 的实部为 b1, nums2 的虚部为 b2
  4. 因此 结果的实部是 a1*b1-a2*b2, 虚部是 a2*b1+a1*b2
  5. 返回结果 a1*b1-a2*b2 + a2*b1+a1*b2 i

代码实现:

  1. class Solution {
  2.     public String complexNumberMultiply(String num1, String num2) {
  3.         String[] s1 = num1.split("\\+|i");
  4.         int a1 = Integer.parseInt(s1[0]);
  5.         int a2 = Integer.parseInt(s1[1]);
  6.         String[] s2 = num2.split("\\+|i");
  7.         int b1 = Integer.parseInt(s2[0]);
  8.         int b2 = Integer.parseInt(s2[1]);
  9.         int res1 = a1 * b1 - a2 * b2;
  10.         int res2 = a2 * b1 + a1 * b2;
  11.         return res1 + "+" + res2 + "i";
  12.     }
  13. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125929367

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法职场和发展

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com