编程题总结

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]))

本文标签：