水题题解

发表于 | 分类于 | 阅读次数:

对不起，我只做水题，前端就是可以为所欲为。

笔试

大疆——格式化字符串

输入：1212320000.11

输出：1,212,320,000.11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function formatFloat(num){
    //按小数点切割字符串
    let strArr = String(num).split('.');
    //将整数部分切割成数组
    let strAArr = strArr[0].split('');
    //整数部分小于等于3，返回原结果
    if(strAArr.length <= 3){
        return num;
    }
    //旧数组从后出队，新数组从头插入，判断新数组长度，插入逗号
    let newStr = [];
    let len = strAArr.length;
    for(let i = 0 ; i < len ; i++){
        if((i)%3 === 0 && i !== 0){
            newStr.unshift(",");
        }
        newStr.unshift(strAArr.pop());
    }
    newStr = newStr.join('');
    return newStr+'.'+strArr[1];
}

console.log(formatFloat(1212320000.11))


num.toLocaleString()

求区间内的素数(只能被1个本身相除)

1
2
3
4
5
6
7
8
9
10
11
12
13
function isPrimeNumber( num ) {
    if ( num == 1 ) return false;
    for (var i = 2; i <= Math.sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}
var primes = [ ];
for(var i=100; i<=200; i++) {
    if ( isPrimeNumber(i) ) primes.push(i);
}
console.log(primes);
// [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

牛客

2018-08-05

dp-拼凑面额

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var num = parseInt(readline());
var arr = [1,5,10,20,50,100];
var dp = new Array(num+1);
for(var i = 0;i<dp.length;i++){
    dp[i] = 0;
}
dp[0]=1;
for(var i=0; i<arr.length; i++){
    for(var j=1; j<dp.length; j++){
        if(j >= arr[i]){
            dp[j] = dp[j] + dp[j-arr[i]];
        }
    }
}
console.log(dp[num]);

进制转化

给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数 

1
2
3
4
5
6
7
8
var line = readline();
line = line.split(" ");
function change(str1,str2){
    str1 = parseInt(str1);
    str2 = parseInt(str2);
    console.log(((str1).toString(str2)).toUpperCase());
}
change(line[0],line[1]);

十进制X转化为N进制：(X).toString(N)，X与N都是Number类型。str.toUpperCase，转化为大写。

正则

读入一个字符串str，输出字符串str中的连续最长的数字串 (数字串本身不需要连续递增，一直理解错了。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function LargeSubString(str){
    var reg = /[0-9]+/g;
    var list = str.match(reg);
    var max = 0, index = 0;
    console.log(list);
    for (var i = 0, n = list.length; i < n; i++) {
        if (list[i].length > max) {
            max = list[i].length;
            index = i;
        }
    }
    return list[index];
}
console.log(LargeSubString("abcd12345ed125ss123"))

2018-07-11

阶乘——末尾0的个数

题解：输入一个整数，求这个整数的阶乘结果末尾有多少个0。

输入：10

输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function count(n){
    var count=0;//暴力破解方法当数值较大时，result为Infity
    while(n){
        var num=parseInt(n/5);//末尾0的个数表示多少个10，而10的形成受2*5的影响，
        //由于2的个数大于5，所以按照5的个数确定10的个数
        count=count+num;
        n=num;
    }
    return count;
}
 
line=readline()
var lines=line.split(' ');
var a=parseInt(lines[0]);
print(count(a))

数学——计算糖果

题解：输入为一行，一共4个整数，分别为A - B，B - C，A + B，B + C，用空格隔开。 范围均在-30到30之间(闭区间)。输出为一行，如果存在满足的整数A，B，C则按顺序输出A，B，C，用空格隔开，行末无空格。 如果不存在这样的整数A，B，C，则输出No

输入：1 -2 3 4

输出：2 1 3

1
2
3
4
5
6
7
8
9
10
11
12
var line = readline();
var lines = line.split(' ');
var m = parseInt(lines[0]),n = parseInt(lines[1]),p = parseInt(lines[2]),q = parseInt(lines[3]);
var A = (m + p)/2,B = (n + q)/2,C = q - B;
function isInteger(obj) {
    return obj%1 === 0
}
if(A>=0 && B>=0 && C>=0 && isInteger(A) && isInteger(B) && isInteger(C)){
    print(A+' '+B+' '+C);
}else{
    print('No');
}

数列求和

题解：数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。 输入数据有多组，每组占一行，由两个整数n（n < 10000）和m(m < 1000)组成，n和m的含义如前所述。

输入：

81 4

2 2

输出（保留2位小数）：

94.73
3.41

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while(line = readline()){
    line = line.split(' ');
    let len = Number(line[1]);
    line[0] = parseInt(line[0]);
    let i = 1;
    let sum = line[0];
    let last = line[0];
    while(i < len){
        let temp = Math.sqrt(last);
        sum = sum + temp;
        last = temp;
        i++;
    }
    print(sum.toFixed(2));
}

正则表达式——小易喜欢的单词

题解：

小易喜欢的单词具有以下特性：

1.单词每个字母都是大写字母

2.单词没有连续相等的字母

3.单词没有形如“xyxy”(这里的x，y指的都是字母，并且可以相同)这样的子序列，子序列可能不连续。 

1
2
3
4
5
6
7
8
9
10
11
while(line = readline()){
    var str = line.trim();
    var pattern1 = /[a-z]/;                    	//存在小写字母
    var pattern2 = /(\w)\1/;                    //存在连续字母
    var pattern3 = /(\w)\w*(\w)\w*\1\w*\2/      //存在交叉字母
    if(str.match(pattern1) || str.match(pattern2) || str.match(pattern3)){
        print("Dislikes");
    }else{
        print("Likes");
    }
}

集合

题解：判断第二个字符串是否为第一个字符串的子串（顺序从左至右），是输出Yes，否则输出No

输入：x.nowcoder.com

输出：Yes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  var len1=arr1.length;
    var len2=arr2.length;
    var j=0;
    for(let i=0; i<len1; i++){
        if(arr1[i]===arr2[j]){
            j++;
        }
    }
    if(j===len2){
        return "Yes";
    }else{
        return "No";
    }
}
var str1=readline();
var str2=readline();
console.log(judge_is_child_str(str1,str2));

2018-07-10

正则表达式——删除公共字符

题解：给定2个字符串s1，s2，将s1中出现的s2元素删除

输入：They are students. aeiou

输出：Thy r stdnts.

1
2
3
4
5
6
7
8
9
10
11
var s1 = readline();
var s2 = readline().split('');

for(let i = 0 ; i < s2.length ; i ++){
    let reg = new RegExp(s2[i],'g');
    s1 = s1.replace(reg,'');
}
print(s1);

//另一种思路
//将s1按空格拆分，然后对数组中每个单词进行去除操作。

字符串/数组操作——filename extension

题解：给定文件路径，求文件后缀

输入：Abc/file.txt

输出：txt

1
2
3
4
5
6
7
8
9
10
11
function getExtension(str){
    var strArr = str.split(".");
    if(!strArr[1]){
        print("null");
        return ;
    }
    //console.log(strArr);
    print(strArr[1]);
}
var str = readline();
getExtension(str);

2018-07-08

数组/字符串操作——求回文数

题解：输入2个字符串A，B，将B插入A中，求新的A是回文数的个数。

输入：aba b

输出：2 （baba，abba，abba，abab，有2个abba）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var count = 0;
function reverse(str){
    return str.split('').reverse().join('');
}
function isTrue(strA,strB){
    let strAArray = strA.split('');
    for(let i = 0 ; i <= strA.length ; i++){
        strAArray.splice(i,0,strB);
        var newStr = strAArray.join('');
        if(newStr === reverse(newStr)){
            count++;
        }
        strAArray = strA.split('')
    }
}
var lineA = readline();
var lineB = readline();
//line = line.split(' ');
isTrue(lineA,lineB);
print(count);

2018-07-07

数字分析——买苹果

题解：小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入：输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出：输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//分三种情况，假设苹果个数n
//情况一：若n不是偶数，直接返回-1
//情况二：若 n%8 = 0，则返回n/8
//情况三：若 n%8 ！= 0；则只需回溯1次或2次8包装购买个数，就可以求解。（偶数个苹果对8取模，余数[0,2,4,6],[0,6]情况下直接模6，2则回溯2次8包装，（16+2）%6，4则回溯一次，（8+4）%6）。
var n=parseInt(readline());
var m=n%8;
var result=Math.floor(n/8);
if(m%6==0){
    result+=m/6;
    print(result);
}else if((m+8)%6==0){
    result+=(m+8)/6-1;
    print(result);
}else if((m+16)%6==0){
    result+=(m+16)/6-2;
    print(result);
}else{
    print(-1);
}

数组过滤——n个数里出现次数大于等于n/2的数

题解：输入n个整数，输出出现次数大于等于数组长度一半的数。 每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。

输入：3 9 3 2 5 6 7 3 2 3 3 3

输出：3

1
2
3
4
5
6
7
8
9
10
11
12
13
while(line = readline()){
    line = line.split(' ');
    var count = [];
    for(var i = 0 ; i < line.length ; i ++){
         count = line.filter((a)=>{
             return a == line[i];
         })
         if(count.length >= (line.length/2)){
             print(count[0]);
             break;
         }
    }
}

数组操作——下厨房

题解：牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。 每个输入包含 1 个测试用例。每个测试用例的第 i 行，表示完成第 i 件料理需要哪些材料，各个材料用空格隔开，输入只包含大写英文字母和空格，输入文件不超过 50 行，每一行不超过 50 个字符。

输入：BUTTER FLOUR

HONEY FLOUR EGG

输出：4

1
2
3
4
5
6
7
8
9
10
11
var resultArr = [];

while(line = readline()){
    line = line.split(' ');
    for(var i = 0 ; i < line.length ; i++){
        if(resultArr.indexOf(line[i]) == -1){
            resultArr.push(line[i]);
        }
    }
}
print(resultArr.length)

数字翻转——数组操作

题解：对于一个整数X，定义操作rev(X)为将X按数位翻转过来，并且去除掉前导0。例如: 如果 X = 123，则rev(X) = 321; 如果 X = 100，则rev(X) = 1. 现在给出整数x和y,要求rev(rev(x) + rev(y))为多少？ 

1
2
3
4
5
6
7
8
function reverse(str){
    var rev = str.split('').reverse().join('');
    return parseInt(rev);
}
var line = readline();
line = line.split(' ');

print(reverse(String(reverse(line[0])+reverse(line[1]))))

数组操作、进制转化——幸运数

题解：小明同学学习了不同的进制之后，拿起了一些数字做起了游戏。小明同学知道，在日常生活中我们最常用的是十进制数，而在计算机中，二进制数也很常用。现在对于一个数字x，小明同学定义出了两个函数f(x)和g(x)。 f(x)表示把x这个数用十进制写出后各个数位上的数字之和。如f(123)=1+2+3=6。 g(x)表示把x这个数用二进制写出后各个数位上的数字之和。如123的二进制表示为1111011，那么，g(123)=1+1+1+1+0+1+1=6。 小明同学发现对于一些正整数x满足f(x)=g(x)，他把这种数称为幸运数，现在他想知道，大于0且小于等于n的幸运数有多少个？ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var count = 0;
//计算十进制时的和
function num2Ten(num){
    num = num.split('');
    var sum = num.reduce((a,b)=>{
        return parseInt(a)+parseInt(b)
    });
    return sum;
}
//计算二进制时的和
function num2Two(num){
    num = (num).toString(2).split('');
    var sum = num.reduce((a,b)=>{
        return parseInt(a)+parseInt(b);
    });
    return sum
};
var line = parseInt(readline());
for(var i = 1 ; i <= line ; i++){
    if(num2Ten(String(i)) == num2Two(i)){
        count++;
    }
}
print(count);

递归——Fibonacci数列

题解：Fibonacci数列是这样定义的： F[0] = 0 F[1] = 1 for each i ≥ 2: F[i] = F[i-1] + F[i-2] 因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。 

1
2
3
4
5
6
7
8
9
var n = Number(readline());
var fn = []; fn[0] = 0; fn[1] = 1;
var i = 1;
while(n > fn[i]){
    fn[i+1] = fn[i] + fn[i-1];
    i++;
}
var min = Math.min(fn[i]-n,n-fn[i-1]);
print(min);

递归——美团-网格走法

题解：有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。

这是一个典型的递归算法问题，因为每次走法必须是往右或者是往下，因此不管是到达那个点，它的必经之路一定是它上方或者左方相邻的那个点，因此可以得出一个递归表达式：f[m][n]=f[m-1][n]+f[m][n-1]；这个递归表达式的条件为m,n都不为0的时候，除了这个表达式还需要写出一个已知条件，f[0][0] = 0;f[{1->m}][0] = 1;f[0][{1->n}] = 1;这样就可以解出最终f[m][n]的值了 

1
2
3
4
5
6
7
8
9
10
11
12
var line = readline();
var lineArr = line.split(' ');
var m = parseInt(lineArr[0]);
var n = parseInt(lineArr[1]);
function move(m,n){
    if(m == 0 || n == 0){
        return 1;
    }else{
        return move(m-1,n)+move(m,n-1);
    }
}
print(move(m,n));

递归——网易-解救小易

题解：有一片1000*1000的草地，小易初始站在(1,1)(最左上角的位置)。小易在每一秒会横向或者纵向移动到相邻的草地上吃草(小易不会走出边界)。大反派超超想去捕捉可爱的小易，他手里有n个陷阱。第i个陷阱被安置在横坐标为xi ，纵坐标为yi 的位置上，小易一旦走入一个陷阱，将会被超超捕捉。你为了去解救小易，需要知道小易最少多少秒可能会走入一个陷阱，从而提前解救小易。

解救小易可以简单理解为从左上角到所有点中步数最小值，因为题中说明了每次都只能横走一步或者纵走一步，所以只需要将要到达的点的横纵坐标进行相加然后减去原始位置1+1即表示到达该点所需要走的步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var num = parseInt(readline());			//陷阱个数
var xNum = (readline()).split(' ');		//x轴坐标数组
var yNum = (readline()).split(' ');		//y轴坐标数组
var resultArr = [];						//各个陷阱的距离数组
function getMove(a,b){
    return a+b-2;
}
for(let i = 0 ; i < xNum.length ; i++){
    var a = parseInt(xNum[i]);
    var b = parseInt(yNum[i]);
    resultArr.push(getMove(a,b));
}
resultArr.sort((a,b)=>{
    return a-b;
})
print(resultArr[0]);

leetcode

2018-08-08更新

leetcode-414-Third Maximum Number

题解：输出数组中第三大的值

输入：[1,2,3]

输出：1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var thirdMax = function(nums) {
    //去重
    nums = Array.from(new Set(nums));
    //排序
    nums = nums.sort((a,b)=>{
        return a-b;
    })
    
    if(nums.length < 3){
        return nums[nums.length-1];
    }else{
        return nums[nums.length-3];
    }
};

leetcode-283-Move-zeroes

题解：在不适用额外空间的情况下，删除数组中的0，并置于数组最后

输入：[0,1,0,3,12]

输出：[1,3,12,0,0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var moveZeroes = function (nums) {
    var zeroes = 0;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            nums.splice(i, 1);
            i--;		//学习了
            zeroes++;
        }
    }
    while (zeroes) {
        nums.push(0);
        zeroes--;
    }
};

