2024年1月30日力扣题目训练
2024年1月30日第六天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。对于一些经典题目的掌握还是有点小问题，需要利用我们已知的性质去完成。
367. 有效的完全平方数
链接: 完全平方数
难度： 简单
题目：
运行示例：
思路：
这个题试求平方，但是不能用自带的函数，需要自己写，我观察到一个数的平方根一般都小于等于这个数的一半，我的思路就是基于这一点完成的。官方的话就是采用二分法，因为这个数的平方根一定位于某一区间内，用二分法进行查找。还有其他方法大家可以点击链接查看。
代码：
class Solution {
public:
bool isPerfectSquare(int num) {
if( num == 1) return true;
for(long i = 1; i <= num/2; i++){
if(i*i == num) return true;
if(i*i > num) return false;
}
return false;
}
};
374. 猜数字大小
链接: 猜数字
难度： 简单
题目：
运行示例：
思路：
这也是在一个区间里找数的问题，所以我采用了二分法。
代码：
class Solution {
public:
int guessNumber(int n) {
int left = 1;
int right = n;
while(left <= right){
int mid = left + (right - left) / 2;
if(guess(mid) == 0) return mid;
else if(guess(mid) == -1){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return -1;
}
};
383. 赎金信
链接: 赎金信
难度： 简单
题目：
运行示例：
思路：
这道题就是看一个字符串中的字母是否能组成另一个字符串，我采用哈希表记录字母出现次数，然后进行对比。
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if(ransomNote.size() > magazine.size()) return false;
unordered_map<char,int> res;
for(int i = 0; i < magazine.size(); i++){
res[magazine[i]]++;
}
for(int i = 0; i < ransomNote.size(); i++){
if(res[ransomNote[i]] == 0) return false;
else res[ransomNote[i]]--;
}
return true;
}
};
99. 恢复二叉搜索树
链接: 二叉搜索树
难度： 中等
题目：
运行示例：
思路：
对于二叉搜索树，如果对其进行中序遍历，得到的值序列是递增有序的。不过我知道这条性质，但是不知道怎么搞，所以我看了官方的方法，记录这两位置然后进行交换。
代码：
class Solution {
public:
void inorder(TreeNode* root, vector<int>& nums){
if(root == NULL) return;
inorder(root->left,nums);
nums.push_back(root->val);
inorder(root->right,nums);
}
void recover(TreeNode* root, int x, int y, int count){
if(root != NULL){
cout<< root->val <<endl;
if(root->val == x || root->val == y){
root->val = (root->val == x)? y:x;
count--;
if(count <= 0) return;
}
recover(root->left,x,y,count);
recover(root->right,x,y,count);
}
}
void recoverTree(TreeNode* root) {
if(root == NULL) return;
vector<int> nums;
inorder(root,nums);
int index1 = -1;
int index2 = -1;
for(int i = 0; i < nums.size()-1; i++){
if(nums[i+1] < nums[i]){
index2 = i+1;
if(index1 == -1){
index1 = i;
}else{
break;
}
}
}
int x = nums[index1];
int y = nums[index2];
recover(root, x, y, 2);
}
};
105. 从前序与中序遍历序列构造二叉树
链接: 构造二叉树
难度： 中等
题目：
运行示例：
思路：
二叉树前序遍历的顺序为：根左右。
二叉树中序遍历的顺序为：左根右。
根据这一性质，我采用了递归利用根结点的位置进行构造。
代码：
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pleft, int pright, int ileft, int iright){
if(pleft > pright || ileft > iright) return NULL;
int preorder_root = pleft;
int inorder_root = index[preorder[preorder_root]];
TreeNode* root = new TreeNode(preorder[preorder_root]);
int size_left_tree = inorder_root - ileft;
root->left = build(preorder,inorder,pleft+1,pleft+size_left_tree,ileft,inorder_root-1);
root->right = build(preorder,inorder,pleft+size_left_tree+1,pright,inorder_root+1,iright);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() != inorder.size() || preorder.size() == 0) return NULL;
for (int i = 0; i < inorder.size(); ++i) {
index[inorder[i]] = i;
}
return build(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
}
};
51. N 皇后
链接: N 皇后
难度： 困难
题目：
运行示例：
文章来源：https://www.toymoban.com/news/detail-834637.html
思路：
N皇后是比较经典的一类题，利用的是回溯法。
代码：文章来源地址https://www.toymoban.com/news/detail-834637.html
class Solution {
private:
vector<vector<string>> res;
public:
bool isValid(vector<string>& board,int row, int col){
int n = board.size();
for(int i = 0; i < n; i++){
if(board[i][col] == 'Q') return false;
}
for (int a = row, b = col; a >= 0 && b >= 0; a--, b--) { // 左上
if (board[a][b] == 'Q') return false;
}
for (int a = row, b = col; a >= 0 && b < n; a--, b++) { // 右上
if (board[a][b] == 'Q') return false;
}
return true;
}
void backtrack(vector<string>&board,int row,int n){
if(row == n)
{
res.push_back(board);
return;
}
for(int i = 0; i < n; i++){
if(isValid(board,row,i)){
board[row][i] = 'Q';
backtrack(board,row+1,n);
board[row][i] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(board, 0,n);
return res;
}
};
到了这里，关于力扣题目训练（6）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
