wy的leetcode刷题记录_Day50

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2022-11-23

前言

补

目录

• wy的leetcode刷题记录_Day50
• • 声明
  • 前言
  • 1742. 盒子中小球的最大数量
  • • 题目介绍
    • 思路
    • 代码
    • 收获
  • 700. 二叉搜索树中的搜索
  • • 题目介绍
    • 思路
    • 代码
    • 收获

1742. 盒子中小球的最大数量

今天的每日一题是：1742. 盒子中小球的最大数量

题目介绍

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

示例 1：
输入：lowLimit = 1, highLimit = 10
输出：2
解释： 盒子编号：1 2 3 4 5 6 7 8 9 10 11 … 小球数量：2 1 1 1 1 1 1 1 1 0 0 … 编号 1 的盒子放有最多小球，小球数量为 2 。

示例 2：
输入：lowLimit = 5, highLimit = 15
输出：2
解释： 盒子编号：1 2 3 4 5 6 7 8 910 11 … 小球数量：1 1 1 1 2 2 1 1 1 0 0 … 编号 5 和 6的盒子放有最多小球，每个盒子中的小球数量都是 2 。

思路

简单的模拟思路：创建一个辅助函数用来计算每个数字每个位数上的数字相加和，然后使用一个hash表来存贮对应下标箱子的存贮个数。最后在这个hash表中寻找最大值就可以了。

代码

class Solution {
public:int countBalls(int lowLimit, int highLimit) {unordered_map hash;for(int i=lowLimit;i<=highLimit;i++){int index=caculate_index(i);if(!hash.count(index))hash[index]=1;elsehash[index]++;}int ans=hash[0];for(auto temp:hash){ans=max(ans,temp.second);}return ans;}int caculate_index(int num){int res=0;while(num!=0){res+=num%10;num/=10;}return res;}
};

收获

简单模拟提，刷刷手速

700. 二叉搜索树中的搜索

700. 二叉搜索树中的搜索

题目介绍

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

思路

递归：
利用搜索树的性质，根节点左边的值小于根节点，右边的值大于根节点递归的搜索。
递推：
同理，只需沿着树的某一条路符合搜索树的性质走就可以了

代码

递归：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==nullptr)return root;TreeNode*ans;if(val>root->val)ans=searchBST(root->right,val);else if(valval)ans=searchBST(root->left,val);else if(val==root->val)return root;return ans;}
};

递推：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root!=nullptr){if(val>root->val){root=root->right;}else if(valval){root=root->left;}else if(val==root->val)return root;}return root;//这个时候就是没找到了}
};

收获

重新温故了二叉树的知识，二叉树的特点就是根节点左边的所有节点的值全部小于根节点的值，根节点右边的所有节点的值全部大于根节点的值。