前端算法实战-利用贪心递归切蛋糕的小栗子

前端算法实战-利用贪心递归切蛋糕的小栗子本篇文章重点分享解决问题的思想,描述业务是真实项目遇到问题,为了简单明了侧重算法思想,会抛去一些业务介绍,重注思想。下面我们一起看一看这个小栗子吧! 在项目中遇到了这样的问题,在电子表格中存在隐藏行和合并单元格这两个概念,当和合并单元格包含在隐藏行的单元格时,就会出问题。例如,…

前言

本篇文章重点分享解决问题的思想,描述业务是真实项目遇到问题,为了简单明了侧重算法思想,会抛去一些业务介绍,重注思想。下面我们一起看一看这个小栗子吧!

背景

在项目中遇到了这样的问题,在电子表格中存在隐藏行合并单元格这两个概念,当和合并单元格包含在隐藏行的单元格时,就会出问题。例如,因为做隐藏行,会把隐藏行的单元格display: none,如果合并单元格被隐藏,会导致这个合并单元格消失,致使占位空间出问题,最终表格展示不正确。

场景分析

经过沟通思考,决定在数据层处理这个问题,思路如下:

  • 如果合并单元格冲突,就对这个单元格重新规划
  • 隐藏行就像一把刀,对合并单元格进行切割
  • 一个包含隐藏行的单元格最终被切割N个不包含隐藏行的单元格

图一:

前端算法实战-利用贪心递归切蛋糕的小栗子

图二:

前端算法实战-利用贪心递归切蛋糕的小栗子

图三:

前端算法实战-利用贪心递归切蛋糕的小栗子

算法思路

代码含义:

  • hiddenRows: 隐藏行索引号
  • mergeCells: 原始合并的单元格
  • row: 行索引
  • rowspan: 行合并跨度
    // 隐藏行
    let hiddenRows = [0, 1];
    // 合并单元格
    let mergeCells = [{
        col: 3,
        colspan: 3,
        row: 2,
        rowspan: 1
    },{
        col: 1,
        colspan: 2 
        row: 0,
        rowspan: 4
    }]

逻辑思考

做一个最简单的假设

  • 假设合并只包含一个隐藏行
  • 根据隐藏行号把合并单元格一份为二

可能存在多个隐藏行,数目不确定

  • 循环、遍历,递归

先贪心一下

  • 保证能先得到一个不包含隐藏的合并单元格(单元格)
  • 把一个大蛋糕不断的缩小

经过上述的思考,最终得到下面的代码(操作数据)

代码

// 隐藏行
let hiddenRows = [3, 6];
// 合并单元格
let mergeCells = [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
}]
let newMergeCells = [];
// 处理合并单元格,判断是否合理,不合理进行切割处理
function handleMergeCell(mergeCell) {
    let canMerge = true;
    let hiddenIndex = 0;
    let { row, rowspan } = mergeCell;
    for (let i = row; i < row + rowspan; i++) {
        if (hiddenRows.includes(i)) {
            if (canMerge) hiddenIndex = i;
            canMerge = false;
        }
    }
    canMerge && newMergeCells.push(mergeCell);
    canMerge || cuttingMergeCell(mergeCell, hiddenIndex);
}
// 切割合并单元格,保证mergeCellsTop没有问题,mergeCellsBottom再进行判断处理
// mergeCellsTop.rowspan > 0 和 mergeCellsBottom.rowspan为边界
function cuttingMergeCell(mergeCell, hiddenIndex) {
    let { row, col, rowspan, colspan } = mergeCell;
    let mergeCellsTop = {
        col,
        colspan,
        row,
        rowspan: hiddenIndex - row - 1
    };
    mergeCellsTop.rowspan > 0 && newMergeCells.push(mergeCellsTop);
    let mergeCellsBottom = {
        col,
        colspan,
        row: hiddenIndex + 1,
        rowspan: row + rowspan - hiddenIndex - 1,
    }
    mergeCellsBottom.rowspan > 0 && handleMergeCell(mergeCellsBottom);
}
mergeCells.forEach((item) => {
    handleMergeCell(item)
});
console.log(newMergeCells);

