[数据结构与算法]算法题-java

dp背包问题

问题：动态规划的优化
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
https://markrepo.github.io/algorithm/2021/01/01/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/

static int fun(int W, int N, int wt[], int val[]) {<!-- -->
        int[][] dp = new int[N + 1][W + 1];//dp[i][w]表示剩余容量为w时，装入前i个物体。
        for (int i = 1; i <= N; ++i) {<!-- -->
            for (int w = 1; w <= W; ++w) {<!-- -->
                if (w - wt[i - 1] < 0)
                    dp[i][w] = dp[i - 1][w];//当前背包的容量装不下第i个。
                else {<!-- -->
                    dp[i][w] = max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
                }                           //装入或者不装入背包，择优。
            }
        }
        for (int i = 1; i <= N; i++) {<!-- -->
            for (int j = 1; j <=W; j++) {<!-- -->
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
        return dp[N][W];
    }

二叉树所有路径的拼接

二叉树的每个节点为0-9的一个数字，根到叶子的一条路径拼成一个数，求所有路径形成的数字和

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int value;
};
 
int dfs(TreeNode* root, int sum)
{
    if (root == nullptr)
    {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr)
    {
        return sum * 10 + root->value;
    }
    return dfs(root->left, sum * 10 + root->value)
         + dfs(root->right, sum * 10 + root->value);
}
 
int SumOfPath(TreeNode* root)
{
    return dfs(root, 0);
}

https://blog.csdn.net/wwj_ff/article/details/46359285

合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n ）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while(len1 >= 0 && len2 >= 0) {
            // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }
}

作者：guanpengchn
链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/hua-jie-suan-fa-88-he-bing-liang-ge-you-xu-shu-zu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。