LeetCode: 두 수의 합 + 두 수의 더하기 + 중복 문자 가 없 는 최 장 문자열 + 두 배열 의 중위 + Z 자형 변환 + 정수 반전 + 문자열 변환 정수 찾기 (atoi)
12119 단어 알고리즘
1. 두 수의 합
2. 두 수 를 더 하 다
3. 중복 문자 없 는 최 장 문자열
4. 두 배열 의 중위 수 찾기
5. Z 자형 변환
6. 정수 반전
7. 문자열 변환 정수 (atoi)
1. 두 수의 합
정수 배열 nums 지정 목표 치 target 과 함께 이 배열 에서 목표 치 를 찾 아 보 세 요. 두 개 정수, 그리고 그들의 배열 아래 표 시 를 되 돌려 줍 니 다.너 는 모든 입력 이 하나의 답안 에 만 대응 할 것 이 라 고 가정 할 수 있다.그러나 이 배열 의 같은 요 소 를 반복 적 으로 이용 해 서 는 안 된다.
예시:
주어진 nums = [2, 7, 11, 15], target = 9
nums [0] + nums [1] = 2 + 7 = 9 이기 때문에 [0, 1] 로 돌아 갑 니 다.
사고: 모든 요소 가 target 에 대응 하 는 차 이 를 map 에 저장 합 니 다. 현재 요소 가 map 에 존재 하면 결 과 를 찾 을 수 있 습 니 다.
class Solution {
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for(int i = 0; i < nums.length; ++i){
int num = target - nums[i];
if(map.containsKey(num)){
return new int[] {map.get(num), i};
}
map.put(nums[i], i);
}
return null;
}
} 2. 두 수 를 더 하 다
두 개 드 리 겠 습 니 다. 비 어 있 는 링크 는 두 개의 비 마이너스 정 수 를 나타 내 는 데 쓰 인 다.그 중에서 도 이들 각자 의 자릿수 는 역순 의 방식 으로 저장 되 고 그들의 모든 노드 는 저장 할 수 밖 에 없다. 한 사람 숫자
만약 우리 가 이 두 개의 수 를 더 하면 새로운 링크 로 돌아 가 그들의 합 을 나 타 낼 것 이다.
예시:
입력: (2 - > 4 - > 3) + (5 - > 6 - > 4) 출력: 7 - > 0 - > 8 원인: 342 + 465 = 807
사고: 덧셈 의 절차 에 따라 진입 표 지 를 기록 하고 한 노드 를 낭비 하여 코드 의 가 독성 을 향상 시 키 는 것 도 좋 습 니 다.
추가 후 마지막 진입 도 처리 해 야 합 니 다 (carry Flag! = 0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carryFlag = 0;
ListNode result = new ListNode(0);
ListNode curr = result;
while (l1 != null || l2 != null || carryFlag != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int tmp = x + y + carryFlag;
curr.next = new ListNode(tmp % 10);
curr = curr.next;
carryFlag = tmp / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return result.next;
}
}3. 중복 문자 없 는 최 장 문자열
문자열 을 지정 합 니 다. 중복 문자 가 없 는 문자열 을 찾 아 보 세 요. 최 장자 꼬치 길이
예시 1:
입력: "abcabcbb" 출력: 3 해석: 중복 문자 가 없 는 가장 긴 문자열 은 "abc" 이기 때문에 길 이 는 3 입 니 다.
사고방식: 슬라이딩 창, i 는 창 왼쪽 경계, j 는 창 오른쪽 경계, 문 자 를 하나씩 hashMap 에 넣 습 니 다. 현재 문자 가 맵 에 있 으 면 i 를 현재 문자 아래 표 시 를 + 1 로 업데이트 합 니 다.
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap map = new HashMap();
int res = 0;
for (int i = 0, j = 0; j < s.length(); ++j) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)) + 1, i);
}
res = Math.max(res, j - i + 1);
map.put(s.charAt(j), j);
}
return res;
}
} 4. 두 배열 의 중위 수 찾기
m 와 n 크기 의 질서 있 는 배열 을 지정 합 니 다. nums 1 과 nums2。
이 두 질서 있 는 배열 의 중위 수 를 찾 아 알고리즘 의 시간 복잡 도 를 요구 하 십시오. O(log(m + n))。
너 는 가정 할 수 있다. nums1 화해시키다 nums2 동시에 비어 있 지 는 않 습 니 다.
예시 1: nums 1 = [1, 3], nums 2 = [2], 중위 수 는 2.0 예시 2: nums 1 = [1, 2], nums 2 = [3, 4], 중위 수 는 (2 + 3) / 2 = 2.5
사고: 먼저 정렬 한 다음 에 중위 수 를 취하 고 정렬 은 두 개의 질서 있 는 링크 와 유사 합 니 다 (자신의 초기 생각, 다음은 초기 코드).
그러나 시간 복잡 도 는 O (m + n) 이 고 공간 복잡 도 는 O (m + n) 이다.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// ，
int length1 = nums1.length;
int length2 = nums2.length;
int[] resArr = new int[length1 + length2];
int i = 0;
int j = 0;
int n = 0;
while (i < length1 || j < length2) {
if (i >= length1) {
resArr[n] = nums2[j++];
} else if (j >= length2) {
resArr[n] = nums1[i++];
} else if (nums1[i] > nums2[j]) {
resArr[n] = nums2[j++];
} else {
resArr[n] = nums1[i++];
}
++n;
}
int resLen = resArr.length;
return resLen % 2 == 0 ? (double) (resArr[resLen / 2] + resArr[resLen / 2 - 1]) / 2 : resArr[resLen / 2];
}
}알고리즘 의 시간 복잡 도 는 O (log (min (m + n)) 의 해법
사고: 우선, 중위 수: 하나의 집합 을 두 개의 길이 가 같은 부분 집합 으로 나 누 는데 그 중에서 한 개의 집중 요 소 는 항상 다른 한 개의 집중 요소 보다 크다.
A, B 두 배열 을 각각 자 르 고 절단 점 은 i, j 로 나 누 어 왼쪽 AB 와 오른쪽 AB 로 나 누 어 절단 점 이 A [i - 1] < = B [j] & B [j - 1] < = A [i] 를 만족 시 키 도록 한다. 이로써 왼쪽 AB 는 모두 오른쪽 AB 보다 작 고 len (왼쪽 AB) = len (총 AB) - len (오른쪽 AB) 을 만족 시 켜 i + j = m - i + n - j, 이때,
A, B 두 배열 의 총 길이 가 짝수 일 때 중위 = (max (A [i - 1], B [j - 1]) + min (A [i] + B [j]) / 2, 왼쪽 AB 의 최대 치 와 오른쪽 AB 의 최소 치 의 평균 값;
A, B 두 배열 의 총 길이 가 홀수 일 때 중위 = max (A [i - 1], B [j - 1]), 왼쪽 AB 의 최대 치
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
// m <= n
return findMedianSortedArrays(B,A);
}
int iMin = 0;
int iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (j != 0 && i != m && B[j - 1] > A[i]) {
iMin = i + 1;
} else if (i != 0 && j != n && A[i - 1] > B[j]) {
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(B[j - 1], A[i - 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;
}
}Q1: 왜 m < = n?
때문에 그리고 j = (m + n + 1) / 2 − i, j 확보 해 야 합 니 다. 음수 가 아니다.만약 n < m, 그러면 j 는 마이너스 일 수 있 고 이것 은 잘못된 답 을 초래 할 수 있 습 니 다.
Q2: j = (m + n + 1) / 2 − i, 왜 + 1?
A 배열 과 B 배열 의 총 길이 가 홀수 일 때 왼쪽 부분의 길이 가 오른쪽 부분 보다 1 크다 는 것 을 보증 해 야 중위 가 왼쪽 AB 의 최대 치 이기 때문이다.
그래서 i + j = m - i + n - j + 1 즉 j = (m + n + 1) / 2 - i
5. Z 자형 변환
주어진 문자열 을 주어진 줄 수 에 따라 위 에서 아래로, 왼쪽 에서 오른쪽으로 진행 합 니 다. Z 자형 배열.예 를 들 어 입력 문자열 은 "LEETCODEISHIRING" 입 니 다. 줄 수가 3 일 때 다음 과 같이 배열 합 니 다.
L C I R
E T O E S I I G
E D H N그 다음 에 출력 은 왼쪽 에서 오른쪽으로 한 줄 씩 읽 어야 합 니 다. 예 를 들 어 'LCIRETOISIGEDHN' 과 같은 새로운 문자열 이 생 성 됩 니 다.문자열 을 지정 한 줄 수 를 변환 하 는 함 수 를 실현 하 십시오: string convert (string s, int numRows);예시 1: 입력: s = "LEETCODEISHIRING", numRows = 3, 출력: "LCIRETOESIGEDHN" 예제 2: 입력: s = "LEETCODEISHIRING", numRows = 4, 출력: "LDREOEIIECIHNTSG"
L D R
E O E I I
E C I H N
T S G사고방식: 1. 줄 마다 StringBuilder 를 만 듭 니 다.2. 문자열 을 옮 겨 다 니 며 각 문 자 를 대응 하 는 줄 에 놓 고 첫 줄 과 마지막 줄 을 만나면 걷 는 방향 이 달라 집 니 다.3. 각 줄 의 StringBuilder 를 연결 합 니 다.
class Solution {
public String convert(String s, int numRows) {
if (s.length() < numRows || numRows == 1) {
return s;
}
// StringBuilder
List rowlist = new ArrayList<>(numRows);
for (int i = 0; i < numRows; ++i) {
rowlist.add(new StringBuilder());
}
// ，
int curRow = 0;
boolean growRow = false;
for (char ch : s.toCharArray()) {
rowlist.get(curRow).append(ch);
//
if (curRow == 0 || curRow == numRows - 1) {
growRow = !growRow;
}
curRow += growRow ? 1 : -1;
}
// StringBuilder
StringBuilder res = new StringBuilder();
for (StringBuilder sb : rowlist) {
res.append(sb);
}
return res.toString();
}
} 6. 정수 반전
32 비트 의 기호 정 수 를 보 여 주 려 면 이 정수 중의 모든 숫자 를 반전 시 켜 야 한다.
예시 1: 입력: 123 출력: 321 예제 2: 입력: - 123 출력: - 321 예제 3: 입력: 120 출력: 21 주의: 우리 의 환경 이 32 비트 의 기호 정수 만 저장 할 수 있다 고 가정 하면 그 수치 범 위 는? [−231, 231 − 1]。이 가설 에 따 르 면 반전 후 정수 가 넘 치면 0 으로 돌아 갑 니 다.
사고방식: 나머지 (%) 를 통 해 매 자릿수 를 얻 고 res = res * 10 + pop 한 자 리 를 통 해 들 어 갑 니 다. 중간 에 넘 치 는 상황 이 있 는 지 판단 해 야 합 니 다.
class Solution {
public int reverse(int x) {
int res = 0;
while (x != 0) {
//
int pop = x % 10;
//Integer ：-2147483648～2147483647
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > 7)) {
return 0;
}
if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < -8)) {
return 0;
}
res = res * 10 + pop;
x /= 10;
}
return res;
}
}7. 문자열 변환 정수 (atoi)
우선, 이 함 수 는 첫 번 째 빈 칸 이 아 닌 문 자 를 찾 을 때 까지 쓸모없는 시작 빈 칸 문 자 를 버 립 니 다.우리 가 찾 은 첫 번 째 비 어 있 는 문자 가 플러스 또는 마이너스 일 때 이 기 호 를 뒤의 가능 한 한 많은 연속 숫자 와 조합 하여 이 정수 의 플러스 와 마이너스 로 한다.첫 번 째 비 어 있 는 문자 가 숫자 라면 그 다음 의 연속 적 인 숫자 문자 와 조합 하여 정 수 를 이룬다.이 문자열 은 유효한 정수 부분 을 제외 하고 불필요 한 문자 가 존재 할 수 있 습 니 다. 이 문자 들 은 함수 에 영향 을 주지 않도록 무시 할 수 있 습 니 다.메모: 이 문자열 의 첫 번 째 빈 칸 문자 가 유효한 정수 문자 가 아니라면 문자열 이 비어 있 거나 문자열 이 빈 문자 만 포함 되 어 있 을 때 함수 가 변환 되 지 않 아 도 됩 니 다.어떠한 경우 에 도 함수 가 효과 적 인 변환 을 할 수 없 을 경우 0 을 되 돌려 주 십시오.
설명: 우리 의 환경 이 32 비트 크기 의 기호 정수 만 저장 할 수 있다 고 가정 하면 그 수치 범 위 는? [−231, 231 − 1]。만약 수치 가 이 범 위 를 초과 한다 면, 되 돌려 주 십시오. INT_MAX (231 또는 INT_MIN (−231) 。
예시 1: 입력: "42" 출력: 42 예제 2: 입력: " -42. 출력: - 42, 해석: 첫 번 째 비 공백 문 자 는 '-' 이 고 마이너스 입 니 다.우 리 는 가능 한 한 마이너스 와 뒤의 모든 연속 적 인 숫자 를 조합 하여 마지막 에 - 42 를 얻 었 다.예시 3: 입력: "4193 with words" 출력: 4193, 해석: 숫자 '3' 까지 변환 합 니 다. 다음 문 자 는 숫자 가 아니 기 때 문 입 니 다.예시 4: 입력: "words and 987" 출력: 0, 설명: 첫 번 째 비 어 있 는 문 자 는 'w' 이지 만 숫자 나 플러스, 마이너스 가 아 닙 니 다. 따라서 효과 적 인 전환 을 수행 할 수 없습니다.예시 5: 입력: "- 91283472332" 출력: - 2147483648 해석: 숫자 "- 91283472332" 는 32 위 를 초과 하여 기호 정수 범위 가 있 기 때문에 INT 로 돌아 갑 니 다.MIN (−231) 。
사고방식: 1. 문자열 의 앞 뒤 공백 제거 하기;2. 첫 번 째 문자 가 양음 호 인 경우 처리 하기;3. 하나씩 취 수 판단 은 res * 10 + tmp 를 통 해 수 를 채 웁 니 다.4. 7 정수 반전 이 넘 쳤 는 지 판단 하기 (초기 생각)
class Solution {
public int myAtoi(String str) {
str = str.trim();
int res = 0;
int i = 0;
boolean negativeFlag = false;
if (str.startsWith("-")) {
i++;
negativeFlag = true;
}
if (str.startsWith("+")) {
i++;
}
char[] strArray = str.toCharArray();
for (; i < strArray.length; ++i) {
if (strArray[i] < '0' || strArray[i] > '9') {
return negativeFlag ? -res : res;
}
int tmp = strArray[i] - '0';
if (!negativeFlag && (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && tmp > 7))) {
return Integer.MAX_VALUE;
}
if (negativeFlag && (-res < Integer.MIN_VALUE / 10 || (-res == Integer.MIN_VALUE / 10 && tmp > 8))) {
return Integer.MIN_VALUE;
}
res = res * 10 + tmp;
}
return negativeFlag ? -res : res;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
