通知设置 新通知
PWA实战：自如互联网研发部官方APP开发历程
zkbhj 发表了文章 • 0 个评论 • 1628 次浏览 • 2017-12-14 13:45
这两天正值谷歌开发者大会在上海召开，（谷歌开发者大会2017官网）。朋友圈中出现了一条大会上关于PWA的状态，恰巧丽姐也我和说到了pwa应该学一学。这就勾起了我对这个pwa到底是啥的好奇心。丽姐说，那就先做一个咱们部门自己的APP呗，一期可以只上个值班表。嗯，起源就是这样。
互联网研发部官方APP（PWA版）：ziroom.zkbhj.com
那既然要用到这个进行开发，首先需要了解什么是PWA，以及开发还需要学习和熟悉哪些相关的知识技术。
一、什么是PWA？
Progressive Web Apps 是结合了 Web 和 原生应用中最好功能的一种体验。对于首次访问的用户它是非常有利的, 用户可以直接在浏览器中进行访问，不需要安装应用。随着时间的推移当用户渐渐地和应用建立了联系，它将变得越来越强大。它能够快速地加载，即使在比较糟糕的网络环境下，能够推送相关消息, 也可以像原生应用那样添加至主屏，能够有全屏浏览的体验。
渐进增强 - 能够让每一位用户使用，无论用户使用什么浏览器，因为它是始终以渐进增强为原则。响应式用户界面 - 适应任何环境：桌面电脑，智能手机，笔记本电脑，或者其他设备。不依赖网络连接 - 通过 service workers 可以在离线或者网速极差的环境下工作。类原生应用 - 有像原生应用般的交互和导航给用户原生应用般的体验，因为它是建立在 app shell model 上的。持续更新 - 受益于 service worker 的更新进程，应用能够始终保持更新。安全 - 通过 HTTPS 来提供服务来防止网络窥探，保证内容不被篡改。可发现 - 得益于 W3C manifests 元数据和 service worker 的登记，让搜索引擎能够找到 web 应用。再次访问 - 通过消息推送等特性让用户再次访问变得容易。可安装 - 允许用户保留对他们有用的应用在主屏幕上，不需要通过应用商店。可连接性 - 通过 URL 可以轻松分享应用，不用复杂的安装即可运行。
本次开发实践是根据官方的引导指南一步步完成自己的 Progressive Web App，包括设计时需要考虑的因素，也包括实现细节，以确保应用程序符合 Progressive Web App 的关键原则。官方指南的地址在文末有附加。
需要注意的是：PWA类型的应用，处于安全考虑，只能允许使用HTTPS协议，如果是非HTTPS加密协议，会报错，虽然能够正常浏览页面，但是核心功能已经失效。Uncaught (in promise) DOMException: Only secure origins are allowed (see: https@//goo.gl/Y0ZkNV).
那么本次开发实践，我们将要学会以下几点：
如何使用 "app shell" 的方法来设计和构建应用程序。如何让你的应用程序能够离线工作。如何存储数据以在离线时使用。
在我们正式开始我们的开发之前，需要熟知以下几个概念：
什么是应用外壳(App Shell)
App Shell是应用的用户界面所需的最基本的 HTML、CSS 和 JavaScript，也是一个用来确保应用有好多性能的组件。它的首次加载将会非常快，加载后立刻被缓存下来。这意味着应用的外壳不需要每次使用时都被下载，而是只加载需要的数据。
应用外壳的结构分为应用的核心基础组件和承载数据的 UI。所有的 UI 和基础组件都使用一个 service worker 缓存在本地，因此在后续的加载中 Progressive Web App 仅需要加载需要的数据，而不是加载所有的内容。换句话说，应用的壳相当于那些发布到应用商店的原生应用中打包的代码。它是让你的应用能够运行的核心组件，只是没有包含数据。
为什么使用基于应用外壳的结构?
使用基于应用外壳的结构允许你专注于速度，给你的 Progressive Web App 和原生应用相似的属性：快速的加载和灵活的更新，所有这些都不需要用到应用商店。
如何设计应用的外壳？
第一步是设计核心组件
首先我们要问问自己：
需要立刻显示什么在屏幕上？我们的应用需要那些关键的 UI 组件？应用外壳需要那些资源？比如图片，JavaScript，样式表等等。
我们将要创建一个部门给大家用的一个 Progressive Web App 。可能包含的功能比如可以展示我们部门人员的信息，值班表信息，项目列表信息等，基于需求，那么这个APP的核心组件包括：
一个基础的UI架构，菜单，页面中会要用到的基本元素，以及这些相关依赖的js文件、css样式表和图片等。
当然这个UI框架有很多种选择，官方推荐的是Web Starter Kit。 ，GIT地址为：https://github.com/google/web-starter-kit
由于我们的目的并不是要做一个功能多复杂的APP，我们的目的是要通过这个简单APP的开发了解和学会PWA的相关知识。
开发正式开始，首先，我们需要创建一个index.html文件，把我们设计的核心组件的代码都填进去。当然还有相关依赖的js文件、css样式表和图片等。
到这里我们的外壳已经有了，接下来，就是要把他启动起来！
在启动代码中，我们将包括(你可以在(js/app.js)的文件夹中找到)。看完了代码结构，我们要认识一个比较牛逼的东西！
使用 Service Workers 来预缓存应用外壳
Progressive Web Apps 是快速且可安装的，这意味着它能在在线、离线、断断续续或者缓慢的网络环境下使用。为了实现这个目标，我们需要使用一个 service worker 来缓存应用外壳，以保证它能始终迅速可用且可靠。详细了解Service Worker是什么，可以访问这篇文章来详细了解：https://developers.google.com/web/fundamentals/getting-started/primers/service-workers
service workers 提供的是一种应该被理解为渐进增强的特性，这些特性仅仅作用于支持service workers 的浏览器。比如，使用 service workers 你可以缓存应用外壳和你的应用所需的数据，所以这些数据在离线的环境下依然可以获得。如果浏览器不支持 service workers ，支持离线的 代码没有工作，用户也能得到一个基本的用户体验。使用特性检测来渐渐增强有一些小的开销，它不会在老旧的不支持 service workers 的浏览器中产生破坏性影响。
注册 service worker
为了让应用离线工作，要做的第一件事是注册一个 service worker，一段允许在后台运行的脚本，不需要 用户打开 web 页面，也不需要其他交互。
这只需要简单两步：
创建一个 JavaScript 文件作为 service worker告诉浏览器注册这个 JavaScript 文件为 service worker
第一步，在你的应用根目录下创建一个空文件叫做 serviceworker.js 。这个 serviceworker.js 文件必须放在跟目录，因为 service workers 的作用范围是根据其在目录结构中的位置决定的。
接下来，我们需要检查浏览器是否支持 service workers，如果支持，就注册 service worker，将下面代码添加至 app.js中。//首先判断浏览器是否支持，如果支持，就注册serviceWorker
if ('serviceWorker' in navigator) {
navigator.serviceWorker
.register('./serviceworker.js')
.then(function() { console.log('Service Worker Registered'); });
}缓存站点的资源
当 service worker 被注册以后，当用户首次访问页面的时候一个 install 事件会被触发。在这个事件的回调函数中，我们能够缓存所有的应用需要再次用到的资源。//定义缓存名称
//缓存名允许我们给缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存
var cacheName = 'pwa-ziroom-php-v4';
//设置需要缓存的文件
var filesToCache = [
'./',
'./css/style.css',
*
];
self.addEventListener('install', function(event) {
console.log('Service Worker: Installing....');
event.waitUntil(
//打开缓存
caches.open(cacheName).then(function(cache) {
console.log('Service Worker: Caching App Shell at the moment......');
return cache.addAll(filesToCache);
})
);
});首先，我们需要提供一个缓存的名字并利用 caches.open()打开 cache 对象。提供的缓存名允许我们给 缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存。
一旦缓存被打开，我们可以调用 cache.addAll() 并传入一个 url 列表，然后加载这些资源并将响应添加至缓存。不幸的是 cache.addAll() 是原子操作，如果某个文件缓存失败了，那么整个缓存就会失败！
ok，到现在我们已经将要缓存的文件缓存到本地了，但是我们的应用目前还不能离线工作。我们缓存了 app shell 的组件，但是我们仍然需要从本地缓存中加载它们。
从缓存中加载 app sheel
Service workers 可以截获 Progressive Web App 发起的请求并从缓存中返回响应。这意味着我们能够 决定如何来处理这些请求，以及决定哪些网络响应能够成为我们的缓存。
self.addEventListener('fetch', function(event) {
console.log('Service Worker: Fetch', event.request.url);
console.log("Url", event.request.url);
event.respondWith(
caches.match(event.request).then(function(response) {
return response || fetch(event.request);
})
);
});从内至外，caches.match() 从网络请求触发的 fetch 事件中得到请求内容，并判断请求的资源是 否存在于缓存中。然后以缓存中的内容作为响应，或者使用 fetch 函数来加载资源（如果缓存中没有该资源）。 response 最后通过 e.respondWith() 返回给 Web 页面。
使用 manifest.json 文件来声明一个应用程序清单
Web 应用程序清单是一个简单的 JSON 文件，它给你了控制你的应用如何出现在用户期待出现的地方（比如用户手机主屏幕），这直接影响到用户能启动什么，以及更重要的，用户如何启动它。
使用 web 应用程序清单，你的应用可以：
能够真实存在于用户主屏幕上在 Android 上能够全屏启动，不显示地址栏控制屏幕方向已获得最佳效果定义启动画面，为你的站点定义主题追踪你的应用是从主屏幕还是 URL 启动的
告诉浏览器你的程序清单文件
将这段代码添加至你的 index.html 的 <head> 部分：<link rel="manifest" href="./manifest.json">一些最佳实践
将程序清单的链接添加至你站点的所有页面上，这样在用户第一次访问的时候它能够被 Chrome 正确检索到，且不管用户从哪个页面访问的。如果同时提供了 name 和 short_name，short_name 是 Chrome 的首选。为不同分辨率的屏幕提供不同的 icon。Chrome 会尝试使用最接近 48dp 的图标，比如在 2x 屏上使用 96px 的，在 3x屏上使用 144px 的。记得要包含一个适合在启动画面上显示的图标，另外别忘了设置 background_color。
iOS Safari 的添加至主屏幕元素<!-- Add to home screen for Safari on iOS -->
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="apple-mobile-web-app-title" content="ZiPHP">
<link rel="apple-touch-icon" href="./images/icon/168x168.png">
Windows 上的贴片图标
<!-- Add to home screen for start menu on Windows -->
<meta name="msapplication-TileImage" content="./images/icon/168x168.png">
<meta name="msapplication-TileColor" content="#6f6f6f">
至此，APP开发完成，你可以把他发布到服务器上进行验证啦！
地址：https://zr.zkbhj.com/
【援引】
https://developers.google.com/web/fundamentals/getting-started/codelabs/your-first-pwapp/
https://www.w3cplus.com/pwa/your-first-pwapp.html
查看全部
互联网研发部官方APP（PWA版）：ziroom.zkbhj.com
那既然要用到这个进行开发，首先需要了解什么是PWA，以及开发还需要学习和熟悉哪些相关的知识技术。
一、什么是PWA？
Progressive Web Apps 是结合了 Web 和 原生应用中最好功能的一种体验。对于首次访问的用户它是非常有利的, 用户可以直接在浏览器中进行访问，不需要安装应用。随着时间的推移当用户渐渐地和应用建立了联系，它将变得越来越强大。它能够快速地加载，即使在比较糟糕的网络环境下，能够推送相关消息, 也可以像原生应用那样添加至主屏，能够有全屏浏览的体验。
渐进增强 - 能够让每一位用户使用，无论用户使用什么浏览器，因为它是始终以渐进增强为原则。响应式用户界面 - 适应任何环境：桌面电脑，智能手机，笔记本电脑，或者其他设备。不依赖网络连接 - 通过 service workers 可以在离线或者网速极差的环境下工作。类原生应用 - 有像原生应用般的交互和导航给用户原生应用般的体验，因为它是建立在 app shell model 上的。持续更新 - 受益于 service worker 的更新进程，应用能够始终保持更新。安全 - 通过 HTTPS 来提供服务来防止网络窥探，保证内容不被篡改。可发现 - 得益于 W3C manifests 元数据和 service worker 的登记，让搜索引擎能够找到 web 应用。再次访问 - 通过消息推送等特性让用户再次访问变得容易。可安装 - 允许用户保留对他们有用的应用在主屏幕上，不需要通过应用商店。可连接性 - 通过 URL 可以轻松分享应用，不用复杂的安装即可运行。
本次开发实践是根据官方的引导指南一步步完成自己的 Progressive Web App，包括设计时需要考虑的因素，也包括实现细节，以确保应用程序符合 Progressive Web App 的关键原则。官方指南的地址在文末有附加。
需要注意的是：PWA类型的应用，处于安全考虑，只能允许使用HTTPS协议，如果是非HTTPS加密协议，会报错，虽然能够正常浏览页面，但是核心功能已经失效。Uncaught (in promise) DOMException: Only secure origins are allowed (see: https@//goo.gl/Y0ZkNV).
那么本次开发实践，我们将要学会以下几点：
如何使用 "app shell" 的方法来设计和构建应用程序。如何让你的应用程序能够离线工作。如何存储数据以在离线时使用。
在我们正式开始我们的开发之前，需要熟知以下几个概念：
什么是应用外壳(App Shell)
App Shell是应用的用户界面所需的最基本的 HTML、CSS 和 JavaScript，也是一个用来确保应用有好多性能的组件。它的首次加载将会非常快，加载后立刻被缓存下来。这意味着应用的外壳不需要每次使用时都被下载，而是只加载需要的数据。
应用外壳的结构分为应用的核心基础组件和承载数据的 UI。所有的 UI 和基础组件都使用一个 service worker 缓存在本地，因此在后续的加载中 Progressive Web App 仅需要加载需要的数据，而不是加载所有的内容。换句话说，应用的壳相当于那些发布到应用商店的原生应用中打包的代码。它是让你的应用能够运行的核心组件，只是没有包含数据。
为什么使用基于应用外壳的结构?
使用基于应用外壳的结构允许你专注于速度，给你的 Progressive Web App 和原生应用相似的属性：快速的加载和灵活的更新，所有这些都不需要用到应用商店。
如何设计应用的外壳？
第一步是设计核心组件
首先我们要问问自己：
需要立刻显示什么在屏幕上？我们的应用需要那些关键的 UI 组件？应用外壳需要那些资源？比如图片，JavaScript，样式表等等。
我们将要创建一个部门给大家用的一个 Progressive Web App 。可能包含的功能比如可以展示我们部门人员的信息，值班表信息，项目列表信息等，基于需求，那么这个APP的核心组件包括：
一个基础的UI架构，菜单，页面中会要用到的基本元素，以及这些相关依赖的js文件、css样式表和图片等。
当然这个UI框架有很多种选择，官方推荐的是Web Starter Kit。 ，GIT地址为：https://github.com/google/web-starter-kit
由于我们的目的并不是要做一个功能多复杂的APP，我们的目的是要通过这个简单APP的开发了解和学会PWA的相关知识。
开发正式开始，首先，我们需要创建一个index.html文件，把我们设计的核心组件的代码都填进去。当然还有相关依赖的js文件、css样式表和图片等。
到这里我们的外壳已经有了，接下来，就是要把他启动起来！
在启动代码中，我们将包括(你可以在(js/app.js)的文件夹中找到)。看完了代码结构，我们要认识一个比较牛逼的东西！
使用 Service Workers 来预缓存应用外壳
Progressive Web Apps 是快速且可安装的，这意味着它能在在线、离线、断断续续或者缓慢的网络环境下使用。为了实现这个目标，我们需要使用一个 service worker 来缓存应用外壳，以保证它能始终迅速可用且可靠。详细了解Service Worker是什么，可以访问这篇文章来详细了解：https://developers.google.com/web/fundamentals/getting-started/primers/service-workers
service workers 提供的是一种应该被理解为渐进增强的特性，这些特性仅仅作用于支持service workers 的浏览器。比如，使用 service workers 你可以缓存应用外壳和你的应用所需的数据，所以这些数据在离线的环境下依然可以获得。如果浏览器不支持 service workers ，支持离线的 代码没有工作，用户也能得到一个基本的用户体验。使用特性检测来渐渐增强有一些小的开销，它不会在老旧的不支持 service workers 的浏览器中产生破坏性影响。
注册 service worker
为了让应用离线工作，要做的第一件事是注册一个 service worker，一段允许在后台运行的脚本，不需要 用户打开 web 页面，也不需要其他交互。
这只需要简单两步：
创建一个 JavaScript 文件作为 service worker告诉浏览器注册这个 JavaScript 文件为 service worker
第一步，在你的应用根目录下创建一个空文件叫做 serviceworker.js 。这个 serviceworker.js 文件必须放在跟目录，因为 service workers 的作用范围是根据其在目录结构中的位置决定的。
接下来，我们需要检查浏览器是否支持 service workers，如果支持，就注册 service worker，将下面代码添加至 app.js中。//首先判断浏览器是否支持，如果支持，就注册serviceWorker
if ('serviceWorker' in navigator) {
navigator.serviceWorker
.register('./serviceworker.js')
.then(function() { console.log('Service Worker Registered'); });
}缓存站点的资源
当 service worker 被注册以后，当用户首次访问页面的时候一个 install 事件会被触发。在这个事件的回调函数中，我们能够缓存所有的应用需要再次用到的资源。//定义缓存名称
//缓存名允许我们给缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存
var cacheName = 'pwa-ziroom-php-v4';
//设置需要缓存的文件
var filesToCache = [
'./',
'./css/style.css',
*
];
self.addEventListener('install', function(event) {
console.log('Service Worker: Installing....');
event.waitUntil(
//打开缓存
caches.open(cacheName).then(function(cache) {
console.log('Service Worker: Caching App Shell at the moment......');
return cache.addAll(filesToCache);
})
);
});首先，我们需要提供一个缓存的名字并利用 caches.open()打开 cache 对象。提供的缓存名允许我们给 缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存。
一旦缓存被打开，我们可以调用 cache.addAll() 并传入一个 url 列表，然后加载这些资源并将响应添加至缓存。不幸的是 cache.addAll() 是原子操作，如果某个文件缓存失败了，那么整个缓存就会失败！
ok，到现在我们已经将要缓存的文件缓存到本地了，但是我们的应用目前还不能离线工作。我们缓存了 app shell 的组件，但是我们仍然需要从本地缓存中加载它们。
从缓存中加载 app sheel
Service workers 可以截获 Progressive Web App 发起的请求并从缓存中返回响应。这意味着我们能够 决定如何来处理这些请求，以及决定哪些网络响应能够成为我们的缓存。
self.addEventListener('fetch', function(event) {
console.log('Service Worker: Fetch', event.request.url);
console.log("Url", event.request.url);
event.respondWith(
caches.match(event.request).then(function(response) {
return response || fetch(event.request);
})
);
});从内至外，caches.match() 从网络请求触发的 fetch 事件中得到请求内容，并判断请求的资源是 否存在于缓存中。然后以缓存中的内容作为响应，或者使用 fetch 函数来加载资源（如果缓存中没有该资源）。 response 最后通过 e.respondWith() 返回给 Web 页面。
使用 manifest.json 文件来声明一个应用程序清单
Web 应用程序清单是一个简单的 JSON 文件，它给你了控制你的应用如何出现在用户期待出现的地方（比如用户手机主屏幕），这直接影响到用户能启动什么，以及更重要的，用户如何启动它。
使用 web 应用程序清单，你的应用可以：
能够真实存在于用户主屏幕上在 Android 上能够全屏启动，不显示地址栏控制屏幕方向已获得最佳效果定义启动画面，为你的站点定义主题追踪你的应用是从主屏幕还是 URL 启动的
告诉浏览器你的程序清单文件
将这段代码添加至你的 index.html 的 <head> 部分：<link rel="manifest" href="./manifest.json">一些最佳实践
将程序清单的链接添加至你站点的所有页面上，这样在用户第一次访问的时候它能够被 Chrome 正确检索到，且不管用户从哪个页面访问的。如果同时提供了 name 和 short_name，short_name 是 Chrome 的首选。为不同分辨率的屏幕提供不同的 icon。Chrome 会尝试使用最接近 48dp 的图标，比如在 2x 屏上使用 96px 的，在 3x屏上使用 144px 的。记得要包含一个适合在启动画面上显示的图标，另外别忘了设置 background_color。
iOS Safari 的添加至主屏幕元素<!-- Add to home screen for Safari on iOS -->
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="apple-mobile-web-app-title" content="ZiPHP">
<link rel="apple-touch-icon" href="./images/icon/168x168.png">
Windows 上的贴片图标
<!-- Add to home screen for start menu on Windows -->
<meta name="msapplication-TileImage" content="./images/icon/168x168.png">
<meta name="msapplication-TileColor" content="#6f6f6f">
至此，APP开发完成，你可以把他发布到服务器上进行验证啦！
地址：https://zr.zkbhj.com/
【援引】
https://developers.google.com/web/fundamentals/getting-started/codelabs/your-first-pwapp/
https://www.w3cplus.com/pwa/your-first-pwapp.html
查看全部
这两天正值谷歌开发者大会在上海召开，（谷歌开发者大会2017官网）。朋友圈中出现了一条大会上关于PWA的状态，恰巧丽姐也我和说到了pwa应该学一学。这就勾起了我对这个pwa到底是啥的好奇心。丽姐说，那就先做一个咱们部门自己的APP呗，一期可以只上个值班表。嗯，起源就是这样。
互联网研发部官方APP（PWA版）：ziroom.zkbhj.com
那既然要用到这个进行开发，首先需要了解什么是PWA，以及开发还需要学习和熟悉哪些相关的知识技术。
一、什么是PWA？
Progressive Web Apps 是结合了 Web 和 原生应用中最好功能的一种体验。对于首次访问的用户它是非常有利的, 用户可以直接在浏览器中进行访问，不需要安装应用。随着时间的推移当用户渐渐地和应用建立了联系，它将变得越来越强大。它能够快速地加载，即使在比较糟糕的网络环境下，能够推送相关消息, 也可以像原生应用那样添加至主屏，能够有全屏浏览的体验。
- 渐进增强 - 能够让每一位用户使用，无论用户使用什么浏览器，因为它是始终以渐进增强为原则。
- 响应式用户界面 - 适应任何环境：桌面电脑，智能手机，笔记本电脑，或者其他设备。
- 不依赖网络连接 - 通过 service workers 可以在离线或者网速极差的环境下工作。
- 类原生应用 - 有像原生应用般的交互和导航给用户原生应用般的体验，因为它是建立在 app shell model 上的。
- 持续更新 - 受益于 service worker 的更新进程，应用能够始终保持更新。
- 安全 - 通过 HTTPS 来提供服务来防止网络窥探，保证内容不被篡改。
- 可发现 - 得益于 W3C manifests 元数据和 service worker 的登记，让搜索引擎能够找到 web 应用。
- 再次访问 - 通过消息推送等特性让用户再次访问变得容易。
- 可安装 - 允许用户保留对他们有用的应用在主屏幕上，不需要通过应用商店。
- 可连接性 - 通过 URL 可以轻松分享应用，不用复杂的安装即可运行。
本次开发实践是根据官方的引导指南一步步完成自己的 Progressive Web App，包括设计时需要考虑的因素，也包括实现细节，以确保应用程序符合 Progressive Web App 的关键原则。官方指南的地址在文末有附加。
需要注意的是：PWA类型的应用，处于安全考虑，只能允许使用HTTPS协议，如果是非HTTPS加密协议，会报错，虽然能够正常浏览页面，但是核心功能已经失效。
Uncaught (in promise) DOMException: Only secure origins are allowed (see: https@//goo.gl/Y0ZkNV).
那么本次开发实践，我们将要学会以下几点：
- 如何使用 "app shell" 的方法来设计和构建应用程序。
- 如何让你的应用程序能够离线工作。
- 如何存储数据以在离线时使用。
在我们正式开始我们的开发之前，需要熟知以下几个概念：
什么是应用外壳(App Shell)
App Shell是应用的用户界面所需的最基本的 HTML、CSS 和 JavaScript，也是一个用来确保应用有好多性能的组件。它的首次加载将会非常快，加载后立刻被缓存下来。这意味着应用的外壳不需要每次使用时都被下载，而是只加载需要的数据。
应用外壳的结构分为应用的核心基础组件和承载数据的 UI。所有的 UI 和基础组件都使用一个 service worker 缓存在本地，因此在后续的加载中 Progressive Web App 仅需要加载需要的数据，而不是加载所有的内容。换句话说，应用的壳相当于那些发布到应用商店的原生应用中打包的代码。它是让你的应用能够运行的核心组件，只是没有包含数据。
为什么使用基于应用外壳的结构?
使用基于应用外壳的结构允许你专注于速度，给你的 Progressive Web App 和原生应用相似的属性：快速的加载和灵活的更新，所有这些都不需要用到应用商店。
如何设计应用的外壳？
第一步是设计核心组件
首先我们要问问自己：
- 需要立刻显示什么在屏幕上？
- 我们的应用需要那些关键的 UI 组件？
- 应用外壳需要那些资源？比如图片，JavaScript，样式表等等。
我们将要创建一个部门给大家用的一个 Progressive Web App 。可能包含的功能比如可以展示我们部门人员的信息，值班表信息，项目列表信息等，基于需求，那么这个APP的核心组件包括：
一个基础的UI架构，菜单，页面中会要用到的基本元素，以及这些相关依赖的js文件、css样式表和图片等。
当然这个UI框架有很多种选择，官方推荐的是Web Starter Kit。 ，GIT地址为：https://github.com/google/web-starter-kit
由于我们的目的并不是要做一个功能多复杂的APP，我们的目的是要通过这个简单APP的开发了解和学会PWA的相关知识。
开发正式开始，首先，我们需要创建一个index.html文件，把我们设计的核心组件的代码都填进去。当然还有相关依赖的js文件、css样式表和图片等。
到这里我们的外壳已经有了，接下来，就是要把他启动起来！
在启动代码中，我们将包括(你可以在(js/app.js)的文件夹中找到)。看完了代码结构，我们要认识一个比较牛逼的东西！
使用 Service Workers 来预缓存应用外壳
Progressive Web Apps 是快速且可安装的，这意味着它能在在线、离线、断断续续或者缓慢的网络环境下使用。为了实现这个目标，我们需要使用一个 service worker 来缓存应用外壳，以保证它能始终迅速可用且可靠。详细了解Service Worker是什么，可以访问这篇文章来详细了解：https://developers.google.com/web/fundamentals/getting-started/primers/service-workers
service workers 提供的是一种应该被理解为渐进增强的特性，这些特性仅仅作用于支持service workers 的浏览器。比如，使用 service workers 你可以缓存应用外壳和你的应用所需的数据，所以这些数据在离线的环境下依然可以获得。如果浏览器不支持 service workers ，支持离线的 代码没有工作，用户也能得到一个基本的用户体验。使用特性检测来渐渐增强有一些小的开销，它不会在老旧的不支持 service workers 的浏览器中产生破坏性影响。
注册 service worker
为了让应用离线工作，要做的第一件事是注册一个 service worker，一段允许在后台运行的脚本，不需要 用户打开 web 页面，也不需要其他交互。
这只需要简单两步：
- 创建一个 JavaScript 文件作为 service worker
- 告诉浏览器注册这个 JavaScript 文件为 service worker
第一步，在你的应用根目录下创建一个空文件叫做 serviceworker.js 。这个 serviceworker.js 文件必须放在跟目录，因为 service workers 的作用范围是根据其在目录结构中的位置决定的。
接下来，我们需要检查浏览器是否支持 service workers，如果支持，就注册 service worker，将下面代码添加至 app.js中。
//首先判断浏览器是否支持，如果支持，就注册serviceWorker缓存站点的资源
if ('serviceWorker' in navigator) {
navigator.serviceWorker
.register('./serviceworker.js')
.then(function() { console.log('Service Worker Registered'); });
}
当 service worker 被注册以后，当用户首次访问页面的时候一个 install 事件会被触发。在这个事件的回调函数中，我们能够缓存所有的应用需要再次用到的资源。
//定义缓存名称首先，我们需要提供一个缓存的名字并利用 caches.open()打开 cache 对象。提供的缓存名允许我们给 缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存。
//缓存名允许我们给缓存的文件添加版本，或者将数据分开，以至于我们能够轻松地升级数据而不影响其他的缓存
var cacheName = 'pwa-ziroom-php-v4';
//设置需要缓存的文件
var filesToCache = [
'./',
'./css/style.css',
*
];
self.addEventListener('install', function(event) {
console.log('Service Worker: Installing....');
event.waitUntil(
//打开缓存
caches.open(cacheName).then(function(cache) {
console.log('Service Worker: Caching App Shell at the moment......');
return cache.addAll(filesToCache);
})
);
});
一旦缓存被打开，我们可以调用 cache.addAll() 并传入一个 url 列表，然后加载这些资源并将响应添加至缓存。不幸的是 cache.addAll() 是原子操作，如果某个文件缓存失败了，那么整个缓存就会失败！
ok，到现在我们已经将要缓存的文件缓存到本地了，但是我们的应用目前还不能离线工作。我们缓存了 app shell 的组件，但是我们仍然需要从本地缓存中加载它们。
从缓存中加载 app sheel
Service workers 可以截获 Progressive Web App 发起的请求并从缓存中返回响应。这意味着我们能够 决定如何来处理这些请求，以及决定哪些网络响应能够成为我们的缓存。
self.addEventListener('fetch', function(event) {
console.log('Service Worker: Fetch', event.request.url);
console.log("Url", event.request.url);
event.respondWith(
caches.match(event.request).then(function(response) {
return response || fetch(event.request);
})
);
});从内至外，caches.match() 从网络请求触发的 fetch 事件中得到请求内容，并判断请求的资源是 否存在于缓存中。然后以缓存中的内容作为响应，或者使用 fetch 函数来加载资源（如果缓存中没有该资源）。 response 最后通过 e.respondWith() 返回给 Web 页面。使用 manifest.json 文件来声明一个应用程序清单
Web 应用程序清单是一个简单的 JSON 文件，它给你了控制你的应用如何出现在用户期待出现的地方（比如用户手机主屏幕），这直接影响到用户能启动什么，以及更重要的，用户如何启动它。
使用 web 应用程序清单，你的应用可以：
- 能够真实存在于用户主屏幕上
- 在 Android 上能够全屏启动，不显示地址栏
- 控制屏幕方向已获得最佳效果
- 定义启动画面，为你的站点定义主题
- 追踪你的应用是从主屏幕还是 URL 启动的
告诉浏览器你的程序清单文件
将这段代码添加至你的 index.html 的 <head> 部分：
<link rel="manifest" href="./manifest.json">一些最佳实践
- 将程序清单的链接添加至你站点的所有页面上，这样在用户第一次访问的时候它能够被 Chrome 正确检索到，且不管用户从哪个页面访问的。
- 如果同时提供了 name 和 short_name，short_name 是 Chrome 的首选。
- 为不同分辨率的屏幕提供不同的 icon。Chrome 会尝试使用最接近 48dp 的图标，比如在 2x 屏上使用 96px 的，在 3x屏上使用 144px 的。
- 记得要包含一个适合在启动画面上显示的图标，另外别忘了设置 background_color。
iOS Safari 的添加至主屏幕元素
<!-- Add to home screen for Safari on iOS -->
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="apple-mobile-web-app-title" content="ZiPHP">
<link rel="apple-touch-icon" href="./images/icon/168x168.png">
Windows 上的贴片图标
<!-- Add to home screen for start menu on Windows -->
<meta name="msapplication-TileImage" content="./images/icon/168x168.png">
<meta name="msapplication-TileColor" content="#6f6f6f">
至此，APP开发完成，你可以把他发布到服务器上进行验证啦！
地址：https://zr.zkbhj.com/
【援引】
https://developers.google.com/web/fundamentals/getting-started/codelabs/your-first-pwapp/
https://www.w3cplus.com/pwa/your-first-pwapp.html
凯冰科技开源分享：凯冰音乐音乐平台歌曲解析之虾米音乐
zkbhj 发表了文章 • 0 个评论 • 1906 次浏览 • 2017-12-05 11:13
凯冰音乐（music.zkbhj.com）是凯冰科技旗下一个音乐类型的APP，主要解决了目前音乐市场歌曲版权分散，无法集中欣赏自己喜欢的音乐的问题而开发的。截止目前，已经可以对酷狗音乐、酷我音乐、虾米音乐、QQ音乐、网易云音乐和咪咕音乐六大主流音乐平台的歌曲解析。今天把这几个当中比较有意思的一个“破解解析”之路分享给大家，那就是虾米音乐。（记不记得前几天网上比较火的那个“穷逼VIP”，哈哈哈，就是出自阿里虾米音乐程序员之手！）。
言归正传，步入正题！
首先，破解虾米音乐的歌曲地址需要了解以下一些概念：
1、动态歌曲地址（所有音乐平台的歌曲地址都不是固定不变的，每一次请求的url都是经过计算甚至加密的）；
2、恺撒加密，这个是虾米音乐使用的一种加密混淆方式，这也是我把他拿出来给大家分享的原因，比较有意思，破解难度稍高！
在密码学中，恺撒密码是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。
古罗马皇帝凯撒在打仗时曾经使用过以下方法加密军事情报，下面这张图加密方法就是错三个位来实现加密功能。
好了，开始整个破解过程！
首先，按照套路，我们需要观察虾米音乐的PC端播放器，在播放歌曲的时候，音乐文件的url是怎么获取到的。这个很简单，一个F12即可！
先来搜一首我的邓紫棋的一首歌曲，点击进入详情页，嗯，这个时候你会发现url中有一个数字，这个很重要，是这首歌曲的id，下面是要用得到的。
点击播放，进入PC版播放器界面，熟悉的音乐传来，按下F12，过滤掉其他无用的请求信息，只留下XHR类型的请求，你会发现第一个就是你想要的。没错，就是他！
来看一下请求地址：Request URL:http://www.xiami.com/song/play ... np670
Request Method:GET熟悉不？是个jsonp请求。里面用到了刚刚提到的那个id。当然，这个url地址你是无法直接请求的，因为做了refer来源的判断，只有*.xiami.com的来源请求才会被应答，否则是404。
ok，再看下返回结果。{
"status":true,
"message":null,
"data":{
"trackList":[
{
"songId":"1770016497",
"songName":"A.I.N.Y. (爱你)",
"subName":"",
"newSubName":"",
"translation":"",
"albumId":424082,
"artistId":55712,
"singers":"G.E.M.邓紫棋",
"mvId":489278,
"cdSerial":1,
"track":9,
"pinyin":"A.I.N.Y. (ai ni )",
"bakSongId":0,
"panFlag":0,
"musicType":"NORMAL",
"bakSong":null,
"lyricInfo":{
"lyricId":10064461,
"lyricType":3,
"lyricFile":"http://img.xiami.net/lyric/97/ ... ot%3B,
"isOfficial":true
},
"songwriters":"",
"composer":"",
"arrangement":"",
"boughtCount":0,
"pace":140,
"albumLanguage":"国语",
"playCount":2875407,
"offline":false,
"downloadCount":false,
"originOffline":false,
"exclusive":false,
"bizTags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"recommendCount":811,
"collectCount":7657,
"songStringId":"xLsLMvc02a4",
"albumStringId":"kkCgaa42a",
"artistStringId":"be6yda0f8",
"singerIds":[
55712
],
"demoCreateTime":1340847262000,
"tags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"offLyric":false,
"artist":"G.E.M.邓紫棋",
"songOpt":"NORMAL",
"purviews":{
"LISTEN":{
"LOW":"FREE",
"HIGH":"FREE"
},
"DOWNLOAD":{
"LOW":"FREE",
"HIGH":"FREE"
}
},
"publishStatus":"PUBLISH",
"demo":false,
"s":2875407,
"song_id":"1770016497",
"album_id":424082,
"name":"A.I.N.Y. (爱你)",
"title":"A.I.N.Y. 爱你",
"album_name":"A.I.N.Y. 爱你",
"sub_title":"",
"new_sub_title":"",
"song_sub_title":"",
"artist_name":"G.E.M.邓紫棋",
"artist_id":55712,
"cd_serial":1,
"singersSource":[
{
"artistId":55712,
"artistStringId":"be6yda0f8",
"artistName":"G.E.M.邓紫棋",
"artistLogo":"images/artistlogo/23/14578645251123_1.jpg",
"albumCount":28,
"area":"Hongkong 香港",
"alias":"邓紫棋 / 邓诗颖",
"pinyin":"G.E.M.deng zi qi ",
"isMusician":false,
"isShow":false,
"description":""
}
],
"length":224,
"recommends":811,
"collects":7657,
"key_words":null,
"music_type":0,
"play_volume":89,
"flag":null,
"album_logo":"images/album/img12/55712/4240821466497268_1.jpg",
"needpay":0,
"mvUrl":"K6YhbP",
"playstatus":1,
"downloadstatus":1,
"downloadjson":"%7B%22LOW%22%3A%22FREE%22%2C%22HIGH%22%3A%22FREE%22%7D",
"can_show":1,
"can_check":1,
"location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",
"lyric":"http://img.xiami.net/lyric/97/ ... ot%3B,
"lyric_url":"http://img.xiami.net/lyric/97/ ... ot%3B,
"object_id":"1770016497",
"object_name":"default",
"insert_type":1,
"background":"http://img.xiami.net/res/playe ... ot%3B,
"aritst_type":"",
"artist_url":"http://www.xiami.com/artist/55712",
"grade":-1,
"tryhq":0,
"pic":"http://img.xiami.net/images/al ... ot%3B,
"album_pic":"http://img.xiami.net/images/al ... ot%3B,
"rec_note":""
}
],
"lastSongId":0,
"type":"default",
"type_id":1,
"clearlist":null,
"vip":0,
"vip_role":0,
"hqset":0
},
"jumpurl":null
}
失望！接口并没有直接返回音频文件的地址，而是返回了一个下面这样的东东："location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",没错，它是这首歌曲这次请求返回对的音频文件地址，拿来用肯定是不行的，那我该怎么办！
现在遇到了两个问题：
1、获取地址的接口没办法直接调用；
2、返回的音频地址经过了加密处理，没办法直接使用。
还好，虾米音乐有些场景还是需要直接调的，比如外链播放器、甚至是APP客户端等，所以能够直接获取歌曲信息的接口找到了，可用的有以下两个：http@//www.xiami.com/widget/xml-single/sid/1770016497
http@//www.xiami.com/widget/json-single/sid/1770016497
他们分别返回的格式有xml和json两种，我们选择第一种来看看，（json太简单了，而且试过了，有些歌曲没有数据返回）好了，第一个问题解决了，那么来第二个问题：如何把加密后的结果还原成可以正常访问的音频文件地址！还好，它用了加密算法领域最简单的恺撒加密，只要按照规律就可以轻松破解。
用类似于恺撒方阵把链接的第一个数字去掉然后前两行分为21个字符，后六行分为20个字符排列：h28n557%45E.u3E553513
tF.e%%826E1mtD4EEbf92
t%xt22%F593ph17--5%87
p2i%FF532%93_56%de58e
%Fa253E4_57%k1%556E3f
3mmF6%%%1E83e35E%58f6
A1i115555%7Fy%E-5f7ae
%2.33EEE%54a%5%%Ea79你会发现从左边开始竖着往下拼起来类似于音乐链接了：http%3A%2F%2Fm128.xiami.net%2F135%2F56135%2F3%5E78%5E%5E%2F34%5E4652_15%5E9%5E%5E1397874.mp3%3Fauth_key%3D1513%5E476%5E%5E-%5E-%5E-d5%5E3b5e65fa5f%5E87719883fa9327ef6e把这条链接UrlDecode解码一下得到：http://m128.xiami.net/135/56135/3^78^^/34^4652_15^9^^1397874.mp3?auth_key=1513^476^^-^-^-d5^3b5e65fa5f^87719883fa9327ef6e然后把^字符替换成0得到：http://m128.xiami.net/135/56135/307800/3404652_1509001397874.mp3?auth_key=1513047600-0-0-d503b5e65fa5f087719883fa9327ef6e
好了，这个就是我们最终想要的音频文件地址，拿来可以直接用了！
bingo，到此为止，解析结束。
PHP实现的代码如下：<?php
/*
虾米音乐音频文件地址解密算法，凯撒数列加密方式。
*/
namespace Org\Util;
class XiaMiMusic
{
public function decode($t) {
$l = substr($t, 0, 1);
$t = substr($t, 1);
$tn = strlen($t);
$ln = floor($tn / $l);
$r = $tn % $l;
$tex = str_split($t);
$text = '';
for ($i = 0;$i <= $ln;$i++) {
for ($j = 0;$j < $l;$j++) {
$n = $j * $ln + $i;
if ($j < $r) $n+= $j;
else $n+= $r;
if (isset($tex[$n])) $text.= $tex[$n];
else break;
}
}
$preg = array('^', '%');
$replace = array(0, '|');
return str_replace($preg, $replace, urldecode(substr($text, 0, $tn)));
}
public function getMusicUrl($id)
{
if($id){
$xml = file_get_contents('http://www.xiami.com/widget/xml-single/uid/0/sid/'.$id);
//匹配location内容
preg_match("/<\!\[CDATA\[([^\]].*)\]\]><\/location>/i",$xml,$location);
//转码得到正确的地址
return (string)$this->decode($location[1]);
}else{
return "";
}
}
}
$a = new xiamiMusic();
echo $a->getMusicUrl(1770016497);
好了，来听听这首《爱你A.I.N.Y》吧（实际这首歌曲解析来自QQ音乐平台，下次再分享这个喽，嘿嘿）！http://music.zkbhj.com/?goto=listen&id=646
查看全部
言归正传，步入正题！
首先，破解虾米音乐的歌曲地址需要了解以下一些概念：
1、动态歌曲地址（所有音乐平台的歌曲地址都不是固定不变的，每一次请求的url都是经过计算甚至加密的）；
2、恺撒加密，这个是虾米音乐使用的一种加密混淆方式，这也是我把他拿出来给大家分享的原因，比较有意思，破解难度稍高！
在密码学中，恺撒密码是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。
古罗马皇帝凯撒在打仗时曾经使用过以下方法加密军事情报，下面这张图加密方法就是错三个位来实现加密功能。
好了，开始整个破解过程！
首先，按照套路，我们需要观察虾米音乐的PC端播放器，在播放歌曲的时候，音乐文件的url是怎么获取到的。这个很简单，一个F12即可！
先来搜一首我的邓紫棋的一首歌曲，点击进入详情页，嗯，这个时候你会发现url中有一个数字，这个很重要，是这首歌曲的id，下面是要用得到的。
点击播放，进入PC版播放器界面，熟悉的音乐传来，按下F12，过滤掉其他无用的请求信息，只留下XHR类型的请求，你会发现第一个就是你想要的。没错，就是他！
来看一下请求地址：Request URL:http://www.xiami.com/song/play ... np670
Request Method:GET熟悉不？是个jsonp请求。里面用到了刚刚提到的那个id。当然，这个url地址你是无法直接请求的，因为做了refer来源的判断，只有*.xiami.com的来源请求才会被应答，否则是404。
ok，再看下返回结果。{
"status":true,
"message":null,
"data":{
"trackList":[
{
"songId":"1770016497",
"songName":"A.I.N.Y. (爱你)",
"subName":"",
"newSubName":"",
"translation":"",
"albumId":424082,
"artistId":55712,
"singers":"G.E.M.邓紫棋",
"mvId":489278,
"cdSerial":1,
"track":9,
"pinyin":"A.I.N.Y. (ai ni )",
"bakSongId":0,
"panFlag":0,
"musicType":"NORMAL",
"bakSong":null,
"lyricInfo":{
"lyricId":10064461,
"lyricType":3,
"lyricFile":"http://img.xiami.net/lyric/97/ ... ot%3B,
"isOfficial":true
},
"songwriters":"",
"composer":"",
"arrangement":"",
"boughtCount":0,
"pace":140,
"albumLanguage":"国语",
"playCount":2875407,
"offline":false,
"downloadCount":false,
"originOffline":false,
"exclusive":false,
"bizTags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"recommendCount":811,
"collectCount":7657,
"songStringId":"xLsLMvc02a4",
"albumStringId":"kkCgaa42a",
"artistStringId":"be6yda0f8",
"singerIds":[
55712
],
"demoCreateTime":1340847262000,
"tags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"offLyric":false,
"artist":"G.E.M.邓紫棋",
"songOpt":"NORMAL",
"purviews":{
"LISTEN":{
"LOW":"FREE",
"HIGH":"FREE"
},
"DOWNLOAD":{
"LOW":"FREE",
"HIGH":"FREE"
}
},
"publishStatus":"PUBLISH",
"demo":false,
"s":2875407,
"song_id":"1770016497",
"album_id":424082,
"name":"A.I.N.Y. (爱你)",
"title":"A.I.N.Y. 爱你",
"album_name":"A.I.N.Y. 爱你",
"sub_title":"",
"new_sub_title":"",
"song_sub_title":"",
"artist_name":"G.E.M.邓紫棋",
"artist_id":55712,
"cd_serial":1,
"singersSource":[
{
"artistId":55712,
"artistStringId":"be6yda0f8",
"artistName":"G.E.M.邓紫棋",
"artistLogo":"images/artistlogo/23/14578645251123_1.jpg",
"albumCount":28,
"area":"Hongkong 香港",
"alias":"邓紫棋 / 邓诗颖",
"pinyin":"G.E.M.deng zi qi ",
"isMusician":false,
"isShow":false,
"description":""
}
],
"length":224,
"recommends":811,
"collects":7657,
"key_words":null,
"music_type":0,
"play_volume":89,
"flag":null,
"album_logo":"images/album/img12/55712/4240821466497268_1.jpg",
"needpay":0,
"mvUrl":"K6YhbP",
"playstatus":1,
"downloadstatus":1,
"downloadjson":"%7B%22LOW%22%3A%22FREE%22%2C%22HIGH%22%3A%22FREE%22%7D",
"can_show":1,
"can_check":1,
"location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",
"lyric":"http://img.xiami.net/lyric/97/ ... ot%3B,
"lyric_url":"http://img.xiami.net/lyric/97/ ... ot%3B,
"object_id":"1770016497",
"object_name":"default",
"insert_type":1,
"background":"http://img.xiami.net/res/playe ... ot%3B,
"aritst_type":"",
"artist_url":"http://www.xiami.com/artist/55712",
"grade":-1,
"tryhq":0,
"pic":"http://img.xiami.net/images/al ... ot%3B,
"album_pic":"http://img.xiami.net/images/al ... ot%3B,
"rec_note":""
}
],
"lastSongId":0,
"type":"default",
"type_id":1,
"clearlist":null,
"vip":0,
"vip_role":0,
"hqset":0
},
"jumpurl":null
}
失望！接口并没有直接返回音频文件的地址，而是返回了一个下面这样的东东："location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",没错，它是这首歌曲这次请求返回对的音频文件地址，拿来用肯定是不行的，那我该怎么办！
现在遇到了两个问题：
1、获取地址的接口没办法直接调用；
2、返回的音频地址经过了加密处理，没办法直接使用。
还好，虾米音乐有些场景还是需要直接调的，比如外链播放器、甚至是APP客户端等，所以能够直接获取歌曲信息的接口找到了，可用的有以下两个：http@//www.xiami.com/widget/xml-single/sid/1770016497
http@//www.xiami.com/widget/json-single/sid/1770016497
他们分别返回的格式有xml和json两种，我们选择第一种来看看，（json太简单了，而且试过了，有些歌曲没有数据返回）好了，第一个问题解决了，那么来第二个问题：如何把加密后的结果还原成可以正常访问的音频文件地址！还好，它用了加密算法领域最简单的恺撒加密，只要按照规律就可以轻松破解。
用类似于恺撒方阵把链接的第一个数字去掉然后前两行分为21个字符，后六行分为20个字符排列：h28n557%45E.u3E553513
tF.e%%826E1mtD4EEbf92
t%xt22%F593ph17--5%87
p2i%FF532%93_56%de58e
%Fa253E4_57%k1%556E3f
3mmF6%%%1E83e35E%58f6
A1i115555%7Fy%E-5f7ae
%2.33EEE%54a%5%%Ea79你会发现从左边开始竖着往下拼起来类似于音乐链接了：http%3A%2F%2Fm128.xiami.net%2F135%2F56135%2F3%5E78%5E%5E%2F34%5E4652_15%5E9%5E%5E1397874.mp3%3Fauth_key%3D1513%5E476%5E%5E-%5E-%5E-d5%5E3b5e65fa5f%5E87719883fa9327ef6e把这条链接UrlDecode解码一下得到：http://m128.xiami.net/135/56135/3^78^^/34^4652_15^9^^1397874.mp3?auth_key=1513^476^^-^-^-d5^3b5e65fa5f^87719883fa9327ef6e然后把^字符替换成0得到：http://m128.xiami.net/135/56135/307800/3404652_1509001397874.mp3?auth_key=1513047600-0-0-d503b5e65fa5f087719883fa9327ef6e
好了，这个就是我们最终想要的音频文件地址，拿来可以直接用了！
bingo，到此为止，解析结束。
PHP实现的代码如下：<?php
/*
虾米音乐音频文件地址解密算法，凯撒数列加密方式。
*/
namespace Org\Util;
class XiaMiMusic
{
public function decode($t) {
$l = substr($t, 0, 1);
$t = substr($t, 1);
$tn = strlen($t);
$ln = floor($tn / $l);
$r = $tn % $l;
$tex = str_split($t);
$text = '';
for ($i = 0;$i <= $ln;$i++) {
for ($j = 0;$j < $l;$j++) {
$n = $j * $ln + $i;
if ($j < $r) $n+= $j;
else $n+= $r;
if (isset($tex[$n])) $text.= $tex[$n];
else break;
}
}
$preg = array('^', '%');
$replace = array(0, '|');
return str_replace($preg, $replace, urldecode(substr($text, 0, $tn)));
}
public function getMusicUrl($id)
{
if($id){
$xml = file_get_contents('http://www.xiami.com/widget/xml-single/uid/0/sid/'.$id);
//匹配location内容
preg_match("/<\!\[CDATA\[([^\]].*)\]\]><\/location>/i",$xml,$location);
//转码得到正确的地址
return (string)$this->decode($location[1]);
}else{
return "";
}
}
}
$a = new xiamiMusic();
echo $a->getMusicUrl(1770016497);
好了，来听听这首《爱你A.I.N.Y》吧（实际这首歌曲解析来自QQ音乐平台，下次再分享这个喽，嘿嘿）！http://music.zkbhj.com/?goto=listen&id=646
查看全部
凯冰音乐（music.zkbhj.com）是凯冰科技旗下一个音乐类型的APP，主要解决了目前音乐市场歌曲版权分散，无法集中欣赏自己喜欢的音乐的问题而开发的。截止目前，已经可以对酷狗音乐、酷我音乐、虾米音乐、QQ音乐、网易云音乐和咪咕音乐六大主流音乐平台的歌曲解析。今天把这几个当中比较有意思的一个“破解解析”之路分享给大家，那就是虾米音乐。（记不记得前几天网上比较火的那个“穷逼VIP”，哈哈哈，就是出自阿里虾米音乐程序员之手！）。
言归正传，步入正题！
首先，破解虾米音乐的歌曲地址需要了解以下一些概念：
1、动态歌曲地址（所有音乐平台的歌曲地址都不是固定不变的，每一次请求的url都是经过计算甚至加密的）；
2、恺撒加密，这个是虾米音乐使用的一种加密混淆方式，这也是我把他拿出来给大家分享的原因，比较有意思，破解难度稍高！
好了，开始整个破解过程！
首先，按照套路，我们需要观察虾米音乐的PC端播放器，在播放歌曲的时候，音乐文件的url是怎么获取到的。这个很简单，一个F12即可！
先来搜一首我的邓紫棋的一首歌曲，点击进入详情页，嗯，这个时候你会发现url中有一个数字，这个很重要，是这首歌曲的id，下面是要用得到的。
点击播放，进入PC版播放器界面，熟悉的音乐传来，按下F12，过滤掉其他无用的请求信息，只留下XHR类型的请求，你会发现第一个就是你想要的。没错，就是他！
来看一下请求地址：
ok，再看下返回结果。
失望！接口并没有直接返回音频文件的地址，而是返回了一个下面这样的东东：
现在遇到了两个问题：
1、获取地址的接口没办法直接调用；
2、返回的音频地址经过了加密处理，没办法直接使用。
还好，虾米音乐有些场景还是需要直接调的，比如外链播放器、甚至是APP客户端等，所以能够直接获取歌曲信息的接口找到了，可用的有以下两个：
他们分别返回的格式有xml和json两种，我们选择第一种来看看，（json太简单了，而且试过了，有些歌曲没有数据返回）好了，第一个问题解决了，那么来第二个问题：如何把加密后的结果还原成可以正常访问的音频文件地址！还好，它用了加密算法领域最简单的恺撒加密，只要按照规律就可以轻松破解。
用类似于恺撒方阵把链接的第一个数字去掉然后前两行分为21个字符，后六行分为20个字符排列：
好了，这个就是我们最终想要的音频文件地址，拿来可以直接用了！
bingo，到此为止，解析结束。
PHP实现的代码如下：
好了，来听听这首《爱你A.I.N.Y》吧（实际这首歌曲解析来自QQ音乐平台，下次再分享这个喽，嘿嘿）！http://music.zkbhj.com/?goto=listen&id=646
言归正传，步入正题！
首先，破解虾米音乐的歌曲地址需要了解以下一些概念：
1、动态歌曲地址（所有音乐平台的歌曲地址都不是固定不变的，每一次请求的url都是经过计算甚至加密的）；
2、恺撒加密，这个是虾米音乐使用的一种加密混淆方式，这也是我把他拿出来给大家分享的原因，比较有意思，破解难度稍高！
在密码学中，恺撒密码是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。
古罗马皇帝凯撒在打仗时曾经使用过以下方法加密军事情报，下面这张图加密方法就是错三个位来实现加密功能。
好了，开始整个破解过程！
首先，按照套路，我们需要观察虾米音乐的PC端播放器，在播放歌曲的时候，音乐文件的url是怎么获取到的。这个很简单，一个F12即可！
先来搜一首我的邓紫棋的一首歌曲，点击进入详情页，嗯，这个时候你会发现url中有一个数字，这个很重要，是这首歌曲的id，下面是要用得到的。
点击播放，进入PC版播放器界面，熟悉的音乐传来，按下F12，过滤掉其他无用的请求信息，只留下XHR类型的请求，你会发现第一个就是你想要的。没错，就是他！
来看一下请求地址：
Request URL:http://www.xiami.com/song/play ... np670熟悉不？是个jsonp请求。里面用到了刚刚提到的那个id。当然，这个url地址你是无法直接请求的，因为做了refer来源的判断，只有*.xiami.com的来源请求才会被应答，否则是404。
Request Method:GET
ok，再看下返回结果。
{
"status":true,
"message":null,
"data":{
"trackList":[
{
"songId":"1770016497",
"songName":"A.I.N.Y. (爱你)",
"subName":"",
"newSubName":"",
"translation":"",
"albumId":424082,
"artistId":55712,
"singers":"G.E.M.邓紫棋",
"mvId":489278,
"cdSerial":1,
"track":9,
"pinyin":"A.I.N.Y. (ai ni )",
"bakSongId":0,
"panFlag":0,
"musicType":"NORMAL",
"bakSong":null,
"lyricInfo":{
"lyricId":10064461,
"lyricType":3,
"lyricFile":"http://img.xiami.net/lyric/97/ ... ot%3B,
"isOfficial":true
},
"songwriters":"",
"composer":"",
"arrangement":"",
"boughtCount":0,
"pace":140,
"albumLanguage":"国语",
"playCount":2875407,
"offline":false,
"downloadCount":false,
"originOffline":false,
"exclusive":false,
"bizTags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"recommendCount":811,
"collectCount":7657,
"songStringId":"xLsLMvc02a4",
"albumStringId":"kkCgaa42a",
"artistStringId":"be6yda0f8",
"singerIds":[
55712
],
"demoCreateTime":1340847262000,
"tags":[
"RI_A5YY",
"X_FREE",
"XN_BJ9QM"
],
"offLyric":false,
"artist":"G.E.M.邓紫棋",
"songOpt":"NORMAL",
"purviews":{
"LISTEN":{
"LOW":"FREE",
"HIGH":"FREE"
},
"DOWNLOAD":{
"LOW":"FREE",
"HIGH":"FREE"
}
},
"publishStatus":"PUBLISH",
"demo":false,
"s":2875407,
"song_id":"1770016497",
"album_id":424082,
"name":"A.I.N.Y. (爱你)",
"title":"A.I.N.Y. 爱你",
"album_name":"A.I.N.Y. 爱你",
"sub_title":"",
"new_sub_title":"",
"song_sub_title":"",
"artist_name":"G.E.M.邓紫棋",
"artist_id":55712,
"cd_serial":1,
"singersSource":[
{
"artistId":55712,
"artistStringId":"be6yda0f8",
"artistName":"G.E.M.邓紫棋",
"artistLogo":"images/artistlogo/23/14578645251123_1.jpg",
"albumCount":28,
"area":"Hongkong 香港",
"alias":"邓紫棋 / 邓诗颖",
"pinyin":"G.E.M.deng zi qi ",
"isMusician":false,
"isShow":false,
"description":""
}
],
"length":224,
"recommends":811,
"collects":7657,
"key_words":null,
"music_type":0,
"play_volume":89,
"flag":null,
"album_logo":"images/album/img12/55712/4240821466497268_1.jpg",
"needpay":0,
"mvUrl":"K6YhbP",
"playstatus":1,
"downloadstatus":1,
"downloadjson":"%7B%22LOW%22%3A%22FREE%22%2C%22HIGH%22%3A%22FREE%22%7D",
"can_show":1,
"can_check":1,
"location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",
"lyric":"http://img.xiami.net/lyric/97/ ... ot%3B,
"lyric_url":"http://img.xiami.net/lyric/97/ ... ot%3B,
"object_id":"1770016497",
"object_name":"default",
"insert_type":1,
"background":"http://img.xiami.net/res/playe ... ot%3B,
"aritst_type":"",
"artist_url":"http://www.xiami.com/artist/55712",
"grade":-1,
"tryhq":0,
"pic":"http://img.xiami.net/images/al ... ot%3B,
"album_pic":"http://img.xiami.net/images/al ... ot%3B,
"rec_note":""
}
],
"lastSongId":0,
"type":"default",
"type_id":1,
"clearlist":null,
"vip":0,
"vip_role":0,
"hqset":0
},
"jumpurl":null
}
失望！接口并没有直接返回音频文件的地址，而是返回了一个下面这样的东东：
"location":"8h28n557%45E.u3E553513tF.e%%826E1mtD4EEbf92t%xt22%F593ph17--5%87p2i%FF532%93_56%de58e%Fa253E4_57%k1%556E3f3mmF6%%%1E83e35E%58f6A1i115555%7Fy%E-5f7ae%2.33EEE%54a%5%%Ea79",没错，它是这首歌曲这次请求返回对的音频文件地址，拿来用肯定是不行的，那我该怎么办！
现在遇到了两个问题：
1、获取地址的接口没办法直接调用；
2、返回的音频地址经过了加密处理，没办法直接使用。
还好，虾米音乐有些场景还是需要直接调的，比如外链播放器、甚至是APP客户端等，所以能够直接获取歌曲信息的接口找到了，可用的有以下两个：
http@//www.xiami.com/widget/xml-single/sid/1770016497
http@//www.xiami.com/widget/json-single/sid/1770016497
他们分别返回的格式有xml和json两种，我们选择第一种来看看，（json太简单了，而且试过了，有些歌曲没有数据返回）好了，第一个问题解决了，那么来第二个问题：如何把加密后的结果还原成可以正常访问的音频文件地址！还好，它用了加密算法领域最简单的恺撒加密，只要按照规律就可以轻松破解。
用类似于恺撒方阵把链接的第一个数字去掉然后前两行分为21个字符，后六行分为20个字符排列：
h28n557%45E.u3E553513你会发现从左边开始竖着往下拼起来类似于音乐链接了：
tF.e%%826E1mtD4EEbf92
t%xt22%F593ph17--5%87
p2i%FF532%93_56%de58e
%Fa253E4_57%k1%556E3f
3mmF6%%%1E83e35E%58f6
A1i115555%7Fy%E-5f7ae
%2.33EEE%54a%5%%Ea79
http%3A%2F%2Fm128.xiami.net%2F135%2F56135%2F3%5E78%5E%5E%2F34%5E4652_15%5E9%5E%5E1397874.mp3%3Fauth_key%3D1513%5E476%5E%5E-%5E-%5E-d5%5E3b5e65fa5f%5E87719883fa9327ef6e把这条链接UrlDecode解码一下得到：
http://m128.xiami.net/135/56135/3^78^^/34^4652_15^9^^1397874.mp3?auth_key=1513^476^^-^-^-d5^3b5e65fa5f^87719883fa9327ef6e然后把^字符替换成0得到：
http://m128.xiami.net/135/56135/307800/3404652_1509001397874.mp3?auth_key=1513047600-0-0-d503b5e65fa5f087719883fa9327ef6e
好了，这个就是我们最终想要的音频文件地址，拿来可以直接用了！
bingo，到此为止，解析结束。
PHP实现的代码如下：
<?php
/*
虾米音乐音频文件地址解密算法，凯撒数列加密方式。
*/
namespace Org\Util;
class XiaMiMusic
{
public function decode($t) {
$l = substr($t, 0, 1);
$t = substr($t, 1);
$tn = strlen($t);
$ln = floor($tn / $l);
$r = $tn % $l;
$tex = str_split($t);
$text = '';
for ($i = 0;$i <= $ln;$i++) {
for ($j = 0;$j < $l;$j++) {
$n = $j * $ln + $i;
if ($j < $r) $n+= $j;
else $n+= $r;
if (isset($tex[$n])) $text.= $tex[$n];
else break;
}
}
$preg = array('^', '%');
$replace = array(0, '|');
return str_replace($preg, $replace, urldecode(substr($text, 0, $tn)));
}
public function getMusicUrl($id)
{
if($id){
$xml = file_get_contents('http://www.xiami.com/widget/xml-single/uid/0/sid/'.$id);
//匹配location内容
preg_match("/<\!\[CDATA\[([^\]].*)\]\]><\/location>/i",$xml,$location);
//转码得到正确的地址
return (string)$this->decode($location[1]);
}else{
return "";
}
}
}
$a = new xiamiMusic();
echo $a->getMusicUrl(1770016497);
好了，来听听这首《爱你A.I.N.Y》吧（实际这首歌曲解析来自QQ音乐平台，下次再分享这个喽，嘿嘿）！http://music.zkbhj.com/?goto=listen&id=646
2017自如技术大赛研发组题目七：单源最短路径算法问题
zkbhj 发表了文章 • 0 个评论 • 1888 次浏览 • 2017-12-04 00:08
7. 自如今年年底就会拥有50W间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电，家具等物品从仓库送到需要配置的每个房间。为了能在更多的时间配置更多的房子，我要不断的优化物流从仓库A到房间G的路径或者仓库B到房间E的距离，请写出一种算法给你任意图中两点，计算出两点之间的最短距离。
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法，迪科斯彻算法（Dijkstra），又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离。
*/
class Road {
//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",
);
//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);
//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);
//设置一个无穷大距离的数字
private $soBig = 999999;
private $path = array();
private function getOptimalPath($a, $b)
{
if($a == $b){
return "start and end could not be one point";
}
//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);
//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();
//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}
//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;
// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{
$current_min = $c[$v];
$current_min_v = $v;
}
}
//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);
//更新最短路径
foreach($others as $k=>$u)
{
if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{
$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];
}
}
}
$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];
return $c[$b]." ".$finalPath;
}
//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}
}
public function getResult($towPoint){
return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params); 查看全部
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法，迪科斯彻算法（Dijkstra），又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离。
*/
class Road {
//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",
);
//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);
//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);
//设置一个无穷大距离的数字
private $soBig = 999999;
private $path = array();
private function getOptimalPath($a, $b)
{
if($a == $b){
return "start and end could not be one point";
}
//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);
//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();
//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}
//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;
// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{
$current_min = $c[$v];
$current_min_v = $v;
}
}
//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);
//更新最短路径
foreach($others as $k=>$u)
{
if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{
$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];
}
}
}
$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];
return $c[$b]." ".$finalPath;
}
//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}
}
public function getResult($towPoint){
return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params); 查看全部
7. 自如今年年底就会拥有50W间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电，家具等物品从仓库送到需要配置的每个房间。为了能在更多的时间配置更多的房子，我要不断的优化物流从仓库A到房间G的路径或者仓库B到房间E的距离，请写出一种算法给你任意图中两点，计算出两点之间的最短距离。
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】
<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法，迪科斯彻算法（Dijkstra），又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离。
*/
class Road {
//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",
);
//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);
//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);
//设置一个无穷大距离的数字
private $soBig = 999999;
private $path = array();
private function getOptimalPath($a, $b)
{
if($a == $b){
return "start and end could not be one point";
}
//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);
//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();
//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}
//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;
// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{
$current_min = $c[$v];
$current_min_v = $v;
}
}
//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);
//更新最短路径
foreach($others as $k=>$u)
{
if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{
$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];
}
}
}
$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];
return $c[$b]." ".$finalPath;
}
//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}
}
public function getResult($towPoint){
return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params);
2017自如技术大赛研发组题目六：木木熊问题（类约瑟夫环问题）
zkbhj 发表了文章 • 0 个评论 • 1979 次浏览 • 2017-12-04 00:06
6. 每年夏季自如都会组织夏季夏令营活动，每年组委会都会给来京参加夏令营的小朋友准备好多礼物，今年也是如此。
组委会准备了一些小游戏来获得这些礼物，其中有一个游戏是这样的：组委会让小朋友围成一个圈。然后随机制定一个数e,让编号为0的小朋友开始报数。每次喊道e-1的小朋友直接出列，淘汰出局。从本次喊道e-1的下一个小朋友开始，继续从0报数...e-1淘汰出局...一直这样进行....最后进行到最后一个小朋友，这位小朋友可以拿到“熊帅”亲笔签名的“木木”熊毛绒玩具。
(注：小朋友的编号是从0到n-1)
示例：
输入：n=1314 e=520
输出：796
【PHP实现】
<?php
/**
* Created by PhpStorm.
* User: ZKBHJ
* Date: 2017/12/2
* Time: 18:14
*/
class Summer {
//小朋友总数
public $childCounts = 1314;
//小朋友围成的圈儿
public $childCircle = array();
//指定的随机数
public $e = 520;
//初始化围成一个圈儿
private function initCircle()
{
for($i = 0; $i< $this->childCounts; $i++){
$this->childCircle[$i] = $i;
}
}
private function findChild()
{
$index = 0;
for ($i = 2; $i <= $this->childCounts; $i ++) {
$index = ($index + $this->e) % $i;
}
return $index;
}
public function getResult()
{
$this->initCircle();
return $this->findChild();
}
}
//获取输入变量
$params = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
foreach($params as $k => $v){
$params[$k] = explode('=',$v);
}
$summer = new Summer();
$summer->childCounts = $params[0][1];
$summer->e = $params[1][1];
echo $summer->getResult(); 查看全部
组委会准备了一些小游戏来获得这些礼物，其中有一个游戏是这样的：组委会让小朋友围成一个圈。然后随机制定一个数e,让编号为0的小朋友开始报数。每次喊道e-1的小朋友直接出列，淘汰出局。从本次喊道e-1的下一个小朋友开始，继续从0报数...e-1淘汰出局...一直这样进行....最后进行到最后一个小朋友，这位小朋友可以拿到“熊帅”亲笔签名的“木木”熊毛绒玩具。
(注：小朋友的编号是从0到n-1)
示例：
输入：n=1314 e=520
输出：796
【PHP实现】
<?php
/**
* Created by PhpStorm.
* User: ZKBHJ
* Date: 2017/12/2
* Time: 18:14
*/
class Summer {
//小朋友总数
public $childCounts = 1314;
//小朋友围成的圈儿
public $childCircle = array();
//指定的随机数
public $e = 520;
//初始化围成一个圈儿
private function initCircle()
{
for($i = 0; $i< $this->childCounts; $i++){
$this->childCircle[$i] = $i;
}
}
private function findChild()
{
$index = 0;
for ($i = 2; $i <= $this->childCounts; $i ++) {
$index = ($index + $this->e) % $i;
}
return $index;
}
public function getResult()
{
$this->initCircle();
return $this->findChild();
}
}
//获取输入变量
$params = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
foreach($params as $k => $v){
$params[$k] = explode('=',$v);
}
$summer = new Summer();
$summer->childCounts = $params[0][1];
$summer->e = $params[1][1];
echo $summer->getResult(); 查看全部
6. 每年夏季自如都会组织夏季夏令营活动，每年组委会都会给来京参加夏令营的小朋友准备好多礼物，今年也是如此。
组委会准备了一些小游戏来获得这些礼物，其中有一个游戏是这样的：组委会让小朋友围成一个圈。然后随机制定一个数e,让编号为0的小朋友开始报数。每次喊道e-1的小朋友直接出列，淘汰出局。从本次喊道e-1的下一个小朋友开始，继续从0报数...e-1淘汰出局...一直这样进行....最后进行到最后一个小朋友，这位小朋友可以拿到“熊帅”亲笔签名的“木木”熊毛绒玩具。
(注：小朋友的编号是从0到n-1)
示例：
输入：n=1314 e=520
输出：796
【PHP实现】
组委会准备了一些小游戏来获得这些礼物，其中有一个游戏是这样的：组委会让小朋友围成一个圈。然后随机制定一个数e,让编号为0的小朋友开始报数。每次喊道e-1的小朋友直接出列，淘汰出局。从本次喊道e-1的下一个小朋友开始，继续从0报数...e-1淘汰出局...一直这样进行....最后进行到最后一个小朋友，这位小朋友可以拿到“熊帅”亲笔签名的“木木”熊毛绒玩具。
(注：小朋友的编号是从0到n-1)
示例：
输入：n=1314 e=520
输出：796
【PHP实现】
<?php
/**
* Created by PhpStorm.
* User: ZKBHJ
* Date: 2017/12/2
* Time: 18:14
*/
class Summer {
//小朋友总数
public $childCounts = 1314;
//小朋友围成的圈儿
public $childCircle = array();
//指定的随机数
public $e = 520;
//初始化围成一个圈儿
private function initCircle()
{
for($i = 0; $i< $this->childCounts; $i++){
$this->childCircle[$i] = $i;
}
}
private function findChild()
{
$index = 0;
for ($i = 2; $i <= $this->childCounts; $i ++) {
$index = ($index + $this->e) % $i;
}
return $index;
}
public function getResult()
{
$this->initCircle();
return $this->findChild();
}
}
//获取输入变量
$params = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
foreach($params as $k => $v){
$params[$k] = explode('=',$v);
}
$summer = new Summer();
$summer->childCounts = $params[0][1];
$summer->e = $params[1][1];
echo $summer->getResult();
2017自如技术大赛研发组题目五：订单最优分配问题
zkbhj 发表了文章 • 0 个评论 • 1498 次浏览 • 2017-12-04 00:04
5. 服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单
假设师傅每天工作8个小时，给定一天n个订单，每个订单其占用时间长为Ti,挣取价值为Vi,1
现请您为师傅安排订单，并保证师傅挣取价值最大
输入格式
输入n组数据，每组以逗号分隔并且每一个订单的编号，时长，挣取价值，数字以空格分隔
输出格式
输出争取价值，订单编号，订单编号按照价值由大到小排序，争取价值相同，则按照每小时平均争取价值由大到小排序
输入样例
[MV10001 2 100,MV10002 3 120,MV10003 1 200,MV10004 3 200,MV10005 4 70,MV10006 3 120,MV10007 2 10,MV10008 2 30,MV10009 6 500,MV10010 3 400]
输出样例
800 MV10010 MV10003 MV10004
【PHP实现】
<?php
/**
* Class ServiceOrder
* 服务师傅订单最优分配计算
* User: 郑凯
* Date: 2017/12/2
* Time: 18:13
*/
class ServiceOrder {
//待分配的订单数组
public $orderList = array();
//服务师傅每天的工作时长
public $workTime = 8;
//最终筛选出来的收益最大订单列表
public $finalOrderList = array();
//按照预设好的格式，将数据进行初始化，装填到数组中
public function initOrder($orderList)
{
//去除前后多余的[]
$orderList = substr($orderList, 1);
$orderList = substr($orderList, 0, -1);
$tempArray = explode(",",$orderList);
foreach($tempArray as $key => $value){
$this->orderList[$key] = explode(" ",$value);
}
}
function arraySequence($array, $field, $sort = 'SORT_DESC')
{
$arrSort = array();
foreach ($array as $uniqid => $row) {
foreach ($row as $key => $value) {
$arrSort[$key][$uniqid] = $value;
}
}
array_multisort($arrSort[$field], constant($sort), $array);
return $array;
}
//给师傅按最大收益安排订单
public function planOrder()
{
//计算每个订单的平均赚取收益
foreach($this->orderList as $key => $value){
$this->orderList[$key][3] = $value[2]/$value[1];
}
//将订单按照平均赚取收益由高到低排序
$this->orderList = $this->arraySequence($this->orderList,'3','SORT_DESC');
//按照每日工作时长限制，取收益率最高的头几个订单
$workTime = 0;
foreach($this->orderList as $k => $v){
if($this->workTime - $workTime >= $v[1]){
$this->finalOrderList[] = $v;
$workTime+=$v[1];
}
}
}
public function printOrder()
{
//输出总收益
$string = array_sum(array_map(create_function('$val', 'return $val["2"];'), $this->finalOrderList))." ";
//输出订单编号（按单笔订单收益由高到低排序，相同的，则按照平均赚取收益由高到低排序）
foreach($this->finalOrderList as $k => $v){
$total[$k] = $v[2];
$average[$k] = $v[3];
}
array_multisort($total, SORT_DESC, $average, SORT_DESC, $this->finalOrderList);
//输出订单号
foreach($this->finalOrderList as $k => $v){
$string .= $v[0]." ";
}
return $string;
}
public function getResult()
{
$this->planOrder();
return $this->printOrder();
}
}
//获取输入变量
$orderList = trim(fgets(STDIN), " \t\n\r\0\x0B");
$service = new ServiceOrder();
$service->initOrder($orderList);
echo $service->getResult(); 查看全部
假设师傅每天工作8个小时，给定一天n个订单，每个订单其占用时间长为Ti,挣取价值为Vi,1
现请您为师傅安排订单，并保证师傅挣取价值最大
输入格式
输入n组数据，每组以逗号分隔并且每一个订单的编号，时长，挣取价值，数字以空格分隔
输出格式
输出争取价值，订单编号，订单编号按照价值由大到小排序，争取价值相同，则按照每小时平均争取价值由大到小排序
输入样例
[MV10001 2 100,MV10002 3 120,MV10003 1 200,MV10004 3 200,MV10005 4 70,MV10006 3 120,MV10007 2 10,MV10008 2 30,MV10009 6 500,MV10010 3 400]
输出样例
800 MV10010 MV10003 MV10004
【PHP实现】
<?php
/**
* Class ServiceOrder
* 服务师傅订单最优分配计算
* User: 郑凯
* Date: 2017/12/2
* Time: 18:13
*/
class ServiceOrder {
//待分配的订单数组
public $orderList = array();
//服务师傅每天的工作时长
public $workTime = 8;
//最终筛选出来的收益最大订单列表
public $finalOrderList = array();
//按照预设好的格式，将数据进行初始化，装填到数组中
public function initOrder($orderList)
{
//去除前后多余的[]
$orderList = substr($orderList, 1);
$orderList = substr($orderList, 0, -1);
$tempArray = explode(",",$orderList);
foreach($tempArray as $key => $value){
$this->orderList[$key] = explode(" ",$value);
}
}
function arraySequence($array, $field, $sort = 'SORT_DESC')
{
$arrSort = array();
foreach ($array as $uniqid => $row) {
foreach ($row as $key => $value) {
$arrSort[$key][$uniqid] = $value;
}
}
array_multisort($arrSort[$field], constant($sort), $array);
return $array;
}
//给师傅按最大收益安排订单
public function planOrder()
{
//计算每个订单的平均赚取收益
foreach($this->orderList as $key => $value){
$this->orderList[$key][3] = $value[2]/$value[1];
}
//将订单按照平均赚取收益由高到低排序
$this->orderList = $this->arraySequence($this->orderList,'3','SORT_DESC');
//按照每日工作时长限制，取收益率最高的头几个订单
$workTime = 0;
foreach($this->orderList as $k => $v){
if($this->workTime - $workTime >= $v[1]){
$this->finalOrderList[] = $v;
$workTime+=$v[1];
}
}
}
public function printOrder()
{
//输出总收益
$string = array_sum(array_map(create_function('$val', 'return $val["2"];'), $this->finalOrderList))." ";
//输出订单编号（按单笔订单收益由高到低排序，相同的，则按照平均赚取收益由高到低排序）
foreach($this->finalOrderList as $k => $v){
$total[$k] = $v[2];
$average[$k] = $v[3];
}
array_multisort($total, SORT_DESC, $average, SORT_DESC, $this->finalOrderList);
//输出订单号
foreach($this->finalOrderList as $k => $v){
$string .= $v[0]." ";
}
return $string;
}
public function getResult()
{
$this->planOrder();
return $this->printOrder();
}
}
//获取输入变量
$orderList = trim(fgets(STDIN), " \t\n\r\0\x0B");
$service = new ServiceOrder();
$service->initOrder($orderList);
echo $service->getResult(); 查看全部
5. 服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单
假设师傅每天工作8个小时，给定一天n个订单，每个订单其占用时间长为Ti,挣取价值为Vi,1
现请您为师傅安排订单，并保证师傅挣取价值最大
输入格式
输入n组数据，每组以逗号分隔并且每一个订单的编号，时长，挣取价值，数字以空格分隔
输出格式
输出争取价值，订单编号，订单编号按照价值由大到小排序，争取价值相同，则按照每小时平均争取价值由大到小排序
输入样例
[MV10001 2 100,MV10002 3 120,MV10003 1 200,MV10004 3 200,MV10005 4 70,MV10006 3 120,MV10007 2 10,MV10008 2 30,MV10009 6 500,MV10010 3 400]
输出样例
800 MV10010 MV10003 MV10004
【PHP实现】
假设师傅每天工作8个小时，给定一天n个订单，每个订单其占用时间长为Ti,挣取价值为Vi,1
现请您为师傅安排订单，并保证师傅挣取价值最大
输入格式
输入n组数据，每组以逗号分隔并且每一个订单的编号，时长，挣取价值，数字以空格分隔
输出格式
输出争取价值，订单编号，订单编号按照价值由大到小排序，争取价值相同，则按照每小时平均争取价值由大到小排序
输入样例
[MV10001 2 100,MV10002 3 120,MV10003 1 200,MV10004 3 200,MV10005 4 70,MV10006 3 120,MV10007 2 10,MV10008 2 30,MV10009 6 500,MV10010 3 400]
输出样例
800 MV10010 MV10003 MV10004
【PHP实现】
<?php
/**
* Class ServiceOrder
* 服务师傅订单最优分配计算
* User: 郑凯
* Date: 2017/12/2
* Time: 18:13
*/
class ServiceOrder {
//待分配的订单数组
public $orderList = array();
//服务师傅每天的工作时长
public $workTime = 8;
//最终筛选出来的收益最大订单列表
public $finalOrderList = array();
//按照预设好的格式，将数据进行初始化，装填到数组中
public function initOrder($orderList)
{
//去除前后多余的[]
$orderList = substr($orderList, 1);
$orderList = substr($orderList, 0, -1);
$tempArray = explode(",",$orderList);
foreach($tempArray as $key => $value){
$this->orderList[$key] = explode(" ",$value);
}
}
function arraySequence($array, $field, $sort = 'SORT_DESC')
{
$arrSort = array();
foreach ($array as $uniqid => $row) {
foreach ($row as $key => $value) {
$arrSort[$key][$uniqid] = $value;
}
}
array_multisort($arrSort[$field], constant($sort), $array);
return $array;
}
//给师傅按最大收益安排订单
public function planOrder()
{
//计算每个订单的平均赚取收益
foreach($this->orderList as $key => $value){
$this->orderList[$key][3] = $value[2]/$value[1];
}
//将订单按照平均赚取收益由高到低排序
$this->orderList = $this->arraySequence($this->orderList,'3','SORT_DESC');
//按照每日工作时长限制，取收益率最高的头几个订单
$workTime = 0;
foreach($this->orderList as $k => $v){
if($this->workTime - $workTime >= $v[1]){
$this->finalOrderList[] = $v;
$workTime+=$v[1];
}
}
}
public function printOrder()
{
//输出总收益
$string = array_sum(array_map(create_function('$val', 'return $val["2"];'), $this->finalOrderList))." ";
//输出订单编号（按单笔订单收益由高到低排序，相同的，则按照平均赚取收益由高到低排序）
foreach($this->finalOrderList as $k => $v){
$total[$k] = $v[2];
$average[$k] = $v[3];
}
array_multisort($total, SORT_DESC, $average, SORT_DESC, $this->finalOrderList);
//输出订单号
foreach($this->finalOrderList as $k => $v){
$string .= $v[0]." ";
}
return $string;
}
public function getResult()
{
$this->planOrder();
return $this->printOrder();
}
}
//获取输入变量
$orderList = trim(fgets(STDIN), " \t\n\r\0\x0B");
$service = new ServiceOrder();
$service->initOrder($orderList);
echo $service->getResult();
2017自如技术大赛研发组题目四：蓄水池蓄水量计算问题
zkbhj 发表了文章 • 0 个评论 • 2033 次浏览 • 2017-12-04 00:02
4. 自如寓打算门口用砖头围立一个蓄水池子，从上面看凹凸不平，凹的地方会有积水。那如果用数字代表每个砖头的高度，就形成一个二维数据（如示例），请问这个池子能存储多少单位的水？
例如二维数组为：
9 9 9 9<br>
3 0 0 9<br>
7 8 9 6<br>
时，答案是中间的0,0位置可以存储3（因为其外面最低是3）个单位的水，因此答案为3+3=6
示例：
输入：[1 1 1 1,1 0 0 1,1 1 1 1]
输出：2
【PHP实现】<?php
/**
* Class Pool
* 蓄水池蓄水量计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 15:35
*/
class WaterPool {
//水池数组(二维数组)
public $poolArray = array();
//水池中凹的地方的数量
public $aoCounts = 0;
//水池中木桶效应的最低“短板”数量（决定单个凹的地方的储水量）
public $bottomCounts = 0;
private function getWater()
{
//遍历水池数组(二维数组)
$bottomTemp = array("height"=>9,"counts"=>0);
foreach($this->poolArray as $key => $value){
foreach($value as $k => $v){
//统计水池中凹的地方的数量
if($v == 0){
$this->aoCounts++;
}
//统计水池中木桶效应的最低“短板”数量
if($bottomTemp["height"] > $v && $v != 0){
$bottomTemp["height"] = $v;
$bottomTemp["counts"] = 1;
}elseif($bottomTemp["height"] == $v){
$bottomTemp["counts"]++;
}
}
}
//计算水池中的最多储水量
return $this->aoCounts * $bottomTemp["height"];
}
//得到结果
public function getResult()
{
return $this->getWater();
}
}
//获取输入变量
$params = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B"));
foreach($params as $k => $v){
$params[$k] = explode(' ',$v);
}
//实例化
$pool = new WaterPool();
$pool->poolArray = $params;
echo $pool->getResult(); 查看全部
例如二维数组为：
9 9 9 9<br>
3 0 0 9<br>
7 8 9 6<br>
时，答案是中间的0,0位置可以存储3（因为其外面最低是3）个单位的水，因此答案为3+3=6
示例：
输入：[1 1 1 1,1 0 0 1,1 1 1 1]
输出：2
【PHP实现】<?php
/**
* Class Pool
* 蓄水池蓄水量计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 15:35
*/
class WaterPool {
//水池数组(二维数组)
public $poolArray = array();
//水池中凹的地方的数量
public $aoCounts = 0;
//水池中木桶效应的最低“短板”数量（决定单个凹的地方的储水量）
public $bottomCounts = 0;
private function getWater()
{
//遍历水池数组(二维数组)
$bottomTemp = array("height"=>9,"counts"=>0);
foreach($this->poolArray as $key => $value){
foreach($value as $k => $v){
//统计水池中凹的地方的数量
if($v == 0){
$this->aoCounts++;
}
//统计水池中木桶效应的最低“短板”数量
if($bottomTemp["height"] > $v && $v != 0){
$bottomTemp["height"] = $v;
$bottomTemp["counts"] = 1;
}elseif($bottomTemp["height"] == $v){
$bottomTemp["counts"]++;
}
}
}
//计算水池中的最多储水量
return $this->aoCounts * $bottomTemp["height"];
}
//得到结果
public function getResult()
{
return $this->getWater();
}
}
//获取输入变量
$params = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B"));
foreach($params as $k => $v){
$params[$k] = explode(' ',$v);
}
//实例化
$pool = new WaterPool();
$pool->poolArray = $params;
echo $pool->getResult(); 查看全部
4. 自如寓打算门口用砖头围立一个蓄水池子，从上面看凹凸不平，凹的地方会有积水。那如果用数字代表每个砖头的高度，就形成一个二维数据（如示例），请问这个池子能存储多少单位的水？
例如二维数组为：
9 9 9 9<br>
3 0 0 9<br>
7 8 9 6<br>
时，答案是中间的0,0位置可以存储3（因为其外面最低是3）个单位的水，因此答案为3+3=6
示例：
输入：[1 1 1 1,1 0 0 1,1 1 1 1]
输出：2
【PHP实现】
例如二维数组为：
9 9 9 9<br>
3 0 0 9<br>
7 8 9 6<br>
时，答案是中间的0,0位置可以存储3（因为其外面最低是3）个单位的水，因此答案为3+3=6
示例：
输入：[1 1 1 1,1 0 0 1,1 1 1 1]
输出：2
【PHP实现】
<?php
/**
* Class Pool
* 蓄水池蓄水量计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 15:35
*/
class WaterPool {
//水池数组(二维数组)
public $poolArray = array();
//水池中凹的地方的数量
public $aoCounts = 0;
//水池中木桶效应的最低“短板”数量（决定单个凹的地方的储水量）
public $bottomCounts = 0;
private function getWater()
{
//遍历水池数组(二维数组)
$bottomTemp = array("height"=>9,"counts"=>0);
foreach($this->poolArray as $key => $value){
foreach($value as $k => $v){
//统计水池中凹的地方的数量
if($v == 0){
$this->aoCounts++;
}
//统计水池中木桶效应的最低“短板”数量
if($bottomTemp["height"] > $v && $v != 0){
$bottomTemp["height"] = $v;
$bottomTemp["counts"] = 1;
}elseif($bottomTemp["height"] == $v){
$bottomTemp["counts"]++;
}
}
}
//计算水池中的最多储水量
return $this->aoCounts * $bottomTemp["height"];
}
//得到结果
public function getResult()
{
return $this->getWater();
}
}
//获取输入变量
$params = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B"));
foreach($params as $k => $v){
$params[$k] = explode(' ',$v);
}
//实例化
$pool = new WaterPool();
$pool->poolArray = $params;
echo $pool->getResult();
2017自如技术大赛研发组题目三：给定数字连接最大数
zkbhj 发表了文章 • 0 个评论 • 1585 次浏览 • 2017-12-04 00:01
3. 给定一个数组，将数组中的数字连接起来，求最大数。
示例：
输入：4,94,9,14,1
输出：9944141
【PHP实现】
<?php
/**
* Class Max
* 计算最大数字
* User: 郑凯
* Date: 2017/12/2
* Time: 14:02
*/
class Max {
//要进行处理的原始数字数组
public $numbers = array();
//经过处理后排序好的数字数组
public $lastNumber = array();
/**
* 获取整数某个位置的数字值
* @param $number
* @param int $position
* @return bool
*/
public function getPositionNumber($number,$position = 0)
{
//将数字当成字符串，将数字分离个位数存到数组中
for($i=0;$i<strlen($number);$i++){
$array[] = substr($number,$i,1);
}
return isset($array[$position])?$array[$position]:false;
}
/**
* 比较两个数，决定谁优先排在前面（即下面注释中的“最大数”）
* @param $a
* @param $b
* @return null
*/
private function compare($a,$b){
//默认最大值是null
$max = null;
//按两个数中数学概念中的最小数的长度进行从高到低每一位数字的对比
for($i = 0; $i<min(array(strlen($a),strlen($b))); $i++){
//如果同一位上的两个数字相等，则继续向下一位比较
if($this->getPositionNumber($a, $i) == $this->getPositionNumber($b, $i)){
continue;
}else{
//如果两个数字不等，则“最大数”是比较大的那个整数，跳出循环，不再继续比较
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b, $i) ? $max = $a:$max = $b;
break;
}
}
//如果走到这里，说明数学概念中最小数的长度的头几位两个整数一样，那么就需要比较较长数字的下一位和较短数字的第一位
//首先判断这两个整数中哪个是短的
//如果两个整数长度一致，说明两个整数一样，则返回谁都可以
//如果较长数字的下一位比较短整数的第一位大，则“最大数”应该是前者，否则，应该是后者
if($max == null){
if(strlen($a)<strlen($b)){
$this->getPositionNumber($b, $i) > $this->getPositionNumber($a,0) ? $max = $b:$max = $a;
}elseif(strlen($a)>strlen($b)){
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b,0) ? $max = $a:$max = $b;
}else{
$max = $a;
}
}
//返回“最大数”
return $max;
}
//主体函数，获取最大数字
public function getMaxNumber()
{
//初始化最大数，赋值为给定数字数组中的第一个
$max = array("key"=> 0, "value"=>$this->numbers[0]);
//对数组中的每个数字进行循环，将其与Max中的数字进行比较
for($j=0 ;$j < count($this->numbers); $j++){
$tempMax = $this->compare($this->numbers[$j],$max['value']);
//如果得到的“最大数”应不是原来的“最大数”，那么进行最大数的更新（更新key和value），这里的key主要用于下面的unset
if($tempMax != $max['value']){
$max['value'] = $tempMax;
$max['key'] = $j;
}
}
//把这一轮比较中的“最大数”放入数组中
$this->lastNumber[] = $max;
//将这个比较出来的“最大数”从原始数组中删除，不再让他捣乱啦
unset($this->numbers[$max['key']]);
//将原始数组重建key
$this->numbers = array_values($this->numbers);
//如果原始数组中还有数组，继续递归调用
if(count($this->numbers) > 0){
$this->getMaxNumber();
}
}
//输出最后连起来最大的数字
public function getResult()
{
$this->getMaxNumber();
foreach($this->lastNumber as $key => $value){
echo $value['value'];
}
}
}
//获取输入变量
$numbers = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
//实例化
$max = new Max();
$max->numbers = $numbers;
$max->getResult(); 查看全部
示例：
输入：4,94,9,14,1
输出：9944141
【PHP实现】
<?php
/**
* Class Max
* 计算最大数字
* User: 郑凯
* Date: 2017/12/2
* Time: 14:02
*/
class Max {
//要进行处理的原始数字数组
public $numbers = array();
//经过处理后排序好的数字数组
public $lastNumber = array();
/**
* 获取整数某个位置的数字值
* @param $number
* @param int $position
* @return bool
*/
public function getPositionNumber($number,$position = 0)
{
//将数字当成字符串，将数字分离个位数存到数组中
for($i=0;$i<strlen($number);$i++){
$array[] = substr($number,$i,1);
}
return isset($array[$position])?$array[$position]:false;
}
/**
* 比较两个数，决定谁优先排在前面（即下面注释中的“最大数”）
* @param $a
* @param $b
* @return null
*/
private function compare($a,$b){
//默认最大值是null
$max = null;
//按两个数中数学概念中的最小数的长度进行从高到低每一位数字的对比
for($i = 0; $i<min(array(strlen($a),strlen($b))); $i++){
//如果同一位上的两个数字相等，则继续向下一位比较
if($this->getPositionNumber($a, $i) == $this->getPositionNumber($b, $i)){
continue;
}else{
//如果两个数字不等，则“最大数”是比较大的那个整数，跳出循环，不再继续比较
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b, $i) ? $max = $a:$max = $b;
break;
}
}
//如果走到这里，说明数学概念中最小数的长度的头几位两个整数一样，那么就需要比较较长数字的下一位和较短数字的第一位
//首先判断这两个整数中哪个是短的
//如果两个整数长度一致，说明两个整数一样，则返回谁都可以
//如果较长数字的下一位比较短整数的第一位大，则“最大数”应该是前者，否则，应该是后者
if($max == null){
if(strlen($a)<strlen($b)){
$this->getPositionNumber($b, $i) > $this->getPositionNumber($a,0) ? $max = $b:$max = $a;
}elseif(strlen($a)>strlen($b)){
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b,0) ? $max = $a:$max = $b;
}else{
$max = $a;
}
}
//返回“最大数”
return $max;
}
//主体函数，获取最大数字
public function getMaxNumber()
{
//初始化最大数，赋值为给定数字数组中的第一个
$max = array("key"=> 0, "value"=>$this->numbers[0]);
//对数组中的每个数字进行循环，将其与Max中的数字进行比较
for($j=0 ;$j < count($this->numbers); $j++){
$tempMax = $this->compare($this->numbers[$j],$max['value']);
//如果得到的“最大数”应不是原来的“最大数”，那么进行最大数的更新（更新key和value），这里的key主要用于下面的unset
if($tempMax != $max['value']){
$max['value'] = $tempMax;
$max['key'] = $j;
}
}
//把这一轮比较中的“最大数”放入数组中
$this->lastNumber[] = $max;
//将这个比较出来的“最大数”从原始数组中删除，不再让他捣乱啦
unset($this->numbers[$max['key']]);
//将原始数组重建key
$this->numbers = array_values($this->numbers);
//如果原始数组中还有数组，继续递归调用
if(count($this->numbers) > 0){
$this->getMaxNumber();
}
}
//输出最后连起来最大的数字
public function getResult()
{
$this->getMaxNumber();
foreach($this->lastNumber as $key => $value){
echo $value['value'];
}
}
}
//获取输入变量
$numbers = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
//实例化
$max = new Max();
$max->numbers = $numbers;
$max->getResult(); 查看全部
3. 给定一个数组，将数组中的数字连接起来，求最大数。
示例：
输入：4,94,9,14,1
输出：9944141
【PHP实现】
示例：
输入：4,94,9,14,1
输出：9944141
【PHP实现】
<?php
/**
* Class Max
* 计算最大数字
* User: 郑凯
* Date: 2017/12/2
* Time: 14:02
*/
class Max {
//要进行处理的原始数字数组
public $numbers = array();
//经过处理后排序好的数字数组
public $lastNumber = array();
/**
* 获取整数某个位置的数字值
* @param $number
* @param int $position
* @return bool
*/
public function getPositionNumber($number,$position = 0)
{
//将数字当成字符串，将数字分离个位数存到数组中
for($i=0;$i<strlen($number);$i++){
$array[] = substr($number,$i,1);
}
return isset($array[$position])?$array[$position]:false;
}
/**
* 比较两个数，决定谁优先排在前面（即下面注释中的“最大数”）
* @param $a
* @param $b
* @return null
*/
private function compare($a,$b){
//默认最大值是null
$max = null;
//按两个数中数学概念中的最小数的长度进行从高到低每一位数字的对比
for($i = 0; $i<min(array(strlen($a),strlen($b))); $i++){
//如果同一位上的两个数字相等，则继续向下一位比较
if($this->getPositionNumber($a, $i) == $this->getPositionNumber($b, $i)){
continue;
}else{
//如果两个数字不等，则“最大数”是比较大的那个整数，跳出循环，不再继续比较
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b, $i) ? $max = $a:$max = $b;
break;
}
}
//如果走到这里，说明数学概念中最小数的长度的头几位两个整数一样，那么就需要比较较长数字的下一位和较短数字的第一位
//首先判断这两个整数中哪个是短的
//如果两个整数长度一致，说明两个整数一样，则返回谁都可以
//如果较长数字的下一位比较短整数的第一位大，则“最大数”应该是前者，否则，应该是后者
if($max == null){
if(strlen($a)<strlen($b)){
$this->getPositionNumber($b, $i) > $this->getPositionNumber($a,0) ? $max = $b:$max = $a;
}elseif(strlen($a)>strlen($b)){
$this->getPositionNumber($a, $i) > $this->getPositionNumber($b,0) ? $max = $a:$max = $b;
}else{
$max = $a;
}
}
//返回“最大数”
return $max;
}
//主体函数，获取最大数字
public function getMaxNumber()
{
//初始化最大数，赋值为给定数字数组中的第一个
$max = array("key"=> 0, "value"=>$this->numbers[0]);
//对数组中的每个数字进行循环，将其与Max中的数字进行比较
for($j=0 ;$j < count($this->numbers); $j++){
$tempMax = $this->compare($this->numbers[$j],$max['value']);
//如果得到的“最大数”应不是原来的“最大数”，那么进行最大数的更新（更新key和value），这里的key主要用于下面的unset
if($tempMax != $max['value']){
$max['value'] = $tempMax;
$max['key'] = $j;
}
}
//把这一轮比较中的“最大数”放入数组中
$this->lastNumber[] = $max;
//将这个比较出来的“最大数”从原始数组中删除，不再让他捣乱啦
unset($this->numbers[$max['key']]);
//将原始数组重建key
$this->numbers = array_values($this->numbers);
//如果原始数组中还有数组，继续递归调用
if(count($this->numbers) > 0){
$this->getMaxNumber();
}
}
//输出最后连起来最大的数字
public function getResult()
{
$this->getMaxNumber();
foreach($this->lastNumber as $key => $value){
echo $value['value'];
}
}
}
//获取输入变量
$numbers = explode(',', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
//实例化
$max = new Max();
$max->numbers = $numbers;
$max->getResult();
2017自如技术大赛研发组题目二：110的算式计算
zkbhj 发表了文章 • 0 个评论 • 1431 次浏览 • 2017-12-04 00:00
2. 2016年自如将品质管理中心升级为安全与品质管理中心，并开通了自如举报邮箱。请看下边的算式
1 2 3 4 5 6 7 8 9 = ？（举报邮箱前缀数字）;（备注110）
为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法。
请大家帮忙计算出多少个可能组合吧，至少3个以上算有效
示例
输入：[1 2 3 4 5 6 7 8 9 ]
输出：12+34+56+7-8+9
…………………………
【PHP实现】
<?php
class Fire {
private $numberItems = array();
//用于存储所有可能的情况
private $situation = array();
//设计的最终结果
private $result = 110;
//用于存储计算结果和设计结果一直的情况
private $rightSituation = array();
//用0,1,2分别代表空格、加号和减号
private $symbol = array(0=>"",1=>"+",2=>"-");
private $temp = array();
//获取所有可能出现的情况
public function getSituation($index)
{
if ($index == 8) {
$this->situation[] = $this->temp;
return;
}
//每个空有三种可能，0,1,2
for ($i = 0; $i < 3; $i++) {
$this->temp[$index] = $i;
$this->getSituation($index + 1);
$this->temp[$index] = 0; //恢复原来的状态
}
}
//获得表达式和输出结果
public function calculate()
{
foreach($this->situation as $k => $v){
$number = 1;
$expression = 1;
foreach($v as $key => $value){
switch($value)
{
//空格
case 0:
{
$expression = $expression.$this->numberItems[$key+1];
break;
}
//加号
case 1:
{
$expression = $expression . "+" .$this->numberItems[$key+1];
break;
}
//减号
case 2:
{
$expression = $expression . "-" .$this->numberItems[$key+1];
break;
}
}
}
//判断是否等于预期结果
$expressionResult = $this->getExpressionResult($expression);
if($this->result == $expressionResult){
echo $expression . " = ". $expressionResult, PHP_EOL;
}
}
}
//根据字符串表达式计算结果
public function getExpressionResult($expression)
{
//将加减符号进行分解排序
$all = str_split($expression,1);
$flag_reduce = array_keys($all,'-');
$flag_add = array_keys($all,'+');
$flags = array_merge($flag_add,$flag_reduce);
asort($flags);
foreach($flags as $key => $value){
array_search($value,$flag_reduce) === false ? $flags[$key] = "+":$flags[$key] = "-";
}
//重建key
$flags = array_values($flags);
//按顺序获得运算数
$expression_reduce = str_replace("+","-",$expression);
$array_numbers = explode('-',$expression_reduce);
//逐个数字进行运算
$result = 0;
foreach($array_numbers as $k => $v){
if($k == 0){
$result = $v;
continue;
}
$flag = isset($flags[$k-1])?$flags[$k-1]:"";
switch($flag){
case "+":
{
$result = $result + $v;
break;
}
case "-":
{
$result = $result - $v;
break;
}
case "":
{
break;
}
}
}
return $result;
}
public function getResult($base)
{
$this->numberItems = $base;
$this->getSituation(0);
$this->calculate();
}
}
//获取输入变量
$base = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
$fire = new Fire();
$fire->getResult($base); 查看全部
1 2 3 4 5 6 7 8 9 = ？（举报邮箱前缀数字）;（备注110）
为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法。
请大家帮忙计算出多少个可能组合吧，至少3个以上算有效
示例
输入：[1 2 3 4 5 6 7 8 9 ]
输出：12+34+56+7-8+9
…………………………
【PHP实现】
<?php
class Fire {
private $numberItems = array();
//用于存储所有可能的情况
private $situation = array();
//设计的最终结果
private $result = 110;
//用于存储计算结果和设计结果一直的情况
private $rightSituation = array();
//用0,1,2分别代表空格、加号和减号
private $symbol = array(0=>"",1=>"+",2=>"-");
private $temp = array();
//获取所有可能出现的情况
public function getSituation($index)
{
if ($index == 8) {
$this->situation[] = $this->temp;
return;
}
//每个空有三种可能，0,1,2
for ($i = 0; $i < 3; $i++) {
$this->temp[$index] = $i;
$this->getSituation($index + 1);
$this->temp[$index] = 0; //恢复原来的状态
}
}
//获得表达式和输出结果
public function calculate()
{
foreach($this->situation as $k => $v){
$number = 1;
$expression = 1;
foreach($v as $key => $value){
switch($value)
{
//空格
case 0:
{
$expression = $expression.$this->numberItems[$key+1];
break;
}
//加号
case 1:
{
$expression = $expression . "+" .$this->numberItems[$key+1];
break;
}
//减号
case 2:
{
$expression = $expression . "-" .$this->numberItems[$key+1];
break;
}
}
}
//判断是否等于预期结果
$expressionResult = $this->getExpressionResult($expression);
if($this->result == $expressionResult){
echo $expression . " = ". $expressionResult, PHP_EOL;
}
}
}
//根据字符串表达式计算结果
public function getExpressionResult($expression)
{
//将加减符号进行分解排序
$all = str_split($expression,1);
$flag_reduce = array_keys($all,'-');
$flag_add = array_keys($all,'+');
$flags = array_merge($flag_add,$flag_reduce);
asort($flags);
foreach($flags as $key => $value){
array_search($value,$flag_reduce) === false ? $flags[$key] = "+":$flags[$key] = "-";
}
//重建key
$flags = array_values($flags);
//按顺序获得运算数
$expression_reduce = str_replace("+","-",$expression);
$array_numbers = explode('-',$expression_reduce);
//逐个数字进行运算
$result = 0;
foreach($array_numbers as $k => $v){
if($k == 0){
$result = $v;
continue;
}
$flag = isset($flags[$k-1])?$flags[$k-1]:"";
switch($flag){
case "+":
{
$result = $result + $v;
break;
}
case "-":
{
$result = $result - $v;
break;
}
case "":
{
break;
}
}
}
return $result;
}
public function getResult($base)
{
$this->numberItems = $base;
$this->getSituation(0);
$this->calculate();
}
}
//获取输入变量
$base = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
$fire = new Fire();
$fire->getResult($base); 查看全部
2. 2016年自如将品质管理中心升级为安全与品质管理中心，并开通了自如举报邮箱。请看下边的算式
1 2 3 4 5 6 7 8 9 = ？（举报邮箱前缀数字）;（备注110）
为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法。
请大家帮忙计算出多少个可能组合吧，至少3个以上算有效
示例
输入：[1 2 3 4 5 6 7 8 9 ]
输出：12+34+56+7-8+9
…………………………
【PHP实现】
1 2 3 4 5 6 7 8 9 = ？（举报邮箱前缀数字）;（备注110）
为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法。
请大家帮忙计算出多少个可能组合吧，至少3个以上算有效
示例
输入：[1 2 3 4 5 6 7 8 9 ]
输出：12+34+56+7-8+9
…………………………
【PHP实现】
<?php
class Fire {
private $numberItems = array();
//用于存储所有可能的情况
private $situation = array();
//设计的最终结果
private $result = 110;
//用于存储计算结果和设计结果一直的情况
private $rightSituation = array();
//用0,1,2分别代表空格、加号和减号
private $symbol = array(0=>"",1=>"+",2=>"-");
private $temp = array();
//获取所有可能出现的情况
public function getSituation($index)
{
if ($index == 8) {
$this->situation[] = $this->temp;
return;
}
//每个空有三种可能，0,1,2
for ($i = 0; $i < 3; $i++) {
$this->temp[$index] = $i;
$this->getSituation($index + 1);
$this->temp[$index] = 0; //恢复原来的状态
}
}
//获得表达式和输出结果
public function calculate()
{
foreach($this->situation as $k => $v){
$number = 1;
$expression = 1;
foreach($v as $key => $value){
switch($value)
{
//空格
case 0:
{
$expression = $expression.$this->numberItems[$key+1];
break;
}
//加号
case 1:
{
$expression = $expression . "+" .$this->numberItems[$key+1];
break;
}
//减号
case 2:
{
$expression = $expression . "-" .$this->numberItems[$key+1];
break;
}
}
}
//判断是否等于预期结果
$expressionResult = $this->getExpressionResult($expression);
if($this->result == $expressionResult){
echo $expression . " = ". $expressionResult, PHP_EOL;
}
}
}
//根据字符串表达式计算结果
public function getExpressionResult($expression)
{
//将加减符号进行分解排序
$all = str_split($expression,1);
$flag_reduce = array_keys($all,'-');
$flag_add = array_keys($all,'+');
$flags = array_merge($flag_add,$flag_reduce);
asort($flags);
foreach($flags as $key => $value){
array_search($value,$flag_reduce) === false ? $flags[$key] = "+":$flags[$key] = "-";
}
//重建key
$flags = array_values($flags);
//按顺序获得运算数
$expression_reduce = str_replace("+","-",$expression);
$array_numbers = explode('-',$expression_reduce);
//逐个数字进行运算
$result = 0;
foreach($array_numbers as $k => $v){
if($k == 0){
$result = $v;
continue;
}
$flag = isset($flags[$k-1])?$flags[$k-1]:"";
switch($flag){
case "+":
{
$result = $result + $v;
break;
}
case "-":
{
$result = $result - $v;
break;
}
case "":
{
break;
}
}
}
return $result;
}
public function getResult($base)
{
$this->numberItems = $base;
$this->getSituation(0);
$this->calculate();
}
}
//获取输入变量
$base = explode(' ', trim(fgets(STDIN), " \t\n\r\0\x0B[]"));
$fire = new Fire();
$fire->getResult($base);
2017自如技术大赛研发组题目一：租金卡大放送
zkbhj 发表了文章 • 0 个评论 • 1524 次浏览 • 2017-12-03 23:58
题目：“司庆大放送，一元即租房”，司庆当日，签约入住的客户，住满30天，返还（首月租金-1元）额度的租金卡。租金卡的面额遵循了类似人民币的固定面额（1000元、500元、100元、50元、20元、10元、5元、1元），请实现一个算法，给客户返还的租金卡张数是最少的。
示例：
输入（租金卡金额）：54 输出：5
【PHP实现】
<?php
/**
* Class Money
* 租金卡张数计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 12:15
*/
class Money {
//租金卡总金额
public $totalValue;
//租金卡面额列表
public $couponList = array(1000=>0,500=>0,100=>0,50=>0,20=>0,10=>0,5=>0,1=>0);
//算法主体，计算当前金额中可以整租的最大基础面额，并计数
private function getMaxValue($money)
{
//按基础面额从高到低依次循环，如果能够被当前金额“整除”，则计算张数并递归
//当金额最后为0时，结束循环，完成计算
foreach ($this->couponList as $key => $value){
if($money / $key >= 1 && $money > 0){
//对应金额数组的个数增加
$this->couponList[$key] = floor($money / $key);
//更新下次计算金额
$money-=$key*floor($money / $key);
//递归调用
$this->getMaxValue($money);
}
}
}
//获取完整列表结果
public function getResult()
{
//调用计算函数进行计算
$this->getMaxValue($this->totalValue);
//输出结果
echo "当总金额为 ".$this->totalValue." 时，需要";
foreach ($this->couponList as $key => $value){
if($value > 0){
echo $value . "张面额为 ".$key." 元的租金卡, ";
}
}
echo "总计 ".array_sum($this->couponList)." 张！";
}
//获取总张数
public function getTotalCounts()
{
return array_sum($this->couponList);
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B[]");
//实例化类并初始化类
$myCoupon = new Money();
$myCoupon->totalValue = $params;
$myCoupon->getResult();
//\n是为了让输出结果在anycodes.cn的输出界面可以换行
echo "\n" . $myCoupon->getTotalCounts(); 查看全部
示例：
输入（租金卡金额）：54 输出：5
【PHP实现】
<?php
/**
* Class Money
* 租金卡张数计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 12:15
*/
class Money {
//租金卡总金额
public $totalValue;
//租金卡面额列表
public $couponList = array(1000=>0,500=>0,100=>0,50=>0,20=>0,10=>0,5=>0,1=>0);
//算法主体，计算当前金额中可以整租的最大基础面额，并计数
private function getMaxValue($money)
{
//按基础面额从高到低依次循环，如果能够被当前金额“整除”，则计算张数并递归
//当金额最后为0时，结束循环，完成计算
foreach ($this->couponList as $key => $value){
if($money / $key >= 1 && $money > 0){
//对应金额数组的个数增加
$this->couponList[$key] = floor($money / $key);
//更新下次计算金额
$money-=$key*floor($money / $key);
//递归调用
$this->getMaxValue($money);
}
}
}
//获取完整列表结果
public function getResult()
{
//调用计算函数进行计算
$this->getMaxValue($this->totalValue);
//输出结果
echo "当总金额为 ".$this->totalValue." 时，需要";
foreach ($this->couponList as $key => $value){
if($value > 0){
echo $value . "张面额为 ".$key." 元的租金卡, ";
}
}
echo "总计 ".array_sum($this->couponList)." 张！";
}
//获取总张数
public function getTotalCounts()
{
return array_sum($this->couponList);
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B[]");
//实例化类并初始化类
$myCoupon = new Money();
$myCoupon->totalValue = $params;
$myCoupon->getResult();
//\n是为了让输出结果在anycodes.cn的输出界面可以换行
echo "\n" . $myCoupon->getTotalCounts(); 查看全部
题目：“司庆大放送，一元即租房”，司庆当日，签约入住的客户，住满30天，返还（首月租金-1元）额度的租金卡。租金卡的面额遵循了类似人民币的固定面额（1000元、500元、100元、50元、20元、10元、5元、1元），请实现一个算法，给客户返还的租金卡张数是最少的。
示例：
输入（租金卡金额）：54 输出：5
【PHP实现】
示例：
输入（租金卡金额）：54 输出：5
【PHP实现】
<?php
/**
* Class Money
* 租金卡张数计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 12:15
*/
class Money {
//租金卡总金额
public $totalValue;
//租金卡面额列表
public $couponList = array(1000=>0,500=>0,100=>0,50=>0,20=>0,10=>0,5=>0,1=>0);
//算法主体，计算当前金额中可以整租的最大基础面额，并计数
private function getMaxValue($money)
{
//按基础面额从高到低依次循环，如果能够被当前金额“整除”，则计算张数并递归
//当金额最后为0时，结束循环，完成计算
foreach ($this->couponList as $key => $value){
if($money / $key >= 1 && $money > 0){
//对应金额数组的个数增加
$this->couponList[$key] = floor($money / $key);
//更新下次计算金额
$money-=$key*floor($money / $key);
//递归调用
$this->getMaxValue($money);
}
}
}
//获取完整列表结果
public function getResult()
{
//调用计算函数进行计算
$this->getMaxValue($this->totalValue);
//输出结果
echo "当总金额为 ".$this->totalValue." 时，需要";
foreach ($this->couponList as $key => $value){
if($value > 0){
echo $value . "张面额为 ".$key." 元的租金卡, ";
}
}
echo "总计 ".array_sum($this->couponList)." 张！";
}
//获取总张数
public function getTotalCounts()
{
return array_sum($this->couponList);
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B[]");
//实例化类并初始化类
$myCoupon = new Money();
$myCoupon->totalValue = $params;
$myCoupon->getResult();
//\n是为了让输出结果在anycodes.cn的输出界面可以换行
echo "\n" . $myCoupon->getTotalCounts();