信大家看到这张图片就知道我们这篇文章要讲什么了，没错就是-商品多规格选择的解法。

近来在掘金上面看见大家都在研究“商品多规格选择”的问题，例如晨曦大佬的前端电商 sku 的全排列算法很难吗？学会这个套路，彻底掌握排列组合。 在这篇文章里面，大佬写明了如何实现sku的全排列，思路非常的棒，但是并没有紧贴业务场景。真正的业务场景是，我们要根据用户每一次选择的规格，找出剩下可选的规格和不可选的规格，表现在前端页面上：就是将不可选的规格置回，也就是如下效果（可以点击这里查看最终效果）：

那么今天我们就来讲讲这个问题的一个解决方法，要讲明白很难，但是我相信你看了这篇文章之后，sku就再也难不倒你了。

什么是 sku

在介绍具体解法之前，我们先来介绍一下什么是sku? sku是会计学中的一个名词，被称作库存单元。说人话？简单来讲就是，我们上图 中每一个单规格选项，例如深空灰色、64G,都是一个规格(sku)。商品和sku属于一对多的关系，也就是我们可以选择多个sku来确定到某个具体的商品:

业务场景

可以这么说，只要是做电商类相关的产品，比如购物 APP、购物网站等等，都会遇到这么一个场景，每个商品对应着多个规格，用户可以根据不同的规格组合，选择出自己想要的产品。我们自己在生活中也会经常用到这个功能，然而就是这样一个简单的功能，却难倒了很多小伙伴。

笔者也是一样，刚开始遇到这个场景，笔者觉得应该一个下午就能搞定，完美收工，奈何还是太过于年轻，搞了差不多两天，在网上查阅了很多相关的文章和资料，但是不得其解，最后没有办法，只能硬着头皮采用暴力求解（也就是不断循环）的方法来解决的，时间复杂度贼高，达到了O(m*n)也就是O(n²),这种实现方法其实也不是不行（能跑就行），对吧。但是后来笔者发现，当一个商品的规格非常非常多、并且用户的设备性能不是那么好的情况下，那么这种实现方式就会导致运行时间过长，表现在页面上就是：当用户点击了一个规格，会有明显的卡顿，那怎么行，客户都流失了，老板还怎么买法拉利 ️？所以笔者又开始了研究。

图

一个偶然的机会，笔者在逛知乎的时候，看到了有人在讨论图，这个数据结构，突然灵光一现，貌似咱们的多规格选择也可以用图来作求解方法，后来一尝试，还真的可行。而且时间复杂度只有O(n)，简直完美。所以我们下面来介绍一下图，什么是图？相信大学学过数据结构与算法的同学都应该知道，不过应该已经忘得一干二净了。

什么是图

图其实是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系：

图通常有如下分类:

• 分为有向图和无向图
• 分为有权图和无权图

好了知道这两个概念就差不多了,当然如果想了解更多更多概念，请看这里

那么我们需要用到的是无向图，什么是无向图呢，就像这样：

两个顶点之间如果有连线，则表示这两个顶点是互通的。小伙伴们看到这里可能会懵逼了，说了这么多，好像跟我们要解决的问题没关系啊。小伙伴们现在想一想：用户在选择规格的时候，肯定是没有先后顺序的，假设我们现在把每种规格看作是无向图的一个顶点的话，我们可以根据这些单项规格的组合规格，就可以画出一个像上图一样的无向图。

邻接矩阵

假设我们已经画出了如上 的无向图，那么我们如何将这个图用咱们的代码来表示呢？这里就用到了邻接矩阵

邻接矩阵其实是《线性代数》里面的概念，相信很多小伙伴都不会陌生，我们在代码中，表示它的方法是用一个n x n的二维数组来抽象邻接矩阵。让我们来把上面 这个无向图用邻接矩阵(二维数组)表示出来：

很显然，如果两个顶点互通（有连线），那么它们对应下标的值则为 1，否则为 0。

好了，下面开始逐步都是高能，请小伙伴们认真观看。

假设现在我们有如下规格列表：

