设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 859_亲密字符串
返回列表 发新帖
查看: 1998|回复: 3

[技术交流] 859_亲密字符串

[复制链接]
风扫地
发表于 2019-6-27 10:20:15 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
  1. /*
  2. 给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，就返回 true ；否则返回 false 。



  6. 示例 1：

  8. 输入： A = "ab", B = "ba"
  9. 输出： true

  11. 示例 2：

  13. 输入： A = "ab", B = "ab"
  14. 输出： false

  16. 示例 3:

  18. 输入： A = "aa", B = "aa"
  19. 输出： true

  21. 示例 4：

  23. 输入： A = "aaaaaaabc", B = "aaaaaaacb"
  24. 输出： true

  26. 示例 5：

  28. 输入： A = "", B = "aa"
  29. 输出： false

  31. */
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

风扫地
 楼主| 发表于 2019-6-27 10:20:52 | 显示全部楼层
  1. void swap(char* a, char* b)
  2. {
  3.     char c = *a;
  4.     *a = *b;
  5.     *b = c;
  6. }

  8. bool compareTwoStr(char* A , char* B , int size)
  9. {
  10.     int i = 0;
  11.     bool ret_val = true;
  12.     for(i = 0; i < size;i++)
  13.     {
  14.         if(A[i]!=B[i])
  15.         {
  16.             ret_val = false;
  17.             break;
  18.         }
  19.     }
  20.    
  21.     return ret_val;
  22. }

  24. /*方法1:逐一比较交换情况*/
  25. bool buddyStrings(char* A,char*B)
  26. {
  27.    
  28.     bool ret_val        = false;
  29.     int len_A           = strlen(A);
  30.     int len_B           = strlen(B);
  31.     int i               = 0;
  32.     int j               = 0;
  33.     int no_match_count  = 0;
  34.     int no_match_idx[2] = {0,};
  35.     do
  36.     {
  37.         if(   ( len_A != len_B  )
  38.             ||( len_A < 2       )
  39.             ||( len_B < 2       )
  40.         )
  41.         {
  42.             ret_val = false;
  43.             break;
  44.         }
  45.         
  46.         for(i = 0; i < len_A;i++)
  47.         {
  48.             if(A[i]!=B[i])
  49.             {
  50.                 if(no_match_count<2)
  51.                 {
  52.                     no_match_idx[no_match_count] = i;
  53.                     no_match_count++;
  54.                 }
  55.                 else
  56.                 {
  57.                     no_match_count++;
  58.                     break;
  59.                 }
  60.             }
  61.         }
  62.         
  63.         
  64.         if(no_match_count==2)
  65.         {
  66.             swap(&A[no_match_idx[0]],&A[no_match_idx[1]]);
  67.             ret_val = compareTwoStr(A,B,len_A);
  68.             break;
  69.         }
  70.         else if ((no_match_count==1)||(no_match_count==3))
  71.         {
  72.             ret_val = false;
  73.             break;
  74.         }
  75.         else /* no_match_count == 0 */
  76.         { /* 逐一遍历交换情况,看是否有满足的情况*/
  77.             for(i = 0; i < len_A;i++)
  78.             {
  79.                 for(j = len_B-1; j > i ; j--)
  80.                 {
  81.                     swap(&A[i],&A[j]);
  82.                     ret_val = compareTwoStr(A,B,len_A);
  83.                     if(ret_val)
  84.                     {
  85.                         break;
  86.                     }
  87.                     swap(&A[i],&A[j]);
  88.                 }
  89.                 if(ret_val)
  90.                 {
  91.                     break;
  92.                 }
  93.             }
  94.         }
  95.     }while(0);
  96.     return ret_val;
  97. }
复制代码


  1. /*
  2. 方法1:
  3. 执行用时 :12 ms, 在所有 C 提交中击败了23.33%的用户
  4. 内存消耗 :7 MB, 在所有 C 提交中击败了39.39%的用户
  5. */
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

风扫地
 楼主| 发表于 2019-6-27 10:21:42 | 显示全部楼层
  1. void swap(char* a, char* b)
  2. {
  3.     char c = *a;
  4.     *a = *b;
  5.     *b = c;
  6. }

  8. bool compareTwoStr(char* A , char* B , int size)
  9. {
  10.     int i = 0;
  11.     bool ret_val = true;
  12.     for(i = 0; i < size;i++)
  13.     {
  14.         if(A[i]!=B[i])
  15.         {
  16.             ret_val = false;
  17.             break;
  18.         }
  19.     }
  20.    
  21.     return ret_val;
  22. }
