🏆一、在LR字符串中交换相邻字符
在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
今日份的每日一题，题目要求很简单： 一个"LX"替换一个"XL"；"XR"替换一个"RX"使得两个字符串相一致。
如果是这样的思路：遇到R，判断相邻字符是否为X，如果是X，就交换两个字符；遇到X，判断相邻字符是否为R，如果是R就交换两个字符；最终就是所有的XL被我们替换成LX;所有的XR被我们替换成RX。这种思路显然是行不通的，连测试用例都跑不过，因为：
测试用例就出现了R X L这样的相邻字符，你是替换RX,还是XL呢？单纯的替换得不到答案，所以我们肯定得对照目标字符串进行交换。
🖊双指针解法：
我们肯定要使得start字符串去和end一致，如果做不到就返回false，如果成功变换使得匹配成功，就返回true。怎么使得start字符串和end字符串一致呢？我们设pos指针指向start，pt指针指向end。
1、寻找：如果pos和pt指向的字符相一致，就都++。如果不一致，pos指针不断++，直到pos指针指向的字符和pt指向的字符相一致，如果pos一直++到指向了末尾（'\0'）,都没有找到和pt指向的字符一致，那么start字符串肯定不能和end字符串一致，返回false。
2、当pos指向的字符和pt指向的字符一致，pos指向的字符为‘L’并且pos-1指向的字符为'X'或者pos指向的字符为‘X’并且pos-1指向的字符为‘R’时（交换条件），就交换，pos--。如果pos能减到pos==pt并且start[pos]==end[pt]就继续，直到pt走到end末尾。
3、不能找到pos和pt指向字符一样返回false；找到后，不满足交换条件的返回false；pos不能回到pt的，返回false；返回后start[pos]不等于end[pt]的返回false。
void Swap(char* a,char* b) { char tmp=*a; *a=*b; *b=tmp; } bool canTransform(char * start, char * end) { int pos=0; int pt=0; int m=strlen(start); int n=strlen(end); while(end[pt]!='\0') { if(start[pos]!=end[pt]) { while(start[pos]!=end[pt]) { pos++; //找不到 if(start[pos]=='\0') { return false; } } while(pos!=pt) { if((start[pos]=='L'&&start[pos-1]=='X') ||(start[pos]=='X'&&start[pos-1]=='R'))//交换的前提 { Swap(&start[pos],&start[pos-1]); pos--; } else { return false; } } //pos==pt if(start[pos]!=end[pt]) { return false; } } pos++; pt++; } return true; }
🏆二、数值的整数次方
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
这道题目，说实话，菜鸟都会写：
double myPow(double x, int n) { double ret=1; int flag=1; if(n<0) { flag=0; n=-n; } while(n--) { ret*=x; } if(flag==0) { ret=1.0/ret; } return ret; }
然后呢？超时┭┮﹏┭┮：
这个测试用例还是挺不当人的，说明我们这个算法不够优化。
🖊幂指递归
如果我们要计算一个数的32次方，如果我知道它的16次方，那么我们再平方一次就能得到32次方，而16次方也有同样的思路，如果我们直到8次方，那么8次方再平方一次就得到了16次方。然后8次方也是如此，所以我们求32次方只需要5次乘法。
我们可以用如下公式求次方：
bool isinvalidinput=false; double myPow(double x, int n) { if(x==0.0&&n<0) { isinvalidinput=false; return 0.0; } if(n==0) return 1; if(n==-1) return 1.0/x; if(n==1) return x; double ans=1; if(n&1==1)//乘除转换为位操作符 { //奇数 ans=myPow(x,(n-1)>>1); ans*=ans; ans*=x; } else { //偶数 ans=myPow(x,n>>1); ans*=ans; } return ans; //对于负偶数，由于最后一定会不断右移1位等于-1 ，所以一定会返回它的倒数，然后倒数不断平方 //对于负奇数，-1转化为负偶数，然后最后乘以指数 }
1、这里所做的第一个优化是，用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率高很多。
2、这里还有一个bool值isinvalidinput，这个在这道oj题里没有什么作用，但是在IO题里面非常有必要，因为我们知道0的负次幂是没有意义的，而让它返回0.0；如果计算0的正次幂也是返回0.0，我们知道这两个虽然都返回0.0，但是意义截然不同，前一个表示无意义返回0.0，后一个表示值计算为0.0，这一个bool值用于标识。
3、我们这里把负数和正数统一处理了。对于负偶数，由于最后一定会不断右移1位等于-1 ，所以一定会返回它的倒数，然后倒数不断平方。对于负奇数，减一转化为负偶数，然后和负偶数一样的操作，只不过我们多乘了一个倒数，所以最后乘以指数。
