GALA-Lin6/17/25Less than 1 minute

Introduction

name: GALA-Lin
email:
personal website: https://gala-lin.github.io/
Code repositories：https://github.com/GALA-Lin/
interests: programming, open source, sharing.

GALA-Lin6/14/25Less than 1 minute

Homework5

图像灰度压缩

⼀幅4*4的图像, 灰度值序列如下.请根据课堂上所讲代码,写出构造解的S数组、l数组和b数组, 追踪解的S数组. 需要体现做题过程,如:每⼀轮i的循环写出内部j循环的前两次和最后两次, 内部循环少于等于四次的需要全部j的计算过程

GALA-LinOriginal5/28/25About 17 min

Homework4

一、01 backpack problem

Given:

Value array v = {8, 10, 6, 3, 7, 2}
Weight array w = {4, 6, 2, 2, 5, 1}
Knapsack capacity c = 12

Solution analysis

1. Two-dimensional DP

m[i,j] : The largest value in the set of values with volume <=j from the first i items

GALA-LinOriginal5/14/25About 8 min

Homework3

第一题

在构建 c 数组时，不再维护额外的 b 数组来记录方向。在需要回溯寻找具体的最长公共子序列时，直接通过比较 c[i] [j]、c[i-1] [j] 和 c[i] [j-1] 的值来判断当前字符是否属于最长公共子序列，以及应该向哪个方向回溯。

伪代码

FUNCTION LCS(const string s1, const string s2):
    m = s1.size() // 获取字符串 s1 的长度
    n = s2.size() // 获取字符串 s2 的长度
    dp[m+1][n+1] // 初始化动态规划表
    for i from 1 to m:
        for j from 1 to n: 
            if s1[i-1] == s2[j-1]: // 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1 // 当前位置的 LCS 长度等于左上方的值加 1，表示找到了一个公共子序列字符
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 // 如果当前字符不同，当前位置的 LCS 长度取上方和左方的最大值，表示不考虑当前字符
        end for
    end for

    return dp[m][n] // 返回最终的最长公共子序列长度，位于动态规划表的右下角
END FUNCTION

GALA-LinOriginal5/7/25About 6 min

Homework2

1. binary search

FUNCTION binary_search1(arr[], low, high, x):
    WHILE low <= high:  # 持续搜索直到搜索区间无效
        mid = (low + high) >> 1  # 位运算计算中间索引 (等价于/2但更快)
        
        IF arr[mid] == x:        # 找到目标元素
            PRINT "Found at index " + mid
            RETURE
        ELSE IF arr[mid] < x:    # 目标在右半区
            low = mid + 1        # 调整左边界
        ELSE:                    # 目标在左半区
            high = mid - 1       # 调整右边界
    END WHILE
    PRINT "Element not found"    # 搜索空间耗尽未找到
RETURE

# 时间复杂度 O(log n)，空间复杂度 O(1)