小编cod*_*ior的帖子

我最近遇到了这个问题:

Given two strings, return true if they are one edit away from each other,else return false.
An edit is insert/replace/delete a character. 
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false

解决此问题的一种方法是使用动态编程找到两个字符串之间的编辑距离,并检查它是否为1.这将花费O(N2)时间.有没有办法在线性时间内完成此操作,因为我们只检查它们是否为1编辑？

我在下面写的代码适用于大多数情况,但是对于像{"m",""}这样的情况却失败了

public boolean isOneEditDistance(String s1,String s2){
    if(s1==null || s2==null)
        return true;
    if(s1.equals(s2))
        return false;
    if (Math.abs(s1.length() - s2.length()) > 1)
        return false;
    int i = -1;
    int j = -1;
    while (true)
    {
        i++;
        j++;
        if (i == s1.length())
            return true;
        if (s1.charAt(i) == s2.charAt(j))
            continue;
        if (i != j)
            return false; …

我最近遇到了这个问题- 给定一个二进制字符串，检查是否可以将字符串分区/分割为0..n个部分，使得每个部分的幂为5。如果可以的话，返回最小分割数。

例如：

input = "101101" - returns 1, as the string can be split once to form "101" and "101",as 101= 5^1.
input = "1111101" - returns 0, as the string itself is 5^3.
input = "100"- returns -1, as it can't be split into power(s) of 5.

我想出了这个递归算法：

1. 检查字符串本身是否为5的幂。如果是，则返回0
2. 否则，逐个字符地遍历字符串，在每个点上检查到目前为止所看到的数字是否为5的幂。如果是，则将1分配给split count，然后从步骤1开始递归检查字符串的其余部分是否为5的幂。
3. 返回到目前为止看到的最小分割数。

我用Java实现了上述算法。我相信它可以正常运行，但这是一个简单的递归解决方案。可以使用动态编程来改善运行时间吗？

代码如下：

public int partition(String inp){
    if(inp==null || inp.length()==0)
        return 0;
    return partition(inp,inp.length(),0);
}
public int partition(String inp,int len,int index){
    if(len==index)
        return 0;
    if(isPowerOfFive(inp,index))
        return 0; …

我在下面写了下面的代码来找到第n个素数.这可以改善时间复杂度吗？

描述:

ArrayList arr存储计算的素数.一旦arr达到'n'大小,循环退出,我们检索ArrayList中的第n个元素.在计算素数之前添加数字2和3,并且从4开始的每个数字被检查为素数或不是素数.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter …

问题是根据字符串的长度对字符串数组进行排序.

例如

input = {"cat", "star", "act", "gid", "arts", "dog", "rats"}  
output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}

我使用插入排序(使用字符串的长度而不是字符串本身)来完成它.我的问题:有没有更好的方法呢？

我想到的另一种选择是 - 使用a TreeMap来存储每个字符串及其长度作为值(假设字符串在给定数组中是唯一的).然后根据其值对其进行排序.运行时间将是O(nlogn)空间复杂性O(n).你认为这是一种更好的方法吗？

编辑:很抱歉没有提到这个 - 我想这样做而不使用Arrays.sort()或自定义比较器.

插入排序的代码示例:

public static String[] insertionSort(String[] arr) {
    for(int i=1;i<arr.length;i++) {
        int j = 0;
        for(;j<i;j++) {
            if(arr[j].length() > arr[j+1].length()) {
                String temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

我是C#和Linq-to-Sql的新手.

我有一个这种形式的表'InstrumentTypes':

typeId(int)  | type(varchar)  |  subttype(varchar)

101               Keys           keyboard
102               Keys           accessories
103               Guitar         acoustic
104               Guitar         electric

我需要根据'type'搜索作为输入从表中获取所有'typeId',并且所有typeId都需要绑定到ASP Repeater.

到目前为止,我已经编写了以下代码:

// requestType contains the type from the search
var type = (from m in database.InstrumentTypes
            where m.type == requestType
            select m);
foreach(var typeId in type)
{
    //code
}

我无法弄清楚如何迭代查询结果,将它们存储在数据结构中并将它们绑定到Repeater.

以下代码将其绑定到Repeater:

Repeater1.DataSource= //name of data structure used to store the types goes here
Repeater1.DataBind();

有人可以帮帮我吗？

编辑:对于获得的每个typeID,我想访问另一个表'Instruments'并检索属于该typeId的所有Instruments.表'仪器'是这样的:

instrumentId     typeID    name     description
1000             101       yamaha   xyz

根据Arialdo的回答,我这样做:

var type = (from …

我正在尝试一种迭代方法来查找二叉搜索树的高度/深度.基本上,我尝试使用广度优先搜索来计算深度,方法是使用队列存储树节点并仅使用整数来保存树的当前深度.树中的每个节点都排队,并检查子节点.如果存在子节点,则增加深度变量.这是代码:

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    TreeNode node = root;
    int level = 0;
    boolean flag = false;

    nodeQ.add(node);
    while(!nodeQ.isEmpty()) {
        node = nodeQ.remove();
        flag = false;
        if(node.leftChild != null) {
            nodeQ.add(node.leftChild);
            flag = true;
        }

        if(node.rightChild != null) {
            nodeQ.add(node.rightChild);
            flag = true;
        }
        if(flag) level++;
    }
    System.out.println(level);

}

但是,该代码并不适用于所有情况.例如,对于以下树:

     10
   /    \
  4      18
   \    /  \
    5  17   19

它将深度显示为3,而不是2.我使用此页面中的想法使用额外的队列来存储当前深度的替代版本.我想避免使用额外的队列,所以我试图优化它.这是有效的代码,尽管使用了额外的Queue.

public void calcDepthIterativeQueue() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    Queue<Integer> lenQ …

我正在客户端上使用 Angular 开发应用程序。该应用程序有一组可以重新排序的幻灯片，如下所示：

<div ng-controller="SortableCTRL">
    <ul id="sortable">
        <li ng-repeat="item in sortableArray" ng-bind="item"></li>
    </ul>

    <button ng-click="add()">Add</button>
    <hr>
    <pre ng-bind="sortableArray|json"></pre>
</div>

js：

    $scope.sortableArray = [
        'One', 'Two', 'Three'
    ];

    $scope.add = function() {
        $scope.sortableArray.push('Item: '+$scope.sortableArray.length);

        sortableEle.refresh();
    }

    $scope.dragStart = function(e, ui) {
        ui.item.data('start', ui.item.index());
    }
    $scope.dragEnd = function(e, ui) {
        var start = ui.item.data('start'),
            end = ui.item.index();

        $scope.sortableArray.splice(end, 0, 
            $scope.sortableArray.splice(start, 1)[0]);

        $scope.$apply();
    }

    sortableEle = $('#sortable').sortable({
        start: $scope.dragStart,
        update: $scope.dragEnd
    });
}

http://jsfiddle.net/dj_straycat/Q5FWt/3/

该应用程序可由多人访问，因此，在添加/重新排序幻灯片时推送通知会很有用。在搜索时，我发现 socket.io 是正确的方法；但是我工作的公司还没有批准socket.io。有没有办法在不使用 socket.io 的情况下做到这一点？