2018-07-04更新

leetcode-78-Subsets

题解：输出集合的全部子集。

输入：[1,2,3]

输出：[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//遍历原数组，生成子集，每轮子集的生成，都依赖之前的子集，直至原集合遍历结束。
var subsets = function(nums) {
    if(!nums || nums.length < 0){
        return [];
    }
    let returnArr = [[]];
    nums.forEach(num=>{
        let len = returnArr.length;
        let i = 0;
        //遍历之前生成的自己，插入新元素，生成新的子集
        while (i < len){
            let tempArr = returnArr[i].slice(0);
            tempArr.push(num);
            returnArr.push(tempArr);
            i++;
        }
    })
    return returnArr;
};

2018-07-02更新

leetcode-383-Ransom Note

题解：给定字符串1和字符串2，若字符串1能从字符串2中构造出来，返回true，否则返回false。

样例：”aa”,”aba”

输出：”true”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    let newRansomNote = ransomNote.split("");
    let newMagazine = magazine.split("");
    for(let i = 0 ; i < newRansomNote.length ; i++){
        let index = newMagazine.indexOf(newRansomNote[i]);
        if(index === -1){
            return false;
        }else{
            newMagazine.splice(index,1);
        }
    }
    return true;
};

leetcode-169-Majority Element

题解：给定一个数字数组，如果数组中存在重复元素，返回true，否则，返回false

