leetcode1-10

LeetCode 1-10

1、两数之和 https://leetcode-cn.com/problems/two-sum/

如果本题使用暴力的做法，就直接双重for循环，此时时间复杂度是O(n^2)，这里我们需要利用哈希表去记录元素。

如果使用哈希表的话，时间复杂度是O(n)，空间复杂度也是O(n)，此时相当于 用空间换时间

1
2
3
4
5
6
7
8
9
10
11
12
class Solution{
  public int []twoSum(int []nums,int target){
        if(nums==null||nums.length==0) return new int[]{-1,-1};
     Map<Integer,Integer>map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
       int diff=target-nums[i];
      if(map.containsKey(diff)) return new int[]{i,map.get(diff)};
      map.put(nums[i],i);
    }
    return new int []{-1,-1};
  }
}

2、两数相加 https://leetcode-cn.com/problems/add-two-numbers/

本题就是一个模拟加法的过程，在关于链表的解题中，我们可以采取构造出虚拟头节点的方法，避免头节点的判断。

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         if(l1==null) return l2;
         if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
       ListNode cur=dummy;
       int carry=0;
      int sum=0;
      while(l1!=null||l2!=null){
         if(l1!=null&&l2!=null){
           sum=l1.val+l2.val+carry;
           l1=l1.next;
           l2=l2.next;
         }else if(l1!=null){
            sum=l1.val+carry;
           l1=l1.next;
         }else {
           sum =l2.val+carry;
           l2=l2.next;
         }
         cur.next=new ListNode(sum%10);
        cur=cur.next;
        carry=sum/10;
      }
      if(carry!=0) cur.next=new ListNode(carry);
      return dummy.next;
    }
}

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 lengthOfLongestSubstring(String s) {
         if(s==null||s.length()==0) return 0;
        int res=0;
        int i=0,j=0;
        int []freq=new int[128];
        while(j<s.length()){
             char c1=s.charAt(j);
            freq[c1]++;
            j++;
            while(freq[c1]>1){
                char c2=s.charAt(i);
                freq[c2]--;
                i++;
            }
            res=Math.max(res,j-i);
        }
        return res;
    }
}

4、寻找两个正序数组的中位数

本题我们利用递归的思想，寻找数组中的第k个数。 在递归的过程中，可以直接舍弃某一段数组一般的长度，最后的时间复杂度为O(log(m+n))

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
37
38
39
40
41
42
43
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n=nums1.length+nums2.length;
      //如果总长度为偶数，我们计算中间两个数的平均数
       if(n%2==0){
         int left=find(nums1,0,nums2,0,n/2);
         int right=find(nums1,0,nums2,0,n/2+1);
         return (left+right)/2.0;
       }else{
         //如果总长度为奇数，直接求出最中间的一个数即可
          return find(nums1,0,nums2,0,n/2+1);
       }
    }
  /**
  *找数组中的第k个数
  */
  private int find(int nums1[],int i,int nums2[],int j,int k){
           //保证nums1的长度小于nums2
        if(nums1.length-i>nums2.length-j){
          return find(nums2,j,nums1,i,k);
        }
    //如果是查找第一个数
        if(k==1){
           if(nums1.length==i){
             return nums2[j];
           }
          return Math.min(nums1[i],nums2[j]);
        }
    if(nums1.length==i){
       return nums2[j+k-1];
    }
    //计算两个数组第k个数的索引
     int si=Math.min(nums1.length,i+k/2),sj=j+k-k/2;
    //舍弃第二个数组的前半段
     if(nums1[si-1]>nums2[sj-1]){
       return find(nums1,i,nums2,sj,k-(sj-j));
     }else{
       //舍弃第一个数组的前半段
       return find(nums1,si,nums2,j,k-(si-i));
     }
    
  }
}

5、最长回文字串 https://leetcode-cn.com/problems/longest-palindromic-substring/

因为是判断回文子串， 我们可以使用最常规的方法，本题java可以利用O(n^3)的复杂度通过。先把暴力解法写一下

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
class Solution {
    public String longestPalindrome(String s) {
        String res="";
        int len=0;
         for(int i=0;i<s.length();i++){
             for(int j=i+1;j<=s.length();j++){
                 if((j-i)>len&&isValid(s.substring(i,j))){
                     len=j-i;
                     res=s.substring(i,j);
                     
                 }
             }
         }
        return res;
        
    }
    private boolean isValid(String s){
        int l=0,r=s.length()-1;
        while(l<r){ 
            if(s.charAt(l)!=s.charAt(r)) return false;
            l++;
            r--;
        }
        return  true;
    }
}

接下来我们考虑这样一种方式。

