Java解码LeetCode经典50题面试指南

需积分: 9 83 浏览量更新于2024-07-19 3 收藏 1.67MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

private static final int maxDiv10 = Integer.MAX_VALUE / 10;

public int atoi(String str) {

int i = 0, n = str.length();

while (i < n && Character.isWhitespace(str.charAt(i))) i++;

int sign = 1;

if (i < n && str.charAt(i) == '+') {

i++;

} else if (i < n && str.charAt(i) == '-') {

sign = -1;

i++;

}

int num = 0;

while (i < n && Character.isDigit(str.charAt(i))) {

int digit = Character.getNumericValue(str.charAt(i));

if (num > maxDiv10 || num == maxDiv10 && digit >= 8) {

return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;

}

num = num * 10 + digit;

i++;

}

return sign * num;

}

10. Longest Substring Without Repeating Characters

Code it now: Difficulty: Medium, Frequency: Medium

https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/

Question:

Given a string, find the length of the longest substring without repeating characters. For

example, the longest substring without repeating letters for “abcabcbb” is “abc”, which

the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Solution:

O(n) runtime, O(1) space – Two iterations:

How can we look up if a character exists in a substring instantaneously? The answer is to

use a simple table to store the characters that have appeared. Make sure you communicate

with your interviewer if the string can have characters other than ‘a’–‘z’. (ie, Digits?

Upper case letter? Does it contain ASCII characters only? Or even unicode character

sets?)

The next question is to ask yourself what happens when you found a repeated character?

For example, if the string is “abcdcedf”, what happens when you reach the second

appearance of ‘c’?

When you have found a repeated character (let’s say at index j), it means that the current

substring (excluding the repeated character of course) is a potential maximum, so update

the maximum if necessary. It also means that the repeated character must have appeared

before at an index i, where i is less than j.

Since you know that all substrings that start before or at index i would be less than your

current maximum, you can safely start to look for the next substring with head which

starts exactly at index i + 1.

Therefore, you would need two indices to record the head and the tail of the current

substring. Since i and j both traverse at most n steps, the worst case would be 2n steps,

which the runtime complexity must be O(n).

Note that the space complexity is constant O(1), even though we are allocating an array.

This is because no matter how long the string is, the size of the array stays the same at

256.

剩余99页未读，继续阅读

ConjurerKong

粉丝: 0
资源: 2

Java解码LeetCode经典50题面试指南

leetcode中文版-LeetCode:LeetcodeC++/Java

LeetCode上的剑指offerJAVA题解.pdf

算法刷题LeetCode

leetcode java pdf

leetcodejava刷题

leetcode刷题 java

leetcode java刷题

leetcodejava69

leetcode题库

leetcode的java代码编译器

leetcode刷题java顺序

leetcode219java

leetcode刷题java 常用函数

a leetcode grinding guide java

java刷leetcode可以吗

java leetcode 及测试用例写法

java写leetcode的通用包

leetcode高频100题java

leetcode滑动窗口java

leetcode 2146 java

最新资源