样例：[1,2,3,1]

输出：true

1
2
3
4
5
6
7
8
9
10
var containsDuplicate = function(nums) {
    //去重
    let newArr = Array.from(new Set(nums));
    //判断去重后数组长度与原数组长度是否相等
    if(newArr.length === nums.length){
        return false;
    }else{
        return true;
    }
};

2018-07-01更新

leetcode-217-Contains Duplicate

题解：给定一个数组，将数组向右旋转k步，其中 k 为非负数。

样例：[1,2,3,4,5,6,7]，k=3

输出：[5,6,7,1,2,3,4] ([7,1,2,3,4,5,6]->[6,7,1,2,3,4,5]->[5,6,7,1,2,3,4])

1
2
3
4
5
var rotate = function(nums, k) {
  for(let i = 0 ; i < k ; i ++){
    nums.unshift(nums.pop());
  }
};

leetcode-169-Majority Element

题解：给定一个非空数组，找出一个目标元素，目标元素在数组中出现的次数要大于（数组长度/2 ）向下取整。

样例：[2,2,1,1,1,2,2]

输出：2（2出现的次数为4，4>7/2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var majorityElement = function(nums) {
  //新建一个数组，去重，遍历这个去重之后的数组，优化效率，不会超时
  let simpleArray = Array.from(new Set(nums));
  for(let i = 0 ; i < simpleArray.length ; i ++){
    let element = simpleArray[i];
    let count = nums.filter((a)=>{
      return a === element;
    });
    if(count.length > Math.floor(nums.length/2)){
      return simpleArray[i];
    }
  }
  return 0;
};

