검 지 offer 알고리즘 문제 분석 및 정리 (5)

다음은 제 가 검 지 를 칠 할 때 제 가 한 것 과 인터넷 의 신 이 한 여러 가지 사고 와 답 을 정리 하 겠 습 니 다. 자신의 코드 는 사고 1 로 네티즌 의 코드 를 통 해 출처 링크 를 제공 할 수 있 도록 보장 합 니 다.
목차

1. 동그라미 중 마지막 남 은 숫자 (조세 프 링)

2. 대칭 적 인 이 진 트 리

3. 이 진 트 리 를 여러 줄 로 인쇄

4. 좌회전 문자열

5. 링크 의 고리

6. 부동 소수점 의 정수 제곱

7. min 함 수 를 포함 한 스 택

8. 회전 배열 의 최소 숫자

9. 두 개의 링크 의 첫 번 째 공공 노드

10. 1 부터 N 정수 까지 1 이 나타 나 는 횟수

1. 동그라미 중 마지막 남 은 숫자 (조세 프 링)
n 개의 숫자 (0, 1,..., n - 1) 는 하나의 원 을 형성 하고 숫자 0 부터 매번 이 원 에서 m 번 째 숫자 (첫 번 째 는 현재 숫자 자체 이 고 두 번 째 는 현재 숫자의 다음 숫자) 를 삭제 합 니 다.한 숫자 가 삭제 되면 삭 제 된 숫자의 다음 숫자 에서 m 번 째 숫자 를 계속 삭제 합 니 다.이 동그라미 에 남 은 마지막 숫자 를 구하 세 요.사고방식 1: 수조 시 뮬 레이 션 링 으로

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        boolean[] flag=new boolean[n];//         
        int alive=n-1;
        int index=0;
        int c=0;
        while(alive>0){
            while(c!=m){
                if(!flag[index]){c++;}//        
                if(index+1==n)index=0;
                else index++;
            }
            //        true
            if(index==0)flag[n-1]=true;
            else flag[index-1]=true;
            alive--;
            c=0;
        }
        for(int i=0;iif(!flag[i])return i;
        }
        return -1;
    }
}

배열 이 후기 까지 표 시 를 하면 쓸데없는 판단 이 많 습 니 다. 삭제 로 표 시 된 경우 가 많아 서 좋 지 않 습 니 다.
사고 2: 링크 로 시 뮬 레이 션 을 하고 진정한 삭제, 시간 과 공간 복잡 도 는 모두 O (n) O (n) 는 우 객 망 에서 온 것 입 니 다 @ 1 신 입 니 다.

import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        LinkedList list = new LinkedList();
        for (int i = 0; i < n; i ++) {
            list.add(i);
        }

        int bt = 0;
        while (list.size() > 1) {
            bt = (bt + m - 1) % list.size();
            list.remove(bt);
        }

        return list.size() == 1 ? list.get(0) : -1;
    }
}

사고방식 3: 추이 공식 을 내놓다.A 라운드 설정: n 개인 에서 m - 1 로 표 시 된 수 를 삭제 하고 다음 라운드 B: m 로 표 시 된 수 아래 표 시 를 0 으로 기록 하고 다시 삭제 합 니 다. B 라운드 부터 마지막 으로 남 긴 수 아래 표 시 는 x 라 고 가정 하면 이 수 는 A 라운드 에서 이 수의 아래 표 시 는 (x + m)% n B - A 입 니 다.
0 - m 1 - m + 1 2 - m + 2 ~ ~ ~ n - m - 1 - n - m - 0 n - m + 1 - 1 ~ n - 2 - m - 2 n - 1 - m - 1 (A 에서 B 까지 삭제)
그래서 마지막 라 운 드 는 한 사람 만 의 게임 이 고 0 을 남 겼 습 니 다. 그러면 마지막 2 라 운 드 는 두 사람의 게임 이 있 습 니 다. 남 은 것 은 (0 + m)% 2,... 그리고 n 명의 게임 이 있 을 때 까지 계산 합 니 다.

