📖 剑指offer刷题笔记(四)
本文记录了牛客网剑指offer JZ46-JZ67的刷题过程。
约瑟夫环
描述
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
题解
设杀人后的进行重排，被杀的人下一个人编号为 0 ，则有下一个被杀的人的原始编号 = （重排前被杀的人下一个人的编号 + 重排后下一个人被杀的编号）%（重排前的人数）。由于最后一个被杀的人在最后一轮一定是 0 号那么可以层层递推知道其最原始的编号。那么对于倒数第二个人被杀的时候的圈圈可以知道是第 M % 2 -1 号人被杀（从 0 起编），那么对于下一轮的编号则是 M % 2 （被杀的人下一个人的位置）+ 0 （重拍后下一个人被杀的编号），那么有递推公式（从最后一个人（胜利者）被杀起推：
代码
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
if ( n <= 0 )
return -1;
int lastRemain = 0;
for (int i = 2; i <= n; ++i)
lastRemain = (lastRemain + m) % i;
return lastRemain;
}
};限制条件求累加
描述
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
题解
不能循环，只能递归。递归需要结束条件，那么采用 双目逻辑运算符 && 前面为假则不对后面进行运算。
代码
class Solution {
public:
int Sum_Solution(int n) {
// 这也是表达式
n > 1 && (n += Sum_Solution(n-1));
return n;
}
};不用四则运算求加法
描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
题解
采用本位加异或，本位进位移位循环相加即可。
代码
class Solution {
public:
int Add(int num1, int num2) {
while (num2) {
int temp1 = num1 ^ num2;
int temp2 = (num1 & num2) << 1;
num1 = temp1;
num2 = temp2;
}
return num1;
}
};把字符串转换为一个整数
描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
题解
需要考虑一些边界情况，即最小的 int 的取负值仍然是它本身，采用减法可以规避这种情况。
代码
class Solution {
public:
int StrToInt(string str) {
if (str.length() == 0)
return 0;
int isNeg = str[0] == '-' ? -1 : 1;
int ret = 0, len = 0;
if (str[0] == '+' || str[0] == '-')
++len;
for (; len < str.length(); ++len) {
if (!isdigit(str[len]))
return 0;
ret = 10 * ret + isNeg * (str[len] - '0');
}
return ret;
}
};数组中任意一个相同的数
描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。
题解
可以采用哈希表，由于所有数字都是在[0, n-1]范围内的，所以可以直接另原数组充当哈希标记数组。
代码
class Solution {
public:
int duplicate(vector<int>& numbers) {
for (int i=0; i<numbers.size(); ) {
if (numbers[i] == i)
++i;
else {
if (numbers[numbers[i]] == numbers[i])
return numbers[i];
else
// 交换完之后应继续在本位判定
swap(numbers[i], numbers[numbers[i]]);
}
}
return -1;
}
};构建乘积数组
描述
给定一个数组,请构建一个数组,其中B中的元素。不能使用除法。（注意：规定，;）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
题解
分别迭代求前一部分乘积和后一部分乘积。后一部分乘积采用一个临时变量保存。
代码
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> B(A.size(),1);
// 算前一部分 A_0*A_1*...*A_i-1
for(int i = 1; i < A.size(); ++i) {
B[i] = A[i-1] * B[i-1];
}
// 设置一个变量保存后一部分
// 计算 A_n-1*A_n-2*...*A_i+1
int temp = 1;
for(int i=A.size()-2;i>=0;i--){
temp *= A[i+1];
B[i] *= temp;
}
return B;
}
};正则表达式匹配*
描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
题解
采用动态规划，注意这里其中有空串可能匹配也可能不匹配，先特判初始条件后递归。
初始情况，即模式串与字符串有一个为空串的匹配情况。
- 模式串和字符串都为空串则一定匹配
- 模式串为空串而字符串不为空串则一定不匹配
- 字符串为空而模式串不为空则需考虑所有匹配 0 次的情况，只有模式串如 的情况才能匹配。
再考虑递推，令 表示为字符串前位与模式串前位匹配，那么有
当模式串为普通字符时（即不为 * 号，. 可看作普通字符处理为匹配任意字符）
当模式串出现 * 时考虑几种情况：
- ch * 匹配 0 次，则观察
- ch * 匹配 1 次，则观察
- ch * 匹配 1 次及以上，则观察
代码
class Solution {
public:
bool match(string str, string pattern) {
int len1 = str.length();
int len2 = pattern.length();
vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
dp[0][0] = true;
if (len2)
dp[0][1] = false;
for (int j=2; j<len2+1; ++j) {
if (pattern[j-1]=='*')
dp[0][j] = dp[0][j-2];
}
for (int i=1; i<len1 + 1; ++i) {
for (int j = 1; j < len2 + 1; ++j) {
if (pattern[j-1] == '*')
dp[i][j] = dp[i][j-2] || dp[i][j-1] || equal(str[i-1], pattern[j-2]) && dp[i-1][j];
else
dp[i][j] = dp[i-1][j-1] && equal(str[i-1], pattern[j-1]);
}
}
return dp[len1][len2];
}
bool equal(char c, char patChar){
return patChar == '.' || c == patChar;
}
};表示数值的字符串
描述
请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。
科学计数法的数字(按顺序）可以分成以下几个部分:
若干空格
一个整数或者小数
（可选）一个 'e' 或 'E' ，后面跟着一个整数(可正可负)
若干空格
小数（按顺序）可以分成以下几个部分：
若干空格
（可选）一个符号字符（'+' 或 '-'）
可能是以下描述格式之一:
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
若干空格
整数（按顺序）可以分成以下几个部分：
若干空格
（可选）一个符号字符（'+' 或 '-')
至少一位数字
若干空格
题解
采用有限状态机，难点在于状态机状态和转移方向。具体实现见代码注释。
代码
class Solution {
public:
bool isNumeric(string str) {
// 空格 - ' ' 数字 - 'd' e/E - 'e' +/- - 's'
// 0 1 2 3 4 5 6 7 8 9
// (空格)(+/-)(数字)(.)|(数字 .)|(数字)(e/E)(+/-)(数字)(空格)
// 状态 0
// - 空格 至 0
// - +-号 至 1
// - 数字 至 2
// - . 至 3
unordered_map<char, int> state_0;
state_0.insert({' ', 0});
state_0.insert({'s', 1});
state_0.insert({'d', 2});
state_0.insert({'.', 3});
// 状态 1
// - 数字 至 2
// - . 至 3
unordered_map<char, int> state_1;
state_1.insert({'d', 2});
state_1.insert({'.', 3});
// 状态 2 ok
// - 数字 至2
// - . 至4
// - e 至6
// - 空格 至9
unordered_map<char, int> state_2;
state_2.insert({'d', 2});
state_2.insert({'.', 4});
state_2.insert({'e', 6});
state_2.insert({' ', 9});
// 状态 3
// - 数字 至5
unordered_map<char, int> state_3;
state_3.insert({'d', 5});
// 状态 4 ok
// - 数字 至5
// - e 至6
// - 空格 至9
unordered_map<char, int> state_4;
state_4.insert({'d', 5});
state_4.insert({'e', 6});
state_4.insert({' ', 9});
// 状态 5 ok
// 数字 至5
// - e 至6
// - 空格 至9
unordered_map<char, int> state_5;
state_5.insert({'d', 5});
state_5.insert({'e', 6});
state_5.insert({' ', 9});
// 状态 6
// - +-号 至7
// - 数字 至8
unordered_map<char, int> state_6;
state_6.insert({'s', 7});
state_6.insert({'d', 8});
// 状态 7
// - 数字 至8
unordered_map<char, int> state_7;
state_7.insert({'d', 8});
// 状态 8 ok
// - 数字 至8
// - 空格 至9
unordered_map<char, int> state_8;
state_8.insert({'d', 8});
state_8.insert({' ', 9});
// 状态 9 ok
// - 空格 至9
unordered_map<char, int> state_9;
state_9.insert({' ', 9});
int stateIndex = 0, curChar;
unordered_map<char, int> state[] =
{state_0, state_1, state_2, state_3, state_4, state_5, state_6, state_7, state_8, state_9};
for (char ch: str) {
if (ch == ' ') {
curChar = ' ';
} else if (ch == '.') {
curChar = '.';
} else if (ch == '+' || ch == '-') {
curChar = 's';
} else if (ch == 'e' || ch == 'E') {
curChar = 'e';
} else if (ch <= '9' && ch >='0') {
curChar = 'd';
} else {
curChar = '?';
}
auto nextStatePtr = state[stateIndex].find(curChar);
if (nextStatePtr == state[stateIndex].end()) {
return false;
} else {
stateIndex = nextStatePtr->second;
}
}
array<int, 5> caseOK{2, 4, 5, 8, 9};
if (find(caseOK.begin(), caseOK.end(), stateIndex) != caseOK.end())
return true;
else return false;
}
};字符流中第一个不重复的字符
描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
题解
采用两个哈希集合（已出现和出现多次）和一个队列实现。
当出现一个字符时，先验证是否已经出现，是则插入【多次出现】哈希表中，否则插入【已出现】哈希表中，插入队列。
当要取出第一个时，需从哈希表中验证出队（若已出现多次则出队直到为空或取到只出现一次的）再取出。
代码
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch) {
if (appeared.find(ch) == appeared.end()) {
appear.push(ch);
appeared.insert(ch);
}
else
appeared_2.insert(ch);
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce() {
while (!appear.empty() && appeared_2.find(appear.front())!=appeared.end())
appear.pop();
if (appear.empty())
return '#';
else
return appear.front();
}
private:
unordered_set<char> appeared;
unordered_set<char> appeared_2;
queue<char> appear;
};链表中环的入口节点
描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null
题解
+++ 哈希表
采用哈希表，遍历链表，查找是否有相同节点，若有则输出，否则输出NULL
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
while (pHead != nullptr && appearedListSet.find(pHead) == appearedListSet.end()){
appearedListSet.insert(pHead);
pHead = pHead->next;
}
return pHead;
}
private:
unordered_set<ListNode*> appearedListSet;
};+++
+++ 双指针
用两个指针，快指针一下走两步，慢指针一下走一步。如果有环，则必定会相遇。设相遇时慢指针走了 步，快指针走了 步，则相遇时差值也是慢指针走的步数为环的长度()的倍数()。即有此时慢指针走了 步，再走头节点到入口节点的步数()即为入口节点共步，此时另一个指针走步也到入口节点即相遇。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
ListNode *fast = pHead, *slow = pHead;
while (fast && slow) {
slow = slow->next;
if (fast->next) {
fast = fast->next->next;
} else return nullptr;
if (fast == slow) {
break;
}
}
if (fast && slow) {
fast = pHead;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
return nullptr;
}
};+++
删除链表中重复的结点
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
题解
设置虚拟的头指针。另设三个指针 pre, cur, next ，初始分别指向虚拟头结点、表头结点、表头结点下一结点（如果有的话）。设置一个比较布尔值，令 cur 与 next 比较，若相同，持续移动 next 直到不同处，令 pre 结点的指针域指向 next ，更新 pre 为 next，cur、next类推；若不相同，三者同时移动。移动时注意判空指针。
代码
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if (pHead==nullptr || pHead->next==nullptr)
return pHead;
ListNode headNode(-1);
headNode.next = pHead;
ListNode *prePtr = &headNode;
ListNode *curPtr = pHead;
ListNode *nextPtr = pHead->next;
while (nextPtr) {
bool hasSame = false;
while (nextPtr && curPtr->val == nextPtr->val) {
if (!hasSame)
hasSame = true;
nextPtr = nextPtr->next;
}
if (hasSame){
prePtr->next = nextPtr;
curPtr = nextPtr;
if (curPtr)
nextPtr = curPtr->next;
}
else{
prePtr = prePtr->next;
curPtr = curPtr->next;
if(nextPtr)
nextPtr = nextPtr->next;
}
}
return headNode.next;
}
};二叉树中序遍历的下一个结点
描述
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
题解
如果有右孩子，则是其右孩子的最左孩子 如果没有右孩子：
- 自己是左孩子，则指向其父节点
- 自己是右孩子，则寻找其父辈为左孩子的节点，找不到则为空
- 自己不是孩子又没有右孩子，则指向空
代码
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
if (!pNode)
return nullptr;
// 如果有右孩子，则是其右孩子的最左孩子
// 如果没有右孩子：
// - 自己是左孩子，则指向其父节点
// - 自己是右孩子，则寻找其父辈为左孩子的节点，找不到则为空
// - 自己不是孩子又没有右孩子，则指向空
if (pNode->right) {
pNode = pNode->right;
while (pNode->left)
pNode = pNode->left;
return pNode;
} else {
if (!pNode->next) {
return nullptr;
} else {
if (pNode == pNode->next->left) {
return pNode->next;
} else {
pNode = pNode->next;
while (pNode->next && pNode->next->right == pNode)
pNode = pNode->next;
return pNode->next;
}
}
}
}
};对称的二叉树
描述
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
题解
采用递归，递归层次是将两个树的左右子树交替递归。
代码
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot) {
if (!pRoot)
return true;
return isMirrorTree(pRoot->left, pRoot->right);
}
bool isMirrorTree (TreeNode* pRoot1, TreeNode* pRoot2) {
if ((pRoot1 && !pRoot2) || (!pRoot1 && pRoot2))
return false;
if (!pRoot1 && !pRoot2)
return true;
if (pRoot1->val != pRoot2->val)
return false;
return isMirrorTree(pRoot1->left, pRoot2->right) && isMirrorTree(pRoot1->right, pRoot2->left);
}
};按之字形打印二叉树
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
题解
设置两个栈，一个栈保存从左往右的结点，一个栈保存从右往左的结点，交替入栈出栈。
让第一个栈表示从左往右遍历的结点，让第二个栈保存从右往左遍历的结点。
那么有：
- 初始情况：根节点入第一个栈。
- 栈 1 非空：栈 1 出栈遍历至空，左子树、右子树依次进栈 2，这样能保证栈 2 先进后出从右往左遍历。
- 栈 2 非空：栈 2 出栈遍历至空，右子树、左子树依次进栈 1 ，这样能保证栈 1 先进后出从左往右遍历。
- 循环判断 2，3 直至两个栈都为空结束。
代码
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> quence;
if (pRoot)
sPrint1.push(pRoot);
while (!sPrint1.empty() || !sPrint2.empty()) {
vector<int> temp;
if (!sPrint1.empty()) {
while (!sPrint1.empty()) {
TreeNode* top = sPrint1.top();
sPrint1.pop();
temp.push_back(top->val);
if (top->left)
sPrint2.push(top->left);
if (top->right)
sPrint2.push(top->right);
}
} else if (!sPrint2.empty()) {
while (!sPrint2.empty()) {
TreeNode* top = sPrint2.top();
sPrint2.pop();
temp.push_back(top->val);
if (top->right)
sPrint1.push(top->right);
if (top->left)
sPrint1.push(top->left);
}
}
quence.push_back(temp);
}
return quence;
}
private:
stack<TreeNode*> sPrint1;
stack<TreeNode*> sPrint2;
};把二叉树打印成多行
描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
题解
此题是二叉树层序遍历的变种，可以采取如上题一样的方法，设置两个队列交替入队。
代码
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> ret;
if (pRoot)
queue1.push(pRoot);
while (!queue1.empty() || !queue2.empty()) {
vector<int> temp;
if (!queue1.empty()) {
while (!queue1.empty()) {
TreeNode* ptr = queue1.front();
queue1.pop();
temp.push_back(ptr->val);
if (ptr->left)
queue2.push(ptr->left);
if (ptr->right)
queue2.push(ptr->right);
}
} else if (!queue2.empty()) {
while (!queue2.empty()) {
TreeNode* ptr = queue2.front();
queue2.pop();
temp.push_back(ptr->val);
if (ptr->left)
queue1.push(ptr->left);
if (ptr->right)
queue1.push(ptr->right);
}
}
ret.push_back(temp);
}
return ret;
}
private:
queue<TreeNode*> queue1;
queue<TreeNode*> queue2;
};序列化二叉树
描述
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
题解
这里采取先根遍历策略保存，令根不为空的二叉树的结点值加入序列，然后递归左子树、右子树。根为空则令 ‘#’ 加入序列，每个字符均用空格隔开。这里反序列化用到了 stringstream ，递归反序列化。
代码
class Solution {
public:
char* Serialize(TreeNode* root) {
string *pStr = new string("");
preOrder(root, *pStr);
return const_cast<char*>(pStr->c_str());
}
TreeNode* Deserialize(char* str) {
stringstream sstr(str);
return dePreOrder(sstr);
}
private:
void preOrder (TreeNode* root, string &str) {
if (!root)
str += "# ";
else {
str += to_string(root->val);
str += " ";
preOrder(root->left, str);
preOrder(root->right, str);
}
}
TreeNode* dePreOrder (stringstream &sstr) {
string str("");
sstr >> str;
if (str=="#")
return nullptr;
else {
TreeNode *root = new TreeNode(stoi(str));
root->left = dePreOrder(sstr);
root->right = dePreOrder(sstr);
return root;
}
}
};排序二叉树第 k 小的结点
描述
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
题解
即中序遍历排序二叉树，设置变量 cnt 计数即可。
代码
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k) {
cnt = k;
kTh = nullptr;
inOrder(pRoot);
return kTh;
}
void inOrder(TreeNode* pRoot) {
if (cnt < 0 || !pRoot)
return;
if (pRoot->left)
inOrder(pRoot->left);
--cnt;
if (cnt == 0) {
kTh = pRoot;
return;
}
if (pRoot->right)
inOrder(pRoot->right);
}
private:
TreeNode* kTh = nullptr;
int cnt = 0;
};class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k) {
if (pRoot) {
sNode.push(pRoot);
}
while (!sNode.empty()) {
if (k < 0) {
return nullptr;
}
if (hasAppeared.find(sNode.top()) == hasAppeared.end()) {
// 对标志位的判断需要立即更新标记，注意前后次序
hasAppeared.insert(sNode.top());
if (sNode.top()->left) {
sNode.push(sNode.top()->left);
}
} else {
--k;
TreeNode* temp = sNode.top();
hasAppeared.erase(temp);
sNode.pop();
if (k == 0) {
return temp;
}
if (temp->right) {
sNode.push(temp->right);
}
}
}
return nullptr;
}
private:
unordered_set<TreeNode*> hasAppeared;
stack<TreeNode*> sNode;
};数据流的中位数
描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
题解
采用两个堆，一个大顶堆为较小数的集合，一个小顶堆为较大数的集合。
插入一个数时，大顶堆为空或者小于大顶堆的顶部元素插入大顶堆，否则加入小顶堆。
再判断左右两个堆的数量，移动元素保持左堆数量与右堆一致或大一。
中位数是左堆右堆堆顶的平均值（偶数）或左堆堆顶（奇数）。
代码
class Solution {
public:
void Insert(int num) {
if (left.empty() || num < left.top()) {
left.push(num);
} else right.push(num);
if (left.size() > right.size() + 1) {
right.push(left.top());
left.pop();
} else if (right.size() > left.size()) {
left.push(right.top());
right.pop();
}
}
double GetMedian() {
return left.size() > right.size() ? left.top() : (left.top()+right.top())/2.;
}
private:
priority_queue<int> left;
priority_queue<int, vector<int>, greater<>> right;
};滑动窗口的最大值 *
描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
题解
采用双端队列：
- 队列为空时，添加元素进入队列
- 队列不为空时，当前元素与未过期的队列头（如果过期则从头部删去，可保存下标）比较，若比队列头大替换队列头（此时原队列头下标比新的小，以后这个元素都不可能最大），若比队列头小，则比较队列尾（同样的，如果比队列尾大则替换队列尾，比队列尾小则添加至队列尾）。这个双端队列保证了一个递减序列。
代码
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> ret;
if (size > num.size() || size == 0)
return ret;
for (int i = 0; i < num.size(); ++i) {
// 先判断是否过期
// 注意题目的 size 是 unsigned 型如果直接相减会转换至无符号型导致死循环
while (!dqMax.empty() && dqMax.front() <= static_cast<int>(i - size)) {
dqMax.pop_front();
}
// 没有元素则添加
if (dqMax.empty()) {
dqMax.push_back(i);
}
if (num[i] >= num[dqMax.front()]) {
dqMax.front() = i;
} else {
if (num[i] >= num[dqMax.back()]) {
dqMax.back() = i;
} else {
dqMax.push_back(i);
}
}
if (i >= size - 1) {
ret.push_back(num[dqMax.front()]);
}
}
return ret;
}
private:
deque<int> dqMax;
};矩阵中的路径
描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
题解
采用遍历 + 回溯的方法递归。
代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
if (matrix.empty() || matrix[0].empty() || word.empty())
return false;
vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
for (int i=0; i < matrix.size(); ++i) {
for(int j=0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == word.at(0) && travel(matrix, visited, word, 0, i, j))
return true;
}
}
return false;
}
private:
bool travel(vector<vector<char> >& matrix, vector<vector<bool> >& visited, string word, int rank, int i, int j) {
if (matrix[i][j] != word.at(rank))
return false;
if (rank == word.length()-1)
return true;
visited[i][j] = true;
if (i + 1 < matrix.size() && visited[i+1][j] == false && travel(matrix, visited, word, rank + 1, i + 1, j))
return true;
if (i - 1 >= 0 && visited[i - 1][j] == false && travel(matrix, visited, word, rank + 1, i - 1, j))
return true;
if (j + 1 < matrix[0].size() && visited[i][j + 1]==false && travel(matrix, visited, word, rank + 1, i, j + 1))
return true;
if (j - 1 >= 0 && visited[i][j-1] == false && travel(matrix, visited, word, rank + 1, i, j - 1))
return true;
visited[i][j] = false;
return false;
}
};机器人的行动范围
描述
地上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如，当threshold为18时，机器人能够进入方格[35,37]，因为3+5+3+7 = 18。但是，它不能进入方格[35,38]，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
题解
递归，这里不需要回溯，但需要访问标记（否则重复计数）
广度优先与非递归待实现。
代码
class Solution {
public:
int movingCount(int threshold, int rows, int cols) {
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
return dfs(visited, threshold, rows, cols, 0, 0);
}
int dfs(vector<vector<bool>> &visited, int threshold, int rows, int cols, int i, int j) {
// 超出界限或访问过返回 0
if (i < 0 || j < 0 || i >= rows || j >= cols || visited[i][j] || !leqThanThreshold(i, j, threshold))
return 0;
visited[i][j] = true;
// 在往右和往下的基础上加 1
return 1 + dfs(visited, threshold, rows, cols, i + 1, j) + dfs(visited, threshold, rows, cols, i, j + 1);
}
int leqThanThreshold (int i, int j, int threshold) {
int sum = 0;
while (i) {
sum += i % 10;
i /= 10;
}
while (j) {
sum += j % 10;
j /= 10;
}
return sum <= threshold;
}
};剪绳子
描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
题解
采用动态规划。令 表示绳长为 可以剪成的最大乘积数。
先考虑特判情况和初始情况.
当绳子较短的时候如绳长为 2，3时，它不剪比剪了的乘积要长，但由于题目限制，他不能不剪（但是考虑递推情况时是已经剪过一次，对于低阶段来说可以不剪）所以产生了特别判定情况。
代码
class Solution {
public:
int cutRope(int number) {
// 特判
if (number==2 || number==3)
return number-1;
vector<int> dp(number + 1, 1);
// 初值
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// 迭代求最大
for (int i = 4; i <= number; ++i) {
int max = dp[i-1];
for (int j = 2; j < i; ++j) {
if (j * dp[i-j] > max)
max= j * dp[i-j];
}
dp[i] = max;
}
return dp[number];
}
};