2018-06-20更新

leetcode-121-Best Time to Buy and Sell Stock

题解：给定一个数组，n个元素表示n天，每个元素代表当天股票的价格，求最大利润（买入-卖出）。假设第i天的价格最低是n，第k天的价格最大是m，maxprofit = m-n，其中i<k。

样例：[7,1,5,3,6,4]

输出：5。（第二天1元，第5天6元，6-1=5）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let maxProfit = function (prices) {
    if(!prices || prices.length <= 1){
        return 0;
    }
    let profitArr = [];     //存放每一轮得出的差值
    let maxProfitArr = [];  //存放每一轮的最大值
    for(let i = 0 ; i < prices.length ; i++){
        let temp = prices[i];
        for(let j = i+1 ; j < prices.length ; j++){
            profitArr.push(prices[j]-temp);
        }
        maxProfitArr.push(Math.max(...profitArr));
        //中间数组用完清空
        profitArr = [];
    }
    let max = Math.max(...maxProfitArr);
    if(max <= 0){
        return 0 ;
    }else{
        return max;
    }
}
console.log(maxProfit([7,1,5,3,6,4]))

leetcode-122-Best Time to Buy and Sell Stock II

题解：假设有一个数组，其中第i 个元素是第i天给定股票的价格。 设计一个算法来找到最大的利润。您可以根据需要完成尽可能多的交易（即多次买入和卖出一次股票）。注意：不得同时进行多笔交易（即您必须在再次购买之前出售股票）。

