leetcode 21-30

LeetCode 21-30

21、合并两个有序链表 https://leetcode-cn.com/problems/merge-two-sorted-lists/

提供两种做法 1、我们将这一步骤可以看为归并排序最后一步合并的操作，然后利用dummyNode即可

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 ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                cur.next=l1;
                cur=cur.next;
                l1=l1.next;
            }else{
                cur.next=l2;
                cur=cur.next;
                l2=l2.next;
            }
        }
        if(l1!=null){
            cur.next=l1;
            l1=l1.next;
        }
        if(l2!=null){
            cur.next=l2;
            l2=l2.next;
        }
        return dummy.next;
    }
}

2、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1==null)return l2;
            if(l2==null)return l1;
             if(l1.val<=l2.val) {
                 l1.next= mergeTwoLists(l1.next,l2);
                 return l1;
             }else{
                 l2.next= mergeTwoLists(l1,l2.next);
                 return l2;
             }
      
    }
}

22、括号生成https://leetcode-cn.com/problems/generate-parentheses/

dfs+回溯

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 {
    private List<String>res=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n==0)return res;
      //有n对括号，那么左边有n个，右边有n个
        dfs(n,n,new StringBuilder());
        return res;
    }
    private void dfs(int left,int right,StringBuilder sb){
        if(left==0&&right==0){
            res.add(sb.toString());
            return;
        }
     //可以生成左括号
        if(left>0){
            dfs(left-1,right,sb.append("("));
            sb.deleteCharAt(sb.length()-1);
            
        }
            //可以生成右括号
        if(left<right) {
            dfs(left,right-1,sb.append(")"));
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

23、合并K个排序链表 https://leetcode-cn.com/problems/merge-k-sorted-lists/

利用最小堆，并且依次取出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
         if(lists.length==0) return null;
      //按照节点大小的值，升序排列
         PriorityQueue<ListNode>queue=new PriorityQueue<>((o1,o2)->o1.val-o2.val);
      //将链表加入到最小堆中
         for(ListNode list:lists){
            if(list!=null)queue.add(list);
         }
         ListNode dummy=new ListNode(0);
         ListNode cur=dummy;
          while(!queue.isEmpty()){
              cur.next=queue.poll();
              cur=cur.next;
              if(cur.next!=null)queue.add(cur.next);
          }
        return dummy.next;
        
    }
}

24、两两交换链表中的节点 https://leetcode-cn.com/problems/swap-nodes-in-pairs/

利用递归，我们将整个链表分为三个部分，head -> head.next->剩余部分(剩余部分为已经处理好的)

那么此时我们只需要将上述链表转换为head.next->head->剩余部分

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode swapPairs(ListNode head) {
           if(head==null||head.next==null)return head;
         ListNode next=head.next;
        head.next=swapPairs(next.next);
       next.next=head;
        return next;
    }
}

25、K个一组翻转链表 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

递归解法

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 ListNode reverseKGroup(ListNode head, int k) {
           if(head==null||head.next==null)return head;
        //计算链表总节点个数
           int count=1;
        ListNode cur=head;
        while(cur.next!=null){
            count++;
            cur=cur.next;
        }
        if(count<k) return head;
      //开始反转
        count=k;
        cur=head;
        ListNode newNode=null,next=null;
        while(count>0){
             next=cur.next;
            cur.next=newNode;
            newNode=cur;
            cur=next;
            count--;
        }
        head.next=reverseKGroup(next,k);
        return newNode;
    }
}

非递归解法，利用多个指针

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 ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy=new ListNode(0);
           dummy.next=head;
         ListNode pre=dummy,end=dummy;
        while(end.next!=null){
            for(int i=0;i<k&&end!=null;i++) end=end.next;
            if(end==null) break;
            ListNode start=pre.next;
            ListNode next=end.next;
            end.next=null;
            pre.next=reverse(start);
            start.next=next;
            pre=start;
            end=pre;   
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head){
        ListNode cur=head;
        ListNode newNode=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=newNode;
            newNode=cur;
            cur=next;
        }
        return newNode;
    }
}

26、删除排序数组中的重复项 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

我们利用快慢指针，其中慢指针所指的位置就是数组存放的位置，快指针用来遍历数组中的全部元素

1
2
3
4
5
6
7
8
9
10
class Solution{
  public int removeDuplicates(int[]nums){
        if(nums==null||nums.length==0) return 0;
     int slow=1;
    for(int fast=1;fast<nums.length;fast++){
      if(nums[fast]!=nums[fast-1]) nums[slow++]=nums[fast];
    }
    return slow;
  }
}

27、移除元素https://leetcode-cn.com/problems/remove-element/

与上一题同理，利用快慢指针，一个指针存放数组元素，另外一个遍历整个数组

1
2
3
4
5
6
7
8
9
10
class Solution{
  public int removeElement(int[] nums, int val){
     if(nums==null||nums.length==0) return 0;
     int j=0;
    for(int i=0;i<nums.length;i++){
      if(nums[i]!=val) nums[j++]=nums[i];
    }
    return j;
  }
}

28、实现strStr() https://leetcode-cn.com/problems/implement-strstr/

我们遍历一遍haystack，如果碰到元素与needle的第一个元素相等，那么就继续遍历，否则就清0，然后重新判断

1
2
3
4
5
6
7
8
9
class Solution{
   public int strStr(String haystack, String needle){
     int n=needle.length();
     for(int i=0;i<haystack.length()-n+1;i++){
       if(haystack.substring(i,i+n).equals(needle)) return i;
     }
     return -1;
   }
}

29、两数相除 https://leetcode-cn.com/problems/divide-two-integers/

模拟除法的过程。 我们通过让除数一直向左移，达到逼近被除数的效果

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
class Solution {
  public int divide(int dividend, int divisor) {
          if(divisor==0) return Integer.MAX_VALUE;
          if(dividend==Integer.MIN_VALUE){
              if(divisor==1) return Integer.MIN_VALUE;
              else if(divisor==-1) return Integer.MAX_VALUE;
          }
      int res=0;
      int minus=1;
      
      long divd=(long)dividend;
      long divs=(long)divisor;
      if(divd<0){
          divd=-divd;
          minus=-minus;
      }
      if(divs<0){
          divs=-divs;
          minus=-minus;
      }
      while(divd>=divs){
          int shift=0;
          while(divd>=divs<<shift){
              shift++;
          }
          res+=1<<(shift-1);
          divd-=divs<<(shift-1);
          
      }
      return minus*res;
  }
}

30、串联所有单词的字串 https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

采用哈希表+滑动窗口实现

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 List<Integer> findSubstring(String s,String words[]){
      List<Integer>res=new ArrayList<>();
      if(s.length()==0||words.length==0)return res;
    int m=words.length,n=words[0].length;
    if(s.length()<m*n) return res;
    Map<String,Integer>map=new HashMap<>();
    for(String word:words) map.put(word,map.getOrDefault(word,0)+1);
    //滑动窗口
    for(int i=0;i<s.length()-m*n+1;i++){
      String substr=s.substring(i,i+n*m);
      Map<String,Integer>window=new HashMap<>();
      for(int j=0;j<m*n;j+=n){
        //截取单词
        String str=substr.substring(j,j+n);
        window.put(str,window.getOrDefault(str,0)+1);
      }
      if(map.equals(window)) res.add(i);
    }
    return res;
  }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

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