首页 / JAVASCRIPT / 最长的夜晚的最佳搜索算法-Javascript

最长的夜晚的最佳搜索算法-Javascript

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最长的夜晚的最佳搜索算法-Javascript，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10686字，纯文字阅读大概需要16分钟。

内容图文

给定一系列酒店客房及其有效期(1月1日至1月6日)：

[
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
]

上面的可用性的表格说明：

|     | 1 Jan | 2 Jan | 3 Jan | 4 Jan | 5 Jan | 6 Jan |
| 101 |   O   |   O   |   O   |       |   O   |   O   |
| 102 |   O   |       |   O   |   O   |   O   |       |
| 103 |       |   O   |   O   |       |       |   O   |
| 104 |       |       |       |   O   |   O   |   O   |
| 105 |   O   |   O   |       |   O   |       |   O   |

根据上面的输入,预期结果是具有分组可用性的最终会议室：

{
  roomId: 101, // determined by the first object in the array
  availability: [
    { roomId: 101, date: '2018-01-01' },
    { roomId: 101, date: '2018-01-02' },
    { roomId: 101, date: '2018-01-03' },
    { roomId: 104, date: '2018-01-04' },
    { roomId: 104, date: '2018-01-05' },
    { roomId: 104, date: '2018-01-06' }
  ]
}

Final grouping selection to be: 101 & 104

|     | 1 Jan | 2 Jan | 3 Jan | 4 Jan | 5 Jan | 6 Jan |
| 101 |  ??  |  ??   |  ??  |       |   O   |   O   |
| 102 |   O   |       |   O   |   O   |   O   |       |
| 103 |       |   O   |   O   |       |       |   O   |
| 104 |       |       |       |   ??  |  ??  |  ??  |
| 105 |   O   |   O   |       |   O   |       |   O   |

因此,如何根据整个住宿期间最少的房间移动来确定最终选择.

在javascript中执行此操作最有效的搜索算法是什么(就性能而言)？ (即使在长期要求可用性或将更多房间分组的情况下,也需要有效地保持真正快速的处理)

I’ll put my algorithm in the answer section, but I don’t think it is
the most efficient way to do it. Please suggest if there is a better way!

解决方法:

我建议在几天中使用循环,并在每次迭代中,确定从当天开始连续营业时间最长的房间；然后,将天数增加该天数.

为了简化解析,您可以对数据进行预处理,以使可用性信息在以数字日期索引索引的对象中可用-例如,将

availability: [
  { roomId: 105, date: '2018-01-01' },
  { roomId: 105, date: '2018-01-02' },
  { roomId: 105, date: '2018-01-04' },
  { roomId: 105, date: '2018-01-06' }
]

进入

'105': {
  1: true,
  2: true,
  4: true,
  6: true
}

这样,要弄清楚从第N天起房间X的可用时间,只需重复对room [x] [n] === true的测试,并递增n直到测试失败.

如果这是多次执行(从相同的房间数据集开始),则可以提前一次进行所有实际计算,并构造一个包含每天最佳房间的对象,例如：

{ // keys represent day index
  1: { roomId: 101, availableUntil: 3 },
  2: { roomId: 101, availableUntil: 3 }, // just as good as room 103
  3: { roomId: 101, availableUntil: 3 }, // just as good as 103 and 102
  // room 101 not available on Jan 4, room 104 becomes the best room to choose:
  4: { roomId: 104, availableUntil: 6 },
  5: { roomId: 104, availableUntil: 6 },
  6: { roomId: 104, availableUntil: 6 } // just as good as 105
}

然后,在输入了想要停留的天数之后,计算最不具破坏性的房间变化是财产查询的简单问题,直到结束时为止.

为了简化以下代码的可读性,我将使用一个辅助函数

const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

以便使索引从1开始到6,以测试您的输入,但是在您的真实代码中,您当然应该使用可靠的方法来计算dateStr和某个日期之间的天数,例如1970年1月1日,或者这样的事情. (或者,如果适合的话,可以随意使用您当前正在使用的moment(toDate).diff(moment(fromDate),’days’)

现在,执行代码：首先将数据集转换为如下所示的对象：

/*
{
  101: {
    1: true,
    2: true,
    3: true,
    5: true,
    6: true,
  },
  102:
  // ...
}
*/
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

然后,主要的getBestRoomFromDay函数获取日期索引,并搜索datasetByRoom中的每个房间对象,以查找从当前日期开始连续营业的对象：

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

在操作中,为输入中的每个dayIndex调用getBestRoomFromDay的示例(1-6)：

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}}

console.log('Example of testing getBestRoomFromDay function on all days:');
for (let i = 1; i < 7; i++) {
  console.log('Day ' + i + ': ' + JSON.stringify(getBestRoomFromDay(i)));
}

