前端刷华为机考第16题购物车

作者: 小遁哥 | 来源:发表于2023-08-26 16:21 被阅读0次

前端刷题网站
前端刷题网站
心理学备考第16天:学习小技巧:
50天木木提醒
IOS面试 (华为) --- 算法编辑器介绍
八年级的学生雅思考了6.5分做对了什么？
前端刷题（不停更新记录）
刷题刷题
2018法考改革将实行2+1考试模式
遇到的问题

先看一下正确且符合时间和内存要求的答案，我模拟了牛客网的输入

    let count = 0,
      totalMoney = 0,
      firstList = [],
      secondObj = {};
    `14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0`
      .trim()
      .split("\n")
      .forEach((item, i) => {
        if (i == 0) {
          [totalMoney, count] = item.split(" ");
        } else {
          const dataList = item.split(" ");
          if (dataList[2] == 0) {
            firstList.push({
              key: i,
              price: +dataList[0],
              weight: +dataList[1] * +dataList[0],
            });
          } else {
            if (!secondObj[dataList[2]]) {
              secondObj[dataList[2]] = [];
            }

            secondObj[dataList[2]].push({
              price: +dataList[0],
              weight: +dataList[1] * +dataList[0],
            });
          }
        }
      });

        function able() {
      let goodTwoList = [];
      for (let i = 0; i < firstList.length; i++) {
        const goods = firstList[i];
        goodTwoList[i] = [];
        goodTwoList[i].push(goods);

        let childList = [...(secondObj[goods.key] || [])];
        if (childList.length == 2) {
          childList.push({
            price: childList[0].price + childList[1].price,
            weight: childList[0].weight + childList[1].weight,
          });
        }
        childList.forEach((item) => {
          const price = goods.price + item.price;
          if (price <= totalMoney) {
            goodTwoList[i].push({
              price,
              weight: goods.weight + item.weight,
            });
          }
        });
      }

      const weightTwoList = [];
      for (let i = 0; i < 2; i++) {
        weightTwoList[i] = [];
        for (let j = 0; j <= totalMoney; j++) {
          weightTwoList[i][j] = 0;
        }
      }

      for (let i = 0; i < goodTwoList.length; i++) {
        let j = totalMoney;
        while (j > 10) {
          weightTwoList[1][j] = weightTwoList[0][j];
          goodTwoList[i].forEach((item) => {
            if (j >= item.price) {
              weightTwoList[1][j] = Math.max(
                weightTwoList[1][j],
                weightTwoList[0][j - item.price] + item.weight
              );
            }
          });
          j -= 10;
        }

        [weightTwoList[1], weightTwoList[0]] = [
          weightTwoList[0],
          weightTwoList[1],
        ];
      }

      console.log(weightTwoList[0][totalMoney]);
    }
    able();

首先每件物品只能购买一次；购买主件时可以不买附件的，可以买一个也可以买两个。

400 5 1是800 2 0的附件，在这里很容易直观的看出来，但在收集数据的时候要注意索引，因为这条测试用例就算主附件关系搞错了答案也是对的，最佳选择是购买400 3 0和500 2 0

为了便于展示在简化下

这时候j-=10需要改成j--，j>10要改为j>0

用firstList存储主件，secondObj存储附件，weight一开始就算好，分别分：

 [
  {
    "key": 1,
    "price": 8,
    "weight": 16
  },
  {
    "key": 4,
    "price": 4,
    "weight": 12
  },
  {
    "key": 5,
    "price": 5,
    "weight": 10
  }
]

{
  "1": [
    {
      "price": 4,
      "weight": 20
    },
    {
      "price": 3,
      "weight": 15
    }
  ]
}

因为当主件有附件时产生的结果就多于一个，所以用二维数组goodTwoList存储

