剑指offer-2

剑指offer day2

13、机器人的运动范围 https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

本题与上一题类似，是一个简单的dfs标记题。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][]vis=new boolean[m][n];
            return dfs(m,n,0,0,k,vis);
    }
    private int dfs(int m,int n,int i,int j,int k,boolean[][]vis){
        if(i<0||i>=m||j<0||j>=n||(i/10+i%10+j/10+j%10)>k||vis[i][j]==true) return 0;
        vis[i][j]=true;
        //只用往右下角走
        return dfs(m,n,i+1,j,k,vis)+dfs(m,n,i,j+1,k,vis)+1;
    }
}

提供一个BFS解法,BFS也是一个标准的模版.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int movingCount(int m, int n, int k) {
       Queue<int[]>queue=new LinkedList<>();
        int dx[]={1,0},dy[]={0,1};
        boolean[][]vis=new boolean[m][n];
        vis[0][0]=true;
        queue.add(new int[]{0,0});
        int res=1;
        while(!queue.isEmpty()){
            int cur[]=queue.poll();
            int x=cur[0],y=cur[1];
            for(int i=0;i<2;i++){
                int a=x+dx[i],b=y+dy[i];
                if(a>=0&&a<=m-1&&b>=0&&b<=n-1&&!vis[a][b]&&
                  (a/10+a%10+b/10+b%10)<=k){
                    vis[a][b]=true;
                    res++;
                    queue.add(new int[]{a,b});
                }
            }
        }
        return res;
    }
}

14、剪绳子 https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题目意思很明确，给我们一根长度为n的绳子，把绳子剪成m段，使得最后的乘积最大.

  • 我们应该尽可能地将绳子剪为3，多余的用2补齐。
  • 如果长度为5，此时(2,3)>(1,4)。
  • 如果长度为6，(3,3)>(2,2,2)。
  • 往后同理，即我们最多只能留两个2，因为3段长度为2的绳子可以用两段长度为3的绳子代替
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int cuttingRope(int n) {
           if(n<=3) return n-1;
        int res=1;
            while(n%3==1){
                n-=4;
                res*=4;
            }
            while(n%3==2){
                n-=2;
                res*=2;
            }
            
        while(n>0){
            n-=3;
            res*=3;
        }
        return res;
    }
}

14-2 剪绳子II https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/

思路跟上一题是一样的

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return 1*(n-1);
        long res=1;
        while(n>4){
             res=(res*3)%1000000007;
             n-=3;
        }
        return (int) (res*n%1000000007);
    }
}

15、二进制中1的个数 https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

利用语法

1
2
3
4
5
public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

利用位运算。把一个整数减-1，然后与原来的整数做与运算，会把最右边的数字由1变成0，我们记录这个次数

1
2
3
4
5
6
7
8
9
10
public class Solution{
   public int hammingWeight(int n){
      int res=0;
     while(n!=0){
        res++;
       n=n&(n-1);
     }
     return res
   }
}

16、数值的整数次方 https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

1
2
3
4
5
6
7
8
9
10
class Solution {
    public double myPow(double x, int n) {
          if(n==0) return 1;
        if(n==1) return x;
        if(n==-1) return 1/x;
        double half=myPow(x,n/2);
        double mod=myPow(x,n%2);
        return half*half*mod;
    }
}

快速幂非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double myPow(double x, int n) {
        if(x>1&&n==Integer.MIN_VALUE) return 0;
           double res=1;
        int temp=Math.abs(n);
        while(temp>0){
            if(temp%2==1){
                res*=x;
            }
            x*=x;
            temp>>=1;
        }
        return n>0?res:1/res;
    }
}

17、打印从1到最大的n位数 https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

好像这一题对原题也有改动，具体的原题不记得了

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] printNumbers(int n) {
        int len=(int)Math.pow(10,n)-1;
        int res[]=new int[len];
        for(int i=0;i<len;i++){
            res[i]=i+1;
        }
        return res;
    }
}

18、删除链表的节点 https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

本题相对于剑指offer原题进行了稍加改动

首先链表中各个节点的值互不相同，我们不必考虑重复节点的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head==null) return null;
           ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;
    while(pre!=null&&pre.next!=null){
        if(pre.next.val==val) pre.next=pre.next.next;
        pre=pre.next;  
    }
        return dummy.next;
    }
}

递归解法

1
2
3
4
5
6
7
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
           if(head==null) return null;
        head.next=deleteNode(head.next,val);
       return head.val==val?head.next:head;
    }
}

