建模的第一步是選擇合理的數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)問(wèn)題。實(shí)際生活中的問(wèn)題千變?nèi)f化，但是數(shù)據(jù)結(jié)構(gòu)就只有固定的幾種。選擇合理的數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)問(wèn)題，也就是建立模型。
建模的第二步是分析模型的內(nèi)在規(guī)律，并用變成語(yǔ)言表達(dá)其規(guī)律。
面試題43：n個(gè)骰（tou二聲）子的點(diǎn)數(shù)
把n個(gè)骰子扔在地上，所有的骰子朝上一面的點(diǎn)數(shù)和為s。輸入n，打印出s的所有的可能值出現(xiàn)的概率
leetcode鏈接 https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/class Solution { public: vector<double> twoSum(int n) { vector<double> result; if (n < 1) { return result; } // 為了好交替調(diào)用，將兩個(gè)矩陣定義為二維矩陣 int* sum[2]; sum[0] = new int[n*6 + 1]; // 所有可能和的總數(shù)，每位存放的就是該位對(duì)應(yīng)和出現(xiàn)次數(shù) sum[1] = new int[n*6 + 1]; int flag = 0; for(int i = 0; i < n*6 + 1; i++) { sum[0][i] = 0; sum[1][i] = 0; } for(int i = 1; i <= 6; i++) { sum[0][i] = 1; // 只有一個(gè)骰子的情況 } for(int k = 2; k <= n; k++) { for(int i = 0; i < k; i++) // k個(gè)骰子最小和是k，因此小于k是不可能了 { sum[1-flag][i] = 0; } for(int i = k ; i < n*6 + 1; i++) // 當(dāng)點(diǎn)數(shù)大于k，考慮當(dāng)前骰子點(diǎn)數(shù)和=上一次骰子點(diǎn)數(shù)和-1....前一次骰子點(diǎn)數(shù)和-6 { sum[1-flag][i] = 0; for(int j = 1; j <= 6 && j <= i; j++) { sum[1-flag][i] += sum[flag][i-j]; } } flag = 1 -flag; } double total = pow(6, n); for(int i = n; i <= 6*n; i++) { result.push_back(sum[flag][i] / total); } return result; } };
解題思路：
思路1：全排列。建立數(shù)組，每次排列后sum=n，則數(shù)組第n位+1，最后循環(huán)數(shù)組，計(jì)算每一個(gè)非零位概率。全排列用遞歸，會(huì)超時(shí)。這里遞歸思路用的是每次固定數(shù)組中一位，更正規(guī)一點(diǎn)的思想是用回溯。定義一個(gè)棧，每次循環(huán)push進(jìn)當(dāng)前位固定好的元素，遞歸調(diào)用n-1函數(shù)，函數(shù)退出后將push進(jìn)元素pop出來(lái)。
class Solution {
public:
int all = 0;
void fullPer(int* arr, map<int, int>& sum, int index, int n)
{
if (index >= n - 1)
{
all++;
int tmp = 0;
for(int i = 0; i < n; i++)
{
// cout << arr[i] << endl;
tmp = tmp + arr[i];
}
sum[tmp]++;
return;
}
for(int i = 1; i < 7; i++)
{
arr[index+1] = i;
fullPer(arr, sum, index+1, n);
}
return;
}
vector<double> twoSum(int n) {
vector<double> result;
map<int, int> sum;
int *arr = new int[n];
for(int i = 1; i < 7; i++)
{
arr[0] = i;
fullPer(arr, sum, 0, n);
}
map<int, int>::iterator iter = sum.begin();
while(iter != sum.end())
{
result.push_back(iter->second / double(all));
iter++;
}
return result;
}
};
思路2：用兩個(gè)數(shù)組來(lái)存儲(chǔ)骰子點(diǎn)數(shù)的每一個(gè)總數(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-6的和，所以我們把另一個(gè)數(shù)組的n位設(shè)置為n-1，n-2...n-6的和。最后被循環(huán)的數(shù)組就代表全排列后的結(jié)果。
class Solution {
public:
vector<double> twoSum(int n) {
vector<double> result;
if (n < 1)
{
return result;
}
// 為了好交替調(diào)用，將兩個(gè)矩陣定義為二維矩陣
int* sum[2];
sum[0] = new int[n*6 + 1]; // 所有可能和的總數(shù)，每位存放的就是該位對(duì)應(yīng)和出現(xiàn)次數(shù)
sum[1] = new int[n*6 + 1];
int flag = 0;
for(int i = 0; i < n*6 + 1; i++)
{
sum[0][i] = 0;
sum[1][i] = 0;
}
for(int i = 1; i <= 6; i++)
{
sum[0][i] = 1; // 只有一個(gè)骰子的情況
}
for(int k = 2; k <= n; k++)
{
for(int i = 0; i < k; i++) // k個(gè)骰子最小和是k，因此小于k是不可能了
{
sum[1-flag][i] = 0;
}
for(int i = k ; i < n*6 + 1; i++) // 當(dāng)點(diǎn)數(shù)大于k，考慮當(dāng)前骰子點(diǎn)數(shù)和=上一次骰子點(diǎn)數(shù)和-1....前一次骰子點(diǎn)數(shù)和-6
{
sum[1-flag][i] = 0;
for(int j = 1; j <= 6 && j <= i; j++)
{
sum[1-flag][i] += sum[flag][i-j];
}
}
flag = 1 -flag;
}
double total = pow(6, n);
for(int i = n; i <= 6*n; i++)
{
result.push_back(sum[flag][i] / total);
}
return result;
}
};
面試題44：撲克牌的順子
從撲克牌中隨機(jī)抽5張牌，判斷是不是順子。撲克牌中2-10為數(shù)字本身，A為1，J為11，Q為12，K為13。而大王小王可以看做任意數(shù)字。
leetcode鏈接 https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/class Solution { public: bool isStraight(vector<int>& nums) { if (nums.size() == 0) { return false; } int max = nums[0]; int min = nums[0]; int zeroNum = 0; vector<int> tmpVec; for(int i = 0; i < nums.size(); i++) { int tmp; if (nums[i] == 0) { zeroNum++; continue; } if (nums[i] == 'A') { tmp = 1; } else if (nums[i] == 'J') { tmp = 11; } else if (nums[i] == 'Q') { tmp = 12; } else if (nums[i] == 'K') { tmp = 13; } else { tmp = nums[i]; } if (find(tmpVec.begin(), tmpVec.end(), tmp) == tmpVec.end()) { tmpVec.push_back(tmp); } else{ return false; } if (tmp < min || min == 0) { // cout << "min: " << min << endl; min = tmp; } if (tmp > max || max == 0) { max = tmp; } } // cout << "max: " << max << " min: " << min << " zeroNum: " << zeroNum << " size: " << nums.size() << endl; return (max - min + 1) <= nums.size(); } };
解題思路：由于大小王可以是任意數(shù)，將其設(shè)為0，方便操作 1）數(shù)組排序 2）記錄數(shù)組中0的個(gè)數(shù)，記錄數(shù)組最大值-非零最小值的差 + 1=數(shù)組長(zhǎng)度+n，若n=0的個(gè)數(shù)，則為順子，否則，不是。
轉(zhuǎn)變下思路，感覺(jué)不排序也可以，遍歷，最大，最小值，無(wú)相等元素，若最大值-最小值+1 <= 數(shù)組長(zhǎng)度，則為順子。
面試題45：圓圈中最后剩下的數(shù)字（約瑟夫環(huán)）
0，1....n-1這n個(gè)數(shù)字排成一個(gè)圓圈，從數(shù)字0開(kāi)始，每次從圓圈中刪除第m個(gè)數(shù)字，求圓圈中剩余的最后一個(gè)數(shù)字。
leetcode鏈接 https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/class Solution { public: int lastRemaining(int n, int m) { if (n == 0) { return 0; } if (m == 1) // 總是刪除當(dāng)前節(jié)點(diǎn)，最后獲得的一定是最后一個(gè)節(jié)點(diǎn) { return n - 1; } // 遞歸寫(xiě)法,效率低 // return (lastRemaining(n-1, m) + m) % n; int* result = new int[n]; result[0] = 0; for(int i = 1; i < n; i++) { result[i] = (result[i-1] + m) % (i+1); // cout << i << " " << result[i] << endl; } return result[n-1]; } };
解題思路：
解法一：經(jīng)典解法。用環(huán)形鏈表模擬操作過(guò)程。超時(shí)，心塞。注意m=1的情況。
class Solution {
public:
struct ListNode{
int val;
ListNode* next;
ListNode(int val) {this->val = val; next = NULL;}
};
int lastRemaining(int n, int m) {
if (n == 0)
{
return 0;
}
m = m % n;
ListNode* head = new ListNode(0);
ListNode* tmp = head;
// 構(gòu)建一個(gè)環(huán)形鏈表
for(int i = 1; i < n; i++)
{
ListNode* h = new ListNode(i);
tmp->next = h;
tmp = h;
}
tmp->next = head;
/* 驗(yàn)證鏈表構(gòu)建是否正確
tmp = head;
for(int i = 0; i < n + 1; i++)
{
cout << tmp->val << " ";
tmp = tmp->next;
}
cout << endl;
*/
if (m == 1) // 一直在刪除當(dāng)前節(jié)點(diǎn)，剩余的一定是尾節(jié)點(diǎn)
{
return tmp->val;
}
tmp = head;
while(tmp->next != tmp)
{
for(int i = 1; i < m - 1; i++)
{
tmp = tmp->next;
}
// cout << tmp->val << endl;
ListNode* del = tmp->next;
tmp->next = tmp->next->next;
delete del;
tmp = tmp->next;
}
return tmp->val;
}
};
解法二：找規(guī)律，(自己推一推）最終歸納出在n個(gè)數(shù)中刪除第m個(gè)數(shù)的最終剩余元素的關(guān)系是
參考鏈接https://blog.csdn.net/u011500062/article/details/72855826
思路上就是，用f(n,m)代表n個(gè)人殺掉第m個(gè)人之后的幸存者下標(biāo)。那個(gè)f(n-1,m）就是殺掉一個(gè)人之后，當(dāng)前幸存者的下標(biāo)移動(dòng)到的位置。因?yàn)橄乱淮斡?jì)數(shù)是從被殺掉的下一個(gè)開(kāi)始，因此就是從m+1開(kāi)始記。因此幸存者的下標(biāo)往前移動(dòng)了m位。反推，則得到f(n,m) = f(n-1,m) + m。因?yàn)橄聵?biāo)可能存在越界，因此更改為f(n,m)=[f(n-1,m) + m] % n。
過(guò)程
class Solution {
public:
int lastRemaining(int n, int m) {
if (n == 0)
{
return 0;
}
if (m == 1) // 總是刪除當(dāng)前節(jié)點(diǎn)，最后獲得的一定是最后一個(gè)節(jié)點(diǎn)
{
return n - 1;
}
// 遞歸寫(xiě)法,效率低
// return (lastRemaining(n-1, m) + m) % n;
int* result = new int[n];
result[0] = 0;
for(int i = 1; i < n; i++)
{
result[i] = (result[i-1] + m) % (i+1);
// cout << i << " " << result[i] << endl;
}
return result[n-1];
}
};
