Leetcode刷题-(1~5)-Java+Python+JavaScript

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

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

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

目录

1.两数之和

2.两数相加

3.无重复字符串的最长子串

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

5.最长回文子串

---

1.两数之和

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

思路：首先想到的是暴力双层循环，时间复杂度过高，可以使用哈希表，空间换时间，降低时间复杂度。利用hash表，时间复杂度O(n),存储当前值与下标，每次判断目标值-当前值是否存在，若存在，则找出。

java版：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>() ;
        for(int i=0; i<nums.length; i++){
            int element = target - nums[i] ;
            if(!map.containsKey(element)){
                map.put(nums[i], i) ;
            }else{
                return new int []{map.get(element), i} ;
            }
        }
        return new int []{} ;
    }
}

python版：
?

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = []
        d = {}
        index = 0
        for element in nums:
            if d.get(target - element) == None:
                d[element] = index 
            else:
                 res.append(d[target - element])
                 res.append(index)
                 return res 
            index += 1 
        return res 
        

JS版：
?

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const obj = {}
    const ans = []
    for(let i=0; i<nums.length; i++){
        let element = target - nums[i]
        if(obj[element] === undefined){
            obj[nums[i]] = i 
        }else{
            ans.push(obj[element])
            ans.push(i)
            return ans 
        }
    }
    return ans 
};

2.两数相加

题目链接：https://leetcode.cn/problems/add-two-numbers/description/https://leetcode.cn/problems/add-two-numbers/description/

思路：遍历链表，求和后，拼接即可，取余保留到当前，取整用于进位。

Java版：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0) ;
        ListNode pre = node ;
        int carry = 0 ;
        while(l1 != null || l2 != null){
            int x = l1 == null ? 0 : l1.val ;
            int y = l2 == null ? 0 : l2.val ;
            
            int sum = x + y  + carry ;
            carry = sum / 10 ;
            sum = sum % 10 ;

            ListNode node1 = new ListNode(sum) ;
            if(l1 != null){
                l1 = l1.next ;
            }
            if(l2 != null){
                l2 = l2.next ;
            }
            node.next = node1 ;
            node = node.next ;

        }
        if(carry != 0){
            node.next = new ListNode(carry) ;
        }
        return pre.next ;
    }
}

Python版：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        node = ListNode(0)
        pre = node 
        carry = 0
        while (l1  or l2):
            x = y = 0
            if l1:
                x = l1.val
            if l2:
                y = l2.val 
            sum = x + y + carry
            # python与java不一样，这里需要用整除才行
            carry = sum // 10
            sum = sum % 10

            if l1 != None:
                l1 = l1.next
            if l2 != None:
                l2 = l2.next
            
            node.next = ListNode(sum)
            node = node.next
        if carry > 0:
            node.next = ListNode(carry)
            node = node.next
        return pre.next


            

JS版：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
     node = new ListNode(0)
     pre = node 
     let carry = 0 
     while(l1 != null || l2 != null){
         const x = l1 == null ? 0 : l1.val 
         const y = l2 == null ? 0 : l2.val 

         let sum = x + y + carry
         // js与python都是弱类型的，需要取整
         carry = Math.floor(sum / 10) 
         sum = sum % 10 
         
         if(l1 != null){
             l1 = l1.next 
         }
         if(l2 != null){
             l2 = l2.next
         }

         node.next = new ListNode(sum)
         node = node.next 
     }
     if(carry > 0){
         node.next = new ListNode(carry)
         node = node.next 
     }
     return pre.next
};

3.无重复字符串的最长子串

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/longest-substring-without-repeating-characters/

思路：可以用队列实现，队列满足先进先出的特性，如果队列中不含有当前元素，则元素入队，如果队列中含有当前元素，则出队直至不含有当前元素，整个过程中队列的最大长度即是答案。

Java版：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        LinkedList<Character> queue = new LinkedList<>() ;
        int max = 0 ;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i) ;
            while(queue.contains(c)){
                queue.poll() ;
            }
            if(!queue.contains(c)){
                queue.add(c) ;
            }
           max = max < queue.size() ? queue.size() : max ;
        }
        return max ;
    }
}

Python版：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max = 0
        i = 0
        list = []
        for s1 in s:
            while self.contains_str(s1, list):
                list.pop(0)
            if not self.contains_str(s1, list):
                list.append(s1)
            if max < len(list):
                max = len(list)
        return max 
    def contains_str(self, s1, list):
        for s2 in list:
            if s1 == s2:
                return True
        return False

