깜짝 이 야!모 985 대학교 의 사람 leetcode 는 할 수 없 었 고 남 묵 녀 는 눈물 을 흘 렸 다.

LEETCODE DAY1
오늘 문 제 를 연 습 했 습 니 다. 문 제 는 어렵 지 않 지만 많은 사람들 이 쓸 수 없습니다. 큰 사람 이 몇 줄 을 다 썼 고 저도 쓸 수 없 기 때문에 블 로 그 를 쓸 필요 가 있 습 니 다.
제목: 1371. 모음 마다 짝수 의 최 장자 문자열 이 포함 되 어 있 습 니 다.
이것 은 제 가 처음으로 leetcode 를 쓴 것 입 니 다. 저 는 잘 모 르 겠 습 니 다. 다만 일부 변 수 는 클래스 밖 에 두 었 고 계속 컴 파일 했 지만 힘 들 었 습 니 다.나중에 나 는 이 문 제 를 발 견 했 지만 지나 갈 수 없 었 다. 그 이 유 는 시간 을 초 과 했 기 때문이다. ojs 는 하늘 을 돌파 할 정도 로 길 고 긴 문 자 를 주 었 다. 그리고 나의 불쌍 한 O (n ^ 2) 알고리즘 은 은하계 에서 느 려 졌 다.

times = {
    'a': 1,
    'e': 1,
    'i': 1,
    'o': 1,
    'u': 1
};

yuanyin = "aeiou"
class Solution(object):
    def findTheLongestSubstring(self, s):
        lenth = len(s)
        li = []
        for i in range(lenth):
            li.append([])
        for j in range(lenth):
            if s[j] in yuanyin:
                times[s[j]] *= -1
            for value in times.values():
                li[j].append(value)
        maxN = 0
        N = 0
        li.insert(0, [1, 1, 1, 1, 1])
        le = len(li)
        for k in range(le):
            for l in range(le):
                if li[k] == li[l]:
                    N = l - k
                if N > maxN:
                    maxN = N
            return maxN

s = input('S: ')
Word = Solution()
num = Word.findTheLongestSubstring(s)
print(num)

문자열 의 모든 위치의 모음 패 리 티 는 32 가지 밖 에 없 을 수 있 기 때문에 친구 가 나 에 게 시 계 를 하나 써 서 하 쉬 를 빨리 할 수 있다 고 알려 주 었 다.제 가 했 어 요.

class Solution(object):
	def findTheLongestSubstring(self, s):
		yuanyin = "aeiou"
		biao = {
			(1, 1, 1, 1, 1) :[-1, -1],
			(-1, 1, 1, 1, 1) :[-1, -1],
			(1, -1, 1, 1, 1) :[-1, -1],
			(-1, -1, 1, 1, 1) :[-1, -1],
			(1, 1, -1, 1, 1) :[-1, -1],
			(-1, 1, -1, 1, 1) :[-1, -1],
			(1, -1, -1, 1, 1) :[-1, -1],
			(-1, -1, -1, 1, 1) :[-1, -1],
			(1, 1, 1, -1, 1) :[-1, -1],
			(-1, 1, 1, -1, 1) :[-1, -1],
			(1, -1, 1, -1, 1) :[-1, -1],
			(-1, -1, 1, -1, 1) :[-1, -1],
			(1, 1, -1, -1, 1) :[-1, -1],
			(-1, 1, -1, -1, 1) :[-1, -1],
			(1, -1, -1, -1, 1) :[-1, -1],
			(-1, -1, -1, -1, 1) :[-1, -1],
			(1, 1, 1, 1, -1) :[-1, -1],
			(-1, 1, 1, 1, -1) :[-1, -1],
			(1, -1, 1, 1, -1) :[-1, -1],
			(-1, -1, 1, 1, -1) :[-1, -1],
			(1, 1, -1, 1, -1) :[-1, -1],
			(-1, 1, -1, 1, -1) :[-1, -1],
			(1, -1, -1, 1, -1) :[-1, -1],
			(-1, -1, -1, 1, -1) :[-1, -1],
			(1, 1, 1, -1, -1) :[-1, -1],
			(-1, 1, 1, -1, -1) :[-1, -1],
			(1, -1, 1, -1, -1) :[-1, -1],
			(-1, -1, 1, -1, -1) :[-1, -1],
			(1, 1, -1, -1, -1) :[-1, -1],
			(-1, 1, -1, -1, -1) :[-1, -1],
			(1, -1, -1, -1, -1) :[-1, -1],
			(-1, -1, -1, -1, -1) :[-1, -1]
		}
		times = {
		    'a': 1,
		    'e': 1,
		    'i': 1,
		    'o': 1,
		    'u': 1
		}
		lenth = len(s)
		for j in range(lenth):
			li = []
			if s[j] in yuanyin:
				times[s[j]] *= -1
			for value in times.values():
				li.append(value)
			li = tuple(li)
			if biao[li][0] == -1 and li != (1, 1, 1, 1, 1):
				biao[li][0] = j
			else:
				biao[li][1] = j
		maxN = 0
		N = 0
		for value in biao.values():
			N = value[1] - value[0]
			if N > maxN:
				maxN = N
		return maxN