然后,要构造一个从日期到日期的字符串(例如“ 2018-01-01”至“ 2018-01-06”)的时间表,只需重复调用具有适当日期的getBestRoomFromDay,就可以将每个日期的日索引增加所需的数量迭代：

const dataset=[{roomId:101,availability:[{roomId:101,date:'2018-01-01'},{roomId:101,date:'2018-01-02'},{roomId:101,date:'2018-01-03'},{roomId:101,date:'2018-01-05'},{roomId:101,date:'2018-01-06'}]},{roomId:102,availability:[{roomId:102,date:'2018-01-01'},{roomId:102,date:'2018-01-03'},{roomId:102,date:'2018-01-04'},{roomId:102,date:'2018-01-05'}]},{roomId:103,availability:[{roomId:103,date:'2018-01-02'},{roomId:103,date:'2018-01-03'},{roomId:103,date:'2018-01-06'}]},{roomId:104,availability:[{roomId:104,date:'2018-01-04'},{roomId:104,date:'2018-01-05'},{roomId:104,date:'2018-01-06'}]},{roomId:105,availability:[{roomId:105,date:'2018-01-01'},{roomId:105,date:'2018-01-02'},{roomId:105,date:'2018-01-04'},{roomId:105,date:'2018-01-06'}]}];const dateStrToDayIndex=dateStr=>Number(dateStr.match(/\d\d$/)[0]);const datasetByRoom=dataset.reduce((datasetA,{roomId,availability})=>{datasetA[roomId]=availability.reduce((a,{date})=>{a[dateStrToDayIndex(date)]=!0;return a},{});return datasetA},{});function getBestRoomFromDay(dayIndex){let bestRoomSoFar;let bestCumulativeDaysSoFar=0;Object.entries(datasetByRoom).forEach(([room,availObj])=>{let thisRoomDays=0;let dayIndexCheck=dayIndex;while(availObj[dayIndexCheck]){dayIndexCheck++;thisRoomDays++}
if(thisRoomDays>bestCumulativeDaysSoFar){bestRoomSoFar=room;bestCumulativeDaysSoFar=thisRoomDays-1}});return{room:bestRoomSoFar,until:dayIndex+bestCumulativeDaysSoFar}};

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

完整,未缩小：

const dataset = [
  {
    roomId: 101,
    availability: [
      { roomId: 101, date: '2018-01-01' },
      { roomId: 101, date: '2018-01-02' },
      { roomId: 101, date: '2018-01-03' },
      { roomId: 101, date: '2018-01-05' },
      { roomId: 101, date: '2018-01-06' }
    ]
  },
  {
    roomId: 102,
    availability: [
      { roomId: 102, date: '2018-01-01' },
      { roomId: 102, date: '2018-01-03' },
      { roomId: 102, date: '2018-01-04' },
      { roomId: 102, date: '2018-01-05' }
    ]
  },
  {
    roomId: 103,
    availability: [
      { roomId: 103, date: '2018-01-02' },
      { roomId: 103, date: '2018-01-03' },
      { roomId: 103, date: '2018-01-06' }
    ]
  },
  {
    roomId: 104,
    availability: [
      { roomId: 104, date: '2018-01-04' },
      { roomId: 104, date: '2018-01-05' },
      { roomId: 104, date: '2018-01-06' }
    ]
  },
  {
    roomId: 105,
    availability: [
      { roomId: 105, date: '2018-01-01' },
      { roomId: 105, date: '2018-01-02' },
      { roomId: 105, date: '2018-01-04' },
      { roomId: 105, date: '2018-01-06' }
    ]
  }
];
const dateStrToDayIndex = dateStr => Number(dateStr.match(/\d\d$/)[0]);

const datasetByRoom = dataset.reduce((datasetA, { roomId, availability }) => {
  datasetA[roomId] = availability.reduce((a, { date }) => {
    a[dateStrToDayIndex(date)] = true;
    return a;
  }, {});
  return datasetA;
}, {});

function getBestRoomFromDay(dayIndex) {
  let bestRoomSoFar;
  let bestCumulativeDaysSoFar = 0;
  Object.entries(datasetByRoom).forEach(([room, availObj]) => {
    let thisRoomDays = 0;
    let dayIndexCheck = dayIndex;
    while (availObj[dayIndexCheck]) {
      dayIndexCheck++;
      thisRoomDays++;
    }
    if (thisRoomDays > bestCumulativeDaysSoFar) {
      bestRoomSoFar = room;
      bestCumulativeDaysSoFar = thisRoomDays - 1;
    }
  });
  return {
    room: bestRoomSoFar,
    until: dayIndex + bestCumulativeDaysSoFar
  };
}