if (childList.length == 2) {先把两个附件一起的情况算好，这里childList.forEach就可以统一处理，goodTwoList内容如下

[
  [
    {
      "key": 1,
      "price": 8,
      "weight": 16
    }
  ],
  [
    {
      "key": 4,
      "price": 4,
      "weight": 12
    }
  ],
  [
    {
      "key": 5,
      "price": 5,
      "weight": 10
    }
  ]
]

虽然8 2 0有两个附件，但他们组合的情况已大于总钱数，所以没有出现

初始化 weightTwoList

weightTwoList[1][j] = weightTwoList[0][j]; 这个是同步上一次的值，也代表了没有当前物品的情况。

weightTwoList[0][j - item.price] + item.weight 表示买下当前物品后，再用剩余的钱还能买到物品的期望值，买不到就是 0，因为 weightTwoList[0]的值全部初始化为 0

当执行到weightTwoList[1][j] = Math.max 就是对比最优解，先看一下 weightTwoList[1]每次存储的值:

[0, 0, 0, 0, 0, 0, 0, 0, 16, 16, 16]
[0, 0, 0, 0, 12, 12, 12, 12, 16, 16, 16]
[0, 0, 0, 0, 12, 12, 12, 12, 16, 22, 22]

也就是w[i][j] 中j就是预算为j买i 件物品的最优解，因此weightTwoList长度为 2 就可以了

因为执行了互换操作，所以最优解是weightTwoList[0][totalMoney]

想起来之间遇到过类似的题算法=>魔法硬币,j可以先从totalMoney开始，每次减去 10，虽然减少不了二维数组的长度，但是到了最后一个商品时，结果可以优先产出。

时间超出了要求

我想到了递归，

   let i = 0,
      count = 30,
      money = 18000,
      minPrice = 0;
    const firstObj = {
      1: {
        price: 100,
        weight: 3,
      },
      2: {
        price: 400,
        weight: 5,
      },
      5: {
        price: 500,
        weight: 2,
      },
      6: {
        price: 800,
        weight: 2,
      },
      7: {
        price: 1400,
        weight: 5,
      },
      8: {
        price: 300,
        weight: 5,
      },
      9: {
        price: 1400,
        weight: 3,
      },
      10: {
        price: 500,
        weight: 2,
      },
      11: {
        price: 1800,
        weight: 4,
      },
      14: {
        price: 1400,
        weight: 3,
      },
      15: {
        price: 500,
        weight: 2,
      },
      16: {
        price: 800,
        weight: 2,
      },
      17: {
        price: 1400,
        weight: 5,
      },
      18: {
        price: 300,
        weight: 4,
      },
      19: {
        price: 1400,
        weight: 3,
      },
      20: {
        price: 500,
        weight: 2,
      },
      21: {
        price: 1800,
        weight: 2,
      },
      25: {
        price: 1400,
        weight: 3,
      },
      25: {
        price: 500,
        weight: 2,
      },
      26: {
        price: 800,
        weight: 5,
      },
      27: {
        price: 1400,
        weight: 5,
      },
      28: {
        price: 300,
        weight: 5,
      },
    };
    const secondObj = {
      1: [
        {
          price: 1300,
          weight: 5,
        },
      ],
      2: [
        {
          price: 1400,
          weight: 2,
        },
      ],
      9: [
        {
          price: 400,
          weight: 5,
        },
        {
          price: 1300,
          weight: 5,
        },
      ],
      20: [
        {
          price: 400,
          weight: 5,
        },
        {
          price: 1300,
          weight: 5,
        },
      ],
    };
    function able() {
      const firstKeyList = Object.keys(firstObj);
      let maxWeight = 0;

      getCountWeight(firstObj[firstKeyList[0]], 0, 0, 0);
      console.log(maxWeight);

      function getCountWeight(infos, currentMoney, currentWeight, deep) {
        for (let i = 0; i < 2; i++) {
          currentMoney += infos.price * i;
          currentWeight += infos.price * i * infos.weight;

          let childList = secondObj[firstKeyList[deep]];
          let dataList = [{ currentMoney, currentWeight }];

          if (childList && i > 0) {
            if (childList.length > 0) {
              dataList.push({
                currentMoney: currentMoney + childList[0].price,
                currentWeight:
                  currentWeight + childList[0].price * childList[0].weight,
              });
            }

            if (childList.length > 1) {
              dataList.push({
                currentMoney: currentMoney + childList[1].price,
                currentWeight:
                  currentWeight + childList[1].price * childList[1].weight,
              });
              dataList.push({
                currentMoney:
                  currentMoney + childList[1].price + childList[0].price,
                currentWeight:
                  currentWeight +
                  childList[1].price * childList[1].weight +
                  childList[0].price * childList[0].weight,
              });
            }
          }

          dataList.forEach((item) => {
            if (item.currentMoney <= money) {
              if (deep < firstKeyList.length - 1) {
                getCountWeight(
                  firstObj[firstKeyList[deep + 1]],
                  item.currentMoney,
                  item.currentWeight,
                  deep + 1
                );
              } else if (item.currentWeight > maxWeight) {
                maxWeight = item.currentWeight;
              }
            }
          });
        }
      }
    }
    able();

答案是正确的，但是当数据较大时，它超时了。

把主件存在firstObj里，附件存在secondObj

getCountWeight的形参分别是,infos：当前主件，currentMoney:现在用了多少钱，currentWeight:现在的期望,deep:处理到哪个主件

dataList先存下不买的情况，因为主间可能有附件，再依次处理，这里的for (let i = 0; i < 2; i++) {是多余的

Java 算法

我看了下其它答案，其中有一个 Java 算法，我把它转换为了 JS

let i = 0,
      m = 5,
      N = 10,
      minPrice = 0;

    const goods = [
      {
        v: 8,
        p: 1600,
        main: true,
        a1: 1,
        a2: 2,
      },
      {
        v: 4,
        p: 2000,
        main: false,
        a1: -1,
        a2: -1,
      },
      {
        v: 3,
        p: 1500,
        main: false,
        a1: -1,
        a2: -1,
      },
      {
        v: 4,
        p: 1200,
        main: true,
        a1: -1,
        a2: -1,
      },
      {
        v: 5,
        p: 1000,
        main: true,
        a1: -1,
        a2: -1,
      },
    ];

    function able() {
      let dp = [];
      for (let i = 0; i <= m; i++) {
        dp[i] = [];
        for (let j = 0; j <= N; j++) {
          dp[i][j] = 0;
        }
      }

      for (let i = 1; i <= m; i++) {
        for (let j = 0; j <= N; j++) {
          //情况一：什么都不选
          dp[i][j] = dp[i - 1][j];
          if (!goods[i - 1].main) {
            //附件，直接跳过
            continue;
          }
          //情况二：只选择主件
          if (j >= goods[i - 1].v) {
            dp[i][j] = Math.max(
              dp[i][j],
              dp[i - 1][j - goods[i - 1].v] + goods[i - 1].p
            );
          }
          //情况三：只选择主件和第一个附件
          if (
            goods[i - 1].a1 != -1 &&
            j >= goods[i - 1].v + goods[goods[i - 1].a1].v
          ) {
            dp[i][j] = Math.max(
              dp[i][j],
              dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a1].v] +
                goods[i - 1].p +
                goods[goods[i - 1].a1].p
            );
          }
          //情况四：只选择主件和第二个附件
          if (
            goods[i - 1].a2 != -1 &&
            j >= goods[i - 1].v + goods[goods[i - 1].a2].v
          ) {
            dp[i][j] = Math.max(
              dp[i][j],
              dp[i - 1][j - goods[i - 1].v - goods[goods[i - 1].a2].v] +
                goods[i - 1].p +
                goods[goods[i - 1].a2].p
            );
          }
          //情况五：选择主件和两个附件
          if (
            goods[i - 1].a1 != -1 &&
            goods[i - 1].a2 != -1 &&
            j >=
              goods[i - 1].v +
                goods[goods[i - 1].a1].v +
                goods[goods[i - 1].a2].v
          ) {
            dp[i][j] = Math.max(
              dp[i][j],
              dp[i - 1][
                j -
                  goods[i - 1].v -
                  goods[goods[i - 1].a1].v -
                  goods[goods[i - 1].a2].v
              ] +
                goods[i - 1].p +
                goods[goods[i - 1].a1].p +
                goods[goods[i - 1].a2].p
            );
          }
        }
      }
      console.log(dp);
    }
    able();

