// Use this variable as the eye position to start your rays. Vector3f eye_pos(0); int m = 0; for (int j = 0; j < scene.height; ++j) { for (int i = 0; i < scene.width; ++i) { // generate primary ray direction float x; float y; // TODO: Find the x and y positions of the current pixel to get the direction // vector that passes through it. // Also, don't forget to multiply both of them with the variable *scale*, and // x (horizontal) variable with the *imageAspectRatio* // To NDC space x = (float)i / scene.width - 0.5; y = (float)(scene.height - j) / scene.height - 0.5; // To world space x *= scale * imageAspectRatio; y *= scale;
Vector3f dir = Vector3f(x, y, -1); // Don't forget to normalize this direction! dir = normalize(dir); framebuffer[m++] = castRay(eye_pos, dir, scene, 0); } UpdateProgress(j / (float)scene.height); }
int depth = 1; while(!curLevel.empty()) { int curSize = curLevel.size(); // pop all curLevel and do next level while(curSize-- > 0) { // 最关键的，一定不要直接写成curLevel.size，因为curLevel会放后面的节点的呜呜呜 auto board = curLevel.front(); curLevel.pop();
auto coord = getPos(board); int x = coord.first; int y = coord.second; for(int mv = 0; mv < 4; ++mv) { int nextX = x + dx[mv]; int nextY = y + dy[mv]; if(0 <= nextX && nextX < 2 && 0 <= nextY && nextY < 3) { swap(board[nextX][nextY], board[x][y]); // cout << "trying : " << x << ", " << y << " to " << nextX << ", " << nextY << " withd d = " << depth <<endl; // print(board); int intBoard = toInt(board);
int depth = 1; while(!curLevel.empty()) { int curSize = curLevel.size(); // pop all curLevel and do next level while(curSize-- > 0) { auto board = curLevel.front(); curLevel.pop();
auto coord = getPos(board); int x = coord.first; int y = coord.second; for(int mv = 0; mv < 4; ++mv) { int nextX = x + dx[mv]; int nextY = y + dy[mv]; if(0 <= nextX && nextX < 2 && 0 <= nextY && nextY < 3) { swap(board[nextX][nextY], board[x][y]); // cout << "trying : " << x << ", " << y << " to " << nextX << ", " << nextY << " withd d = " << depth <<endl; // print(board); int intBoard = toInt(board);
classSolution { public: int m; int n; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, -1, 0, 1}; int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; intcutOffTree(vector<vector<int>>& forest){ // get all trees m = forest.size(); n = forest[0].size();
auto cmp = [](const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) { return a.second > b.second; }; priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, decltype(cmp)>trees (cmp);
for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(forest[i][j] > 1) { trees.push({{i, j}, forest[i][j]}); } } }
int curX = 0, curY = 0; int tarX = -1, tarY = -1; int res = 0; while(!trees.empty()) { auto tree = trees.top(); trees.pop();
intbfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty){ if (sx == tx && sy == ty) { return0; }
int row = forest.size(); int col = forest[0].size(); int step = 0; queue<pair<int, int>> qu; vector<vector<bool>> visited(row, vector<bool>(col, false)); qu.emplace(sx, sy); visited[sx][sy] = true; while (!qu.empty()) { step++; int sz = qu.size(); for (int i = 0; i < sz; ++i) { auto [cx, cy] = qu.front(); qu.pop(); for (int j = 0; j < 4; ++j) { int nx = cx + dirs[j][0]; int ny = cy + dirs[j][1]; if (nx >= 0 && nx < row && ny >= 0 && ny < col) { if (!visited[nx][ny] && forest[nx][ny] > 0) { if (nx == tx && ny == ty) { return step; } qu.emplace(nx, ny); visited[nx][ny] = true; } } } } } return-1; }
// using bfs from <curX, curY> to <tarX, tarY>, the depth of bfs should be the distance booltryWalk(vector<vector<int>>& forest, int curX, int curY, int tarX, int tarY, int& res){ // bfs queue<pair<int, int>> curLevel; vector<vector<int>> vis(m, vector<int>(n, false)); curLevel.push({curX, curY}); vis[curX][curY] = true;
int depth = 0; while(!curLevel.empty()) { // queue<pair<int, int>> nextLevel;
// while(!curLevel.empty()) { int curLevelSize = curLevel.size(); while(curLevelSize-- > 0) { auto curNode = curLevel.front();
curLevel.pop(); if(curNode == pair<int, int>{tarX, tarY}) { // update res res += depth; returntrue; } for(int mv = 0; mv < 4; ++mv) { int nextX = curNode.first + dx[mv]; int nextY = curNode.second + dy[mv];
while(!curLevel.empty()) { int curSize = curLevel.size(); while(curSize-- > 0) { auto curNode = curLevel.front(); int curDis = dis[curNode]; int x = curNode.first.first; int y = curNode.first.second; int curKey = curNode.second;
vec3 T = normalize(vec3(model * vec4(tangent, 0.0))); vec3 N = normalize(vec3(model * vec4(normal, 0.0))); // re-orthogonalize T with respect to N T = normalize(T - dot(T, N) * N); // then retrieve perpendicular vector B with the cross product of T and N vec3 B = cross(T, N);
// get texture coordinates before collision (reverse operations) vec2 prevTexCoords = currentTexCoords + deltaTexCoords;
// get depth after and before collision for linear interpolation float afterDepth = currentDepthMapValue - currentLayerDepth; float beforeDepth = texture(depthMap, prevTexCoords).r - currentLayerDepth + layerDepth;
// ----------------------------------- phase1 gbuffer获取纹理，法向，反射率给ssao shader #version 330 core layout (location = 0) out vec3 gPosition; layout (location = 1) out vec3 gNormal; layout (location = 2) out vec3 gAlbedo;
in vec2 TexCoords; in vec3 FragPos; in vec3 Normal;
voidmain() { // store the fragment position vector in the first gbuffer texture gPosition = FragPos; // also store the per-fragment normals into the gbuffer gNormal = normalize(Normal); // and the diffuse per-fragment color gAlbedo.rgb = vec3(0.95); }
// parameters (you'd probably want to use them as uniforms to more easily tweak the effect) int kernelSize = 64; // 减小然后去掉模糊，我们看一下ssao带来的波纹 float radius = 0.5; float bias = 0.025;
// 屏幕的平铺噪声纹理会根据屏幕分辨率除以噪声大小的值来决定 // tile noise texture over screen based on screen dimensions divided by noise size const vec2 noiseScale = vec2(800.0/4.0, 600.0/4.0);
uniform mat4 projection;
voidmain() { // get input for SSAO algorithm vec3 fragPos = texture(gPosition, TexCoords).xyz; vec3 normal = normalize(texture(gNormal, TexCoords).rgb); vec3 randomVec = normalize(texture(texNoise, TexCoords * noiseScale).xyz); // create TBN change-of-basis matrix: from tangent-space to view-space // 由于对每个表面法线方向生成采样核心非常困难，也不合实际，我们将在切线空间(Tangent Space)内生成采样核心，法向量将指向正z方向。 vec3 tangent = normalize(randomVec - normal * dot(randomVec, normal)); vec3 bitangent = cross(normal, tangent); mat3 TBN = mat3(tangent, bitangent, normal); // iterate over the sample kernel and calculate occlusion factor float occlusion = 0.0; for(int i = 0; i < kernelSize; ++i) { // get sample position vec3 samplePos = TBN * samples[i]; // from tangent to view-space samplePos = fragPos + samplePos * radius; // project sample position (to sample texture) (to get position on screen/texture) vec4 offset = vec4(samplePos, 1.0); offset = projection * offset; // from view to clip-space offset.xyz /= offset.w; // perspective divide offset.xyz = offset.xyz * 0.5 + 0.5; // transform to range 0.0 - 1.0 // get sample depth float sampleDepth = texture(gPosition, offset.xy).z; // get depth value of kernel sample // 。当检测一个靠近表面边缘的片段时，它将会考虑测试表面之下的表面的深度值；这些值将会(不正确地)影响遮蔽因子。 // range check & accumulate, 在这里根据它非常光滑地在第一和第二个参数范围内插值了第三个参数。如果深度差因此最终取值在radius之间， // 它们的值将会光滑地根据下面这个曲线插值在0.0和1.0之间 float rangeCheck = smoothstep(0.0, 1.0, radius / abs(fragPos.z - sampleDepth)); occlusion += (sampleDepth >= samplePos.z + bias ? 1.0 : 0.0) * rangeCheck; } occlusion = 1.0 - (occlusion / kernelSize); FragColor = occlusion; }
voidmain() { // 对于三个顶点，都去做这个 GenerateLine(0); // first vertex normal GenerateLine(1); // second vertex normal GenerateLine(2); // third vertex normal }
1 融合阶段：是将像素着色器中生成的各个片段的深度和颜色与帧缓冲结合在一起的地方。这个阶段也就是进行模板缓冲（Stencil-Buffer）和 Z 缓冲（Z-buffer）操作的地方。最常用于透明处理（Transparency）和合成操作（Compositing）的颜色混合（Color Blending）操作也是在这个阶段进行的。一下
// ambient *= attenuation; // remove attenuation from ambient, as otherwise at large distances the light would be darker inside than outside the spotlight due the ambient term in the else branche diffuse *= attenuation; specular *= attenuation; vec3 result = ambient + diffuse + specular; FragColor = vec4(result, 1.0); } else// 聚光灯外面 { // else, use ambient light so scene isn't completely dark outside the spotlight. FragColor = vec4(light.ambient * texture(material.diffuse, TexCoords).rgb, 1.0); } }
这里简单举个例子： 在text = abcccab中查找tar = ab出现次数，那么构造串： ab#abcccab，然后计算前缀函数： a b # a b c c c a b [0,0,0,1,2,0,0,0,1,2] = pi, 为前缀函数的结果，找出i>tar.size()且pi[i] == n的i的集合，每一个i - 2*tar.size()就是tar出现在text中的下标
classSolution { public: string shortestPalindrome(string s){ // prefix function && kmp: https://oi-wiki.org/string/kmp/#_10 int len = s.size(); string rs = s; reverse(rs.begin(), rs.end());
string all = s + "#" + rs; vector<int> pi(all.size(), 0); // see: our target is to find the "b c c b"，so we use kmp // s = b c c b a e // rs = e a b c c b // all = b c c b a e # e a b c c b // 求解pi[i] for(int i = 1; i < all.size(); ++i) { // i - 1的前缀函数的值，有s[0:j] == s[i - j : i - 1] int j = pi[i - 1]; // 当s[i] != s[j]，说明s[i]这个字符无法成为后缀的最后一个字符，此时pi[i] = 0，于是得一直找到下一个j，直到j = 0，或者s[i] == s[j] while(j > 0 && all[i] != all[j]) { j = pi[j - 1]; }
int x; // x是⼀个变量的名字，所以decltype(x) 是int。但是如果⽤⼀个小括号包覆这个名字，⽐如这样(x)， // 就会产⽣⼀个⽐名字更复杂的表达式。对于名字来说，x是⼀个左值，C++11定义了表达式(x) 则是⼀个左值。因此decltype((x)) 是int&
//decltype(x）是int，所以f1返回int decltype(auto) f1(){ int x = 0; ... return x; } //decltype((x))是int&，所以f2返回int& decltype(auto) f2(){ int x =0l; return (x); }
classWidget { public: Widget(int i, bool b); // 同上 Widget(int i, double d); // 同上 Widget(std::initializer_list<longdouble> il); //新添加的 … }; Widget w1(10, true); // calls first ctor Widget w2{10, true}; // uses braces, but now calls std::initializer_list ctor (10 and true convert to long double) Widget w3(10, 5.0); // uses parens and, as before, calls second ctor Widget w4{10, 5.0}; // uses braces, but now calls std::initializer_list ctor， (10 and 5.0 convert to long double) Widget w5(w4); // 使⽤小括号，调⽤拷⻉构造函数 Widget w6{w4}; // 使⽤花括号，调⽤std::initializer_list构造函数 Widget w7(std::move(w4)); // 使⽤小括号，调⽤移动构造函数 Widget w8{std::move(w4)}; // 使⽤花括号，调⽤std::initializer_list构造函数
classWidget { public: Widget(int i, bool b); Widget(int i, double d); Widget(std::initializer_list<bool> il); // element type is now bool … // no implicit conversion funcs }; Widget w{10, 5.0}; //错误！要求变窄转换
// 优点1： 限域枚举(scoped enum)，它不会导致枚举名泄漏 // 非限域枚举 enumColor { black, white, red }; // black, white, red 和 // Color⼀样都在相同作⽤域 auto white = false; // 错误! white早已在这个作⽤ // 域中存在
// 限域枚举 enum classColor { black, white, red }; // black, white, red // 限制在Color域内 auto white = false; // 没问题，同样域内没有这个名字 Color c = white; //错误，这个域中没有white Color c = Color::white; // 没问题 auto c = Color::white; // 也没问题（也符合条款5的建议）
// 优点2：在不存在任何隐式转换可以将限域枚举中的枚举名转化为任何其他类型，也就是拒绝隐式转换 enumColor { black, white, red }; // 未限域枚举 std::vector<std::size_t> // func返回x的质因⼦ primeFactors(std::size_t x); Color c = red; … if (c < 14.5) { // Color与double⽐较 auto factors = // 计算⼀个Color的质因⼦(!) primeFactors(c); … }
enum classColor { black, white, red }; // Color现在是限域枚举 Color c = Color::red; // 和之前⼀样，只是 多了⼀个域修饰符 … if (c < 14.5) { // 错误！不能⽐较Color和double auto factors = // 错误! 不能向参数为std::size_t的函数 primeFactors(c); // 传递Color参数 … }
// 若真的非常想，需要用类型转化如下： if (static_cast<double>(c) < 14.5) { // 奇怪的代码，但是有效 auto factors = // suspect, but primeFactors (static_cast<std::size_t>(c)); // 能通过编译 … }
// Rule of Three规则。这个规则告诉我们如果你声明了拷⻉构造函数，拷⻉赋值运算符， 或者析构函数三者之⼀，你应该也声明其余两个 // Rule of Three规则背后的解释依然有效，再加上对声明拷⻉操作阻⽌移动操作隐式⽣成的观察，使得C++11不会为那些有⽤⼾定义的析构函数的类⽣成移动操作。
auto spw = //spw创建之后，指向的Widget的 std::make_shared<Widget>(); //引用计数（ref count，RC）为1。 //std::make_shared的信息参见条款21 … std::weak_ptr<Widget> wpw(spw); //wpw指向与spw所指相同的Widget。RC仍为1 … spw = nullptr; //RC变为0，Widget被销毁。 //wpw现在悬空 if (wpw.expired()) … // if wpw doesn't point to an object
// 从weak_ptr创建shared_ptr std::shared_ptr<Widget> spw1 = wpw.lock(); // if wpw's expired, spw1 is null auto spw2 = wpw.lock(); // same as above, but uses auto std::shared_ptr<Widget> spw3(wpw); // if wpw's expired, throw std::bad_weak_ptr
// 在上⾯的 f({1,2,3}) 例⼦中，问题在于，如标准所⾔，将括号初始化器传递给未声明为 std::initializer_list 的函数模板参数，该标准规定为“⾮推导上下⽂”。简单来讲，这意味着编译器 在对fwd的调⽤中推导表达式 {1,2,3} 的类型，因为fwd的参数没有声明为 std::initializer_list 。 对于fwd参数的推导类型被阻⽌，编译器只能拒绝该调⽤。 // 有趣的是，Item2 说明了使⽤braced initializer的auto的变量初始化的类型推导是成功的。这种变量被 视为 std::initializer_list 对象，在转发函数应推导为 std::initializer_list 类型的情况，这 提供了⼀种简单的解决⽅法----使⽤auto声明⼀个局部变量，然后将局部变量转发： auto il = {1,2,3}; // il's type deduced to be std::initializer_list<int> fwd(il); // fine, perfect-forwards il to f
// 软件线程是有限的资源。如果开发者试图创建⼤于系统⽀持的硬件线程数量，会抛出 std::system_error 异常。即使你编写了不抛出异常的代码，这仍然会发⽣，⽐如下⾯的代码，即使 doAsyncWork 是 noexcept intdoAsyncWork()noexcept; // see Item 14 for noexcept // 这段代码仍然会抛出异常。 std::thread t(doAsyncWork); // throw if no more threads are available
// 有趣的是， std::async 的默认launch policy是以上两种都不是。相反，是求或在⼀起的。下⾯的两种 调⽤含义相同 auto fut1 = std::async(f); // run f using default launch policy auto fut2 = std::async(std::launch::async | std::launch::deferred, f); // run f either async or defered // 因此默认策略允许f异步或者同步执⾏。如同Item 35中指出，这种灵活性允许 std::async 和标准库的 线程管理组件（负责线程的创建或销毁）避免超载。这就是使⽤ std::async 并发编程如此⽅便的原 因。 auto fut = std::async(f); // run f using default launch policy // - ⽆法预测f是否会与t同时运⾏，因为f可能被安排延迟运⾏ // - ⽆法预测f是否会在调⽤ get或wait 的线程上执⾏。如果那个线程是t，含义就是⽆法预测f是否也在 线程t上执⾏ // - ⽆法预测f是否执⾏，因为不能确保 get或者wait 会被调⽤ // 默认启动策略的调度灵活性导致使⽤线程本地变量⽐较⿇烦，因为这意味着如果f读写了线程本地存储 （thread-local storage, TLS），不可能预测到哪个线程的本地变量被访问： auto fut = std::async(f); // TLS for f possibly for independent thread, but possibly for thread invoking get or wait on fut // 还会影响到基于超时机制的wait循环，因为在task的 wait_for 或者 wait_until 调⽤中会产⽣延迟求值(当wait或者get被调用才异步执行函数)（ std::launch::deferred ）。意味着，以下循环看似应该终⽌，但是实际上永 远运⾏: usingnamespace std::literals; //为了使用C++14中的时间段后缀；参见条款34
// 这种有话讲仅仅在内存表现正常时有效。“特殊”的内存不⾏。最常⻅的“特殊”内存是⽤来mapped I/O的内存。这种内存实际上是与外围设备（⽐如外部传感器或者显⽰器，打印机，⽹络端口） 通信，而不是读写（⽐如RAM）。这种情况下，再次考虑多余的代码： auto y = x; // read x y = x; // read x again // 如果x的值是⼀个温度传感器上报的，第⼆次对于x的读取就不是多余的，因为温度可能在第⼀次和第⼆ 次读取之间变化。类似的，写也是⼀样： x = 10; x = 20; // 如果x与⽆线电发射器的控制端口关联，则代码时控制⽆线电，10和20意味着不同的指令。优化会更改 第⼀条⽆线电指令。 // volatile 是告诉编译器我们正在处理“特殊”内存。意味着告诉编译器“不要对这块内存执⾏任何优化”。 所以如果x对应于特殊内存，应该声明为 volatile ： volatileint x; auto y = x; y = x; // can't be optimized away x = 10; // can't be optimized away x = 20; // 在处理特殊内存时，必须保留看似多余的读取或者⽆效存储的事实，顺便说明了为什么 std::atomic 不 适合这种场景。 std::atomic 类型允许编译器消除此类冗余操作。代码的编写⽅式与使⽤ volatile 的 ⽅式完全不同，但是如果我们暂时忽略它，只关注编译器执⾏的操作，则可以说， std::atomic<int> x; auto y = x; //概念上会读x（见下） y = x; //概念上会再次读x（见下） x = 10; //写x x = 20; //再次写x // 原则上，编译器可能会优化为： auto y = x; // conceptually read x x = 20; // write x // 对于特殊内存，显然这是不可接受的
// 因为 std::atomic 和 volatile ⽤于不同的⽬的，所以可以结合起来使⽤： volatile std::atomic<int> vai; // operations on vai are atomic and can't be optimized away // 这可以⽤在⽐如 vai 变量关联了memory-mapped I/O内存并且⽤于并发程序的场景。
// 最后⼀点，⼀些开发者尤其喜欢使⽤ std::atomic 的 load 和 store 函数即使不必要时，因为这在代码 中显式表明了这个变量不“正常”。强调这⼀事实并⾮没有道理。因为访问 std::atomic 确实会更慢⼀ 些，我们也看到了 std::atomic 会阻⽌编译器对代码执⾏顺序重排。调⽤ load 和 store 可以帮助识别 潜在的可扩展性瓶颈。从正确性的⻆度来看，没有看到在⼀个变量上调⽤ store 来与其他线程进⾏通信 （⽐如flag表⽰数据的可⽤性）可能意味着该变量在声明时没有使⽤ std::atomic 。这更多是习惯问 题，但是，⼀定要知道 atomic 和 volatile 的巨⼤不同。
1 dp: 首先搞明白动态规划的单元，注意，不仅仅是说增加一个元素，对分割造成了什么影响，而且还要考虑，不通的分割数目，本题目是分割，那么一定是分割数目以及分割对象带来的变化为dp的状态迁移， dp[i][j] means: res of: nums[:i] to be splited in j’s segments, dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1}，所以
classSolution { public: intsplitArray(vector<int>& nums, int m){ int n = nums.size(); vector<int> preSum = { 0 }; for(int i = 0; i < n; ++i) { preSum.push_back(preSum.back() + nums[i]); } // // dp[i][j] means: res of: nums[:i] to be splited in j's segments // // dp[i][j] = max {dp[k][j-1], sum[k+1, i] | j <= k <= i - 1} // vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX)); // dp[1][1] = nums[0]; // for(int i = 1; i <= n; ++i) { // for(int j = 1; j <= min(m, i); ++j) { // if(j == 1) { // dp[i][1] = preSum[i] - preSum[0]; // continue; // } // int tmpMaxMin = 0; // for(int k = j - 1; k < i; ++k) { // tmpMaxMin = max(dp[k][j-1], preSum[i] - preSum[k]); // dp[i][j] = min(dp[i][j], tmpMaxMin); // } // } // } // return dp[n][m]; // binsearch x as the min max res int st = *max_element(nums.begin(), nums.end()); int ed = preSum[n]; int x = -1;
bool lastCheck = false; while(st < ed) { x = (st + ed) >> 1; lastCheck = xIsLarge(x, nums, m); if(lastCheck) { ed = x; // when ed - st = 1, (st + ed) >> 1 == st } else { st = x + 1; } } // at last, st == ed return st; }
boolxIsLarge(int x, vector<int>& nums, int m){ int cnt = 1; int curSum = 0; for(int i = 0; i < nums.size(); ++i) { if(curSum + nums[i] > x) { ++cnt; curSum = nums[i]; } else { curSum += nums[i]; } } // cout << ">> x/cnt is" << x << "/" << cnt << endl; return cnt <= m; } };
classSolution { public: boolcanCross(vector<int>& stones){ int n = stones.size(); // jump to i, and last jump dis vector<vector<bool>> jump(n , vector<bool>(n, false)); jump[0][0] = true;
// the i th jump len <= i for(int i = 1; i < n; ++i) { if(stones[i] - stones[i - 1] > i) { returnfalse; } }
// dp, from j jump to i bool res = false; for(int i = 1; i < n; ++i) { for(int j = 0; j < i; ++j) { int k = stones[i] - stones[j]; // cout << j << " -> " << i << " 's dis: " << k << endl; if(k > j + 1) { continue; } // cout << jump[j].size() << " / " << k + 1 << " jump[j][k] || jump[j][k-1] || jump[j][k+1] " << jump[j][k] << jump[j][k-1] << jump[j][k+1] << endl; jump[i][k] = jump[j][k] || jump[j][k-1] || jump[j][k+1]; if(i == n - 1 && jump[i][k]) { res = true; } } } return res; } };
// case1: cut the same ball if(tarBallStr == lastTarBallStr) { continue; }
// use this char, find put pos for(int i = 0; i <= board.size(); ++i) { // case2: only insert at the start of str with same chars if(i > 0 && board[i - 1] == hand[k]) { continue; }
// case3: only put when cur is equal current || when cur is not equal to two continuous same chars if(i < board.size() && board[i] == hand[k] || \ i > 0 && board[i] == board[i-1] && hand[k] != board[i-1]) { string tmpBoard1 = board; tmpBoard1.insert(i, tarBallStr); // reduce repeat balls reduceRepeat(tmpBoard1);
// put to tarBall left and right int lRes = bfs(tmpBoard1, nextHand);
int bigInt = 1000000007; intcheckRecord(int n){ if(n <= 2) { return n == 1 ? 3 : 8; } // we can use A to interrupt the LLL, so we calculate A after only PL // // n's day without 'A' // vector<vector<long long>> dp(n + 1, vector<long long>(3, 0)); // // dp[i][j], j means end with n's L // dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 0;
// for(int i = 2; i <= n; ++i) { // // end with p // dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]; // // ent with l // dp[i][1] = (dp[i - 1][0]) % bigInt;
// // when there is a A: // long long res = 0; // res += ((dp[n][0] + dp[n][1]) % bigInt + dp[n][2]) % bigInt; // res += (((dp[n-1][0] + dp[n-1][1]) % bigInt + dp[n-1][2]) % bigInt * n) % bigInt;
// n's day without 'A' vector<vector<vector<longlong>>> dp(n + 1, vector<vector<longlong>>(2, vector<longlong>(3, 0))); // dp[i][j], j means end with n's L dp[0][0][0] = 1;
for(int i = 1; i <= n; ++i) { // end with p for(int j = 0; j < 2; ++j) { for(int k = 0; k <= 2; ++k) { dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % bigInt; } }
// end with a for(int k = 0; k <= 2; ++k) { dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % bigInt; } // ent with l for(int j = 0; j < 2; ++j) { for(int k = 1; k <= 2; ++k) { dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k-1]) % bigInt; } } }
int res = 0;
for(int j = 0; j < 2; ++j) { for(int k = 0; k < 3; ++k) { res = (res + dp[n][j][k]) % bigInt; } }
// assume the biggest bit starts with 0 int res = dp[lastOneBitIdx][0] + dp[lastOneBitIdx][1]; // cout << "assume biggest bit = 0's res : " << res << endl;
classSolution { public: int n = -1; int k = -1; vector<char> kVec; string crackSafe(int n, int k){ // since for each bit, there a k's possiblity // so the final str's length = k^n // consider a G, vertices are {0, 1, ..., k-1} // for each edge: vi -> vj(vi could equal vj), // there shall be n-1's such same edge // we just need a way to walk through the G // try hierholzer algo if(1 == n) { string tmpRes = ""; for(int i = 0; i < k; ++i) { tmpRes.push_back(i + '0'); } return tmpRes; }
this->k = k; this->n = n; for(int i = 0; i < k; ++i) { kVec.push_back(i + '0'); }
unordered_set<string> seen; unordered_map<string, vector<char>> graph; buildGraph("", n - 1, graph); string stStr(n-1, '0'); string res = ""; hierholzer(stStr, graph, res, seen); // when n=3, k=3, we start from "00" node, so we add reverse of "00" to the end of the res, cause hierholzer produce a reverse eular path (start from "00", end to "00") res += stStr; return res; }
// no memo dfs, too slow intdfs(int tar, int markPos, unordered_map<char, vector<int>>& ringMap, string& key){ if(tar == key.length()) { return0; }
int minStep = INT_MAX; // for cur key char, try ervery possible way on the ring for(auto tarPos : ringMap[key[tar]]) { int curStep = minDis(tarPos, markPos); // rotate curStep += 1; // write
// choosing: right int tmpRightCover = min( // r的监控器对r的两个子节点都有监控作用，于是直接去计算两个子节点的子节点 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l), min( // r的监控器对r的两个子节点中的右孩子有监控作用，于是计算方式变为算右孩子两个子节点加上左侧节点 // partly ignore, will not put cam on r_rr, may on r_r 1 + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_rl) + minCameraCover(r_l), // r的监控器对r的两个子节点中的左孩子有监控作用，于是计算方式变为算左孩子两个子节点加上右侧节点 // partly ignore, will not put cam on r_rl, may on r_l 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rr) + minCameraCover(r_l) ) );
// // choosing: right // int tmpRightCover = min( // // don't ignore, will not put cam on r_rl, r_rr // 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_l), // min( // // partly ignore, will not put cam on r_rr, may on r_r // 1 + minCameraCover(r_rrl) + minCameraCover(r_rrr) + minCameraCover(r_rl) + minCameraCover(r_l), // // partly ignore, will not put cam on r_rl, may on r_l // 1 + minCameraCover(r_rll) + minCameraCover(r_rlr) + minCameraCover(r_rr) + minCameraCover(r_l) // ) // );
classSolution { public: vector<int> sortArray(vector<int>& nums){ // quick sort, most bad when it is sorted o(n**2), not stable // quickSort(0, nums.size() - 1, nums);
voidhead_sort(int st, int ed, vector<int>& nums){ // init buildMaxHeap(nums);
// everytime select max and put to end and call maxHeapify int len = nums.size(); for(int ed = len - 1; ed >= 0; --ed) { swap(st, ed, nums); // nums[ed:] is sorted maxHeapify(st, ed - 1, nums); } }
voidbuildMaxHeap(vector<int>& nums){ // start from the last dad node, till all dad node be the max heap root int len = nums.size(); for(int dad = len / 2 - 1; dad >= 0; --dad) { maxHeapify(dad, len - 1, nums); } }
intpartition(int st, int ed, vector<int>& nums){ // put 'smaller than st' to left, others right int r = ed; int l = st; // st is the first blank place int pivot = nums[st]; while(l < r){ // r form right to left while(r > l && nums[r] > pivot) { r--; } nums[l] = nums[r];
// l form left to right while(l < r && nums[l] <= pivot) { l++; } nums[r] = nums[l]; } nums[l] = pivot; return l; }
voidswap(int& a, int& b, vector<int>& nums){ // cout << "swaping! " << a << " " << b << endl; int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; }
voidprint(vector<int>& nums){ for(auto& i : nums) { cout << i << " "; } cout << "\n"; } };
classSolution { public: int len = -1; intmaximumGap(vector<int>& nums){ len = nums.size(); if(len <= 1) { return0; } // bucket sort bucketSort(nums);
// getMaxGap int gap = INT_MIN; int last = nums[0]; for(auto i : nums) { gap = max(i - last, gap); last = i; } return gap; }
voidbucketSort(vector<int>& nums){ int maxNum = *max_element(nums.begin(), nums.end()); int bucketSize = maxNum / len + 1; int bucketNum = len + 1; vector<list<int>> buckets(bucketNum, list<int>(0));
// put to buckets for(int i = 0; i < len; ++i) { insertSort(buckets[nums[i] / bucketSize], nums[i]); } // merge int idx = 0; for(auto& l : buckets) { for(auto num : l) { nums[idx++] = num; } } } voidinsertSort(std::list<int>& l, int num){ for(list<int>::iterator it = l.begin(); it != l.end(); ++it) { if(*it > num) { l.insert(it, num); return; } }