public class Solution {
    public int LastRemaining_Solution(int n,int m) {
        if(n==0) return -1;

       int s=0;
       for(int i=2;i<=n;i++){
           s=(s+m)%i;
       }
       return s;
    }
}

2. 대칭 적 인 이 진 트 리
하나의 함 수 를 실현 하여 이 진 트 리 가 대칭 적 인지 아 닌 지 를 판단 하 십시오.이 진 트 리 가 이 진 트 리 의 거울 과 같다 면 대칭 으로 정의 합 니 다.
사고 1: 층 차 를 옮 겨 다 니 며 각 층 의 판단 서열 이 대칭 적 인지, 하위 노드 가 비어 있 으 면 '\ #' 로 표시 합 니 다.

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot){  
        if(pRoot==null)return true;
        Queue q=new LinkedList<>();
        StringBuffer sb=new StringBuffer();
        q.add(pRoot);
        TreeNode t;
        while(!q.isEmpty()){

            int count=q.size();

            while(count-->0){
                t=q.poll();                
                if(t.left==null){sb.append("#");}
                else{q.offer(t.left);sb.append(t.left.val);}
                if(t.right==null){sb.append("#");}
                else{q.offer(t.right);sb.append(t.right.val);}
            }
            String s=sb.toString();
            sb=new StringBuffer();
            int m=0,n=s.length()-1;
            while(mif(s.charAt(m)!=s.charAt(n))return false;
                m++;n--;
            }
        }
    return true;
    }
}

뿌리 노드 의 좌우 나 무 를 두 개의 나무 로 보고 이 두 나 무 를 동시에 옮 겨 다 니 며 (거울 에 대응 하 는 점 을 동시에 옮 겨 다 니 며) 소 객 망 에서 온 것 을 판단 합 니 다 @ CV 라 는 벽돌 을 옮 깁 니 다.

//  ，      ，      
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        queue<TreeNode*> q1,q2;
        TreeNode *left,*right;
        q1.push(root->left);
        q2.push(root->right);
        while(!q1.empty() and !q2.empty()){
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            //     
            if(NULL==left && NULL==right)
                continue;
            //      
            if(NULL==left||NULL==right)
                return false;
            if (left->val != right->val)
                return false;
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left);
        }         
        return true;         
    }
};

소 객 망

//      ，          
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot){
        stack<TreeNode*> s1,s2;
        TreeNode *p1,*p2;
        p1=p2=pRoot;
        while((!s1.empty()&&!s2.empty())||(p1!=NULL&&p2!=NULL)){
            while(p1!=NULL&&p2!=NULL){
                s1.push(p1);
                s2.push(p2);
                p1=p1->left;
                p2=p2->right;
            }
            p1=s1.top();
            s1.pop();
            p2=s2.top();
            s2.pop();
            if(p1->val!=p2->val)
                return false;
            p1=p1->right;
            p2=p2->left;
        }
        if(!s1.empty()||!s2.empty())
            return false;
        if(p1!=NULL||p2!=NULL)
            return false;
        return true;
    }
};

사고 2: 하나의 스 택 이나 대열 로 미 러 에 대응 하 는 점, 즉 하나의 쌍 을 동시에 들 어가 고 동시에 소 객 망 @ 화 과 슬 래 그 석 에서 나 옵 니 다.

//DFS
boolean isSymmetricalDFS(TreeNode pRoot){
        if(pRoot == null) return true;
        Stack s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.empty()) {
            TreeNode right = s.pop();//    
            TreeNode left = s.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //    
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }

//BFS
boolean isSymmetricalBFS(TreeNode pRoot){
        if(pRoot == null) return true;
        Queue s = new LinkedList<>();
        s.offer(pRoot.left);
        s.offer(pRoot.right);
        while(!s.isEmpty()) {
            TreeNode right = s.poll();//    
            TreeNode left = s.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //    
            s.offer(left.left);
            s.offer(right.right);
            s.offer(left.right);
            s.offer(right.left);
        }
        return true;
    }

사고방식 3: 소 객 망 @ Aurora 1

boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null)return true; 
        return f(pRoot.left,pRoot.right);
    }

    boolean f(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null)
            return true;

        if (t1 != null && t2 != null)
            return t1.val == t2.val && f(t1.left,t2.right) && f(t1.right, t2.left);

        return false;
    }

3. 이 진 트 리 를 여러 줄 로 인쇄
위 에서 아래로 두 갈래 나 무 를 층 별로 인쇄 하고 같은 층 의 결점 은 왼쪽 에서 오른쪽으로 출력 합 니 다.각 층 마다 한 줄 씩 출력 합 니 다.
사고 1: 각 층 의 노드 에 대한 계산

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    ArrayList > Print(TreeNode pRoot) {
        ArrayList > AA=new ArrayList>();
        if(pRoot==null)return AA;
        Queue q=new LinkedList<>();
        TreeNode t;

        q.offer(pRoot);
        int count,c;
        ArrayList A=new ArrayList<>();
        while(!q.isEmpty()){
            count=q.size();
            c=0;
            while(c++.peek().left!=null)q.offer(q.peek().left);
                if(q.peek().right!=null)q.offer(q.peek().right);
                A.add(q.peek().val);
                q.poll();              
            }
            //       A    ，clear  AA      
            AA.add(new ArrayList<>(A));
            A.clear();
        }
        return AA;
    }
}

사고방식 2: 소 객 망 @ spursKawhi

//     
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }

    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
        if(root == null) return;
        if(depth > list.size())//     A  ，            A 
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);

        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }
}

