Arts

题目： Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: 1 2 3 4 5 6 [1,null,2,3] 1 \ 2 / 3 Output: 1 [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 遍历顺序“根-左-右” 实现： 使用栈实现 从根节点开始，先将根节点压入栈，保存结果值，然后移动到左节点， 保证“根-左”顺序， 为空后出栈，取其右节点入栈中。这样就保证了访问顺序为“根-左-右”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> ss; TreeNode *p = root; while (!ss.empty()||p){ if (p!=NULL){ ss.push(p); res.push_back(p->val); p = p->left; } else{ p = ss.top(); ss.pop(); p=p->right; } } return res; } }; 实现： 递归实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; preorder(root, res); return res; } void preorder(TreeNode *root, vector<int> &res){ if (!root) return; res.push_back(root->val); preorder(root->left, res); preorder(root->right, res); } }; 参考: [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 ...

对于正常使用rm无法删除的文件可以通过查找inode进行删除 1 2 ls -i find -inum xxx -delete or 1 2 ls -i find -inum xxx -exec rm -i {} \; 直接删除 1 2 3 4 5 6 7 8 9 [root@centosgpt vm]# ls -i 2278688 &gt; 13592459 memdump2.c~ 13592454 memzero 7506486 test.c~ 2275894 118902.mem 2275882 memdump2.py 13592461 memzero.c 9733651 translate ... [root@centosgpt vm]# find -inum 2278688 -delete [root@centosgpt vm]# ls 118902.mem idle.py~ memdump3.c memory_layout processwrite.c test.c~ vsyscall.c 18 memdump memdump4 memory_layout.c processwrite.c~ translate 交互式 1 2 3 4 5 6 7 8 9 [root@centosgpt vm]# ls -i 7506464 &gt; 13592459 memdump2.c~ 13592454 memzero 7506486 test.c~ 2275894 118902.mem 2275882 memdump2.py 13592461 memzero.c 9733651 translate [root@centosgpt vm]# find -inum 7506464 -exec rm -i {} \; rm: remove regular empty file ‘./&gt;’? y [root@centosgpt vm]# ls 118902.mem idle.py~ memdump3.c memory_layout processwrite.c test.c~ vsyscall.c 18 memdump memdump4 memory_layout.c processwrite.c~ translate

Linux进程内存布局及映射信息 处理器在运行程序时，需要存储器来存放程序和程序使用的数据， 现代操作系统提供了存储器的抽象:虚拟存储器, 使得应用程序来说不用过多的考虑物理存储使用，简化了内存管理. 虚拟存储器 虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件完美的交互，它为每一个进程提供了一个大的、一致的、私有的地址空间. --深入理解计算机系统 在多应用复杂任务场景下，进程直接使用物理内存存在一些问题： 处理数据大小: 应用程序存储的使用,将受制于物理内存大小; 复杂性：应用程序要清楚需要使用的物理地址，何时申请，何时释放，甚至产生碎片后是否要进行整理等; 安全性：如果一个进程不小心改写了另外一个进程也正在使用的内存，进程可能会莫名其妙的挂掉. 虚拟存储器很好的解决了这类问题： 高效使用内存: 将主存看作存储在磁盘上地址空间的高速缓存，主存只保存活动区域 简化存储管理: 虚拟存储提供一致的地址空间 对进程空间的保护: 以免地址空间被其他进程破坏 内存布局、映射的信息 虚拟存储用于管理，最终还是要使用到物理内存, Linux提供了一些接口可以查看，进程(虚拟)内存布局， 虚拟内存与物理内存的映射等。 相关的proc文件 可以通过下面的proc文件查看布局及映射信息 /proc/iomem: 物理内存布局 /proc/pid/maps: 进程虚拟内存布局 /proc/pid/mem: 进程内存查看 /proc/pid/pagemap: 虚拟内存映射到物理内存的信息 /proc/kpagecount: 映射的次数 /proc/kpageflags: 页面的状态 /proc/kpagecgroup: 可以查看每一页对应的cgroup的inode 物理内存使用布局 /proc/iomem 这个文件显示统内存与每个物理设备映射关系, 虚拟机内存物理内存配置了512M 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 00000000-00000fff : Reserved 00001000-0009ebff : System RAM 0009ec00-0009ffff : Reserved 000a0000-000bffff : PCI Bus 0000:00 000c0000-000c7fff : Video ROM 000ca000-000cafff : Adapter ROM 000cc000-000cffff : PCI Bus 0000:00 000d0000-000d3fff : PCI Bus 0000:00 000d4000-000d7fff : PCI Bus 0000:00 000d8000-000dbfff : PCI Bus 0000:00 000dc000-000fffff : Reserved 000f0000-000fffff : System ROM 00100000-1fedffff : System RAM 0ba00000-0c600de0 : Kernel code 0c800000-0cc16fff : Kernel rodata 0ce00000-0d00a8ff : Kernel data 0d5dc000-0dbfffff : Kernel bss 1fee0000-1fefefff : ACPI Tables 1feff000-1fefffff : ACPI Non-volatile Storage 1ff00000-1fffffff : System RAM ... 第一列:内存地址范围 第二列:对应的内存用途 可以看到含有System RAM的几个段 ...

工作需要汇总整理相关excel数据信息，并按照规定格式进行反馈，用python写了一个脚本处理了一下。 样例中表格内容也进行了调整。 环境： windows10 python3.7 + openpyxl 目标： 以data1数据为准，通过查找data2补全相关信息, 将数据填入要求的result文件中。 表格格式: 表格1 data1.xlsx 姓名 张三 李四 表格2 data2.xlsx 序号 姓 名 性别 身份证号 联系电话 01 张三 男 130012345678901234 13911111111 02 李四 男 123012345678901234 13922222222 03 王五 男 123012345678901234 13933333333 表格3 result.xlsx 序号 所属部门 厂商 姓名 身份证号 联系电话 备注 代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 from openpyxl import load_workbook from openpyxl import Workbook import pandas as pd wb_in = load_workbook( filename = '.\\test\\data1.xlsx') ws_in = wb_in.active ## 名字列表开始结束行号 start_index = 2 end_index = 4 wb_info = load_workbook( filename = '.\\test\\data2.xlsx') ws_info = wb_info.active wb_out = load_workbook( filename = '.\\test\\result.xlsx') ws_out = wb_out.active out_index = 2 ## 找到要统计人员姓名 for x in range(start_index,end_index): name = ws_in.cell(row=x,column=1) print(name.value) ## 查找要统计人员附件信息并更新到统计表格中 find_flag = 0 for row in ws_info.iter_rows("B"): for col in row: #print(col.value) if (str(col.value).strip() == str(name.value).strip()) and (find_flag == 0): ## 第四列 身份证 第五列 联系电话 idno = ws_info.cell(row=col.row,column=4) phoneno = ws_info.cell(row=col.row, column=5) ## 更新到统计文件 ws_out['A'+ str(out_index)].value = str(out_index-1) ws_out['B'+ str(out_index)].value = 'XX部' ws_out['C'+ str(out_index)].value = 'XXX' ws_out['D'+ str(out_index)].value = name.value ws_out['E'+ str(out_index)].value = idno.value ws_out['F'+ str(out_index)].value = phoneno.value out_index = out_index + 1 find_flag = 1 break if find_flag == 0: print(name.value) wb_out.save( filename = '.\\test\\result.xlsx') 运行结果 序号 所属部门 厂商 姓名 身份证号 联系电话 备注 1 XX部 XXX 张三 130012345678901234 13911111111 2 XX部 XXX 李四 130012345678901234 13922222222 参考 Openpyxl Doc Using openpyxl to find rows that contain cell with specific value (Python 3.6)

这篇文章 Timers and time management in the Linux kernel. Part 5. 是出自 linux-insides一书中 Timers and time management 章节 Introduction to timers 内核版本比对5.5-rc6 进行了相关调整, 增加相关备注 clockevents框架简介 这是本章节的第五部分，它描述了Linux内核中与计时器和时间管理相关的内容。正如您可能从本部分的标题中注意到的那样，将讨论clockevents框架。我们已经在本章的第二部分中看到了一个框架。这是clocksource框架。这两个框架都是Linux内核中的计时抽象。 首先，让我们回忆一下clocksource框架以及它的用途。 clocksource框架的主要目标是提供timeline。如documentation中所述： 例如，在Linux终端上输入命令date将最终读取时钟源以确定确切的时间。 Linux内核支持许多不同的时钟源。 您可以在drivers/clocksource中找到其中的一些。 例如，老一些的比如Intel 8253-可编程间隔计时器，频率为1193182, 还有一个-ACPI PM计时器，频率为3579545Hz。 除了drivers/clocksource目录之外，每种体系结构都可以提供自己的体系结构专用时钟源。 例如x86架构提供了高精度事件计时器，或者例如是powerpc通过timebase寄存器提供对处理器计时器的访问。 每个时钟源都提供单调原子计数器。 Linux内核支持大量不同的时钟源，每个时钟源都有自己的参数，例如frequency。 clocksource框架的主要目标是提供API，以选择系统中最佳的可用时钟源，即频率最高的时钟源。 clocksource框架的另一个目标是由时钟源提供的以人类时间单位的表示的原子计数器。 在这个时候，纳秒是Linux内核中给定时钟源的时间值单位的首选。 clocksource框架被定义在include/linux/clocksource.h头文件中的clocksource结构中，其中包含时钟源的name，系统中某些时钟源的额定值(频率较高的时钟源在系统中具有最大的额定值)，系统中所有已注册时钟源的list，enable和disable字段来启用和禁用时钟源，指向read函数(必须返回时钟源的原子计数器)的指针等等。 另外，clocksource结构提供了两个字段：mult和shift，这是由某个时钟源提供给人类计时单位的原子计数器转换所必需的，即nanoseconds.通过以下公式进行转换： 1 ns ~= (clocksource * mult) &gt;&gt; shift 我们已经知道，除了clocksource结构之外，clocksource框架还提供了一个API，用于注册具有不同频率比例因子的时钟源： 1 2 static inline int clocksource_register_hz(struct clocksource *cs, u32 hz) static inline int clocksource_register_khz(struct clocksource *cs, u32 khz) 时钟源注销: 1 int clocksource_unregister(struct clocksource *cs) … 除了clocksource框架之外，Linux内核还提供了clockevents框架。 如文档中所述： 时钟事件与时钟源在概念上相反 主要目标是管理时钟事件设备，或者换句话说，即管理允许注册事件的设备，换句话说，就是要进行以下操作的设备：中断将在将在将来的指定时间发生。 现在，我们对Linux内核中的clockevents框架有了一些了解，现在是时候来看一下API. clockevents框架相关API 描述时钟事件设备的主要结构是clock_event_device结构。 此结构在include/linux/clockchips.h头文件中定义，并且包含大量字段。 除了clocksource结构之外，它还具有name字段，其中包含时钟事件设备的可读名称，例如local APIC计时器： 1 2 3 4 5 6 static struct clock_event_device lapic_clockevent = { .name = "lapic", ... ... ... } 某个时钟事件设备的event_handler，set_next_event，next_event函数的地址是中断处理程序，下一个事件的设置程序和本地分别存储下一个事件。 clock_event_device结构的另一个字段是-features字段。 它的价值可能来自以下通用功能： ...

题目： There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v. ...

内存管理发展阶段 内存(RAM)是计算机一种重要资源, 随着应用越来越复杂，不管存储器有多大,程序都可以把他填满,这就迫使人们不断寻找解决方案去管理它. 内存管理经历的几个阶段； 无存储抽象阶段 (No Memory abstraction) 地址空间 (Address Spaces) 虚拟内存 (Virtual Memory) 无存储抽象阶段: 直接使用物理地址, 简单和划分了用户和操作系统，(驱动程序)使用的内存. 早期的MSDOS采用这种管理方案。 通过每个进程基址寄存器和界限寄存器实现动态重定位,映射到不通的物理内存。通过交换技术和空闲内存管理， 处理内存超载 构建虚拟地址空间，通过MMU(内存管理单元)完成虚拟内存与物理内存的映射。 分页 分页就是出现虚拟内存这个阶段.虚拟地址按照固定大小划分成若干个页面Page， 物理内存中对应为页框 Page Frame (物理内存最小数据单位), 当程序试图访问内存时，MMU根据虚拟地址映射为物理地址. 页面大小 不同处理器体系结构页面大小 体系结构 最小页面 支持大页面 32-bit x86 4 KiB 4 MiB, 2 MiB x86-64 4 KiB 2 MiB, 1 GiB IA-64 (Itanium) 4 KiB 8 KiB, 64 KiB, 256 KiB, 1 MiB, 4 MiB, 16 MiB, 256 MiB Power ISA 4 KiB 64 KiB, 16 MiB, 16 GiB SPARC v8 with SPARC Reference MMU 4 KiB 256 KiB, 16 MiB ARMv7 4 KiB 64 KiB, 1 MiB , 16 MiB UltraSPARC Architecture 2007 8 KiB 64 KiB, 512 KiB , 4 MiB, 32 MiB, 256 MiB, 2 GiB, 16 GiB 页面大小考虑因素(wiki) 页面大小通常有处理器体系结构决定， 目前常用页面大小4KB。选择最佳页面大小要考虑一下几个因素： ...

这篇文章 Huge TLB Pages是出Linux Kernel文档 概述 该文档目的是简要概述在Linux内核HugePage。 现代CPU体系架构支持基于多个页面。 例如，x86 CPU通常支持4K和2M（如果体系结构支持，则为1G）页面大小，ia64架构支持多种页面大小4K，8K，64K，256K，1M，4M，16M，256M和ppc64支持4K和16M。 TLB是虚拟到物理的缓存转化。 通常，这是处理器上非常稀缺的资源。 操作系统试图充分利用有限数量的TLB资源。 现在，随着物理内存越来越大，这种优化变得越来越（几个GB）容易获得。 用户可以通过使用mmap系统调用来使用Linux内核中的Huge Page或标准SYSV共享内存系统调用(shmget，shmat)。 首先，Linux内核需要使用CONFIG_HUGETLBFS构建和CONFIG_HUGETLB_PAGE配置选项。 /proc/meminfo 文件提供内核Huge Page池中的持久性Huge Page的总数。它还显示默认Huge Page大小和空闲的数量，保留数量的信息 以及默认大小的Huge Page池中的多余Huge Page。 需要Huge Page大小才能生成正确的对齐方式， 映射Huge Page区域的系统调用的参数大小。 /proc/meminfo 文件中包含Huge Page信息如下: 1 2 3 4 5 6 HugePages_Total: uuu HugePages_Free: vvv HugePages_Rsvd: www HugePages_Surp: xxx Hugepagesize: yyy kB Hugetlb: zzz kB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 HugePages_Total 总页面数量 HugePages_Free 未使用页面数量 HugePages_Rsvd 预留未使用数量 HugePages_Surp 预留未使用数量, 指大于/proc/sys/vm/nr_hugepages部分， 最大保留值由/proc/sys/vm/nr_overcommit_hugepages控制. Hugepagesize 每个页的大小单位Kb Hugetlb 占用内存大小（kB）相当于 HugePages_Total * Hugepagesize 详细信息可以查看 /sys/kernel/mm/hugepages /proc/filesystems 可以看到内核中的的hugetlbfs文件系统类型 ...

环境 cenos7(X86_64) + openssh windows10 putty 配置 生成公私钥对 - 使用puttygen.exe生成公私钥对； 1. 运行puttygen.exe 点击 Generate按钮， 鼠标在进度条下方的窗口空白区移动生成公私钥对。 2. 分别点击 Save public key,Save private key导出后保存在本地. 安装公钥到远程服务器 公钥上传server, 相应用户目录下, 生成authorized_keys文件; 1 2 mkdir .ssh ssh-keygen -i -f mypublickey >> .ssh/authorized_keys 其中mypublickey,为上一个步骤保存的公钥文件 配置putty 载入服务器配置信息 Session 选项卡片 Load按钮，载入要登录服务器信息 登录用户 Connection - Data选项，Auto-login username 输入登录使用的用户名 配置私钥 Connection - SSH - Auth选项卡片中, 点击Browse按钮选择之前导出私钥文件 保存信息 Session 选项卡片 Save按钮，保存登录服务器信息配置步骤： 常见问题 Server refused our key： 由于目录权限问题到导致可以通过以下命令处理： 1 2 $ chmod 700 ~/.ssh $ chmod 600 ~/.ssh/authorized_keys ...

题目： Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1: Input: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Output: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Example 2: 1 2 3 4 Input: [[0,0,0], [0,1,0], [1,1,1]] Output: 1 2 3 [[0,0,0], [0,1,0], [1,2,1]] Note: ...