这里为了更直观的的看结果，我简化了输入，dp的存储是这样的:

[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 0, 0, 0, 0, 1600, 1600, 1600]
[0, 0, 0, 0, 1200, 1200, 1200, 1200, 1600, 1600, 1600]
[0, 0, 0, 0, 1200, 1200, 1200, 1200, 1600, 2200, 2200]

一维数组代表货物。二维数组的下标代表花的钱，对应的值代表最大的期望，所以dp[m][N]就是最大的期望，这很好的控制空间，最后两个双重循环搞定，时间也没问题，这比递归的穷举好多了。

首先这个变量命名增大了阅读难度。

算法选择先初始化goods来解决先遇到附件的问题，但是主附件放到一起可以很明显的看到，dp[0]、dp[1]、dp[2]完全是重复的。

算法选择进入双重循环的时候再去处里主附件产生的不同的情况，其实增加了重复逻辑的抒写,而且有的附件加主件可能超过总钱数，没必要处理

j 没必要每次加一，因为商品的价格都是 10 的倍数

dp数组只需要两个就够了,可以看到dp[4]存储的每个数据就是当前与预算对应的最佳期望值

存储空间超出限制的算法

正所谓时间不够空间来补，看来上面的解法，我有了灵感

  let count = 0,
      totalMoney = 0,
      firstList = [],
      secondObj = {};
    `14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0`
      .trim()
      .split("\n")
      .forEach((item, i) => {
        if (i == 0) {
          [totalMoney, count] = item.split(" ");
        } else {
          const dataList = item.split(" ");
          if (dataList[2] == 0) {
            firstList.push({
              key: i,
              price: +dataList[0],
              weight: +dataList[1] * +dataList[0],
            });
          } else {
            if (!secondObj[dataList[2]]) {
              secondObj[dataList[2]] = [];
            }

            secondObj[dataList[2]].push({
              price: +dataList[0],
              weight: +dataList[1] * +dataList[0],
            });
          }
        }
      });

    function able() {
      let goodTwoList = [];
      for (let i = 0; i < firstList.length; i++) {
        const goods = firstList[i];
        goodTwoList[i] = [];
        goodTwoList[i].push(goods);

        let childList = secondObj[goods.key] || [];
        if (childList.length == 2) {
          childList.push({
            price: childList[0].price + childList[1].price,
            weight: childList[0].weight + childList[1].weight,
          });
        }
        childList.forEach((item, index) => {
          const price = goods.price + item.price;
          if (price <= totalMoney) {
            goodTwoList[i].push({
              price,
              weight: goods.weight + item.weight,
            });
          }
        });
      }

      let wayList = [],
        maxWeight = 0,
        baseLength = 0;

      for (let i = 0; i < goodTwoList.length; i++) {
        let tempList = [...goodTwoList[i]];
        goodTwoList[i].forEach((goods) => {
          wayList.forEach((item) =>
            tempList.push({
              price: item.price + goods.price,
              weight: item.weight + goods.weight,
            })
          );
        });
        tempList = tempList.filter((item) => {
          if (item.price <= totalMoney) {
            if (item.weight > maxWeight) {
              maxWeight = item.weight;
            }
            return true;
          }
        });

        wayList = [...wayList, ...tempList];
      }
      console.log(maxWeight);
    }
    able();

