给定一个按随机顺序排列的整数列表,将其拆分为两个新的链表,这样每个列表元素总和的差异最大,列表长度相差不超过1(在原始情况下) list有奇数个元素). 我不能假设列表中的数字是唯一的.
我想到的算法是在原始链表(O(n·log n)时间,O(n)空间)上进行合并排序,然后使用递归函数走到列表末尾以确定其长度,在递归函数展开时进行拆分.递归函数是O(n)时间和O(n)空间.
这是最佳解决方案吗？如果有人认为它是相关的,我可以发布我的代码.
我正在从erlang.org课程中做这个练习:
2)编写一个在环中启动N个进程的函数,并在环中的所有进程周围发送M次消息.发送消息后,进程应正常终止.
这是我想出的:
-module(ring).
-export([start/2, node/2]).
node(NodeNumber, NumberOfNodes) ->
NextNodeNumber = (NodeNumber + 1) rem NumberOfNodes,
NextNodeName = node_name(NextNodeNumber),
receive
CircuitNumber ->
io:format("Node ~p Circuit ~p~n", [NodeNumber, CircuitNumber]),
LastNode = NodeNumber =:= NumberOfNodes - 1,
NextCircuitNumber = case LastNode of
true ->
CircuitNumber - 1;
false ->
CircuitNumber
end,
if
NextCircuitNumber > 0 ->
NextNodeName ! NextCircuitNumber;
true ->
ok
end,
if
CircuitNumber > 1 ->
node(NodeNumber, NumberOfNodes);
true ->
ok
end
end.
start(NumberOfNodes, NumberOfCircuits) ->
lists:foreach(fun(NodeNumber) -> …背景：我有一个很大的现有进程（它恰好在 AIX 上，所以基本上是 POSIX 语义），它是更大系统的一部分。现有流程旨在连续运行。这个过程的一个新要求是处理一种新的复杂输入流。为了降低风险，我决定 fork/exec 一个子进程来进行实际的输入处理，这将现有的主进程与错误输入数据的崩溃或挂起等问题隔离开来。
子进程从标准输入读取数据，处理后写入标准输出。我已经设置了所有通信管道，因此我可以将输入数据从主进程传递给子进程，并以另一种方式读取输出，这一切正常（非阻塞以避免死锁等）。子进程与主进程从外部源接收（有限）输入流所需的时间一样长。
我的问题是关于管道手柄本身。主进程通过调用close()连接到孩子的标准输入的管道来通知孩子输入流已经完成。只要主进程持有该管道写入端的唯一句柄，这就会起作用。如果主进程由于其他不相关的原因决定分叉怎么办？这将创建管道写入端的两个句柄，这意味着当我尝试关闭 stdin 管道的写入端时，孩子不会注意到，因为还有另一个打开的写入端句柄。另一个打开的手柄不在我的控制范围内。
我知道FD_CLOEXEC我可以在文件描述符上设置一些位，以便在exec()完成后自动关闭。但是，这不会防止主进程分叉但不执行的情况。
这个问题的一般解决方案是什么？我只能想到几个想法：
我无法解释有关将元素插入二叉搜索树的某个问题。我熟悉前序、后序和中序遍历，但我不熟悉以下问题：
假设我们按顺序将元素 3、5、6、1、2、4、7 插入到最初为空的二叉搜索树中。
如果我只得到一组按该顺序插入的数字，我应该如何将其变成二叉搜索树？3 会是根吗？我会自己平衡其他数字到正确的子树吗？在那种情况下不会有很多解释吗？是否遵循某种约定？
谢谢。
我正在努力将一些代码从AIX移植到Linux.部分代码使用shmat()系统调用来创建新文件.当SHM_MAP在可写模式下使用时,可以将文件扩展到其原始长度之外(在我的情况下为零):
将文件映射到段时,通过访问段来引用该文件.内存分页系统自动处理物理I/O. 超出文件末尾的引用会导致文件以页面大小的增量进行扩展.文件无法扩展到下一个段边界之外.
(AIX中的"段"是256 MB的地址空间块,"页面"通常是4 KB.)
我会想在Linux上做的是以下几点:
我知道我可以在Windows上使用VirtualProtect函数,PAGE_GUARD内存保护位和结构化异常处理程序执行此操作.Linux上相应的方法是做什么的呢？是否有更好的方法在Linux上实现这种写入扩展功能？
我已经考虑过:
mmap()一些固定的大尺寸,但我无法分辨应用程序代码写入了多少文件mmap() 本身似乎没有提供任何延长支持文件长度的工具当然,我只想对应用程序代码进行最小的更改即可.
在scons中,我试图建立一个UnitTest系统(见下面的代码),基于这里的一个很好的例子:http://spacepants.org/blog/scons-unit-test
然而,由于最近的scons 2.0.1及更新版本中存在问题,这会产生依赖性循环,如下所述:http://old.nabble.com/AddPostAction-executes-on-first-build-but-not-subsequent- td18360675.html(和其他地方).
有谁知道这个问题的良好解决方案或替代解决方案？
码:
def UnitTest(env, target, source, **kwargs):
curTest = env.Program(target, source, **kwargs)
env.AddPostAction(curTest, curTest[0].abspath)
env.Alias('unit_tests', curTest)
env.AlwaysBuild(curTest)
return curTest
SConsEnvironment.UnitTest = UnitTest
mandolineTest = env.UnitTest(target='./codeTest',
source = mix(['test.cc', 'base.cc'),
LIBS = default_libs + ['bgl',],
LIBPATH = default_libs_path,
CPPPATH = default_includes )
具体来说:我有两个无符号整数(a,b),我想计算(a*b)%UINT_MAX(UINT_MAX定义为最大无符号整数).这样做的最佳方法是什么？
背景:我需要为linux编写一个模拟几何序列的模块,从中读取将给我下一个元素(模UINT_MAX),我发现的唯一解决方案是将当前元素添加到自身时间,同时添加完成使用以下逻辑:(我用于算术序列)
for(int i=0; i<b; ++i){
if(UINT_MAX - current_value > difference) {
current_value += difference;
} else {
current_value = difference - (UINT_MAX - current_value);
}
当current_value = a在第一次迭代中(并且在每次迭代中更新,并且差异= a(总是).显然这不是一个智能解决方案.一个聪明的人如何实现这一点？
谢谢!
如果这是错误的堆栈交换,我很抱歉; 它似乎是最接近一个可能对计算机体系结构有帮助的地方.对于计算机系统中的家庭作业问题,我被问到:
Consider three direct mapped caches X, Y, and Z each interpreting an
8-bit address slightly differently according to the {tag:setIdx:byteOffset}
format speci?ed. For each address in the reference stream, indicate whether the
access will hit (H) or miss (M) in each cache.
C1 C2 C3
Address Formats: {2:2:4} {2:3:3} {2:4:2}
Address References in Binary: 00000010, 00000100...
我应该说每个地址引用是否会导致命中或错过,但我不知道从哪里开始.
对于格式,我认为标签意味着高速缓存块中数据的标记,setIdx意味着用于表示高速缓存中不同块的位数,而偏移量是可以选择的块内的特定字节.
我觉得我不明白什么是打击或错过.我认为有三种类型:强制,容量和冲突.如果我不知道缓存中已有什么,我怎么知道哪个是强制性的错过？在给定标签格式的情况下,如何判断缓存的容量？
感谢任何提示或提示.
我只是想知道命令svn log -v的输出是否始终相同.对我来说,它看起来像:
------------------------------------------------------------------------
r2 | username | 2011-01-16 16:52:23 +0100 (Sun, 16 Jan 2011) | 1 line
Changed paths:
D /foo
Removed foo
------------------------------------------------------------------------
r1 | balzarot | 2011-01-16 16:51:03 +0100 (Sun, 16 Jan 2011) | 1 line
Changed paths:
A /foo
created foo
------------------------------------------------------------------------
但我不知道它是否总是那样,特别是日期的格式!你能帮助我吗？
我目前正在攻读算法入门考试,我遇到了一个我无法解决的问题,问题是:你有一个n个整数的数组,前m个元素是偶数,剩下的元素很奇怪.您需要编写一个算法来查找m的值(找到最后一个偶数的索引),并且时间复杂度为O(log m).
我想做类似于二分搜索的事情,如果奇数就向左移动,如果直到我发现索引是偶数并且他的下一个是奇数,则向右移动但是这个东西在O(log n)而不是O(记录m).