Day55 | k's Learn Notes

手写算法: 最接近的三数之和

同样可用双指针

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  const len = nums.length;
  if (len < 3) return [];
  nums.sort((a, b) => a - b);
  let result = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < len; i++) {
    let L = i + 1,
      R = len - 1;
    while (L < R) {
      let temp = nums[i] + nums[L] + nums[R];
      if (Math.abs(target - temp) < Math.abs(target - result)) {
        result = temp;
      }
      if (temp < target) {
        L++;
      } else if (temp > target) {
        R--;
      } else {
        return result;
      }
    }
  }
  return result;
};

手写题

Virtual DOM I

113. Virtual DOM I open in new window

思路

在构建虚拟 dom 的时候，要思考需要拿到一些什么数据，才能把它转换成 dom 结构，就按照这个思路下去。

其实代码很简单，就是个递归的过程罢了。

一些用到的 API

【 Get 】

node.tagName 拿到节点的类型type
node.childNodes 拿到节点的子节点

【 Check 】

node.hasAttributes() 查找节点上是否有带属性
node.hasChildNodes() 查找节点上是否有子节点

【 Set 】

node.setAttribute(name, value) 给节点加上属性

【 Create 】

document.createElement(tagName) 创建 element 节点
document.createTextNode(textContent) 创建文本节点

【 Add 】

node.classList.add(className) 给节点上添加类名
node.append(childNode) 添加子节点

【 NodeType 】

1 -> element node
2 -> attribute node
3 -> text node
8 -> comment node
9 -> document node 文本节点
10 -> documentType node 文本类型节点
11 -> documentFragment node 文档碎片

/**
 * @param {HTMLElement}
 * @return {object} object literal presentation
 */
function virtualize(element) {
  let result = {
    type: element.tagName.toLowerCase(),
    props: {},
  };

  let props = {};
  if (element.hasAttributes()) {
    for (const { name, value } of element.attributes) {
      props[name === 'class' ? 'className' : name] = value;
    }
  }

  let children = [];
  if (element.hasChildNodes()) {
    for (const node of element.childNodes) {
      if (node.nodeType === 1) {
        children.push(virtualize(node));
      } else if (node.nodeType === 3) {
        children.push(node.textContent);
      }
    }
  }

  children.length && (props.children = children.length === 1 ? children[0] : children);

  result.props = props;
  return result;
}

/**
 * @param {object} valid object literal presentation
 * @return {HTMLElement}
 */
function render(obj) {
  let {
    type,
    props: { className, children, ...restProps },
  } = obj;
  const element = document.createElement(type);

  if (className) {
    element.classList.add(className);
  }

  if (children) {
    if (!Array.isArray(children)) {
      // 为了给底下遍历，统一将不是数组的转换成数组
      children = [children];
    }

    children.forEach(child => {
      if (typeof child === 'string') {
        element.append(document.createTextNode(child));
      } else {
        element.append(render(child));
      }
    });
  }

  if (restProps) {
    Object.entries(restProps).forEach(([key, value]) => {
      element.setAttribute(key, value);
    });
  }

  return element;
}

🎉 🎉 👏 完成了！再来一题～～

Virtual DOM II - createElement

118. Virtual DOM II - createElementopen in new window

/**
 * MyElement is the type your implementation supports
 *
 * type MyNode = MyElement | string
 */

/**
 * @param { string } type - valid HTML tag name
 * @param { object } [props] - properties.
 * @param { ...MyNode} [children] - elements as rest arguments
 * @return { MyElement }
 */
function createElement(type, props, ...children) {
  const element = document.createElement(type);

  for (key in props) {
    element.setAttribute(key === 'className' ? 'class' : key, props[key]);
  }

  for (const child of children) {
    if (typeof child === 'string') {
      element.append(document.createTextNode(child));
    } else {
      element.append(child);
    }
  }

  return element;
}

/**
 * @param { MyElement }
 * @returns { HTMLElement }
 */
function render(myElement) {
  return myElement;
}

趁热打铁！！再来一题 🚬

Virtual DOM III - Functional Component

140. Virtual DOM III - Functional Componentopen in new window

思路

分析题意，createElement(type, props, children)，type 的类型不单单只是 String，也有可能是 Function
当 type 为 Function 时，入参为 props，其中包含 children、className 以及其他属性，即type({children, ...rest})

内部会调用调用 createElement，返回 json

/**
 * MyElement is the type your implementation supports
 *
 * type MyNode = MyElement | string
 * type FunctionComponent = (props: object) => MyElement
 */

/**
 * @param { string | FunctionComponent } type - valid HTML tag name or Function Component
 * @param { object } [props] - properties.
 * @param { ...MyNode} [children] - elements as rest arguments
 * @return { object | string } MyElement
 */
function createElement(type, props, ...children) {
  // your code here
  if (typeof type === 'function') {
    return type({ children, ...props });
  }
  return { type, props, children };
}

/**
 * @param { object | string } MyElement - json Object
 * @returns { HTMLElement }
 */
function render(myElement) {
  if (typeof myElement === 'string') {
    return document.createTextNode(myElement);
  }

  const { type, props, children } = myElement;
  const element = document.createElement(type);

  for (const key in props) {
    element.setAttribute(key === 'className' ? 'class' : key, props[key]);
  }

  children.forEach(node => element.append(render(node)));

  return element;
}

再升级一下 ✍️ ～～

Virtual DOM IV - JSX 1

143. Virtual DOM IV - JSX 1open in new window

/**
 * @param {code} string
 * @returns {any} AST
 */