当然，本题的原题的题意给定一个单向链表的节点指针，定义一个函数在O(1)的时间内删除该节点.

假设链表一定存在，并且该节点一定不是尾节点。

1
2
3
4
5
6
7
8
9
class Solution{
   public void deleteNode(ListNode node){
     //如果该节点不是尾节点，那么它的下一个节点一定非空
     //我们可以利用下一个节点的值，把当前节点的值覆盖
     node.val=node.next.val;
     //删除node的下一个节点
     node.next=node.next.next;
   }
}

19、正则表达式匹配 https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
   public boolean isMatch(String s,String p){
      if(p.isEmpty()) return s.isEmpty();
     //首字母是否匹配
     boolean first_match=!s.isEmpty()&&(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.');
     //与'*'匹配，存在两种情况
     //1、'*'号匹配0个字符，此时我们直接砍掉p的前两个字符
     //2、'*'号匹配1个或多个字符，此时我们要确认二者首字母是否匹配，然后砍掉s的首字母继续匹配
    if(p.length()>=2&&p.charAt(1)=='*'){
       return isMatch(s,p.substring(2))||(first_match&&isMatch(s.substring(1),p));
    }
     return first_match&&isMatch(s.substring(1),p.substring(1));
     
   }
}
  • 递归在写起代码来比较简单，但是效率属实不高，现在我们转用dp来做
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
class Solution{
    public boolean isMatch(String s,String p){
           boolean dp[][]=new boolean[s.length()+1][p.length()+1];
        dp[0][0]=true;
      //当s字符串为空时
      for(int j=2;j<=p.length();j++){
        //砍掉j的前两个字符
        dp[0][j]=p.charAt(j-1)=='*'&&dp[0][j-2];
      }
      for(int i=0;i<s.length();i++){
        for(int j=0;j<p.length();j++){
          if(p.charAt(j)=='*'){
            //现在的转移方程与上面的递归式子是一样的。
            dp[i+1][j+1]=dp[i+1][j-1]||(first_match(s,p,i,j-1)&&dp[i][j+1]);
          }else{
            dp[i+1][j+1]=first_match(s,p,i,j)&&dp[i][j];
          }
        }
      }
      return dp[s.length()][p.length()];
    }
  private boolean first_match(String s,String p,int i,int j){
          return (s.charAt(i)==p.charAt(j))||(p.charAt(j)=='.');
  }
}

20、表示数值的字符串 https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/

个人感觉这道题是为测试人员所出的，各种奇形怪状的判定……

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
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean isNumber(String s) {
        
         //去除空格
        s=s.trim();
         if(s==null||s.length()==0) return false;
        //第一个字符为正负号，直接去掉
        if(s.charAt(0)=='+'||s.charAt(0)=='-') s=s.substring(1);
        // +, -, .,
        if(s.isEmpty()||(s.charAt(0)=='.'&&s.length()==1)) return false;
        
        //点的数量和e的数量
        int dot=0,e=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)>='0'&&s.charAt(i)<='9');
            else if(s.charAt(i)=='.'){
                dot++;
                //出现两个.不合法
                if(dot>1||e>0) return false;
            }
            else if(s.charAt(i)=='e'||s.charAt(i)=='E'){
                e++;
                //e的前后都必须要有数字
                if(i==0||i==s.length()-1||e>1||i==1&&s.charAt(i-1)=='.') return false;
                //如果出现e+...的情况，则要保证后面有数字
                if(s.charAt(i+1)=='+'||s.charAt(i+1)=='-'){
                    if(i+2==s.length()) return false;
                    i++;
                }
            }
            else return false;
        }
        return true;
        
    }
}

21、调整数组顺序使奇数位于偶数前面

本题是一道意思很明确的题目。如果我们利用额外的空间，可以很容易的解决这个问题，例如将奇数和偶数分别放在不同的集合中，然后在顺序放入。

我们也可以利用不需要额外空间复杂度的方法，我们可以利用快速排序中partation的过程，将奇数都放左边，偶数都放右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
      public int []exchange(int []nums){
            int l=0,r=nums.length-1;
        while(l<r){
            while(l<r&&nums[l]%2==1) l++;
            while(l<r&&nums[r]%2==0)r--;
           if(l<r){
              int temp=nums[l];
             nums[l]=nums[r];
             nums[r]=temp;
             
           }
        }
        return nums;
      }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家