【POJ】2159

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_LENGTH = 100;

char str1[MAX_LENGTH], str2[MAX_LENGTH];
int len;

inline int getLen(const char* str){
    int head = 0, tail = MAX_LENGTH;
    while(head <= tail){
        int mid = (head + tail) >> 1;
        if('A' <= *(str + mid) && *(str + mid) <='Z')head = mid + 1;
        else tail = mid - 1;
        if(*(str + mid) == '\0')tail = mid;
        if(head >= tail && *(str + mid) == '\0')return mid;
    }
    return head;
}

inline bool mapping(){
    int table1[26], table2[26];
    memset(table1, 0, sizeof(table1));
    memset(table2, 0, sizeof(table2));
    for (int i = 0; i < len; ++i){
        table1[*(str1 + i) - 'A']++;
    }
    for (int i = 0; i < len; ++i){
        table2[*(str2 + i) - 'A']++;
    }
    sort(table1, table1 + 26);
    sort(table2, table2 + 26);
    for (int i = 0; i < 26; ++i){
        if(table1[i] != table2[i])return false;
    }
    return true;
}

int main(int argc, char const *argv[]){
    scanf("%s%s", str1, str2);
    len = getLen(str1);
    if(len != getLen(str2)){
        printf("NO\n");
        return 0;
    }
    if(mapping()){printf("YES\n");return 0;}
    printf("NO\n");
    return 0;
}

Review

  • 水题。之所以卡了有点久,是因为题意理解错了。

    • 题意:检测一个字符串(仅包含大写字母长度不超过100)能否通过凯撒+乱序的方式变换为另一个串
    • 所以只要统计26个字母的频数就可以了,甚至不需要考虑凯撒
    • 坑:
      1. 首先看两串长度是否一致(小坑)
      2. 凯撒的位移不是统一的。比如说,有一个A凯撒后得到B,不意味着其他字母也是往后位移一位。(!important 就这搞错了)
  • 据说cstring中的strlen()是O(n)的,于是用二分写了个getLen(),不过需要提前指定MAX_LENGTH

  • 传字符串做实参:const char* str,习惯加个const。读取str[1]时写作*(str + 1)即可。

  • memset只能赋值0或-1。

  • WA的代码里写了做一次凯撒的代码,贴下:

    • inline void caesar(char* str){
          for (int i = 0; i < len; ++i){
              *(str + i) += 1;
              if(*(str + i) == 'Z' + 1)*(str + i) = 'A';
          }
      }
      
  • C++中数组名可以作为数组的首地址使用,所以可以用sort(table1, table1 + 26);

  • sort()默认升序。给一个自定义cmp()来记一下。

    • // 降序
      inline bool cmp(const int a, const int b){
          return a > b;
      }
      
上一篇:iview报错[Vue warn]: Error in render: "TypeError: ctx.injections.tableRoot.$scopedSlots[ctx.props


下一篇:888. 求组合数 IV