검지 제공 문제 정리 (31 - 40), 자바 버 전
12005 단어 데이터 구조/알고리즘
제목 설명
1 ~ 13 의 정수 중 1 이 나타 나 는 횟수 를 구하 고 100 ~ 1300 의 정수 중 1 이 나타 나 는 횟수 를 계산 합 니까?이 를 위해 그 는 1 ~ 13 에 1 이 포 함 된 숫자 가 1, 10, 11, 12, 13 이 라 고 특별히 세 어 보 았 지만 뒤의 문제 에 대해 서 는 어 쩔 수 없 었 다.ACMer 는 여러분 이 그 를 도와 주 고 문 제 를 더욱 보편화 시 켜 서 임의의 부정 정수 구간 에서 1 이 나타 나 는 횟수 (1 에서 n 에서 1 이 나타 나 는 횟수) 를 빨리 구 할 수 있 기 를 바 랍 니 다.
생각:
이 문제 의 사고방식 은 평론 구역 에서 나온다.
알고리즘 구현
class Solution31 {
public int NumberOf1Between1AndN_Solution(int n) {
int count=0;
int i=1;//i
int current=0,before=0,after=0;
while(n/i!=0) {
current=(n/i)%10;// ( )
before=n/(i*10);// ( )
after=n%i;// ( )
if(current==0) {
// 0, 1 , *
count+=before*i;
}else if(current==1) {
// 1, 1 , * + +1
count+=before*i+after+1;
}else {
// 1, 1 ,
//（ +1）*
count+=(before+1)*i;
}
i*=10;
}
return count;
}
}
32. 배열 을 가장 작은 수로 배열 한다.
제목 설명
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
생각:
비교 기 가 들 어간 sort () 를 사 용 했 습 니 다.
알고리즘 구현
class Solution32 {
public String PrintMinNumber(int [] numbers) {
ArrayList list = new ArrayList();
for(int i =0; i() {
@Override
public int compare(Integer o1, Integer o2) {
String str1=o1+""+o2;
String str2=o2+""+o1;
return str1.compareTo(str2);
}
});
for (Integer i : list) {
s+=i;
}
return s;
}
}
33. 축 수
제목 설명
질 인자 2, 3, 5 만 포 함 된 수 를 축 수 (Ugly Number) 라 고 한다.예 를 들 어 6, 8 은 모두 못 생 긴 숫자 이지 만 14 는 그렇지 않다. 왜냐하면 그것 은 질 인자 7 을 포함 하기 때문이다.습관 적 으로 우 리 는 1 을 첫 번 째 못 생 긴 숫자 로 여 긴 다.어 릴 때 부터 큰 순서 로 N 번 째 축 수 를 구하 세 요.
생각:
세 개의 대기 열 을 유지 합 니 다. 각각 2 의 배수, 3 의 배수, 5 의 배수 입 니 다. 대기 열 에서 순서대로 가장 작은 것 을 가 져 옵 니 다.
알고리즘 구현
여 기 는 세 개의 색인 으로 세 개의 대기 열 을 대표 하여 공간 을 절약 할 수 있다.
class Solution33 {
public int GetUglyNumber_Solution(int index) {
// 0-6 0-6
if(index < 7) return index;
//p2，p3，p5 ，newNum
int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
Vector arr = new Vector();
arr.add(newNum);
while(arr.size() < index) {
//
newNum = Math.min(arr.get(p2) * 2, Math.min(arr.get(p3) * 3, arr.get(p5) * 5));
// if ，
if(arr.get(p2) * 2 == newNum) p2++;
if(arr.get(p3) * 3 == newNum) p3++;
if(arr.get(p5) * 5 == newNum) p5++;
arr.add(newNum);
}
return newNum;
}
}
34. 첫 번 째 는 순서대로 문자 만 나타 납 니 다.
제목 설명
문자열 (0 < = 문자열 길이 < = 10000, 모두 알파벳 으로 구 성 됨) 에서 첫 번 째 로 한 번 만 나타 나 는 문 자 를 찾 고 그 위 치 를 되 돌려 줍 니 다. 없 으 면 - 1 (대소 문 자 를 구분 해 야 합 니 다) 을 되 돌려 줍 니 다.
생각:
HashMap 사용 하기
알고리즘 구현
class Solution34 {
public int FirstNotRepeatingChar(String str) {
HashMap map = new HashMap();
for(int i=0;i 35. 배열 의 역순 대
제목 설명
배열 에 있 는 두 개의 숫자 가 앞의 숫자 가 뒤의 숫자 보다 크 면 이 두 개의 숫자 는 하나의 역순 대 를 구성한다.배열 을 입력 하여 이 배열 의 역순 쌍 의 총 P 를 구하 십시오.그리고 P 를 1000000007 모드 로 출력 합 니 다.출력 P% 1000000007 입력 설명:
제목 은 입력 한 배열 에 같은 숫자 가 없 음 을 보증 합 니 다.
데이터 범위:
%50 ,size<=10^4
%75 ,size<=10^5
%100 ,size<=2*10^5.
생각:
댓 글 영역 에서 왔 습 니 다. 정렬 개선 을 병합 하고 데 이 터 를 앞 뒤 두 배열 로 나 누 었 습 니 다. (각 배열 에 하나의 데이터 항목 만 있 음) 배열 을 합 쳤 습 니 다. 합 쳤 을 때 앞의 배열 값 array [i] 가 뒤의 배열 값 array [j] 보다 클 때;앞의 배열 array [i] ~ array [mid] 는 모두 array [j] 보다 크 고 count + = mid + 1 - i 입 니 다.검 지 Offer 를 참고 하 였 으 나 검 지 Offer 의 병합 과정 이 한 단계 빠 진 것 같 습 니 다.그리고 테스트 용례 출력 결과 가 비교적 커서 매번 되 돌아 오 는 count mod (1000000007) 에 여 유 를 구 합 니 다.
알고리즘 구현
public class Solution {
public int InversePairs(int [] array) {
if(array==null||array.length==0)
{
return 0;
}
int[] copy = new int[array.length];
for(int i=0;i>1;
int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
int count = 0;
int i=mid;
int j=high;
int locCopy = high;
while(i>=low&&j>mid)
{
if(array[i]>array[j])
{
count += j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007)//
{
count%=1000000007;
}
}
else
{
copy[locCopy--] = array[j--];
}
}
for(;i>=low;i--)
{
copy[locCopy--]=array[i];
}
for(;j>mid;j--)
{
copy[locCopy--]=array[j];
}
for(int s=low;s<=high;s++)
{
array[s] = copy[s];
}
return (leftCount+rightCount+count)%1000000007;
}
}
36. 두 개의 링크 의 첫 번 째 공공 노드
제목 설명
두 개의 링크 를 입력 하여 그들의 첫 번 째 공공 노드 를 찾 아 라.
생각:
두 개의 링크 가 공공 노드 가 존재 하면 링크 의 꼬리 부분 에 만 있 을 수 있 습 니 다. 링크 는 단 방향 이기 때 문 입 니 다.그래서 먼저 링크 의 길 이 를 통계 한 다음 에 긴 링크 는 짧 은 링크 의 길이 와 같 을 때 까지 거 리 를 먼저 가 야 한다.그리고 같은 노드 를 만 날 때 까지 순서대로 비교 합 니 다.
알고리즘 구현
class Solution36 {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int len1 = GetLengthOfList(pHead1);
int len2 = GetLengthOfList(pHead2);
ListNode LongList = pHead1;
ListNode ShortList = pHead2;
int k = len1 - len2;
if (len2 > len1) {
LongList = pHead2;
ShortList = pHead1;
k = len2 - len1;
}
for (int i = 0; i < k; i++) {
LongList = LongList.next;// K
}
while ((LongList != null) && (ShortList != null) && (LongList.val != ShortList.val)) {
LongList = LongList.next;
ShortList = ShortList.next;
}
return LongList;
}
private int GetLengthOfList(ListNode pHead) {
ListNode p = pHead;
int count = 0;
while (p != null) {
count++;
p=p.next;
}
return count;
}
}
37. 정렬 배열 에 나타 난 숫자
제목 설명
정렬 배열 에 나타 난 숫자 를 집계 합 니 다.
생각:
정렬 배열 을 보고 2 분 검색 을 고려 합 니 다. 여 기 는 주로 첫 번 째 로 이 숫자 가 나타 난 위치 와 마지막 으로 이 숫자 가 나타 난 위 치 를 찾 은 다음 에 개 수 를 계산 하면 됩 니 다.
알고리즘 구현
class Solution37 {
public int GetNumberOfK(int [] array , int k) {//
int count=0;
if(array!=null&&array.length>0) {
int first=GetFirstK(array,k,0,array.length-1);
int last=GetLastK(array,k,0,array.length-1);
if(first>-1&&last>-1) {
count=last-first+1;
}
}
return count;
}
private int GetLastK(int[] array, int k, int start, int end) {
if(start>end) {
return -1;
}
int midIndex = (start+end)/2;
int middle = array[midIndex];
if(middle==k) {
if((midIndexk) {
end = midIndex-1;
}else {
start = midIndex+1;
}
return GetLastK(array,k,start,end);
}
private int GetFirstK(int[] array, int k, int start, int end) {
if(start>end) {
return -1;
}
int midIndex = (start+end)/2;
int middle = array[midIndex];
if(middle==k) {
if((midIndex>start && array[midIndex-1]!=k) || midIndex==start) {
return midIndex;
}
else {
end = midIndex-1;
}
}else if(middle>k) {
end = midIndex-1;
}else {
start = midIndex+1;
}
return GetFirstK(array,k,start,end);
}
}
38. 이 진 트 리 의 깊이
제목 설명
이 진 트 리 의 깊이 를 구 하려 면 이 진 트 리 를 입력 하 십시오.뿌리 결점 에서 잎 결점 까지 순서대로 지나 가 는 결점 (뿌리, 잎 결점 포함) 은 나무의 한 경 로 를 형성 하고 가장 긴 경로 의 길 이 는 나무의 깊이 이다.
생각:
되돌리다.
알고리즘 구현
class Solution38 {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return TreeDepth(root.left) > TreeDepth(root.right) ? TreeDepth(root.left) + 1 : TreeDepth(root.right) + 1;
}
}
39. 밸 런 스 이 진 트 리
제목 설명
이 진 트 리 를 입력 하여 이 진 트 리 가 균형 이 잡 힌 이 진 트 리 인지 판단 하 십시오.
생각:
좌우 하위 트 리 의 높이 가 같 는 지 판단 하고, 뒤 를 옮 겨 다 니 며, 옮 겨 다 니 는 것 을 판단 하면 된다.
알고리즘 구현
class Solution39 {
boolean balanced=true;
public boolean IsBalanced_Solution(TreeNode root) {
IsBalanced(root);
return balanced;
}
private int IsBalanced(TreeNode root) {
if(root==null) {
return 0;
}
int left=IsBalanced(root.left);
int right=IsBalanced(root.right);
if(Math.abs(left-right)>1) {
balanced=false;
}
return left>right?left+1:right+1;
}
}
40. 배열 에 한 번 만 나타 나 는 수
제목 설명
하나의 정형 배열 에 두 개의 숫자 를 제외 하고 다른 숫자 는 모두 두 번 나 타 났 다.프로그램 을 써 서 이 두 개의 한 번 만 나타 나 는 숫자 를 찾 아 보 세 요.
생각:
알고리즘 구현
class Solution40 {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int a=0;
for(int i = 0;i좋은 웹페이지 즐겨찾기