Js版：
?

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let max = 0
    const arr = []
    for(let i=0; i<s.length; i++){
    
        while (arr.includes(s[i])){
            arr.shift()
        }
        if(!arr.includes(s[i])){
            arr.push(s[i])
        }
        max = max <  arr.length ? arr.length : max 

    }
    return max 
};

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

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

思路：题目要求时间复杂度是Olog(m+n)，这样的话就不能合并数组后排序了，我们需要找出中位数，但是并不需要合并数组，那么我们要做的就是模拟走(数组1的长度+数组2的长度)/2步即可，每次让两个数组的中小的继续走，若其中一个走完了，则只能走另外一个。最后如果两个数组的长度之和是偶数，则除以2得到中位数，否则直接得到中位数。

Java版：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int start1 = 0, start2 = 0 ;
        int left = -1, right = -1 ;
        int m = nums1.length, n = nums2.length ;
        int len = m + n ;
        for(int i=0; i<=len/2; i++){
            left = right ;
            if(start1 < m && (start2 >= n || nums1[start1] <= nums2[start2])){
                right = nums1[start1 ++] ;
            }else{
                right = nums2[start2 ++] ;
            }
        }
        if(len%2 == 0){
            return (left + right) / 2.0  ;
        }else{
            return right ;
        }

    }
}

Python版：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        left = right = -1
        start1 = start2 = 0
        m = len(nums1)
        n = len(nums2)
        l = m + n

        for i in range(l // 2 + 1):
            left = right 
            # 这里需要注意防止列表下标越界
            if (start1 < m) and (start2 >= n or  nums1[start1] <= nums2[start2]):
                right = nums1[start1]
                start1 += 1
            else:
                right = nums2[start2]
                start2 += 1 
        
        if l%2 == 0:
            return (left + right) / 2
        else:
            return right

Js版：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let left = -1, right = -1
    let start1 = 0, start2 = 0
    const m = nums1.length, n = nums2.length
    const len = m+n 
    for(let i=0; i<=Math.floor(len/2); i++){
        left = right 
        if(start1 < m && (start2 >=n || nums1[start1] <= nums2[start2])){
            right = nums1[start1++] ;
        }else{
            right = nums2[start2++] ;
        }
    }
    if(len % 2 == 0){
        return (left + right) / 2 ;
    }else{
        return right ;
    }
};

5.最长回文子串

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

思路：动态规划，递推式,外层循环很重要，要确保当前所用到的递推式之前推导出了结果。

dp[i][j] = dp[i+1][j-1] s[i] == s[j] && j-i>2

dp[i][j] = true s[i]==s[j] && j-i<=2

dp[i][j] = false? ?s[i] != s[j]

Java版：

class Solution {
    public String longestPalindrome(String s) {
       int n = s.length() ;
       boolean [][] dp = new boolean[n][n] ;
       int max = 0 ;
       String ans = "" ;
       // 动态规划递推式很重要，两层循环，当前所需的表达式要在之前递推出来了才行
       for(int j=0; j<n; j++){
           for(int i=0; i<=j; i++){
               if(s.charAt(i) != s.charAt(j)){
                   dp[i][j] = false ;
               }else{
                   if(j-i<=2){
                       dp[i][j] = true ;
                   }else{
                       dp[i][j] = dp[i+1][j-1] ;
                   }
               }
               if(dp[i][j] && max < j - i + 1){
                    max = j - i + 1 ;
                    ans = s.substring(i,j+1) ; 
               }
           }
       }
       return ans ;
    }
}

Python版：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        row = column = len(s)
        matrix = [[False for _ in range(column)] for _ in range(row)]
        max = 0 
        res = ""
        for j in range(column):
            for i in range(j+1):
                if s[i] == s[j]:
                    if j - i <= 2:
                        matrix[i][j] = True
                    else:
                        matrix[i][j] = matrix[i+1][j-1]
                if matrix[i][j] and j-i+1 >= max:
                    max = j - i + 1
                    res = s[i:j+1]
        return res 

Js版：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let max = 0 
    let ans = ""
    const n = s.length 
    const arr = new Array(n)
    for(let i=0; i<n; i++){
        arr[i] = new Array(n).fill(false) ;
    }
    for(let j=0; j<n; j++){
        for(let i=0; i<=j; i++){
            if(s.charAt(i) == s.charAt(j)){
                if(j-i<=2){
                    arr[i][j] = true
                }else{
                    arr[i][j] = arr[i+1][j-1]
                }
            }
            if(arr[i][j] && max < j - i + 1){
                max = j - i + 1
                ans = s.substring(i,j+1)
            }
        }
    }
    return ans 
};

今天的算法题就到这里喽，我们下次继续，道阻且长，行则降至！