头像

小呆呆

墨染空粉丝团




离线:1小时前


活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100000 + 10;

int n;
int a[N];
int main()
{
    cin >> n ;
    for(int i = 1;i <= n;i ++) cin >> a[i];

    sort(a + 1, a + n);

    int sum = 0, mid = (n + 1) / 2;
    for(int i = 1;i <= n;i ++)
    {
        sum += abs(a[i] - a[mid]);
    }

    cout << sum << endl;

    return 0;
}



题目描述

未知 整数数组 arrn 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ,其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如,arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3]

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first(arr[0])

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

样例

输入:encoded = [1,2,3], first = 1
输出:[1,0,2,1]
解释:若 arr = [1,0,2,1] ,那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
输入:encoded = [6,2,7,3], first = 4
输出:[4,2,0,7,4]

提示:

2 <= n <= 10^4
encoded.length == n - 1
0 <= encoded[i] <= 10^5
0 <= first <= 10^5


算法分析

  • 由于encoded[i] = arr[i] XOR arr[i + 1],当已知arr[i]时,可以计算出arr[i + 1] = encode[i] XOR arr[i],也就是当知道arr的前一个元素时,可以计算出后一个元素

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;
        for(int i = 1;i <= n;i ++)
        {
            arr[i] = encoded[i - 1] ^ arr[i - 1]; 
        }
        return arr;
    }
}



题目描述

给你一个整数数组 jobs ,其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化

返回分配方案中尽可能 最小最大工作时间

样例

输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3 。
输入:jobs = [1,2,4,7,8], k = 2
输出:11
解释:按下述方式分配工作:
1 号工人:1、2、8(工作时间 = 1 + 2 + 8 = 11)
2 号工人:4、7(工作时间 = 4 + 7 = 11)
最大工作时间是 11 。

提示:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10^7


算法分析

题目等价于将 n 份工作分成 k 个组,求每个组总时间的最小值。其中n的大小是最多是12,因此可以使用爆搜,把所有情况搜出来。搜索情况类似 小猫爬山

dfs(u, cnt, val):代表当前枚举到第u份工作,一共开了cnt个集合,开出的集合当前最大的总时间是val
枚举顺序:

  • u份工作往第0个集合中放

  • u份工作往第1个集合中放

  • u份工作往第k个集合中放

  • 新开一个集合,第u份工作往第k + 1个集合中放

时间复杂度

不好分析

Java 代码

class Solution {
    static int[] s = new int[13];
    static int[] jobs;
    static int ans;
    static int k;
    static void dfs(int u, int cnt, int val)
    {
        if(val >= ans) return ;//剪枝
        if(u == jobs.length)
        {
            ans = val;
            return ;
        }

        for(int i = 0;i < cnt;i ++)
        {
            s[i] += jobs[u];
            dfs(u + 1, cnt, Math.max(val, s[i]));
            s[i] -= jobs[u];
        }
        //新开一个集合
        if(cnt < k)
        {
            s[cnt] = jobs[u];
            dfs(u + 1, cnt + 1, Math.max(val, s[cnt]));
            s[cnt] = 0;
        }
    }
    public int minimumTimeRequired(int[] _jobs, int _k) {
        jobs = _jobs;
        k = _k;
        ans = 1000000000;
        dfs(0, 0, 0);
        return ans;
    }
}


新鲜事 原文

小呆呆
10天前
8天不见,66个信息,会一一回复的



小呆呆
1个月前

题目描述

您需要在二叉树的每一行中找到最大的值。

样例

输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

算法1

dfs

在搜索每个点的过程中,用h变量标记该点的深度,对于相同的深度选出最大值

  • 1、当到h高度时,不存在其他元素,则当前h层的最大值是root.val
  • 2、当到h高度时,存在最大值,则用root.val更新最大值

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static List<Integer> ans = new ArrayList<Integer>();
    static void dfs(TreeNode root, int h)
    {
        if(root == null) return ;
        if(h == ans.size())
        {
            ans.add(root.val);
        }else
        {
            int t = ans.get(h);
            ans.set(h, Math.max(root.val , t));
        }
        dfs(root.left, h + 1); dfs(root.right, h + 1);
    }
    public List<Integer> largestValues(TreeNode root) {
        ans.clear();
        dfs(root, 0);
        return ans;
    }
}

算法2

bfs

  • 通过bfs搜索出每一层的元素,在某一层中对所有元素比较出最大值即为当前层的最大值,同时将该层所有节点的左子树和右子树加入到队列中,以遍历下一层

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static List<Integer> ans = new ArrayList<Integer>();
    static void bfs(TreeNode root)
    {
        if(root == null) return ;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty())
        {
            int n = q.size();
            int maxv = q.peek().val;
            for(int i = 0;i < n;i ++)
            {
                TreeNode t = q.poll();
                maxv = Math.max(maxv, t.val);
                if(t.left != null) q.add(t.left);
                if(t.right != null) q.add(t.right);
            }
            ans.add(maxv);
        }
    } 
    public List<Integer> largestValues(TreeNode root) {
        ans.clear();
        bfs(root);
        return ans;
    }
}