执行结果

执行代码,预期应该是2🔪切出3份

// 隐藏行
let hiddenRows = [3, 6];
// 合并单元格
let mergeCells = [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
}]

前端算法实战-利用贪心递归切蛋糕的小栗子

测试

jest

我们可以使用jest框架,做一些多场景的测试,来保证代码质量

测试代码

modify.js

export default {
    modifyMerageCells(hiddenRows, mergeCells) {
        let newMergeCells = [];
        // 处理合并单元格,判断是否合理,不合理进行切割处理
        function handleMergeCell(mergeCell) {
            let canMerge = true;
            let hiddenIndex = 0;
            let { row, rowspan } = mergeCell;
            for (let i = row; i < row + rowspan; i++) {
                if (hiddenRows.includes(i)) {
                    if (canMerge) hiddenIndex = i;
                    canMerge = false;
                }
            }
            canMerge && newMergeCells.push(mergeCell);
            canMerge || cuttingMergeCell(mergeCell, hiddenIndex);
        }
        // 切割合并单元格,保证mergeCellsTop没有问题,mergeCellsBottom再进行判断处理
        // mergeCellsTop.rowspan > 0 和 mergeCellsBottom.rowspan为边界
        function cuttingMergeCell(mergeCell, hiddenIndex) {
            let { row, col, rowspan, colspan } = mergeCell;
            let mergeCellsTop = {
                col,
                colspan,
                row,
                rowspan: hiddenIndex - row
            };
            mergeCellsTop.rowspan > 0 && newMergeCells.push(mergeCellsTop);
            let mergeCellsBottom = {
                col,
                colspan,
                row: hiddenIndex + 1,
                rowspan:row + rowspan - hiddenIndex - 1
            }
            mergeCellsBottom.rowspan > 0 && handleMergeCell(mergeCellsBottom);
        }
        mergeCells.forEach((item) => {
            handleMergeCell(item)
        });
        return newMergeCells
    }
}

modify.test


import modify  from '../src/modify';


test('modifyMerageCells测试1', () => {
  expect(modify.modifyMerageCells([0], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 1,
    rowspan: 7
  }]);
})

test('modifyMerageCells测试2', () => {
  expect(modify.modifyMerageCells([0, 1], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 2,
    rowspan: 6
  }]);
})

test('modifyMerageCells测试3', () => {
  expect(modify.modifyMerageCells([0, 1, 2], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 3,
    rowspan: 5
  }]);
})


test('modifyMerageCells测试4', () => {
  expect(modify.modifyMerageCells([1], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 1
  },{
    col: 1,
    colspan: 2,
    row: 2,
    rowspan: 6
  }]);
})


test('modifyMerageCells测试5', () => {
  expect(modify.modifyMerageCells([3], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 3
  }, {
    col: 1,
    colspan: 2,
    row: 4,
    rowspan: 4
  }]);
})

test('modifyMerageCells测试6', () => {
  expect(modify.modifyMerageCells([3, 5], [{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 8
  }])).toEqual([{
    col: 1,
    colspan: 2,
    row: 0,
    rowspan: 3
  }, {
    col: 1,
    colspan: 2,
    row: 4,
    rowspan: 1
  }, {
    col: 1,
    colspan: 2,
    row: 6,
    rowspan: 2
  }]);
})

测试结果

前端算法实战-利用贪心递归切蛋糕的小栗子

优化

这小算法写道这里还不算完事,我们可以进一步进行思考,通过空间复杂度和时间复杂度的角度进行一些优化,还可以通过缓存的角度来思考,这里就不进行进一步分析和优化啦。

如果你有什么好的建议点可以写在评论区里面,期待你的评论o!

总结

仔细想想,解决这个问题,我们做了哪些事

  • 分析问题
  • 设计解决方案
  • 利用算法知识,生成有效代码逻辑
  • 测试
  • 优化

github地址

今天的文章前端算法实战-利用贪心递归切蛋糕的小栗子分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/22774.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注