specList: [
  { title: "颜色", list: ["红色", "紫色"] },
  { title: "套餐", list: ["套餐一", "套餐二"] },
  { title: "内存", list: ["64G", "128G", "256G"] },
];

可供选择的规格组合有：

specCombinationList: [
    { id: "1", specs: ["紫色", "套餐一", "64G"] },
    { id: "2", specs: ["紫色", "套餐一", "128G"] },
    { id: "3", specs: ["紫色", "套餐二", "128G"] },
    { id: "4", specs: ["红色", "套餐二", "256G"] }
  ],

首先，我们根据specList知道：我们有“颜色”、“套餐”、“内存”三种规格类别。分别有红色、紫色、套餐一、套餐二、64G、128G、256G这些单项规格。每个单项规格作为一个顶点，所以就有如下顶点：

然后我们根据specCombinationList，我们可以知道，哪些规格的组合是可选的。好了我们要开始画图了。

根据{ id: "1", specs: ["紫色", "套餐一", "64G"] },我们可以画出：

接下来依葫芦画瓢：我们可以根据specCombinationList剩下的数据画出如下的图：

好了，我们已经根据specCombinationList(也就是可选规格组合)将我们的规格无向图画完了。现在我们来模拟一下用户的选择:

specCombinationList: [
    { id: "1", specs: ["紫色", "套餐一", "64G"] },
    { id: "2", specs: ["紫色", "套餐一", "128G"] },
    { id: "3", specs: ["紫色", "套餐二", "128G"] },
    { id: "4", specs: ["红色", "套餐二", "256G"] }
  ],

假设用户先选择了紫色、根据specCombinationList,我们发现套餐一、套餐二、64G、128G是可选的，这个时候我们发现一个问题：显然跟紫色同级的红色其实也是可选的。所以这个图其实我们还没有画完。所以相同类型的规格其实是应该连接起来的：

好了，无向图画好了，现在我们将它映射到邻接矩阵上面（这一步强烈建议小伙伴们拿出纸笔来一起画一画）：

到了这一步，恭喜你，你已经懂了一大半了 。

好了，到这我们就可以公布最终结论了：

• 当用户初次进入该页面时，所有的规格均可选：

• 当用户选择了某个顶点后，当前顶点所有可选项均被找出（即是当前顶点所在列值为 1 的顶点）：

• 选取多个顶点时，可选项是各个顶点邻接点的交集：（即是选中顶点所在列的交集）

代码实现

说真的，我觉得小伙伴们看明白了我上面 这些讲解，相信你已经完全懂了该如何实现“多规格选择”算法了。不过有句话叫做：光说不练假把式！那下面我们就一起来捋一捋，用代码如何实现吧，笔者这里用的前端框架是react，明白思路了，用什么框架都一样的哦。

这里先说下思路：

1、根据规格列表（specList）创建邻接矩阵（数组）

2、根据可选规格组合(specCombinationList)填写顶点的值

3、获得所有可选顶点，然后根据可选顶点填写同级顶点的值

创建邻接矩阵

首先，我们需要提供一个类来创建邻接矩阵。一个邻接矩阵，首先需要传入一个顶点数组：vertex,需要一个用来装邻接矩阵的数组：adjoinArray。刚刚我们上面说到了，这个类还必须提供计算并集和交集的方法：

export type AdjoinType = Array<string>;

export default class AdjoinMatrix {
  vertex: AdjoinType; // 顶点数组
  quantity: number; // 矩阵长度
  adjoinArray: Array<number>; // 矩阵数组

  constructor(vertx: AdjoinType) {
    this.vertex = vertx;
    this.quantity = this.vertex.length;
    this.adjoinArray = [];
    this.init();
  }
  // 初始化数组
  init() {
    this.adjoinArray = Array(this.quantity * this.quantity).fill(0);
  }

