单词搜索

212. 单词搜索 II

思路:

虽然明明知道硬写一定会,超时,但还是写了一个。

超时后考虑什么优化:自然想到了字典树。不过没有想透彻:

  • 用字典树构造dfs遍历的路径,❌ :dfs搜索的路径不需要被查询,因为只出现一次

  • 正确做法:用字典树存储所有words,方便查询。或者进一步的,在dfs过程中,可以直接用字典树进行搜索剪枝。

    Orz

Read more

安全状态

思路

建图后,需要判断一次深搜路径上有无重复点出现,并用涂色法记录整条路径上的安全或者不安全状态。

Read more

之字形标记

1104. 二叉树寻路

思路

思路其实很清晰,翻转出层序的下标,在遍历的时候,把层序下标翻转回之字下标即可。

良好的编程习惯其实蛮重要的,每个变量都有自己的用处。良好的代码对后续的修改友善的。

Read more

二叉树中距离为K的节点

思路

这题还是有点点复杂的,距离为K的节点,完全可以分为两类,target节点构成树的K-dis节点,和其路径经过target祖父节点的节点。分类搜索即可,考虑到后者需要定点采集,所以用回溯的方式获取。

Read more

二叉树的两个错误节点

CD169 找到搜索二叉树中两个错误的节点

如果两个节点交换,那么在中序遍历里就有至少一次降序,可能有两个相邻的节点交换,或者两个不相邻的节点交换,产生一个或两次降序。

Read more

二叉树累加和的最长路径

CD165 在二叉树中找到累加和为指定值的最长路径长度

写的好心酸, 明明只有有类似的题目接触到。又是没思考就动手

  • 先静态化构造二叉树(不要嫌麻烦,一题写好了所有题目都可以用)

  • 前序遍历节点,

    • 记录根节点到当前节点的综合newadd,只记录最短长度的newadd路径。
    • 同时判断,newadd - target之和是否有在当前遍历路径下,是否存在从根节点到同路径的某个节点连成的路径。
    • 最后回溯时,为了下次遍历路径不受这里遍历数据影响,消减掉当次遍历时候设置新路径长度。
Read more

单链表中K节点逆序

思路

超级大杂烩,左程云出的题的风格。

K节点逆序+ K节点检测 + 链表链接

代码

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * reverse_knode(list_node * head1, int K)
{
    list_node whead = {0, head1};
    list_node *before, *pre, *p, *next; // pre, p, next 单单在K个节点逆序起作用; bofore指向逆序链表的前一个节点
    p = head1;
    before = &whead;
    
    while(p) {
        int k = 0;
       list_node *now = before;
        while(k < K){
            k++;
            if (now) now = now->next;
        
        }
        if(now == nullptr) break;
        
        k = 0;
        pre = nullptr;
        list_node *kend = before->next;
        while(k < K) {
            k++;    
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
            if(next) next = next->next;
        }
        before->next = pre;
        kend->next = p;
        
        before = kend;
        
    }
    return whead.next;

}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    int K;
    scanf("%d", &K);
    list_node * new_head = reverse_knode(head, K);
    print_list(new_head);
    return 0;
}

约瑟夫问题

思路:

实际上是一个非常巧妙的数学问题。

从结果上来看, 如果只剩最后一个人(最后的幸存者),那么被杀掉一定是它。那么它的当前号码为1,问其原坐标?思考一下新旧人列的下标关系:

Old(k+1) : 
1 2 3 4 5 6 7 --- k + 1 
New(k)
4 5 6    m -1 (s) 1 2 3 

可能的一种形式,其中s是old被杀掉的人的下标。 且s = (m - 1 )% (k + 1) + 1

但不难发现有: old = (new + s - 1) % (k + 1) + 1

综上有逆推式: old =(new + m - 1) % (k + 1) + 1

Read more

最大子矩阵

类似于面试题17.24;

不过是每个单元的元素只是一,可以把问题转化为求取面积。

直接用单调栈求取从一个柱子可扩展的的最大面积即可。

代码

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
int n , m;
vector<int> height;
int maxarea = 0;

void caculateArea(vector<int>&area){
    for(int i = 0; i < area.size(); ++i){
        if(area[i]) height[i] += area[i];
        else height[i] = 0;

    }
    stack<int> st;
    height.push_back(0);
    
    for(int i = 0; i < height.size(); ++i){

        while(st.size() && height[st.top()] >= height[i]){
            int hei = height[st.top()];
            st.pop();
            int l = st.size() ? st.top() : -1;
            maxarea = max(maxarea, (i - 1 - l)* hei);
          //  cout << l << ' ' << maxarea << ' ' << i - 1  << ' ' << hei<< endl;

        }
        st.push(i);
    }
    height.erase(height.end() - 1);
    
}