4. 좌회전 문자열
어 셈 블 리 언어 에는 순환 왼쪽 이동 (ROL) 이라는 위치 이동 명령 이 있 습 니 다. 현재 간단 한 작업 이 있 습 니 다. 바로 문자열 로 이 명령 의 연산 결 과 를 모 의 하 는 것 입 니 다.주어진 문자 시퀀스 S 에 대해 서 는 K 비트 를 왼쪽으로 이동 한 후의 시퀀스 를 출력 하 십시오.예 를 들 어 문자 시퀀스 S = "abc XYZdef" 는 출력 순환 이 왼쪽으로 3 자리 이동 한 후의 결과, 즉 "XYZdefabc" 를 요구 합 니 다.사고방식 1: YX = (XYT) T Y X = (X T Y T) T

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str==null||str.length()==0||n==0)return str;
        char[] chars = str.toCharArray();        
        n%=chars.length;
        reverse(chars, 0, n-1);
        reverse(chars, n, chars.length-1);
        reverse(chars, 0, chars.length-1);

        return new String(chars);
    }

    public void reverse(char[] chars,int low,int high){
        char temp;
        while(low

사고방식 2: 우 객 망 @ OutOfBounds Exception 에서 자바 와 유사 한 Collections 의 rotate 방법의 실현: Collections 의 rotate 는 두 가지 실현 이 있다.

유사 한 배열 과 같은 무 작위 방문 데이터 구조 에 대해 '전달' 사상

을 사용한다.

링크 와 유사 한 데이터 구조 에 대해 '링크 반전' 의 사상

을 사용한다.
이 문 제 는 첫 번 째 로 볼 수 있 기 때문에 전달 하 는 사상 을 사용한다.

public class Solution {
    //rotation
    public String LeftRotateString(String str,int n) {
        int len = str.length();
        if (n == 0 || len == 0) return str;
        n %= len;
        char[] ch = str.toCharArray();
        int doneCnt = 0, i = 0;
        while (doneCnt < len && i < len) {
            int j = i++;
            char cur = ch[j];//cur                  ，     ，   cur           
            while (cur != ch[j=(j-n+len)%len]) { 
                char tmp = ch[j]; ch[j] = cur; cur = tmp; //exchange
                doneCnt++;
            }
        }
        return new String(ch);
    }
}

자바 Collections 의 rotate 방법 에 대한 소스 분석
5. 링크 의 고리
링크 에 링 이 포함 되 어 있 으 면 이 링크 의 입구 점 을 찾 으 십시오. 그렇지 않 으 면 null 을 출력 합 니 다.
사고방식 1:

출발점 에서 빠 르 고 느 린 지침 으로 시작 하여 만 나 면 고리 가 있 고 그렇지 않 으 면 고리 가 없다.

만 남 점 에서 부터 계산 하고 빠 른 포인터 가 다시 만 나 는 것 (아니면 만 남 점 에서) 은 바로 고리 의 크기 이다.

하 나 는 출발점 에서 하 나 는 만 남 점 에서 같은 속도 로 운동 하고 만 나 는 곳 이 바로 입구 이다.또는 이미 알 고 있 는 링 의 크기, 두 바늘 은 동시에 출발점 에서 출발 하고 한 바늘 은 다른 먼저 가 는 링 의 크기 의 걸음 수 를 기다 리 며 다시 가면 두 바늘 이 만 나 는 것 이 바로 입구 이다.

/**
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead==null||pHead.next==null)return null;
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)break; //            
        }
        if(fast!=slow)return null;//   
        slow=pHead;
        while(fast!=slow){//      ，     ，    
            fast=fast.next;
            slow=slow.next;
        }
        return fast;        
    }
}

사고 2: 체인 끊 기 법 은 링크 구 조 를 파괴 하고 추천 하지 않 습 니 다.우 객 망 에서 왔 습 니 다 @겨울지

/**
      O（n），    ，     ，          ，   。
          ，     ，      next  NULL。
    ：         ，                   ，
         。
                   ，                 NULL，
      。
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead){
        if (!pHead->next)
            return NULL;
        ListNode* previous = pHead;
        ListNode* front = pHead ->next;
        while (front){
            previous->next = NULL;
            previous = front;
            front = front->next;
        }
        return previous;
    }
};

6. 부동 소수점 의 정수 제곱
double 형식의 부동 소수점 base 와 int 형식의 정수 exponent 를 지정 합 니 다.base 의 exponent 제곱 을 구하 다.
사고 1: 빠 른 속도

public class Solution {
    public double Power(double base, int exponent) {
        double result=1;
        int i=0;
        boolean flag=false;
        if(exponent<0){exponent=-exponent;flag=true;}
        while(i<32){
            //if((exponent&(1<
            if((exponent>>i&1)==1){
                result*=base;
            }
            i++;
            if((1<exponent)break;
            base*=base;
        }
        return  flag?1/result:result;
    }
}

위 에 제 가 엉망 으로 썼 고 base 가 0 인지 아 닌 지 판단 하지 못 했 습 니 다. 다음은 우 객 망 @ hey 독 행 에서 왔 습 니 다.

//   
   public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001)  {
            if (exponent < 0) {
                throw new RuntimeException(" 0  "); 
            }else{
                return 0.0;
            }
        }
        int e = exponent > 0 ? exponent: -exponent;
        double res = 1;
        while (e != 0) {//  0     
            res = (e & 1) != 0 ? res * base : res;
            base *= base;
            e = e >> 1;
        }
        return exponent > 0 ? res : 1/res;
  }

사고 2: 재 귀, 홀수 짝수

//    
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1.0;
        }
        if (base - 0.0 == 0.00001 || base - 0.0 == -0.00001)  {
            if (exponent < 0) {
                throw new RuntimeException(" 0  "); 
            }else{
                return 0.0;
            }
        }
        return exponent > 0 ? getPower(base, exponent) : 1/getPower(base, -exponent);
    }

    public static double getPower(double base, int e) {
        if (e == 1) {
            return base;
        }
        double halfPower = getPower(base, e >> 1);//e    ，e       （e-1）/2，e    e/2
        return (e & 1) != 0 ? base * halfPower * halfPower : halfPower * halfPower;
    }

7. min 함 수 를 포함 하 는 스 택
스 택 의 데이터 구 조 를 정의 합 니 다. 이 형식 에서 스 택 에 포 함 된 최소 요 소 를 얻 을 수 있 는 min 함수 (시간 복잡 도 는 O (1) 를 실현 하 십시오.사고방식: 공간 으로 시간 을 바 꾸 려 면 보조 창고 의 최소 수 를 저장 해 야 한다.

//             
import java.util.Stack;

public class Solution {
    Stack s=new Stack<>();
    Stack sAssist=new Stack<>();

    public void push(int node) {
        s.push(node);
        if(!sAssist.isEmpty()&&sAssist.peek()else sAssist.push(node);
    }

    public void pop() {
        s.pop();
        sAssist.pop();
    }

    public int top() {
        return s.peek();
    }

    public int min() {
        return sAssist.peek();
    }
}

스 택 에 들 어 갈 때마다 스 택 에 들 어 가 는 요소 가 min 의 스 택 꼭대기 요소 보다 작 거나 같 으 면 스 택 에 들 어 가 는 것 을 고려 합 니 다. 그렇지 않 으 면 스 택 보다 못 합 니 다.예 를 들 어 data 에서 순서대로 스 택 에 들 어 갑 니 다. 5, 4, 3, 8, 10, 11, 12, 1 은 min 이 스 택 에 들 어 갑 니 다. 5, 4, 3, no, no, no, no, no, 1. 그러나 이런 방법 은 여러 개의 중복 최소 치 를 입력 할 때 min 스 택 이 나 가면 최소 치 는 이 값 이 없습니다. 이런 방법 은 그다지 좋 지 않 습 니 다.
8. 회전 배열 의 최소 숫자
정렬 되 지 않 은 배열 의 회전 을 입력 하고 회전 배열 의 최소 요 소 를 출력 합 니 다.예 를 들 어 배열 {3, 4, 5, 1, 2} 은 {1, 2, 3, 4, 5} 의 회전 이 고 이 배열 의 최소 값 은 1 이다.NOTE: 제 시 된 모든 요 소 는 0 보다 큽 니 다. 배열 크기 가 0 이면 0 을 되 돌려 주 십시오.사고: 시비 체감 수열 에 주의 하 세 요. 중복 이 있 을 수 있 습 니 다.AB, A < = B, BA, 최소 값 이 A 부분의 첫 번 째 값 입 니 다.

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array==null||array.length==0)return 0;
        int s=0,e=array.length-1,mid;
        while(s//        array[s]~array[e]  
            mid=(s+e)/2;
            if(array[s]<array[e]){//    ，        
                return array[s];               
            }
            else if(array[s]==array[e]){//    
                if(array[mid]<array[s])e=mid;//  mid         ,  mid       ，      e=mid-1
                else if(array[mid]>array[s])s=mid+1;//  mid         ,    mid   ，s=mid+1
                else s++;//   mid           ， 22222212，22122222，         s++          
            }
            else{//    
                if(array[mid]>=array[s]){s=mid+1;}//mid       
                else{ e=mid;}
            }      
        }
         return array[s];      
    }
}

9. 두 개의 링크 의 첫 번 째 공공 노드
두 개의 링크 를 입력 하여 그들의 첫 번 째 공공 노드 를 찾 아 라.
사고 1: 처음에 제 가 생각 한 것 은 그 중의 한 체인 을 링 으로 바 꾸 고 링 의 길 이 를 알 고 다른 체인 의 출발점 부터 시작 하 는 것 입 니 다. 한 지침 은 링 의 길이 의 걸음 수 를 먼저 가 고 다른 지침 은 다시 가 는 것 입 니 다. 두 지침 이 만 나 는 곳 은 바로 링 의 입구, 즉 첫 번 째 공공 노드 입 니 다.

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p=pHead1;
        int c=1;
        while(p.next!=null){
            p=p.next;
            c++;
        }
        p.next=pHead1;
        ListNode p1=pHead2;
        ListNode p2=pHead2;
        while(c!=0){
            p1=p1.next;
            c--;
        }

        while(p1!=null){
            p1=p1.next;
            p2=p2.next;
            if(p1==p2)return p1;
        }
        return null;
    }
}

그러나 이 코드 는 순환 시간 이 초과 되 었 다 는 것 을 계속 보 여 주 었 다. 알 고 보 니 내 가 링크 의 구 조 를 바 꾸 었 다. 우 객 망 이 인쇄 한 링크 는 첫 번 째 공공 노드 부터 뒤로 고리 이기 때문에 이 링크 는 인쇄 할 수 없다.실제로 링크 구 조 를 바 꿀 필요 가 없 으 며 링 의 효 과 를 실현 하려 면 수 동 으로 포인 터 를 꼬리 에서 머리 로 뛰 면 된다.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            if(pHead1==null||pHead2==null)return null;
            ListNode p=pHead1;
            //  pHead1   ，     
            int c=1;
            while(p.next!=null){       
                p=p.next;
                c++;
            }
            //     pHead2     
            ListNode p1=pHead2;
            ListNode p2=pHead2;
            for(;c>0;c--){    //p1      ，        
                p1=p1.next==null?pHead1:p1.next;
            }
            //  p2                
            while(p2!=null){
                if(p1==p2)return p1;
                p1=p1.next==null?pHead1:p1.next;
                p2=p2.next;  
            }
        return null;
    }
}

사고방식 2: 두 개의 체인 시계의 길이 차 이 를 찾 아 라. 긴 체인 시계의 기점 부터 한 바늘 은 길이 의 차 이 를 먼저 가 고 다른 바늘 은 짧 은 체인 시계 부터 시작한다. 만 남 점 은 두 개의 체인 시계의 교점 이다.우 객 망 에서 왔 습 니 다 @ 조 진 강12. 파도 유파

public ListNode FindFirstCommonNodeII(ListNode pHead1, ListNode pHead2) {
        ListNode current1 = pHead1;//   1
        ListNode current2 = pHead2;//   2
        if (pHead1 == null || pHead2 == null)
            return null;
        int length1 = getLength(current1);
        int length2 = getLength(current2);
        //        

        //     1       2   
        if (length1 >= length2) {
            int len = length1 - length2;
            //      1，              
            while (len > 0) {
                current1 = current1.next;
                len--;
            } 
        }
        //     2       1   
        else if (length1 < length2) {
            int len = length2 - length1;
            //      1，              
            while (len > 0) {
                current2 = current2.next;
                len--;
            } 
        }
        //      ，           
        while(current1!=current2){
            current1=current1.next;
            current2=current2.next;
        }
        return current1; 
    }

    //         
    public static int getLength(ListNode pHead) {
        int length = 0;
        ListNode current = pHead;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

사고방식 3: 하나의 체인 시 계 는 AN 이 고 하 나 는 BN 이다. 하나의 지침 은 A 부터 체인 시계의 끝부분 까지 B 로 뛰 고 하나의 지침 은 B 부터 체인 시계의 끝부분 까지 A 로 뛴다. 마지막 에 교점 에서 만나면 모든 지침 은 A + B + N 의 거 리 를 걷는다.그러나 만약 두 개의 체인 시계 가 교점 이 없다 면 아래 의 순환 은 끝나 지 않 을 것 이다.소 객 망 @ selfboot 에서 왔 습 니 다.

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==NULL ? pHead2 : p1->next);
            p2 = (p2==NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};

10. 1 부터 N 까지 정수 중 1 이 나타 나 는 횟수
예 를 들 어 1 ~ 13 에 1 이 포 함 된 숫자 는 1, 10, 11, 12, 13 이다.그래서 모두 6 차례 나 나 나 왔 다.사고방식 1: 귀속

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n==0)return 0;
        int x=1;
        while(n/(10*x)!=0)x*=10;
        //x  N       ， n=134,x=100
        if(x==1)return 1;//  n 1 9
        int a=n/x;//      ， n=134，a=1
        int b=n%x;//       ， n=134，b=34
        // b    1   +a*（1 x-1   1   ）+    1   
        return f(b,x/10)+a*f(x-1,x/10)+(a>1?x:b+1);
    }
    //          x
    int f(int n,int x){
        if(n==0)return 0;
        if(x==1)return 1;
        int a=n/x;
        int b=n%x;
        //a   0
        int c;
        if(a>1)c=x;
        else if(a==1)c=b+1;
        else c=0;

        return f(b,x/10)+a*f(x-1,x/10)+c;
    }
}

사고 2: 업데이트 대기