  /*
   * @param id string
   * @param sides Array<string>
   *  传入一个顶点，和当前顶点可达的顶点数组，将对应位置置为1
   */
  setAdjoinVertexs(id: string, sides: AdjoinType) {
    const pIndex = this.vertex.indexOf(id);
    sides.forEach((item) => {
      const index = this.vertex.indexOf(item);
      this.adjoinArray[pIndex * this.quantity + index] = 1;
    });
  }

  /*
   * @param id string
   * 传入顶点的值，获取该顶点的列
   */
  getVertexCol(id: string) {
    const index = this.vertex.indexOf(id);
    const col: Array<number> = [];
    this.vertex.forEach((item, pIndex) => {
      col.push(this.adjoinArray[index + this.quantity * pIndex]);
    });
    return col;
  }

  /*
   * @param params Array<string>
   * 传入一个顶点数组，求出该数组所有顶点的列的合
   */
  getColSum(params: AdjoinType) {
    const paramsVertex = params.map((id) => this.getVertexCol(id));
    const paramsVertexSum: Array<number> = [];
    this.vertex.forEach((item, index) => {
      const rowtotal = paramsVertex
        .map((value) => value[index])
        .reduce((total, current) => {
          total += current || 0;
          return total;
        }, 0);
      paramsVertexSum.push(rowtotal);
    });
    return paramsVertexSum;
  }

  /*
   *  @param params Array<string>
   * 传入一个顶点数组，求出并集
   */
  getCollection(params: AdjoinType) {
    const paramsColSum = this.getColSum(params);
    let collections: AdjoinType = [];
    paramsColSum.forEach((item, index) => {
      if (item && this.vertex[index]) collections.push(this.vertex[index]);
    });
    return collections;
  }

  /*
   *  @param params Array<string>
   * 传入一个顶点数组，求出交集
   */
  getUnions(params: AdjoinType) {
    const paramsColSum = this.getColSum(params);
    let unions: AdjoinType = [];
    paramsColSum.forEach((item, index) => {
      if (item >= params.length && this.vertex[index]) unions.push(this.vertex[index]);
    });
    return unions;
  }
}

有了这个类，接下来可以创建一个专门用于生成商品多规格选择的类，它继承于AdjoinMatrix。

创建多规格选择邻接矩阵

我们这个多规格选择的邻接矩阵，需要提供一个查询可选顶点的方法：getSpecscOptions

import AdjoinMatrix from "./adjoin-martix";
import { AdjoinType } from "./adjoin-martix";
import { SpecCategoryType, CommoditySpecsType } from "../redux/reducer/spec-reducer";

export default class SpecAdjoinMatrix extends AdjoinMatrix {
  specList: Array<CommoditySpecsType>;
  specCombinationList: Array<SpecCategoryType>;

  constructor(specList: Array<CommoditySpecsType>, specCombinationList: Array<SpecCategoryType>) {
    super(specList.reduce((total: AdjoinType, current) => [...total, ...current.list], []));
    this.specList = specList;
    this.specCombinationList = specCombinationList;
    // 根据可选规格列表矩阵创建
    this.initSpec();
    // 同级顶点创建
    this.initSameLevel();
  }

  /**
   * 根据可选规格组合填写邻接矩阵的值
   */
  initSpec() {
    this.specCombinationList.forEach((item) => {
      this.fillInSpec(item.specs);
    });
  }
  // 填写同级点
  initSameLevel() {
    // 获得初始所有可选项
    const specsOption = this.getCollection(this.vertex);
    this.specList.forEach((item) => {
      const params: AdjoinType = [];
      // 获取同级别顶点
      item.list.forEach((value) => {
        if (specsOption.includes(value)) params.push(value);
      });
      // 同级点位创建
      this.fillInSpec(params);
    });
  }
  /*
   * 传入顶点数组，查询出可选规格
   * @param params
   */
  getSpecscOptions(params: AdjoinType) {
    let specOptionCanchoose: AdjoinType = [];
    if (params.some(Boolean)) {
      // 过滤一下选项
      specOptionCanchoose = this.getUnions(params.filter(Boolean));
    } else {
      // 所有可选项
      specOptionCanchoose = this.getCollection(this.vertex);
    }
    return specOptionCanchoose;
  }