如果字符串长度为奇数，我们从中点开始左右扩张 枚举i的长度，左右边界为i-1,i+1 .

如果字符串长度为偶数，左右边界为i,i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
  public String longestPalindrome(String s){
    String res="";
    for(int i=0;i<s.length();i++){
       int l=i-1,r=i+1;
      while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
        l--;
        r++;
      }
      if(res.length()<r-l-1) res=s.substring(l+1,r);
      l=i;
      r=i+1;
       while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
        l--;
        r++;
      }
      if(res.length()<r-l-1) res=s.substring(l+1,r);
      
      
    }
    return res;
  }
}

6、Z字形变换

本题是一个找规律的题目。 当我们从最上面一行，遍历到最下面一行时，索引顺序是增加的，当我们从最下面一行遍历到最上面一行的时候，索引顺序再减少。即是一个往返的过程，我们需要引入一个变量控制这个顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
   public String convert(String s,int numRows){
      if(numRows<=1) return s;
     StringBuilder[]sb=new StringBuilder[numRows];
     for(int i=0;i<numRows;i++){
        sb[i]=new StringBuilder();
     }
     //控制顺序的变量
     boolean flag=true;
     int row=0;
     for(int i=0;i<s.length();i++){
         sb[row].append(s.charAt(i));
       //当是第一行和最后一行时，反转
       if(row==0||row==numRows-1)flag=!flag;
       if(flag) row--;
       else row++;
     }
     StringBuilder res=new StringBuilder();
     for(int i=0;i<numRows;i++) res.append(sb[i]);
     return res.toString();
   }
}

7、整数反转

本题可以使用转换为字符串再考虑的方法

接下来主要讲数学方法：

假设x=1234， 为了得到个位数字，我们每次将 x%10 ,然后x/10,这样就得到了4 ，3，2，1

然后我们将4,3,2,1变成4321 这也是一个固定的套路，即 从最高位开始累加，

n=n*10+x

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int reverse(int x) {
         long n=0;
         while(x!=0){
             n=n*10+x%10;
             x=x/10;
         }
         return (int)n==n?(int)n:0;
    }
}

8、字符串转换整数(atoi)

其实本题就是一个模拟题，为了省去多余的步骤，我们可以先用long，最后转换为int

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
class Solution{
  public int myAtoi(String str){
        int k=0;
    char[]ch=str.toCharArray();
    //去除空格
    while(k<str.length()&&ch[k]==' ')k++;
   if(k==str.length())return 0;
    //选取正负号
    int minus=1;
    if(ch[k]=='-'){
      minus=-1;
      k++;
    }else if(ch[k]=='+'){
      k++;
    }
    long res=0;
    while(k<str.length()&&ch[k]>='0'&&ch[k]<='9'){
          res=res*10+ch[k]-'0';
      k++;
      //如果溢出直接中断
      if(res>Integer.MAX_VALUE) break;
      
    }
     res*=minus;
     if(res>Integer.MAX_VALUE) return Integer.MAX_VALUE;
      if(res<Integer.MIN_VALUE) return Integer.MIN_VALUE;
    return (int)res;
    
  }
}

9、回文数

本题最直接的做法就是转换为字符串，然后再判断是否是回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;
       String s=String.valueOf(x);
      int l=0,r=s.length()-1;
      while(l<r){
        if(s.charAt(l)!=s.charAt(r)) return false;
        l++;
        r--;
      }
      return true;
    }
}

或者我们可以采用第7题的方法，先将该数字反转过来，然后对比是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPalindrome(int x) {
     if(x<0) return false;
      //将x保存
        int temp=x;
      int n=0;
      //反转x
        while(x!=0){
            n=n*10+x%10;
            x/=10;
        }
        return n==temp;
    }
}

10、正则表达式匹配 https://leetcode-cn.com/problems/regular-expression-matching/

本题有一个很直接的做法，我们直接采取dfs搜索的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)=='.');
     //第一种情况，*匹配0个元素
       //第二种情况,*匹配一个或多个元素
     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做法

dp(i,j)表示s的前i个字符和p的前j个字符是否匹配.

其实当明白了上述的递归做法后，下面的dp理解起来也非常简单。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
26
27
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 i=2;i<=p.length();i++){
       dp[0][i]=(p.charAt(i-1)=='*'&&dp[0][i-2]);
     }
     for(int i=0;i<s.length();i++){
       for(int j=0;j<p.length();j++){
         if(p.charAt(j)=='*'){
           //与之前一样，第一种情况匹配0个字符，即截掉p的前两个字符再比较
           //第二种情况匹配一个或者多个字符，那么截掉s的第一个字符再比较
           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)=='.');
  }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

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>谢谢大家