wineandchord

原创 stanford cs143 Compilers 15 Global Optimization

文章目录Dataflow AnalysisDataflow Analysis

原创 洛谷 P3835 【模板】可持久化平衡树

前置知识是 无旋Treap// 可持久化平衡树（可持久化 Treap）// 1.插入 x// 2.删除 x// 3.查询 x 的排名// 4.查询排名为 x 的数// 5.求 x 的前驱// 6.求 x 的后继// 每次操作都基于某一历史版本，同时生成一个新的版本#include<iostream>#include<cstdio>#include<cstdlib>#define MAXN 500010using namespace std;.

原创 洛谷 P3834 【模板】可持久化线段树 2（主席树）

可持久化线段树（主席树）nnn 个数，mmm 次查询每次查询区间第 kkk 小暴力的话每次查询进行区间排序，时间复杂度最坏为：O(mnlog⁡n)O(mn\log n)O(mnlogn)主席树的 update 每次改变的结点数为 O(log⁡n)O(\log n)O(logn)，query 的时间复杂度也为 O(log⁡n)O(\log n)O(logn)总的时间复杂度为 O((m+n)log⁡n)O((m+n)\log n)O((m+n)logn)#include&..

原创 洛谷 P1044 栈 （栈混洗，卡特兰数）

1∼n1\sim n1∼n，问出栈可能的序列数文章目录记忆化搜索/递归递推/DP卡特兰数记忆化搜索/递归#include<iostream>#include<cstdio>#define MAXN 20using namespace std;typedef long long ll;int n;ll f[MAXN][MAXN];ll dfs(int i,int j){ if(f[i][j])return f[i][j]; // i:队列中的个数, j:.

原创 洛谷 P1002 过河卒 （二维DP）

#include<iostream>#include<cstdio>#include<algorithm>#define MAXN 35using namespace std;typedef unsigned long long ull;int a,b,c,d;ull f[MAXN][MAXN];int s[MAXN][MAXN];int dx[9]={0,-2,-1,1,2,2,1,-1,-2};int dy[9]={0,1,2,2,1,-1,-2.

原创 添加最少的括号使得括号匹配，包含 []() （区间DP）

来源看这个：https://blog.csdn.net/coolanfei/article/details/7475542给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的输入第一行输入一个正整数N，表示测试数据组数(N<=10)每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100输出对于每组测试

原创 洛谷 P2392 kkksc03考前临时抱佛脚 （01背包）

很有趣的一道 01 背包首先，每个科目单独进行考虑对于每个科目，理想情况应该是左右脑的时间尽可能相等相等时为 sum/2，看作 01 背包问题，背包的容量是 sum，物品是该科目内的题目，放置题目使得背包尽可能装满sum 减去背包的最大装载即为该科目需要花费的时间#include<iostream>#include<cstdio>#include<cstring>#define MAXN 25#define MAXM 5000using name

原创 leetcode 121. Best Time to Buy and Sell Stock

文章目录C++JavaPythonGoSay you have an array for which the ith element is the price of a given stock on day i.If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maxi

原创 leetcode 160. Intersection of Two Linked Lists