function getSchedule(dateStrFrom, dateStrTo) {
  const [from, to] = [dateStrFrom, dateStrTo].map(dateStrToDayIndex);
  let day = from;
  const schedule = [];
  while (day < to) {
    const schedObj = getBestRoomFromDay(day);
    schedule.push({ from: day, ...schedObj });
    // increment day, so as to find the next longest consecutive room:
    day = schedObj.until + 1;
  }
  schedule[schedule.length - 1].until = to;
  return schedule;
}
console.log(getSchedule('2018-01-01', '2018-01-06'));

如前所述,如果必须从同一个数据集计算多个getBestRoomFromDays(即,不插入新的保留),则可以预先构造一个对象,该对象包含可以调用的每个可能值的getBestRoomFromDay,从而确保每天的计算将只进行一次.

内容总结

以上是互联网集市为您收集整理的最长的夜晚的最佳搜索算法-Javascript全部内容，希望文章能够帮你解决最长的夜晚的最佳搜索算法-Javascript所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/669050.html

来源：【匿名】

【上一篇】javascript-如何使用复选框将所有复选框全部选中或取消选中以将其选中【下一篇】javascript 怎么调用php方法

更多 ►

【最长的夜晚的最佳搜索算法-Javascript】教程文章相关的互联网学习教程文章

原创JavaScript Jquery特效之----多重特效折叠菜单(附带详细注释和算法思路)【图】

<!DOCTYPE html> <html><head><meta charset="utf-8"><title>折叠菜单</title><script type="text/javascript" src="js/jquery-2.1.0.js"></script><script type="text/javascript" src="js/foldMenu.js" ></script><style type="text/css">* {padding: 0;margin: 0;}#FoldingMenuBar {margin: 200px;;}li {list-style: none;}.left {float: left;}.TotalMenu {float: left;}.TotalMenu li{height: auto;overflow:auto;}.menuBody{...

JavaScript Base64算法的实现【代码】

js 版base 64 算法 base64.jsvar keyStr = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; //将Ansi编码的字符串进行Base64编码function encode64(input) { var output = ""; var chr1, chr2, chr3 = ""; var enc1, enc2, enc3, enc4 = ""; var i = 0; do { chr1 = input.charCodeAt(i++); chr2 = input.charCodeAt(i++); chr3 = input.charCodeAt(i++); enc1 = chr1 >> 2; enc2 = ((chr1 & 3) << 4) | (...

javascript数组去重算法-----3【代码】

