刷题

LRU
大概思路就是unordered_map hash+双向链表head,tail
拿的时候hahsmap key int value node
我能直接get拿到这个node，然后把这个node 先remove，然后插到链表头部
put的时候，也是，如果有，就修改这个value，然后remove，再insert
如果没有，new一个node，然后再看size和cap的关系，如果大于等于，就要
先remove这个tail的一个，然后再insert头

class LRUCache {
private:
int cap;
struct Node {
int key, value;
struct Node* prev;
struct Node* next;
Node(int key, int value): key(key), value(value) {
}
};

struct Node* head;
struct Node* tail; 

unordered_map<int, Node*> mp;

Node* removeNode(int key) {
    if (!mp.count(key)) return NULL;
    Node* node = mp[key];
    return removeNode(node);
}

Node* removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev; 
    mp.erase(node->key);
    return node;
}

int insertHead(int key, Node* node) {
    if (node == NULL) return -1;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
    mp[key] = node;
    return node->value;
}

public:
LRUCache(int capacity): cap(capacity) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
head->prev = NULL;
tail->next = NULL;
tail->prev = head;
}

int get(int key) {
    return insertHead(key, removeNode(key));
}

void put(int key, int value) {
    if (mp.count(key)) {
        Node* node = mp[key];
        node->value = value;
        insertHead(key, removeNode(key));
    } else {
        Node* node = new Node(key, value);
        if (mp.size() >= cap) {
            removeNode(tail->prev);
        } 
        insertHead(key, node);
    } 
}

};

有效的括号
这个是栈匹配这个这个，进来先看栈顶能不能匹配
匹配了直接弹，continue
不匹配入栈
class Solution {
public:
stack st;
bool isValid(string s) {
for (int i = 0; i < s.size(); i ++ ) {
if (!st.empty() && (
s[i] == ‘)’ && st.top() == ‘(‘ ||
s[i] == ‘]’ && st.top() == ‘[‘ ||
s[i] == ‘}’ && st.top() == ‘{‘
)) {
st.pop();
cout << i << “pop” << endl;
continue;
}
cout << i << “push” << endl;
st.push(s[i]);
}
return st.size() == 0;
}
};

数组中的第K个最大元素

这个还有点复杂，我的思路就堆，但是建堆好像是nlogn，跟这个排序没啥区别
有个思路很厉害，就是第k个，那就是有序列表的下标n-k
这个可以用快排做，为什么，因为这有点像是一个二分找n-k下标
我每次快排就是分成两个部分+当前的pivot，pivot左边的是<pivot的，右边是大于的，那这个位置
很显然就是pivot的排序之后的index
然后快排这个pivot需要在left，right之间取一个rand，不取也行，我一般用这个l+r+1>>1;
拿到pivot之后，就快排思路了
这俩部分是left到pivot i ，pivot到right j
就while(true)进来
左边找到第一个大于pivot的，右边找到第一个小于pivot的，&&i<=j, swap
i++，j–
然后i>=j break;
让我写的话，我这里应该是会写不出来。。。

买卖股票的最佳时机1 & 2
1 这里就是只能买卖一次
2 这里可以多次买卖
这里1的话就是第i天，我最大利润就是第i天的price-前面最小值，然后这利润取最大遍历就行了
2这里可以多次买卖的话，就可以用dp
大致思路就是第i天如果持有了，那说明要么是之前就持有了，要么就前一天买了
第i天卖了，要么是之前就卖了，要么昨天卖了
然后就是这个可以最简单，贪心，第二天比第一天涨，我就吃，也就是说，所有的涨幅我都吃，是一个贪心思路
class Solution {
public:
int dp[100010][2];
int maxProfit(vector& prices) {
// dp[i][j] 表示第i天持有/卖出这只股票的最大利润
// dp[i][0] = dp[0…i - 1][1] max dp[i-1][ 1] + prices[i]
// dp[i][1] = dp[i-1][0] - prices[i]
dp[0][1] = -prices[0];
dp[0][0] = 0;
for (int i = 1; i < prices.size(); i ++ ) {
dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
}
return dp[prices.size() - 1][0];
}
};

最长回文子串
区间dp
外层length
枚举左边界，定位右边界
如果ij不相等不是回文，是的话，看size是不是2，是直接赋值
不是看里面是不是回文，是的话赋值
记录index，返回substr
class Solution {
public:
int dp[1010][1010];

  string longestPalindrome(string s) {
      int n = s.size();
      int res = 1;
      pair<int, int> idx = {0, 0};

      for (int i = 0; i < n; i++) dp[i][i] = 1;

      for (int length = 2; length <= n; length++) {//<=
          for (int i = 0; i + length - 1 < n; i++) {// 直接限制 j 范围,不用 continue
              int j = i + length - 1;
              if (s[i] != s[j]) {
                  dp[i][j] = 0;
              } else if (length == 2) {
                  dp[i][j] = 2;
              } else if (dp[i + 1][j - 1] > 0) {//里层是回文
                  dp[i][j] = dp[i + 1][j - 1] + 2;
              } else {
                  dp[i][j] = 0;// 里层不是,整个不是
              }

              if (dp[i][j] > res) {
                  res = dp[i][j];
                  idx = {i, j};
              }
          }
      }
      return s.substr(idx.first, idx.second - idx.first + 1);
  }

};

