41.题目描述
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
class Solution {
public:
int Sum_Solution(int n) {
char a[n][n+];
return sizeof(a)>>;
}
};42.题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
class Solution {
public:
int Add(int num1, int num2)
{
if(num1 == )
return num2;
if(num2 == ){
return num1;
}
return Add(num1^num2,(num1&num2)<<);
}
};43.题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
class Solution {
public:
int StrToInt(string str) {
if(str.length()==){
return ;
}
int symbol = ;
int val = ;
if(str[]=='+'){
symbol=;
}else if(str[]=='-'){
symbol=-;
}else if(str[]-''>= && str[]-''<){
val = str[]-'';
symbol=;
}
for(int i=;i<str.length();i++){
if(str[i]-''> || str[i]-''<){
return ;
}
val = val* + str[i]-'';
}
return val*symbol;
}
};44.题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
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) {
map<int,int>a;
for(int i=;i<length;i++){
a[numbers[i]]++;
}
for(auto it=a.begin();it!=a.end();it++){
if(it->second>){
*duplication = it->first;
return true;
}
}
return false;
}
};45.题目描述
给定一个数组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]。不能使用除法。
思路：
利用两个辅助数组，第一个数组L依次保存A数组从0-length-1的乘积，第二个数组h依次保存从length-1到0的乘积，然后每一个要求的B[i]=L[i-1]*H[i+1].//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
//从左到右算 B[i]=A[0]*A[1]*...*A[i-1]
//从右到左算B[i]*=A[i+1]*...*A[n-1]
class Solution {
public:
vector<int> multiply(const vector<int>& A) { int n=A.size();
vector<int> b(n);
int ret=;
for(int i=;i<n;ret*=A[i++]){
b[i]=ret;
}
ret=;
for(int i=n-;i>=;ret*=A[i--]){
b[i]*=ret;
}
return b;
}
};
46.题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
class Solution {
public:
bool match(char* str, char* pattern)
{
if (*str == '\0' && *pattern == '\0')
return true;
if (*(pattern + ) == '*')
{
// 如果已经到结尾了，把后面的*都匹配掉
if (*str == '\0')
return match(str, pattern + );
if ((*pattern == *str || *pattern == '.'))
{
// 尝试匹配一个，模式串往后移动
// 尝试匹配一个，模式串不往后移
// 一个都不匹配，模式串往后移动
// 3种当中有一种成功就可以了
return match(str + , pattern + ) || match(str + , pattern) || match(str, pattern + );
}
else
{
// 因为是*所以不匹配也没事，直接跳到下一个
return match(str, pattern + );
}
}
else if (*str == '\0') // 如果没有*了，但是模式串还没匹配完，那么失败
return false;
else if (*pattern == '.' || *pattern == *str) // .或者模式串字符本来就匹配
{
return match(str + , pattern + );
}
return false;
}
};47.题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
class Solution {
public:
bool isNumeric(char* str) {
// 标记符号、小数点、e是否出现过
bool sign = false, decimal = false, hasE = false;
for (int i = ; i < strlen(str); i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == strlen(str)-) return false; // e后面一定要接数字
if (hasE) return false; // 不能同时存在两个e
hasE = true;
} else if (str[i] == '+' || str[i] == '-') {
// 第二次出现+-符号，则必须紧接在e之后
if (sign && str[i-] != 'e' && str[i-] != 'E') return false;
// 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
if (!sign && i > && str[i-] != 'e' && str[i-] != 'E') return false;
sign = true;
} else if (str[i] == '.') {
// e后面不能接小数点，小数点不能出现两次
if (hasE || decimal) return false;
decimal = true;
} else if (str[i] < '' || str[i] > '') // 不合法字符
return false;
}
return true;
}
};48.题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
class Solution
{
public:
//Insert one char from stringstream
string str;
void Insert(char ch)
{
str += ch;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
vector<char> a;
map<char, int>b;
for (int i = ; i<str.size() ; i++){
a.push_back(str[i]);
b[str[i]]++;
}
for (int i = ; i<a.size();i++){
if (b[a[i]]>){
continue;
}
else if (b[a[i]] == ){
return a[i];
}
}
return '#';
} };
49.题目描述
一个链表中包含环，请找出该链表的环的入口结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
//if(pHead == NULL)return NULL;
ListNode* p = pHead;
map<ListNode*,int>a; while(p){
if(++a[p] == )
{
break;
}
p = p->next;
} return p;
}
};
50.题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL)
return pHead; /*---------先为链表创建一个头结点---------*/ int firstNumber = pHead->val; //假设我的头结点数值为-1
int myFirst = -; //万一链表的头结点也为-1，那么我就改成-2
if (myFirst == firstNumber)
{ myFirst = -;
}
ListNode *head = new ListNode(myFirst);
head->next = NULL;
head->next = pHead; ListNode *p = head;
ListNode *q = head->next; while (q)
{
while (q->next && (q->next->val == q->val))
{
q = q->next;
}
if (p->next != q)
{ q = q->next;
p->next = q;
}
else
{
p = q;
q = q->next;
}
} //返回的时候，注意去掉头结点（自己创建的辅助节点）
return head->next; } };
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL)
return pHead;
int val;
if (pHead->val != -){
val = pHead->val-;
}
else{
val = -;
}
ListNode* node = pHead;
ListNode* fp = node->next;
ListNode* pre = NULL;
ListNode* head = NULL;
while (fp)
{
if (node->val != fp->val&&val != node->val){ //如果相邻两个值不等，且也不是前一个相等的和当前的值相等。
if (pre == NULL){
pre = node;
head = pre;
}
else{
pre->next = node;
pre = pre->next;
}
}
else{
val = node->val;
}
node = node->next;
fp = node->next;
}//end while
//处理最后一个节点
if (node -> val == val){
if (pre)
pre->next = NULL;
}
else{
if (pre)
pre->next = node;
else{
pre = node;
head = pre;
}
}
return head;
}
};