1<!DOCTYPE html> 2<html lang="en"> 3<head> 4<meta charset="UTF-8"> 5<title>javascript数组去重算法-----3</title> 6</head> 7<body> 8<script> 9var arr = [1,1,2,2,3,2,2,3,3,1,1,4,4,5,6]; 10function unique(array){ 11var n = []; 12var a = {}; 13for (var i =0; i < array.length; i++) { 14if (!a[array[i]]) { 15 a[array[i]] =true; 16 n.push(array[i]) 17 }; 18 ...

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇【代码】【图】

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： 650) this.width=650;" src="/upload/getfiles/default/2022/11/8/20221108060054389.jpg" title="1513609480-59142359dda6f_articlex.png" />归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法...

JavaScript版几种常见排序算法【代码】

今天发现一篇文章讲“JavaScript版几种常见排序算法”，看着不错，推荐一下原文：http://www.w3cfuns.com/blog-5456021-5404137.html算法描述：* 冒泡排序：最简单，也最慢，貌似长度小于7最优* 插入排序：比冒泡快，比快速排序和希尔排序慢，较小数据有优势* 快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合* 希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快* 系统方法：在forfox...

数据结构算法-JavaScript常用排序法（常用排序方法的总结）【代码】【图】

JavaScript常见排序以下两个函数是排序中会用到的通用函数，就不一一写了function checkArray(array) {if (!array || array.length <= 2) return } function swap(array, left, right) {let rightValue = array[right]array[right] = array[left]array[left] = rightValue }View Code冒泡排序冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一...

关于JavaScript算法的几个小练习--DonyZ

各位小伙伴们，以下的内容来自于我在freecodecamp上做的练习，这是一个很好的学习平台，在此分享给大家，下面的题目答案在文章的最后(答案都是我自己写的，虽然都写出来了，可并不一定是最好的写法，所以希望能和大家一起交流，嘿嘿)，并且会持续更新关于JavaScript算法的文章，希望小伙伴们能多多交流，互相学习1.翻转字符串先把字符串转化成数组，再借助数组的reverse方法翻转数组顺序，最后把数组转化成字符串。你的结果必须得是...

重读《学习JavaScript数据结构与算法-第三版》- 第6章链表（一）【代码】【图】

定场诗伤情最是晚凉天，憔悴厮人不堪言；邀酒摧肠三杯醉.寻香惊梦五更寒。钗头凤斜卿有泪，荼蘼花了我无缘；小楼寂寞新雨月.也难如钩也难圆。前言本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。链表链表，为什么要有这种数据结构呢？当然，事出必有因！数组-最常用、最方便的数据结构，But，当我们从数组的起点或中间插入或移动项的成本很高，因为我们需要移...

不会全排列算法(Javascript实现)，我教你呀！【图】

今天我很郁闷，在实验室凑合睡了一晚，准备白天大干一场，结果一整天就只做出了一道算法题。看来还是经验不足呀，同志仍需努力呀。算法题目要求是这样的：Return the number of total permutations of the provided string that don‘t have repeated consecutive letters. Assume that all characters in the provided string are each unique.For example, aab should return 2 because it has 6 total permutations (aab, aab, ...

动态规划之最大公共子串算法代码实现(使用JavaScript实现)【代码】【图】

问题描述最大公共子串问题:要求在两个字符串之间找出最大的公共字符串.并且输出其所在位置.通过递推可以分析得出递推公式(博主是跟着学的,没分析) : c[i,j] = c[i-1,j-1] + 1以下图示列出了过程.文中的代码使用的是动态规划求解.其中可能有点难以理解的是下标问题: arr[i] == 0 arr[j] == 0的情况是需要进行列出来的,并且都是为0.在进行字符对比的时候,按照下标从1开始进行对比.而不是从0开始进行对比.图析代码实现 let lis...

快速排序算法的 JavaScript 实现【代码】

快速排序是一种在大多数情况下比冒泡排序效率更高（详情参考有关算法复杂度的文章）的算法。注意：许多编程语言内置的排序 API 底层实现便是基于快速排序。ES5 与 ES6 语法在实现该算法时区别不大，以下仅提供 ES5 版本。function quickSort(arr) {var len = arr.length;if (len <= 1) {return arr.slice(0); // 注意用 slice 可防范 arr[0] 为 undefined }var left = [], right = [], mid = [];mid.push(arr[0]);for (var i = 1; ...

javascript算法--随机选取10个数，并降序排列【代码】

1function rd(n,m){2var c = m - n + 1;3return Math.floor(Math.random()*c+n);4 }5var n = 10;6var m = 100;7var i = 10;8var j = 0;9var arr = []; 10while (i>0){ 11var a = rd(n,m); 12var b = 10 - i; 13var k; 14for(k = 0;k < b;k++){ 15if (a == arr[k]) { 16break; 17 } 18 }; 19if (k == b) { 20 arr[j++] = a; 21 i--; 22 } 23 ...

常见的排序算法总结（JavaScript）【代码】【图】

引言　　排序算法是数据结构和算法之中的基本功，无论是在笔试还是面试，还是实际运用中都有着很基础的地位。这不正直七月，每年校招的备战期，所以想把常见的排序算法记录下来。在本篇文章中的排序算法使用 JavaScript 实现。一、冒泡排序　　冒泡排序是排序算法中最简单的一个算法，其优点是易理解，易实现。在一些对性能要求不高且数据量不大的需求中，冒泡排序是一个很好的选择。　　原理：假设排序顺序为增序，数组长度为 N...

javascript算法挑战【代码】

1、翻转字符串算法挑战: 先把字符串转化成数组，再借助数组的reverse方法翻转数组顺序，最后把数组转化成字符串。你的结果必须得是一个字符串function reverseString(str) {arr = str.split(‘‘);str = arr.reverse().join(‘‘);return str; } reverseString("hello");2、阶乘算法挑战: 如果用字母n来代表一个整数，阶乘代表着所有小于或等于n的整数的乘积。阶乘通常简写成 n!例如: 5! = 1 * 2 * 3 * 4 * 5 = 120function factor...

一道javascript算法面试题

实现一个数组内所有元素的和。代码如下:function add(runningTotal, currentValue) {return runningTotal + currentValue; } var nums = [1,2,3,4,5,6,7,8,9,10]; var sum = nums.reduce(add); console.log(sum); // 显示55请写出reduce的实现功能。答案如下：Array.prototype.reduce=function(callback){ var total=0; this.forEach(function(e){ total=callback(total,parseInt(e));}); return total; };原文：http:/...

首页 / JAVASCRIPT / 最长的夜晚的最佳搜索算法-Javascript

最长的夜晚的最佳搜索算法-Javascript

内容导读

内容图文

内容总结

内容备注

内容手机端

【最长的夜晚的最佳搜索算法-Javascript】教程文章相关的互联网学习教程文章

JAVASCRIPT - 相关标签

搜索算法 - 相关标签

JAVASCRIPT - 技术教程分类

JAVASCRIPT - 最新教程

JAVASCRIPT - 最热教程