数据结构和算法
第一部分：习题
注意：使用typeof的时候，一定是在后面的类型上加引号，否则会出错。
1.使用XO()函数判断一个字符串中x和o的数量是否相等，相等则返回true，否则返回false。且忽略大小写。
方法一：
function XO(str) {
if(str.match(/x/ig).length == str.match(/o/ig).length){
return true;
}
return false;
}
注意：1.匹配正则表达式时，ig表示忽略大小写且在全局中匹配，否则只会返回第一个匹配的字符串；
2.match()方法，如果匹配成功，则返回一个数组；如果匹配不成功，则返回null。
3.但是如果不存在o或着x，那么该方法将报错，因为null没有length属性，讨论将会复杂。
方法二：
<!DOCTYPE html>
<html>
<head>
<title>test</title>
</head>
<body>
<script>
function XO (str){
var strArr = str.split("");
// console.log(strArr);
var j=0;
var k=0;
for(var i=0;i<strArr.length;i++){
if(strArr[i].toLowerCase()== "x"){
//注意toLowerCase()是一个方法！
j++;
}
if(strArr[i].toLowerCase()== "o"){
k++;
}
}
if(j===k){
return true;
}
return false;
}
console.log(XO("xxxxxo")); //false
console.log(XO("xxoo")); //true
console.log(XO("xXoo")); //true
console.log(XO("mmpp")); //true
console.log(XO("xoo")); //false
</script>
</body>
</html>
首先将字符串使用split()方法转化成数组，然后遍历，如果等于O,则j加，如果等于x，则k加1；最后判断是否相等，这种方法也非常棒。
2.DNA链条 A和T互补 C和G互补，输入字符串ATCG应当输出TAGC，如下：
<!DOCTYPE html>
<html>
<head>
<title>test</title>
</head>
<body>
<script>
//需求：输入的dna是大写的，并且是一个字符串，A和T互补，C和G互补，假设输入AATG，则应当输出TTAC
function DNAStrand(dna){
var dnaArr = dna.split("");
for (var i = 0; i < dnaArr.length; i++) {
if(dnaArr[i]=="A"){
dnaArr[i]="T";
continue;
}
if(dnaArr[i]=="T"){
dnaArr[i]="A";
continue;
}
if(dnaArr[i]=="C"){
dnaArr[i]="G";
continue;
}
if(dnaArr[i]=="G"){
dnaArr[i]="C";
continue;
}
}
var dnaCom = dnaArr.join("");
console.log(dnaCom);
}
DNAStrand("TCTG"); //AGAC
DNAStrand("ACCA"); //TGGT
DNAStrand("GTAC"); //CATG
DNAStrand("CTAG"); //GATC
</script>
</body>
</html>
注意：一定要continue，否则会出现问题。另外可以发现：处理字符串时，先转化为数组往往有好的效果，因为可以遍历。
3.判断一个数是否是 square number,方法如下：
<!DOCTYPE html>
<html>
<head>
<title>codewars</title>
</head>
<body>
<script>
//Task:输入一个整数，判断它是否是 square number:In mathematics, a square number or perfect square is an interger that is the square fo an interger; in other words, it is the product of some interger with itself.
function isSquare(integer){
if(typeof integer!== 'number'){
console.log(integer+" is not a number");
}
else if(integer<0||Math.sqrt(integer)%1!==0){
console.log(integer+" is not a square number");
}
else{
console.log(integer+" is a square number");
}
}
//思路：square Number使用Math.sqrt()得到的一定是整数。且任何整数都会被1整除，即余数为0。
isSquare("string");
isSquare(true);
isSquare(-5);
isSquare(5);
isSquare(4);
isSquare(9);
isSquare(9.5);
isSquare(0.36);
// 说明:js中判断是否是整数为本题的关键，上例中采用求余的方法是可行的，除此之外，还可以是下列方法：
//1. 使用Math.round()或Math.floor()或Math.ceil()取整后判断是否等于它自己。
//2. 使用ES6提供的Number.isInterger()方法来判断，返回true，则表示是整数。
</script>
</body>
</html>
4.给你m块砖搭建一个房子，最底层为n的三次方块转，第二层为(n-1)的三次方...最上面为1块砖，然后给你一个m，去判断是否存在这样的一个n，有则输出n，没有则输出-1.
<!DOCTYPE html>
<html>
<head>
<title>find_nb</title>
</head>
<body>
<script>
// Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3. You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build? The parameter of the function findNb (find_nb, find-nb) will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.
function find_nb(m){
if(typeof m !== 'number'){
console.log(m+" is not a number");
console.warn(" what you input is not a number");
return;
}
//先判断这个数是否为number类型。
var i=1,
sum=0;
while(sum<m){
sum += Math.pow(i,3);
i++;
}
if(sum==m){
console.log(i-1);
}else{
console.log(-1)
}
//循环，在sum<m的条件下循环，一旦不满足条件就跳出循环（防止无限循环），然后判断sum和m的关系，并输出相应的n，注意n的结果是i-1而不是i。
}
find_nb(true);
find_nb(4654);
find_nb(1071225);
</script>
</body>
</html>
5. 删除一个数组中冗余的项。
<!DOCTYPE html>
<html>
<head>
<title>unique_in_order</title>
</head>
<body>
<script>
//Implement the function unique_in_order which takes as argument a sequence and returns a list of items without any elements with the same value next to each other and preserving the original order of elements.
function uniqueInOrder(arr){
if(typeof arr == "string"){
arr = arr.split("");
}
if(typeof arr !== "object"){
// 注意：这里不能使用instanceof来判断
console.error("plz input a string or a Array");
return;
}
// 如果是字符串，就把字符串转化成数组
for (var i = 1; i < arr.length; i++) {
//注意：这里数组arr可能是会变化的，所以arr.length是不能缓存的。
if(arr[i]==arr[(i-1)]){
arr.splice(i,1);
// splice方法指定的第一个参数时 要删除的位置的index，而第二个参数是删除的个数，这里用slice方法也可以实现。
i--;
// 重要，一旦删除，那么i必须减去1，否则有可能导致遗漏。
}
}
console.log(arr);
}
//核心：解决问题时，先解决主要问题，次要问题最后再完善，即渐进增强。
uniqueInOrder('AAAABBBCCDAABBB'); //['A', 'B', 'C', 'D', 'A', 'B']
uniqueInOrder('ABBCcAD'); //['A', 'B', 'C', 'c', 'A', 'D']
uniqueInOrder([1,2,2,3,3]); //[1,2,3]
uniqueInOrder(8); //[1,2,3]
</script>
</body>
</html>
6.给一个字符串，返回中间两个数
<!DOCTYPE html>
<html>
<head>
<title>middle_string</title>
</head>
<body>
<script>
//You are going to be given a word. Your job is to return the middle character of the word. If the word's length is odd, return the middle character. If the word's length is even, return the middle 2 characters.
function return_mid (str){
// 如果不是字符串，则return
if(typeof str !== "string"){
console.warn(str+" is not a string");
return;
//当出现问题后，直接return
}
if(str.length==0){
console.warn("you input a vacant string");
return;
// 当出现问题后，直接return
}
if(str.length%2==0){
console.log(str.charAt(str.length/2-1).concat(str.charAt(str.length/2)));
}
if(str.length%2==1){
console.log(str.charAt((str.length-1)/2));
}
}
return_mid(888); //888 is not a string
return_mid("string"); //"ri"
return_mid("inter"); // "t"
return_mid("");
</script>
</body>
</html>
7. （好题）判断输入一个整数返回的乘积次数。
<!DOCTYPE html>
<html>
<head>
<title>persistence</title>
</head>
<body>
<script>
function persistence(number){
if(typeof number !== 'number'){
console.error("plz input number");
return;
}
if(number<0){
console.warn("plz input a positive number");
return;
}
var arr = (number).toString().split("");
// 将一个数字先转化成字符串，再转化成数组，操作数组会更方便一些。
var arrLen = arr.length;
if(arrLen == 1){
console.log("0");
return;
}
// 若长度为1，则直接返回0即可。
var sum = 1;
var return_num = 0;
//因为sum和return_num在后面的过程中是变化的，所以要放在循环外面
do{
return_num++;
//因为只要是执行到这一步的数，其return_num至少为1.
sum = 1;
//注意：这一步和var sum =1 不同，它是不可缺少的，为了每次循环都重新开始！
for (var i = 0; i < arrLen; i++) {
sum *= arr[i]
}
arr = (sum).toString().split("");
arrLen = arr.length;
//得到新的数组之后，第二次就会以这个新的数组循环了。
}while(sum>=10)
console.log(return_num);
//思想非常简单： 先求出各个位的乘积，然后将这个乘积“缓存”，如果满足一定条件，下次就使用这个缓存，注意：这个缓存的每次不是相同的。
}
persistence(39); //3
persistence("dfa"); //plz input number
persistence(-8); //lz input a positive number
persistence(999); //4
persistence(4); //0
persistence(25);//2
//Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.
</script>
</body>
</html>
8. 智商检测---从偶数中找奇数，从奇数中找偶数
<!DOCTYPE html>
<html>
<head>
<title>iqTest</title>
</head>
<body>
<script>
// Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given numbers differs from the others. Bob observed that one number usually differs from the others in evenness.
//Help Bob — to check his answers, he needs a program that among the given numbers finds one that is different in evenness, and return a position of this number.
//! Keep in mind that your task is to help Bob solve a real IQ test, which means indexes of the elements start from 1 (not 0)
function iqTest(str){
var test = /(ds)+d/;
var de = test.test(str);
if(!de){
console.error("illegal!");
return;
}
var arr = str.split(" ");
// 首先，判断这个数组arr中odd多还是even多，如果odd多，就输出even的index；如果even多，就输出odd的index；
var odd=0;
var even=0;
for(var i=0,len=arr.length;i<len;i++){
if(Math.abs(arr[i]%2)==0||arr[i]==0){
even++;
}else{
odd++;
}
// 分别得出even和odd的数目
}
if((even>odd)&&(odd!==0)){
// 如果even多，且odd不为0，就找到odd并返回索引加1
for(var i=0,len=arr.length;i<len;i++){
if(Math.abs(arr[i])%2==1){
console.log(i+1);
return;
}
}
}else if((even<odd)&&(even!==0)){
// 如果odd多，且even不为0，就找到even并返回索引加1
for(var i=0,len=arr.length;i<len;i++){
if(Math.abs(arr[i])%2==0){
console.log(i+1);
return;
}
}
}else{
console.log("your question is wrong");
}
}
iqTest("2 4 7 8 10") // 3 Third number is odd, while the rest of the numbers are even
iqTest("1 2 1 1") // 2 Second number is even, while the rest of the numbers are odd
iqTest("1 1 2 2") // your question is wrong
iqTest("1 1 1 1") // your question is wrong
iqTest(null); // illegal!
</script>
</body>
</html>
9. 找出所有的除数
<!DOCTYPE html>
<html>
<head>
<title>divisors</title>
</head>
<body>
<script>
//Create a function named divisors that takes an integer and returns an array with all of the integer's divisors(except for 1 and the number itself). If the number is prime return the string '(integer) is prime' (use Either String a in Haskell).
function divisors(number){
if(typeof number !== "number"){
console.err("plz input a number");
return;
}
if(number<=0){
console.warn("plz input a positive number");
return;
}
var divisorsArr = [];
for(var i=2;i<number;i++){
if(number/i == ((number/i)|0)){
divisorsArr.push(i);
}
}
if(divisorsArr.length==0){
console.warn(number+" is prime");
return;
}
console.log(divisorsArr);
}
divisors(12); //[2,3,4,6]
divisors(25); //[5]
divisors(13); //"13 is prime"
divisors(-12); //plz input a positive number
divisors(0); //plz input a positive number
</script>
</body>
</html>
第二部分： 常见题
function foo(n) { var i = 1; while (i < = n) { i *= 2; } }
这个函数的时间复杂度是多少?
时间复杂度即根据不同的输入（这里是n），那么程序的语句执行的次数就可以理解为时间复杂度。
这里每执行一次，i为2x ,每执行一次，x就会增加1， 可见当2x = n 时， 程序执行完毕，那么x为log n ，于是程序的复杂度为 O(logn)
斐波那契数列的时间复杂度是多少？
斐波那契数列f(0)开始，第0项是0，第1项是1，后面的每一项是前面两项之和，最易理解的是递归形式。那么它的时间复杂度是多少呢？
function fibbnaqi(n) { if (n <= 1) { return n; } else { return fibbnaqi(n - 1)+fibbnaqi(n - 2); } } function log(n) { console.log(fibbnaqi(n)); } log(0); // 0在斐波那契数列中有f(0)这一项，所以从0开始 log(1); // 1 log(2); // 1 log(3); // 2 log(4); // 3