复制代码

  1. /*方法2:检测有无重复元素*/
  2. bool buddyStrings(char* A,char*B)
  3. {
  4.    
  5.     bool ret_val        = false;
  6.     int len_A           = strlen(A);
  7.     int len_B           = strlen(B);
  8.     int i               = 0;
  9.     int j               = 0;
  10.     int no_match_count  = 0;
  11.     int no_match_idx[2] = {0,};
  12.     do
  13.     {
  14.         if(   ( len_A != len_B  )
  15.             ||( len_A < 2       )
  16.             ||( len_B < 2       )
  17.         )
  18.         {
  19.             ret_val = false;
  20.             break;
  21.         }
  22.         
  23.         for(i = 0; i < len_A;i++)
  24.         {
  25.             if(A[i]!=B[i])
  26.             {
  27.                 if(no_match_count<2)
  28.                 {
  29.                     no_match_idx[no_match_count] = i;
  30.                     no_match_count++;
  31.                 }
  32.                 else
  33.                 {
  34.                     no_match_count++;
  35.                     break;
  36.                 }
  37.             }
  38.         }
  39.         
  40.         
  41.         if(no_match_count==2)
  42.         { // 这里仍可优化
  43.             swap(&A[no_match_idx[0]],&A[no_match_idx[1]]);
  44.             ret_val = compareTwoStr(A,B,len_A);
  45.             break;
  46.         }
  47.         else if ((no_match_count==1)||(no_match_count==3))
  48.         {
  49.             ret_val = false;
  50.             break;
  51.         }
  52.         else /* no_match_count == 0 */
  53.         { /* 其实只要检测有无重复元素即可*/
  54.             for(i = 0; i < len_A;i++)
  55.             {
  56.                 for(j = len_B-1; j > i ; j--)
  57.                 {
  58.                     ret_val = (A[i] == A[j]);
  59.                     if(ret_val)
  60.                     {
  61.                         break;
  62.                     }
  63.                 }
  64.                 if(ret_val)
  65.                 {
  66.                     break;
  67.                 }
  68.             }
  69.         }
  70.     }while(0);
  71.     return ret_val;
  72. }
复制代码


  1. /*
  2. 方法2:
  3. 执行用时 :0 ms, 在所有 C 提交中击败了100.00%的用户
  4. 内存消耗 :7 MB, 在所有 C 提交中击败了39.39%的用户
  5. */
复制代码

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

风扫地
 楼主| 发表于 2019-6-27 10:23:17 | 显示全部楼层
  1. /*方法3:直接判断对应字符是否相等*/
  2. bool buddyStrings(char* A,char*B)
  3. {
  4.    
  5.     bool ret_val        = false;
  6.     int len_A           = strlen(A);
  7.     int len_B           = strlen(B);
  8.     int i               = 0;
  9.     int j               = 0;
  10.     int no_match_count  = 0;
  11.     int no_match_idx[2] = {0,};
  12.     do
  13.     {
  14.         if(   ( len_A != len_B  )
  15.             ||( len_A < 2       )
  16.             ||( len_B < 2       )
  17.         )
  18.         {
  19.             ret_val = false;
  20.             break;
  21.         }
  22.         
  23.         for(i = 0; i < len_A;i++)
  24.         {
  25.             if(A[i]!=B[i])
  26.             {
  27.                 if(no_match_count<2)
  28.                 {
  29.                     no_match_idx[no_match_count] = i;
  30.                     no_match_count++;
  31.                 }
  32.                 else
  33.                 {
  34.                     no_match_count++;
  35.                     break;
  36.                 }
  37.             }
  38.         }
  39.         
  40.         if(no_match_count==2)
  41.         {
  42.             /* 只有两个不相等了*/
  43.             if( (A[no_match_idx[0]]==B[no_match_idx[1]])
  44.               &&(A[no_match_idx[1]]==B[no_match_idx[0]])
  45.             )
  46.             {
  47.                 ret_val = true;
  48.             }
  49.             else
  50.             {
  51.                 ret_val = false;
  52.             }
  53.             break;
  54.         }
  55.         else if (  (no_match_count==1)
  56.                  ||(no_match_count==3)
  57.         )
  58.         {
  59.             ret_val = false;
  60.             break;
  61.         }
  62.         else /* no_match_count == 0 */
  63.         { /* 其实只要检测有无重复元素即可*/
  64.             for(i = 0; i < len_A;i++)
  65.             {
  66.                 for(j = len_B-1; j > i ; j--)
  67.                 {
  68.                     ret_val = (A[i] == A[j]);
  69.                     if(ret_val)
  70.                     {
  71.                         break;
  72.                     }
  73.                 }
  74.                 if(ret_val)
  75.                 {
  76.                     break;
  77.                 }
  78.             }
  79.         }
  80.     }while(0);
  81.     return ret_val;
  82. }

复制代码

  1. /*
  2. 方法3:
  3. 执行用时 :4 ms, 在所有 C 提交中击败了91.67%的用户
  4. 内存消耗 :7 MB, 在所有 C 提交中击败了45.45%的用户
  5. */
复制代码


奇怪，明明方法3降低了时间复杂度,还不涉及交换，耗时居然增加了。。= = .
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-5-1 22:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表