  /*
   * @params
   * 填写邻接矩阵的值
   */
  fillInSpec(params: AdjoinType) {
    params.forEach((param) => {
      this.setAdjoinVertexs(param, params);
    });
  }

页面渲染

好了到了这一步，我们已经可以在页面中使用这两个类了：

import React, { useState, useMemo } from "react";
import { useSelector } from "react-redux";
import { RootState } from "../redux/reducer/root-reducer";
import SpecAdjoinMatrix from "../utils/spec-adjoin-martix";
import "./spec.css";
const classNames = require("classnames");

const Spec: React.FC = () => {
  const { specList, specCombinationList } = useSelector((state: RootState) => state.spec);
  // 已选择的规格，长度为规格列表的长度
  const [specsS, setSpecsS] = useState(Array(specList.length).fill(""));

  // 创建一个规格矩阵
  const specAdjoinMatrix = useMemo(() => new SpecAdjoinMatrix(specList, specCombinationList), [specList, specCombinationList]);
  // 获得可选项表
  const optionSpecs = specAdjoinMatrix.getSpecscOptions(specsS);

  const handleClick = function(bool: boolean, text: string, index: number) {
    // 排除可选规格里面没有的规格
    if (specsS[index] !== text && !bool) return;
    // 根据text判断是否已经被选中了
    specsS[index] = specsS[index] === text ? "" : text;
    setSpecsS(specsS.slice());
  };

  return (
    <div className="container">
      {specList.map(({ title, list }, index) => (
        <div key={index}>
          <p className="title">{title}</p>
          <div className="specBox">
            {list.map((value, i) => {
              const isOption = optionSpecs.includes(value); // 当前规格是否可选
              const isActive = specsS.includes(value); // 当前规格是否被选
              return (
                <span
                  key={i}
                  className={classNames({
                    specOption: isOption,
                    specAction: isActive,
                    specDisabled: !isOption,
                  })}
                  onClick={() => handleClick(isOption, value, index)}
                >
                  {value}
                </span>
              );
            })}
          </div>
        </div>
      ))}
    </div>
  );
};

export default Spec;

好了，打完收工了，如果有小伙伴想看实现效果，可以查看这里，如果有小伙伴想把代码拉到本地看看，那么请点击这里

总结

实践证明：大学学的东西是真的有用的。我们通过图，解决了商品多规格选择的难题。在求解可选规格的时候，时间复杂度由原来的O(n²)变成了O(n)。不过值得一提的是，采用邻接矩阵来存储图，空间复杂度就变成了O(n²)了，同时也存在浪费空间的问题，但是图肯定不止有邻接矩阵这一种存储方法，我们还可以用链表来存储图，小伙伴们可以自己去试一试。另外如果用链表来存储图，空间复杂度会变低，但是时间复杂度会变高，具体如何选择，就看小伙伴们自己权衡了。

以后遇到这个需求，小伙伴们肯定是分分钟实现，提早下班。

我是觉非，码字不易，如果你觉得这篇文章对你有用的话，请给个赞吧！！

作者：觉非
链接：https://juejin.im/post/5eef2fcee51d4574113a0203
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

、HTML标签：表单标签

1.1 表单概念：用于采集用户输入的数据的。用于和服务器进行交互。

1.2 语法：

form：用于定义表单的，可以定义一个范围，范围代表采集用户数据的范围

属性：

action：指定提交数据的URL

method：指定提交方式

method分类：一共7种，2种比较常用

get：

1. 请求参数会在地址栏中显示。会封装到请求行中(HTTP协议后讲解)。

2. 请求参数大小是有限制的。

3. 不太安全。

post：

1. 请求参数不会再地址栏中显示。会封装在请求体中(HTTP协议后讲解)

2. 请求参数的大小没有限制。

3. 较为安全。

注意：表单项中的数据要想被提交：必须指定其name属性

二、表单项标签：

2.1 input：可以通过type属性值，改变元素展示的样式

2.1.1 type属性：

text：文本输入框，默认值

placeholder：指定输入框的提示信息，当输入框的内容发生变化，会自动清空提示信息

password：密码输入框

radio:单选框

注意：

1. 要想让多个单选框实现单选的效果，则多个单选框的name属性值必须一样。

2. 一般会给每一个单选框提供value属性，指定其被选中后提交的值

3. checked属性，可以指定默认值

checkbox：复选框

注意：

1. 一般会给每一个单选框提供value属性，指定其被选中后提交的值

2. checked属性，可以指定默认值

file：文件选择框

hidden：隐藏域，用于提交一些信息。

按钮：

submit：提交按钮。可以提交表单

button：普通按钮

image：图片提交按钮

src属性指定图片的路径

label：指定输入项的文字描述信息

注意：

label的for属性一般会和 input 的id属性值对应。如果对应了，则点击label区域，会让input输入框获取焦点。

select: 下拉列表，子元素option，指定列表项

textarea：文本域，cols指定列数，每一行有多少个字符，rows默认多少行。

三、CSS：页面美化和布局控制

3.1 概念： Cascading Style Sheets 层叠样式表

层叠：多个样式可以作用在同一个html的元素上，同时生效

3.2 好处：

1. 功能强大

2. 将内容展示和样式控制分离

3. 降低耦合度。解耦

4. 让分工协作更容易

5. 提高开发效率

3.3 CSS的使用：CSS与html结合方式

3.3.1 内联样式：在标签内使用style属性指定css代码

如：<div style="color:red;">hello css</div>

3.3.2 内部样式：在head标签内，定义style标签，style标签的标签体内容就是css代码

如：

<style>

div{

color:blue;

}

</style>

<div>hello css</div>

3.3.3 外部样式

1. 定义css资源文件。

2. 在head标签内，定义link标签，引入外部的资源文件

如：

a.css文件：

div{

color:green;

}

html文件：

<link rel="stylesheet" href="css/a.css">

<div>hello css</div>

注意：

1,2,3种方式 css作用范围越来越大

1方式不常用，后期常用2,3

3.4 css语法：

3.4.1 格式：

选择器 {

属性名1:属性值1;

属性名2:属性值2;

...

}

* 选择器:筛选具有相似特征的元素

* 注意：

* 每一对属性需要使用；隔开，最后一对属性可以不加；

3.5 css选择器：筛选具有相似特征的元素

3.5.1 分类：

1. 基础选择器：

1. id选择器：选择具体的id属性值的元素.建议在一个html页面中id值唯一

* 语法：#id属性值{}

2. 元素选择器：选择具有相同标签名称的元素

* 语法： 标签名称{}

* 注意：id选择器优先级高于元素选择器

3. 类选择器：选择具有相同的class属性值的元素。

* 语法：.class属性值{}

* 注意：类选择器选择器优先级高于元素选择器

2. 扩展选择器：

1. 选择所有元素：

* 语法： *{}

2. 并集选择器：

* 选择器1,选择器2{}

3. 子选择器：筛选选择器1元素下的选择器2元素

* 语法： 选择器1 选择器2{}

4. 父选择器：筛选选择器2的父元素选择器1

* 语法： 选择器1 > 选择器2{}

5. 属性选择器：选择元素名称，属性名=属性值的元素

* 语法： 元素名称[属性名="属性值"]{}

6. 伪类选择器：选择一些元素具有的状态

* 语法： 元素:状态{}

* 如： <a>

* 状态：

* link：初始化的状态

* visited：被访问过的状态

* active：正在访问状态

* hover：鼠标悬浮状态

3.6 css属性：

1. 字体、文本

* font-size：字体大小

* color：文本颜色

* text-align：对其方式

* line-height：行高

2. 背景

* background：

3. 边框

* border：设置边框，符合属性

4. 尺寸

* width：宽度

* height：高度

5. 盒子模型：控制布局

* margin：外边距

* padding：内边距

* 默认情况下内边距会影响整个盒子的大小

* box-sizing: border-box; 设置盒子的属性，让width和height就是最终盒子的大小

* float：浮动

* left

* right