首页 > 其他分享 >[Leetcode] 0728. 自除数

[Leetcode] 0728. 自除数

时间:2023-06-21 15:11:41浏览次数:51  
标签:right int 0728 整数 num Leetcode 除数 left

728. 自除数

点击上方,跳转至leetcode

题目描述

自除数 是指可以被它包含的每一位数整除的数。

  • 例如,128 是一个 自除数 ,因为 128 % 1 == 0128 % 2 == 0128 % 8 == 0

自除数 不允许包含 0 。

给定两个整数 left 和 right ,返回一个列表,列表的元素是范围 [left, right] 内所有的 自除数

 

示例 1:

输入:left = 1, right = 22
输出:[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

示例 2:

输入:left = 47, right = 85
输出:[48,55,66,77]

 

提示:

  • 1 <= left <= right <= 104

解法

遍历范围 [left,right]内的所有整数,分别判断每个整数是否为自除数。

根据自除数的定义,如果一个整数不包含 0 且能被它包含的每一位数整除,则该整数是自除数。判断一个整数是否为自除数的方法是遍历整数的每一位,判断每一位数是否为 0 以及是否可以整除该整数。

遍历整数的每一位的方法是,每次将当前整数对 10 取模即可得到当前整数的最后一位,然后将整数除以 10。重复该操作,直到当前整数变成 0 时即遍历了整数的每一位。

时间复杂度:\(O(n \log \textit{right})\),其中 \(n\) 是范围内的整数个数,\(right\) 是范围内的最大整数。对于范围内的每个整数,需要 \(O(\log \textit{right})\) 的时间判断是否为自除数。

空间复杂度:\(O(1)\)。除了返回值以外,使用的额外空间为 \(O(1)\)。

Python3

from typing import List
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def isSelfDividing(num):
            temp = num
            while temp > 0:
                digit = temp % 10
                if digit == 0 or num % digit !=0:
                    return False
                temp = temp // 10
            return True
        return [i for i in range(left,right+1) if isSelfDividing(i)]
    
# left = 1
# right = 22
left = 47
right = 85
res = Solution().selfDividingNumbers(left,right)
print(res)
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        return [
            num
            for num in range(left, right + 1)
            if all(i != '0' and num % int(i) == 0 for i in str(num))
        ]

C++

#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    bool isSelfDividing(int num){
        int temp = num;
        while(temp>0){
            int digit = temp % 10;
            if(digit ==0 || num % digit !=0)
                return false;
            temp /= 10;
        }
        return true;
    }
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> res;
        for(int i = left; i<= right; i++){
            if(isSelfDividing(i)){
                res.push_back(i);
            }
        }
        return res;
    }
};

int main(){
    // int left = 1, right = 22;
    int left = 47, right = 85;
    vector<int> res = Solution().selfDividingNumbers(left,right);
    for(int i=0; i<res.size();i++){
        cout << res[i] << '\t';
    }
    cout << endl;
    return 0;
}

//g++ 728.cpp -std=c++11

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ans;
        for (int i = left; i <= right; ++i)
            if (check(i))
                ans.push_back(i);
        return ans;
    }

    bool check(int num) {
        for (int t = num; t; t /= 10) {
            int x = t % 10;
            if (x == 0 || num % x) return false;
        }
        return true;
    }
};

标签:right,int,0728,整数,num,Leetcode,除数,left
From: https://www.cnblogs.com/yege/p/17496260.html

相关文章

  • [Leetcode] 0733. 图像渲染
    733.图像渲染点击上方,跳转至leetcode题目描述有一幅以 mxn 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数sr, sc和newColor。你应该从像素 image[sr][sc] 开始对图像进行上色填充。为了完成上色工作,从......
  • [Leetcode] 0709. 转换成小写字母
    709.转换成小写字母点击上方跳转至Leetcode题目描述给你一个字符串s,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。 示例1:输入:s="Hello"输出:"hello"示例2:输入:s="here"输出:"here"示例3:输入:s="LOVELY"输出:"lovely" 提示:1<=s.l......
  • 离线安装binlog2sql恢复误删除数据
    下载离线包先在一台能上网的机器下载好离线包gitclonehttps://github.com/danfengcao/binlog2sql.gitpip3download-rrequirements.txt./将依赖包下载到./目录因为是mysql8.0还需要安装PyMySQL和mysql-replicationpip3downloadPyMySQL==0.9.3./pip3downloadmysq......
  • [Leetcode] 0717. 1 比特与 2 比特字符
    717.1比特与2比特字符点击上方,跳转至leetcode题目描述有两种特殊字符:第一种字符可以用一比特 0表示第二种字符可以用两比特(10 或 11)表示给你一个以0结尾的二进制数组 bits ,如果最后一个字符必须是一个一比特字符,则返回true。 示例 1:输入:bits=[1,......
  • [Leetcode] 0706. 设计哈希映射
    706.设计哈希映射点击跳转至leetcode题目描述不使用任何内建的哈希表库设计一个哈希映射(HashMap)。实现MyHashMap类:MyHashMap()用空映射初始化对象voidput(intkey,intvalue)向HashMap插入一个键值对(key,value)。如果key已经存在于映射中,则更新其对应的值v......
  • [LeetCode] 2090. K Radius Subarray Averages
    Youaregivena 0-indexed array nums of n integers,andaninteger k.The k-radiusaverage forasubarrayof nums centered atsomeindex i withthe radius k istheaverageof all elementsin nums betweentheindices i-k and i+k (i......
  • 每日一题力扣 1262 https://leetcode.cn/problems/greatest-sum-divisible-by-three/
    、 题解这道题目核心就算是要知道如果x%3=2的话,应该要去拿%3=1的数字,这样子才能满足%3=0贪心sum不够%3的时候,就减去余数为1的或者余数为2的需要注意两个余数为1会变成余数为2的,所以可能减去2个余数为1核心代码如下publicintmaxSumDivThreeOther(int[]nums){​  ......
  • LeetCode 周赛 350(2023/06/18)01 背包变型题
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和[BaguTreePro]知识星球提问。往期回顾:LeetCode单周赛第348场·数位DP模版学会了吗?T1.总行驶距离(Easy)标签:模拟T2.找出分区值(Medium)标签:排序T3.特别的排列(Medium)标签:图、状态压缩、......
  • Leetcode Hot 100 & 239. Sliding Window Maximum
    参考资料:Python文档heapq部分考点:子串&[题干]1Input:nums=[1,3,-1,-3,5,3,6,7],k=32Output:[3,3,5,5,6,7]3Explanation:4WindowpositionMax5--------------------6[13-1]-353673......
  • 图解LeetCode——437. 路径总和 III
    一、题目给定一个二叉树的根节点root ,和一个整数targetSum,求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。二、示例2.1>示例1:【输入】root=[10,5,-3,3,2,null......