LeetCode(力扣)算法题

找出字符串的可除整数组

题目描述

��度：中等

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div  是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

  返回 word 的可整除数组。

   

  示例 1：

  输入：word = "998244353", m = 3
  输出：[1,1,0,0,0,1,1,0,0]
  解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。
  

  示例 2：

  输入：word = "1010", m = 10
  输出：[0,1,0,1]
  解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

  解题思路

  根据题意可知：

          我们需要进行 word.length() 次（字符串长度）的整除计算，根据每一次计算后的结果，生成 word.length() 个 0 或 1 作为输出结果；

          每次遍历的整除计算表示为：

                  (a * 10 + (word.charAt(i) - '0')) % m

          其中 a 的初始值为 0 ，word.charAt(i) - '0' 的写法是为了将 word.charAt(i) 的字符转为对应的ASCII码值，在这个题中 word.charAt(i) 的字符是数字，那么 word.charAt(i) - '0' 得到的就是对应的数字；

          此时已经有了一个大概的框架：

  class Solution {
      public int[] divisibilityArray(String word, int m) {
          int n = word.length();
          long temp = 0;
          for(int i = 0;i  
          这时候我们只差一个返回的结果，那么加入一个数组，并且长度等于 word.length()。然后再将遍历过程中的计算结果 temp 进行判断（是否被整除），根据判断结果将 0 或 1 存入结果数组中。
   
  class Solution {
      public int[] divisibilityArray(String word, int m) {
          int n = word.length();
          int[] res = new int[n];
          long temp = 0;
          for(int i = 0;i  
  代码改动
   
          在第一遍写代码的时候，犯了一些错误，当时的代码如下：
   
  class Solution {
      public int[] divisibilityArray(String word, int m) {
          int[] res = new int[word.length()];
          int temp = 0;
          for(int i = 0;i  
  错误一：
   
          temp 使用的是 int 数据类型，这个看起来是没有任何问题的，但是在面临一些 word 较长的测试用例时，数据范围是不够的，所以说需要改为 long。
   
  优化一：
   
          上述代码读了两次 word.length() 。整体代码运行时长为 9 ms，如果将 word.length() 的值存在内存中在需要时进行调用，可优化代码运行时长，优化后的代码运行时长为 7 ms。
   
  优化二：
   
          将 if 语句换为条件表达式，这一步优化的时候只是为了简化代码，在这个例子中好像没有起到别的优化作用。