1.求1+2+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
思路：利用递归和布尔运算符，当n>0时，执行递归操作。
class Solution {
public:
int Sum_Solution(int n) {
int sum=n;
bool t=(n>0)&&(sum+=Sum_Solution(n-1));
return sum;
}
};2.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
class Solution {
public:
int Add(int num1, int num2)
{ /*
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，
得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得
到1010，(101&111)<<1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果 */
int sum,carry;
do
{
sum=num1^num2;
carry=(num1&num2)<<1;//进位
num1=sum;
num2=carry;
}
while(num2!=0);//进位为0则是结束条件
return num1;
}
};3.实现字符串转整数函数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
思路：从头开始遍历，如果前面是空格，就继续遍历，出现第一个加号或减号，记录一个flag标志，接下来，如果遇到非数字字符，直接返回0，最后要进行一下得到整数是否越界的判断。
class Solution {
public:
int StrToInt(string str) {
int len=str.length();
if(len==0) return 0;//空字符串
if(str=="-2147483649"||str=="2147483648") return 0;//两个特殊情况
int i=0;
while(str[i]==' ')
i++;
int flag=1;
int num=0;
if(str[i]=='+') i++;
if(str[i]=='-')
{
i++;
flag=-1;
}//开始的第一个非空格字符是正负号的情况
while(str[i]!='\0')
{
if(str[i]>='0'&&str[i]<='9')
num=num*10+(str[i]-'0');
else
return 0;//出现非法字符，直接返回0
i++;
}
if(((flag>0)&&(num>0x7FFFFFFF))||((flag<0)&&(num>0x80000000)))
return 0;//大于最大整数或小于最小负数
return num*flag;
}
};4.数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路:利用哈希表。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(numbers==NULL||length==0) return 0;
int res[255]={0};
for(int i=0;i<length;i++)
{
res[numbers[i]]++;
}
int count=0;
for(int i=0;i<length;i++)
{
if(res[numbers[i]]>1)
{
duplication[count++]=numbers[i];
//break;
return true;
}
}
return false;
}
};5.构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=（A[0] * A[1] ... A[i-1] * A[i+1]...A[n-1]）。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
思路：画一个矩阵图，可以发现1在左对角线上，先计算左面部分，可以看出 B[i]=B[i-1] * A[i-1]，然后计算右面部分，temp * =A[i+1];B[i] * =temp;
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int len=A.size();
vector<int> B(len,1);
for(int i=1;i<len;i++)
{
B[i]=B[i-1]*A[i-1];//左面部分
}
int temp=1;
for(int i=len-2;i>=0;i--)
{
temp*=A[i+1];
B[i]*=temp;//右面部分
}
return B;
}
};6.正则表达式匹配
class Solution {
public:
bool match(char* str, char* pattern)
{
if (*str == '\0' && *pattern == '\0')
return true;//若都为空，匹配
if (*str != '\0' && *pattern == '\0')
return false;//第一个非空第二个空，不匹配
//if the next character in pattern is not '*'
if (*(pattern+1) != '*')
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str+1, pattern+1);//直接匹配，如果二者相等或str不为空，pattern为.则成功
else
return false;//不成功直接返回
}
//if the next character is '*'
else
{
if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str, pattern+2) || match(str+1, pattern);//当*匹配1个或多个字符，aaa与aa*aa aaa与a*
else
return match(str, pattern+2);//当*匹配0个字符时
}
}
};
京公网安备 11010502036488号