打家劫舍（4）

题目

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

题目分析

这里的核心是找到最少能偷的K间房
设x是预设的偷窃能力
f(x)是在x的偷窃能力下，能够偷的房屋
随着x的增大，f(x)总是能保持增加或者相等
我们只需要找到这个搜索能力值，并且满足f(x)正好小于k的情况

测试代码

测试代码在上

测试结果：
build avl tree cost time: 52999 ms
build binary tree cost time: 41526 ms
build FuzzyLookUpList cost time: 860 ms
avl queryTime:40 ms
binary queryTime:45231 ms
FuzzyLookUpList queryTime:9 ms
SimpleMap insertTime:51 ms
SimpleMap queryTime:7 ms

结论：多用数组多用数组

package com.liangyumingblog;

public class LinkList
{
    private class Node
    {
        int value;

        Node next;

        public Node(int value, Node next)
        {
            this.value = value;
            this.next = next;
        }
    }

    private Node head = new Node(-1, null);

    private int size = 0;

    public void add(int value)
    {
        size++;
        Node current = head;
        while (current.next != null)
        {
            current = current.next;
        }
        current.next = new Node(value, null);
    }

    public Node getLast()
    {
        Node current = head;
        while (current.next != null)
        {
            current = current.next;
        }
        return current;
    }

    public Node removeLast()
    {
        Node current = head;
        while (current.next.next != null)
        {
            current = current.next;
        }
        Node tmp = current.next;
        current.next = null;
        tmp.next = null;
        return tmp;
    }

    public void reverse()
    {
        int length = 0;
        while (length != size)
        {
            insert(length, removeLast());
            length++;
        }
    }

    public boolean insert(int index, Node node)
    {
        if (index > size)
        {
            return false;
        }
        int now = 0;
        Node current = head;
        while (now != index)
        {
            ++now;
            current = current.next;
        }
        Node tmp = current.next;
        current.next = node;
        node.next = tmp;
        return true;
    }

    @Override
    public String toString()
    {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("[");
        Node current = head;
        while (current.next != null)
        {
            if (head != current)
            {
                stringBuffer.append(current.value);
                stringBuffer.append(", ");
            }
            current = current.next;
        }
        stringBuffer.append(current.value);
        stringBuffer.append("]");
        return stringBuffer.toString();
    }
}

(totalrow+singlePageSize-1 )/singlePageSize

为什么说是个小trick呢

直观上我们做分页算法应该是这样的

return totalSize%singlePageSize!=0?totalSize/singlePageSize+1:totalSize/singlePageSize;

但是呢，最开始提到的算法，如果total/single有余数，由于int的直接截取的性质，所以totalrow/singlePageSize是向下取整了，但是这个余数加上（singlePageSize-1）再去除singlePagesize就刚好能够+1

否则因为（singePageSize-1）/SinglePageSize向下取整的性质，就变成了+0。所以说这里这个小Trick我还真没想到过，很巧妙

第一种，简洁算法

根据矩阵运算中的可得

package com.liangyumingblog;

public class RollUpString
{
    private String string;

    public RollUpString(String s)
    {
        this.string = s;
    }

    public String rollup(int n)
    {
        StringBuilder s1 = new StringBuilder(string.substring(0, n));
        StringBuilder s2 = new StringBuilder(string.substring(n + 1));
        return s1.reverse().append(s2.reverse().toString()).reverse().toString();
    }
}

继续阅读“字符串左移N位”