• Leetcode刷题-(16~20)-Java+Python+JavaScript

     

    算法是程序员的基本功，也是各个大厂必考察的重点，让我们一起坚持写算法题吧。

    遇事不决，可问春风，春风不语，即是本心。

    我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

    目录

    1.最接近三数之和

    2.电话号码的字母组合

    3.四数之和

    4.删除链表的倒数第 N 个结点

    5.有效的括号

    1.最接近三数之和

    题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/3sum-closest/description/

    思路：1.三层循环暴力法。

    2.排序+双指针。

    Java版：
     

    1. class Solution {
    2.     public int threeSumClosest(int[] nums, int target) {
    3.         int min = Integer.MAX_VALUE ;
    4.         int res = 0 ;
    5.         for(int i=0; i
    6.             for(int j=i+1; j
    7.                 for(int k=j+1; k
    8.                     int abs = Math.abs(target -(nums[i] + nums[j] + nums[k]) ) ;
    9.                     if(abs < min){
    10.                         min = abs ;
    11.                         res = nums[i] + nums[j] + nums[k] ;
    12.                     }
    13.                 }
    14.             }
    15.         }
    16.         return res ;
    17.     }
    18. }
    1. class Solution {
    2.     public int threeSumClosest(int[] nums, int target) {
    3.         // 排序+双指针
    4.         Arrays.sort(nums) ;
    5.         int res = 0 ;
    6.         int min = Integer.MAX_VALUE ;
    7.         for(int i=0; i1; i++){
    8.             int left = i+1, right = nums.length - 1 ;
    9.             while(left < right){
    10.                 int sum = nums[i] + nums[left] + nums[right] ;
    11.                 int abs = Math.abs(sum - target) ;
    12.                 if(abs < min){
    13.                     min = abs ;
    14.                     res = sum ;
    15.                 }
    16.                 if(sum == target){
    17.                     return sum ;
    18.                 }else if(sum < target){
    19.                     left ++ ;
    20.                 }else{
    21.                     right -- ;
    22.                 }
    23.             }
    24.         }
    25.         return res ;
    26.     }
    27. }

    Python版：

    1. class Solution:
    2.     def threeSumClosest(self, nums: List[int], target: int) -> int:
    3.         nums.sort() 
    4.         l = len(nums)
    5.         res = 0 
    6.         min = 1000000
    7.         for i in range(l-2):
    8.             left = i+1
    9.             right = l - 1
    10.             while(left < right):
    11.                 sum = nums[i] + nums[left] + nums[right]
    12.                 sub = abs(sum - target)
    13.                 if(sub < min):
    14.                    min = sub
    15.                    res = sum 
    16.                 if (sum == target):
    17.                    return sum 
    18.                 elif(sum < target):
    19.                    left += 1
    20.                 else:
    21.                    right -= 1
    22.             
    23.         return res 
    24.

    Javascript版：

    1. /**
    2.  * @param {number[]} nums
    3.  * @param {number} target
    4.  * @return {number}
    5.  */
    6. var threeSumClosest = function(nums, target) {
    7.     // JS需要自定义排序规则，因为默认情况是按照字符串进行排序，而不是数值
    8.     nums.sort(function(a,b){
    9.         return a - b
    10.     }) 
    11.     let res = 0 
    12.     let min = 10000000
    13.     for(let i=0; ilength; i++){
    14.         let left = i + 1, right = nums.length - 1
    15.         while(left < right){
    16.             const sum = nums[i] + nums[left] + nums[right] 
    17.             const abs = Math.abs(sum - target)
    18.             if(abs < min){
    19.                 min = abs
    20.                 res = sum 
    21.             }
    22.             if(sum == target){
    23.                 return sum
    24.             }else if(sum > target){
    25.                 right -- 
    26.             }else{
    27.                 left ++ 
    28.             }
    29.         }
    30.     }
    31.     return res 
    32. };

    2.电话号码的字母组合

    题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
    思路：方法1：条件函数判断+字符串拼接

    方法2：hashmap+dfs

    Java版：
     

    1. class Solution {
    2.     public List letterCombinations(String digits) {
    3.          List list = new ArrayList<>() ;
    4.          String str = "" ;
    5.          String [] arr = new String[4] ;
    6.          Arrays.fill(arr,"") ;
    7.         for(int i=0; i
    8.             arr[i] = f(digits.charAt(i)) ;
    9.         }
    10.                         
    11.         for(int i=0; i0].length(); i++){
    12.             if(arr[1].length()==0){
    13.                  StringBuilder sb = new StringBuilder("") ;
    14.                  sb.append(arr[0].charAt(i)) ;
    15.                  list.add(sb.toString()) ;
    16.             }
    17.             for(int j=0; j1].length(); j++){
    18.                    if(arr[2].length()==0){
    19.                     StringBuilder sb = new StringBuilder("") ;
    20.                     sb.append(arr[0].charAt(i))
    21.                     .append(arr[1].charAt(j)) ;
    22.                     list.add(sb.toString()) ;     
    23.             }
    24.                 for(int k=0;  k2].length(); k++){
    25.                     if(arr[3].length()==0){
    26.                     StringBuilder sb = new StringBuilder("") ;
    27.                     sb.append(arr[0].charAt(i))
    28.                     .append(arr[1].charAt(j))
    29.                     .append(arr[2].charAt(k)) ;
    30.                     list.add(sb.toString()) ;
    31.                     }
    32.                     for(int l=0;  l3].length(); l++){
    33.                         StringBuilder sb = new StringBuilder("") ;
    34.                         sb.append(arr[0].charAt(i))
    35.                          .append(arr[1].charAt(j))
    36.                          .append(arr[2].charAt(k))
    37.                          .append(arr[3].charAt(l)) ;
    38.                          list.add(sb.toString()) ;
    39.                     }
    40.                 }
    41.             }
    42.            
    43.         }
    44.         return list ;
    45.     
    46. }
    47. public static String f(char c){
    48.     switch(c){
    49.         case '2': return "abc";
    50.         case '3': return "def";
    51.         case '4': return "ghi";
    52.         case '5': return "jkl"; 
    53.         case '6': return "mno";
    54.         case '7': return "pqrs";
    55.         case '8': return "tuv";
    56.         case '9': return "wxyz";
    57.         default : return "";
    58.     }
    59. }
    60. }
    1. class Solution {
    2.     public List letterCombinations(String digits) {
    3.        
    4.         List list = new ArrayList<>() ;
    5.         Map map = new HashMap<>() ;
    6.          if(digits.length() == 0){
    7.             return list ;
    8.         }
    9.         map.put('2',"abc") ;
    10.         map.put('3',"def") ;
    11.         map.put('4',"ghi") ;
    12.         map.put('5',"jkl") ;
    13.         map.put('6',"mno") ;
    14.         map.put('7',"pqrs") ;
    15.         map.put('8',"tuv") ;
    16.         map.put('9',"wxyz") ;
    17.         dfs(map,digits,0,list,new StringBuilder()) ;
    18.         return list ;
    19. }
    20. public void dfs(Map map,String digits, int k, List list, StringBuilder sb){
    21.      
    22.      if(k==digits.length()){
    23.          list.add(sb.toString()) ;
    24.      }else{
    25.          String s = map.get(digits.charAt(k)) ;
    26.          for(int i=0; i
    27.              sb.append(s.charAt(i)) ;
    28.              dfs(map,digits,k+1,list,sb) ;
    29.              sb.deleteCharAt(k) ;
    30.          }
    31.      }
    32. }
    33. }
    34.

    Python版：

    1. class Solution:
    2.     def letterCombinations(self, digits: str) -> List[str]:
    3.         list = []
    4.         d = {}
    5.         if len(digits) == 0:
    6.             return list
    7.         d['2'] = "abc"
    8.         d['3'] = "def"
    9.         d['4'] = "ghi"
    10.         d['5'] = "jkl"
    11.         d['6'] = "mno"
    12.         d['7'] = "pqrs"
    13.         d['8'] = "tuv"
    14.         d['9'] = "wxyz"
    15.         self.dfs(list,d,0,"",digits)
    16.         return list 
    17.  
    18.     def dfs(self, list, d, k, s,digits):
    19.         if k == len(digits):
    20.             list.append(s)
    21.         else:
    22.             tmp = d[digits[k]]
    23.             for i in range(len(tmp)):
    24.                 s += tmp[i]
    25.                 self.dfs(list,d,k+1,s,digits)
    26.                 s = s[:k] + s[k+1:]
    3.四数之和

    题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/4sum/description/
    思路：方法1：四层循环

    方法2：排序+双指针+三层循环

    Java版：
    超时版：

    1. class Solution {
    2.     public List> fourSum(int[] nums, int target) {
    3.         List> res = new ArrayList<>() ;
    4.         for(int i=0; i
    5.             for(int j=i+1; j
    6.                 for(int k=j+1; k
    7.                     for(int l=k+1; l
    8.                         if(target == (nums[i] + nums[j] + nums[k] + nums[l])){
    9.                             List tmp = new ArrayList<>() ;
    10.                             tmp.add(nums[i]) ;
    11.                             tmp.add(nums[j]) ;
    12.                             tmp.add(nums[k]) ;
    13.                             tmp.add(nums[l]) ;
    14.                             Collections.sort(tmp) ;
    15.                             if(!res.contains(tmp)){
    16.                                 res.add(tmp) ;
    17.                             }
    18.                         }
    19.                     }
    20.                 }
    21.             }
    22.         }
    23.         return res ;
    24.     }
    25. }

    击败5%的Java用户版：

    1. class Solution {
    2.     public List> fourSum(int[] nums, int target) {
    3.         List> res = new ArrayList<>() ;
    4.         Arrays.sort(nums) ;
    5.  
    6.         for(int i=0; i
    7.             for(int j=i+1; j
    8.                 int left = j+1, right = nums.length - 1 ;
    9.                 while(left < right){
    10.                     // 防止超出整型最大范围
    11.                     long sum =  (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right] ;
    12.                     if(target == sum){
    13.                         List tmp = new ArrayList<>() ;
    14.                         tmp.add(nums[i]) ;
    15.                         tmp.add(nums[j]) ;
    16.                         tmp.add(nums[left]) ;
    17.                         tmp.add(nums[right]) ;
    18.                         Collections.sort(tmp) ;
    19.                         if(!res.contains(tmp)){
    20.                             res.add(tmp) ;
    21.                         }
    22.                         right -- ;
    23.                     }else if(target > sum){
    24.                         left ++ ;
    25.                     }else{
    26.                         right -- ;
    27.                     }
    28.  
    29.                 }
    30.             }
    31.         }
    32.         
    33.         return res ;
    34.     }
    35. }

    击败50%的Java选手：
     

    1. class Solution {
    2.     public List> fourSum(int[] nums, int target) {
    3.         List> res = new ArrayList<>() ;
    4.         Arrays.sort(nums) ;
    5.  
    6.         for(int i=0; i
    7.             // 去重
    8.             if(i>0 && nums[i] == nums[i-1]){
    9.                 continue ;
    10.             }
    11.             for(int j=i+1; j
    12.                 // 去重
    13.                 if(j>i+1 && nums[j] == nums[j-1]){
    14.                     continue ;
    15.                 }
    16.                 int left = j+1, right = nums.length - 1 ;
    17.                 while(left < right){
    18.                     // 防止超出整型最大范围
    19.                     long sum =  (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right] ;
    20.                     if(target == sum){
    21.                         while(left < right && nums[left] == nums[left+1]){
    22.                             left ++ ;
    23.                         }
    24.                         while(left < right && nums[right] == nums[right-1]){
    25.                             right -- ;
    26.                         }
    27.                         List tmp = new ArrayList<>() ;
    28.                         tmp.add(nums[i]) ;
    29.                         tmp.add(nums[j]) ;
    30.                         tmp.add(nums[left]) ;
    31.                         tmp.add(nums[right]) ;
    32.                         res.add(tmp) ;
    33.                         left ++ ;
    34.                         right -- ;
    35.                     }else if(target > sum){
    36.                         left ++ ;
    37.                     }else{
    38.                         right -- ;
    39.                     }
    40.  
    41.                 }
    42.             }
    43.         }
    44.         
    45.         return res ;
    46.     }
    47. }

    Python版：

    1. class Solution:
    2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    3.         res = []
    4.         nums.sort()
    5.         for i in range(0,len(nums)-2):
    6.             if i>0 and nums[i] == nums[i-1]:
    7.                 continue
    8.             for j in range(i+1,len(nums)-1):
    9.                 if j>i+1 and nums[j] == nums[j-1]:
    10.                     continue
    11.                 left = j + 1
    12.                 right = len(nums) - 1
    13.                 while left < right:
    14.                     sum = nums[i] + nums[j] + nums[left] + nums[right]
    15.                     if(sum == target):
    16.                         while(left < right and nums[left] == nums[left+1]):
    17.                             left += 1
    18.                         while(left < right and nums[right] == nums[right-1]):
    19.                             right -= 1
    20.                         res.append([nums[i],nums[j],nums[left],nums[right]])
    21.                         left  += 1
    22.                         right -= 1
    23.                     elif(sum > target):
    24.                         right -= 1
    25.                     else:
    26.                         left += 1
    27.         return res 
    28.

    Js版：

    1. /**
    2.  * @param {number[]} nums
    3.  * @param {number} target
    4.  * @return {number[][]}
    5.  */
    6. var fourSum = function(nums, target) {
    7.     nums.sort(function(a,b){
    8.         return a - b 
    9.     })
    10.     const res = []
    11.     for(let i=0; ilength; i++){
    12.         if(i>0 && nums[i] == nums[i-1]){
    13.             continue 
    14.         }
    15.         for(let j=i+1; jlength; j++){
    16.             if(j>i+1 && nums[j] == nums[j-1]){
    17.                 continue
    18.             }
    19.             let left = j + 1, right = nums.length - 1
    20.             while(left < right){
    21.                 const sum = nums[i] + nums[j] + nums[left] + nums[right] 
    22.                 if(sum === target){
    23.                     while(left < right && nums[left] == nums[left+1]){
    24.                       left ++
    25.                 }
    26.                    while(left < right && nums[right] == nums[right-1]){
    27.                       right -- 
    28.                 }
    29.                     res.push([nums[i],nums[j],nums[left],nums[right]])
    30.                     left ++ 
    31.                     right --
    32.                 }else if(sum > target){
    33.                     right -- 
    34.                 }else{
    35.                     left ++ 
    36.                 }
    37.             }
    38.         }
    39.     }
    40.     return res 
    41. };
    4.删除链表的倒数第 N 个结点

    题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

    思路：先计算链表长度，然后找到相应的结点位置，修改指针即可。

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode removeNthFromEnd(ListNode head, int n) {
    13.         // 找到倒数第n个节点，然后修改指针即可
    14.         ListNode p = head ;
    15.  
    16.         int len = 0 ;
    17.         while(p != null){
    18.             len ++ ;
    19.             p = p.next ;
    20.         }
    21.  
    22.         if(n > len){
    23.             return head ;
    24.         }
    25.         if(len==n){
    26.             head = head.next ;
    27.             return head ;
    28.         }
    29.         ListNode cur = head.next ;
    30.         ListNode pre = head ;
    31.         ListNode res = pre ;
    32.         for(int i=0; i1; i++){
    33.             pre = pre.next ;
    34.             cur = pre.next ;
    35.         }
    36.  
    37.         pre.next = cur.next ;
    38.         return res ;
    39.  
    40.     
    41.     }
    42. }

    5.有效的括号

    题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/valid-parentheses/

    思路：HashMap存储映射关系，栈模拟匹配括号匹配过程。

    1. class Solution {
    2.     public boolean isValid(String s) {
    3.         Map map = new HashMap<>() ;
    4.         map.put('{','}') ;
    5.         map.put('(',')') ;
    6.         map.put('[',']') ;
    7.         LinkedList stack = new LinkedList<>() ;
    8.         for(int i=0; i
    9.             char c = s.charAt(i) ;
    10.             if(c == '{' || c == '(' || c == '['){
    11.                 stack.push(c) ;
    12.             }else{
    13.                 // 没有匹配的左括号，右括号多
    14.                 if(stack.isEmpty()){
    15.                     return false ;
    16.                 }
    17.                 char top = stack.pop() ;
    18.                 if(s.charAt(i) != map.get(top)){
    19.                     return false ;
    20.                 }
    21.             }
    22.         }
    23.         // 栈不空，说明左括号多，没匹配
    24.         if(stack.isEmpty() == false){
    25.             return false ;
    26.         }
    27.         return true ;
    28.     }
    29. }
  • 相关阅读:
    论文笔记：A survey of deep nonnegative matrix factorization
    72道Java线程面试题，一题一答案，不搞花里胡哨
    构建AR视频空间大数据平台（物联网及工业互联网、视频、AI场景识别）
    软件测试人在深圳有哪些值得去的互联网公司【软件测试人员专供版】
    事务，不只ACID
    保卫你的应用：探索过滤器和拦截器的奥秘
    Zip Slip漏洞审计实战
    Servlet —— Tomcat, 初学 Servlet 程序
    【LeetCode-二叉树训练】
    Arcgis如何制作专题地图中漂亮的饼图
  • 原文地址：https://blog.csdn.net/nuist_NJUPT/article/details/136398883