编辑

【枚举】012 s1用s2表示

2019-11-16 2019-11-16 56 2 ---【暴力破解】 Hoji

一、题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成,返回true;否则返回false

注意:你可以假设两个字符串均只含有小写字母

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

二、题解

题目设置的很简单,不计较顺序,不掺和大写字母.

步骤:

  • 1、定义一个大小为26的用于记录每个字符出现次数的字符数组count
  • 2、第一遍for循环先记录已知字符串的每一种字符出现的次数,第二遍for循环减去对应的出现次数,如果count[i]出现负数,那么return false

(1)字符减法

public boolean canConstruct(String ransomNote, String magazine) {
  int[] count = new int[26];
  for (int i = 0; i < magazine.length(); i++) {
    count[magazine.charAt(i) - 'a']++;
  }
  for (int i = 0; i < ransomNote.length(); i++) {
    if((--count[ransomNote.charAt(i) - 'a']) < 0)  return false;
  }
  return true;
}

复杂度分析

时间复杂度:O(n)
空间复杂度:一个count数组的大小


Hoji的CSDN(在这里随意任性地创作,一首诗、一幅画、一篇文章.... 在这里你可以get到但不仅限算法、Spring, SpringBoot等后端技术、MySql,Oracle数据库探索....,其中更不乏各种框架教程、学习方法..)
博客地址:https://blog.csdn.net/qq_43539599

倘若小文于你有益,欢迎
  • 如果您的提问博主没能及时回复,通过分享文章获得援助,何尝不是一种查缺补漏的好做法
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY版权协议
  • 文章转载:请在文末添加原文章地址,这也是尊重他人劳动成果的一点体现,谢谢您的配合!
  • 评论信息 (注:评论收到回复后,会以邮箱的方式提醒您;您的邮箱不会显示到页面中)

    验证码信息 看不清?点击图片进行切换!
    精彩随处可见 更多精彩内容
    作者: 浏览 61 评论 1 赞 1 2020-01-15
    作者: 浏览 62 评论 1 赞 1 2019-11-29
    作者: 浏览 83 评论 1 赞 1 2019-11-29
    作者: 浏览 54 评论 1 赞 1 2019-11-29
    作者: 浏览 52 评论 1 赞 1 2019-11-29
    目录