s = input('S: ')
Word = Solution()
num = Word.findTheLongestSubstring(s)
print(num)
      

그 중에서 가장 큰 문제 라 고 생각 합 니 다. 하 나 는 key (1, 1, 1, 1, 1) 를 처리 하 는 것 입 니 다. 이 상황 은 스 캔 테이프 가 이 문자열 로 이동 할 때 이 문자 와 이 문자 앞 에 있 는 a, e, i, o, u 의 패 리 티, 1 대표 패 리 티, - 1 대표 기 를 포함 합 니 다.그래서 우 리 는 (1, 1, 1, 1, 1) 의 value [0] = - 1 을 유지 해 야 한다. - 1 은 스 캔 테이프 가 0 번 째 문 자 를 스 캔 하지 않 았 을 때 (이해 하지 못 하면 스스로 예 를 들 어 생각해 볼 수 있다).
다 쓴 후에 제출 했 습 니 다. 지 났 습 니 다.
공식 적 인 답 을 보 자. 생각 은 비슷 하지만 코드 의 간결 정 도 는 크게 다르다.상태 압축 으로 11111 - > 31...

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ans = 0, status = 0, n = s.length();
        vector<int> pos(1 << 5, -1);
        pos[0] = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'a') {
                status ^= 1<<0;
            } else if (s[i] == 'e') {
                status ^= 1<<1;
            } else if (s[i] == 'i') {
                status ^= 1<<2;
            } else if (s[i] == 'o') {
                status ^= 1<<3;
            } else if (s[i] == 'u') {
                status ^= 1<<4;
            }
            if (~pos[status]) {
                ans = max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        return ans;
    }
};

코드 를 보기 시 작 했 을 때 알 아 볼 수 없고 비트 연산 을 잘 배우 지 못 했 습 니 다. 많은 세부 사항 이 명확 하지 않 습 니 다 & (또한), | (또는), ^ (이상 또는), ~ (반대), 그 중에서 가장 현혹 되 는 것 은 ~ pos [status] 입 니 다. 마지막 으로 추 리 를 통 해 1 위 를 얻 었 습 니 다.양수 의 화 1 위 는 0 이 고, 반 을 취하 면 1 이다.
모 대 lao

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        D = {"a": 1, "e": 2, "i": 4, "o": 8, "u": 16}
        L = {0: 0}
        m = t = 0
        for i, c in enumerate(s, 1): # i   1  
            t ^= D.get(c, 0) #     0
            m = max(m, i - L.setdefault(t, i))
        return m

for      enumerate
>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three

setdefault () 방법 은 한 줄 에서 이 일 을 완성 하 는 방식 을 제공 합 니 다.이 방법 에 전 달 된 첫 번 째 매개 변 수 는 검사 할 키 입 니 다.두 번 째 매개 변 수 는 이 키 가 존재 하지 않 을 때 설정 할 값 입 니 다.이 키 가 확실히 존재 한다 면 방법 은 키 의 값 을 되 돌려 줍 니 다.