输入：[7,1,5,3,6,4]

输出：7（在第2天买入（价格= 1）并在第3天卖出（价格= 5），利润= 5-1 = 4。然后在第4天购买（价格= 3）并在第5天卖出（价格= 6），利润= 6-3 = 3。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let maxProfit = function (prices) {
    if(prices == null || prices.length <= 1){
        return 0;
    }
    let profit = 0;
    for(let i = 1 ; i < prices.length ; i++){
        let fast = prices[i];
        let slow = prices[i - 1];
        if(fast > slow){
            profit += fast - slow;
        }
    }
    return profit;
}

2018-06-20更新

leetcode-66-Plus One

题解：给定一个数字数组，最后一个元素+1，输出新数组。

样例：[1,2,3,4];(1234)

输出：[1,2,3,5]。

1
2
3
4
5
6
7
8
9
10
11
var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        digits[i] = (digits[i] + 1) % 10;
        //检测第一个元素是否为0
        if (digits[i]) {
            return digits;
        }        
    }
    digits.unshift(1);
    return digits;
};

2018-06-02更新

leetcode-53-Maximum Subarray

题解：给定一个数组，求子序列中和最大的序列，返回最大的和

样例：[-2,1,-3,4,-1,2,1,-5,4]

输出：6（[4,-1,2,1]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let last = 0;
    let max = nums[0];
    for(let num of nums){
        if(last>=0){
            last += num;
        }else{
            last = num;
        }
        if(last>max){
            max = last;		//保留最大值
        }
    }
    return max
};