小呆呆
1个月前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static List<Integer> ans = new ArrayList<Integer>();
    static void dfs(TreeNode root, int h)
    {
        if(root == null) return ;
        if(h == ans.size())
        {
            ans.add(root.val);
        }else
        {
            int t = ans.get(h);
            ans.set(h, Math.max(root.val , t));
        }
        dfs(root.left, h + 1); dfs(root.right, h + 1);
    }
    public List<Integer> largestValues(TreeNode root) {
        ans.clear();
        dfs(root, 0);
        return ans;
    }
}


活动打卡代码 LeetCode 514. 自由之路

小呆呆
1个月前
class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        ring = " " + ring;
        key = " " + key;
        int[][] f = new int[m + 10][n + 10];
        for(int i = 0;i <= m;i ++) Arrays.fill(f[i], 0x3f3f3f3f);
        f[0][1] = 0;
        for(int i = 1;i <= m;i ++)
            for(int j = 1;j <= n;j ++)
                if(key.charAt(i) == ring.charAt(j))
                {
                    for(int k = 1;k <= n;k ++)
                    {
                        int t = Math.abs(j - k);
                        f[i][j] = Math.min(f[i][j], f[i - 1][k] + Math.min(n - t, t) + 1);
                    }
                }
        int res = 0x3f3f3f3f;
        for(int i = 1;i <= n;i ++) res = Math.min(res, f[m][i]);

        return res;
    }
}



小呆呆
1个月前

题目描述

电子游戏“辐射4”中,任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘,并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring,表示刻在外环上的编码;给定另一个字符串 key,表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初,ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐,然后按下中心按钮,以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中:

  • 您可以将 ring 顺时针或逆时针旋转一个位置,计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐,并且这个字符必须等于字符 key[i]
  • 如果字符 key[i] 已经对齐到12:00方向,您需要按下中心按钮进行拼写,这也将算作 1 步。按完之后,您可以开始拼写 key 的下一个字符(下一阶段), 直至完成所有拼写。

样例

ring.jpg

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g',已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd',我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

提示:

  • ring 和 key 的字符串长度取值范围均为 1 至 100
  • 两个字符串中都只有小写字符,并且均可能存在重复字符;
  • 字符串 key 一定可以由字符串 ring 旋转拼出。

算法分析

03f25e332884894443734522aa11ab6.png

时间复杂度 $O(n^3)$

Java 代码

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        ring = " " + ring;
        key = " " + key;
        int[][] f = new int[m + 10][n + 10];
        for(int i = 0;i <= m;i ++) Arrays.fill(f[i], 0x3f3f3f3f);
        f[0][1] = 0;
        for(int i = 1;i <= m;i ++)
            for(int j = 1;j <= n;j ++)
                if(key.charAt(i) == ring.charAt(j))
                {
                    for(int k = 1;k <= n;k ++)
                    {
                        int t = Math.abs(j - k);
                        f[i][j] = Math.min(f[i][j], f[i - 1][k] + Math.min(n - t, t) + 1);
                    }
                }
        int res = 0x3f3f3f3f;
        for(int i = 1;i <= n;i ++) res = Math.min(res, f[m][i]);

        return res;
    }
}


活动打卡代码 LeetCode 518. 零钱兑换 II

小呆呆
2个月前
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] f = new int[amount + 10];
        f[0] = 1;
        for(int i = 0;i < n;i ++)
        {
            for(int j = coins[i];j <= amount;j ++)
                f[j] += f[j - coins[i]];
        }
        return f[amount];
    }
}



小呆呆
2个月前

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

样例

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
输入: amount = 10, coins = [10] 
输出: 1

注意:

你可以假设:

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数

算法分析

状态表示

f[i, j]表示从前i个物品选,且总体积恰好是j的总方案数

状态计算

f[i, j] = f[i - 1, j] + f[i - 1, j - v] + ... + f[i - 1, j - sv]
f[i, j - v] =           f[i - 1, j - v] + ... + f[i - 1, j - sv]

因此 f[i, j] = f[i - 1, j] + f[i, j - v]

初始化:f[0][0] = 1
结果:f[n][m]

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] f = new int[amount + 10];
        f[0] = 1;
        for(int i = 0;i < n;i ++)
        {
            for(int j = coins[i];j <= amount;j ++)
                f[j] += f[j - coins[i]];
        }
        return f[amount];
    }
}