文章目录C++JavaPythonGoWrite a program to find the node at which the intersection of two singly linked lists begins.For example, the following two linked lists:begin to intersect at node c1.Example 1:Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [

原创 leetcode 75. Sort Colors （快排/双指针）

文章目录QuickSortC++JavaPythonGoTwo passC++One pass with two pointersC++JavaPythonGoGiven an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

原创 leetcode 74. Search a 2D Matrix （二分）

文章目录C++JavaPythonGoWrite an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of t

原创 leetcode 73. Set Matrix Zeroes

文章目录C++JavaPythonGoGiven an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.Follow up:A straight forward solution using O(mn) space is probably a bad idea.A simple improvement uses O(m + n) space, but still not the

原创 stanford cs143 Compilers 14 Optimization

文章目录Intermediate CodeIntermediate Code

原创 MySQL 必知必会 第8章 用通配符进行过滤 （LIKE） 笔记

文章目录LIKE 操作符% 通配符下划线 （_） 通配符LIKE 操作符通配符 wildcard ：用来匹配值的一部分的特殊字符搜索模式 search pattern：由字面值、通配符或两者组合构成的搜索条件% 通配符% 表示任意字符出现任意次数SELECT prod_id, prod_nameFROM productsWHERE prod_name LIKE 'jet%';检索的是以 jet 开头的任意字符可以使用多个通配符：SELECT prod_id,

原创 leetcode 72. Edit Distance（动态规划）

文章目录C++JavaPythonGoGiven two words word1 and word2, find the minimum number of operations required to convert word1 to word2.You have the following 3 operations permitted on a word:Insert a characterDelete a characterReplace a characterExample 1:Inp

原创 leetcode 71. Simplify Path（栈）

文章目录C++JavaPythonGoGiven an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period … moves the director

原创 leetcode 70. Climbing Stairs （DP）

文章目录C++JavaPythonGoYou are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Example 1:Input: 2Output: 2Explanation: There are two ways to climb

原创 leetcode 68. Text Justification

文章目录C++JavaPythonGoGiven an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.You should pack your words in a greedy approach; that is, pack as many words as y

原创 leetcode 67. Add Binary （二进制加法）

文章目录C++JavaPythonGoGiven two binary strings, return their sum (also a binary string).The input strings are both non-empty and contains only characters 1 or 0.Example 1:Input: a = “11”, b = “1”Output: “100”Example 2:Input: a = “1010”, b = “1011”Outp

原创 NCE4 L11 How to grow old

Lesson 11 How to grow old 如何安度晚年First listen and then answer the following question.听录音，然后回答以下问题。What, according to the author, is the best way to overcome the fear of death as you get older?Some old people are oppressed by(压抑) the fear of death(对死亡的恐惧

原创 洛谷 P3919 【模板】可持久化线段树 1（可持久化数组）

维护长度为 N 的数组，可支持如下操作：在某个历史版本上修改某一个位置上的值访问某个历史版本上的某一位置的值此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本，版本编号即为当前操作的编号（版本0表示初始状态数组）可持久化线段树（主席树）#include<cstdio>#include<iostream>#define MAXN 1000010using namespace std;int n,m,a[MAXN]

原创 洛谷 P4929 【模板】舞蹈链（DLX）

精确覆盖问题使用 dancing links本质思想是十字链表// P4929 模板 舞蹈链 DLX#include<iostream>#include<cstdio>#define MAXN 510#define MAXM 510#define MAX (MAXN*MAXM)using namespace std;int n,m;struct DLX{ int n,m,sz; // n为行数，m为列数，sz表示总节点数 int U[MAX].

原创 How to Write Go Code

How to Write Go CodeCode Organizationpackage: a collection of source files in the same directory that are compiled togethermodule: a collection of related Go packages that are released togethergo.mod declares the module path: the import path prefix fo

原创 MySQL 必知必会 第7章 数据过滤 （高级的 WHERE） 笔记

文章目录组合 WHERE 子句AND 操作符OR 操作符计算次序IN 操作符NOT 操作符组合 WHERE 子句操作符 operator：用来连结或改变 WHERE 子句中的子句的关键字，也叫 logical operatorAND 操作符通过不止一个列进行过滤：SELECT prod_id, prod_price, prod_nameFROM productsWHERE vend_id = 1003 AND prod_price <= 10;OR 操作符OR 用来检索

原创 leetcode 66. Plus One （大整数加一）

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.You may assum

原创 leetcode 65. Valid Number （合法的浮点数）

文章目录DFA （Deterministic Finite Automata）JavaPythonValidate if a given string can be interpreted as a decimal number.Some examples:“0” => true" 0.1 " => true“abc” => false“1 a” => false“2e10” => true" -90e3 " => true" 1e" => f

原创 stanford cs143 Compilers 13.4 Cool Semantics II

原创 MySQL 必知必会 第6章 过滤数据（WHERE） 笔记

文章目录使用 WHERE 子句WHERE 子句操作符检查单个值不匹配检查范围值检查空值检查使用 WHERE 子句只检索所需要的数据要指定搜索条件（search criteria），也称为 过滤条件（filter condition）SELECT prod_name, prod_priceFROM productsWHERE prod_price = 2.50;ORDER BY 应该放在 WHERE 后面WHERE 子句操作符检查单个值不匹配检查范围值检查空值检查...

原创 Linux 内核设计与实现 第二章 从内核出发 笔记

文章目录内核源码树编译内核内核开发的特点内核源码树编译内核make config会逐一遍历所有的配置项，要求用户自己选择 yes,no,modulemake menuconfig具有图形界面的配置环境make defconfig上面这条命令会根据默认的配置为你的体系结构创建一个配置配置项保存在 .config 文件中，修改过配置文件或用已有的配置文件配置新的代码树时，需要验证和更新配置：make oldconfig配置好内核后，通过 make 来进行编译

原创 stanford cs143 Compilers 13.3 Cool Semantics I

原创 Linux 内核设计与实现 第一章 Linux 内核简介 笔记

文章目录历史Linux 简介操作系统和内核简介Linux 内核和传统 Unix 内核比较单内核和微内核设计之比较Linux 内核版本历史Unix 的特点：简洁一切皆文件，这种抽象使得对数据和对设备的操作可以通过一套相同的系统调用接口来进行：open(),read(),write(),lseek()由 C 语言编写，移植能力强进程创建迅速：有一个非常独特的 fork() 系统调用提供了一套非常简单但很稳定的进程间通信原语Linux 简介类 Unix 系统，但不是 Unix操作

原创 leetcode 215. Kth Largest Element in an Array （数组中的第 k 个最大元素）

文章目录直接排序 O(nlog⁡n)+O(1)O(n\log n)+O(1)O(nlogn)+O(1)JavaC++PythonGo最大堆/最小堆 O(nlog⁡k)+O(k)O(n\log k)+O(k)O(nlogk)+O(k)JavaC++PythonGoPartitation O(n)∼O(n2)+O(1)O(n)\sim O(n^2)+O(1)O(n)∼O(n2)+O(1)JavaC++PythonGoQuickSelect O(n)∼O(n2)+O(1)O(n)\sim O(n^2)+O(1)O

原创 leetcode 64. Minimum Path Sum （简单 DP）

文章目录空间 O(n2)O(n^2)O(n2)C++JavaPythonGo空间 O(n)O(n)O(n)C++JavaPythonGoGiven a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down o

原创 stanford cs143 Compilers 13.2 Operational Semantics

原创 洛谷 P1923 求第 k 小的数

直接排序会 TLE 两个点，O(nlog⁡n)O(n\log n)O(nlogn)#include<iostream>#include<cstdio>#include<algorithm>#define MAXN 5000010using namespace std;int n,k,a[MAXN];int main(){#ifdef WINE freopen("data.in","r",stdin);#endif scanf("%d%.

原创 leetcode 63. Unique Paths II （简单DP）

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the dia

原创 leetcode 62. Unique Paths （组合）

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the dia

原创 leetcode 61. Rotate List （链表循环移动 k 位）

Given a linked list, rotate the list to the right by k places, where k is non-negative.Example 1:Input: 1->2->3->4->5->NULL, k = 2Output: 4->5->1->2->3->NULLExplanation:rotate 1 steps to the right: 5->1->2->3-&gt

原创 leetcode 60. Permutation Sequence （n 位数的第 k 个排列）

The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order, we get the following sequence for n = 3:“123”“132”“213”“231”“312”“321”Given n and k, return the kth permutation sequence.Note:

原创 stanford cs143 Compilers 13.1 Semantics Overview