function parse(code) {
  code = code.trim();
  if (code[0] !== '<' || code[code.length - 1] !== '>') return;
  if (code.split('<').length !== code.split('>').length) return;

  // 找闭合标签开头
  const openTagIndex = code.indexOf('<');
  const closeTagIndex = code.indexOf('>');
  const str = code.slice(openTagIndex + 1, closeTagIndex).trim();
  // 检查标签，是否符合标准。开始标签中不应该出现/，若出现了就中断
  if (str.indexOf('/') !== -1) {
    return;
  }

  const arr = str.split(' ');
  const tagName = arr[0];
  let props = {};
  for (let i = 1; i < arr.length; i++) {
    const [key, value] = arr[i].split('=');
    props[key] = value;
  }

  // 找闭合标签结束
  const lastOpenTagIndex = code.lastIndexOf('<');
  const lastCloseTagIndex = code.lastIndexOf('>');
  // 将前后空格全部都去掉
  const lastTagName = code
    .slice(lastOpenTagIndex + 1, lastCloseTagIndex)
    .trim()
    .replaceAll(' ', '');
  // 检查闭合标签，是否符合标准，是否跟开始标签一致
  if (lastTagName[0] !== '/' || tagName !== lastTagName.slice(1)) {
    return;
  }
  const child = code.slice(closeTagIndex + 1, lastOpenTagIndex);
  props.children = child ? [child] : [];

  return {
    type: tagName,
    props,
  };
}

/**
 * @param {any} your AST
 * @returns {string}
 */
function generate(ast) {
  // your code here
  const { type, props } = ast;
  return {
    type,
    props,
  };
}

console.log(parse('<a href="www.baidu.com">bfe.dev</a>'));

Virtual DOM V - JSX 2

150. Virtual DOM V - JSX 2open in new window

type JSXOpeningElement = {
  tag: string;
};

type JSXClosingElement = {
  tag: string;
};

type JSXChildren = Array<string | JSXElement>;

type JSXElement = {
  openingElement: JSXOpeningElement;
  children: JSXChildren;
  closingElement: JSXClosingElement;
};

// 转化成抽象语法树
function formatJSX({ openTagName, closeTagName, children }: Record<string, any>) {
  return {
    openingElement: { tag: openTagName },
    closingElement: { tag: closeTagName },
    children,
  };
}

// 检查是否是闭合标签
function checkCloseTag(str: string, i: number): boolean {
  if (str[i] === '/') return true;
  if (str[i] === '>') return false;
  return checkCloseTag(str, i + 1);
}

// 解析tag
function parseTag(str: string): [tagEndIndex: number, tagName: string, isClose: boolean] {
  let tagEndIndex = str.indexOf('>');
  let tagName = str.slice(1, tagEndIndex).trim();
  let isClose = false;

  if (tagName[0] === '/') {
    tagName = tagName.slice(1).trim();
    isClose = true;
  }
  return [tagEndIndex, tagName, isClose];
}

// 解析children
function parseChildren(str: string): [JSXChildren, number] {
  let children = [],
    text = '',
    i = 0;

  for (; i < str.length; i++) {
    // 判断是否是闭合标签，是的话，跳出循环
    if (str[i] === '<' && checkCloseTag(str, i)) {
      break;
    }

    // 非结束标签，进行递归codeParse函数，拿到内容塞到children里面
    if (str[i] === '<') {
      if (text) {
        children.push(text);
        text = '';
      }
      const childTag = codeParse(str.slice(i));
      children.push(formatJSX(childTag));
      i += childTag.closeTagEndIndex;
      continue;
    }
    text += str[i];
  }
  // 如果是文本内容，也塞到children中
  if (text) children.push(text);
  return [children, i];
}

// 解析html
function codeParse(code: string): {
  openTagName: string;
  closeTagName: string;
  children: JSXChildren;
  closeTagEndIndex: number;
} {
  code = code.trim();
  if (code[0] !== '<' || code[code.length - 1] !== '>' || code.split('<').length !== code.split('>').length) {
    throw new Error('不是正确的html格式，请检查');
  }

  /**
   * 记录当前字符的位置
   * 这里为什么是1呢？
   * 因为indexOf('>')找到的是当前结束标签的位置，需要+1，才能到后面的内容元素，
   * 不然的话在底下计* 算i要变成 i += openTagEndIndex + 1;
   **/
  let i = 1;
  // 解析开标签
  const [openTagEndIndex, openTagName] = parseTag(code);
  // 去掉开标签字符
  code = code.substring(openTagEndIndex + 1);
  // 同步检查到的字符索引
  i += openTagEndIndex;
  // 解析子节点
  const [children, skipIndex] = parseChildren(code);
  // 去掉子节点的字符
  code = code.substring(skipIndex);
  // 同步索引
  i += skipIndex;
  // 解析结束标签
  const [closeTagEndIndex, closeTagName, isClose] = parseTag(code);
  code = code.substring(closeTagEndIndex);
  i += closeTagEndIndex;

  if (!isClose || openTagName !== closeTagName) {
    throw new Error(`isClose: ${isClose}, openTagName: ${openTagName}, closeTagName: ${closeTagName}`);
  }

  return {
    openTagName,
    closeTagName,
    children,
    // 目的是为了子节点碰到标签需要递归时，知道目前位置到哪里了
    closeTagEndIndex: i,
  };
}

function parse(code: string): JSXElement {
  // your code here
  const json = codeParse(code);
  return formatJSX(json);
}

function generate(ast: JSXElement | string): string | Record<string, any> {
  if (typeof ast === 'string') return ast;

  const tagName = ast.openingElement.tag;
  const type = tagName[0] === tagName[0].toUpperCase() ? Heading : tagName;

  return {
    type,
    props: { children: ast.children.map(generate) },
  };
}

# 手写算法: 最接近的三数之和

# 手写题

# Virtual DOM I

# 思路

# Virtual DOM II - createElement

# Virtual DOM III - Functional Component