首页 > 代码库 > Nim Game，Reverse String，Sum of Two Integers
Nim Game，Reverse String，Sum of Two Integers
下面是今天写的几道题：
292. Nim Game
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
1 bool canWinNim(int n) {2 if ( 0<n && n<4 ) return true;3 else if(n==4) return false;4 else return n%4 != 0;5 }
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
1.C++ code Runtime：12ms
1 class Solution {2 public:3 string reverseString(string s) {4 reverse(s.begin(),s.end());5 return s;6 }7 };
2.C code Runtime：4ms
1 char* reverseString(char* s) { 2 int len = strlen(s); 3 for(int i=0;i<len/2;i++) 4 { 5 char tempc = s[i]; 6 s[i] = s[len-1-i]; 7 s[len-1-i] = tempc; 8 } 9 return s;10 }
371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -
这道题自己虽然知道要用位运算但是一开始没想出来，下边的方法借鉴网上，原文地址http://www.cnblogs.com/la0bei/p/5659829.html
1 int main() 2 { 3 int a,b,c; 4 cin >> a >> b; 5 while(b) 6 { 7 c = a^b; 8 b = (a&b)<<1; 9 a = c;10 }11 cout << a << endl;12 system("pause");13 }
--------------------------------------------------------------------------------------------------------------------------------------------------------
下边这个方法按道理是不符合题目的，题中要求不使用+-符号，但是这竟然在LeetCode上ac了，我这个代码需要小心边界即负数最小值。
1 //整数转换为二进制数组 2 int intToBit(int *str,long long num) 3 { 4 int i=0; 5 do 6 { 7 str[i++] = num%2; 8 num = num/2; 9 }while(num>0); 10 11 return i; 12 } 13 //负数的话二进制取反+1 14 void reverdBitAdd1(int *str,int *num) 15 { 16 //取反 17 int temp = *num; 18 while(temp--) str[temp] = ( (str[temp] == 0)? 1 : 0 ); 19 20 //负数需要反转+1; 21 int sum = 1; 22 for(int i=0;i<*num;i++) 23 { 24 sum += str[i]; 25 str[i] = sum%2; 26 sum = sum/2; 27 } 28 str[*num] = 1; 29 (*num)++; 30 } 31 32 //两个二进制相加 33 int bitAdd(int *sumbit,int*a,int sizea,int*b,int sizeb) 34 { 35 int sum = 0; 36 int num = (sizea>sizeb?sizea:sizeb); 37 for (int i=0;i<num;i++) 38 { 39 sum +=(a[i]+b[i]); 40 sumbit[i] = sum%2; 41 sum /=2; 42 } 43 if (sum ==1) sumbit[num++] = 1; 44 return num; 45 } 46 47 //将二进制转换为十进制 48 int sumBit(int *bitNum, int n) 49 { 50 int sum = 0; 51 int bit2 = 1; 52 for(int i=0;i<n;i++) 53 { 54 sum += bitNum[i]*bit2; 55 bit2 *=2; 56 } 57 return sum; 58 } 59 60 int getSum(int a, int b) { 61 //定义存储结果的sum，标识a，b的符号的falg 62 int sum = 0,flaga = 0,flagb = 0; 63 //定义存储ab以及相加后的二进制数组 64 int bita[33] = {0}; 65 int bitb[33] = {0}; 66 int sumbit[34] = {0}; 67 //考虑a，b可能为负数最小值 68 long long la = a; 69 long long lb = b; 70 //先按无符号位处理 71 if(la<0) 72 { 73 la = -la; 74 flaga = 1; 75 } 76 77 if(lb<0) 78 { 79 lb = -lb; 80 flagb = 1; 81 } 82 83 int sizea = intToBit(bita,la); 84 int sizeb = intToBit(bitb,lb); 85 86 //如果符号相同直接相加 87 if(flaga == flagb) 88 { 89 int num = bitAdd(sumbit,bita,sizea,bitb,sizeb); 90 sum = sumBit(sumbit,num); 91 if(flaga == 1) sum = -sum; 92 } 93 //如果a是负数 94 else if(flaga == 1) 95 { 96 //先将a反转+1，此时a多了个符号位 97 reverdBitAdd1(bita,&sizea); 98 while(sizea<sizeb)//补齐负数位 99 {100 bita[sizea++] = 1;101 }102 int num = bitAdd(sumbit,bita,sizea,bitb,sizeb);103 if(sizeb>sizea-1) sum = sumBit(sumbit,num-1);//正数二进制位多104 else if(sizea-1>sizeb)//负数符号位多105 {106 num--;107 reverdBitAdd1(sumbit,&num);108 sum = -sumBit(sumbit,num-1);109 }110 else if(sizea-1 == sizeb)//不包括符号位两个位数一样多111 {112 if(sumbit[num] == 1) sum = -sumBit(sumbit,num-1);113 else sum = sumBit(sumbit,num-1);114 }115 }116 else if(flagb == 1)117 {118 reverdBitAdd1(bitb,&sizeb);119 while(sizeb<sizea)120 {121 bitb[sizeb++] = 1;122 }123 int num = bitAdd(sumbit,bita,sizea,bitb,sizeb);124 if(sizea>sizeb-1) sum = sumBit(sumbit,num-1);125 else if(sizeb-1>sizea)126 {127 num--;128 reverdBitAdd1(sumbit,&num);129 sum = -sumBit(sumbit,num-1);130 }131 else if(sizeb-1 == sizea)132 {133 if(sumbit[num] == 1) sum = -sumBit(sumbit,num-1);134 else sum = sumBit(sumbit,num-1);135 }136 }137 return sum;138 }
Nim Game，Reverse String，Sum of Two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。