专栏首页用户2133719的专栏LeetCode 刷题记录 1-5

LeetCode 刷题记录 1-5

1. Two Sum

题目

给定一个整数数组 nums 和一个目标值 target ,找出数组中和为目标值的两个数,并返回它们的数组下标。

假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

代码

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 complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Python 解法

class Solution(object):
    def twoSum(self, nums, target):
        buff_dict = {}
        for i,num in enumerate(nums):
            complement = target - num
            if complement in buff_dict: # 判断键是否存在于字典中
                return [buff_dict[complement], i]
            buff_dict[nums[i]] = i

2. Add Two Numbers

题目

给定两个「非空」的链表,用来表示两个非负的整数。其中,低位在前,高位在后,并且每个节点只能存储「一位」数字。

将这两个数相加,返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

从链表头部开始,一位位相加即可,注意进位。

注意:我们使用「哑结点」来简化代码(防止需要额外判断表头是否为空)

伪代码如下:

  • 将当前结点初始化为返回列表的哑结点(即一个非空结点)
  • 将进位 carry 初始化为 0
  • pq 分别初始化为列表 l1l2 的头部
    • 直接使用 l1l2 也可以,但会使其指向位置发生改变
  • 遍历列表 l1l2 直至到达它们的尾端:
    • 然后将当前结点前进到下一个结点
    • x 设为结点 p 的值。如果 p 已经到达 l1 的末尾,则将其值设置为 0
    • y 设为结点 q 的值。如果 q 已经到达 12 的末尾,则将其值设置为 0
    • 设定 sum = x + y + carry
    • 更新进位的值 carry = sum / 10
    • 创建一个数值为 sum mod 10 的新结点,并将其设置为当前结点的下一个结点
    • 同时,将 pq 前进到下一个结点
  • 检查 carry = 1 是否成立,如果成立,则向返回列表追加一个含有数字 1 的新结点
  • 返回哑结点的下一个结点

代码

Java 解法
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null){
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}
Python 解法
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        curr = dummy
        p = l1
        q = l2
        carry = 0
        while (p or q):
            x = p.val if p else 0
            y = q.val if q else 0
            sum = x + y + carry
            carry = sum // 10
            curr.next = ListNode(sum % 10)
            curr = curr.next
            if p: 
                p = p.next
            if q: 
                q = q.next
        if (carry > 0):
            curr.next = ListNode(carry)
        return dummy.next

3. Longest Substring Without Repeating Characters

题目

给定一个字符串,找出其中不含有重复字符的「最长子串」的长度。

示例:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

代码

Java 解法

class Solution {
    public int lengthOfLongestSubstring03(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                //左边界移动到相同字符的下一个位置和i当前位置中更靠右的位置(防止i向左移动)
                i = Math.max(map.get(s.charAt(j)), i);
            }
            //比对当前无重复字段长度和储存的长度,选最大值并替换
            //j-i+1是因为此时i,j索引仍处于不重复的位置,j还没有向后移动,取的[i,j]长度
            ans = Math.max(ans, j - i + 1);
            // 将当前字符作为key,下一个索引作为value放入map中(注意value会发生更新)
            // value为j+1是为了当出现重复字符时,i直接跳到上个相同字符的下一个位置
            map.put(s.charAt(j), j+1);
        }
        return ans;
    }
}

Python 解法

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        used = {}
        max_length = start = 0
        for i,c in enumerate(s):
            if c in used:
                start = max(used[c], start)
            max_length = max(max_length, i - start + 1)
            used[c] = i + 1
        return max_length

4. Median of Two Sorted Arrays

题目

给定两个大小为 m 和 n 的有序数组 nums1nums2

你可以假设 nums1nums2 不会同时为空。

示例:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

思路

看到对数复杂度与有序数组,可以判断需要采用「二分法」求解。

在统计中,中位数的作用是:

❝将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。 ❞

基于上述思想,我们可以考虑对数组进行切分。

如下图所示,一个长度为 m 的数组,有 0 到 m 总共有 m + 1 个位置可以切。

对于本道题,我们把有序数组 A 和数组 B 分别在 i 和 j 进行切割:

将 i 的左边和 j 的左边组合成「左半部分」,将 i 的右边和 j 的右边组合成「右半部分」,如上图所示。

