Chapter 7 - Sword finger offer

## Topic 1

Characters that appear once for the first time

Topic Description

Find the first character that appears only once in a string (0 <= string length <= 10000, all consisting of letters) and return its position. If not, return - 1 (case sensitive).

import java.util.LinkedHashMap; public class Solution { public int FirstNotRepeatingChar(String str) { char[] p = str.toCharArray(); LinkedHashMap<Character,Integer> check = new LinkedHashMap(); int pos = -1; for(char i:p) { int count = check.getOrDefault(i,0); check.put(i,++count); } for(char i:p) { if(check.get(i)==1) return ++pos; ++pos; } return pos; } }

TreeMap was the beginning of the question, then HashMap was used, but the question was about location.

You can use TreeMap or LinkedHashMap because they are ordered tables. Here's how long they run

This is an online article about TreeMap and LinkedHashMap.

Various Map s TreeMap addition and deletion are log(N), because it is a red-black tree implementation, log(N) time adjustment tree structure, similar to heap, and LinkedHashMap is a two-way linked list, two-way linked list should be faster

Another way is to look at the comments written in C++ and write it in java. This indexOf is said to be implemented by the kmp algorithm. Of course, it's string matching. This is just to find characters, characters in every position in str. I start to look on the left side and start to look on the right side, if the positions found in these two directions are the same. Yes, that means that the character appears only once in the string.

Here's the runtime and code

It's still quite fast. Time complexity is not mistaken. It should be o(N^2).

import java.util.LinkedHashMap; public class Solution { public int FirstNotRepeatingChar(String str) { int len = str.length(); for(int i=0;i<len;++i) { char p = str.charAt(i); if(str.indexOf(p)==str.lastIndexOf(p)) return i; } return -1; } }

## Question 2

Inverse pairs in arrays

Topic Description

In an array, if the first number is larger than the last number, the two numbers form an inverse pair. Input an array to find the total number of inverse pairs in the array P. And the output of P to 1000000007 is given. That is to say, output P%1000000007

Input Description:

Topic Guarantees the same number that is not in the input array

Data range:

For% 50 data, size <=10^4 For% 75 data, size <=10^ 5 For% 100 data, size <=2*10^5

For example: 12 3 4 5 0

Because 1 > 0, 2 > 0, 3 > 0... 5 > 0, 5 is greater than 0, then return 5

The question is to find the logarithm of inverse order pairs.

Idea analysis:

Direct violence algorithm, enumeration i, enumeration j, double-loop enumeration of each number

Method 2: Merge and Sort

For example, I divide an array into two halves. The left side is ordered and the right side is ordered. I'm going to merge the two arrays.

[1,3,5,6,7,-4,-2,0,2]

We see that arr[mid] = 7, from [4,-2,0] is smaller than 1, and the reverse sequence is 3. Note that the following 3,5,6,7 must be larger than [4,-2,0], so each number in arr[l] to arr[mid] is larger than this sequence.

// a[i] > a[j], then this time, from a[i] to a[mid], it must be larger than this a[j], because at this time the two sides of the division are already in order.

public class Solution { private int P; public int InversePairs(int [] arr) { this.P=0; mergeSort(arr,0,arr.length-1); return P; } public void mergeSort(int[] arr,int l,int r) { if(r<=l) return; int m = (l+r)>>>1; mergeSort(arr,l,m); mergeSort(arr,m+1,r); merge(arr,l,m,r); } public void merge(int[] arr,int l,int m,int r) { int[] temp = new int[r-l+1]; int leftEnd=m++,rightEnd=r; r=0; while(l<=leftEnd&&m<=rightEnd) { if(arr[l]<arr[m]) temp[r++]=arr[l++]; else { P+=(leftEnd-l+1); if(P>1000000007) P%=1000000007; temp[r++]=arr[m++]; } } while(l<=leftEnd) temp[r++]=arr[l++]; while(m<=rightEnd) temp[r++]=arr[m++]; do{ arr[rightEnd--]=temp[--r]; }while(r>0); } }

## Topic 3

The first common node of two linked lists

Topic Description

Enter two linked lists to find their first common node.

Time complexity O(N), space complexity O(N)

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ import java.util.HashSet; public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null) return null; if(pHead1.next==pHead2) return pHead2; if(pHead2.next==pHead1) return pHead2; HashSet<ListNode> set = new HashSet(); ListNode begin=pHead1; while(begin!=null) { set.add(begin); begin=begin.next; } begin = pHead2; while(begin!=null) { if(set.contains(begin)) return begin; begin= begin.next; } return null; } }

I see another fantastic approach in the comment area.

For example, if the length of list 1 is m and the length of list 2 is n, then suppose n > m and n-m =d, the long list takes D steps more than the short list.

Two lists start at the beginning, one is a short list, and then run back to the starting point at the end.

That is to say, the short list needs to circle the d wheel to be on the same starting line as the long list, and it may meet. If the back points to null at the same time, it exits the loop and returns to null.

But what if the list is looped? It seems that this method is not feasible.

There is also the stack method, do not write

public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null) return null; ListNode l = pHead1,r= pHead2; while(l!=r) { l = l==null ? pHead2:l.next; r = r==null ? pHead1:r.next; } return l; } }

## Question 4

Number number of occurrences in a sorted array

Topic Description

Statistics the number of times a number appears in a sorted array.

public class Solution { public int GetNumberOfK(int [] array , int k) { int ans = 0; for(int i:array) { if(i==k) ++ans; } return ans; } }

When I see this question, I'm thinking... Why is it so water? awkward

import java.util.Arrays; public class Solution { public int GetNumberOfK(int [] array , int k) { int ans = 0; if(array.length==1) return ans= array[0]==k ? 1:0; int i = Arrays.binarySearch(array,k); if(i>0){ int l = i-1,r=i+1; while(l>=0) { if(array[l--]==k) ans++; } while(r<array.length) { if(array[r++]==k) ans++; } return ans+1; } return ans; } }

The title does not say that the array is ordered. If it is ordered, it only takes logN time to find the k, and if the length of the K sequence is m.

Just O (m*logN)

However, if the array is out of order, using dichotomy to sort, the time complexity is O(N *logN), rather than traversal.

## Question 5

Maximum depth of binary tree

Topic Description

Input a binary tree to find the depth of the tree. From root node to leaf node, a path is formed by successive nodes (including root and leaf nodes), and the longest path is the depth of the tree.

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public int TreeDepth(TreeNode root) { if(root==null) return 0; return dfs(root); } public int dfs(TreeNode root) { if(root==null) return 0; int left = dfs(root.left); int right = dfs(root.right); return Math.max(left,right)+1; } }

The sequence traverses a binary tree, requiring its maximum depth and remembering the total number of nodes in the current layer. When the number of nodes in the queue equals the total number of nodes in the current layer, it counts the number of next nodes and begins the traversal of the next layer.

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.Queue; import java.util.LinkedList; public class Solution { public int TreeDepth(TreeNode root) { int d=0; if(root==null) return d; Queue<TreeNode> q = new LinkedList(); q.offer(root); int curCount = q.size(),count=0; while(curCount!=0) { TreeNode top = q.poll(); ++count; if(top.left!=null) q.offer(top.left); if(top.right!=null) q.offer(top.right); if(count==curCount) { ++d; count=0; curCount= q.size(); } } return d; } }