leetcode 11-20

Leetcode11-20

11、盛最多水的容器https://leetcode-cn.com/problems/container-with-most-water/

在最开始，我们将连个指针分别指向头尾，此时的底部最大，要想增大盛水面积，我们只能通过增大高度来实现。注意我们每次移动底部只会少1,那么就意味着我们应该向着高度更高的地方移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxArea(int[] height) {
           if(height==null||height.length==0) return 0;
           int l=0,r=height.length-1;
        int res=0;
        while(l<r){
            if(height[l]<height[r]){
                res=Math.max(height[l]*(r-l),res);
                l++;
            }else{
                res=Math.max(height[r]*(r-l),res);
                r--;
            }
        }
        return res;
    }
}

12、整数转罗马数字 https://leetcode-cn.com/problems/integer-to-roman/

枚举所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String intToRoman(int num) {
        Map<Integer,String>map=new HashMap<>();
        int []nums={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String strs[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<nums.length;i++) map.put(nums[i],strs[i]);
        for(int i=0;i<nums.length;i++){
            while(num>=nums[i]){
                num-=nums[i];
                sb.append(map.get(nums[i]));
            }
            
        }
        return sb.toString();
    }
}

13、罗马数字转整数 https://leetcode-cn.com/problems/roman-to-integer/

利用哈希表做简单的映射即可

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 int romanToInt(String s){
         Map<Character,Integer>map=new HashMap<>();
         char c[]={'I','V','X','L','C','D','M'};
         int nums[]={1,5,10,50,100,500,1000};
         for(int i=0;i<nums.length;i++){
             map.put(c[i],nums[i]);
         }
         int res=0;
          char arr[]=s.toCharArray();
         for(int i=s.length()-1;i>=0;i--){
             if(i==arr.length-1){
                 res+=map.get(arr[i]);
                 continue;
             }
             if(map.get(arr[i])<map.get(arr[i+1])) res-=map.get(arr[i]);
             else res+=map.get(arr[i]);
         }
               return res;
         
     }
}

14、最长公共前缀 https://leetcode-cn.com/problems/longest-common-prefix/\\

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
    public String longestCommonPrefix(String[] strs){
         if(strs==null||strs.length==0) return "";
        String res=strs[0];
        for(String str:strs){
            //必须从0开始包含
            while(str.indexOf(res)!=0){
                //开始滑动求解
                res=res.substring(0,res.length()-1);
            }
        }
        return res;
    }
}

15、三数之和 https://leetcode-cn.com/problems/3sum/

与之前的两数之和类似，不过这里多了一个去重的操作，为了更加方便去重，我们对数组先排序，让相等的两个数都挨着。

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 List<List<Integer>> threeSum(int[] nums) {
       List<List<Integer>> res=new ArrayList<>();
        if(nums.length<3) return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            int l=i+1,r=nums.length-1;
             if(i>0&&nums[i]==nums[i-1]) continue;
            while(l<r){
                if(nums[i]+nums[r]+nums[l]==0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while(l<r&&nums[l]==nums[l+1]) l++;
                    while(l<r&&nums[r]==nums[r-1])r--;
                    l++;
                    r--;
                }else if(nums[i]+nums[r]+nums[l]<0) l++;
                else r--;
                
            }
        }
        return res;
    }
}

16、最接近的三数之和 https://leetcode-cn.com/problems/3sum-closest/

与上述三数之和基本思想一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int threeSumClosest(int[] nums, int target) {
           if(nums.length<3) return 0;
        Arrays.sort(nums);
        int min=nums[0]+nums[1]+nums[2];
           for(int i=0;i<nums.length-2;i++){
               int l=i+1,r=nums.length-1;
               while(l<r){
                   int sum=nums[i]+nums[l]+nums[r];
                   if(Math.abs(sum-target)<Math.abs(min-target)){
                       min=sum;
                   }
                   if(sum==target) return sum;
                   else if(sum>target) r--;
                   else l++;
               }
           }
        return min;
    }
}