2018-05-26更新

leetcode-69-Sqrt(x)

题解：输入一个目标值，返回目标值的平方根

样例：4 8

输出：2 2(2.8…取整)

1
2
3
4
5
6
7
8
9
10
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x <= 0){
        return 0;
    }
    return parseInt(Math.sqrt(x));
};

2018-05-20更新

leetcode-58- Length of Last Word

题解：给定一个以空格分隔的字符串，求最后一个单词的长度，若不存在最后一个单词，返回0

样例：”hello world”

输出：5

注意：字符串切割完成之后要进行去除空格的操作，如果去除之后数组长度为空，返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    let wordArr = s.split(" ");
    // 去除空格
    let wordArrNoEmpty = [];
    for(let i = 0 ; i < wordArr.length ; i++){
        if(wordArr[i] === ''){
            continue;
        }
        wordArrNoEmpty.push(wordArr[i]);
    }
    if(!wordArrNoEmpty || wordArrNoEmpty.length <= 0){
        return 0;
    }
    return wordArrNoEmpty[wordArrNoEmpty.length-1].length;
};

leetcode-28-Implement strStr()

题解：给定两个字符串，若第二个字符串为第一个字符串的子串，输出下标，否则，返回-1。

样例： haystack = “hello”, needle = “ll”

输出：2

1
2
3
4
5
6
7
8
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

2018-05-19更新

leetcode-35-Search Insert Position

题解：给定一个排好序的数组和目标值，若数组中存在目标值，输出下标，若不存在，输出目标值若在数组中应处的下标。（可认为数组中不存在重复值）

样例：[2,4,5,7] 5

输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if(nums.indexOf(target) < 0){
    nums.push(target);
    //此处做了排序，不知道如何利用已经排好序这个条件
    nums.sort((a,b)=>a-b);
    return nums.indexOf(target);
  }else{
    return nums.indexOf(target);
  }
};

2018-05-14更新

leetcode-27-Remove Element

题解：给定一个数组和一个目标值，去除数组中存在的目标值，返回数组长度，要求不使用额外空间。

样例：[2,2,3,3] , 3

输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if(nums.length === 0){
        return 0
    }
    for(let i = 0 ; i < nums.length ; i ++){
        if(nums[i] === val){
            nums.splice(i,1);
            removeElement(nums,val);
        }else{
            continue;
        }
    }
    return nums.length;
};

2018-05-13更新

leetcode-09-Palindrome Number

题解：给定一个数字，判断是否为回文数。

样例：121

输出：true

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    let xStr = String(x).split('').reverse().join('');
    if(x === parseInt(xStr)){
        return true;
    }else{
        return false;
    }
};

leetcode-26-Remove Duplicates from Sorted Array

题解：给定一个排好序的数组，去除重复元素，返回数组长度，空间复杂度为O(1)，不能使用辅助空间。

样例：[1,1,2]

输出：2

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  for (let i = 0; i < nums.length; ++i) {
    while(nums[i] === nums[i + 1]) {
      nums.splice(i + 1, 1);
    }
  }

  return nums.length;
};

2018-05-12更新

leetcode-14-Longest Common Prefix

题解：给定一个字符串数组，输出最长前缀，不存在输出空字符。

样例：[“flower”,”flow”,”flight”]

输出：”fl”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var prefix = strs[0] || '';
    for (var i = 1; i < strs.length; i++) {
        var str = strs[i];
        while (str.indexOf(prefix) != 0) {
            prefix = prefix.substr(0, prefix.length - 1);
        }
    }
    return prefix;
};

