2024年1月31日力扣题目训练
2024年1月31日力扣题目训练
2024年1月31日第七天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。前几天家里有事加上有一个作业所以没办法只能拖到今天，今天能写也是利用了作业数据下载的时间，但是我不会放弃的我会认真完成的。
387. 字符串中的第一个唯一字符
链接: 唯一字符
难度： 简单
题目：
运行示例：
思路：
找唯一就是计数，我采用的是哈希表。
代码：
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> res;
for(char ch: s){
res[ch]++;
}
for(int i = 0; i < s.size(); i++){
if(res[s[i]] == 1){
return i;
}
}
return -1;
}
};
389. 找不同
链接: 找不同
难度： 简单
题目：
运行示例：
思路：
找出添加的字母，也就是计数看哪个多了，所以我采用了哈希表。
代码：
class Solution {
public:
char findTheDifference(string s, string t) {
unordered_map<char,int>res;
char ans;
for(int i = 0; i < s.size(); i++){
res[s[i]]++;
}
for(int i = 0; i < t.size(); i++){
if(res[t[i]] == 0){
ans = t[i];
}
else res[t[i]]--;
}
return ans;
}
};
401. 二进制手表
链接: 二进制手表
难度： 简单
题目：
运行示例：
思路：
这道题本质就是看二进制中总共有多少个1，所以利用位运算取最高4位和低6位然后计算。
代码：
class Solution {
public:
vector<string> readBinaryWatch(int turnedOn) {
vector<string> ans;
if(turnedOn >= 9) return ans;
for(int i = 0; i < 1024; i++){
int h = i >>6;
int m = i & 63;
if(h < 12 && m < 60 && __builtin_popcount(i) == turnedOn){
ans.push_back(to_string(h)+":"+(m<10?"0":"")+to_string(m));
}
}
return ans;
}
};
109. 有序链表转换二叉搜索树
链接: 二叉搜索树
难度： 中等
题目：
运行示例：
思路：
对于二叉搜索树，如果对其进行中序遍历，得到的值序列是递增有序的。此外左右子树高度差不超过1，利用这两条性质通过分治和中序遍历完成这道题。
代码：
class Solution {
public:
int getLength(ListNode* head){
int count = 0;
while(head!=NULL){
count++;
head = head->next;
}
return count;
}
TreeNode* buildTree(ListNode* &head,int left,int right){
if(left > right) return NULL;
int mid = (left+right+1)/2;
TreeNode* root = new TreeNode();
root->left = buildTree(head, left, mid-1);
root->val = head->val;
head = head->next;
root->right = buildTree(head,mid+1,right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
int length = getLength(head);
return buildTree(head,0,length-1);
}
};
114. 二叉树展开为链表
链接: 展开为链表
难度： 中等
题目：
运行示例：
思路：
二叉树前序遍历的顺序为：根左右。
这个结果也是前序遍历的结果，所以可以利用前序遍历解决。
代码：
class Solution {
public:
void preorder(TreeNode*root,vector<TreeNode*> &res){
if(root != NULL){
res.push_back(root);
preorder(root->left,res);
preorder(root->right,res);
}
}
void flatten(TreeNode* root) {
vector<TreeNode*> res;
preorder(root,res);
for(int i = 1 ; i < res.size(); i++){
TreeNode*pre = res[i-1];
TreeNode*curr = res[i];
pre->left = NULL;
pre->right = curr;
}
}
};
52. N 皇后 II
链接: N 皇后
难度： 困难
题目：
运行示例：
思路：
这与上次的51.N皇后类似，只是输出一个是解决，一个是总数。利用的是回溯法。
代码：
class Solution {
private:
int res = 0;
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++;
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] = '.';
}
}
}
int totalNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(board, 0,n);
return res;
}
};
