编程之美 数字中的技巧3

· 1120 words · 3 minute read
2017年9月

计算字符串的相似度

题目

对于abcdefg和abcdef两个字符串来说，我们可以通过增加/减少一个g的方式来达到目的。上面的两种方案，都仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。相似度等于“距离+1”的倒数

方法

对于第一个字符相同的两个字符串，只要计算除第一个字符的后面的字符串。对于第一个字符不相同的两个字符串，需要，会有6种情况：

  1. 删除A的第一个字符，计算
  2. 删除B的第一个字符，计算
  3. 修改A的第一个字符，计算
  4. 修改B的第一个字符，计算
  5. 增加B的第一个字符到A的第一个字符之前，计算
  6. 增加A的第一个字符到B的第一个字符之前，计算

重点,我们并不在乎两个字符串变得相等后的字符串是怎么样的，所以可以将上面的6个操作合并为：

  1. 一步操作之后，将A[2…lenA]和B[1…lenB]变成相同的字符串
  2. 一步操作之后，将A[1…lenA]和B[2…lenB]变成相同的字符串
  3. 一步操作之后，将A[2…lenA]和B[2…lenB]变成相同的字符串

即简单递归即可

int cal(String sA, int beginA, int endA, String sB, int beginB, int endB){
    if(beginA > endA){
        if(beginB > endB){
            return 0;
        }else{
            return endB-beginB+1;
        }
    }

    if(beginB > endB){
        if(beginA > endA){
            return 0;
        }else{
            return endA-beginA+1;
        }
    }

    if(sA.charAt(beginA) == sB.charAt(beginB)){
        return cal(sA,beginA+1,endA,sB,beginB+1,endB);
    }else{
        int t1 = cal(sA,beginA+1,endA,sB,beginB,endB);
        int t2 = cal(sA,beginA,endA,sB,beginB+1,endB);
        int t3 = cal(sA,beginA+1,endA,sB,beginB+1,endB);
        return Math.min(t1,t2,t3) + 1;
    }
}

最短摘要的生成

题目

找到在摘要中，包含所有关键字的最短距离

例：

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

在摘要中，包含所有关键字的最短距离为2.

方法

第一次扫描，包含所有关键字

w0,w1,w2,w3,**q0**,w4,w5,**q1**,w6,w7,w8,**q0**,w9,**q1**

0                          7

第二次扫描，包含所有关键字

w0,w1,w2,w3,**q0**,w4,w5,**q1**,w6,w7,w8,**q0**,w9,**q1**

                    5                            12

在while循环中，直到end >= N才跳出. isAllExisted()表示包含所有关键字

int targetlen = N + 1； 设置最短距离长度
int begin = 0;
int end = 0;
int len = N; 数组长度为N
int resBegin = 0; 最短摘要开始地址
int resEnd = 0; 最短摘要结束地址

while(true){
    while(!isAllExisted() && end < len){
        end++;
    }
    while(isAllExisted()){
        if(end - begin < targetlen){
            tagetlen = end - begin;
            resBegin = begin;
            resEnd = end;
        }
        begin++;
    }
    if(end >= N){
        break;
    }
}

二叉树节点间的最大距离问题

题目

求二叉树节点间的最大距离。

方法

在以h为头的树上，最大距离只可能来自以下三种情况

  1. h的左子树上的最大距离
  2. h的右子树上的最大距离
  3. h左子树上离h.left最远的距离+1+h右子树上离h.right最远的距离

后序遍历

public int maxDistance(Node head){
    int[] record = new int[1];
    return postOrder(head,record);
}

public int postOrder(Node head, int[] record){
    if(head == null){
        record[0] = 0;
        return 0;
    }
    int lmax = postOrder(head.left,record);
    int maxleftheight = record[0];
    int rmax = postOrder(head.right,record);
    int maxrightheight = record[0];
    int currentDis = maxleftheight + maxrightheight + 1;
    record[0] = Math.max(maxleftheight,maxrightheight) + 1;
    return Math.max(Math.max(lmax,rmax),currentDis);
}

写一个函数，打印二叉树中某层级的节点(从左往右)

题目

打印二叉树中某层级的节点(从左往右)，其中根节点为第0层，函数为int printNodeAtLevel(Node root, int level)，成功返回1，失败则返回0.

方法

递归。假设要求访问二叉树有第k层的节点，k=2,即要求访问原二叉树中第二层的节点（根节点为第0层），可把它转换成求以第一层为根节点的两棵子树中第k-1=1层的节点。

int printAtLevel(Node root, int level){
    if(!root || level < 0){
        return 0;
    }
    if(level == 0){
        System.out.print(root.val+" ");
        return 1;
    }
    return printAtLevel(root.left,level-1)+printAtLevel(root.right,level-1);
}
Share