234 先计数List有多长 将前一半放在一个stack里面 如果奇数就跳过中间node 接着比较节点值与stack里面的数 遇到不同的就return false 直到比较完就true
class Solution {
public:
bool isPalindrome(ListNode* head) {
int count=0;
ListNode* dummy_head = new ListNode(0, head);
ListNode* curr = dummy_head;
while (curr->next!=nullptr) {
curr = curr->next;
count++;
}
stack<int> stack;
curr = head;
for (int i=0; i<count/2; i++) {
stack.push(curr->val);
curr = curr->next;
}
if (count%2==1) curr = curr->next;
while (curr!=nullptr) {
if (curr->val!=stack.top()) return false;
curr = curr->next;
stack.pop();
}
return true;
}
};143 反转list的后面一半 再将两个list穿插合并在一起
class Solution {
private:
ListNode* reverseList (ListNode* head) {
if (head==nullptr) return nullptr;
ListNode* temp=head->next;
head->next = nullptr;
ListNode* pre = head;
ListNode* curr = temp;
while (curr!=nullptr) {
temp = curr->next;
curr->next = pre;
pre = curr;
curr = temp;
}
return pre;
}
public:
void reorderList(ListNode* head) {
int count = 0;
ListNode* curr = head;
while (curr!=nullptr) {
count++;
curr = curr->next;
}//calculate the length of the list
curr = head;
for (int i=0; i<count/2-1; i++) {
curr = curr->next;
}
ListNode* list2 = curr->next;
curr->next=nullptr;
ListNode* list1 = head;//list1 is the first half and list2 is the rest
list2 = reverseList(list2);//reverse the second half
ListNode* l1=list1;
ListNode* l2=list2;
while (l1!=nullptr && l2!=nullptr) {
ListNode* temp1 = l1->next;
l1->next = l2;
l1 = temp1;
ListNode* temp2 = l2->next;
if (l1!=nullptr) l2->next=l1;//when the length is odd, list2 will be longer than list1
l2=temp2;
}//combine the two parts
head = list1;
}
};141 之前做过一题找环形入口的 这题更简单 记得用快慢指针做就可以了！
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
bool flag = true;
while (flag == true|| slow!=fast) {
flag = false;
if (fast==NULL || fast->next==NULL) return false;
fast = fast->next->next;
slow = slow->next;
}
return true;
}
};面试题02.07相交链表 做过的题这次记住了！（表扬自己
因为两个链表在末尾相交 算出两个链表的长度之后 为了右侧对齐 长的那条砍掉前面多出来的几个 然后一一比较 直到两个链表的节点相同 即是交点
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int count1=0;
ListNode* curr1 = headA;
while (curr1!=NULL) {
count1++;
curr1 = curr1->next;
}
int count2=0;
ListNode* curr2 = headB;
while (curr2!=NULL) {
count2++;
curr2 = curr2->next;
}
if (count1>count2) {
for (int i=0; i<count1-count2; i++) {
headA=headA->next;
}
}
else if (count2>count1) {
for (int i=0; i<count2-count1; i++) {
headB=headB->next;
}
}
while (headA!=headB) {
headA=headA->next;
headB=headB->next;
}
return headA;
}
};205 用umap来一一对应s里的字符在t的映射和t的字符在s里的映射 必须要互相都一一对应 所以要有两个umap来写！！
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map <char, char> umap1;
for (int i=0; i<s.size(); i++) {
if (umap1.find(s[i])!=umap1.end()) {
if (t[i]!=umap1[s[i]]) return false;
}
else umap1[s[i]] = t[i];
}
unordered_map <char, char> umap2;
for (int i=0; i<t.size(); i++) {
if (umap2.find(t[i])!=umap2.end()) {
if (s[i]!=umap2[t[i]]) return false;
}
else umap2[t[i]]=s[i];
}
return true;
}
};简化后的代码如下 cr to 代码随想录
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map <char, char> umap1;
unordered_map <char, char> umap2;
for (int i=0; i<s.size(); i++) {
if (umap1.find(s[i])==umap1.end()) umap1[s[i]] = t[i];
if (umap2.find(t[i])==umap2.end()) umap2[t[i]] = s[i];
if (t[i]!=umap1[s[i]] || s[i]!=umap2[t[i]]) return false;
}
return true;
}
};1002 写过两遍的题 记得大致思路但是还是没自己写出来
卡住的地方有二：1.不记得有重复元素怎么取公共的 -> 用数组每个word都计数 取最小值
2. char转变成string！！！ string s(1, c); 前面1表示长度 c是char 重要重要！！
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<int> hash(26,0);
for (int j=0; j<words[0].size(); j++) {
hash[words[0][j]-'a']++;
}
for (int i=1; i<words.size(); i++) {
vector<int> count(26, 0);
for (int j=0; j<words[i].size(); j++) {
count[words[i][j]-'a']++;
}
for (int k=0; k<26; k++) {
hash[k]=min(hash[k], count[k]);
}
}
vector<string> result;
for (int k=0; k<26; k++) {
while(hash[k]>0) {
string s(1, 'a'+k);
result.push_back(s);
hash[k]--;
}
}
return result;
}
};925 以name为准 一个一个顺着在typed里面找 直到i和j任意一个走到末尾为止
如果相同 两个指针都往后走一个
如果不同 看j是否是因为连按停留在上一个字符 如果没停留在上一个字符或者j==0 就return false
出loop后看是i走完还是j走完
如果i没走完一定false
如果j没走完 检测j后面剩下的是否都与name的最后一个字符相同 如果出现不同的就是false
class Solution {
public:
bool isLongPressedName(string name, string typed) {
int i=0; int j=0;
while (j<typed.size() && i<name.size()) {
if (name[i]==typed[j]) {
i++; j++;
}
else {
if (j==0 || typed[j]!=typed[j-1]) {
return false;
}
j++;
}
}
if (i!=name.size()) {
return false;
}
while (j<typed.size()) {
if (typed[j]!=name[name.size()-1]) return false;
j++;
}
return true;
}
};844 我写的->用栈的思路
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> stack1;
for (int i=0; i<s.size(); i++) {
if (s[i]=='#') {
if (!stack1.empty()) {
stack1.pop();
}
}
else {
stack1.push(s[i]);
}
}
stack<char> stack2;
for (int i=0; i<t.size(); i++) {
if (t[i]=='#') {
if (!stack2.empty()) {
stack2.pop();
}
}
else {
stack2.push(t[i]);
}
}
while (!stack1.empty() && !stack2.empty()) {
if (stack1.top()!=stack2.top()) return false;
stack1.pop();
stack2.pop();
}
if (!stack1.empty() || !stack2.empty()) return false;
return true;
}
};cr to 代码随想录：
那么本题，确实可以使用栈的思路，但是没有必要使用栈，因为最后比较的时候还要比较栈里的元素，有点麻烦。
这里直接使用字符串string，来作为栈，末尾添加和弹出，string都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。
class Solution {
private:
string get_string (string s) {
string s1;
for (int i=0; i<s.size(); i++) {
if (s[i]=='#') {
if (!s1.empty()) s1.pop_back();
}
else {
s1+=s[i];
}
}
return s1;
}
public:
bool backspaceCompare(string s, string t) {
return get_string(s)==get_string(t);
}
};用双指针来写 从后往前遍历 思路好想 但写起来不少很容易 标记一下 以后要来重新写一遍 这遍算边看边写的
要先把两个string的有后退格的都删掉 都停留在最后留下来的字符上
如果任意一个到头 return是否都到头
else 如果不相等return false 相等就都--
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i=s.size()-1;
int j=t.size()-1;
int count1=0; int count2=0;
while (1) {
while (i>=0) {
if (s[i]=='#') {
i--;
count1++;
}
else if (count1>0) {
i--;
count1--;
}
else break;
}
while (j>=0) {
if (t[j]=='#') {
j--;
count2++;
}
else if (count2>0){
j--;
count2--;
}
else break;
}
if (i<0 || j<0) return i==-1 && j==-1;
if (s[i]!=t[j]) return false;
i--; j--;
}
return true;
}
};129 用回溯法先把每个到达子节点的path记下来 最后再加就可以了文章来源：https://www.toymoban.com/news/detail-614361.html
class Solution {
vector<vector<int>> results;
void backtracking(TreeNode* root, vector<int>& path) {
if (root->left==nullptr && root->right==nullptr) {
results.push_back(path);
return;
}
if (root->left) {
path.push_back(root->left->val);
backtracking(root->left, path);
path.pop_back();
}
if (root->right) {
path.push_back(root->right->val);
backtracking(root->right, path);
path.pop_back();
}
}
public:
int sumNumbers(TreeNode* root) {
if (!root) return 0;
vector<int> path;
path.push_back(root->val);
backtracking(root, path);
long sum=0;
for (int i=0; i<results.size(); i++) {
long num=0; long unit=1;
for (int j=results[i].size()-1; j>=0; j--) {
num+=results[i][j]*unit;
unit*=10;
}
sum+=num;
}
return sum;
}
};1382 先变成有序数组（用了递归，明天再试一下不用递归用stack的中序遍历 今天没写出来） 再通过有序数组建立平衡二叉树（这里用左闭右开）文章来源地址https://www.toymoban.com/news/detail-614361.html
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
if (root->left) traversal(root->left);
vec.push_back(root->val);
if (root->right) traversal(root->right);
}
TreeNode* getTree(vector<int> vecvec, int start, int end) {
if (start==end) return nullptr;
int mid = (start+end)/2;
TreeNode* root = new TreeNode(vecvec[mid]);
root->left = getTree(vecvec, start, mid);
root->right = getTree(vecvec, mid+1, end);
return root;
}
public:
TreeNode* balanceBST(TreeNode* root) {
traversal(root);
TreeNode* new_tree = getTree(vec, 0, vec.size());
return new_tree;
}
};到了这里，关于额外题目第2天｜234 143 141 面试题02.07相交链表 205的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![力扣[24、19、面试题02.07、142]](https://imgs.yssmx.com/Uploads/2024/02/609413-1.png)
