검지 offer (31 --- 40)
1 에서 13 의 정수 중 1 이 나타 나 는 횟수 를 구하 고 100 에서 1300 의 정수 중 1 이 나타 나 는 횟수 를 계산 합 니까?이 를 위해 그 는 1 ~ 13 에 1 이 포 함 된 숫자 가 1, 10, 11, 12, 13 이 라 고 특별히 세 어 보 았 지만 뒤의 문제 에 대해 서 는 어 쩔 수 없 었 다.ACMer 는 여러분 이 그 를 도와 주 고 문 제 를 더욱 보편화 시 켜 서 임의의 부정 정수 구간 에서 1 이 나타 나 는 횟수 (1 에서 n 에서 1 이 나타 나 는 횟수) 를 빨리 구 할 수 있 기 를 바 랍 니 다.
이 문 제 를 얻 으 면 시간 효율 을 고려 하지 않 는 방법, 즉 모든 숫자 중 1 의 개 수 를 통계 하고 매번 정수 에 대해 나머지 를 취 하 는 방식 으로 한 자리 가 1 인지 아 닌 지 를 판단 할 수 있다. 만약 에 이 수가 10 보다 많 으 면 10 을 나 눈 후에 한 자리 가 1 인지 아 닌 지 를 판단 해 야 한다. 그러나 이런 방법 은 연산 효율 이 높 지 않 기 때문에 우 리 는 효율 이 비교적 높 은 알고리즘 을 고려 해 야 한다.사실 우 리 는 규칙 을 찾 을 수 있다. 예 를 들 어 우 리 는 한 수의 백 자 리 를 예 로 들 면 이때 우 리 는 백 자 리 를 0 으로 고려 할 수 있다. 만약 에 이때 n 이 12014 라면 그의 백 자 리 는 1 이 더 높 은 위치 와 관련 이 있 고 그의 백 자 리 는 1 인 상황 은 100 에서 199, 1100 에서 1199, 2100 에서 2199, 3100 에서 3199 이다.11100 에서 11199 까지 모두 1200 개가 있 는데 그것 이 바로 더 높 은 숫자 (12) 에 현재 자릿수 (100) 를 곱 하 는 것 이다.이때 우 리 는 백 위 가 1 이라는 것 을 고려 했다. 만약 에 이때 n 이 12114 이 고 그의 백 위 는 1 이 더 높 은 위치 와 낮은 위치 와 관련 이 있다. 그의 백 위 가 1 인 상황 은 100 에서 199, 1100 에서 1199, 2100 에서 2199, 3100 에서 3199 이다.11100 에서 11199 까지 이 때 는 12 * 100 개, 그리고 12100 에서 12114 개 입 니 다. 이 때 는 115 개 로 모두 더 높 은 숫자 (12) * 현재 자릿수 + 낮은 숫자 (114) + 1 = 1315 개 입 니 다.이때 우 리 는 백 자리 숫자 가 1 보다 크다 는 것 을 고려 했다. 이때 n 이 12314 이면 백 자리 가 1 이 고 더 높 은 자리 와 관련 이 있다. 그의 백 자리 가 1 인 경 우 는 100 에서 199, 1100 에서 1199, 2100 에서 2199, 3100 에서 3199 이다.11100 에서 11199, 12100 에서 12199 까지 모두 1300 개, 즉 더 높 은 위치 (12) + 1 에 현재 자릿수 100 을 곱 합 니 다.이때 우 리 는 코드 를 실현 합 니 다. 코드 에서 i 는 정수 점 이 위치 점 을 대표 합 니 다. 즉, 1 은 개 위 치 를 대표 하고 10 은 10 위 를 대표 합 니 다.
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
int count=0;// 1
int i=1;//
while(n/i)
{
int before=n/i/10;//
int after=n%i;//
int cur=(n/i)%10;// ， 0,1， 1
if(cur==0)
count+=before*i;
else if(cur==1)
count+=before*i+after+1;
else
count+=(before+1)*i;
i*=10;
}
return count;
}
};
32. 배열 을 가장 작은 수로 배열 한다.
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
마지막 으로 돌아 온 결 과 는 문자열 이기 때문에 배열 의 모든 요 소 를 문자열 형식 으로 바 꾸 는 것 을 고려 해 야 합 니 다. to 를 사용 하 십시오.string 함 수 는 최소 숫자 로 배열 해 야 하기 때문에 예 를 들 어 a = 2, b = 21 로 각각 문자열 로 전환 한 후에 a + b 는 221, b + a 는 212, 즉 b + a
class Solution { private: static bool cmp (int a, int b) / / 정의 비교 규칙, 예 를 들 어 a = 2, b = 21, 둘 다 문자열 로 바 뀌 었 습 니 다. a + b 는 221 이 고 b + a 는 212 이 며 b + a 는 앞 에 있어 야 합 니 다. a + b 는 뒤에 있 습 니 다. { string before = "; / / 저장 a + b string after = "; / / 저장 b + a before+=to_string(a); before+=to_string(b); after+=to_string(b); after+=to_string(a); return before numbers) { string result=""; if(numbers.empty()) return result; / / numbers 의 요 소 를 cmp 가 정의 하 는 규칙 에 따라 정렬 하고 순 서 를 정렬 한 후 처음부터 문자열 로 조합 하면 결과 입 니 다. sort(numbers.begin(),numbers.end(),cmp); for(int i=0;i
33、丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
我们拿到这个题，第一就是想到先实现一个判断丑数的方法，然后逐个数进行判断，找到第index个丑数即可，但是这种方法效率很低，因为是逐个判断每个数，因此要考虑另一种算法，也就是定义一个数组存放排序的丑数，一个数是丑数，那么它*2、3、5的结果都是丑数，此时这个数组中最大的丑数为M，要生成下一个丑数，就是这个数组中某一个丑数2、3、5的结果，若将每一个丑数都2，可能有小于M的一些丑数，因为数组中已经存在这些丑数（因为数组是排序的），就忽略，也会有大于M的一些丑数，在这里面第一个大于M的数的下标记为M2，同时关于3和5的情况也和上述一样，得到M3和M5，最后求M2、M3、M5代表的元素最小的即可。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<7)//1---6
return index;
vector arr(index);// ， index
arr[0]=1;// 1
int m2=0,m3=0,m5=0;
for(int i=1;i 34. 첫 번 째 한 번 만 나타 나 는 문자
한 문자열 (0 < = 문자열 길이 < = 10000, 모두 알파벳 으로 구성) 에서 첫 번 째 로 한 번 만 나타 나 는 문 자 를 찾 아 그 위 치 를 되 돌려 줍 니 다. 없 으 면 - 1 (대소 문 자 를 구분 해 야 합 니 다) 을 되 돌려 줍 니 다. (0 부터 계산 합 니 다)
여기 서 해시 의 사상 을 사용 하여 모든 문자 가 나타 나 는 횟수 를 통계 하고 하나의 용 기 를 사용 하여 해당 위치 에 저장 한 다음 에 이 용 기 를 옮 겨 다 니 며 어느 횟수 가 1 이면 다음 표 시 를 되 돌려 주면 됩 니 다.
class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(str.empty())
return -1;
unordered_map m;
for(int i=0;i 35. 배열 의 역순 대
배열 에 있 는 두 개의 숫자 가 앞의 숫자 가 뒤의 숫자 보다 크 면 이 두 개의 숫자 는 하나의 역순 대 를 구성한다.배열 을 입력 하여 이 배열 의 역순 쌍 의 총 P 를 구하 십시오.그리고 P 를 1000000007 모드 로 출력 합 니 다.출력 P% 1000000007
이 문 제 를 받 으 면 가장 먼저 생각 나 는 것 은 배열 을 옮 겨 다 니 는 것 입 니 다. 현재 요 소 는 뒤의 모든 요소 에 비해 마지막 에 역순 을 맞 추 면 됩 니 다. 그러나 이런 방법 은 그의 시간 복잡 도 는 O (n ^ 2) 입 니 다. 효율 을 높이 기 위해 여기 서 우 리 는 병합 정렬 사상 을 사용 하여 공간 으로 시간 을 바 꾸 는 것 입 니 다. 즉, 7, 5, 4, 6 입 니 다. 우 리 는 이 를 75 와 4, 6 으로 나 눈 다음 에 진행 합 니 다.(1) 75 역순 대 (여기 서 재 귀 방식 으로 이 하위 배열 의 역순 대 를 구 하 는 것) 7 > 5, 한 쌍 이 있 습 니 다. (2) 46 역순 대 (또한 재 귀 방식 으로 이 하위 배열 의 역순 대 를 구 하 는 것) 6 > 4, 한 쌍 이 있 습 니 다. (3) 75 와 46 은 각각 5, 7, 4, 6 으로 정렬 되 어 있 습 니 다. (4)두 개의 지침 을 설정 하여 각각 두 개의 하위 배열 의 최대 치 를 가리 키 고 i 는 7, j 는 6 을 가리 키 며 (5) i 와 j 가 가리 키 는 값 을 비교 합 니 다. 만약 에 array [i] > array [j] 가 가리 키 는 것 은 현재 하위 배열 의 최대 치 이기 때문에 이 하위 배열 은 몇 개의 요소 가 있 습 니 다. array [i] 와 몇 쌍 의 역순 쌍 이 있 습 니 다 (현재 두 개의 요소 가 4, 6, 역순 대 2 가 있 으 면 이때 역순 대 는 모두 2 + 2 = 4)., 7 > 6 을 비교 한 후에 i 가 가리 키 는 값 을 보조 배열 에 넣 고 i 는 5 까지 한 걸음 앞으로 갑 니 다. 이때 보조 배열 에 요소 7 이 있 습 니 다. (6) i 와 j 가 가리 키 는 값 을 판단 하고 array [i] (7) 는 array [i] 와 array [j] 를 판단 합 니 다.5 > 4. 두 번 째 키 배열 에 하나의 요소 만 있 기 때문에 역순 대 + 1, 즉 4 + 1 = 5 쌍 으로 5 를 보조 배열 에 넣 고 첫 번 째 키 배열 을 옮 겨 다 니 며 두 번 째 는 4 만 남 고 4 를 보조 배열 에 넣 어 끝 냅 니 다.
class Solution {
public:
int InversePairs(vector data) {
if(data.size()<=1)
return 0;// 1 ， 0
int* ret=new int[data.size()];
// ， ，
for(unsigned int i=0;i& data,int*& ret,int start,int end)
{
if(start==end)
{
ret[start]=data[start];
return 0;
}
// ，
int length=(end-start)/2;
//
int leftcount=MergeSort(data,ret,start,start+length)%1000000007;
int rightcount=MergeSort(data,ret,start+length+1,end)%1000000007;
//
int i=start+length;//
int j=end;//
int index=end;// ，
int count=0;
while(i>=start && j>=start+length+1)// ， i start，j start+length+1
{
if(data[i]>data[j])
{
ret[index--]=data[i--];
//
count+=j-start-length;
if(count>=1000000007)//
count%=1000000007;
}
else
{
ret[index--]=data[j--];
}
}
for(;i>=start;--i)
{
ret[index--]=data[i];
}
for(;j>=start+length+1;--j)
{
ret[index--]=data[j];
}
//
for(int i=start; i<=end; i++) {
data[i] = ret[i];
}
//
return (count+leftcount+rightcount)%1000000007;
}
};
36. 두 개의 링크 의 첫 번 째 공공 노드
두 개의 링크 를 입력 하여 첫 번 째 공공 노드 를 찾 아 보 세 요.
만약 에 공공 결점 이 있 으 면 그 뒤에 공공 꼬리 부분 을 사용 하 는 것 을 설명 한다. 먼저 두 개의 링크 의 길이, 어느 링크 의 길 이 를 계산 하고 어느 링크 부터 그들 이 서로 줄 어 든 크기 를 걷 는 다음 에 둘 이 같이 가면 똑 같은 노드 를 만 나 돌아 올 때 까지 가면 된다.
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
private:
int GetLength(ListNode* head)
{
if(head==nullptr)
return 0;
ListNode* pCur=head;
int sum=0;
while(pCur)
{
sum++;
pCur=pCur->next;
}
return sum;
}
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
int len1=GetLength(pHead1);
int len2=GetLength(pHead2);
if(len1>len2)
{
for(int i=0;inext;
}
}
else
{
for(int i=0;inext;
}
}
while(pHead1!=nullptr)
{
if(pHead1==pHead2)
return pHead1;
pHead1=pHead1->next;
pHead2=pHead2->next;
}
return nullptr;
}
};
37. 숫자 가 정렬 배열 에 나타 난 횟수
정렬 배열 에 나타 난 숫자 를 집계 합 니 다.
먼저 우 리 는 그 가 정렬 배열 이라는 것 을 알 고 있 기 때문에 2 분 동안 찾 을 수 있다. 만약 에 하나의 요소 가 중복 되면 반드시 연속 적 으로 나타 날 것 이다 (정렬 배열 이기 때문이다)따라서 어떤 숫자 가 나타 나 는 횟수 를 알 고 싶다 면 그 가 처음 나타 난 하 표 와 마지막 에 나타 난 하 표를 알 아야 한다. 그러면 처음으로 나타 난 k 와 마지막 에 나타 난 k 의 함 수 를 각각 쓸 수 있다. 예 를 들 어 k 가 처음 나타 난 하 표를 알 아야 한다. 우 리 는 start 와 end 를 정의 하고 매번 mid 를 구 할 수 있다. 만약 에 이때 mid 가 가리 키 는 값 이 k 가 아니라면 두 번 째 로 해 야 한다.검색 방법 을 나 누 어 k 를 찾 습 니 다. 즉, arr [mid] 가 k 보다 크 면 end 를 mid - 1 로 갑 니 다. arr [mid] end 가 끝나 면 - 1 로 돌아 갑 니 다. 물론 마지막 으로 나타 난 k 의 하 표를 얻 는 것 도 이런 사상 입 니 다. 우리 주 함수 에서 첫 번 째 와 마지막 으로 k 가 나타 난 하 표를 얻 은 다음 에 마지막 - 첫 번 째 + 1 은 k 가 나타 난 횟수 입 니 다.
class Solution {
private:
int GetFirstK(vector data,int k,int start,int end)
{
int length=data.size();
int mid = (start+end)>>1;
while(start <= end)
{
if(data[mid]>k)
{
end=mid-1;
}
// k
else if(data[mid]= 0 && data[mid-1] == k)
end = mid-1;
else
return mid;
mid=(start+end)>>1;
}
return -1;
}
int GetLastK(vector data,int k,int start,int end)
{
int length = data.size();
int mid = (start + end) >> 1;
while(start <= end)
{
if(data[mid] > k)
{
end = mid-1;
}
else if(data[mid] < k){
start = mid+1;
}
else if(mid+1 < length && data[mid+1] == k){
start = mid+1;
}
else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
public:
int GetNumberOfK(vector data ,int k) {
int len=data.size();
if(len==0)
return 0;
int count=0;
int first=GetFirstK(data,k, 0,data.size()-1);
int last=GetLastK(data,k, 0,data.size()-1);
if(first!=-1 && last!=-1)
return last-first+1;
return 0;
}
};
38. 이 진 트 리 의 깊이
이 진 트 리 를 입력 하여 이 나무의 깊이 를 구하 십시오. 뿌리 결산 점 에서 잎 결산 점 까지 순서대로 지나 가 는 결산 점 (뿌리, 잎 결산 점 포함) 은 나무의 경 로 를 형성 하고 가장 긴 경로 의 길 이 는 나무의 깊이 입 니 다.
뿌리 노드 가 비어 있 으 면 0 (이것 도 재 귀 종료 조건) 으로 돌아 갑 니 다. 그렇지 않 으 면 왼쪽 나무 에 가서 높이 를 계산 하고 오른쪽 나무 에 가서 높이 (재 귀) 를 계산 한 다음 에 높 은 나무 높이 + 1 로 돌아 가면 됩 니 다.
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==nullptr)
return 0;
int leftDepth=TreeDepth(pRoot->left);
int rightDepth=TreeDepth(pRoot->right);
return leftDepth>rightDepth ? leftDepth+1 : rightDepth+1;
}
};
39. 밸 런 스 이 진 트 리
1 과 나무 가 균형 이 잡 힌 이 진 트 리 인지 아 닌 지 를 판단 하 는 것 입 니 다. 우리 가 가장 먼저 생각 하 는 방법 은 좌우 나무의 높이 를 계산 한 다음 에 그 높이 가 떨 어 지 는 절대 치 < = 1 인지 확인 한 다음 에 좌우 나무 가 모두 균형 을 이 룰 때 균형 을 잡 는 것 입 니 다. 그러나 이런 방법 은 우 리 는 같은 결점 을 반복 해서 옮 겨 다 닙 니 다. 높이 를 계산 할 때 해당 하 는 결점 을 옮 겨 다 니 고 균형 을 판단 할 때 또이러한 노드 를 옮 겨 다 니 기 때문에 우 리 는 다른 더욱 간편 한 알고리즘 을 생각해 야 한다. 우 리 는 뒤의 순서 로 옮 겨 다 닐 수 있다. 그러면 같은 결점 을 반복 하지 않 는 다. 즉, 균형 을 판단 하면 서 현재 의 이 진 트 리 의 높이 를 저장 하고 반복 하지 않 아 도 된다. 특정한 결점 을 옮 겨 다 니 는 좌우 아 이 를 옮 겨 다 닌 후에 높이 에 따라 균형 을 판단 하고 코드 를 실현 한다.
class Solution {
private:
bool _IsBalanced_Solution(TreeNode* pRoot,int* pDepth)//
{
if(pRoot==nullptr)
{
*pDepth=0;
return true;
}
int leftDepth;
int rightDepth;//
if(_IsBalanced_Solution(pRoot->left,&leftDepth) && _IsBalanced_Solution(pRoot->right,&rightDepth))//
// ，
{
int diff=leftDepth-rightDepth;
if(diff<=1 && diff>=-1)
{
*pDepth=leftDepth>rightDepth? leftDepth+1:rightDepth+1;
return true;
}
}
return false;
}
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
int depth=0;
return _IsBalanced_Solution(pRoot,&depth);
}
};
40. 배열 에 한 번 만 나타 나 는 숫자
하나의 전체 배열 에 두 개의 숫자 를 제외 하고 다른 숫자 는 모두 두 번 나 타 났 습 니 다. 프로그램 을 써 서 이 두 개의 한 번 만 나 오 는 숫자 를 찾 아 보 세 요.
이 문제 에 부 딪 히 면 우 리 는 먼저 간단 한 상황 을 생각해 볼 수 있다. 바로 하나의 성형 배열 에서 하나의 숫자 를 제외 하고 다른 숫자 가 두 번 나 타 났 다. 프로그램 을 써 서 이 한 번 만 나타 난 숫자 를 찾 아 낼 수 있다. 이런 문 제 는 해결 하기 어렵 지 않다. 바로 그 어떠한 숫자 가 다 르 거나 자신 이 0, 0 이 되 거나 그 숫자 가 그 숫자 와 같 기 때문에 우 리 는 순서대로 다 를 수 있다.또는 배열 의 모든 숫자, 마지막 결 과 는 바로 찾 아야 할 그 숫자 입 니 다. 그러면 똑 같은 이치 로 우 리 는 이런 사상 으로 이 문 제 를 해결 할 수 있 습 니 다. 바로 배열 을 두 개의 배열 로 나 눈 다음 에 찾 아야 할 두 개의 숫자 를 각각 한 개의 배열 에 두 는 것 입 니 다. 그러면 문 제 는 이 두 개의 숫자 를 어떻게 두 개의 배열 에 두 느 냐 에 있 습 니 다. 여기 서도 우 리 는 할 수 있 습 니 다.다른 방법 을 사용한다. 즉, 우 리 는 배열 의 모든 수 를 차례대로 다 르 게 하거나 최종 적 으로 얻 은 결 과 는 바로 찾 아야 할 두 개의 수 나 결과 (다른 수 는 모두 두 번 나 타 났 기 때문에 모두 다 르 거나 떨 어 졌 다) 이다. 그러면 우 리 는 이 결과 의 2 진법 의 한 사람 이 1 인지 에 따라 두 수 를 각각 한 개의 키 배열 에 있 게 할 수 있다.(한 분 이 1 이 므 로 이 두 개의 수 를 나타 내 는 한 분 은 반드시 0 이 고 하 나 는 1 이 므 로 구분 할 수 있 습 니 다) 그 한 분 의 이 진 위 는 1 의 수 를 첫 번 째 키 배열 에 놓 고 그 한 분 의 이 진 위 는 0 의 수 를 두 번 째 키 배열 에 놓 을 수 있 습 니 다.(두 번 나 오 는 수 는 반드시 한 개의 키 배열 에 있 습 니 다. 왜냐하면 그들 한 명의 바 이 너 리 는 반드시 같 거나 모두 1 이거 나 모두 0 이기 때 문 입 니 다) 그리고 두 개의 키 배열 은 각각 다른 순서 로 이동 하거나 이 두 개의 수 를 얻 을 수 있 습 니 다. 실현 코드:
class Solution {
private:
unsigned int FindFirstBit1(int num)// num 1， index
{
unsigned int index=0;
while(((num&1)==0) && (index < 8*sizeof(int)))// 1， index 32
{
index++;
num = num>>1;
}
return index;
}
private:
bool Isbit1(int num,unsigned int index)// num index 1
{
num = num>>index;
return (num&1);
}
public:
void FindNumsAppearOnce(vector data,int* num1,int *num2) {
if(data.size()==0 || data.size() <2)
return;
int ret=0;// ，
//
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
