데이터 구조와 알고리즘 분석 - 자바 언어 설명(제2장(2)
9332 단어 데이터 구조와 알고리즘 분석
귀속 없이 빠른 멱을 구하는 프로그램을 써라.
/**
*
*
* @param x
* @param n
* @return
*/
public long pow(long x,int n){
if(n == 0){
return 1;
}
if(isEven(n)){
return pow(x * x,n /2);
}else{
return pow(x ,n-1) * x;
}
}
/**
*
*
* @param x
* @param n
* @return
*/
public long pow2(long x,int n){
long pow = 1;
while(n > 0){
if(!isEven(n)){
pow *= x;
}
x *= x;
n = n / 2;
}
return pow;
}
/**
*
*
* @param n
* @return
*/
private static boolean isEven(int n) {
if((n&1) == 0){
return true;
}else{
return false;
}
}연습 문제
크기가 N인 배열 A의 기본 요소는 N/2회 이상 나타나는 요소입니다(이러한 요소는 최대 하나).예를 들어 수조 3, 4, 2, 4, 4, 2, 4, 4, 4는 하나의 주원소 4가 있는데 수조 3, 4, 2, 4, 4, 2, 4는 주원소가 없다.만약 주 요소가 없다면, 너의 프로그램은 반드시 지적해야 한다.다음은 이 문제를 풀기 위한 알고리즘의 개요입니다. 우선, 주원소의 후보원을 찾아라(이것은 어려운 부분이다).이 후보원은 주원소일 가능성이 있는 유일한 원소다.두 번째 단계는 이 후보원이 사실상 주원소인지 여부를 확정한다.이것은 마침 수조에 대한 순서 검색이다.배열 A의 후보원을 찾기 위해 두 번째 배열 B를 구성합니다.A1과 A2를 비교하다.만약 그것들이 같다면 그 중 하나를 취하여 그룹 B에 추가한다.안 그러면 아무것도 안 해.그리고 A3과 A4를 비교한다. 마찬가지로 그것들이 같으면 그 중 하나를 취하여 B에 첨가한다.안 그러면 아무것도 안 해.이 방식으로 전체 그룹을 다 읽을 때까지 계속해라.그리고 그룹 B의 후보원을 차례로 찾기;그것도 A의 후보원이다.
/**
* x
*
* @param A
* @param N
* @param x
* @return
*/
public boolean isMainElement(int[] A,int N,int x){
int count = 0;
for(int i = 0; i < N; i++){
if(A[i] == x){
count++;
}
}
if(count > N/2){
return true;
}
return false;
}
/**
* ： ：
* B， A_1,A_2， B； 。 A_3,A_4， ， B； 。
* 。 B 。
*
* @param A
* @param B
* @param N： A
* @param N2： B
* @return
*/
public int findMainElement(int[] A,int[] B,int N,int N2){
// ： B 1 0 。
if(N == 0){
return Integer.MIN_VALUE;
}
if(N == 1){
if(isMainElement(B,N2,A[0])){
return A[0];
}else{
return Integer.MIN_VALUE;
}
}
int count = 0;
// A
for(int i = 0; i < N - 1; i++){
if(A[i] == A[i + 1]){
B[count++] = A[i];
}
}
int res =findMainElement(B,A,count,N);
// ： ， ，
if(res == Integer.MIN_VALUE && (N&1) == 1 && isMainElement(A,N,A[N - 1])){
return A[N - 1];
}
return res;
}방법2: 추가 배열 B를 사용하지 않습니다.
이 수의 출현 횟수를 x로 설정하면 x는 n/2+1<=x<=n을 만족시킨다.그래서 이 숫자와 나머지 숫자가 모두 상쇄되면 적어도 1개가 남았다고 상상할 수 있다.우리는 뒤로 옮겨다니며 키를 첫 번째 수로 설정하고 키가 나타나는 횟수는count이며 1로 초기화하면 키가 한 번 나타난 것을 의미한다.앞으로 가면 어떤 수가 키와 같지 않으면 둘이 상쇄하고 키가 나타나는 횟수가 1로 줄어든다.키와 같으면 키가 나오는 횟수에 1을 더하고 키가 나오는 횟수가 0이 되면 키가 다 썼기 때문에 키를 다른 수로 다시 초기화해야 한다.상기 절차를 반복하면 반드시 n/2보다 큰 수가 있기 때문에 마지막에 남은 수를 두루 훑어보면 요구된 수이다.
/**
* ： B
*
* @param A
* @return
*/
public int getMainElement(int[] A){
int count = 1;
int result = A[0];
for(int i = 1; i < A.length; i++){
if(count == 0){
result = A[i];
}else{
if(result == A[i]){
count++;
}else{
count--;
}
}
}
// ， X 。
// ， ， X N/2 。
boolean isMainEle = isMainElement(A, A.length, result);
if(isMainEle){
return result;
}else {
return Integer.MIN_VALUE;
}
}연습 문제
입력은 N입니다.×N의 디지털 행렬이 메모리에 읽혔습니다.줄마다 왼쪽에서 오른쪽으로 증가합니다.매 열은 위에서 아래로 증가한다.X가 행렬에 있는지 여부를 결정하기 위해 O (N) 최악의 상황 알고리즘을 제시합니다.
아이디어:
가장 좋은 알고리즘은 행렬의 가장 오른쪽 하단이나 가장 왼쪽 상단을 제거하는 원소이다. 이 원소는 소재열과 행위 안장점, 즉 줄의 최대 열이 가장 작거나 열의 최대 줄이 가장 작다.예를 들어 가장 왼쪽 아래에 있는 원소를 취하여 a로 기록한다. 만약에 a>k가 a보다 크다면 a가 있는 줄이 a보다 크다는 것을 나타낸다. 이 줄은 틀림없이 이 줄에 없고 열로만 찾을 수 있다.하면, 만약, 만약...
/**
* @param arr
* @param N
* @param searchKey
* @return
*/
public boolean findIfExist(int[][] arr,int N,int searchKey){
int i = N - 1,j = 0;
while(i >=0 && j <= N - 1){
if(arr[i][j] > searchKey){
i--;
} else if(arr[i][j] < searchKey){
j++;
} else {
return true;
}
}
return false;
}연습 문제
정수의 수조 a를 사용하여 유효한 알고리즘을 설계하여 확정한다. 그 중에서 j>=i, a[j]+a[i]의 최대치 a[j]-a[i]의 최대치 a[j]*a[i]의 최대치 a[j]/a[i]의 최대치
/**
* ： for ， O(N^2)
*
* @param a
* @param operator
* @return
*/
public static int getMaxValue(int[] a, String operator) {
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
int thisValue = 0;
for (int j = i + 1; j < a.length; j++) {
switch (operator) {
case "+":
thisValue = a[j] + a[i];
break;
case "-":
thisValue = a[j] - a[i];
break;
case "*":
thisValue = a[j] * a[i];
break;
case "/":
thisValue = a[j] / a[i];
break;
default:
return Integer.MIN_VALUE;
}
if (thisValue > maxValue) {
maxValue = thisValue;
}
}
}
return maxValue;
}
확장 문제: 정수의 수조 a를 사용하여 효과적인 알고리즘을 설계하여 그 중에서 j>=i, a[j]-a[i]의 최대치를 확정한다.
문제 해결 방법:
만약 현재 수를 피감수로 한다면, 뒤의 수와 그것을 상감하여 최대치를 얻으려면 뒤의 최대치와 그것을 줄여야 한다. 현재 수 뒤의 최대치를 스캔하면 기록할 수 있다.다음 수의 현재 값을 뺀 최대 값은 max이고, 그룹의 현재 값 왼쪽의 최소 값은minLeft입니다.스캔할 때마다 현재 수에서minLeft를 빼고 max와 비교합니다.크면 max를 업데이트하고 왼쪽 부분의 최소값인minLeft를 업데이트합니다.
/**
* a[j] - a[i] ， j>=i
* O(N)
*
* @param a
* @return
*/
public static int getMinusMax(int[] a) {
if (a == null || a.length == 0) {
return Integer.MIN_VALUE;
}
if (a.length == 1) {
return a[0];
}
int max = a[1] - a[0];
int minLeft = a[0];
for (int i = 1; i < a.length; i++) {
int temp = a[i] - minLeft;
if (temp > max) {
max = temp;
}
if (a[i] < minLeft) {
minLeft = a[i];
}
}
return max;
}따라서 위의 네 가지 연산 최대치도 다른 방법으로 해결할 수 있다.먼저 다음과 같은 열거 클래스 Operator를 만듭니다.
/**
* @description:
* @author:
* @date: 2018/8/1
*/
@Getter
public enum Operator {
PLUS("+"," "),
MINUS("-"," "),
MULTI("*"," "),
DIV("/"," ")
;
private String code;
private String desc;
Operator(String code,String desc){
this.code = code;
this.desc = desc;
}
} /**
* ：
*
* @param a
* @return
*/
public static int getPlusMax(int[] a,String operator) {
if(a == null || a.length == 0){
return Integer.MIN_VALUE;
}
if(a.length == 1){
return a[0];
}
int max;
//
if(Operator.PLUS.getCode().equals(operator)){
max = a[1] + a[0];
} else if(Operator.MINUS.getCode().equals(operator)){
max = a[1] - a[0];
} else if(Operator.MULTI.getCode().equals(operator)){
max = a[1] * a[0];
} else{
max = a[1] / a[0];
}
int left = a[0];
int temp;
for(int i = 1; i < a.length; i++){
//
if(Operator.PLUS.getCode().equals(operator)){
temp = a[i] + left;
} else if(Operator.MINUS.getCode().equals(operator)){
temp = a[i] - left;
} else if(Operator.MULTI.getCode().equals(operator)){
temp = a[i] * left;
} else{
temp = a[i] / left;
}
if(temp > max){
max = temp;
}
if(Operator.PLUS.getCode().equals(operator) || Operator.MULTI.getCode().equals(operator)){
if(a[i] > left){
left = a[i];
}
} else if(Operator.MINUS.getCode().equals(operator) || Operator.DIV.getCode().equals(operator)){
if(a[i] < left){
left = a[i];
}
}
}
return max;
}좋은 웹페이지 즐겨찾기