接下来我们根据两数组长度之和的「奇偶性」分开讨论:

「情况 1」:如果 A 数组和 B 数组的总长度是「偶数」,则中位数的选择条件为:

❝左半部分的长度等于右半部分,且左半部分最大的值小于等于右半部分最小的值。 ❞

「情况 2」:如果 A 数组和 B 数组的总长度是「奇数」,则中位数的选择条件为:

❝左半部分的长度比右半部分大 1,且左半部分最大的值小于等于右半部分最小的值。 ❞

代码

Java 解法

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { 
            return findMedianSortedArrays(B,A); // 保证 m <= n
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (i != m && B[j-1] > A[i]){ // i 需要增大
                iMin = i + 1; 
            }
            else if (i != 0 && A[i-1] > B[j]) { // i 需要减小
                iMax = i - 1; 
            }
            else { // 达到要求,并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }
}

Python 解法

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if (m > n):
            return self.findMedianSortedArrays(nums2,nums1)
        i_min, i_max = 0, m # 注意与java赋值的格式区别
        while i_min <= i_max:
            i = (i_min + i_max) / 2 # python3下需设置为取整
            j = (m + n + 1)/2 - i
            if (i != m and nums2[j-1] > nums1[i]):
                i_min = i + 1
            elif (i != 0 and nums1[i-1] > nums2[j]):
                i_max = i - 1
            else:
                max_left = 0
                if (i == 0):
                    max_left = nums2[j-1]
                elif (j == 0):
                    max_left = nums1[i-1]
                else:
                    max_left = max(nums1[i-1],nums1[j-1])
                if ((m + n) % 2 == 1):
                    return max_left
                
                min_right = 0
                if (i == m):
                    min_right = nums2[j]
                elif (j == n):
                    min_right = nums1[i]
                else:
                    min_right = min(nums2[j],nums1[i])
                return (max_left + min_right) / 2.0 # python3下可设置为2
        return 0

5. Longest Palindromic Substring

题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

思路

中心扩展算法

我们可以观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,关于中心对称。需要注意偶数回文串与奇数回文串的中心不同:

在实现时我们可以利用运算取整性质将奇偶情况合并,需要注意起始位置的计算公式。

动态规划算法

动态规划算法的本质即将复杂的问题拆分为小问题,以空间换取时间,通过状态转移方程将结果传递下去。我们可以将动态规划算法理解为「填表格」(与递归有所区别),将表格中需要的部分填满就得到了最终的结果。

对于本题而言,状态转移方程可以由回文的性质得出:

❝一个回文去掉两头后,剩下的部分仍然是回文。(不考虑边界情况) ❞

在两头字符相等的情况下,一个字符串是否为回文取决于其子串是否为回文。因此我们将「状态」定义为「一个字符串的子串是否为回文」。基于以上思路,动态规划算法的关键步骤如下:

「1. 定义状态」。dp[i][j] 表示字符串 s[i,j] 是否为回文。

「2. 确定状态转移方程」。此时需要考虑边界情况:

对于「一般情况」,状态方程如下所示:

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

需要注意 ij 的关系是 i <= j,因此实际上只需要填表的上半部分。

对于「边界情况」,即 [i+1, j-1] 不构成区间,即 j-1-(i+1)+1 < 2,整理得 j - i < 3,此时 s[i, j] 一定是回文。

因此,在 s[i] == s[j]j - i < 3 的前提下,可以直接得出 dp[i][j] = true,否则执行状态转移。

「3. 初始化」。单个字符一定是回文子串,因此将表格的对角线初始化为 true,即 dp[i][i] = 1。实际上编码过程中单个字符作为输出的默认值,在动态规划中并不会利用到表格中的对应内容,只会考虑 i < j 的情况。

「4. 考虑输出」。只要一得到 dp[i][j] = true,就记录该字符串的长度和起始位置,在输出时截取即可。

动态规划算法的时间和空间复杂度均为 。

Manacher 算法

Manacher 算法专门用于解决最长回文子串问题,其本质是一种中心扩散法,并利用了”以空间换取时间“的思想。其具体流程如下:

第一步:预处理字符串

首先我们需要在原字符串的首尾和相邻字符中插入「分隔符」,该分隔符需要选择未在原始字符串中出现过的字符。例如对于 babad ,添加分隔符 # ,得到新字符串 #b#a#b#a#d#

新的字符串具有如下性质:

  1. 新字符串中的任意一个回文子串在原始字符串中均有唯一回文子串与之对应
  2. 新字符串的回文子串一定以分隔符作为两边的边界
  3. 新字符串的回文子串的长度一定是奇数(如下图所示)
第二步:计算辅助数组 p

辅助数组 p 记录了新字符串中以每个字符为中心,向左右两边同时扩散能够达到的「最大步数」。

以字符串 abbabb 为例,其辅助数组 p 如下表所示:

辅助数组 p 具有如下性质:

❝辅助数组 p 的最大值即为原字符串「最长回文子串」的长度。 ❞

关于上述性质,可以分两种情况进行证明:

  1. 原字符串最长回文子串的中心为字符:
  1. 原字符串最长回文子串的中心为空隙:
第三步:减少中心扩散的次数

基于 imaxRight 的大小关系,我们需要进行分类讨论:

「情况 1」:如果 i >= maxRight ,我们只能够进行原始的中心扩散,逐渐扩大 maxRight

「情况 2」:如果 i < maxRight,我们可以对中心扩散进行优化,为 p[i] 设置初始值,减少一定的扩散次数。

首先我们需要定义循环变量 i 关于 center 对称的索引 mirror,其计算公式为 mirror = 2 * center - i

根据 p[mirror] 的数值从小到大,可以分以下三种情况讨论:

  1. p[mirror] < maxRight - i,此时根据以 center 为中心的回文子串的对称性,可以直接得出结论 p[i] = p[mirror]
  1. p[mirror] == maxRight - i,此时根据对称性,p[i] 至少为 maxRight - i,需要继续扩散;
  1. p[mirror] > maxRight - i,此时 p[i] = maxRight - i,无需扩散;

关于以上三种情况,其示意图中前两张图的回文子串并没有完全对称,只要理解意思即可;关于第三种情况,可以利用回文子串的对称性,通过下图证明「红色箭头」对应的 ce 必不相等:

综上所述,当 i < maxRight 时,可以为 p[i] 设定起始值,减少扩散次数:

p[i] = min(maxRight - i, p[mirror]);

代码

Java 解法

中心扩展算法
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i); // 奇数回文子串
            int len2 = expandAroundCenter(s, i, i+1); // 偶数回文子串
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2; // 上述两个公式利用运算取整的性质将奇偶情况合并
            }
        }
        return s.substring(start, end + 1); // 取子串不包括结束索引
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1; //实际上公式为 R - L + 1 - 2,因为循环结束时两边各多了一个元素
    }
}
动态规划算法
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        boolean dp[][] = new boolean[n][n]; //默认false
        int start = 0;
        int maxLen = 1;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i ++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && ((j - i < 3) || dp[i + 1][j - 1]);
                if (dp[i][j]) {
                    if ((j - i + 1) > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
        }    
        return s.substring (start, start + maxLen);
    }
}
Manacher 算法
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        String str = addBoundaries(s, '#');
        int sLen = 2 * len + 1;
        int[] p = new int[sLen];
        int maxRight = 0;
        int center = 0;
        int maxLen = 1;
        int start = 0;
        for (int i = 0; i < sLen; i++) {
            int mirror = 2 * center - i;
            if (i < maxRight) {
                p[i] = Math.min(maxRight - i, p[mirror]); // 关键代码
            }
            // 执行中心扩散
            int left = i - (1 + p[i]);
            int right = i + (1 + p[i]);
            while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
                p[i]++;
                left--;
                right++;
            }
            // 更新辅助变量
            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                center = i;
            }
            // 记录最长回文子串
            if (p[i] > maxLen) {
                maxLen = p[i];
                start = (i - maxLen) / 2; // 原始字符串中的位置为除以2向下取整
            }
        }
        return s.substring (start, start + maxLen);

    }

    private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("分隔符已存在于字符串中!");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }
}

