[1~3题]剑指offer(Java+JavaScript)

剑指offer练习(测试环境为牛客oj)

第一题

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

考点

数组

解题思路

从左下角开始找,如果目标值比当前值大就往右找,如果比当前值小就往上找,直到找到了返回true

基础知识回顾

1.二维数组长度

如:arr[i][j]

行数 arr.length

列数 arr[i].length

实现代码

1.java

 1 public class Solution {
 2 
 3     public boolean Find(int target, int [][] array) {
 4 
 5         //二维数组的行数
 6 
 7         int row = array.length-1;
 8 
 9         //二维数组的列数
10 
11         int col = array[0].length-1;
12 
13         //当前所在行数,从二维数组的左下角开始找
14 
15         int tr = row;
16 
17         //当前所在列数
18 
19         int tc = 0;
20 
21         //只要没有行数列数都走完就继续找
22 
23         while(tr >= 0 && tc <= col){
24 
25             if(target == array[tr][tc]){
26 
27                  return true;//如果找到返回true
28 
29             }else if(target > array[tr][tc]){
30 
31                 tc++;//如果目标数比当前数大,向右找
32 
33                 continue;
34 
35             }else if(target < array[tr][tc]){
36 
37                 tr--;//如果目标数比当前数小,向上找
38 
39                 continue;
40 
41             }          
42 
43         }
44 
45         //如果所有行数和列数都走完还没找到说明数组中没有目标数,返回false
46 
47         return false;
48 
49     }
50 
51 }

View Code

2.JavaScript

 1 function Find(target, array)
 2 
 3 {
 4 
 5         //二维数组的行数
 6 
 7         var row = array.length-1;
 8 
 9         //二维数组的列数
10 
11         var col = array[0].length-1;
12 
13         //当前所在行数,从二维数组的左下角开始找
14 
15         var tr = row;
16 
17         //当前所在列数
18 
19         var tc = 0;
20 
21         //只要没有行数列数都走完就继续找
22 
23         while(tr >= 0 && tc <= col){
24 
25             if(target == array[tr][tc]){
26 
27                  return true;//如果找到返回true
28 
29             }else if(target > array[tr][tc]){
30 
31                 tc++;//如果目标数比当前数大,向右找
32 
33                 continue;
34 
35             }else if(target < array[tr][tc]){
36 
37                 tr--;//如果目标数比当前数小,向上找
38 
39                 continue;
40 
41             }          
42 
43         }
44 
45         //如果所有行数和列数都走完还没找到说明数组中没有目标数,返回false
46 
47         return false;
48 
49 }

View Code

第二题

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

考点

字符串

解题思路

1.Java:准备一个新的字符串,循环遍历旧字符串的每一个字符,如果当前字符是空格,则把%,2,0这三个字符分别拼接到新字符串结尾,如果当前字符不是空格,就把当前字符拼接到新字符串的结尾,最终新字符串就是替换后的字符串.

2.js:直接使用replace方法通过正则表达式来找出空格并替换.

基础知识回顾

1.Java:

1.StringBuffer

StringBuffer 用于创建可变字符串

创建StringBuffer对象用来拼接成转换后的字符串

2.append()方法

append()方法,在字符串结尾添加字符

2.Js:

1.正则表达式

s 匹配一个空白字符，包括 , ,f, ,v等

g 全文查找出现的所有符合正则表达式的内容

2.replace方法

字符串.replace(“被替换的”,”替换成的”);

实现代码

1.java

 1 public class Solution {
 2 
 3     public String replaceSpace(StringBuffer str) {
 4 
 5              //如果传入的字符串为null,返回null
 6 
 7         if(str==null){
 8 
 9             return null;
10 
11         }
12 
13         //创建一个StringBuffer对象,来拼接成替换后的字符串
14 
15        StringBuffer newStr = new StringBuffer();
16 
17         //循环遍历字符串中的每一个字符
18 
19         for(int i=0;i<str.length();i++){
20 
21             //如果遇到当前字符是空格,就分别将%,2,0这三个字符拼接到新字符串中
22 
23             if(str.charAt(i)==' '){
24 
25                 newStr.append('%');
26 
27                 newStr.append('2');
28 
29                 newStr.append('0');
30 
31             }else{
32 
33                 newStr.append(str.charAt(i));//当前字符不是空格时,就直接将当前字符拼接到新字符串中
34 
35             }
36 
37         }
38 
39         return newStr.toString();//最后将newStr转换成String类型,并返回
40 
41     }
42 
43 }

