1. 最长公共子序列

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

咋说呢，这个题没做出来，我的思路是直接暴力枚举，1 << 1000 直接炸了
这个dp[i][j] i和j表示俩字符串的最后一位，用闫氏dp法，切割最后一位状态，它这俩字符串这个ij位到底可能有哪些情况
比较好想出来的就是字符串是否相等来切割，如果相等，那就直接等于i-1 j-1 + 1，如果不相等，就等于i-1/j-1 取max
个人感觉不是很好想出来，看答案了

class Solution {
public:
int dp[1020][1020];
int longestCommonSubsequence(string text1, string text2) {
for (int i = 1; i <= text1.size(); i ++ ) {
for (int j = 1; j <= text2.size(); j ++ ) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};

还有个链表，这个边界情况烦死人。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
大致思路就是先顺序遍历找到总长度，然后倒排能算出来这个length-n
然后这个就是要删除的节点的前一位，基本上就是它的next执行它下一个的next就行了
然后如果这个是0，那就是要删除头，这里直接看这个头是不是只有一个，如果是的话直接返回NULL
不然的话直接返回head->next
/**

  • 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     removeNthFromEnd(ListNode* head, int n) {
    int length = 0;
    ListNode* hd = head;
    ListNode* tmp = head;
    while (head != NULL) {
    head = head->next;
    length ++ ;
    }
    cout << length << “ “ << n << endl;
    length -= n;
    if (length == 0) {
    if (hd->next) {
    tmp = hd->next;
    } else {
    tmp = NULL;
    }
    return tmp;
    }
    while (–length && hd != NULL) {
    cout << length << “ “;
    cout << hd->val << “ “;
    if (hd->next != NULL) cout << hd->next->val << endl;
    else cout << “NULL” << endl;
    hd = hd->next;
    }
    if (hd) cout << hd->val << endl;
    if (hd != NULL && hd->next != NULL) {
    hd->next = hd->next->next;
    }
    if (hd) cout << hd->val << endl;
    return tmp;
    }
    };
  1. 矩阵置零
    给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
    一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
    一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
    你能想出一个仅使用常量空间的解决方案吗？
    这个思路比较简单，就直接俩set，空间复杂度m+n
    如果要o1，就要直接用这个数组的第零行，第零列，因为本身这俩就有可能会被设置成0，看能不能设置而已，然后最后再看这俩就行了

合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

归并排序，先合并左半边，再合并右半边，然后搞个临时数组，然后这个时候左边和右边都是有序的
我现在需要做的是合并这俩有序的数组，怎么做呢？搞俩指针ij，如果当前i大放进去i++，如果j大放进去，j++
然后如果谁length还有的话，直接塞后面了