python3 解法, 执行用时: 137 ms, 内存消耗: 16.4 MB, 提交时间: 2024-08-11 23:35:29

class Solution:
    def maxUncrossedLines(self, s: List[int], t: List[int]) -> int:
        f = [0] * (len(t) + 1)
        for x in s:
            pre = 0  # f[0]
            for j, y in enumerate(t):
                tmp = f[j + 1]
                f[j + 1] = pre + 1 if x == y else max(f[j + 1], f[j])
                pre = tmp
        return f[-1]

golang 解法, 执行用时: 2 ms, 内存消耗: 2.3 MB, 提交时间: 2024-08-11 23:35:12

func maxUncrossedLines1(s, t []int) int {
    n, m := len(s), len(t)
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    for i, x := range s {
        for j, y := range t {
            if x == y {
                f[i+1][j+1] = f[i][j] + 1
            } else {
                f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
            }
        }
    }
    return f[n][m]
}


func maxUncrossedLines(s, t []int) int {
    m := len(t)
    f := make([]int, m+1)
    for _, x := range s {
        pre := 0 // f[0]
        for j, y := range t {
            if x == y {
                f[j+1], pre = pre+1, f[j+1]
            } else {
                pre = f[j+1]
                f[j+1] = max(f[j+1], f[j])
            }
        }
    }
    return f[m]
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 15.2 MB, 提交时间: 2024-08-11 23:34:36

class Solution {
public:
    int maxUncrossedLines(vector<int>& s, vector<int>& t) {
        int n = s.size(), m = t.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 :
                                  max(f[i][j + 1], f[i + 1][j]);
            }
        }
        return f[n][m];
    }

    int maxUncrossedLines2(vector<int>& s, vector<int>& t) {
        int m = t.size();
        vector<int> f(m + 1);
        for (int x : s) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = x == t[j] ? pre + 1 : max(f[j + 1], f[j]);
                pre = tmp;
            }
        }
        return f[m];
    }
};

java 解法, 执行用时: 4 ms, 内存消耗: 40.6 MB, 提交时间: 2024-08-11 23:33:59

class Solution {
    public int maxUncrossedLines1(int[] s, int[] t) {
        int n = s.length;
        int m = t.length;
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 :
                                  Math.max(f[i][j + 1], f[i + 1][j]);
            }
        }
        return f[n][m];
    }

    public int maxUncrossedLines(int[] s, int[] t) {
        int m = t.length;
        int[] f = new int[m + 1];
        for (int x : s) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = x == t[j] ? pre + 1 : Math.max(f[j + 1], f[j]);
                pre = tmp;
            }
        }
        return f[m];
    }
}

python3 解法, 执行用时: 168 ms, 内存消耗: 15.4 MB, 提交时间: 2022-08-10 16:34:23

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i, num1 in enumerate(nums1):
            for j, num2 in enumerate(nums2):
                if num1 == num2:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        
        return dp[m][n]