其实原计划wayList = [...wayList, ...tempList];只需用把每个货物单独的情况放进去，剩下货物之间的组合只要最后一次的就好，但其实逻辑不对，算法本身还是穷举的，例如 1,2,3,4

1
1 2 12
1 2 3 12 23 123
1 2 3 4  12 23 123 14 24 34 124 234 1234

按照优化算法在 3 的时候就只有1 2 3 23 123,少了12这种情况，如果最优解产生在这里就出问题了。

其实这种算法我在一个方便买足球彩票的前端工具、前端面试用来收尾的一道算法题都用过的，就是为了要全部结果才这么写，优化失败。

前端刷题网站
想要提升自己能力的同学并同时拿到一个满意的offer，刷题当然是提升知识面的必备的一部分，所以今天给大家推荐两个干...
前端刷题网站
leetcode（力扣）算法刷题英文网址 https://leetcode.com/[https://le...
心理学备考第16天:学习小技巧:
1分钟前 ✨心理学备考第16天: 学习小技巧:只有一个网课账号，边刷题边看答案的方法: 先用手机刷完题，打开全部解...
50天木木提醒
同学们~明天晚上八点民法第二次刷题课哈，讲解16年的民法真题。刷题课前，希望大家把16年的民法分年真题自我测试一...
IOS面试 (华为) --- 算法编辑器介绍
华为面试相比其他大厂有点区别, 第一轮是机考算法题, 算法过了才可以继续面试。算法面板用的是牛客网的算法编辑器( ...
八年级的学生雅思考了6.5分做对了什么？
7月13号，小章同学去北京考了雅思。 yq影响，这次考试是机考。考试前刷了三天题，阅读做的不好，小章同学心里没底...
前端刷题（不停更新记录）
1、css兼容性有哪几种处理方案？- 1、css初始化 margin:0;padding:0 2、各自浏览器适应 ...
刷题刷题
时间紧迫，任务繁重，又有疫情影响，搞的人心惶惶，一时间复习得不安宁，又舍不得摆烂。在焦灼、惶恐的情绪中，紧张急迫...
2018法考改革将实行2+1考试模式
法考改革除了报名条件、从业资格范围等方面的变化外，考试形式可以说是变化较大的一个方面：客观题全面机考，主观题试机考...
遇到的问题
还需要学习的东西vue源码nodejshttp等网络知识typescript设计模式还需要刷的题牛客网前端50题...