菜鸡的博客 | WTCL

347. Top K Frequent Elements

你快乐吗

天涯岂是无归意争奈归期未可期 C++，最小堆+hash。说一个很多人不知道的小知识点，C++中不同pair之间大小比较默认先比较first，再比较second，这样对做这道题有帮助。如果没有pair这个特性的话，可能得写个struct进行重载或者自定义比较函数了。思路也是很简单的，先用hash达到记录元素频次的目的，然后再用一个大小为K的最小堆，选出频次最高的K个元素...

Posted by bbkgl on December 18, 2019

338. Counting Bits

你快乐吗

朝辞白帝彩云间千里江陵一日还 C++，数学题。。。这想到了，就是一分钟的事情。我是找规律发现的。分奇数和偶数：偶数的二进制1个数超级简单，因为偶数是相当于被某个更小的数乘2，乘2怎么来的？在二进制运算中，就是左移一位，也就是在低位多加1个0，那样就说明dp[i] = dp[i / 2] 奇数稍微难想到一点，奇数由不大于该数的偶数+1得到，偶数+1在...

Posted by bbkgl on December 17, 2019

C++中负数下标

C++

一川烟草满城风絮梅子黄时雨在阅读luajit源码的时候，发现在特别多地方使用了负数下标，当时觉得特别奇怪，C的数组中使用负数下标，不是会直接报段错误吗？其实这里就引出一个问题，下标在C/C++中，代表的实际意义是什么？下标的意义可以说，在碰到负数下标这个操作之前，我根本就没思考过，为什么会存在下标索引这个操作呢，为什么下标会从0开始？在此之前，...

Posted by bbkgl on December 15, 2019

关于程序入口地址

profile

孤帆远影碧空尽唯见长江天际流关于编译器这里先贴出我使用的开发机信息：疑问来了使用readelf -h <filename>，随意读取一个可执行文件：怪事发生了，居然提示是共享库文件。。。于是我们随便用gcc去编译一段代码，生成可执行文件：还是共享库文件。。。于是我去试试从其他地方拷贝过来的可执行文件：居然是EX...

Posted by bbkgl on December 12, 2019

“远程”获取进程中函数参数值

profile

东风夜放花千树更吹落星如雨获取一个已经在运行的C++进程的函数堆栈信息之前已经讲过了，然后就会想到，怎么获取到对应函数的参数值呢？这是一个不简单的问题，前面讲过了函数压栈的问题，这次讲一下寄存器。函数参数传递程序寄存器在X64计算机上，有多个寄存器，这些寄存器都用来保存函数调用时的临时信息，还有很重要的一点，寄存器是所有函数调用过程中共享的存储资源...

Posted by bbkgl on December 4, 2019

程序中栈帧的分布

profile

千磨万击还坚劲任尔东西南北风函数调用函数调用就是就是一层一层递进的执行某些功能（动作），在这个过程中，考虑到每个函数执行结束后还要返回，必然会留下很多信息，而计算机也需要存储这些信息。举个例子，A()中调用了B()，那B()执行结束后怎么知道返回A呢，以及A中定义的那些局部变量呢？为了存储这些信息，则计算机给每个即将执行或正在执行的函数分配了一个调用过程中存储信息的空...

Posted by bbkgl on December 3, 2019

获取其他进程的全局变量

profile

微微风簇浪散作满河星如何获取存储在bss段上的，未初始化的“其他进程”的全局变量？首先考虑到的是使用ptrace，但是ptrace获取其他进程的全局变量，需要该变量的地址。那如何得到对应bss段变量的地址呢？使用对应程序段的起始地址+变量的地址偏移量，接下来进行验证和说明。这里先贴出被测试的程序： #include <cstdio> #inc...

Posted by bbkgl on December 2, 2019

C/C++获取程序堆栈信息

profile

碧玉妆成一树高万条垂下绿丝绦前言实习的时候有个需求，需要实现一个profile工具，工具的功能（简述）有：根据进程ID和服务器ip获取程序中C++的堆栈信息根据进程ID和服务器ip获取程序中Lua的堆栈信息将堆栈调用信息绘制成火焰图目前打算使用libunwind获得C++的堆栈信息。 libunwind 这玩意特别特别少，特别是相关接口...

Posted by bbkgl on December 1, 2019

337. House Robber III

我太难了

春江花朝秋月夜往往取酒还独倾 C++，动态规划+dfs。这道题里其实也是一种动态规划的思想，而且很容易就能想到如何求解最优解。每个结点对应两种状态，计算自己和不计算自己，也就是对应题意中的偷与不偷。其中每种状态都能对应一个最优解，也就是二叉树中由下到上，考虑偷不偷本结点，得到能偷到的最大钱数。需要注意的是：如果考虑偷当前结点，则一定不能偷最近的左右...

Posted by bbkgl on December 1, 2019

322. Coin Change

我太难了

日出扶桑一丈高人间万事细如毛 C++，动态规划。比较经典的dp题，动态规划的一个最大的特点就是当前的最优解一定可以由之前的某个最优解得到，简而言之就是状态转移方程。这道题也是一样的，因为零钱种类总是有限的，假设\(dp(x) \)表示\(x \)最少可以由(dp(x) \)枚硬币相加得到，我们可以写出如下的状态转移方程： \[dp(x) = min\{dp(x-...

Posted by bbkgl on November 30, 2019

我太菜了

347. Top K Frequent Elements

你快乐吗

338. Counting Bits

你快乐吗

C++中负数下标

C++

关于程序入口地址

profile

“远程”获取进程中函数参数值

profile

程序中栈帧的分布

profile

获取其他进程的全局变量

profile

C/C++获取程序堆栈信息

profile

337. House Robber III

我太难了

322. Coin Change

我太难了

FEATURED TAGS

ABOUT ME

FRIENDS