八皇后
題目：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。
想法1：一層層來(lái)放置。
代碼1：
int que[8]={-1,-1,-1,-1,-1,-1,-1,-1};
int cou=0;
bool avl(int i,int j){
for(int m =0; m<i;m++){
if(que[m]==j) return false;
if((m-i)==(que[m]-j)) return false;
if((m-i)==(j-que[m])) return false;
}
return true;
}
void fin(int cow){
for(int i = 0;i<8;i++){
que[cow]=i;
if(avl(cow,i)){
if(cow==7){//如果八個(gè)皇后都放滿了統(tǒng)計(jì)一下
for(int i = 0 ; i<8;i++){
cout<<que[i];
}
cout<<" "<<endl;
cou++;
}
fin(cow+1);
}
}
return;
}
結(jié)果1：
92種方法。
剪繩子
題目：給你一根長(zhǎng)度為n繩子，請(qǐng)把繩子剪成m段（m、n都是整數(shù)，n>1并且m>1）。每段的繩子的長(zhǎng)度記為k[0]、k[1]、……、k[m]。k[0] * k[1]…k[m]可能的最大乘積是多少？例如當(dāng)繩子的長(zhǎng)度是8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到最大的乘積18。
我的：不會(huì)
int cut(int length) {
if(length<2) return 0;
if(length<4) return length-1;
vector<int> temp;
temp.push_back(0);
temp.push_back(1);
temp.push_back(2);
temp.push_back(3);
for(int i = 4 ;i<=length;i++){
int ma = 0;
for(int j = 1 ;j<=length/2;j++){
ma = max(temp[j]*temp[i-j],ma);
}
temp.push_back(ma);
}
return temp.back();
}
劍指：動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃求解問(wèn)題的四個(gè)特征：
①求一個(gè)問(wèn)題的最優(yōu)解；
②整體的問(wèn)題的最優(yōu)解是依賴于各個(gè)子問(wèn)題的最優(yōu)解；
③小問(wèn)題之間還有相互重疊的更小的子問(wèn)題；
④從上往下分析問(wèn)題，從下往上求解問(wèn)題；
"""
在剪繩子這個(gè)題目中，由于必須要剪一刀，因此會(huì)導(dǎo)致當(dāng)所給的繩子長(zhǎng)度是小于4的時(shí)候，剪完之后的長(zhǎng)度
小于剪之前的長(zhǎng)度。但是我們?cè)谶f推的時(shí)候，例如求f(5) = max{f(1)*f(4), f(2)*f(3)} = 6
如果令f(3)=2的話，將導(dǎo)致遞推公式錯(cuò)誤，因此，對(duì)于小于4的輸入，我們特殊處理。
注意不符合切割條件的輸入n，以及輸入為2、3長(zhǎng)度時(shí)的結(jié)果，因?yàn)轭}中規(guī)定m>1。
"""
//輸入繩子的長(zhǎng)度,輸出最大乘積
int maxProductAfterCutting_solution1(int length) {
if(length < 2)//因?yàn)橐箝L(zhǎng)度n>1,所以這里返回0表示輸入非法
return 0;
if(length == 2)//長(zhǎng)度為2時(shí),因?yàn)橐蠹粝露螖?shù)m>1,所以最大是1x1=1
return 1;
if(length == 3)//長(zhǎng)度為3時(shí),因?yàn)橐蠹粝露螖?shù)m>1,所以最大是1x2=2
return 2;
//運(yùn)行至此,說(shuō)明繩子的長(zhǎng)度是>3的,這之后0/1/2/3這種子問(wèn)題最大就是其自身長(zhǎng)度
//而不再需要考慮剪一刀的問(wèn)題,因?yàn)樗鼈兗粢坏稕](méi)有不剪來(lái)的收益高
//而在當(dāng)下這么長(zhǎng)的繩子上剪過(guò)才可能生成0/1/2/3這種長(zhǎng)度的繩子,它們不需要再減
//所以下面的表中可以看到它們作為子問(wèn)題的值和上面實(shí)際返回的是不一樣的
//在表中先打上子繩子的最大乘積
int* products = new int[length + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;//到3為止都是不剪最好
int max = 0;//用于記錄最大乘積
//對(duì)于4以上的情況,每次循環(huán)要求f(i)
for(int i = 4; i <= length; ++i) {
max = 0;//每次將最大乘積清空
//因?yàn)橐?jì)算f(j)乘以f(i-j)的最大值,j超過(guò)i的一半時(shí)是重復(fù)計(jì)算
//所以只需要考慮j不超過(guò)i的一半的情況
for(int j = 1; j <= i / 2; ++j) {
//計(jì)算f(j)乘以f(i-j)
int product = products[j] * products[i - j];
//如果比當(dāng)前找到的還大
if(max < product)
max = product;//就把最大值更新
}
//這里是循環(huán)無(wú)關(guān)的,書(shū)上在for里面,我把它提出來(lái)
products[i] = max;//最終,更新表中的f(i)=max(f(j)·f(i-j))
}
//循環(huán)結(jié)束后,所求的f(length)也就求出來(lái)了
max = products[length];//將其記錄下來(lái)以在銷毀后能返回
delete[] products;//銷毀打表的輔助空間
return max;
}
打印從1到最大的n位數(shù)
題目：
輸入數(shù)字n，按順序打印出從1到最大的n位十進(jìn)制數(shù)。比如輸入3，則打印出1、2、3一直到最大的3位數(shù)即999。
我的：
//方法1：
void print(int n) {
int ma = 0;
while(n!=0){
ma = ma*10+9;
n--;
}
for(int i = 1 ;i<=ma;i++){
cout<<i<<endl;
}
}
//方法2：全排列
vector<string> result;
void all(int index, int n,string temp){
if(index>n)
{
result.push_back(temp);
return;
}
for(int i = 0;i<10;i++){
string temp2 = temp+char('0'+i);
all(index+1,n,temp2);
}
}
void print(int n) {
string str = "";
all(1,n,str);
string s;
for(int j = 1 ;j<result.size();j++){
s = result[j];
bool flag = false;
int i = 0;
while(i<n){
if(!flag){
if(s[i]!='0'){
flag = true;
cout<<s[i];
}
}else{
cout<<s[i];
}
i++;
}
cout<<""<<endl;
}
}
劍指：
//模擬加法：
class Solution {
public:
void Print1ToMaxOfNDigits(int n)
{
char* number = new char[n + 1];
//開(kāi)辟一個(gè)存放字符數(shù)組(包含n + 1個(gè)元素 number[0]~number[n])的空間，返回字符數(shù)組首元素的地址
memset(number, '0', n); // number[0]~number[n-1]都是'0'
number[n] = '\0';
while (!Increment(number))
{
PrintNumber(number);
}
}
private:
bool Increment(char* number)
{
//此函數(shù)用于在表示數(shù)字的字符串上 + 1，并判斷有沒(méi)有溢出
//number是一個(gè)字符串
bool isOverflow = false; //溢出
int nTackOver = 0; //進(jìn)位標(biāo)志
int nLength = strlen(number); //計(jì)算字符串str 的長(zhǎng)度，直到空結(jié)束字符
// number[nLength - 1]是這個(gè)數(shù)字的倒數(shù)第1位
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTackOver;
if (i == nLength - 1)
nSum++; //如果是個(gè)位（最后一位）的話，+1
if (nSum >= 10)
if (i == 0)
isOverflow = true; //如果nSum==10,且是最高位，則溢出
else
{
nSum -= 10;
nTackOver = 1; //進(jìn)位
number[i] = '0' + nSum;
}
else
{
number[i] = '0' + nSum;
break; //運(yùn)行到某一數(shù)位不需要進(jìn)位，退出循環(huán)
// 例如520+1之后個(gè)位 nSum < 10,此時(shí)不會(huì)產(chǎn)生進(jìn)位，也不會(huì)有溢出的情況
//可以直接退出循環(huán)
}
}
return isOverflow;
}
void PrintNumber(char* number) //此函數(shù)用于打印數(shù)字，數(shù)字前面補(bǔ)位的“0”不打印
{
bool isBeginning0 = true;
int nLength = strlen(number);
for (int i = 0; i < nLength; i++)
{
if (isBeginning0 && number[i] != '0')//開(kāi)始不為0，第i位不是0
isBeginning0 = false; //例如“00098”到number[2]才不是0,兩個(gè)條件都為true
//isBeginning0 = false
if (!isBeginning0) //isBeginning0 = false才能執(zhí)行輸出
cout << number[i];
}
cout << endl;
}
};
//全排序：
class Solution {
public:
void Print1ToMaxOfNDigits(int n)
{
char* number = new char[n + 1];
//開(kāi)辟一個(gè)存放字符數(shù)組(包含n + 1個(gè)元素 number[0]~number[n])的空間，返回字符數(shù)組首元素的地址
memset(number, '0', n); // number[0]~number[n-1]都是'0'
number[n] = '\0';
dfsHelper(number, 0, n);
}
private:
void PrintNumber(char* number) //此函數(shù)用于打印數(shù)字，數(shù)字前面補(bǔ)位的“0”不打印
{
bool isBeginning0 = true;
int nLength = strlen(number);
for (int i = 0; i < nLength; i++)
{
if (isBeginning0 && number[i] != '0')//開(kāi)始不為0，第i位不是0
isBeginning0 = false; //例如“00098”到number[2]才不是0,兩個(gè)條件都為true
//isBeginning0 = false
if (!isBeginning0) //isBeginning0 = false才能執(zhí)行輸出
cout << number[i];
}
cout << endl;
}
void dfsHelper(char* number, int index, int n)
{
if (index == n)
{
PrintNumber(number);
return;
}
for (int i = 0; i < 10; i++)
{
number[index] = i + '0';
dfsHelper(number, index + 1, n);
}
}
};
刪除鏈表的節(jié)點(diǎn)
題目：在O（1）時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)。
我的：遍歷在刪除是O（N）
由于給出了所要?jiǎng)h除結(jié)點(diǎn)指針，所以可以直接考慮用刪除結(jié)點(diǎn)的下一結(jié)點(diǎn)代替要?jiǎng)h除的結(jié)點(diǎn)，然后釋放要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。這里得注意的是需要考慮要?jiǎng)h除結(jié)點(diǎn)的三種情況：1.要?jiǎng)h除的節(jié)點(diǎn)不是尾節(jié)點(diǎn)，2.鏈表只有一個(gè)節(jié)點(diǎn)，刪除頭結(jié)點(diǎn)（也是尾節(jié)點(diǎn)）3.鏈表中有多個(gè)節(jié)點(diǎn)，刪除尾結(jié)點(diǎn)（這里的情況就蛻變成一般從頭到尾遍歷尋找要?jiǎng)h除的節(jié)點(diǎn)的思路，開(kāi)始沒(méi)注意到給出要?jiǎng)h除的結(jié)點(diǎn)的指針已經(jīng)給出，考慮到了這個(gè)O(N）算法...）
劍指：
void DeletNode(ListNode** pListHead,ListNode* pToBeDeleted)//傳遞二級(jí)指針的原因，可能會(huì)修改頭節(jié)點(diǎn)
{
if(!pListHead||pToBeDeleted)
return;
//要?jiǎng)h除的節(jié)點(diǎn)不是尾節(jié)點(diǎn)
if(pToBeDeleted->m_pNext!=nullptr)
{
ListNode* pNext=pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue=pNext->m_nValue;
pToBeDeleted->m_pNext=pNext->m_pNext;
delete pNext;
pNext=nullptr;
}
//鏈表只有一個(gè)節(jié)點(diǎn)，刪除頭節(jié)點(diǎn)（也是尾節(jié)點(diǎn)）
else if(*pListHead==pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted=nullptr;
*pListHead=nullptr;
}
//鏈表中有多個(gè)節(jié)點(diǎn)，刪除尾節(jié)點(diǎn)
else
{
ListNode* pNode=*pListHead;
while(pNode->m_pNext!=pToBeDeleted)
{
pNode=pNode->m_pNext;
}
pNode->m_pNext=nullptr;
delete pToBeDeleted;
pToBeDeleted=nullptr;
}
數(shù)字序列中某一位的數(shù)字
題目：
數(shù)字以01234567891011121314...的格式排列。在這個(gè)序列中，第5位（從0開(kāi)始計(jì)）是5，第13位是1，第19位是4。求任意第n為對(duì)應(yīng)的數(shù)字。
我的：
int num(int n){
if(n==0) return 0;
if(n==1) return 10;
return (pow(10,n)-pow(10,n-1))*n;
}
void test(int index) {
int n = 0;
int sum = 0;
while(index+1>sum){
sum+=num(++n);
}
sum = 0;
int temp = n-1;
while(temp>0){
sum+=num(temp--);
}
int temp2;
if(n==1) temp2 = (index-sum)/n;
else temp2 = pow(10,n-1)+(index-sum)/n;
cout<<to_string(temp2)[index%n]<<endl;
}
//方法2：
int num(int n){
if(n==0) return 0;
if(n==1) return 10;
return (pow(10,n)-pow(10,n-1))*n;
}
void test(int index) {
int n = 0;
int sum = 0;
while(index+1>sum){
sum+=num(++n);
}
sum = 0;
int temp = n-1;
while(temp>0){
sum+=num(temp--);
}
int temp2;
if(n==1) temp2 = (index-sum)/n;
else temp2 = pow(10,n-1)+(index-sum)/n;
for(int i = 0;i<n-index%n-1;i++){
temp2=temp2/10;
}
temp2=temp2%10;
cout<<temp2<<endl;
}
劍指：
以第15位數(shù)字2為例（2隸屬與12，兩位數(shù)，位于12從左側(cè)以0號(hào)開(kāi)始下標(biāo)為1的位置）
步驟1：首先確定該數(shù)字是屬于幾位數(shù)的;
如果是一位數(shù)，n<9;如果是兩位數(shù)，n<9+90*2=189;
說(shuō)明是兩位數(shù)。
步驟2：確定該數(shù)字屬于哪個(gè)數(shù)。10+(15-10)/2= 12。
步驟3：確定是該數(shù)中哪一位。15-10-(12-10)*2 = 1, 所以位于“12”的下標(biāo)為1的位置，即數(shù)字2。
以第1001位數(shù)字7為例
步驟1：首先確定該數(shù)字是屬于幾位數(shù)的;
如果是一位數(shù)，n<9;如果是兩位數(shù)，n<9+90*2=189;如果是三位數(shù)，n<189+900*3=2889;
說(shuō)明是三位數(shù)。
步驟2：確定該數(shù)字屬于哪個(gè)數(shù)。100+(1001-190)/3= 370。
步驟3：確定是該數(shù)中哪一位。1001-190-(370-100)*3 = 1,所以位于“370”的下標(biāo)為1的位置，即數(shù)字7。
禮物的最大值
題目：
?在一個(gè) m*n 的棋盤(pán)中的每一個(gè)格都放一個(gè)禮物，每個(gè)禮物都有一定的價(jià)值（價(jià)值大于0）.你可以從棋盤(pán)的左上角開(kāi)始拿各種里的禮物，并每次向左或者向下移動(dòng)一格，直到到達(dá)棋盤(pán)的右下角。給定一個(gè)棋盤(pán)及上面?zhèn)€的禮物，請(qǐng)計(jì)算你最多能拿走多少價(jià)值的禮物？
比如說(shuō)現(xiàn)在有一個(gè)如下的棋盤(pán)，
image.png
在這個(gè)棋盤(pán)中，按照（1，12，5，7，7，16，5）的順序可以拿到總價(jià)值最大的禮物。
image.png
我的：
//方法1：
int ma = 0;
void dp(vector<vector<int>> in , int nrows, int ncols,int rows, int cols, int sum){
if(nrows>rows-1||ncols>cols-1) return;
if(nrows==rows-1&&ncols==cols-1) {
sum+=in[nrows][ncols];
ma = max(ma, sum);
return;
}
sum+=in[nrows][ncols];
dp(in, nrows+1,ncols,rows,cols,sum);
dp(in, nrows,ncols+1,rows,cols,sum);
}
void test(vector<vector<int>> in , int rows, int cols) {
int sum = 0;
dp(in, 0,0,rows,cols,sum);
cout<<ma<<endl;
}
//方法2：每個(gè)格子等于max（左，上）+本身，而且只用維護(hù)一維列長(zhǎng)的數(shù)組，保存結(jié)果。
int test(vector<vector<int>> in , int rows, int cols) {
if(rows==0||cols==0) return 0;
int result = 0;
vector<int> flag(cols,0);
int temp = 0;
flag[0] = in[0][0];
for(int i = 0 ;i<rows;i++){
for(int j = 0 ;j<cols;j++){
int left = j-1>=0?flag[j-1]:0;
int up = i-1>=0?flag[j]:0;
flag[j] = max(left, up)+in[i][j];
}
}
return flag[cols-1];
}
劍指：方法2
最長(zhǎng)不含重復(fù)字符的子字符串
題目：請(qǐng)從字符串中找出一個(gè)最長(zhǎng)的不包含重復(fù)字符的子字符串，計(jì)算該最長(zhǎng)子字符串的長(zhǎng)度。假設(shè)字符串中只包含從’a’到’z’的字符。例如，在字符串中”arabcacfr”，最長(zhǎng)非重復(fù)子字符串為”acfr”，長(zhǎng)度為4。
我的：不會(huì)
//動(dòng)規(guī)：f（i）表示當(dāng)前字符為結(jié)尾的最大子串長(zhǎng)度
int test(string str) {
int length = str.size();
if(length<2) return length;
vector<int> flag(26,-1);
vector<int> result(length,0);
int ma = 0;
for(int i = 0 ;i < length;i++){
if(flag[str[i]-'a']<0){
flag[str[i]-'a']=i;
if(i>0)result[i] = result[i-1]+1;
else result[i]++;
}else{
int dif = i - flag[str[i]-'a'];
if(dif<= result[i-1]){
result[i] = dif;
}else{
result[i] = result[i-1]+1;
}
flag[str[i]-'a']=i;
}
ma = max(ma, result[i]);
}
return ma;
}
//方法2：雙指針，左到右，start表示開(kāi)始位置
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1); // 用來(lái)記錄字符上次出現(xiàn)的位置
int maxlen=0, start = -1;
for (int i = 0; i != s.length(); i++){
// s[i]字符上次出現(xiàn)的下標(biāo)是否在start之后，若是，則重復(fù)了，則修改start為上一次s[i]的位置，從它后一位開(kāi)始搜索
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxlen = max(maxlen, i - start);
}
return maxlen;
}
劍指：
//動(dòng)規(guī)：
int test(string str) {
int length = str.size();
if(length<2) return length;
vector<int> flag(26,-1);
int currentLength = 0;
int ma = 0;
for(int i = 0 ;i < length;i++){
if(flag[str[i]-'a']<0){
flag[str[i]-'a']=i;
currentLength++;
}else{
int dif = i - flag[str[i]-'a'];
if(dif <= currentLength){
currentLength = dif;
}else{
currentLength++;
}
flag[str[i]-'a']=i;
}
ma = max(ma, currentLength);
}
return ma;
}
N個(gè)骰子的點(diǎn)數(shù)
題目： 把n個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為s，
輸入n，打印出s的所有可能的值出現(xiàn)的概率。
n個(gè)骰子的總點(diǎn)數(shù)，最小為n，最大為6n，根據(jù)排列組合的知識(shí)，那個(gè)骰子，所有點(diǎn)數(shù)的排列數(shù)為6^n。
我們先統(tǒng)計(jì)每一個(gè)點(diǎn)數(shù)出現(xiàn)的次數(shù)，然后把每一個(gè)點(diǎn)數(shù)出現(xiàn)的次數(shù)除以6^n，就能求出每個(gè)點(diǎn)數(shù)出現(xiàn)的概率。
我的：
//遞歸：算出每個(gè)和的個(gè)數(shù)，5n個(gè)和
void dp( vector<int>& flag ,int nn, int n,int sum){
if(nn>n) {
flag[sum-n]++;
return;
}
for(int i = 1;i<7;i++){
sum += i;
dp(flag,nn+1,n,sum);
sum -= i;
}
}
vector<double> test(int n) {
vector<double> result;
if(n<1) return result;
vector<int > flag(5*n+1,0);
dp(flag, 1, n , 0);
for(int i : flag){
result.push_back(i/pow(6,n));
}
return result;
}
劍指：
思路一：
基于遞歸求骰子點(diǎn)數(shù)，時(shí)間效率不夠高。
先把骰子分成兩堆，第一堆只有一個(gè)，第二堆有n-1個(gè)，
單獨(dú)的那一個(gè)可能出現(xiàn)1到6的點(diǎn)數(shù)，我們需要計(jì)算從1-6的每一種點(diǎn)數(shù)和剩下的n-1個(gè)骰子來(lái)計(jì)算點(diǎn)數(shù)和。
還是把n-1個(gè)那部分分成兩堆，上一輪的單獨(dú)骰子點(diǎn)數(shù)和這一輪的單獨(dú)骰子點(diǎn)數(shù)相加，然后再和剩下的n-2個(gè)骰子來(lái)計(jì)算點(diǎn)數(shù)和。
不難發(fā)現(xiàn)這是一種遞歸的思路。
定義一個(gè)長(zhǎng)度為6n-n+1的數(shù)組，和為s的點(diǎn)數(shù)出現(xiàn)的次數(shù)保存到數(shù)組的第s-n個(gè)元素里。
#include <iostream>
#include <cstdio>
using namespace std;
int g_maxValue = 6;
void Probability(int original, int current, int sum, int *pProbabilities)
{
if (current == 1)
{
pProbabilities[sum - original]++;
}
else
{
for (int i = 1; i <= g_maxValue; ++i)
{
Probability(original, current - 1, i + sum, pProbabilities);
}
}
}
void Probability(int number, int *pProbabilities)
{
for (int i = 1; i <= g_maxValue; ++i)
{
Probability(number, number, i, pProbabilities);
}
}
void PrintProbability(int number)
{
if (number < 1)
{
return;
}
int maxSum = number * g_maxValue;
int *pProbabilities = new int[maxSum - number + 1];
for (int i = number; i <= maxSum; ++i)
{
pProbabilities[i - number] = 0;
}
Probability(number, pProbabilities);
int total = pow( (double)g_maxValue, number);
for (int i = number; i <= maxSum; ++i)
{
double ratio = (double)pProbabilities[i - number] / total;
printf("%d: %e\n", i, ratio);
}
delete[] pProbabilities;
}
int main()
{
PrintProbability(6);
return 0;
}
思路二：
基于循環(huán)求骰子點(diǎn)數(shù)，時(shí)間性能好。
用兩個(gè)數(shù)組來(lái)存儲(chǔ)骰子點(diǎn)數(shù)的每一種出現(xiàn)的次數(shù)。
在一次循環(huán)中，第一個(gè)數(shù)組中的第n個(gè)數(shù)字表示骰子和為n出現(xiàn)的次數(shù)。
在下一次循環(huán)中我們加上一個(gè)新的骰子，此時(shí)和為n的骰子出現(xiàn)的次數(shù)應(yīng)該等于上一次循環(huán)中骰子點(diǎn)數(shù)和為n-1、n-2、n-3、n-4、n-5與n-6的次數(shù)的綜合，所以我們把另一個(gè)數(shù)組的第n個(gè)數(shù)字設(shè)為前一個(gè)數(shù)組對(duì)應(yīng)的第n-1、n-2、n-3、n-4、n-5與n-6之和。
#include <iostream>
#include <cstdio>
using namespace std;
int g_maxValue = 6;
void PrintProbability(int number)
{
if (number < 1)
{
return ;
}
int *pProbabilities[2];
pProbabilities[0] = new int[g_maxValue * number + 1];
pProbabilities[1] = new int[g_maxValue * number + 1];
for (int i = 0; i < g_maxValue; ++i)
{
pProbabilities[0][i] = 0;
pProbabilities[1][i] = 0;
}
int flag = 0;
for (int i = 1; i <= g_maxValue; ++i)
{
pProbabilities[flag][i] = 1;
}
for (int k = 2; k <= number; ++k)
{
for (int i = 0; i < k; ++i)
{
pProbabilities[1 - flag][i] = 0;
}
for (int i = k; i <= g_maxValue * k; ++i)
{
pProbabilities[1 - flag][i] = 0;
for (int j = 1; j <= i && j <= g_maxValue; ++j)
{
pProbabilities[1 - flag][i] += pProbabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = pow( (double)g_maxValue, number);
for (int i = number; i <= g_maxValue * number; ++i)
{
double ratio = (double)pProbabilities[flag][i] / total;
printf("%d: %e\n", i, ratio);
}
delete[] pProbabilities[0];
delete[] pProbabilities[1];
}
int main()
{
PrintProbability(6);
return 0;
}
股票的最大利潤(rùn)
題目：假設(shè)把某股票的價(jià)格按照時(shí)間先后順序存儲(chǔ)在數(shù)組中，請(qǐng)問(wèn)買(mǎi)賣該股票一次可獲得的最大利潤(rùn)是多少？例如，一只股票在某些時(shí)間節(jié)點(diǎn)的價(jià)格為{9,11,8,5,7,12,16,14}。如果我們能在價(jià)格為5的時(shí)候買(mǎi)入并在價(jià)格為16時(shí)賣出，則能獲得最大的利潤(rùn)為11.
我的：
//方法1：雙指針
int test(vector<int> in) {
int length = in.size();
if(length<2) return 0;
int mi = in[0];
int ma = INT_MIN;
for(int i = 1;i<length;i++){
mi = min(mi,in[i]);
ma = max(ma, in[i] - mi);
}
return ma;
}
//方法2：動(dòng)規(guī)，當(dāng)前這個(gè)東西的最優(yōu)解
int test(vector<int> in) {
int length = in.size();
if(length<2) return 0;
vector<int> flag(length,0);
int mi = in[0];
for(int i = 1;i<length;i++){
mi = min(mi,in[i]);
flag[i] = in[i]- mi>flag[i-1]?in[i]- mi:flag[i-1];
}
return flag[length-1];
}
劍指：方法1
背包問(wèn)題
題目：
（1）經(jīng)典的0-1背包問(wèn)題（無(wú)物品的價(jià)值）：
假設(shè)有一個(gè)能裝入容量為C的背包和n件重量分別為w1,w2,,...,wn的物品，能否從n件物品中挑選若干件恰好裝滿背包,要求找出所有滿足上述條件的解。
當(dāng)C=10,各件物品重量為{1,8,4,3,5,2}時(shí)，可以找到下列4組解：(1,4,3,2)、(1,4,5)、(8,2)和(3,5,2)。
我的：
//方法1：
void bag( vector<vector<int>>& result,vector<int> temp,int index, int sum ,int c, vector<int> in){
if(index>=in.size()){
if(sum==c) {
result.push_back(temp);
}
return;
}
if(sum+in[index]<=c){
temp.push_back(in[index]);
bag(result,temp,index+1, sum+in[index], c, in);
temp.pop_back();
}
bag(result,temp,index+1, sum, c, in);
}
vector<vector<int>> test(vector<int> in, int c) {
int length = in.size();
vector<vector<int>> result;
if(length<1) return result;
vector<int> temp;
bag(result,temp,0 , 0 , c,in);
return result;
}
（2）經(jīng)典的0-1背包問(wèn)題（有物品的價(jià)值）：
給定n種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？
我的:不對(duì)，不一定放滿，用的是回溯？，不是動(dòng)規(guī)，蠻力法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為：2^n
int ma = 0;
void bag( vector<vector<int>>& result,vector<int> temp,int index, int sum ,int valsum ,int c, vector<int> in,vector<int> in2){
if(index>=in.size()){
if(sum==c) {
if(ma<valsum){
ma= valsum;
result.push_back(temp);
}
}
return;
}
if(sum+in[index]<=c){
temp.push_back(in[index]);
bag(result,temp,index+1, sum+in[index],valsum+in2[index], c, in,in2);
temp.pop_back();
}
bag(result,temp,index+1, sum,valsum, c, in, in2);
}
vector<vector<int>> test(vector<int> in, vector<int> in2,int c) {
int length = in.size();
vector<vector<int>> result;
if(length<1) return result;
vector<int> temp;
bag(result,temp,0 , 0 ,0, c,in,in2);
return result;
}
動(dòng)規(guī)：
image.png
int test(vector<int> zhong, vector<int> value,int n, int c) {
int length = zhong.size();
if(length<1) return 0;
vector<vector<int>> flag(n+1 ,vector<int>(c+1));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=c;j++){
if(zhong[i-1]>j) flag[i][j] = flag[i-1][j];
else{
flag[i][j] = max(flag[i-1][j],flag[i-1][j-zhong[i-1]]+value[i-1]);
}
}
}
for(int i = n,j = C; i > 0; i--){ //找出放入的物品
if(V[i][j] > V[i-1][j]){
x[i-1] = 1;
j = j - a[i-1].wight;
}
else
x[i-1] = 0;
return flag[n][c];
}
236. Lowest Common Ancestor of a Binary Tree
題目：
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
image
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the binary tree.
bool dfs(TreeNode* root,TreeNode* p, vector<TreeNode*>& temp){
temp.push_back(root);
if(root == p) return true;
if(root->left!=NULL) {
if(dfs(root->left, p, temp)) return true;
temp.pop_back();
}
if(root->right!=NULL){
if(dfs(root->right, p, temp)) return true;
temp.pop_back();
}
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL||p==NULL||q==NULL) return NULL;
vector<TreeNode*> temp1;
vector<TreeNode*> temp2;
if(dfs(root, p, temp1)&&dfs(root, q, temp2)){
for(int i = 0;i<temp1.size()&&i<temp2.size();i++){
if(temp1[i]!=temp2[i]){
return temp1[i-1];
}
if(temp1[i]==p){
return temp1[i];
}
if(temp2[i]==q){
return temp2[i];
}
}
}
return NULL;
}
