SkillAgentSearch skills...

CodingSolution

The coding solutions of Leetcode and 剑指Offer using Python and Java.

GenerateConvertImprove

Install / Use

/learn @krahets/CodingSolution
About this skill

Quality Score

0/100

Supported Platforms

Universal

README

CodingSolution

This repository includes coding solutions of Leetcode and 剑指offer using Python and Java.

如果您喜欢我的题解请SATR~ (>_<) 欢迎留言，我会认真尽快回复。

LeetCode

The solutions of leetcode are updated daily, while using Python and Java.

1.two-sum

标签：数组，哈希表Hash

  • 建立HashMap，遍历数组nums，key存储nums[i]，value存储i；
  • 遍历过程中，判断HashMap里是否有target - nums[i]的key值，若有直接返回两个数字index。
class Solution:
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
            if str(target - nums[i]) in dic:
                return [dic[str(target - nums[i])], i]
            dic[str(nums[i])] = i

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

2. Add Two Numbers

标签：链表

  • 模拟整个做加法的过程，carry记录进位，需要注意两点：
    • 由于两链表长度可能不同，因此在做加法时，要将超出短链表的值填0再计算；
    • 当l1，l2都遍历完后，还需要判断是否有进位，如果有需要再添一位1。
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        head = ListNode(0)
        res = head
        while l1 or l2:
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0
            tmp = num1 + num2 + carry
            carry = 1 if tmp >= 10 else 0
            head.next = ListNode(tmp % 10)
            head = head.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        if carry: head.next = ListNode(1)
        return res.next

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        int carry = 0;
        while(l1 != null || l2!= null){
            int num1 = l1 != null ? l1.val : 0;
            int num2 = l2 != null ? l2.val : 0;
            int tmp = num1 + num2 + carry;
            carry = tmp / 10;
            head.next = new ListNode(tmp % 10);
            head = head.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        if(carry == 1) head.next = new ListNode(1);
        return res.next;
    }
}

3. Longest Substring Without Repeating Characters

标签：双指针，哈希表Hash，字符串

  • 设定左右双指针l和r，遍历字符串；
  • 哈希表存储某字符s[i]最新在字符串中出现的位置index + 1，key, value对应s[i], i；
  • 左指针在遍历过程中：
    • 若s[i]不在HashMap中，则跳过；
    • 否则，l指针设定为l和dic[s[r]]的最大值，即修改之后，保证新字符串中没有重复字符。
    • 每次更新长度最大值res。
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        l, res = 0, 0
        for r in range(len(s)):
            if s[r] in dic:
                l = max(dic[s[r]], l)
            dic[s[r]] = r + 1
            res = max(res, r - l + 1)
        return res

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            map.put(s.charAt(j), j + 1);
            res = Math.max(res, j - i + 1);
        }
        return res;
    }
}

5. Longest Palindromic Substring

标签：字符串，双指针

  • 遍历s，以每个char以及两个char中点为中心，计算以此点为中心的最长回文串；
    • 例如： 字符串abcba 共有5（字母） + 4（两字母间） = 9个中心点；
    • 因此，长度为N的string共有2N-1个中心。
  • 我们的目标就是统计以这2N-1个点为中心的最长回文串s1,s2,..,s2N-1，并从中挑出全局最长回文串。
  • 保留最大长度回文串index，记为left和right；
  • 完成遍历后返回以left和right为边界的substring。
class Solution:
    def longestPalindrome(self, s: str) -> str:
        left, right = 0, 0
        for i in range(len(s)):
            odd = self.mid_expand(s, i, i)
            even = self.mid_expand(s, i, i+1)
            m = max(odd, even)
            if m > right - left:
                left = i - (m - 1) // 2
                right = i + m // 2
        return s[left:right+1]

    def mid_expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 0) return "";
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = midExpand(s, i, i);
            int even = midExpand(s, i, i + 1);
            int m = Math.max(odd, even);
            if (m > right - left) {
                left = i - (m - 1) / 2;
                right = i + m / 2;
            }
        }
        return s.substring(left, right + 1);
    }

    private int midExpand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

7. Reverse Integer

标签：位运算

  • 思路为对当前数取对10的余数，再一项项填入res尾部，即可完成int翻转。
  • 难点在于如何处理边界情况，int取值范围为[-2^31, 2^31 - 1]，如果翻转数字溢出，则立即return 0。
    • python存储数字理论上是无限长度，因此每次计算完后判断res与of的大小即可；
    • java数字计算会溢出，因此要判断res和of / 10的大小关系（即确定再添一位一定会溢出）。
  • python负数取余操作与java不同，由于python的//操作是向下取整，导致正负数取余操作结果不一致，因此python需要将原数字转为正数操作。