View Code

2.JavaScript

1 function replaceSpace(str){
2 
3     return str.replace(/s/g,'%20');
4 
5 }

View Code

第三题

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

考点

递归和循环

解题思路

共有递归和非递归两种方式,不推荐递归方式,复杂度高,其中js使用递归oj上不通过.因为给定了n的最大限制.java非递归方式也可以使用数组来实现.js可以动态在数组中添加数据,因此没有最大限制也可以使用数组来实现.

基础知识回顾

1.Java和js创建数组的方式不同

创建字面量数组:

Java:

int[] arr = {1,2,3};

Js:

var arr = [1,2,3];

创建定长数组:

Java:

int[] arr = new int[40];

Js:

var arr = new Array(3)

2.关于push方法

Java定义好普通数组长度之后,不可以再通过push增加元素,但js可以,具体见代码可以理解.

实现代码

1.java

1.递归:

 1 public class Solution {
 2 
 3     public int Fibonacci(int n) {
 4 
 5         if(n < 2){
 6 
 7         return n;
 8 
 9         }else{
10 
11         return Fibonacci(n-1)+Fibonacci(n-2);
12 
13         }
14 
15     }
16 
17 }

View Code

2.非递归:

法一.不使用数组

 1 public class Solution {
 2 
 3     public int Fibonacci(int n) {
 4 
 5         int f0 = 0;
 6 
 7         int f1 = 1;
 8 
 9              int cur = n;
10 
11              if(n > 1){
12 
13                       for(int i = 2;i<=n;i++){
14 
15                                 cur = f0+f1;
16 
17                                 f0 = f1;
18 
19                                 f1 = cur;
20 
21                       }                    
22 
23              }
24 
25         return cur;
26 
27     }
28 
29 }

View Code

法二.使用数组

 1 public class Solution {
 2 
 3     public int Fibonacci(int n) {
 4 
 5         int[] arr = new int[40]; //0~39,一共40个数
 6 
 7                    arr[0] = 0;
 8 
 9              arr[1] = 1;
10 
11              if(n > 1){
12 
13                       for(int i = 2;i <= n;i++){
14 
15                                 arr[i] = arr[i-1] + arr[i-2];
16 
17                  }
18 
19         }
20 
21         return arr[n];
22 
23     }
24 
25 }

View Code

2.JavaScript

1.递归

 1 function Fibonacci(n){
 2 
 3     if(n < 2){
 4 
 5         return n;
 6 
 7     }else{
 8 
 9         return Fibonacci(n-1)+Fibonacci(n-2);
10 
11     }
12 
13 }

View Code

2.非递归

法一.不使用数组

 1 function Fibonacci(n){
 2 
 3         var f0 = 0;
 4 
 5         var f1 = 1;
 6 
 7              var cur = n;
 8 
 9              if(n > 1){
10 
11                       for(var i = 2;i<=n;i++){
12 
13                                 cur = f0+f1;
14 
15                                 f0 = f1;
16 
17                                 f1 = cur;
18 
19                       }                    
20 
21              }
22 
23         return cur;
24 
25 }

View Code

法二.使用数组

 1 function Fibonacci(n){
 2 
 3         var arr = [0,1,1];
 4 
 5         var cur = 0;
 6 
 7              if(n > 2){
 8 
 9                       for(var i = 3;i <= n;i++){
10 
11                                 cur = arr[i-1] + arr[i-2];
12 
13                 arr.push(cur);
14 
15                  }
16 
17         }
18 
19         return arr[n];
20 
21 }

View Code