经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
力扣刷题笔记 (1) - HM-7
来源:cnblogs  作者:HM-7  时间:2021/12/31 9:04:15  对本文有异议

2021-12-30 

LeetCode T846

希望自己可以坚持写博客的习惯??

题目描述:

  Alice 手中有一把牌,她想要重新排列这些牌,分成若干组,使每一组的牌数都是 groupSize ,并且由 groupSize连续的牌组成。

  给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌,和一个整数 groupSize。如果她可能重新排列这些牌,返回 true否则,返回 false

Input:

 

  1. hand = [1,2,3,6,2,3,4,7,8], groupSize = 3

 

Output:

  1. true

 

初读此题,想都没想直接暴力求解 暴力固然简单,但只适用于不重复数字且不相隔的情况,若遇到 [1,1,2,2,3,3] 则出错。

  1. class Solution {
  2. public:
  3. bool isNStraightHand(vector<int>& hand, int groupSize) {
  4. if(hand.size() % groupSize != 0) return false;
  5. sort(hand.begin(), hand.end());
  6. bool ans = true;
  7. for(int j = 0; j < hand.size(); j += groupSize) {
  8. ans = pd(j, groupSize, hand);
  9. }//划分多组进入判断
  10. return ans;
  11. }
  12. bool pd(int start, int groupSize, vector<int>& hand) {
  13. for(int i = start + 1; i < start + groupSize; i++) {
  14. if(hand[i - 1] + 1 != hand[i]) {
  15. return false;
  16. }//逐个判断是否符合情况
  17. }
  18. return true;
  19. }
  20. };

为了解决这种问题,便去想第二种:用取余判断,貌似精简,但遇到 [8,10,12] 这种隔数的情况会误判。

  1. class Solution {
  2. public:
  3. bool isNStraightHand(vector<int>& hand, int groupSize) {
  4. if(hand.size() % groupSize != 0) return false;
  5. sort(hand.begin(), hand.end());
  6. vector<int> res(groupSize);
  7. for(int i: hand) {
  8. res[i % groupSize]++;
  9. }//将重复部分存入新数组
  10. for(int i = 1; i < groupSize; i++) {
  11. if(res[i - 1] != res[i])
  12. return false;
  13. }//若连续则各位置牌数应该相等
  14. return true;
  15. }
  16. };

最后相当于两种结合求解,采用unordered_map这一高科技??

  1. class Solution {
  2. public:
  3. bool isNStraightHand(vector<int>& hand, int groupSize) {
  4. if(hand.size() % groupSize != 0) return false;
  5. if(groupSize == 1) return true;
  6. unordered_map<int, int> res;
  7. sort(hand.begin(), hand.end());
  8. for(int i: hand) {
  9. res[i]++;
  10. }//在每个Key值内存入该Key出现的次数
  11. for(int t: hand) {
  12. if(res[t] == 0) continue;
  13. for(int i = 0; i < groupSize; i++) {
  14. if(res[t + i]-- <= 0)
  15. return false;
  16. }//进行判断统计出次数
  17. }
  18. return true;
  19. }
  20. };

 

原文链接:http://www.cnblogs.com/LWHCoding/p/15747941.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号