Integer to Roman
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.
罗马数字简介：
https://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97

使用贪心算法，注意900,400,90,40,9,4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
     * @param {number} num
     * @return {string}
     */
function intToRoman(num) {
        var roman =[];
        var str =[ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ];
        var value =[1000,900,500,400, 100, 90,  50, 40,  10, 9, 5, 4, 1];
        for(var i=0; num!=0; ++i){
            while(num >= value[i]){
                num = num - value[i];
                roman.push(str[i]);
            }
        }
        return (roman.join(""));
    }

好多坑= =
1.最开始采取了枚举，一堆循环要上天
2.看了discuss，原来可以贪心呀
3.900,400,90,40,9,4算着太烦直接枚举就好了
4.最后用join转换成字符串，才发现如果在括号里填什么，就会用符号分开，如果不填，就默认逗号(之前真的没印象，逃~)

顺手翻到的一篇总结JavaScript字符串很好的文章
http://riny.net/2012/the-summary-of-javascript-string/

Roman to Integer
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

感觉思路被上一道题困住了(快放开我！)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function romanToInt(s) {
        var int =[];
        var str =[ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ];
        var value =[1000,900,500,400, 100, 90,  50, 40,  10, 9, 5, 4, 1];
        for(var i=0; i< s.length; i++){
            for(var j=0;j<str.length;j++){
                if(s[i]==str[j]){
                    int.push(value[j]);
                }
            }
        }
        console.log(int);
        var intsum=0;
        for(var j=0;j<int.length;j++){
            intsum+=int[j];
        }
        console.log(intsum);
    }

然而我不太清楚怎么区分两个数组排在一起用js写的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int romanToInt(String s) {
    HashMap<Character, Integer> values = new HashMap<Character, Integer>();
    values.put('I',1);
    values.put('V',5);
    values.put('X',10);
    values.put('L',50);
    values.put('C',100);
    values.put('D',500);
    values.put('M',1000);
    int ptr = s.length() - 1;
    int curr;
    int prev = 0;
    int result = 0;
    while(ptr >= 0) {
        curr = values.get(s.charAt(ptr));
        result = curr >= prev ? (result + curr) : (result - curr);
        prev = curr;
        ptr--;
    }
    return result;
}

熬，hashtable
明天再看

Given a string s consists of upper/lower-case alphabets and
empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * @param {string} s
 * @return {number}
 */
 function lengthOfLastWord(s) {
    var sArray = s.split(" ");
    //撸掉那些长度等于0的元素
    sArray = sArray.filter(function(str){
            return str.length > 0;
    })
    if(sArray.length > 0) {
        var lastWord = sArray[sArray.length - 1];
        return lastWord.length;
    } else {
        return 0;
    }
    }

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function getRow(rowIndex) {
        var leng = rowIndex+1;
        var number = new Array(leng);
        for(var k=0;k<leng;k++){
            number[k]=new Array(k+1);
            number[k][0]=1;
            number[k][k]=1;
        }
        for(var m=2;m<leng;m++){
            for(var n=1;n<m;n++){
                number[m][n]=number[m-1][n-1] +number[m-1][n];
            }
        }
        return number[rowIndex];
    }

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

1
2
3
4
5
6
7

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function generate(numRows) {
       var number = new Array(numRows);
       for(var k=0;k<numRows;k++){
           number[k]=new Array(k+1);
           number[k][0]=1;
           number[k][k]=1;
       }
       for(var m=2;m<numRows;m++){
           for(var n=1;n<m;n++){
               number[m][n]=number[m-1][n-1] +number[m-1][n];
           }
       }
       return number;
   }

1
2
3

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

给定一个数组和一个值，删除该值的所有实例，并返回新的长度。
元素的顺序可以被改变，也不关心最终的数组长度

思路：先排个序
加了一个position数组来存储位置相关的信息
一开始没注意是返回number，以为返回nums
加了个length就好啦

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}
 */
 function removeElement(nums,val) {
        function compare(num1,num2){
            return num1 -num2;
        }
        nums.sort(compare);
        var position=[];
        for(var i=0;i<nums.length;i++){
            if(nums[i]==val){
                position.push(i);
            }
        }
        nums.splice(position[0],position.length);
        return nums.length;
    }

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

思路：
1.除最高位外，每一位若为9，+1后为0；
2.若不为9，就还是原来的数字；// sum = (push + digits[i]) % 10;
3.若最高位仍有进位，那便使进位值为1，加到number数组的第一位；
//push=Math.floor((push+digits[i])/10);

function plusOne(digits) {
        var  number=[];
        var push=1;
        var n=digits.length-1;
        var sum=0;
        for(i=n; i>=0; i--) {
            sum = (push + digits[i]) % 10;
            //if(digit[i]==10){push=2}
            push=Math.floor((push+digits[i])/10);
            number[n]=sum;
            n--;
        }
        if(push!==0) {
            number.unshift(push);
        }
        console.log(number);
    }

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
The number of elements initialized in nums1 and nums2 are m and n respectively.

给定两个排序的整型数组nums1和nums2，将nums2合并到nums1成一个排序数组。

Note：
你可以假设nums1中有足够的空间（空间大于或等于m+n）来存放来自nums2的额外元素。
nums1和nums2的初始空间分别是m和n。

