侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 101 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(25) - 动态规划:最长子序列

惊羽
2022-03-24 / 0 评论 / 0 点赞 / 445 阅读 / 222 字
温馨提示:
本文为原创作品,感谢您喜欢~

问题

求解两个数组的最长子序列
例如 :

int[] x = {1,2,3,4,4,5}
int[] y = {1,4,5}

最长子串为 : 1,4,5

code

public class _05LCSTest {

    @Test
    public void LCS_test() {
        String[] s1 = {"1","3","4","5"};
        String[] s2 = {"0","1","3","5"};
        printLCS(s1,s2);
    }

    public void printLCS(String[] str1, String[] str2) {

        int[][] clen = new int[str1.length +1][str2.length+1];

        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                 if(str1[i-1].equals(str2[j-1])){
                     clen[i][j] = clen[i-1][j-1] + 1;
                }else {
                    clen[i][j] =  Math.max(clen[i][j-1],clen[i-1][j]);
                }
            }
        }
        int i = str1.length;
        int j = str2.length;
        StringBuilder sb = new StringBuilder();
        while(i>0 && j > 0){
            if(str1[i-1].equals(str2[j-1])){
                sb.append(str1[i-1]);
                i--;
                j--;
            }else{
                if(clen[i-1][j] > clen[i][j-1] ){
                    i--;
                }else if(clen[i-1][j] < clen[i][j-1] ){
                    j--;
                }else  if(clen[i-1][j] == clen[i][j-1] ){
                    j--;
                }
            }
        }
        System.out.println(sb.reverse().toString());
    }
}

解析

8f21b2d1830e9cb545595dd03e82c31.png

0
广告 广告

评论区