给定一个array和一个固定值sum,

给 定一个array和一个固定值sum,
找出array中加和等于sum的最少元素个数
array中肯定有{1}这个元素，除了{1}这个元素只能用一次意外，其他元素可以重复使用

例如 arr={90，30，18，15，10，5,3，2,1} sum=32
则返回2， 即最小的组合是两个数{30,2}

Java version:

public int solve(int[] a, int sum) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i : a) set.add(i);
        set.remove(1);
        
        int[] m = new int[sum+1];
        m[1] = 1;
        for (int i=2; i<=sum; i++) {
            m[i] = sum+1;
            for (int j : set) {
                if (j<=i) m[i] = Math.min(m[i], 1+m[i-j]);
            }
        }
        
        return m[sum];
    }


带输出的，不用分配那么多空间，只要记住parent index就行。

public int solve2(int[] a, int sum) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for (int i : a) if (i!=1) numbers.add(i);
        
        int[][] m = new int[sum+1][2];
        m[0] = new int[]{0, -1};
        m[1] = new int[]{1, 0};
        for (int i=2; i<=sum; i++) {
            m[i] = new int[]{sum+1, -1};
            for (int j : numbers) {
                if (j<=i && m[i][0] > 1+m[i-j][0]) {
                    m[i][0] = 1+m[i-j][0];
                    m[i][1] = i - j;
                }
            }
        }
        
        print(m, sum);
        return m[sum][0];
    }
    
    private void print(int[][] m, int sum) {
        for (int i=sum; i>0; ) {
            System.out.print(i - m[i][1] + " ");
            i = m[i][1];
        }
        System.out.println();
    }  

G的一道题 分析

http://www.mitbbs.com/article_t/JobHunting/31903469.html

grass的解法完全正确。

[2, 0, 1, 0] 如何得到 (1, 2, 3, 4)的某个排列？
推出第一个元素一定是(1, 2, 3, 4)中排名第三的数，也就是3
然后就有点递归的意味了。
[0, 1, 0] 如何得到(1, 2, 4)的某个排列？
推出第一个元素一定是(1, 2, 4)中排名第一的数，也就是1
[1, 0]如何得到（2，4)的某个排列？
推出第一个元素一定是(2, 4)中排名第二的数，也就是4
[0]如何得到(2)的某个排列？
这个是trival case了。实际上，Count array的最后一个元素永远是0，属于无效信息。

最后推出原数组是[3, 1, 4, 2]

Let Count be the count array, let Array be the original array.
用伪代码实现如下

Create ordered set S, and add 1, 2, ..., n to S

for (i = 0; i < n; i++)
{
    int index = Count[i] + 1;
    Array[i] = S.FindKth(index);
    
    S.RemoveKth(index); 
}

/*
如果RemoveKth同时返回值，如同stack的pop操作那样，还可以简化为
for (i = 0; i < n; i++)
{
    int index = Count[i] + 1;
    Array[i] = S.RemoveKth(index);
}
*/

问题的难点在于如何实现S，使得RemoveKth操作最多是lg(n)的
如果用数组，移动操作是O(n)的
如果用链表，定位操作是O(n)的
都不符合要求

怎么办呢？实际上lg(n)本身就是一个很大的提示，你可以联想到binary search, 
quick sort, binary tree, BST, heap, 分治，递归... 一定是套用其中某个或几个的
思想。

如果考虑BST，从第i个元素这个要求，你可以想到一道经典题：
如何在log(N)时间找到BST的第i个元素？

中序遍历的方法是O(N)的，怎么办？空间换时间!(类似思路有O(1)时间取得stack的最
小值)

方法就是每个节点附加左子树的元素个数，用递归或迭代。假定BST是平衡的，这样FindKth就是log(N)的。

但是这只是FindKth是log(N), RemoveKth呢？

grass巧妙的解决了这个问题，RemoveKth和FindKth的代码几乎一样，只是多了个删除
操作。但是，无须真正删除节点！树还是那棵一开始就创建好的平衡BST, 包含了自然
数1到n。只需要标记节点被删除就可以了，同时需要更新受影响的节点的左子树元素个
数。

代码如下，index从1开始
Node remove(Node node, int index)
{
    if (node.numOfLeftChildren >= index)
    {
        // left
        node.numOfLeftChildren--;
        return remove(node.left, index);
    }
    else if (node.numOfLeftChildren + 1 == index && !node.removed)
    {
        // current
        node.removed = true;
        return node;
    }
    else
    {
        // right
        return remove(node.right, index - node.numOfLeftChildren - (node.
removed ? 0 : 1));
    }
}

也可以用迭代，因为是尾递归。
此外上述代码最好加上判断node是否null, 可以处理index越界而查找失败的情况。

自此问题得到圆满解决。

总结：
1) Try a simple example first.
2) Use pseudo code first, then focus on the details.
3) 多尝试几种不同的数据结构，比较各自的优缺点
4) 化归到经典题(数学中化归的思想, 比如一道DP题能否化归到背包问题)
5) 空间换时间的策略
6) 对树的操作一定和递归密切相关
7) 标记节点状态而不破坏原始结构的思想(比如图的遍历)
8) 其它...

c++ cast Nice Post

http://stackoverflow.com/questions/103512/in-c-why-use-static-castintx-instead-of-intx

ASCII Pronunciation Rules for Programmers

http://www.codinghorror.com/blog/2008/06/ascii-pronunciation-rules-for-programmers.html

Common perl pronunciations:
- # arrow
= # fat arrow
= # spaceship operator 
~ # tilde
# # hash 
! # not , bang
@ # at, ampersand
$ # dollar
[] # square brackets
() # brackets
{} # curlies, curly brackets
` # back tick
"" # double quote
' # single quote
| # pipe
* # asterix, star
# left angle bracket, right angle bracket
In perl there are operators that have identical pronunciation, eg "==" and "eq" which differ by the context they give to. Both pronounced equals.
I rarely pronounce symbols them the same unless I'm actually dictating. Usually, when paring or discussing code, it's just a matter of describing the intent or effect. 
rj on June 12, 2008 2:44 AM

Good Lisp study post

Good Lisp study post

http://abhishek.geek.nz/docs/features-of-common-lisp/

[转载]Common Lisp中使用字符串动态调用函数

 original post:
http://blog.csdn.net/albert_lee/archive/2011/04/14/6322730.aspx

Common Lisp中使用字符串动态调用函数 收藏 应用场景：一个统计查询的后端程序，根据查询名称字符串分别调用相应的处理函数。 一般的处理方法，可以用一个全局的注册表，将名称字符串与函数名对应起来。但是，lisp程序员是很懒惰的，既然lisp环境本身已经提供了名称注册的机制，为什么还要自己写一套呢？事实上，Lisp环境本身的核心就在于 namespace 。 简单的说解决办法如下：

这是第一步的实现，但是没有进行异常处理，例如调用一个不存在的函数，系统会报异常。 待续。。

meetbsd 2010

http://meetbsd.org/category/meetbsd-2010