反转链表
三指针，直接反转，记录一下next，while cur就行了
/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode() : val(0), next(nullptr) {}
  

• ListNode(int x) : val(x), next(nullptr) {}
  

• ListNode(int x, ListNode *next) : val(x), next(next) {}
  

• };
  /
  class Solution {
  public:
  ListNode reverseList(ListNode* head) {
  if (!head) return head;
  ListNode* prev = NULL;
  ListNode* cur = head;
  ListNode* next = cur->next;
  while (cur) {
  next = cur->next;
  cur->next = prev;
  prev = cur;
  cur = next;
  }
  return prev;
  }
  };

环形链表2
这个是结论快慢指针交点得出环
然后这个位置和head同速相交会走到交点
/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• };
  /
  class Solution {
  public:
  ListNode detectCycle(ListNode head) {
  ListNode p = find(head);
  if (!p) return NULL;
  while (head) {
  if (head == p) return head;
  head = head->next;
  p = p->next;
  }
  return NULL;
  }
  ListNode find(ListNode head) {
  ListNode q, * s;
  q = head; s = head;
  while (q) {
  s = s->next;
  q = q->next;
  if (q) q = q->next;
  if (q && s && q == s) return q;
  }
  return NULL;
  }
  };
  K 个一组翻转链表
  这个有点难，模拟可以做，但是太复杂了。这里用递归
  大概思路就是，先看能不能取k个一组，不能直接返回
  可以的话，可以reverse当前的k，然后这个链表的tail和head需要拿到
  因为tail到结束的这部分，可以递归处理
  我当前这个函数表述的是，给一个头+k，我返回处理结束后的新链表的头
  那这里我不就可以递归了吗？然后原来的head变成了尾，head->next链接上新链表的头节点over
  /*
• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode() : val(0), next(nullptr) {}
  

• ListNode(int x) : val(x), next(nullptr) {}
  

• ListNode(int x, ListNode *next) : val(x), next(next) {}
  

• };
  /
  class Solution {
  public:
  ListNode reverseKGroup(ListNode* head, int k) {
  // 先看看前面k个能不能搞出来，不能搞出来就return
  // 能搞出来，你这里直接返回reverse之后的头节点对吧
  // 那我先拿到后面的n-k链表的头，然后我再reverse当前k的
  // 然后我再链接上
  ListNode* tail = head;
  for (int i = 0; i < k; i ++ ) {
  if (tail) {
  tail = tail->next;
  } else {
  return head;
  }
  }
  ListNode* res = reverse(head, k);
  head->next = reverseKGroup(tail, k);
  return res;
  }
  ListNode* reverse(ListNode* head, int k) {
  ListNode* cur, * next, * prev;
  prev = NULL; cur = head;
  while (cur && k – ) {
  next = cur->next;
  cur->next = prev;
  prev = cur;
  cur = next;
  }
  return prev;
  }
  };

24. 两两交换链表中的节点
    这个是这个东西的简化版，k=2

然后还有个
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

这个东西，思路是俩子集相等，那也就是一个凑出total/2就行了，奇数直接false
然后这个就是01dp dp[i][j]表示前i个能不能凑出j，不选直接=i-1
选了的话，|| dp[i-1][j-nums[i]] 这里一般dp会从1开始，这里凑0显然都是true
然后这个nums数组从0开始，这里得-1

class Solution {
public:
int dp[300][10010];
bool canPartition(vector& nums) {
int total = 0;
for (auto val: nums) total += val;
if (total % 2) return false;
int target = total / 2;
int n = nums.size();

    // 前i个数，可以凑出j
    for (int i = 0; i <= n; i ++ ) dp[i][0] = true;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= target; j ++ ) {
            dp[i][j] = dp[i - 1][j];
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[n][target];
}

};
2. 两数相加
模拟，记住有个mod就行了，然后有几个边界条件
就长度不一致，然后最后如果md还有值，这俩
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int md = 0;
ListNode* head = new ListNode();
ListNode* tmp = head;
while (l1 && l2) {
int val = l1->val + l2->val + md;
md = val / 10;
val %= 10;
ListNode* node = new ListNode(val);
tmp->next = node;
tmp = node;
l1 = l1->next;
l2 = l2->next;
}
while (l1) {
int val = l1->val + md;
md = val / 10;
val %= 10;
ListNode* node = new ListNode(val);
tmp->next = node;
tmp = node;
l1 = l1->next;
}
while (l2) {
int val = l2->val + md;
md = val / 10;
val %= 10;
ListNode* node = new ListNode(val);
tmp->next = node;
tmp = node;
l2 = l2->next;
}
if (md) {
ListNode* node = new ListNode(md);
tmp->next = node;
}
return head->next;
}
};
238. 除了自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

不用除法就俩前缀和解决了，这个进阶：
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
这个要优化的话，那可能就是我在算这个前缀和的时候，就直接把结果都存进去了。
class Solution {
public:
int s[100010], a[100010];
vector productExceptSelf(vector& nums) {
// 前缀和，当前这个i，实际上=i-1 * n-i+1
// 哦，不能÷的话，搞俩前缀和不就行了吗
int n = nums.size(); s[0] = 1;
for (int i = 1; i <= n; i ++ ) {
s[i] = s[i - 1] * nums[i - 1];
}
a[n + 1] = 1;
for (int i = n; i >= 1; i – ) {
a[i] = a[i + 1] * nums[i - 1];
}
vector res;
for (int i = 1; i <= n; i ++ ) {
res.push_back(s[i - 1] * a[i + 1]);
}
return res;
}
};
分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

这个我的思路1是枚举分割点2^16
然后2就是dfs，从dfs(s, start)表示从s字符串的start开始切割回文串
那我进入肯定就看你这个是不是结束了，start==size，那就是整体都切完了push一个
然后这里记录path的话，就从start开始吧，这里先看看是不是回文，然后push，然后dfs继续后面部分的
然后记得回溯现场。
class Solution {
vector<vector> ans;
vector path;

  bool isPalin(const string& s, int l, int r) {
      while (l < r) {
          if (s[l] != s[r]) return false;
          l++; r--;
      }
      return true;
  }

  void dfs(string& s, int start) {
      if (start == s.size()) {              // 切到末尾,收答案
          ans.push_back(path);
          return;
      }
      for (int end = start; end < s.size(); end++) {     // 枚举本段终点
          if (isPalin(s, start, end)) {                   // 是回文才往下切
              path.push_back(s.substr(start, end - start + 1));
              dfs(s, end + 1);                            // 递归切剩下的
              path.pop_back();
          }
      }
  }

public:
vector<vector> partition(string s) {
dfs(s, 0);
return ans;
}
};

160. 相交链表
     给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     这个就比较简单，就找相交的就行了
     class Solution {
     public:
     ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     ListNode a = headA, b = headB;
     while (a) {
     ListNode node = find(a, b);
     if (node) return node;
     a = a->next;
     }
     return NULL;
     }
     ListNode find(ListNode a, ListNode* b) {
     while (b) {
     if (a == b) return a;
     b = b->next;
     }
     return NULL;
     }
     };

两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。
嗯，大概就注释里面写的这样，总之记住先查后塞

class Solution {
public:
vector twoSum(vector& nums, int target) {
// 对于固定右边j，实际上我只需要看j左边有没有target-Numj就行了
// 然后我j从0到n，先查后加
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i ++ ) {
if (mp.count(target - nums[i])) {
return {i, mp[target - nums[i]]};
}
mp[nums[i]] = i;
}
return {};
}
};

236. 二叉树的最近公共祖先
     这个就记住一个东西，公共祖先root，这个pq，他得分别在左子树和右子树
     不然的话，就得return left递归找左子树/右子树
     大概思路就是，先找左子树有没有pq，再找右子树有没有pq，都有才返回root
     class Solution {
     public:
     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
     // 这个公共祖先，必须是p&q的祖先，也就是说从祖先能遍历到pq
     // 哦，我想起来了，就是这俩得分别在左右子树里面pq
     // 如果pq都在同一个子树里面，那说明这个祖先也在这里面
     if (root == NULL) return NULL;
     if (root == p || root == q) return root;
     TreeNode* left = lowestCommonAncestor(root->left, p, q);
     TreeNode* right = lowestCommonAncestor(root->right, p, q);
     if (left && right) return root;
     return left ? left : right;
     }
     };

237. 最大子数组和
     给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

这里的思路是dpi表示以i结尾的连续子数组的最大值
你这里前面，i-1这块，要么能接上，要么接不上
能接上，那就是dp-1+numsi，不能那就当前这一个，最大值取max

class Solution {
public:
int dp[100100];
int maxSubArray(vector& nums) {
int res = -1000000;
for (int i = 1; i <= nums.size(); i ++ ) {
dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
res = max(res, dp[i]);
}
return res;
}
};
反转二叉树

class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
// 左右子树都反转之后，切换root的左右子树
if (root == NULL) return NULL;
if (root->left == NULL && root->right == NULL) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->right = left;
root->left = right;
return root;
}
};
101. 对称二叉树
class Solution {
public:
bool isSymmetric(TreeNode* root) {
// 这里左右俩指针相反移动
// pq, p往左，q往右，p往右，q往左
return check(root->left, root->right);
}

bool check(TreeNode* q, TreeNode* p) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}

};