17、电话号码的字母组合 https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

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
27
28
29
30
31
32
33
34
class Solution{
    private List<String>res=new ArrayList<>();
    private StringBuilder sb=new StringBuilder();
     public List<String> letterCombinations(String digits){
          if(digits==null||digits.length()==0) return res;
         dfs(digits,0);
         return res;
     }
    private void dfs(String digits,int index){
        if(sb.length()==digits.length()){
            res.add(sb.toString());
            return ;
        }
        String s=convert(digits.charAt(index));
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            dfs(digits,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
        
    }
    //建立映射，这里也可以通过哈希表来完成
    private String convert(char c){
         if(c=='2') return "abc";
        if(c=='3') return "def";
        if(c=='4') return "ghi";
        if(c=='5') return "jkl";
        if(c=='6') return "mno";
        if(c=='7') return "pqrs";
        if(c=='8') return "tuv";
        if(c=='9') return "wxyz";
        return "";
    }
}

18、四数之和 https://leetcode-cn.com/problems/4sum/

受之前最接近的三数之和的启发，在这边我们引入剪枝策略。 大致情况和三数之和类似

如果不引入剪枝，效果大概差了8倍左右

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
         List<List<Integer>> res=new ArrayList<>();
        if(nums==null||nums.length<4) return res;
        Arrays.sort(nums);
       int n=nums.length;
        int minValue=nums[0]+nums[1]+nums[2]+nums[3];
        int maxValue=nums[n-1]+nums[n-2]+nums[n-3]+nums[n-4];
        if(minValue>target||target>maxValue) return res;
        for(int i=0;i<nums.length-3;i++){
             if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                int l=j+1,r=nums.length-1;
                minValue=nums[i]+nums[j]+nums[l]+nums[l+1];
                maxValue=nums[i]+nums[j]+nums[r]+nums[r-1];
                if(minValue>target||maxValue<target) continue;
                while(l<r){
                    int sum=nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        while(l<r&&nums[l]==nums[l+1])l++;
                        while(l<r&&nums[r]==nums[r-1])r--;
                        l++;
                        r--;
                    }else if(sum<target) l++;
                    else r--;
                }
                
            }
        }
        return res;
    }
}

不剪枝的代码

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 List<List<Integer>> fourSum(int[] nums, int target) {
      List<List<Integer>>res=new ArrayList<>();
        if(nums==null||nums.length<4) return res;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                int l=j+1,r=nums.length-1;
                while(l<r){
                    int sum=nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        while(l<r&&nums[l]==nums[l+1])l++;
                        while(l<r&&nums[r]==nums[r-1])r--;
                        l++;
                        r--;
                    }else if(sum>target) r--;
                    else l++;
                }
            }
        }
        return res;
    }
}

19、删除链表的倒数第N个节点 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

受之前寻找链表中倒数第N个节点的启发，我们在这里寻找倒数第k个节点，然后进行删除操作，有可能要删除第一个节点，此时我们引入dummyNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode dummy=new ListNode(0);
          dummy.next=head;
        ListNode fast=dummy;
        ListNode slow=dummy;
        for(int i=0;i<n;i++)fast=fast.next;
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

20、有效的括号 https://leetcode-cn.com/problems/valid-parentheses/

利用栈后进先出的特性，我们将所有的左括号全部入栈，然后一一比对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValid(String s) {
           Stack<Character>stack=new Stack<>();
        if(s==null||s.length()==0) return true;
           for(int i=0;i<s.length();i++){
                char c=s.charAt(i);
               if(c=='('||c=='['||c=='{') stack.push(c);
               else{
                   if(stack.isEmpty()) return false;
                   char top=stack.pop();
                   if(top=='('&&c!=')') return false;
                   if(top=='['&&c!=']') return false;
                   if(top=='{'&&c!='}') return false;
               }
           }
        return stack.isEmpty();
    }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

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