思路：
1.nums1的空间不足时，num1末尾的元素要舍掉；
//注意先给nums1.length赋值；不要直接在while的判断条件里使用nums.length
2.nums2空间不足时，循环会判断添加的元素个数；
3.最后排个序就好啦~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function merge(nums1, m, nums2, n) {
        var k=m;
        var len=nums1.length;
        while(k<len){
                nums1.pop();
                k++;
        }
        for(var i=0;i<n;i++){
            nums1.push(nums2[i]);
        }
        function compare(num1,num2){
            return num1 -num2;
        }
        nums1.sort(compare);
    }

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

先排个序。
然后突然发现，number出现的次数大于n/2
那就好办了，n/2之后的数不都是number嘛: )

/**
 * @param {number[]} nums
 * @return {number}
 */
 function majorityElement(nums) {
        function compare(num1,num2){
            return num1 -num2;
        }
        nums.sort(compare);
        var leng = nums.length;
        number =nums[Math.floor(leng/2)];
        return number;
    }

1.定义
数组的标准定义是：一个存储元素的线性集合(collection)。
JavaScript的数组是一种特殊的对象，用来表示偏移量的索引是该对象的属性。
2.创建数组
-var numbers = []; //这种方法效率更高,why?
-var numbers = new Array(10); //numbers.length 10
-var objects = [1,”Mary”,true,null];
3.读写数组

1
2
3
4
5
6
7
8
9
10
11
12

//数据赋给数组
var numbers = [];
for ( var i=0; i<100 ;i++){
    nums[i]= i+1;
}
//读取数组
var numbers =[1,2,3,4,5,6,7];
var sum =0;
//使用length控制数组长度
for( var i=0 ;i<numbers.length; i++){
    sum +=numbers[i];
}

4.对数组进行整体性操作
当把一个数组赋给另一个数组时，只是为另一个数组增加了一个新的引用。当通过原引用修改数组的值时，另外一个引用也会感知到这个变化。
即新数组仍旧指向原来的数组。

1
2
3
4
5
6
7

var nums =[];
for( var i=0;i<100;i++ ){
    num[i]= i+1;
}
var samenums =nums;
nums[0]=400;
print(samenums[0]); // 400

一个更好的方案是采用深复制，将原数组的每一个元素都复制到新数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13

funtion copy(arr1,arr2){
    for( var i=0;i<num1.length;i++){
        arr2[i]=arr1[i];
    }
}
var nums =[];
for( var i=0;i<100;i++ ){
    num[i]= i+1;
}
var samenums =[];
copy(nums,samenums);
nums[0]=400;
print(samenums[0]); // 400

5.由字符串生成数组
split()方法

6.存取函数
-查找元素 indexOf(),若目标数组包含该参数，则返回第一个参数的索引；若不存在，则返回-1; var position = arr.indexOf(hello);
-lastIndexOf()返回最后一个参数的索引;
-join() 可以将数组转化为字符串 var str =arr.join();
-toString() 可以将数组转化为字符串 var str = arr.toString();
-concat() 合并数组 var newArr =arr2.concat(arr1);
-splice() 截取数组 var newArr =arr.splice(3,3) //第一个参数是起始索引，第二个参数是截取的长度

7.可变函数
-push() 为数组末尾添加元素 arr.push(6);
-unshift() 为数组开头添加元素 nums.unshift(1,2);
-pop() 可以删除数组末尾的元素 nums.pop();
-shift() 可以删除数组开头的元素 nums.shift();
这个是不使用方法的增加数组的第一个元素

1
2
3
4
5
6
7

var nums =[2,3,4,5];
var newnum =1;
for ( var =nums.length ; i>0; i++){
    nums[i]=nums[i-1];
}
nums[0] =newnum;
print(nums)//1,2,3,4,5

将删除的数组末尾元素追加的数组开始

1
2
3
4

var nums =[6,1,2,3,4,5];
var last=nums.shift();
nums.push(last);
print(nums);//1,2,3,4,5,6

8.从数组的中间位置添加或删除元素
采用splice()方法插入或删除元素，需要提供以下三个参数
-起始索引(希望开始添加元素的地方)
-需要删除的元素个数，添加元素时此项为0
-想要添加进数组的元素

1
2
3
4
5

//添加元素
nums.splice(3,0,[4,5,6]);
nums.splice(3,0,4,5,6);
//删除元素
nums.splice(3,4);

9.为数组排序
-reverser() 该方法将数组中元素的顺序进行翻转
-sort() 该方法对字符串数组按照字典顺序进行排序

1
2
3
4
5
6

function compare(num1,num2){
    return num1 -num2;
}
var nums =[3,2,5,6,4];
nums.sort(compare);
print(nums); //2,3,4,5,6

10.迭代器方法
-forEach() 接受一个函数作为参数，对数组中每个元素使用该函数
arr.forEach(square);
-every() 接受一个返回值为Boolean类型的函数，对数组中每个元素使用该函数，若都为true，则返回true
-some() 同上，但只要有一个为true，就返回true
-reduce() 接受一个函数，返回一个值 对数组中所有元素进行累加
-reduceRight() 同上，不过执行顺序从右到左
-map() 生成新数组 类似forEach
-filter() 同every，不过返回的是Boolean类型为true的元素

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

//reduce
function add (num1,num2){
    return num1+num2;
}
var nums = [1,2,3,4,5,6,7,8,9,10];
var sum =nums.reduce(add);
print(sum); //55
//map()
function curve(num){
    return num+=5;
}
var grades =[1,2,3,4,5];
var  new = grades.map(curve);
print(new); //6,7,8,9,10
//filter()
//过滤不包含cie的元素
function expectCie(str){
    if(str.indexOf("cie")>-1){
        return true;
    }
    return false;
}
var word = words.filter(expectCie);