小编nti*_*tin的帖子

在我的业余时间里,我一直在为Interview Street挑战改变比赛现在已经有一个多星期了,而且此时只是转动我的车轮,所以我希望有人可以给我一个正确方向的指针或暗示.

挑战的基础是采用两位字符串A和B并运行一些操作两位字符串的查询.

设A和B为两个N位数.您将获得A和B的初始值,您应该编写一个处理三种查询的程序:

• set_a idx x:将A [idx]设置为x,其中0 <= idx <N,其中A [idx]是A的idx'最低有效位.
• set_b idx x:将B [idx]设置为x,其中0 <= idx <N.
• get_c idx:打印C [idx],其中C = A + B,0 <= idx

其中位数的长度为1到100,000,并且程序可以具有set_a,set_b或get_c的任意组合的1到500,000个查询.

为了最小化循环,我使用C作为运行总计.当A或B中的位改变时,也从C加上或减去改变的位.当存在进位时,进一步最小化加法和减法时的循环从改变的位到左手.

private static void add(final boolean[] the_array, final int the_index)
{
    for(int iter = the_array.length - the_index - 1; iter >= 0; iter--)
    {
        if(the_array[iter])
        {
            the_array[iter] = false;
        }
        else if(!the_array[iter])
        {
            the_array[iter] = true;
            return ;
        }
    }
}

private static void subtract(final boolean[] the_array, final int the_index)
{ …

我一直trie在练习数据结构（与课程工作无关）。此类用于存储字符串的子字符串。对于长度的串n有n(n+1)/2总的子串。特别地，这种trie保留方式的实现保留了自然顺序，并且比TreeMap或TreeSet对随机字符串更有效。同样，存储单个字符而不是整个字符串可以节省内存。

我认为对于存储子字符串而言，后缀数组可能是更好的方法，但我想确保在开始新项目之前已针对速度合理地优化了这个trie类。

class Trie
{
    final Trie my_parent;
    final Trie[] my_children;
    final char my_value;

    public Trie(final Trie the_parent, final char the_value)
    {
        my_parent = the_parent;
        my_value = the_value;
        my_children = new Trie[26];
    }

    public int insertIterative(final char[] the_text)
    {
        int number = 0;
        Trie parent = this;

        for(int ator = 0; ator < the_text.length; ator++)
        {
            final int key = the_text[ator] - 97;
            Trie child = parent.my_children[key];

            if(child …