class Solution:
    def reverse(self, x: int) -> int:
        y, res = abs(x), 0
        of = (1 << 31) - 1 if x > 0 else 1 << 31
        while y != 0:
            res = res * 10 + y % 10
            if res > of: return 0
            y //= 10
        return res if x > 0 else -res

class Solution {
    public int reverse(int x) {
        int res = 0;
        int of = ((1 << 31) - 1) / 10;
        while (x != 0) {
            if (Math.abs(res) > ((1 << 31) - 1) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

8. String to Integer (atoi)

标签：字符串

  1. 过滤空格；
  2. 判断是否为正负号并存储；
  3. 得到int数字；
  4. 处理溢出；
  5. 根据正负号返回。
class Solution:
    def myAtoi(self, s: str) -> int:
        i, res, neg, over = 0, 0, False, (1 << 31) - 1
        while i < len(s) and s[i] == ' ': # ignore space first
            i += 1
        if i < len(s) and (s[i] == '-' or s[i] == '+'): # save '-'
            neg = s[i] == '-'
            i += 1
        while i < len(s) and '0' <= s[i] <= '9': # generate number
            res = res * 10 + int(s[i])
            i += 1
        if res > over: # handle the overflow
            res = over + 1 if neg else over
        return -res if neg else res

9. Palindrome Number

标签：运算机制

  • 首先，考虑双指针法，但int类型无法遍历每一位，转化为str需要额外空间，不符合题意；
  • 其次，考虑数字反转，若反转后数字和原数字一样则为回文；
  • 本解采用半倒置，即只取数字后一半并反转：
    • 由于return的判断机制，x % 10 == 0要直接返回false；
    • x < 0直接返回false。
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or not x % 10 and x: return False
        r = 0
        while x > r:
            x, rem = x // 10, x % 10
            r = r * 10 + rem
        return x == r or x == r // 10

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0 || x % 10 == 0 && x != 0) return false;
        int y = 0;
        while(x > y){
            y = y * 10 + x % 10;
            x = x / 10;
        }
        return x == y || x == y / 10;
    }
}

11. Container With Most Water （LeetCode精选）

标签：双指针

思路：

  • 算法流程： 设置双指针 $i$,$j$ 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 res，直到 i == j 时返回 res。

  • 指针移动规则与证明： 每次选定围成水槽两板高度 $h[i]$,$h[j]$ 中的短板，向中间收窄 $1$ 格。以下证明：

    • 设每一状态下水槽面积为 $S(i, j)$,$(0 <= i < j < n)$，由于水槽的实际高度由两板中的短板决定，则可得面积公式 $S(i, j) = min(h[i], h[j]) × (j - i)$。
    • 在每一个状态下，无论长板或短板收窄 $1$ 格，都会导致水槽 底边宽度 $-1$：
      • 若向内移动短板，水槽的短板 $min(h[i], h[j])$ 可能变大，因此水槽面积 $S(i, j)$ 可能增大。
      • 若向内移动长板，水槽的短板 $min(h[i], h[j])$ 不变或变小，下个水槽的面积一定小于当前水槽面积。
    • 因此，向内收窄短板可以获取面积最大值。换个角度理解：
      • 若不指定移动规则，所有移动出现的 $S(i, j)$ 的状态数为 $C(n, 2)$，即暴力枚举出所有状态。
      • 在状态 $S(i, j)$ 下向内移动短板至 $S(i + 1, j)$（假设 $h[i] < h[j]$ ），则相当于消去了 ${S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)}$ 状态集合。而所有消去状态的面积一定 $<= S(i, j)$：
        • 短板高度：相比 $S(i, j)$ 相同或更短（$<= h[i]$）；
        • 底边宽度：相比 $S(i, j)$ 更短。
      • 因此所有消去的状态的面积都 $< S(i, j)$。通俗的讲，我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。

  • 复杂度分析：

    • 时间复杂度 $O(N)$，双指针遍历一次底边宽度 $N$ 。
    • 空间复杂度 $O(1)$，指针使用常数额外空间。

<Picture1.png,Picture2.png,Picture3.png,Picture4.png,Picture5.png,Picture6.png,Picture7.png,Picture8.png>

代码：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

class Solution {
    public int

krahets

View profile

View on GitHub
GitHub Stars70
CategoryDevelopment
Updated2mo ago
Forks9
krahets/CodingSolution

Languages

Python

Security Score

95/100

Audited on Jan 3, 2026

No findings