Python 解法

中心扩展算法
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """  
        if (s is None or len(s) < 1):
            return ""
        start, end = 0, 0
        for i in range(len(s)):
            len1 = self.expandAroundCenter(s,i,i)
            len2 = self.expandAroundCenter(s,i,i+1)
            leno = max(len1, len2)
            if (leno > end - start + 1):
                start = i - (leno - 1) / 2 # 注意这是 python2,会自动取整
                end = i + leno / 2
        return s[start:end + 1]
    
    def expandAroundCenter(self, s, left, right):
        L = left
        R = right
        while (L >= 0 and R < len(s) and s[L] == s[R]):
            L -= 1
            R += 1
        return R - L - 1
动态规划算法
class Solution:
    def longestPalindrome(self, s: str) -> str: #python3
        n = len(s)
        if n < 2: #括号可以省略
            return s
        dp = [[False for _ in range(n)] for _ in range(n)]
        maxLen = 1
        start = 0
        for j in range(1, n):
            for i in range(0, j):
                dp[i][j] = (s[i] == s[j]) and ((j - i < 3) or dp[i + 1][j - 1])
                if (dp[i][j]):
                    if (j - i + 1) > maxLen:
                        maxLen = j - i + 1
                        start = i
        return s[start:start + maxLen]
Manacher 算法
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        t = "#"
        for i in range(n):
            t += s[i]
            t += "#"
        t_len = 2 * n + 1
        p = [0 for _ in range(t_len)]
        max_right = 0
        center = 0
        max_len = 1
        start = 0
        for i in range(t_len):
            if i < max_right:
                mirror = 2 * center - i
                p[i] = min(max_right - i, p[mirror])
            left = i - (1 + p[i])
            right = i + (1 + p[i])
            while left >= 0 and right < t_len and t[left] == t[right]:
                p[i] += 1
                left -= 1
                right += 1
            if i + p[i] > max_right:
                max_right = i + p[i]
                center = i
            if p[i] > max_len:
                max_len = p[i]
                start = (i - max_len) // 2
        return s[start:start + max_len]

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指 offer》刷题记录之:动态规划与贪婪算法

    动态规划是编程面试中的热门话题。一般来说,能够用动态规划求解的问题具有如下三个特点:

    口仆
  • 《剑指 offer》刷题记录之:回溯法

    回溯法可以看成蛮力法的升级版,它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合由「多个步骤」组成的问题,并且每个步骤都有多个选项...

    口仆
  • LeetCode 刷题记录(三)

    这道题是「回溯法」的经典应用。基本的思路是:从第一行开始,每行按列循环放置皇后,如果找到一个符合规则的位置,则到下一行,以此类推,如果可以一直进行到最后一行,则...

    口仆
  • CodeForces 198B Jumping on Walls(bfs || dfs)

           这道题纠结了快两天,刚开始因为地图的坐标纠结了好久,题意在下面代码中有,下面就说一下思路,我刚开始用bfs做的,卡在了不知道怎么比较当前位置和水位...

    Ch_Zaqdt
  • C++辗转相除法简便写法

    #include <iostream> using namespace std; int gcb(int a,int b) { if(b==0) re...

    kalifa_lau
  • 《敏捷软件开发:原则、模式与实践》笔记(2)

    https://www.twblogs.net/a/5b957acb2b717750bda47bd5/zh-cn/

    sickworm
  • LintCode斐波纳契数列题目:分析小结

    查找斐波纳契数列中第 N 个数。 所谓的斐波纳契数列是指: 前2个数是 0 和 1 。 第 i 个数是第 i-1 个数和第i-2 个数的和。

    desperate633
  • Int32 最大的数值是多少???(附十进制十六进制相互转换且包含正负数的java代码)

    正数转二进制很简单,转十六进制也很简单。 那么负数的情况下呢?在计算机中无法识别你给的符号“+”,"-",计算机只认识0和1 那么在二进制中如何表示负数。 先简...

    ShenduCC
  • Climbing Stairs

    问题:上楼每次能走一步或两步,有多少种走法 class Solution { public: int a[1000]; int dfs(int ...

    用户1624346
  • 2017.10.1解题报告

    ---- 预计分数:60+50+0=110 实际分数:60+81+0=144 全场rank13?全校rank1?貌似题很难啊23333 ---- T1...

    attack

扫码关注云+社区

领取腾讯云代金券