leetcode-20-Valid Parentheses

题解：给定一串只包含’(){}[]’的字符串，进行有效性判断。

输入：{[()]}

输出：true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let arr = [];
    let obj = {
        ']': '[',
        '}': '{',
        ')': '('
    }
    let strArr = s.split("");
    
    for(let elem of strArr) {
        arr.push(elem);
        if(elem === ']' || elem === '}' || elem === ')') {
            arr.pop();
            if(arr.pop() != obj[elem]) return false
        }
    }
    return arr.length == 0 ? true : false;
};

好吧，好好复习下字符串和数组的知识，惹不起惹不起。

###2018-05-06更新

leetcode-13-Roman to Integer

题解：给定一串罗马数字以及转化规则，计算转化结果

样例：”III”

输出：3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//这题能吸收一些基础知识。。太菜了。。。
//romanNum['I'] === 1
//for 循环中可以改变迭代变量 i 。。
var romanToInt = function(string) {
    const romanNum = {
        "I" : 1,
        "V" : 5,
        "X" : 10,
        "L" : 50,
        "C" : 100,
        "D" : 500,
        "M" : 1000
    };

    let ronabInt = 0;

    for(let i=0; i<string.length; i++){
        if(romanNum[string[i+1]] > romanNum[string[i]]){
            ronabInt += romanNum[string[i+1]] - romanNum[string[i]];
            i++;   						/*在下输了，基础不行。。。*/
        }else{
            ronabInt += romanNum[string[i]];
        }
    }
    console.log(ronabInt);
    return ronabInt;
};

leetcode-7-Reverse Integer

题解：给出一个数字，进行翻转，若翻转之后溢出，返回0。

样例：123

输出：321

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var reverse = function(x) {
    let numArray = String(x).split('');
    let num = '';
    if(x < 0){
        numArray.splice(0,1);     //若输入为负数，去除负号。
        num = -(parseInt(numArray.reverse().join('')));
        if(checkNum(num)){
            return 0;
        }
        return num;
    }
    num = parseInt(numArray.reverse().join(''));
    if(checkNum(num)){
        return 0;
    }
    return num;
};
function checkNum(num) {
    if(num >= ((Math.pow(2,31))-1) || num <= Math.pow(-2,31)){
        return true;
    }
}

leetcode-1-Two Sum

题解：给定一个数组和一个目标值，从数组中找出两个值得和等于目标值，输出下标。

样例：[2,7,11,15]，9

输出：[0,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0 ; i < nums.length ; i++){
        for(let j = 0 ; j < nums.length ; j++){
            if(i === j){
                continue;
            }
            if(nums[i] + nums[j] === target){
                return [i , j];
            }
        }
    }
};

2018-05-01更新

最近心情有点复杂。。。

赛码——研究生考试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let n = parseInt(read_line());
let line,p,e,m,o;
for(let i = 0 ; i < n ; i++){
	line = read_line().split(' ');
  	p = parseInt(line[0]);
  	e = parseInt(line[1]);
  	m = parseInt(line[2]);
  	o = parseInt(line[3]);
	check(p,e,m,o)
}
function check(p,e,m,o) {
	let sum = p+e+m+o;
  if(p < 60 || e < 60 || m < 90 || o < 90 || sum < 310){
    	print('Fail');
    } else if(sum<350) {
    	print('Zifei');
    } else{
        	print('Gongfei');
    }
}

好像不支持变量解构赋值。。。

2018-04-17

完全被迫无奈。。。。重新拿起了java。。。

赛码——公交车乘客

一开始理解错题意了，以为是求某一站上下车之和最大的一个。

仔细看才发现是求车上可能的最大容量。。脑子不中用了。。

MAX（上车人数-下车人数+当前车上的人数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class Main {
    public static void main(String args []){
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int sum = 0;
        int max = 0;
        for(int i = 0 ; i < n ; i++){
            int a = cin.nextInt(); 		//下车人数
            int b = cin.nextInt();  	//上车人数
            sum = sum + b - a;
            if(sum > max){
                max = sum;
            }
        }
        System.out.println(max);
    }
}