LintCode 알고리즘 입문:
묘사 하 다.
두 개의 정 수 를 제시 하 다. aa 화해시키다 bb , 그들의 화 해 를 구하 다.
입력 흐름 에서 데 이 터 를 읽 을 필요 가 없습니다.
aplusb 의 두 매개 변수 a 와 b 에 따라 그들의 합 을 계산 하고 돌아 오 면 됩 니 다.설명 하 다.
a 와 b 는 모두
32 정수 요?하면, 만약, 만약...
a=1 그리고 b=2, 귀환 3.생각:
우선 비트 연산 으로 조작 할 생각 을 해 야 한다. 즉, 이 진 으로 처리 해 야 한다. 좋아, 여기까지 생각 한 이상 당연히 예 를 들 어 생각해 야 한다. 가장 간단 한 1 + 2.
1 의 이 진 · · · 0001
2 의 이 진 · · · 0010
3 의 이 진 · · · 0011
그럼 a + b 는 a | b 와 같 지 않 습 니까?그럼 1 + 3 을 다시 한 번 검증 해 보 겠 습 니 다.
1 의 이 진 · · · 0001
3 의 이 진 · · · 0011
4 의 이 진 · · · 0100
이전의 추측 이 틀 렸 다 는 것 을 발견 한 후에 다른 간단 한 검산 을 거 쳐 우 리 는 하나의 규칙 을 쉽게 발견 할 것 이다. 만약 에 진 위 를 하지 않 으 면 a + b = a | b 가 진 위 를 하면 성립 되 지 않 는 다.
그래서 다음 에 진 위 를 처리 해 야 합 니 다. 우 리 는 1 + 3 으로 진 위 를 연구 하고 있 습 니 다. 만약 에 우리 가 진 위 를 무시 한 후에 진 위 를 해 야 할 위 치 를 더 하면 우리 의 값 입 니 다.
1 의 바 이 너 리 (a) · · · 0001
3 의 2 진법 (b) · · · 0011
진 위 를 무시 하 는 바 이 너 리 (c) · · · 0010 (진 위 를 무시 하 는 위치) 입 니 다. 진 위 를 무시 한 이상 다음 에 진 위 를 추가 해 야 합 니 다.
들 어가 야 할 값 (d) · · · 0010
우리 의 값 은 c + d 여야 합 니 다.
c 의 이 진 · · · 0010
d 의 이 진 · · · 0010
진 을 무시 하 는 바 이 너 리 (e) · · · 0000
들 어가 야 할 값 (f) · · · 0100
결 과 는 e + f = 4
해결 방법:
step 1: a 와 b 를 먼저 계산 합 니 다 (진 위 를 무시 합 니 다) (비트 연산 자 a ^ b 에 해당 합 니 다) a ^ b: 바 이 너 리 의 이 또는 연산
step 2: 들 어가 야 할 값 (진 위 를 계산) (비트 연산 a & b < < 1) a & b <
step 3: 위의 step 1 의 값 과 step 2 의 값 을 더 합 니 다.만약 에 자리 가 있 으 면 step 1, step 2 를 계속 실행 하고 쌍방 이 0 이 될 때 까지 다른 쪽 을 출력 하 는 것 이 추가 적 인 결과 입 니 다.
정 답 1:
public class Solution {
/**
* @param a: An integer
* @param b: An integer
* @return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here
if (a==0)return b;
if(b==0)return a;
int c=a^b;// ，
int d=(a&b)<<1;// ，
return aplusb(c,d);
// c+d ， aplus ， ， //
}
}정 답 2:
public static int add( int number_1, int number_2 )
{
int sum = 0;
int carry = 0;
do
{
sum = number_1 ^ number_2;
carry = ( number_1 & number_2 ) << 1;
number_1 = sum;
number_2 = carry;
}
while ( carry != 0 );
return sum;
}
2. 알고리즘 을 설계 하여 n 단계 곱 하기 중 꼬리 0 의 개 수 를 계산한다.
묘사 하 다.
n 단계 곱 하기 중 꼬리 0 의 개 수 를 계산 하 는 알고리즘 을 설계 하 다.
당신 은 실제 면접 에서 이 문 제 를 만난 적 이 있 습 니까? 예.
본보기
11! = 39916800
도전 하 다.
O (logN) 의 시간 복잡 도
분석 하 다.
1、2、3、4、5、6、7、8、9、10、11、...101
1 - 101 리 에 5 개의 숫자 가 있 고 한 개의 숫자 가 있 는 계층 의 꼬리 부분 에 0 이 생 긴 다. 각각 5, 10, 15, 20, 25, 100 은 모두 101 / 5 = 20 개 이다.
또: 5, 10, 15, 20, 25,... 100
5 * (1, 2, 3, 4, 5, 6,... 20) 로 바 뀌 면 5 개의 숫자 가 연속 되 어 있 습 니 다.
그래서 5 * 5 * (1, 2, 3, 4) 로 바 꿀 수 있 습 니 다.
101. 그래서 최종 적 으로 가지 고 있 는 0 개 수 는...
101/5=20
20/5=4
하나 24 개
디자인 사고: n 개의 데 이 터 를 5 로 나 누고 정리 하지 않 으 면 순환 에 넣 어 0 이 있 는 개 수 를 누적 합 니 다.
public class Solution {
/*
* @param n: An integer
* @return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
// write your code here, try to do it without arithmetic operators.
long temp=n/5;
long count=0;
while(temp!=0){// ，
count+=temp;//
temp/=5;// temp ，
}
return count;
}
}3. 주 원소
하나의 정형 배열 을 지정 하고 주 요 소 를 찾 습 니 다. 배열 에서 의 출현 횟수 는 배열 요소 개수 의 2 분 의 1 보다 엄 격 히 큽 니 다.
본보기
배열 [1, 1, 1, 1, 2, 2, 2] 을 드 리 고 1 로 돌아 갑 니 다.
도전 하 다.
요구 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.
분석:
배열 에서 의 출현 횟수 를 이용 하여 배열 요소 개수 의 2 분 의 1 보다 엄 격 히 제어 한다.
초기 값 과 계수 기 를 정의 합 니 다. 배열 의 다음 원본 은 초기 값 과 같 지 않 습 니 다. 계수 기 는 1 을 줄 입 니 다.
초기 값 카운터 에 1 을 추가 하 는 것 과 같 으 면 카운터 가 1 이 고 출력 할 때의 값 은 주 요소 입 니 다.
public class Solution {
/*
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(List nums) {
// N/2
int n=1;//
int temp=nums.get(0);//
for(int i=1;i 4. 3 자리 정수 반전
세 자리 수 밖 에 없 는 정 수 를 반전 하 다.
본보기
123 반전 다음 에는... 321 。 900 반전 다음 에는... 9 。 주의 사항
너 는 입력 이 반드시 세 자릿수 만 있 는 정수 라 고 가정 할 수 있다. 이 정 수 는 100 보다 크 고 1000 보다 작다.
public class Solution {
/**
* @param number: A 3-digit number.
* @return: Reversed number.
*/
public int reverseInteger(int number) {
// write your code here
int a,b,c,temp;//
a=number/100;// ，
b=(number%100)/10;//
c=number%10;//
temp=c*100+b*10+a;//
return temp;
}
}5、 정렬 배열 병합
본보기
A = [1, 2, 3, 4], B = [2, 4, 5, 6] 을 주 고 돌아 갑 니 다. [1,2,2,3,4,4,5,6]
도전 하 다.
당신 은 당신 의 알고리즘 을 최적화 할 수 있 습 니까? 만약 그 중의 한 배열 이 크 고 다른 배열 이 매우 작다 면?
생각:
1. 길 이 를 A + B 길이 의 배열 로 정의 합 니 다.
2. 발생 가능 한 상황:
1 - A 와 B 는 모두 빈 배열 2 - A 와 B 는 모두 빈 배열 이 아니다 (길이 가 0 이 아니다) 3 - A 와 B 중 하 나 는 빈 배열 이다.
상황 1: 새 배열 로 바로 돌아 가기 상황 2: 만족 상황 2 (길이 가 모두 0 보다 크다). A, B 에 대응 하 는 요소 (배열 요소 순환 비교 크기) 를 순서대로 비교 합 니 다.
작은 것 은 먼저 배열 에 저장 하고 한 배열 이 모두 새 배열 에 삽입 되면 다른 배열 은 순서대로 새 배열 을 삽입 합 니 다.
상황 3: 다른 배열 을 새 배열 에 직접 저장 합 니 다.
public class Solution {
/**
* @param A: sorted integer array A
* @param B: sorted integer array B
* @return: A new sorted integer array
*/
public int[] mergeSortedArray(int[] A, int[] B) {
// write your code here
int[] c=new int[A.length+B.length];// ，
int index1=0;// A
int index2=0;// B
int curr=0;//c
//
while(index16. 반전 배열
： n a， ， ， 。 [l,r] a[l], a[l+1], ..., a[r]。 a[1], a[2], ..., a[l-2], a[l-1], a[l], a[l+1], ..., a[r-1], a[r], a[r+1], a[r+2], ..., a[n-1], a[n]， [l,r] a[1], a[2], ..., a[l-2], a[l-1], a[r], a[r-1], ..., a[l+1], a[l], a[r+1], a[r+2], ..., a[n-1], a[n]。 입력 첫 번 째 줄 데 이 터 는 하나의 정수 이다. n (1 ≤ n ≤ 105) 은 배열 의 길 이 를 나타 낸다.두 번 째 줄 의 데 이 터 는 n 개의 정수 a [1], a [2], a [n] (1 ≤ a [i] ≤ 109) 이다.
샘플 입력 4 2 1 3 4
출력 "yes" 를 출력 합 니 다. 존재 한다 면;그렇지 않 으 면 "no" 를 출력 하고 따옴표 를 출력 하지 않 습 니 다.
샘플 출력 yes
생각:
1. 두 배열 a, b 를 정의 하고 할당 값 이 같 으 며 길이 가 같 습 니 다.
2. 배열 b 를 오름차 순 으로 한다.
3. 배열 a 의 요 소 를 배열 b 의 좌우 양쪽 과 순서대로 비교 하고 왼쪽 에서 배열 이 대응 하지 않 는 번호 left 를 기록 하 며 오른쪽 에서 두 수치 가 서로 다른 번호 right 를 기록 합 니 다.(2134) (1234) 왼쪽 부터 서로 다른 번호 left = 0;오른쪽 이 비교적 같 지 않 은 번 호 는 right = 1 이다.
4. 마지막 으로 이 서로 다른 번호 간 에 교차 하 는 똑 같은 규칙 (21) (12) a [left + i] = = b [right - i] 을 만족 시 키 는 지 비교 합 니 다.이 규칙 을 만족 시 키 면, 이 출력 yes
그렇지 않 으 면 no 출력;
package com.demo.day8.list;
import java.util.Arrays;
import java.util.Scanner;
/* 。
* ： n a， ，
* ，
* ：n (1≤n≤105)， 。
* n a[1], a[2], ..., a[n] (1≤a[i]≤109)。
* “yes”， ； “no”， 。
*/
public class ArrayTest {
public static void main(String[] args) {
//
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int len=sc.nextInt();//
// 1、 a、b， ， ；
int[]a=new int[len];// A， len
int[]b=new int[len];// B， len
for(int i=0;i7. 수열 의 합 을 구한다
제목 설명:
수열 의 정 의 는 다음 과 같다. 수열 의 첫 번 째 항목 은 n 이 고 앞으로 각 항목 은 앞의 제곱 근 이 며 수열 의 앞 m 항목 의 합 을 구한다.
입력
81 4 2 2
입력 데 이 터 는 여러 그룹 이 있 고 각 그룹 은 한 줄 을 차지 하 며 두 개의 정수 n (n < 10000) 과 m (m < 1000) 로 구성 되 며 n 과 m 의 의 미 는 앞에서 말 한 바 와 같다.
출력
94.73 3.41
각 조 의 입력 데이터 에 대해 이 수열 을 출력 하 는 것 과 모든 테스트 인 스 턴 스 가 한 줄 을 차지 하고 정밀도 가 2 비트 소 수 를 유지 해 야 합 니 다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
// ：
/*
* 1 m
* 2 n
* 3
*/
//
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {//
double n=sc.nextInt();//
int m=sc.nextInt();//
double[] arr=new double[m];// m
double num=0;//
arr[0]=n;
for(int i=1;i8. 수선화 찾기
/* * 수선화 찾기 * 수선화 수 는 세 자리 수 를 말 하 는데 그 숫자 들 의 입방 은 그 자체 와 같다. 예 를 들 어 153 = 1 ^ 3 + 5 ^ 3 + 3 ^ 3 * 생각: * 1. 길이 (n - m + 1) 배열 정의 * 2. 한 개의 수 를 꺼 내 고 백 자리, 열 자리, 한 자 리 를 구한다. * 3. 만족 여 부 를 판단 하 는 새로운 배열 에 존재 하고 만족 하지 않 으 면 다음 을 찾 습 니 다. */
package com.test;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main2 {
/*
*
* ” ， ， ：153=1^3+5^3+3^3
* :
* 1、 (n-m+1）
* 2、 ， 、 、
* 3、 ，
*/
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
// String s=sc.nextLine();//
// String[] array=s.split(" ");//
int m=sc.nextInt();//
int n=sc.nextInt();//
// n-m+1
int[] arr= new int[20];
boolean flag=false;
int j=0;
for(int i=m;i=m&&i<=n) {
int a=i/100;//
int b=(i%100)/10;//
int c=(i%100)%10;//
if((a*a*a+b*b*b+c*c*c)==(a*100+b*10+c))
{
arr[j]=a*100+b*10+c;
j++;
flag=true;
}
}
if(flag==true) {
for(int i=0;i 9. 대소 문자 변환 II
묘사 하 다.
문자열 의 소문 자 를 대문자 로 변환 합 니 다. 알파벳 이 아 닌 다른 문 자 는 무시 합 니 다.
본보기
내놓다
"abc", 귀환 "ABC" . 내놓다
"aBc", 귀환 "ABC" . 내놓다
"abC12", 귀환 "ABC12" . 생각:
1. 빈 문자열 Newstr 정의
2. 입력 한 문자열 의 모든 요 소 를 꺼 내 소문 자 여 부 를 판단 합 니 다.
3. 소문 자 는 대문자 로 바 뀌 고 Newstr 에 추가 되 며, 그렇지 않 으 면 Newstr 문자열 에 직접 추가 합 니 다.
public class Solution {
/**
* @param str: A string
* @return: A string
*/
public String lowercaseToUppercase2(String str) {
// write your code here
String newStr ="";//
for (int i = 0; i < str.length(); i++){//
char ch = str.charAt(i);//charAt(i) i
if (Character.isLowerCase(ch)){//
ch = Character.toUpperCase(ch);//
}
newStr += ch;//
}
return newStr;
}
}10. 수선화 찾기 II
묘사 하 다.
수선화 수의 정 의 는 이 수 는 그의 모든 상수 의 멱 차 의 합 과 같다 는 것 이다. 위 키 백과 의 정의 참조
예 를 들 어 세 자리 의 십 진법 정수
153 는 하나의 수선화 수 이다. 153 = 13 이기 때문이다. + 53 + 33。 그리고 한 4 자리 의 10 진수
1634 도 하나의 수선화 수 이다. 왜냐하면 1634 = 14 + 64 + 34 + 44。 n 을 주 고 n 자리 10 진 수선화 수 를 모두 찾 습 니 다.너 는 n 이 8 보다 작다 고 생각 할 수 있다.
본보기
예 를 들 면 n =
1 모든 수선화 수 는: [0,1,2,3,4,5,6,7,8,9] 이 고 n = 2, 2 자리 수선화 수 없 이 되 돌아 갑 니 다. [] 。 사고의 방향
package com.test;
import java.util.ArrayList;
public class Solution {
/*
* @param n: The number of digits.
*
* @return: All narcissistic numbers with n digits.
*/
public ArrayList getNarcissisticNumbers(int n) {
// write your code here
/*
*
* 1.
* 2. pow(m,n) ， m n
* 3.n ， ，
*/
ArrayList result = new ArrayList();
if(n==1)
{
for(int i=0;i<10;i++){
result.add(i);
}
return result;
}
for (int i = pow(10, n - 1); i <= (pow(10, n) - 1); i++) {// n
int num = i;
int temp = 0;
for (int j = 0; j < n; j++) {
temp += pow((num % 10), n);//
num = num / 10;// 、 、..
}
if (temp == i) {
result.add(temp);
}
}
return result;
}
public final int pow(int m, int n) {
int val = 1;
for (int i = 1; i <= n; ++i)
val *= m;//
return val;
}
} 11. 링크 에서 노드 찾기
묘사 하 다.
링크 에서 값 이 value 인 노드 를 찾 습 니 다. 없 으 면 비어 있 습 니 다.
본보기
내놓다
1->2->3 value = 3 과 마지막 노드 last node 를 되 돌려 줍 니 다.내놓다
1->2->3 value = 4 와 비어 있 음 을 되 돌려 줍 니 다.
public class Solution {
/*
* @param head: the head of linked list.
* @param val: An integer.
* @return: a linked node or null.
*/
public ListNode findNode(ListNode head, int val) {
// write your code here
while(head!=null){
if(head.val==val){// ，
return head;
}
head=head.next;// ，
}
return head;
}
}12. 링크 의 중심 점
묘사 하 다.
체인 시계의 중심 점 을 찾다.
본보기
체인 테이블
1->2->3 중점 2 。 체인 테이블
1->2 중점 1 。 도전 하 다.
만약 링크 가 데이터 흐름 이 라면 링크 를 다시 옮 겨 다 니 지 않 고 중심 점 을 얻 을 수 있 습 니까?
사고: 링크 를 옮 겨 다 니 며 링크 의 길 이 를 얻 을 수 있 습 니 다. 중심 점 의 위 치 는 (링크 길이 - 1) / 2 의 아래 표 시 된 위치 이 고 이 노드 로 돌아 갑 니 다.
public class Solution {
/**
* @param head: the head of linked list.
* @return: a middle node of the linked list
*/
public ListNode middleNode(ListNode head) {
// ListNode ，
ListNode ln =head;
int i=0;
while(head!=null){
head=head.next;// ， ，
i++;
}
for(int j=0;j13. 문자열 을 정수 로 변환 하기 (쉬 운 버 전)
묘사 하 다.
Given a string, convert it to an integer. You may assume the string is a valid integer number that can be presented by a signed 32bit integer (-231 ~ 231-1).
본보기
내놓다
"123", 귀환 123 . public class Solution {
/**
* @param str: A string
* @return: An integer
*/
public int stringToInteger(String str) {
// write your code here
//valueOf Integer ，
// string Integer
// Integer.valueOf（"345"） ，345 Integer
return Integer.valueOf(str);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
