제2 장 문자열 의 각종 작은 문제
#include <iostream>
using namespace std;
int CompareSting(string LongSting,string ShortSting)
{
for (int i=0; i<ShortString.length(); i++)
{
for (int j=0; j<LongString.length(); j++) //O(n*m)
{
if (LongString[i] == ShortString[j]) //
{
break;
}
}
if (j==LongString.length())
{
cout << "false" << endl;
return 0;
}
}
cout << "true" << endl;
return 1;
}
int main()
{
string LongString="ABCDEFGHLMNOPQRS";
string ShortString="DCGSRQPOM";
compare(LongString,ShortString);
return 0;
}사고방식 2: O (mlogm) + O (nlogn) + O (m + n) 의 정렬 방법두 문자열 의 정렬 은 O (m log m) + O (n log n) 차 작업 이 필요 하 며, 이후 선형 스 캔 은 O (m + n) 차 작업 이 필요 합 니 다.정렬 에 대해 서 는 일반적으로 빠 른 정렬 을 사용한다.정렬 된 코드 는 쓰 지 않 겠 습 니 다.그리고 찾 은 코드 를 볼 수 있 습 니 다.
#include <iostream>
#include <string>
using namespace std;
// ， O(m log m) + O(n log n)， O(m+n)，
// ：O(mlogm)+O(nlogn)+O(m+n)。
void compare(string str1,string str2)
{
int posOne = 0;
int posTwo = 0;
while (posTwo < str2.length() && posOne < str1.length())
{
while (str1[posOne] < str2[posTwo] && posOne < str1.length() - 1)
posOne++;
// str2 ， 。 str2 ， 。
if (str1[posOne] != str2[posTwo])
break;
//posOne++;
// ，str1[str1Pos] == str[str2Pos] ， str2Pos++,str1Pos 。
// helloword 。
posTwo++;
}
if (posTwo == str2.length())
cout << "true" << endl;
else
cout << "false" << endl;
}
int main()
{
string str1 = "ABCDEFGHLMNOPQRS";
string str2 = "DCGDSRQPOM";
quicksort(str1, 0, str1.length() - 1);
quicksort(str2, 0, str2.length() - 1); //
compare(str1, str2); //
return 0;
}사고방식 3:
O (m + n) 의 계수 정렬 방법
이 방안 은 상기 사고 에 비해 정렬 할 때 선형 시간의 계수 정렬 방법 으로 정렬 O (n + m), 선형 스 캔 O (n + m), 총 시간 복잡 도 는 O (n + m) + O (n + m) = O (n + m) 이다.
#include <iostream>
#include <string>
using namespace std;
// ，O（n+m）
void CounterSort(string str, string &help_str)
{
//
int help[26] = {0};
// help[index] index + 'A'
for (int i = 0; i < str.length(); i++)
{
int index = str[i] - 'A';
help[index]++;
}
//
for (int j = 1; j < 26; j++)
help[j] += help[j-1];
//
for (int k = str.length() - 1; k >= 0; k--)
{
int index = str[k] - 'A';
int pos = help[index] - 1;
help_str[pos] = str[k];
help[index]--;
}
}
// O（n+m）
void Compare(string long_str,string short_str)
{
int pos_long = 0;
int pos_short = 0;
while (pos_short < short_str.length() && pos_long < long_str.length())
{
// pos_long long_str[pos_long] >= short_str[pos_short]
while (long_str[pos_long] < short_str[pos_short] && pos_long < long_str.length() - 1)
pos_long++;
// short_str ，pos_short
while (short_str[pos_short] == short_str[pos_short+1])
pos_short++;
if (long_str[pos_long] != short_str[pos_short])
break;
pos_long++;
pos_short++;
}
if (pos_short == short_str.length())
cout << "true" << endl;
else
cout << "false" << endl;
}
int main()
{
string strOne = "ABCDAK";
string strTwo = "A";
string long_str = strOne;
string short_str = strTwo;
//
CounterSort(strOne, long_str);
CounterSort(strTwo, short_str);
//
Compare(long_str, short_str);
return 0;
}사고방식 4:
O (m + n) 의 hashtable 방법 은 짧 은 문자열 에 대해 문의 할 수 있 습 니 다. 그 중의 모든 자 모 를 하나의 Hashtable 에 넣 을 수 있 습 니 다. (우 리 는 항상 m 를 짧 은 문자열 의 길이 로 설정 합 니 다. 그러면 이 작업 원 가 는 O (m) 입 니 다.그리고 긴 문자열 을 물 어보 고 Hashtable 에서 짧 은 문자열 의 모든 문 자 를 찾 을 수 있 는 지 확인 합 니 다.찾 지 못 하면 일치 하지 않 음 을 설명 합 니 다. 폴 링 긴 문자열 은 n 번 의 조작 을 소모 합 니 다. 이 두 가지 조작 을 합치 면 모두 (m + n) 번 만 있 습 니 다.물론 긴 문자열 의 접두사 가 짧 은 문자열 이 라면 m 회 조작 만 소모 하면 총 2m 회 가 필요 하 다 는 것 이 이상 적 이다.알고리즘 은 다음 과 같 습 니 다. 1. hash [26] 를 모두 제거 한 다음 에 짧 은 문자열 을 스 캔 합 니 다. 해당 하 는 설정 이 있 으 면 1. 2. hash [26] 중 1 의 개 수 를 계산 하여 m 로 기록 합 니 다. 3. 긴 문자열 의 모든 문자 a 스 캔 하기;원래 hash [a] = 1 이면 hash [a] = 0 을 수정 하고 m 를 1 로 줄인다.hash [a] = = 0 이면 처리 하지 않 습 니 다. 4. m = = 0 or 스 캔 이 끝나 면 순환 을 종료 합 니 다.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str1="ABCDEFGHLMNOPQRS";
string str2="DCGSRQPOM";
//
int hash[26] = {0};
// num
int num = 0;
//
for (int j = 0; j < str2.length(); j++)
{
//
int index = str1[j] - 'A';
// 0， 1， num++;
if (hash[index] == 0)
{
hash[index] = 1;
num++;
}
}
//
for (int k = 0; k < str1.length(); k++)
{
int index = str1[k] - 'A';
// 1， num--; ， （ ）。
if(hash[index] ==1)
{
hash[index] = 0;
num--;
if(num == 0) //m==0， 。
break;
}
}
// num 0
if (num == 0)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}사고방식 4:
O (m + n) 의 배열 저장 방법 (이 사고방식 은 사고방식 의 세 가지 본질 과 같다)
두 문자열 shortstr 와 logstr。 1: short 표시str 에 어떤 문자 가 있 는 지 store 배열 에 true 로 표시 합 니 다.(store 배열 은 매 핑 역할 을 합 니 다. A 가 있 으 면 첫 번 째 단원 을 true 로 표시 하고 B 가 있 으 면 두 번 째 단원 을 true 로 표시 합 니 다... Z 가 있 으 면 26 번 째 단원 을 true 로 표시 합 니 다) 2: log str 를 옮 겨 다 니 며, log str 의 문자 가 short str 의 문 자 를 포함 하면 store 배열 에 해당 하 는 위 치 를 false 로 표시 합 니 다. (A 가 있 으 면 첫 번 째 단원 을 false 로 표시 하고, B 가 있 으 면 두 번 째 단원 을 false 로 표시 합 니 다.. Z 가 있 으 면 26 번 째 단원 을 false 로 표시 합 니 다), 없 으 면 처리 하지 않 습 니 다. 3: 이후 store 배열 을 옮 겨 다 니 며 모든 요소 가 false 라면 store str 에 문자 가 log str 에 포함 되 어 있 음 을 설명 합 니 다. true 를 출력 합 니 다. 그렇지 않 으 면 false 를 출력 합 니 다.
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char long_ch[]="ABCDEFGHLMNOPQRS";
char short_ch[]="DEFGHXLMNOPQ";
int i;
bool store[58];
memset(store,false,58);
// ,
for(i=0;i<sizeof(short_ch)-1;i++)
store[short_ch[i]-65]=true;
for(i=0;i<sizeof(long_ch)-1;i++)
{
if(store[long_ch[i]-65]!=false)
store[long_ch[i]-65]=false;
}
for(i=0;i<58;i++)
{
if(store[i]!=false)
{
cout<<"short_ch is not in long_ch"<<endl;
break;
}
if(i==57)
cout<<"short_ch is in long_ch"<<endl;
}
return 0;
}사고 5: O (n) 에서 O (m + n) 까지 의 소수 방법 은 우리 가 일정한 수의 자모 로 문자열 을 구성한다 고 가정 한다. 나 는 모든 자모 에 소 수 를 분배 하고 2 부터 뒤로 유추 한다. 그러면 A 는 2, B 는 3 이 고 5 가 될 것 이다. 지금 나 는 첫 번 째 문자열 을 옮 겨 다 니 며 모든 자모 가 대표 하 는 소 수 를 곱 할 것 이다. 그리고 두 번 째 문자열 을 번갈아 물 어 봅 니 다. 각각 알파벳 으로 나 누 었 습 니 다. 만약 나 누 어 진 결과 에 나머지 가 있다 면, 이것 은 일치 하지 않 는 알파벳 이 있다 는 것 을 설명 합 니 다. 만약 전체 과정 에서 나머지 가 없다 면, 첫 번 째 문자열 의 적당 한 부분 집합 이라는 것 을 알 아야 합 니 다. 사고방식 은 다음 과 같 습 니 다. 1. 가장 작은 26 개의 소 수 를 각각 문자 A '부터' Z '까지 정의 합 니 다. 2. 긴 문자열 을 옮 겨 다 니 며 모든 문자 의 대응 소 를 구하 십시오.수의 곱 하기. 3. 짧 은 문자열 을 옮 겨 다 니 며 곱 하기 가 짧 은 문자열 의 문자 에 대응 하 는 소수 에 의 해 정 리 될 수 있 는 지 판단 합 니 다. 4. 출력 결과.
#include <iostream>
#include <string>
#include "BigInt.h"
using namespace std;
//
int primeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101};
int main()
{
string strOne = "ABCDEFGHLMNOPQRS";
string strTwo = "DCGSRQPOM";
//
CBigInt product = 1; // ， 。
// ，
for (int i = 0; i < strOne.length(); i++)
{
int index = strOne[i] - 'A';
product = product * primeNumber[index];
}
//
for (int j = 0; j < strTwo.length(); j++)
{
int index = strTwo[j] - 'A';
// 0， ，
if (product % primeNumber[index] != 0)
break;
}
// "true"， "false"。
if (strTwo.length() == j)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}다음 의 큰 정수 나 누 기 코드:
//
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class CBigInt
{
public:
// input
friend istream& operator >> (istream &, CBigInt &);
// output
friend ostream& operator << (ostream &os, const CBigInt &value)
{
if (value.bigInt[0] == '-')
os << value.bigInt;
else
{
//
os << value.bigInt.substr(1);
}
return os;
}
friend bool operator == (const CBigInt &, const CBigInt &);
friend bool operator < (const CBigInt &lValue, const CBigInt &rValue)
{
if (lValue.bigInt[0] != rValue.bigInt[0])
{
// '+'ASCII 43，'-'ASCII 45
return lValue.bigInt[0] > rValue.bigInt[0];
}
else
{
if (lValue.bigInt[0] == '+')
return lValue.smaller(rValue.bigInt); //
else
return lValue.greater(rValue.bigInt); //
}
}
friend bool operator > (const CBigInt &lValue, const CBigInt &rValue)
{
if (lValue.bigInt[0] != rValue.bigInt[0])
return lValue.bigInt[0] < rValue.bigInt[0];
else
{
if (lValue.bigInt[0] == '+')
return lValue.greater(rValue.bigInt);
else
return lValue.smaller(rValue.bigInt);
}
}
string bigInt;
public:
CBigInt();
CBigInt(int);
CBigInt(const string &);
CBigInt(const CBigInt &);
CBigInt(const char *);
CBigInt& operator = (const CBigInt &);
CBigInt& operator += (const CBigInt &);
CBigInt& operator -= (const CBigInt &);
CBigInt& operator *= (const CBigInt &);
CBigInt& operator /= (const CBigInt &);
CBigInt& operator %= (const CBigInt &);
// prefix increment
CBigInt& operator ++ ();
// prefix decrement
CBigInt& operator -- ();
// postfix increment
CBigInt operator ++ (int);
// postfix decrement
CBigInt operator -- (int);
private:
// unsigned +=
void plus(const string &);
// unsigned -=
void minus(const string &);
// unsigned ==
bool equal(const string &) const;
// unsigned <
bool smaller(const string &) const;
// unsigned >
bool greater(const string &) const;
};
/************************************************************************/
/*
/************************************************************************/
//
inline CBigInt::CBigInt() : bigInt("+0")
{}
//
inline CBigInt::CBigInt(const string &str) : bigInt(str)
{
if (bigInt.size() > 0)
{
//
if (bigInt[0] != '+' && bigInt[0] != '-')
{
string::size_type i = 0;
for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
if (i > 0)
bigInt.replace((string::size_type)0, i, "+");
else
bigInt.insert((string::size_type)0, 1, '+');
}
else
{
if (bigInt.size() == 1)
bigInt = "+0";
else
{
string::size_type j = 1;
// 0
for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
if (j > 1)
bigInt.erase((string::size_type)1, j - 1);
if (bigInt == "-0")
bigInt = "+0";
}
}
}
else
bigInt = "+0";
}
//
inline CBigInt::CBigInt(const CBigInt &value) : bigInt(value.bigInt)
{}
inline CBigInt::CBigInt(int num)
{
if (num == 0)
bigInt = "+0";
else if (num > 0)
bigInt = '+';
else
{
bigInt = '-';
num *= -1;
}
string temp = "";
while (num != 0)
{
temp += num % 10 + '0';
num = num / 10;
}
for (int i = temp.size() - 1; i >= 0; i--)
bigInt += temp[i];
}
inline CBigInt::CBigInt(const char *str) : bigInt(str)
{
if (bigInt.size() > 0)
{
if (bigInt[0] != '+' && bigInt[0] != '-')
{
string::size_type i = 0;
// 0
for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
if (i > 0)
bigInt.replace((string::size_type)0, i, "+");
else
bigInt.insert((string::size_type)0, 1, '+');
}
else
{
if (bigInt.size() == 0)
bigInt = "+0";
else
{
string::size_type j = 1;
for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
if (j > 1)
bigInt.erase((string::size_type)1, j - 1);
// “-0”
if (bigInt == "-0")
bigInt = "+0";
}
}
}
else
bigInt = "+0";
}
inline bool operator == (const CBigInt &lValue, const CBigInt &rValue)
{
return lValue.bigInt == rValue.bigInt;
}
inline bool operator != (const CBigInt &lValue, const CBigInt &rValue)
{
return !(lValue.bigInt == rValue.bigInt);
}
inline bool operator <= (const CBigInt &lValue, const CBigInt &rValue)
{
return !(lValue > rValue);
}
inline bool operator >= (const CBigInt &lValue, const CBigInt &rValue)
{
return !(lValue < rValue);
}
inline CBigInt& CBigInt::operator = (const CBigInt &value)
{
bigInt = value.bigInt;
return *this;
}
// unsigned ==
inline bool CBigInt::equal(const string &value) const
{
return bigInt.substr(1) == value.substr(1);
}
// unsigned <
inline bool CBigInt::smaller(const string &value) const
{
if (bigInt.size() == value.size())
return bigInt.substr(1) < value.substr(1);
else
return bigInt.size() < value.size();
}
// unsigned >
inline bool CBigInt::greater(const string &value) const
{
if (bigInt.size() == value.size())
return bigInt.substr(1) > value.substr(1);
else
return bigInt.size() > value.size();
}
/************************************************************************/
/* +,-,*,/
/************************************************************************/
void CBigInt::plus(const string &value)
{
if (bigInt.size() < value.size())
bigInt.insert((string::size_type)1, (value.size() - bigInt.size()), '0');
string::size_type i = bigInt.size() - 1;
string::size_type j = value.size() - 1;
while (j > 1)
{
bigInt[i] += value[j] - '0';
if (bigInt[i] > '9')
{
bigInt[i] -= 10;
++bigInt[i-1];
}
i--;
j--;
}
//
bigInt[i] += value[1] - '0';
while (i > 1 && bigInt[i] > '9')
{
bigInt[i] -= 10;
i--;
++bigInt[i];
}
if (bigInt[1] > '9')
{
bigInt[1] -= 10;
bigInt.insert((string::size_type)1, 1, '1');
}
}
void CBigInt::minus(const string &vlaue)
{
string::size_type i = bigInt.size() - 1;
string::size_type j = vlaue.size() - 1;
while (j >= 1)
{
bigInt[i] -= vlaue[j] - '0';
if (bigInt[i] < '0')
{
bigInt[i] += 10;
--bigInt[i-1];
}
i--;
j--;
}
//
while (i > 1 && bigInt[i] < '0')
{
bigInt[i] += 10;
i--;
--bigInt[i];
}
// 0
string::size_type k = 1;
for (; k < bigInt.size() - 1 && bigInt[k] == '0'; k++);
if (k > 1)
bigInt.erase((string::size_type)1, k - 1);
}
CBigInt& CBigInt::operator += (const CBigInt &value)
{
if (bigInt[0] == value.bigInt[0])
plus(value.bigInt);
else
{
//
if (equal(value.bigInt))
bigInt = "+0";
//
else if (smaller(value.bigInt))
{
string temp = bigInt;
bigInt = value.bigInt;
minus(temp);
}
else
minus(value.bigInt);
}
return *this;
}
CBigInt& CBigInt::operator -= (const CBigInt &value)
{
// +=
if (bigInt[0] == value.bigInt[0])
{
if (equal(value.bigInt))
bigInt = "+0";
else if (smaller(value.bigInt))
{
string temp = bigInt;
bigInt = value.bigInt;
minus(temp);
if (bigInt[0] == '+')
bigInt[0] = '-';
else
bigInt[0] = '+';
}
else
minus(value.bigInt);
}
else
plus(value.bigInt);
return *this;
}
CBigInt operator + (const CBigInt &lValue, const CBigInt &rValue)
{
CBigInt sum(lValue);
sum += rValue;
return sum;
}
CBigInt operator - (const CBigInt &lValue, const CBigInt &rValue)
{
CBigInt diff(lValue);
diff -= rValue;
return diff;
}
// prefix increment
CBigInt& CBigInt::operator ++ ()
{
string::size_type i = bigInt.size() - 1;
if (bigInt[0] == '+')
{
++bigInt[i];
while (i > 1 && bigInt[i] > '9')
{
bigInt[i] -= 10;
i--;
++bigInt[i];
}
if (bigInt[i] > '9')
{
bigInt[i] -= 10;
bigInt.insert((string::size_type)1, 1, '1');
}
}
else
{
--bigInt[i];
while(i > 1 && bigInt[i] < '0')
{
bigInt[i] += 10;
i--;
--bigInt[i];
}
string::size_type j = 1;
for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
if (j > 1)
bigInt.erase(1, j - 1);
if (bigInt[1] == '0')
bigInt[0] = '+';
}
return *this;
}
CBigInt& CBigInt::operator -- ()
{
string::size_type i = bigInt.size() - 1;
//
if (bigInt[0] == '+')
{
// 0
if (bigInt[1] == '0')
bigInt = "-1";
else
{
--bigInt[i];
while (i > 1 && bigInt[i] < '0')
{
bigInt[i] += 10;
i--;
--bigInt[i];
}
string::size_type j = 1;
for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
if (j > 1)
bigInt.erase(1, j - 1);
}
}
else
{
++bigInt[i];
while (i > 1 && bigInt[i] > '9')
{
bigInt[i] -= 10;
i--;
++bigInt[i];
}
if (bigInt[1] > '9')
{
bigInt[1] += 10;
bigInt.insert((string::size_type)1, 1, '1');
}
}
return *this;
}
// postfix increment
CBigInt CBigInt::operator ++ (int)
{
CBigInt temp(*this);
++(*this);
return temp;
}
// postfix decrement
CBigInt CBigInt::operator -- (int)
{
CBigInt temp(*this);
--(*this);
return temp;
}
//
CBigInt& CBigInt::operator *= (const CBigInt &value)
{
// 0 0
if (bigInt[1] == '0' || value.bigInt[1] == '0')
{
bigInt = "+0";
return *this;
}
string::size_type sizeofMultiplicand = bigInt.size();
string::size_type sizeofMultiplier = value.bigInt.size();
vector<unsigned int> product(sizeofMultiplier + sizeofMultiplicand - 1);
//
for (string::size_type i = 1; i < sizeofMultiplicand; ++i)
bigInt[i] -= '0';
//
for (string::size_type j = sizeofMultiplier - 1; j > 0; --j)
{
if (value.bigInt[j] > '0')
{
for (string::size_type k = sizeofMultiplicand - 1; k > 0; --k)
product[k+j] += bigInt[k] * (value.bigInt[j] - '0');
}
}
//
if (bigInt[0] == value.bigInt[0])
product[0] = '+';
else
product[0] = '-';
vector<unsigned int>::size_type sizeofProduct = product.size();
bigInt = string(sizeofProduct, '0');
bigInt[0] = product[0];
//
for (vector<unsigned int>::size_type n = sizeofProduct - 1; n > 1; --n)
{
product[n-1] += product[n] / 10;
product[n] %= 10;
bigInt[n] += product[n];
}
if (product[1] == 0)
bigInt.erase(1, 1);
else
bigInt[1] += product[1];
return *this;
}
//
CBigInt& CBigInt::operator /= (const CBigInt &value)
{
// 0
if (value.bigInt == "+0")
{
bigInt = "*Error!";
return *this;
}
//
if (value.smaller(bigInt) == true)
{
string::size_type sizeofDividend = bigInt.size();
string::size_type sizeofDivisor = value.bigInt.size();
string answer(sizeofDividend, '0');
//
if (bigInt[0] == value.bigInt[0])
answer[0] = '+';
else
answer[0] = '-';
string::size_type start = 1;
string::size_type end = sizeofDivisor - 1;
while (end < sizeofDividend)
{
// ，
while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==
false)
{
string::size_type j = end;
//
for (string::size_type i = sizeofDivisor - 1; i > 0; i--, j--)
{
bigInt[j] -= value.bigInt[i] - '0';
if (bigInt[j] < '0')
{
bigInt[j] += 10;
--bigInt[j-1];
}
}
// 1
++answer[end];
// 0
while (start <= end && bigInt[start] == '0')
++start;
}
// 0
while (start < sizeofDividend && bigInt[start] == '0')
++start;
// end-start+1 < sizeofDivisor - 1,
if (end - start + 2 < sizeofDivisor)
end = sizeofDivisor + start - 2;
else
++end;
}
start = 1;
for (; start < answer.size() - 1 && answer[start] == '0'; ++start);
if (start > 1)
answer.erase(1, start - 1);
bigInt = answer;
}
//
else if (value.equal(bigInt) == true)
{
string answer = "-1";
if (bigInt[0] == value.bigInt[0])
answer = "+1";
bigInt = answer;
}
else
bigInt = "+0";
return *this;
}
// ，
CBigInt& CBigInt::operator %= (const CBigInt &value)
{
if (value.bigInt == "+0")
{
bigInt = "*Error!";
return *this;
}
// ， bigInt
if (value.smaller(bigInt) == true)
{
string::size_type sizeofDivident = bigInt.size();
string::size_type sizeofDivisor = value.bigInt.size();
string::size_type start = 1;
string::size_type end = sizeofDivisor - 1;
while (end < sizeofDivident)
{
//
while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==
false)
{
string::size_type j = end;
for (string::size_type i = sizeofDivisor - 1; i > 0; --i, --j)
{
bigInt[j] -= value.bigInt[i] - '0';
if (bigInt[j] < '0')
{
bigInt[j] += 10;
--bigInt[j-1];
}
}
while (start <= end && bigInt[start] == '0')
++start;
}
while (start < sizeofDivident && bigInt[start] == '0')
++start;
if (end - start + 2 < sizeofDivisor)
end = sizeofDivisor + start - 2;
else
++end;
}
start = 1;
for (; start < sizeofDivident - 1 && bigInt[start] == '0'; start++);
if (start > 1)
bigInt.erase(1, start - 1);
if (bigInt == "-0")
bigInt[0] = '+';
}
else if (value.equal(bigInt))
bigInt = "+0";
return *this;
}
CBigInt operator * (const CBigInt &lValue, const CBigInt &rValue)
{
CBigInt product(lValue);
product *= rValue;
return product;
}
CBigInt operator / (const CBigInt &lValue, const CBigInt &rValue)
{
CBigInt quotient(lValue);
quotient /= rValue;
return quotient;
}
CBigInt operator % (const CBigInt &lValue, const CBigInt &rValue)
{
CBigInt mod(lValue);
mod %= rValue;
return mod;
}문제 2: 문자열 일치 문제 설명: 두 문자열 에 포 함 된 문자 와 개수 가 같다 고 가정 하면 이 두 문자열 이 일치 합 니 다. 예 를 들 어 abcda 와 adabc 는 문자 개수 가 같 고 순서 만 다 르 기 때문에 이 두 문자열 이 일치 합 니 다. 분석: 이 문자열 의 일치 문 제 는 상기 문자열 과 일치 하 는 것 임 을 알 수 있 습 니 다.포 함 된 문 제 는 유사 합 니 다. 이 문 제 는 먼저 정렬 한 다음 에 비교 할 수도 있 고 hash 표를 이용 하여 판단 할 수도 있 습 니 다. 여기 서 hash 표 의 방법 을 제시 합 니 다. 원 리 는 앞에서 설명 하 였 습 니 다. 코드 는 다음 과 같 습 니 다.
#include <iostream>
#include <string>
using namespace std;
bool Is_Match(const char *strOne,const char *strTwo)
{
int lenOfOne = strlen(strOne);
int lenOfTwo = strlen(strTwo);
// false
if (lenOfOne != lenOfTwo)
return false;
//
int hash[26] = {0};
//
for (int i = 0; i < strlen(strOne); i++)
{
//
int index = strOne[i] - 'A';
// 1，
hash[index]++;
}
//
for (int j = 0; j < strlen(strTwo); j++)
{
int index = strTwo[j] - 'A';
// 0 1， false
if (hash[index] != 0)
hash[index]--;
else
return false;
}
return true;
}
int main()
{
string strOne = "ABBA";
string strTwo = "BBAA";
bool flag = Is_Match(strOne.c_str(), strTwo.c_str());
// true ，
if (flag == true)
cout << "Match" << endl;
else
cout << "No Match" << endl;
return 0;
}질문 3: 문자열 에서 하위 문자열 문 제 를 찾 습 니 다. 주어진 문자열 A 는 A 에서 하위 문자열 B 를 찾 아야 합 니 다. 예 를 들 어 A = "ABCDF" 는 A 에서 하위 문자열 B = "CD" 를 찾 아야 합 니 다. 분석: 비교적 간단 합 니 다. strstr 라 이브 러 리 함수 에 해당 합 니 다. 주 코드 는 다음 과 같 습 니 다.
int strstr(char *string,char *substring)
{
int len1=strlen(string);
int len2=strlen(substring);
for (int i=0; i<=len1-len2; i++) // O(m*n)
{
for (int j=0; j<len2; j++)
{
if (string[i+j]!=substring[j])
break;
}
if (j==len2)
return i+1;
}
return 0;
} 문제 4: 한 문자열 에서 첫 번 째 로 한 번 만 나타 나 는 문자 분석 을 찾 습 니 다. 먼저 문자 배열 을 한 번 옮 겨 다 니 고 해당 위치 에 있 는 숫자 배열 에 문 자 를 넣 은 다음 에 문자 배열 을 옮 겨 다 니 며 숫자 배열 을 찾 습 니 다.
#include <iostream>
using namespace std;
char find_first_unique_char(char *str)
{
int data[256];
char *p;
if (str == NULL)
return '/0';
memset(data, 0, sizeof(data)); // 0
p = str;
while (*p != '/0')
data[(unsigned char)*p++]++; // ， ++，（ ， ）
while (*str != '/0')
{
if (data[(unsigned char)*str] == 1) // ， 1
return *str;
str++;
}
return '/0';
}
int main()
{
char *str = "afaccde";
cout << find_first_unique_char(str) << endl;
return 0;
}문제 5: 문자열 을 정수 제목 으로 변환 합 니 다. 정 수 를 표시 하 는 문자열 을 입력 하고 이 문자열 을 정수 로 변환 하여 출력 합 니 다. 예 를 들 어 문자열 '345' 를 입력 하 십시오.분석: 이 문 제 는 보기 에는 비교적 간단 합 니 다. 한 문 자 를 스 캔 할 때마다 우 리 는 이전에 얻 은 숫자 에 10 을 곱 하고 현재 문자 로 표 시 된 숫자 를 더 합 니 다. 이 사 고 는 순환 으로 실현 하기 어렵 지 않 습 니 다. 그러나 그 뒤에 많은 함정 이 숨 어 있 습 니 다. zhedahht 가 말 한 것 처럼 다음 과 같은 몇 가지 주의 가 필요 합 니 다.
1. 정 수 는 숫자 뿐만 아니 라 '+' 또는 '-' 로 시작 하여 정수 의 양 과 음 을 나 타 낼 수 있 습 니 다. 첫 번 째 문자 가 '+' 호 라면 어떠한 조작 도 할 필요 가 없습니다. 첫 번 째 문자 가 '-' 호 라면 이 정수 가 음수 임 을 나타 내 고 마지막 에 우리 가 얻 은 수 치 를 음수 로 바 꿔 야 합 니 다. 2, 지침 을 사용 하 는 경우 지침 을 사용 하기 전에 우리 가 해 야 할 첫 번 째 는 이 지침 이 비어 있 는 지 아 닌 지 를 판단 하 는 것 입 니 다. 3. 입력 한 문자열 에는 숫자 가 아 닌 문자 가 들 어 있 을 수 있 습 니 다. 이 불법 문 자 를 만 날 때마다 더 이상 변환 할 필요 가 없습니다. 4. 넘 침 문제 입 니 다. 입력 한 숫자 는 문자열 로 입력 되 기 때문에 큰 숫자 변환 을 입력 하면 표시 할 수 있 는 최대 정 수 를 초과 하여 넘 칠 수 있 습 니 다.
상기 네 가 지 를 정리 하면 코드 는 다음 과 같이 작성 할 수 있 습 니 다.
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
int str_2_int(string str)
{
assert(str.size() > 0);
int pos = 0;
int sym = 1;
//
if (str[pos] == '+')
pos++;
else if (str[pos] == '-')
{
pos++;
sym = -1;
}
int num = 0;
//
while (pos < str.length())
{
//
assert(str[pos] >= '0');
assert(str[pos] <= '9');
num = num * 10 + (str[pos] - '0');
//
assert(num >= 0);
pos++;
}
num *= sym;
return num;
}
int main()
{
string str = "-1024";
int num = str_2_int(str);
cout << num << endl;
return 0;
}문제 6: 문자열 의 복사 문제 설명: 라 이브 러 리 함수 strcpy 를 실현 해 야 합 니 다. 분석: 표준 strcpy 함수 의 총 점 수 를 10 으로 작성 하면 다음 과 같은 몇 가지 다른 점 수 를 얻 을 수 있 습 니 다.
//2
void strcpy( char *strDest, char *strSrc )
{
while( (*strDest++ = * strSrc++) != '/0' );
}
//4
void strcpy( char *strDest, const char *strSrc )
{
// const， ， 2
while( (*strDest++ = * strSrc++) != '/0' );
}
//7
void strcpy(char *strDest, const char *strSrc)
{
// 0 ， 3
assert( (strDest != NULL) && (strSrc != NULL) );
while( (*strDest++ = * strSrc++) != '/0' );
}
//10
// ， ， 3 ！
char * strcpy( char *strDest, const char *strSrc )
{
assert( (strDest != NULL) && (strSrc != NULL) );
char *address = strDest;
while( (*strDest++ = * strSrc++) != '/0' );
return address;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
