20. 값을 나타내는 문자열

21. 수조의 순서를 조정하여 홀수가 짝수 앞에 있게 하다

22. 체인 테이블의 마지막 K번째 결점

23. 체인 시계의 고리의 입구 결점

24. 체인 테이블을 반전합니다

25. 두 개의 정렬된 체인 테이블을 합치다

26. 나무의 자 구조

27. 두 갈래 나무의 거울

28 대칭의 두 갈래 나무

29. 시계 방향으로 행렬을 인쇄하다

20. 값을 나타내는 문자열

NowCoder

제목 설명

true

"+100"
"5e2"
"-123"
"3.1416"
"-1E-16"

false

"12e"
"1a3.14"
"1.2.3"
"+-5"
"12e+4.3"

문제 풀이 사고방식

정규 표현식을 사용하여 일치합니다.

[]  ：  
()  ：  
?   ：   0 ~ 1  
+   ：   1 ~ n  
*   ：   0 ~ n  
.   ：  
\\. ：   .
\\d ：  

public boolean isNumeric(char[] str) {
    if (str == null || str.length == 0) return false; return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?"); }

21. 수조의 순서를 조정하여 홀수를 짝수 앞에 두다

NowCoder

제목 설명

홀수와 홀수, 짝수와 짝수 사이의 상대적인 위치가 변하지 않도록 보증해야 하는데 이것은 책과 그다지 같지 않다.
 

문제 풀이 사고방식

방법1: 시간 복잡도 O(N), 공간 복잡도 O(N)를 위한 새 그룹을 만듭니다.

public void reOrderArray(int[] nums) {
    //  
    int oddCnt = 0; for (int x : nums) if (!isEven(x)) oddCnt++; int[] copy = nums.clone(); int i = 0, j = oddCnt; for (int num : copy) { if (num % 2 == 1) nums[i++] = num; else nums[j++] = num; } } private boolean isEven(int x) { return x % 2 == 0; }

방법2: 거품 사상을 사용하여 매번 현재 짝수가 현재 맨 오른쪽으로 올라간다.시간 복잡도 O(N2), 공간 복잡도 O(1), 시간 교환 공간.

public void reOrderArray(int[] nums) {
    int N = nums.length; for (int i = N - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (isEven(nums[j]) && !isEven(nums[j + 1])) { swap(nums, j, j + 1); } } } } private boolean isEven(int x) { return x % 2 == 0; } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }

22. 체인 테이블의 마지막 K 결점

NowCoder

문제 풀이 사고방식

체인 테이블의 길이는 N입니다.두 개의 포인터 P1과 P2를 설정하고 P1이 먼저 K 노드를 이동하도록 하면 N - K 노드가 이동할 수 있습니다.이때 P1과 P2를 동시에 이동시키면 P1이 체인 테이블의 끝으로 이동할 때 P2는 N-K 노드로 이동합니다. 이 위치가 바로 꼴찌의 K 노드입니다.
 

public ListNode FindKthToTail(ListNode head, int k) {
    if (head == null) return null; ListNode P1 = head; while (P1 != null && k-- > 0) P1 = P1.next; if (k > 0) return null; ListNode P2 = head; while (P1 != null) { P1 = P1.next; P2 = P2.next; } return P2; }

23. 체인 시계 중환의 입구 결점

NowCoder

제목 설명

하나의 체인 테이블에 고리가 포함되어 있습니다. 이 체인 시계의 고리의 입구 결점을 찾으십시오.추가 공간을 사용할 수 없음을 요구합니다.

문제 풀이 사고방식

두 개의 바늘을 사용합니다. 한 개의 바늘fast는 두 개의 노드를 이동하고, 한 개의 바늘slow는 한 개의 노드를 이동합니다.링이 존재하기 때문에 두 바늘은 반드시 링 중의 어느 노드에서 만난다.만약에 만남점이 아래 그림의 z1 위치에 있다고 가정하면 이때fast가 이동하는 노드 수는 x+2y+z이고 slow는 x+y이며 fast속도는 slow보다 배 빠르기 때문에 x+2y+z=2(x+y)를 얻어 x=z를 얻는다.
만남점에서 슬로우가 링의 입구점까지 z개의 노드를 이동해야 한다.fast가 다시 처음부터 이동하고 속도가 매번 하나의 노드로 변하면 링 입구점까지 x개의 노드를 이동해야 한다.위에서 x=z를 유도했기 때문에fast와 slow는 링 입구점에서 만날 것이다.
 

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null) return null; ListNode slow = pHead, fast = pHead; do { fast = fast.next.next; slow = slow.next; } while (slow != fast); fast = pHead; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }

24. 체인 테이블 반전

NowCoder

문제 풀이 사고방식

차례로 돌아가다

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) return head; ListNode next = head.next; head.next = null; ListNode newHead = ReverseList(next); next.next = head; return newHead; }

교체하다

헤드 플러그를 사용하다.

public ListNode ReverseList(ListNode head) {
    ListNode newList = new ListNode(-1); while (head != null) { ListNode next = head.next; head.next = newList.next; newList.next = head; head = next; } return newList.next; }

25. 두 개의 정렬을 합친 체인 테이블

NowCoder

제목 설명

 

문제 풀이 사고방식

차례로 돌아가다

public ListNode Merge(ListNode list1, ListNode list2) {
    if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= list2.val) { list1.next = Merge(list1.next, list2); return list1; } else { list2.next = Merge(list1, list2.next); return list2; } }

교체하다

public ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1); ListNode cur = head; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null) cur.next = list1; if (list2 != null) cur.next = list2; return head.next; }

26. 나무의 자구조

NowCoder

제목 설명

 

문제 풀이 사고방식

public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) return false; return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) { if (root2 == null) return true; if (root1 == null) return false; if (root1.val != root2.val) return false; return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right); }

27. 두 갈래 나무의 거울

NowCoder

제목 설명

 

문제 풀이 사고방식

public void Mirror(TreeNode root) {
    if (root == null) return; swap(root); Mirror(root.left); Mirror(root.right); } private void swap(TreeNode root) { TreeNode t = root.left; root.left = root.right; root.right = t; }

28 대칭의 두 갈래 나무

NowCoder

제목 설명

 

문제 풀이 사고방식

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null)
        return true; return isSymmetrical(pRoot.left, pRoot.right); } boolean isSymmetrical(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left); }

29. 시계 방향으로 행렬 인쇄

NowCoder

제목 설명

다음 그림의 행렬은 시계 방향으로 인쇄된 결과: 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
 

문제 풀이 사고방식

public ArrayList<Integer> printMatrix(int[][] matrix) {
    ArrayList<Integer> ret = new ArrayList<>(); int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1; while (r1 <= r2 && c1 <= c2) { for (int i = c1; i <= c2; i++) ret.add(matrix[r1][i]); for (int i = r1 + 1; i <= r2; i++) ret.add(matrix[i][c2]); if (r1 != r2) for (int i = c2 - 1; i >= c1; i--) ret.add(matrix[r2][i]); if (c1 != c2) for (int i = r2 - 1; i > r1; i--) ret.add(matrix[i][c1]); r1++; r2--; c1++; c2--; } return ret; }

다음으로 전송:https://www.cnblogs.com/daimasanjiaomao/p/11009020.html