剑指Offer题单及题解
题目顺序为牛客上剑指Offer专题
JZ3、数组中重复的数字
分析
可以直接对数组进行排序,通过判断首末数字大小来判断数字越界情况,注意数组为空的情况。发现 \(0 \leq nums[i] \leq n - 1\), 因此直接开一个数组判断是否有重复数字即可,返回第一个重复数字。
代码实现
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = size(nums);
std::sort(nums.begin(), nums.end());
if (n == 0 || nums.back() > n || nums[0] < 0) {
return -1;
}
std::vector<int> buc(n);
for (auto x : nums) {
buc[x] += 1;
if (buc[x] > 1) {
return x;
}
}
return -1;
}
};
JZ5。替换空格
分析
直接调用std::string
中的replace
方法替换
即可。
代码实现
class Solution {
public:
string replaceSpaces(string &str) {
for (int i = 0; i < size(str); ++i) {
if (str[i] == ' ') {
str.replace(str.begin() + i, str.begin() + i + 1, "%20");
}
}
return str;
}
};
JZ6、从尾到头打印链表
分析
直接遍历链表,将链表中的数据存入vector
,最后reverse
一下返回即可。
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
std::vector<int> ans;
while (head != nullptr) {
ans.push_back(head->val);
head = head->next;
}
std::reverse(ans.begin(), ans.end());
return ans;
}
};
JZ7、二叉树的下一个节点
分析
可以分为两种情况讨论:
- 情况1:当前节点的右节点不为空,则下一个节点为其右子树的左子树的最下面的节点
- 情况2:当前节点的右节点为空,则下一个节点为其右子树祖先节点第一个存在右子树节点
代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode *father;
* TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
if (p->right != nullptr) {
p = p->right;
while (p->left != nullptr) {
p = p->left;
}
return p;
}
while (p->father != nullptr && p->father->right == p) {
p = p->father;
}
return p->father;
}
};
未更完...
标签:TreeNode,nums,int,题解,Offer,str,return,合集,节点 From: https://www.cnblogs.com/sleeeeeping/p/18330099