51题解–构建乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

思路解析

因为该题无法运用除法，所以我们需要另外想办法，这里我们可以将整个乘积数组看成是以下两部分：

这样分两个区间，两个循环就能解决问题

源代码

public class Solution {
public int[] multiply(int[] A) {
    int []B=new int [A.length];
    for(int i=0;i<B.length;i++)
    {
      int sum1=1;
      int sum2=1;
      for(int j=0;j<i;j++)
        sum1*=A[j];
      for(int j=i+1;j<B.length;j++)
        sum2*=A[j];
      B[i]=sum1*sum2;
    }
    return B;
    }
}

52题解–正则表达式匹配*****

题目描述

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

思路解析

这题是真的恶心，卡了我好久，关键最后还没A出来。看了别人的题解也是模模糊糊。

这里我就不讲解了，直接贴出大神的想法。评论区大家可以讨论讨论

当模式中的第二个字符不是“”时：

1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。

2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是“”时：

如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：

1、模式后移2字符，相当于x被忽略；

2、字符串后移1字符，模式后移2字符；

3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为可以匹配多位；

源代码

public class Solution {
    public boolean match(char[] str, char[] pattern) {
    if (str == null || pattern == null) {
        return false;
    }
    int strIndex = 0;
    int patternIndex = 0;
    return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
    //有效性检验：str到尾，pattern到尾，匹配成功
    if (strIndex == str.length && patternIndex == pattern.length) {
        return true;
    }
    //pattern先到尾，匹配失败
    if (strIndex != str.length && patternIndex == pattern.length) {
        return false;
    }
    //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
    if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2，视为x*匹配0个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
        } else {
            return matchCore(str, strIndex, pattern, patternIndex + 2);
        }
    }
    //模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
    if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
        return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
    }
    return false;
  }
}

53题解–表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

思路解析

字符串处理的问题，但是这题要考虑的店非常的多，处理起来也是比较的麻烦，主要注意以下的点。

设置三个标志符分别记录“+/-”、“e/E”和“.”是否出现过。

对于“+/-”：正常来看它们第一次出现的话应该出现在字符串的第一个位置，如果它第一次出现在不是字符串首位，而且它的前面也不是“e/E”，那就不符合规则；如果是第二次出现，那么它就应该出现在“e/E”的后面，如果“+/-”的前面不是“e/E”，那也不符合规则。

对于“e/E”：如果它的后面不接任何数字，就不符合规则；如果出现多个“e/E”也不符合规则。

对于“.”：出现多个“.”是不符合规则的。还有“e/E”的字符串出现“.”也是不符合规则的。同时，要保证其他字符均为 0-9 之间的数字。

源代码

public class Solution {
    public boolean isNumeric(char[] str) {
        int len = str.length;
        boolean sign = false, decimal = false, hasE = false;
        for(int i = 0; i < len; i++){
            if(str[i] == '+' || str[i] == '-'){
                if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E')
                    return false;
                if(sign && str[i-1] != 'e' && str[i-1] != 'E')
                    return false;
                sign = true;
            }else if(str[i] == 'e' || str[i] == 'E'){
                if(i == len - 1)
                    return false;
                if(hasE)
                    return false;
                hasE = true;
            }else if(str[i] == '.'){
                if(hasE || decimal)
                    return false;
                decimal = true;
            }else if(str[i] < '0' || str[i] > '9')
                return false;
        }
        return true;
    }
}

54题解–字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述:

如果当前字符流没有存在出现一次的字符，返回#字符。

思路解析

这题本质上也是使用list进行循环添加，之后进行比较输出即可。

源代码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
public  class Node {
      int val;
      char ch;
      Node(char ch) {
          this.ch =ch;
          this.val=1;
      }
  }
   String str="";
   public void Insert(char ch)
      {
          str=str+ch;
      }
   public char FirstAppearingOnce()
      {
     char flag='#';
     char[]ch=str.toCharArray();
     Set<Character>set=new HashSet<Character>();
     List<Node>list=new ArrayList<Node>();
     for(int i=0;i<ch.length;i++)
     {
       if(!set.contains(ch[i]))
       {
         set.add(ch[i]);
         Node node=new Node(ch[i]);
         list.add(node);
       }
       else
       {
         for(int j=0;j<list.size();j++)
         {
           if(list.get(j).ch==ch[i])
             list.get(j).val++;
         }
       }
     }
     for(int i=0;i<list.size();i++)
     {
       if(list.get(i).val==1)
       {
         flag=list.get(i).ch;
         break;
       }
     } 
     return flag;
      }
}

55题解–链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路解析

首先我们举一个出现环状的链表的例子。

显然我们可以想到通过遍历的方式，但是一旦出现环，那么我们是遍历不完的，所以我们必须添加截止条件，每次我们遍历一个元素时就将他的值存入list之中，这样我们就能进行判断，如果list中不存在说明是第一次遍历到，否则就是第二次遍历到，第二次遍历到就说明已经出现环状，所以就可以直接返回该节点。如果没有环，那么遍历结束返回null即可。

源代码

/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.ArrayList;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ArrayList<Integer>list=new ArrayList<Integer>();
    while(pHead!=null) 
    {
        //判断是否存在，第一次直接添加
      if(!list.contains(pHead.val))
        list.add(pHead.val);
      //第二次出现，说明出现环，直接返回该节点
      else {
        return pHead;
      }
      if(pHead.next!=null)
        pHead=pHead.next;
      else
        break;
    }
    //执行到这里说明链表已经遍历完毕所以不存在环，返回null即可
    return null;
    }
}