int main(){
    cin >> n  >> m;
    vector<int> maze(m);
    height.resize(m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j) cin >> maze[j];
        caculateArea(maze);
    }
    cout << maxarea << endl;
    return 0;
}

二分图匹配

二分图匹配

二分图匹配是个经典问题——两组节点在图上尽可能的匹配。

匈牙利算法以不断寻找增光路的方式,寻找更多的匹配;

思想如下:

  1. 从未匹配的点c开始寻找链接的点v,如果v也是未匹配,则匹配成功。如果该点已经匹配了u,则递归尝试让u匹配其他节点。
  2. 如果v匹配失败,那就找找c的其他点。

题解参考

Read more

割点算法

割点算法Tarjan

割点算法 引入了建立在DFS生成树的遍历节点的时间戳概念,如果一个节点u的子节点v可以找到一条不经过u以外的路径到达u的祖先,那么显然有一条通路可以回到u的祖先。反之,如果存在v找不到这么一条路径回到u的祖先,那么显然u是一个割点,他分割了v所在的子树和其他子树(如果u不是根的话,包括祖先所在子树)。

image-20210509113600747

那么一个割点有多少子树呢?
首先,一个割点的对应的v是独立在各个子树的吗?是的,如果存在v1v2都找到路径,且在一个子树中,那么必然有v1可以通过v2找到u,那么在DFS搜索的时候,必定会一次遍历v1v2。所以每个割点对应的子树只会搜索到一个v
扩展一下, 那么经过去掉割点的图最多有几个连通块?

Read more

84. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

思路:

  1. 遍历高度数组的同时,维护形成的矩阵,并更新最大面积。
  2. 观察,矩阵的面积可以不严格递增的情况下在从左到右扩展的,再严格递减的情况下可以确定出矩阵面积。正向数据缓存,逆向面积计算-> 单调栈。read more

代码:

class Solution {
    map<int, pair<int,int>> reg;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        for(int i = 0; i < heights.size(); ++i){
            
            for(auto &item : reg){
                auto high = item.first; 
                auto &pii = item.second;
                auto l = pii.first;
                auto &r = pii.second;
                if(high > heights[i]){
                    reg.insert({heights[i], {l, i}});
                    maxarea = max(maxarea, heights[i] *(i - l + 1));
                    reg.erase(reg.find(high), reg.end());
                    
                    break;
                } 
                else if(high <= heights[i]){
                    r = i;
                    maxarea = max(high * (r - l + 1), maxarea);
                }
            }
            if(reg.count(heights[i]) == 0){
                reg.insert({heights[i], {i, i}});
                maxarea = max(maxarea, heights[i]);
            }
        }
        return maxarea;
    }
};
class Solution {
    stack<int> s;
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxarea = 0;
        heights.push_back(0); // 为了计算所有面积
        for(int i = 0; i < heights.size(); ++i){
            if(s.empty()) s.push(i);
            else if(heights[s.top()] < heights[i]) s.push(i);
            else if(heights[s.top()] == heights[i]) s.top() = i; // 如果相邻的高度相同,则更新;因为不更新单调栈中矩阵左边界会扩展更多
            else if(heights[s.top()] > heights[i]){         
                while(!s.empty() && (heights[s.top()] > heights[i])){                    
                    int high = heights[s.top()]; 
                    s.pop();
                    int temparea = ( i - (s.empty() ? -1 : s.top()) - 1) * high;
                    maxarea = max(maxarea, temparea);
                }
                s.push(i);   
            }   
        }
        return maxarea;
    }
};

当然,这里也可以添加一个哨兵,不过没什么影响。

32. Longest Valid Parentheses

思路:

栈验证匹配括号很简单,但是用如何获取多个匹配成功的括号组合长度就很麻烦!

难的是想到,连续的有效括号()())()()只需要记录一个最先未匹配的位置。具体做法是,在栈中存储一个最后没有匹配到的右括号下标。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxlen = 0; 
        stack<int> st;
        
        st.push(-1); // 压入一个最后未匹配的)。
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == ')'){
                st.pop();
                if(!st.empty()){ // 刚刚的)匹配成功,可以计算最长匹配
                    maxlen = max(maxlen, i - st.top()); 
                }else st.push(i); // 说明该)没有匹配到,是新的最后的最右括号
            }else st.push(i);
        }
        return maxlen;
    }
};