admin管理员组文章数量:1665129
牛客、剑指offer、Leetcode编程题
- 1.跑跑卡丁车加速带求位移
- 2.遍历棋盘
- 3.输出字符串中出现n次的字符串
- 4.逆向输出英文句
- 5.数组去重
- 6.Vue实时显示当前时间
- 7.Vue实现购物车数量加减
- 8. 求m,n的最大公约数
- 9.处理路由表得到路径
- 10.和最大的最长子数组
- 11.求很赞整数对的最少操作次数
- 12.万能数字0补充连续数字组合
- 13.括号匹配并且插入指定key
- 14.利用localStorage对用户访问的标题进行记录
- 15.找数组中的极大值
- 16.把数字转换成中文读法
- 17. 求统计学中的四分位数
- 18.交并补集的运算
- 19.数组按照重复频度输出元素
- 20.最小路径和
- 21.处理JSON数据
- 22. 结束进程树
- 23. 靓号生成
- 24. 机器人大冒险(LeetCode)
- 25. 井字棋获胜者(LeetCode)
- 26. 访问所有点的最少时间(LeetCode)
- 27 独一无二的出现次数(LeetCode)
- 28. 奇数值单元格
- 29.找出数组中出现次数最多和最少的元素
- 30.找出数组中的单独数字
- 31.鲜食制作排风系统时间段启停
- 32.小度买多少瓶果汁
- 33.火柴摆列数字最大
- 34.一组平行线相同数字连线不交叉
- 35.含有对象的数组去重
- 36.买卖股票最大时机
- 37.判断url中参数
- 38.兔子繁殖
- 39.根据经纬度获得两点距离
- 40 海豚繁殖
- 41得到一个整数的逆反数
- 43 计算接雨水量
- 44 股票最佳时机(有冻结期)
- 42 无题
- 43. 行星碰撞-(栈)
1.跑跑卡丁车加速带求位移
泡泡卡丁车路过n个加速带,每个加速带有不同的加速的a1和加速时间t1,求给定n个加速带和对应的n个加速度和n个加速时间时卡丁车的位移。
如输入:
4
1 2
2 6
4 6
6 2
function test(){
var num = read_line(); //加速带的个数
//console.log(num);
var currentSpend = 0; //卡丁车当前速度
var currentAdd = 0; //卡丁车当前的加速度
var currentTime = 0; //卡丁车的加速度时间
var s =[]; //卡丁车的位移
var data = []; //一系列的加速度和时间对
var total = 0;
for(var i=0;i<num;i++){
data[i] = (read_line()).split(' ');
//console.log('data[i]====>>>',data[i]);
currentAdd = parseFloat(data[i][0]);
currentTime = parseFloat(data[i][1]);
if(i !==0){
currentSpend = currentSpend + parseFloat(data[i-1][0]) * parseFloat(data[i-1][1]);
}
getS(currentSpend,currentAdd,currentTime);
}
//计算位移 位移 = 初速度 x 加速时间 + (加速度 x 时间 x 时间)/2
function getS(v,a,t) {
//console.log('v',v,'a',a,'t',t);
var res = v * t + 0.5 * a * t * t;
s.push(res);
}
for(var j = 0; j<s.length;j++){
total += parseFloat(s[j]);
}
return total.toFixed(1);
};
var res = test();
console.log(res);
2.遍历棋盘
有一个M x N 格的棋盘,棋子在棋盘的(1,1)位置,棋子走遍所有格子最后回到原处,问最少的移动次数是多少?
var m = 7 ; //
var n = 7; //
function test(m,n) {
var steps = 0;
if(m % 2 ===0){
//按照m走
steps = (n-1)*m + m;
}else if(n % 2 ===0){
//按照n走
steps = (m-1)*n + m;
}else {
//行数列数都是奇数,重复少点的步数
if(m<n){
steps = (n-1)* (m+1) + (m-1);
}else {
steps = (m-1)* (n+1) + (n-1);
}
}
return steps;
}
var res = test(m,n);
console.log(res);
3.输出字符串中出现n次的字符串
在一个字符串中找到出现指定次数的字符并通过控制台输出。
如输入abaccdeff及1,则通过控制台输出:b d e
如输入abaccdeff及2,则通过控制台输出:a c f
function arrayNonRepeatfy(arr) {
let map = new Map();
for (let i = 0; i < arr.length; i++) {
if(map.has(arr[i])) { // 如果有该key值个数增加1
var number = map.get(arr[i]) + 1 ;
map.set(arr[i], number);
} else {
map.set(arr[i], 1); // 如果没有该key值先存进去,个数为1
}
}
return map;
}
var str = 'abaccdeff'; var times = 1; //这里自行获取控制台的输入
var arr = str.split('');
var res = arrayNonRepeatfy(arr);
console.log('处理完成的map是',res);
for(var item of res){
if(item[1] == times){
console.log(item[0])
}
}
4.逆向输出英文句
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子中单词以单个空格符隔开,为简单起见,不带标点符号。
例如输入“”,则通过控制台输出“student a am I”
var str = 'I am a student'; //自行获取数据
var res = str.split(' ').reverse().join(' '); //单词存入数组后反转顺序后再用空格拼接成字符串
console.log(res);
5.数组去重
方法一:利用for…of循环 + object 效率最高
首先创建一个空对象,然后用 for 循环遍历;
利用对象的属性不会重复这一特性,校验数组元素是否重复。
function distinct(a, b) {
let arr = a.concat(b)
let result = []
let obj = {}
for (let i of arr) {
if (!obj[i]) {
result.push(i)
obj[i] = 1 //随便赋一个值就可以
}
}
return result
}
方法二:利用set数据结构
set可以接受数组作为参数,并且可以
function distinct(a, b) {
return Array.from(new Set([...a, ...b]))
}
方法三:先排序再判断相邻元素是否相等
function distinct(a, b) {
let arr = a.concat(b)
arr = arr.sort()
let result = [arr[0]]
for (let i=1, len=arr.length; i<len; i++) {
arr[i] !== arr[i-1] && result.push(arr[i])
}
return result
}
方法四:利用includes
function distinct(a, b) {
let arr = a.concat(b)
let result = []
for (let i of arr) {
!result.includes(i) && result.push(i)
}
return result
}
方法五:利用indexOf
function distinct(data) {
let result = [];
data.forEach(function (currentValue,index,arr) {
if(arr.indexOf(currentValue) === index){
result.push(currentValue);
}
});
console.log(result);
return result;
}
distinct(data);
6.Vue实时显示当前时间
<template>
<div style="background-color: #eeeeee">
{{time}}
</div>
</template>
<script>
export default {
name: "test1",
data(){
return{
time:''
}
},
created(){
let that = this;
this.timer = setInterval(() => {
let myDate = new Date();
let Year = myDate.getFullYear(); // 获取当前年份
let Month = myDate.getMonth() +1; // 获取当前月份
let Day = myDate.getDate(); // 获取当前日(1- 31)
let Hours = myDate.getHours(); // 获取当前小时(0-23)
let Min = myDate.getMinutes(); // 获取当前分钟(0-59)
let sec = myDate.getSeconds(); // 获取当前秒数(0-59)
that.time = Year + '年'+Month + "月" + Day + '日' + Hours + '时' + Min + '分' + sec + '秒'
}, 1000)
},
beforeDestroy(){
if (this.timer) { clearInterval(this.timer); }//在组件销毁前把计时器清除掉。
}
}
</script>
<style scoped>
</style>
7.Vue实现购物车数量加减
<template>
<div style="background-color: #eeeeee">
<button @click="change(0)" style="margin: 10px ;padding: 10px;font-size:15px;background-color: #cccccc" >—</button>
<input v-model="data" style="text-align: center;font-size: 10px">
<button @click="change(1)" style="margin: 10px;padding: 10px; font-size:15px;background-color: #cccccc">+</button>
</div>
</template>
<script>
export default {
name: "test2",
data(){
return{
data:0
}
},
methods:{
//改变数字
change(params) {
if(params === 0 && this.data > 0 ){
this.data--;
}if(params ===1){
this.data++;
}
},
}
}
</script>
<style scoped>
</style>`在这里插入代码片`
8. 求m,n的最大公约数
function(num1,num2){
long k = 0, y = 0;
if(num1 < num2)
{
k = num1;
num1 = num2;
num2 = k;
}
while(num1 % num2 != 0)
{
y = num1 % num2;
num1 = num2;
num2 = y;
}
return num2;}
9.处理路由表得到路径
用以下结构表示一个路由表,内容简化为字符串表示,现给定一组路由表,要求设计一个函数,得到所有路径上的内容。
/ /==============比如输入数据如下
const routes = [
{
path : "/home",
content: 'Home',
},
{
path:'/about',
content:'About',
children:[
{
path:'/a',
content:'a'
},
{
path:'/b',
content:'b'
}
]
}
];
/ /===============要求得到如下的输出
[
{ path: '/home', content: 'Home' },
{ path: '/about/a', content: [ 'About', 'a' ] },
{ path: '/about/b', content: [ 'About', 'b' ] }
]
方法:遍历路由表结构,判断有无子路由,将指定字段按照要求存入即可
//这个是测试数据
const routes = [
{
path : "/home",
content: 'Home',
},
{
path:'/about',
content:'About',
children:[
{
path:'/a',
content:'a'
},
{
path:'/b',
content:'b'
}
]
}
];
function getRoutes(data) {
var res = [];
for(let i=0;i<data.length;i++){
if(data[i].children){
let datas = data[i].children;
for(let j= 0;j<datas.length;j++){
let obj = {};let arr = [];
obj.path = data[i].path.toString() + datas[j].path;
arr[0] = data[i].content;
arr[1] = datas[j].content;
obj.content = arr;
res.push(obj)
}
}else {
let obj = {};
obj.path = data[i].path;
obj.content = data[i].content;
res.push(obj)
}
}
return res
}
var result = getRoutes(routes);
console.log(result);
10.和最大的最长子数组
方法一: 从头到尾逐个累加数组中的每个数字,初始化和为0;比较累加子数组和最大子数组。
定义两个变量:“累加子数组和” CurrentRes 和“最大子数组和” MaxRes 。
第一步把数组中的第一个数字赋值给他们,然后从第二个数字开始累加,累加值放入“累加子数组和”。
1.如果当前“累加子数组和”小于0,那抛弃前面的“累加子数组和”,从下一个数字开始重新累加,“最大子数组和”的值不更新。
2.如果当前“累加子数组和”大于0,再让当前“累加子数组和”和当前的“最大子数组和”进行比较。
①如果当前“累加子数组和”大于当前“最大子数组和”,则更新“最大子数组和”的值为“累加子数组和”的值。
②如果当前“累加子数组和”小于当前“最大子数组和”,“最大子数组和”的值不更新。
3.再加入数组中的下一个值,“累加子数组和”进入下一轮的累加,“最大子数组和”也进入下一轮的更新。知道数组中所有值都累加完毕。
function MaxRes(arr) {
var currentRes = arr[0]; //当前的累加子数组和
var MaXRes = arr[0]; //最大子数组和
var len=arr.length;
for(let i=1;i<len;i++){
if(currentRes > 0){
currentRes +=arr[i];//当前子数组和是正数可以继续加
}else {
currentRes = arr[i] //已经是复数就不要之前的了,按当前的开始再次计算
}
if(currentRes >MaXRes){
MaXRes = currentRes ;//有了更大的子数组和,更新最大子数组和这个变量
}
console.log('当前子数组和',currentRes,'最大的子数组和',MaXRes);
}
return MaXRes
}
console.log(MaxRes([1,-1,-2,5,6,6,9,6])) //结果 32
当前子数组和 0 最大的子数组和 1
当前子数组和 -2 最大的子数组和 1
当前子数组和 5 最大的子数组和 5
当前子数组和 11 最大的子数组和 11
当前子数组和 17 最大的子数组和 17
当前子数组和 26 最大的子数组和 26
当前子数组和 32 最大的子数组和 32
32
/ /下边这个一个意思
function test(array) {
let count = 0;
var result = array[0];
if(array.length <= 1){
//数组长度为1直接返回即可
return result;
} else {
for(let i = 0;i< array.length ;i++){
if(count <=0){
count = array[i]
}else {
count += array[i]
}
if(count > result){
result = count;
}
}
}
return result;
}
console.log(test(data));
11.求很赞整数对的最少操作次数
题目描述: 给出一对整数(x,y) ,再给出一个整数m,如果x或y中至少有一个数大于等于m,我们就称(x,y)对m是一个很赞的整数对。
现在给定一个整数对(x,y)和一个整数m,允许把x或者y中的整数修改之前两个数的和,比如(1,2)可以操作为(1,3)或者(2,3);问至少进行多少次操作才能使得数对称为m的很赞整数对。
如果做多少次都不可能成功则返回-1.
//提供三组测试数据
// [1 2] 5 输出 2
// [-1 4] 15 输出 4
// [0 -1] 5 输出 -1
function main() {
var arr = [0,-1]; //初始的整数对
var m = 5; //整数m
var max = Math.min.apply(null,arr); //记录整数对中的最大值
var times = 0;//记录操作次数
if(max >= m){
//直接是很赞整数对不需要做操作
times = 0;
}else {
if(arr[0] <= 0 && arr[1] <=0){
if(arr[0] < m && arr[1] < m){
//都是负数或0 越加越小或不变 永不可能比m大
times = -1;
}
}else {
//至少有一个正数 总能加够
while (max < m) {
max = Math.max.apply(null, arr);
let min = Math.min.apply(null,arr);
max = max + min;
[arr[0],arr[1]] = [max+ min,max];
times = times + 1;
console.log('进行一次操作');
}
}
}
return times;
}
console.log(main());
12.万能数字0补充连续数字组合
题目描述: 给定一组数字(数字取值范围是0-100,可能重复,0是万能数字,可以代表其他数字空位),判断给定的一组数字是否是连续数字组合。
例如: 3 5 4 2 和3 5 0 2(0代表4)3 6 0 0(分别代表4 5)都可以当作连续数字组合。
而 3 5 2 或者 3 5 0 1 、3 7 0 0 、 3 3 4 5都没办法作为连续数字组合。
现在输入两行数据,第一个是组合中数字个数,第二行是具体的组合中的数字,
是连续数字组合输出 YES+ n; 否则输出NO+ n
注意:单个数字认为是连续数字组合。
//测试数据
// 4
// 3 5 4 2
//输出 YES+0 可以组成 2 3 4 5
//4
//3 6 0 0
//YES+2 可以组成3 4 5 6
function main() {
var m = 4; //这里获取第一行输入表示有几个数字
var require = [3, 6, 0, 0]; //这里获取第二行输入
var key = 0; //这里放万能数字0的个数
var data = []; //这里放除去万能数字的数字
var res = '' ;//最后结果
if(m === 1){
(require[0] === 0 ? key = 1 : key = 0);
res = 'YES+' + key;
}else {
//把数据分开 data存放除去0 的数字
for (var i = 0; i < require.length; i++) {
if (require[i] === 0) {
key = key + 1;
} else {
data.push(require[i])
}
}
let dis = Math.max.apply(null,data) - Math.min.apply(null,data) + 1;
let len = data.length;
if(len- dis === 0){
//刚好是连续的
res = 'YES+' + key;
}else if(len - dis > 0){
//有重复的
res = 'NO+' + key
}else {
//有插值不连续需要用0补充
let needKey = dis -len;
if(needKey <= key){
res = 'YES+' + key;
}else {
res = 'NO+' + key
}
}
}
return res;
}
var res = main();
console.log(res);
13.括号匹配并且插入指定key
给出n代表括号的对数,设置一个函数生成所有可能的有效括号组合,并且在其中一个中插入给定的关键词。
// 测试数据 n=5 key = *;
[ '(key)()','((key))' ]
function f(n,key) {
let res = [];
function h(ps,l,r) {
if(l===n && r==n){
res.push(ps);
return;
}
if(l< n){
h(ps +'(',l+1,r);
}
if(l > r){
h(ps+')',l, r+1);
}
}
h('',0,0);
let data = res; //data 代表已经生成的所有合法的括号对数组
for(var i =0 ;i<data.length;i++){
var item = data[i].split('');//把每个合法的括号对存成数组
for(var j=0;j<item.length;j++){
if(item[j] ==='(' && item[j+1] === ')'){
item[j] ='('+ key;//检测到左括号就修改添加关键词
data[i] = item.join('');//把修改好的在存入原来的括号队中
break; //决定在一个括号对中加好事所有的都加
}
}
}
console.log(data);
}
f(5,'*');
14.利用localStorage对用户访问的标题进行记录
使用前端缓存localstorage实现两个方法来缓存用户标题的历史记录,可存储可读取。
function get() {
var data = window.localStorage.getItem("title_history");
if(data == null)return null;
if(data) return data.split(',');
}
function setTitle(title) {
var res = window.localStorage.getItem("title_history");
if(res == null) window.localStorage.setItem("title_history", title);
if(res){
var data = res.split(',');
data.push(title);
var data1 = data.join(',');
window.localStorage.setItem("title_history",data1);
}
}
// console.log(get());
// setTitle('记录2'); //模拟存入
// localStorage.removeItem('title_history')
15.找数组中的极大值
function findMax() {
var arr = [2,3,8,3,4,7,10,8,2,0];
var res = '-';
var data = [];
for(var i=1;i<arr.length-1;i++){
if(arr[i-1]< arr[i] && arr[i]>arr[i+1] ){
data.push(arr[i]);
res = Array.from(new Set([...data]))
}
}
return res;
}
console.log(findMax());
16.把数字转换成中文读法
题目描述: 输入一个五位数以内的数字,要求输出他的中文读法。
如:10101 一万零一百零一
(下面的有待完善。还有bug)
function f(num) {
var data = num.toString().split('');
var res = '';
// var arr = ['零', '一', '二', '三', '四', '五', '六', '七', '八', '九'];
// var unit1 = ['', '十', '百'];
// var unit2 = ['千', '万', '十万'];
var CountingUnit = ['','万','亿'];//代表数量级
if(data.length>4 && data.length <=8){
let reading = read(data.slice(0,data.length - 4),CountingUnit[1]) + read(data.slice(data.length -4),CountingUnit[0])
res = reading.replace('零千','零').replace('零百','零').replace('零十','零').replace('零零','');
if(res.substr(res.length-1,1) ==='零'){
res = res.substr(0,res.length-1);
}
}else if(data.length <=4 && data.length >0) {
let reading = read(data,CountingUnit[0]);
res = reading.replace('零百','零').replace('零十','零').replace('零零','零');
if(res.substr(res.length-1,1) ==='零'){
res = res.substr(0,res.length-1);
}else {
res = '数字不能随便输入啊~~'
}
}
return res;
function read(data, unit) { //data:位数 unit:单位
var map = new Map([
['0', '零'],
['1', '一'],
['2', '二'],
['3', '三'],
['4', '四'],
['5', '五'],
['6', '六'],
['7', '七'],
['8', '八'],
['9', '九']
]);
let base = ['千', '百', '十', ''];
let result = '';
if (data.length === 4) {
result = map.get(data[0]) + base[0] +
map.get(data[1]) + base[1] +
map.get(data[2]) + base[2] +
map.get(data[3]) + base[3] + unit;
} else if (data.length === 3) {
result = map.get(data[0]) + base[1] +
map.get(data[1]) + base[2] +
map.get(data[2]) + base[3] + unit;
} else if (data.length === 2) {
result = map.get(data[0]) + base[2] +
map.get(data[1]) + base[3] + unit;
} else {
result = map.get(data[0]) + base[3] + unit;
}
return result;
}
}
17. 求统计学中的四分位数
题目描述: 四分位数是统计学的一个概念,把序列中的数值由小到大排列并分成四等分,处于三个分割点位置的数就是四分位数。n为序列的总长度,三个四分位数可以根据如下公式求出:
Q1的位置=(n+1)x 0.25
Q2的位置=(n+1)x 0.5
Q3的位置=(n+1)x 0.75
比如数据序列:1,3,5,7,2,4,6
由小到大排列的结果是:1,2,3,4,5,6,7
共7项,Q1的位置=(7+1)*0.25=2,Q2的位置=(7+1)*0.5=4,Q3的位置=(7+1)*0.75=6,四分位数即为第2,4,6个元素上对应的数值:(2,4,6)
现在给定一个序列求四分位数。
function four(arr) {
function test(a,b) {
return a-b;
}
var data = arr.sort(test);
console.log(data);
var q1 = (data.length +1) *0.25;
var q2 = (data.length + 1) *0.5;
var q3 = (data.length + 1) *0.75;
console.log(q1,q2,q3);
console.log(data[q1 -1],data[q2 -1],data[q3 -1]);
};
four([6,45,49,16,42,41,7,38,43,40,36]);
18.交并补集的运算
题目描述: 给定三个数组,求同时存在于arr1和arr2且步存在于arr3中的元素。
/ /其实就是相当于求数组1和2交集相对于arr3中不存在的元素。
function test() {
var arr1 = ['f','3','4','k'];
var arr2 = ['4','1','k'];
var arr3 = ['j','2','4'];
var res = [];
var result = [];
for(var i=0;i<arr1.length;i++){
if(arr2.includes(arr1[i])){
res.push(arr1[i]);
}
}
for(var j=0;j<res.length;j++){
if(!arr3.includes(res[j])){
result.push(res[j])
}
}
return result;
}
console.log(test())
19.数组按照重复频度输出元素
题目描述: 给定一个无序的数组,数组元素可重复,长度不确定,
求按照原数组中重复频度最高的排列到顺序输出一个新数组,频度一样按照原顺序。
如: [1,6,5,5,4,5,9,6,9]
输出 :[5,,6,9,1,4]
var data = [1,2,5,1,6,2,2];
function arrayNonRepeatfy(arr) {
let map = new Map();
for (let i = 0; i < arr.length; i++) {
if(map.has(arr[i])) { // 如果有该key值个数增加1
var number = map.get(arr[i]) + 1 ;
map.set(arr[i], number);
} else {
map.set(arr[i], 1); // 如果没有该key值先存进去,个数为1
}
}
return map;
}
function sort(a,b) {
return a-b
}
var res = arrayNonRepeatfy(data);
var result = [];
var arrStatus = [];
for(var item of res){
arrStatus.push(item[1])
}
arrStatus = arrStatus.sort(sort).reverse();
arrStatus = Array.from( new Set(arrStatus));
for(var i=0; i<arrStatus.length;i++){
for(let item of res){
if(item[1] ===arrStatus[i]){
result.push(item[0]);
}
}
}
//result = Array.from(new Set(result));
console.log(result) ;
//========================草稿
//
// function arrayNonRepeatfy(arr) {
// let map = new Map();
// for (let i = 0; i < arr.length; i++) {
// if(map.has(arr[i])) { // 如果有该key值个数增加1
// var number = map.get(arr[i]) + 1 ;
// map.set(arr[i], number);
// } else {
// map.set(arr[i], 1); // 如果没有该key值先存进去,个数为1
// }
// }
// return map;
// }
// function sort(a,b) {
// return a-b
// }
// var res = arrayNonRepeatfy([1,2,5,1,6,2,2]);
// var result = [];
// console.log('处理完成的map是',res);
// var arrStatus = [];
// for(var item of res){
// arrStatus.push(item[1])
// }
// arrStatus = arrStatus.sort(sort).reverse();
// for(var i=0; i<arrStatus.length;i++){
// for(let item of res){
// if(item[1] ===arrStatus[i]){
// result.push(item[0]);
// }
// }
// }
// result = Array.from(new Set(result));
// console.log(result);
20.最小路径和
题目描述如下:
var minPathSum = function(grid) {
let l = grid.length,h=grid[0].length;
let temp = [];
for(let i=0;i<l;i++)
{
temp[i]=[];
}
// console.log(temp)
for(let i = 0;i<l;i++)
{
for(let j = 0;j<h;j++)
{
if(i==0&&j==0)
{
temp[i][j]=grid[i][j]
}
else if(i==0)
{
temp[i][j]=temp[i][j-1]+grid[i][j]
}
else if(j==0)
{
temp[i][j]=temp[i-1][j]+grid[i][j]
}
else
{
temp[i][j]=grid[i][j]+Math.min(temp[i][j-1],temp[i-1][j])
}
}
}
// console.log(temp)
return temp[l-1][h-1]
};
21.处理JSON数据
题目描述: 处理JSON数据进行排序
var price = {
"k3845": {"name": "name3012", "price": 2715, "rank": 1},
"k3489": {"name": "name2855", "price": 3105, "rank": 1}
};
//price = JSON.parse(price)
let keys = Object.keys(price);
keys.sort((a, b) => {
if (price[a].price > price[b].price) {
return 1;
} else if (price[a].price === price[b].price) {
if (price[a].rank > price[b].rank) {
return 1
} else {
return -1
}
} else {
return -1
}
});
for (let item of keys) {
console.log(price[item].name + ':' + price[item].rank + ':' + item + ":" + price[item].price)
}
22. 结束进程树
题目描述:
(1)每个进程有唯一的PID,其中PID为进程ID
(2)每个进程最多只有一个父进程,但是可能有多个子进程,用PPID表示父进程的ID
(3)若一个进程没有父进程,则PPID为0
(4)PID、PPID都是无符号整数
结束进程树的含义为:当结束一个进程时,它所有的子进程也会被结束,包括子进程的子进程。
现在如果给定大小为n的两组输入列表A和B(1<=n<=100),列表A表示进程的PID列表,列表B表示列表A对应的父进程的列表,即PPID,若在给定一个PID,请输出结束该PID的进程树总共结束的进程数量。
/**
* 以下三个参数都是模拟的,根据输入替换
*/
let m = [3,1,5,21,10]; //PID
let n = [0,3,3,1,5]; //PPID
let PID = 3;//随机给定的ID
function test(id) {
var res = 0;
for(let i=0;i<n.length;i++){
if(n[i] === id){
// n.splice(i,1);
// m.splice(i,1);
m[i] = null;
n[i] = null;
res = res + 2;
}
}
for(let j=0;j<m.length;j++){
if(m[j]=== id){
res = res + 1;
}
}
return res;
}
console.log(test(PID)); //结果应该为5
23. 靓号生成
题目描述: 人们排队取号,从1开始取,碰到带4的数字就跳过,现在第n个人来,取的号码是多少?
第一个人拿1
第二个人拿2,
第四个拿5,第十个拿11
第五万个人拿的号码是96626
function test(n){
let res = [];
let i=1;
while (res.length <= n){
if(!i.toString().includes('4')){
res.push(i);
//i++ 放在这里会遇到4就无限循环
}
//无论是否包含4,i都得增加,只不过res需要考虑要不要而已
i++;
}
return res[n-1];
}
var result = test(50000);
console.log(result); //86626
24. 机器人大冒险(LeetCode)
题目描述: 力扣团队买了一个可编程机器人,机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command,机器人就会无限循环这条指令的步骤进行移动。指令有两种:
U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是,在 xy 平面上还有一些障碍物,他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
给定终点坐标(x, y),返回机器人能否完好地到达终点。如果能,返回true;否则返回false。
var robot = function (command, obstacles, x, y) {
let steps = 0; //当前步数
let options = command.split('');//把指令存到数组里面
let flag = 0; //标志位
let position = [0, 0]; //当前位置
do {
if (options[steps] === 'U') {
position[1] = position[1] + 1
} else {
position[0] = position[0] + 1
}
//无限循环滚动,未执行完步数加一,执行完则重置步数,steps是从0开始的所以数组长度需要-1
if (steps < options.length - 1) {
steps += 1
} else {
steps = 0
}
//碰到障碍物或者走到终点就结束
if (obstacles.length > 0) {
for (let i = 0; i < obstacles.length; i++) {
//不能用== 或 === 判断数组是否相等,因为数组是对象一种,只能判断是否是同一个实例化对象,必须比较每一个元素
if (position[0] === obstacles[i][0] && position[1] === obstacles[i][1]) {
flag = false
}
}
}
if (position[0] === x && position[1] === y) {
flag = true
}
//无限循环限制,任何一个坐标超过了其实就不能在到终点了
if (position[0] > x || position[1] > y) {
flag = false
}
} while (flag === 0);
return flag;
};
25. 井字棋获胜者(LeetCode)
题目描述:
A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下:
玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 “X” 作为棋子,而第二个玩家 B 总是用 “O” 作为棋子。
“X” 和 “O” 只能放在空方格中,而不能放在已经被占用的方格上。
只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏结束。
如果所有方块都放满棋子(不为空),游戏也会结束。
游戏结束后,棋子无法再进行任何移动。
给你一个数组 moves,其中每个元素是大小为 2 的另一个数组(元素分别对应网格的行和列),它按照 A 和 B 的行动顺序(先 A 后 B)记录了两人各自的棋子位置。
如果游戏存在获胜者(A 或 B),就返回该游戏的获胜者;如果游戏以平局结束,则返回 “Draw”;如果仍会有行动(游戏未结束),则返回 “Pending”。
你可以假设 moves 都 有效(遵循井字棋规则),网格最初是空的,A 将先行动。
var tictactoe = function (moves) {
let res = null;
let conditions = new Array(9);
if ( moves.length < 5) {
res = "Pending";
} else {
for (let i = 0; i < moves.length; i++) {
switch (moves[i].join('')) {
case '00' :
conditions[0] = i % 2 === 0 ? 'X' : 'O';
break;
case '01' :
conditions[1] = i % 2 === 0 ? 'X' : 'O';
break;
case '02' :
conditions[2] = i % 2 === 0 ? 'X' : 'O';
break;
case '10' :
conditions[3] = i % 2 === 0 ? 'X' : 'O';
break;
case '11' :
conditions[4] = i % 2 === 0 ? 'X' : 'O';
break;
case '12' :
conditions[5] = i % 2 === 0 ? 'X' : 'O';
break;
case '20' :
conditions[6] = i % 2 === 0 ? 'X' : 'O';
break;
case '21' :
conditions[7] = i % 2 === 0 ? 'X' : 'O';
break;
case '22' :
conditions[8] = i % 2 === 0 ? 'X' : 'O';
break;
default :
break;
}
}
let flag = [];
for (let j = 0; j < 8; j++) {
switch (j.toString()) {
case '0' :
flag.push((conditions[0] === conditions [1] && conditions[1] === conditions[2]) ? conditions[0] : null);
break;
case '1' :
flag.push((conditions[3] === conditions [4] && conditions[4] === conditions[5]) ? conditions[3] : null);
break;
case '2' :
flag.push((conditions[6] === conditions [7] && conditions[7] === conditions[8]) ? conditions[6] : null);
break;
case '3' :
flag.push((conditions[0] === conditions [3] && conditions[3] === conditions[6]) ? conditions[0] : null);
break;
case '4' :
flag.push((conditions[1] === conditions [4] && conditions[4] === conditions[7]) ? conditions[1] : null);
break;
case '5' :
flag.push((conditions[2] === conditions [5] && conditions[5] === conditions[8]) ? conditions[2] : null);
break;
case '6' :
flag.push((conditions[0] === conditions [4] && conditions[4] === conditions[8]) ? conditions[0] : null);
break;
case '7' :
flag.push((conditions[2] === conditions [4] && conditions[4] === conditions[6]) ? conditions[2] : null);
break;
default:
break;
}
}
//console.log(flag);
if(flag.includes('X')){
res = "A"
}else if(flag.includes("O")){
res = "B"
}else {
res = "Pending"
}
//console.log(res);
}
return res;
};
tictactoe([[0,2],[1,0],[2,2],[1,2],[2,0],[0,0],[0,1],[2,1],[1,1]]);
26. 访问所有点的最少时间(LeetCode)
题目描述: 平面上有 n 个点,点的位置用整数坐标表示 points[i] = [xi, yi]。请你计算访问所有这些点需要的最小时间(以秒为单位)。
你可以按照下面的规则在平面上移动:
每一秒沿水平或者竖直方向移动一个单位长度,或者跨过对角线(可以看作在一秒内向水平和竖直方向各移动一个单位长度)。
必须按照数组中出现的顺序来访问这些点。
var minTimeToVisitAllPoints = function(points) {
//求出两点之间的最短时间,其实就是找两个点所能构造的最大的正方形,在加上差值即可
let result = 0;
/**
* @return {number}
*/
function WithTwoPoints(pointA,pointB) {
let x = Math.abs(pointA[0]-pointB[0]);
let y = Math.abs(pointA[1]-pointB[1]);
return Math.min.apply(Math, [x, y]) + Math.abs(x - y);
}
for(var i=0;i<points.length-1;i++){
result = result + WithTwoPoints(points[i],points[i+1])
}
console.log(result);
};
minTimeToVisitAllPoints([[1,1],[3,4],[-1,0]]);
27 独一无二的出现次数(LeetCode)
题目描述:
给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false。
var uniqueOccurrences = function (arr) {
var res = []; //存储所有数字出现的次数,就是存储value即可
var flag = true;
var map = new Map();
for (let i = 0; i < arr.length; i++) {
//利用Map的数据结构统计次数
if (!map.has(arr[i])) {
map.set(arr[i], 1)
} else {
map.set(arr[i], map.get(arr[i]) + 1)
}
}
for (let value of map.values()) {
res.push(value)
}
//现在只需要判断res这个数组是否有重复值即可知道是否独一无二
let obj = {};
for (let j = 0, length = res.length; j < length; j++) {
obj[res[j]] = j;
}
if (res.length !== Object.keys(obj).length) {
flag = false
}
return flag;
};
uniqueOccurrences([1,2,2,1,1,3]);
28. 奇数值单元格
题目要求:
给你一个 n 行 m 列的矩阵,最开始的时候,每个单元格中的值都是 0。
另有一个索引数组 indices,indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列(从 0 开始编号)。
你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
请你在执行完所有 indices 指定的增量操作后,返回矩阵中 「奇数值单元格」 的数目。
var oddCells = function (n, m, indices) {
// var arr = Array.apply(null,Array(n)).map(() => new Array(m));
// var arr = new Array(n).fill(new Array(m).fill(0));
//初始化数组
var arr = new Array(n);
for(var len = 0;len< n; len++){
arr[len] = new Array(m).fill(0)
}
//开始赋值
var res = 0;
for (var i = 0; i < indices.length; i++) {
//处理所有行
arr[indices[i][0]].forEach(function (currentValue, index) {
arr[indices[i][0]][index] += 1;
});
//处理所有列
arr.forEach(function (currentValue, index) {
arr[index][indices[i][1]] += 1;
})
}
//判断奇数偶数
for (var j = 0; j < arr.length; j++) {
arr[j].forEach(function (currentValue) {
if (currentValue % 2 !== 0) {
res += 1
}
})
}
return res;
};
oddCells(2, 3, [[0, 1], [1, 1]]);
29.找出数组中出现次数最多和最少的元素
题目: 给出一个数组,找出数组中出现次数最多和最少的元素,并且给出现的次数,暂时不考虑空数组。
思路:
利用map数据结构(实际上object和set也可以)的key不重复的特点,采用key-value存储元素和他出现的次数;
再遍历map选择出出现次数最多的和次数最少的分别存储到max和min中,注意min初始值必须是存在的,但是不能在这里直接把key也拿出来,因为出现最多或者最少次数的元素可能都不只是一个;
最后再次遍历map,把值为最多最少的元素分别存储到各自的res结果集中。
let arr = [1, 1, 2, 2, 2, 6, 6, 2, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 0];
function f(arr) {
let map = new Map();
for (let i = 0; i < arr.length; i++) {
if (!map.has(arr[i])) {
map.set(arr[i], 1)
} else {
let data = map.get(arr[i]) + 1;
map.set(arr[i], data)
}
}
let max = 0;
let min = map.get(arr[0]);
let Maxres = [];
let Minres = [];
map.forEach(function (value, key, map) {
if (value > max) {
max = value
}
if (value < min) {
min = value
}
});
map.forEach(function (value, key, map) {
if (max === value) {
Maxres.push(key)
}
if (min === value) {
Minres.push(key)
}
});
console.log(`出现次数最多的元素有${Maxres},出现了${max}次。`);
console.log(`出现次数最少的元素有${Minres},出现了${min}次。`);
}
f(arr);
30.找出数组中的单独数字
题目: 1001个数 500成对相同 找出落单数 要求O(n)时间 O(1)空间。
思路:从头部和尾部分别遍历这个数组,如果发现同一个元素在数组中出现的序号一致,说明这个元素是单独存在的。
(function f(arr) {
let res = arr[6];
for(let i=0;i<6;i++){
if(arr.indexOf(arr[i]) === arr.lastIndexOf(arr[i])){
res = arr[i]
}
}
console.log('res',res)
})([1,3,1,11,5,3,6,4,9,6,9,4,5]);
31.鲜食制作排风系统时间段启停
题目: 便利蜂门店里面有一个新鲜食品制作的区域,在这个区域里面,每天早晨、中午、晚上的一些时段,会制作早餐、午餐、晚餐。
当前有一个能耗节约的项目,需要动态控制这个食品制作区域的排风装置,控制的策略上,时如下的两个约束条件:
(1)在全部的食品制作时间段内,制作时间段前后30分钟,开启排风装置(将制作区域里面制作导致的热空气抽出去);其他时间段,关闭排风装置。
(2)为了避免排风装置频繁停启,规定排风装置的每一段关闭时间段长度应该大于60分钟,否则就不予关闭,即关闭时间不足30分钟就一直保持开启状态。
比如:
一家门店制作事件段是:
[05:30,07:30),[10:30,11:30),[12:30,13:00),[16:30,17:30)
按照上述规则,我们排风装置在如下时间段打开:
[05:00,08:00),[10:00,13:30),[16:00,18:00)
精确到分钟,每天按照1440分钟来计算,上述时间段分别对应如下输入输出:
input:【330,450,630,690,750,990,1050】
output:【300,480,600,810,960,1080】
构造一个算法,完成输入到输出的过程,为了简化算法,输入数据直接用分钟(上面的input)表示,且不会出现元素数是奇数个,数值不是单调递增等情况,需要考虑边界值,如input首末数字分别是0,1439(一天是1440分钟)时,putput将是-30,1469.
思路:step1:先处理开关时间段,解决了各个时间段开启关闭时间,也处理了边界值。
step2:卡点,处理各个时间段的衔接部分,即间隔时间是不是大于60分钟
step3:小于60分钟的时间段需要合并,用·delete· 标记
step4:把detele标记的数据删掉,返回最后的result
function test(params) {
let res = [];
let len = params.length / 2 - 1;
//处理开关时间段 step1
for(let i=0;i<params.length;i++){
if(i % 2 ===0){
res.push(params[i] - 30)
}else {
res.push(params[i] + 30)
}
}
//处理待处理位置 step2
let data = [];
for(let m=0;m<len;m++){
data.push(2*m+1)
}
//处理需要合并的地方 step3
for(let j=0;j<len;j++){
if(res[data[j] + 1] - res[data[j]] < 60 ){
res[data[j]] = 'delete';
res[data[j] + 1] = 'delete';
}
}
//合并时间段,整合最后结果 step4
for(let k=0;k<res.length;k++){
if(res[k] === 'delete'){
res.splice(k,2)
}
}
return res
}
let arr = [330,450,630,690,750,780,990,1050]; // 这里是获取的输入
let res = test(arr);//把arr传入test函数
console.log(res);
32.小度买多少瓶果汁
function bottle(n,k,arr) {
let map = new Map();
for(let i=0;i<n;i++){
if(!map.has(arr[i])){
map.set(arr[i],1)
}else {
map.set(arr[i],map.get(arr[i])+1)
}
}
for(let item of map){
if(item[1] % 2===0){
n = n-item[1] / 2
}else {
n= n- (item[1]-1) / 2
}
}
return n
}
console.log(bottle(5,3,[1,2,3,1,2]));
33.火柴摆列数字最大
下面解法不对 没做完。。。。
function test(n,m,list) {
let map = new Map([[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]);
let arr = [[]];
let obj = {};//可以摆出的数字 3 7 8 4 // 5 3 7 4
let res = [];
for(let i=0;i<m;i++){
obj[`${list[i]}`] = map.get(list[i])
// arr.push([list[i],map.get(list[i])]); // 升级为二维数组
}
// 写出所有的解法
// 找出数位最多的一组或几组解
for(let j=0;j<arr.length;j++){
arr[j] = arr[j].sort((a,b) => { return a-b})
}
// 排序,然后组成数字,返回最大值
}
34.一组平行线相同数字连线不交叉
function line(arr1,arr2) {
let m =arr1.length ;
let n = arr2.length ;
let result = 0;
let dp = [] ;
for(let s=0;s<m+1;s++){
dp.push(new Array(n+1))
}
for(let i=0;i<m;i++){
for(let j=0;j<n;j++){
if(i== 0 || j==0){
dp[i][j] = 0
} else if(arr1[i-1]==arr2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1
}else {
dp[i][j] = Math.max.call(Math,dp[i-1][j],dp[i][j-1]);
}
}
}
console.log(dp[m][n])
return dp[m][n]
}
console.log(line([1,4,2],[1,2,4]))
35.含有对象的数组去重
function uniqObjInArray(objarray) {
let len = objarray.length;
let tempJson = {};
let res = [];
for (let i = 0; i < len; i++) { //取出每一个对象
tempJson[JSON.stringify(objarray[i])] = true;
}
let keyItems = Object.keys(tempJson);
for (let j = 0; j < keyItems.length; j++) {
res.push(JSON.parse(keyItems[j]));
}
return res;
}
36.买卖股票最大时机
function f(arr) {
if(arr.length==0) return 0 ;
let max = 0;
let min = 0;
min = arr[0];
for(let i = 0;i<arr.length - 1;i++){
if(arr[i]>arr[i+1]) {
min = Math.min(min,arr[i+1]);
} else{
max = Math.max(max, arr[i+1] - min);
}
}
return max;
}
console.log(f([7,1,5,3,6,4]))
37.判断url中参数
function f(url,params) {
let index = url.indexOf('?');
let allParams = url.slice(index + 1);
let data = allParams.split("&");
console.log('data=====>',data);
let res = false;
for(let i=0;i<data.length;i++){
let item = data[i].split("=");
if(item[0] === params){
res = true;
}
}
return res;
}
let url = 'http://www.google/?q=sangfor';
let params = 'q';
console.log(f(url,params));
38.兔子繁殖
function test(n,m,p,arr,x){
let result = [];
result.push(0);//暂存一只海豚
for(let i=0;i<x;i++){ //遍历所有的年份
for(let j=0;j<result.length;j++){
result[j] = result[j] + 1; //首先自增一岁
}
for(let k=0;k<result.length;k++){
if(result[k] > m){ //超龄的话就删除,并改变原数组长度
result.splice(k,1)
}
if(arr.includes(result[k])){//符合生育年龄增加一个为0岁的数据
result.push(0)
}
}
}
return n * result.length;//n只海豚是同样的结果
}
console.log(test(5,5,2,[2,4],5));
}
console.log(test(7));
39.根据经纬度获得两点距离
/**
* @return {number}
*/
function GetDistance( lat1, lng1, lat2, lng2){
var radLat1 = lat1*Math.PI / 180.0;
var radLat2 = lat2*Math.PI / 180.0;
var a = radLat1 - radLat2;
var b = lng1*Math.PI / 180.0 - lng2*Math.PI / 180.0;
var s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a/2),2) +
Math.cos(radLat1)*Math.cos(radLat2)*Math.pow(Math.sin(b/2),2)));
s = s *6378.137 ; // EARTH_RADIUS;
s = Math.round(s * 10000) / 10000;
console.log(s);
return s;
}
// return的距离单位为km
GetDistance( 36.658613116840925,114.58875406432438, 36.61632,114.49073);
function getDistance(e1, n1, e2, n2){
const R = 6371;
const { sin, cos, asin, PI, hypot } = Math;
/** 根据经纬度获取点的坐标 */
let getPoint = (e, n) => {
e *= PI/180;
n *= PI/180;
//这里 R* 被去掉, 相当于先求单位圆上两点的距, 最后会再将这个距离放大 R 倍
return {x: cos(n)*cos(e), y: cos(n)*sin(e), z: sin(n)}
};
let a = getPoint(e1, n1);
let b = getPoint(e2, n2);
let c = hypot(a.x - b.x, a.y - b.y, a.z - b.z);
let r = asin(c/2)*2*R;
console.log('r1',r);
return r
}
getDistance(36.6652816800,114.5983279000,32.8124280500,113.0997531000)
/**
* @return {number}
*/
function GetDistance( lat1, lng1, lat2, lng2){
var radLat1 = lat1*Math.PI / 180.0;
var radLat2 = lat2*Math.PI / 180.0;
var a = radLat1 - radLat2;
var b = lng1*Math.PI / 180.0 - lng2*Math.PI / 180.0;
var s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a/2),2) +
Math.cos(radLat1)*Math.cos(radLat2)*Math.pow(Math.sin(b/2),2)));
s = s *6378.137 ;// EARTH_RADIUS;
s = Math.round(s * 10000) / 10000;
console.log('r2',s);
return s;
}
// 调用 return的距离单位为km
GetDistance(36.6652816800,114.5983279000,32.8124280500,113.0997531000);
40 海豚繁殖
题目: 海洋馆目前有n只小海豚,初始均为0岁,每只小海豚的寿命都是m岁,并且这些小海豚在birthYear[i] 年会生产一位海豚宝宝(1 <= birthYear[i] <= m),每个海豚宝宝刚刚出生都是0岁。
问 x 年时海洋馆有多少个宝宝?
function test(n,m,p,arr,x){
let result = [];
result.push(0);//一只海豚
for(let i=0;i<x;i++){ //遍历所要求的年份
for(let j=0;j<result.length;j++){
result[j] = result[j] + 1; //首先自增一岁
}
for(let k=0;k<result.length;k++){
if(result[k] > m){ //超龄的话就删除
result.splice(k,1)
}
if(arr.includes(result[k])){//符合生育年龄增加一个为0岁的数据
result.push(0)
}
}
}
return n * result.length;
}
console.log(test(5,5,2,[2,4],5)); // 20
41得到一个整数的逆反数
题目: 逆反数是把一个整数每一位上的数字进行反转得到的,
如:123 ⇒ 321 -123 ⇒ -321 120 =>21
输入一个32位有符号整数,得到相反数。
function inverse(params) {
let arr = params.toString().split('');
let result = 0;
if(arr[0] === '-'){
let len = arr.length -1;
arr.reverse().splice(len,1);
result = arr.join('');
result = '-' + Number(result).toString();
}else {
result = arr.reverse().join('');
}
return Number(result)
}
console.log(inverse(123));
43 计算接雨水量
// 时间复杂度高
function rain(arr) {
if (arr.length < 3) {
return 0;
}
let count = 0,
leftMax = [arr[0]],
rightMax = [];
// 从左向右扫描,获取除两端之外的每个位子左侧的最高值
for (let i = 1; i <= arr.length - 2; i++) {
leftMax[i] = Math.max(leftMax[i - 1], arr[i - 1]);
}
rightMax[arr.length - 1] = arr[arr.length - 1];
// 从右向左扫描,获取除两端之外的每个位子右侧的最高值
for (let i = arr.length - 2; i >= 1; i--) {
rightMax[i] = Math.max(rightMax[i + 1], arr[i + 1]);
}
for (let i = 1; i <= arr.length - 2; i++) {
let increment = Math.min(leftMax[i], rightMax[i]) - arr[i];
count = increment > 0 ? count + increment : count;
}
return count
}
console.log(rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
//【10,1,0,2,1,0,1,3,2,1,2,10】 =》 87
//时间复杂度低
function trap(arr) {
let left = 0;
let right = arr.length - 1;
let res = 0;
let left_max = 0;
let right_max = 0;
while (left < right) {
if (arr[left] < arr[right]) {
if (arr[left] >= left_max) {
left_max = arr[left]
}
res += (left_max - arr[left]);
left++
} else {
if (arr[right] >= right_max) {
right_max = arr[right]
}
res += (right_max - arr[right]);
right--
}
}
return res
};
console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
44 股票最佳时机(有冻结期)
function max_profit(prices){
let n = prices.length;
if(n === 0){
return 0;
}
let arr = Array.from(new Array(n),() => new Array(2)); //创建二维数组
for(var i = 0;i < n;i++){
if(i === 0){
arr[0][0] = 0;
arr[0][1] = -prices[i];
continue;
}else if(i === 1){
arr[1][0] = Math.max(arr[0][0],arr[0][1]+prices[i]);
arr[1][1] = Math.max(arr[0][1], - prices[i]);
continue;
}
arr[i][0] = Math.max(arr[i-1][0],arr[i-1][1] + prices[i]);
arr[i][1] = Math.max(arr[i-1][1],arr[i-2][0] - prices[i]);
}
return arr[n-1][0];
}
console.log(max_profit([1,2,3,0,2]));
42 无题
//思路:因为是环屏,所以可以起始点的不同可以组成个数组,这n个数组都调用maxScore函数(这个函数是为了找出单个数组最大的和),
//最后将结果集中的最大值选择出来即可。
function main(){
var n = parseInt(readline());
var result = [];
while(line=readline()){
var lines = line.split(" ");
}
for(var i=0;i<n;i++){
var data1 = lines.slice(i,n);
var data2 = lines.slice(0,i);
var data = data1.concat(data2);
result.push(maxScore(data));
}
// console.log(result[1])
console.log(Math.max.apply(Math,result))
}
function maxScore(arr) {
var currentRes = arr[0];
var res = arr[0];
var len = arr.length;
for (let i = 0; i < len; i++) {
if (currentRes > 0) {
currentRes += arr[i];
} else {
currentRes = arr[i]
}
if (currentRes > res) {
res = currentRes
}
}
return parseFloat(res);
}
main()
43. 行星碰撞-(栈)
给定一个整数数组 asteroids,表示在同一行的行星。
对于数组中的每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向(正表示向右移动,负表示向左移动)。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞。
实例:
输入:asteroids = [5,10,-5]
输出:[5,10]
解释:10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
/**
* @param {number[]} asteroids
* @return {number[]}
*/
var finished = false;
var asteroidCollision = function (asteroids) {
let result = [...asteroids];
do {
result = digui(result);
} while (!finished);
return result;
};
function digui(asteroids) {
let result = [...asteroids];
if(result.length < 2){
finished = true;
return result;
}
let newStep = 0;
for (let i = 0; i < asteroids.length; i++) {
if (asteroids[i] > 0 && asteroids[i + 1] < 0) {
if (Math.abs(asteroids[i]) > Math.abs(asteroids[i + 1])) {
result[i + 1] = 0;
newStep = newStep + 1;
} else if (Math.abs(asteroids[i]) == Math.abs(asteroids[i + 1])) {
result[i] = 0;
result[i + 1] = 0;
newStep = newStep + 1;
} else {
result[i] = 0;
newStep = newStep + 1;
}
}
}
if (newStep == 0) {//某次遍历完成后没有任何一个行星碰撞则递归结束
finished = true;
}
let res = [];
result.forEach((item) => { if (item !== 0) { res.push(item) } });
return res;
}
console.log(asteroidCollision([10, 2, -5]))
本文标签:
版权声明:本文标题:编程题总结 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1730038452a1220239.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论