Now it is January, spring recruitment golden three silver four, to grasp, remember last January I was still busy reading the interview summary, this is the interview summary of my knowledge, part of the Internet down, part of the interview questions collected, should be very comprehensive, ask to ask the basic also those. Whether BAT a gleam of metal or other different companies such as the interview questions enough, can have some of the recommended list like this you can find on the Internet and then download and also attach some of my information, specific learning course needless to say, Baidu itself, make sense of these common interview questions, basic aspect is solved, The rest of the project experience should also pay attention to accumulation at ordinary times, avoid cramming at the last minute, will soon be revealed.

Website recommends

http://gityuan.com/2016/01/09/java-memory/ memory model http://www.guokr.com/post/114121/ Https to shake hands The working principle of the core http://blog.csdn.net/laner0515/article/details/27692673/ http://www.cnblogs.com/fanzhidongyzby/p/4098546.html IO http://blog.csdn.net/sszgg2006/article/details/38664789 IO http://blog.csdn.net/forfuture3513/article/details/52445213 IO http://www.blogjava.net/bolo/archive/2015/01/20/422296.html concurrency model http://blog.csdn.net/qq396229783/article/details/19924393 String http://www.cnblogs.com/200911/p/3965108.html http://jingyan.baidu.com/article/acf728fd2182e7f8e510a32e.html Chinese coding problem Out of memory solution spring https://www.nowcoder.com/discuss/5683 http://blog.csdn.net/u010425776/article/details/55006347 computer network problem http://blog.csdn.net/hguisu/article/details/7445768/ Socket http://www.jb51.net/article/19024.htm SQL optimization Index of http://www.cnblogs.com/coder2012/p/5309197.html http://www.360doc.com/content/14/0903/10/15077656_406704297.shtml Redis design and implementation of interview questions summary web site at http://blog.csdn.net/sinat_35512245/article/details/59056120

Books recommended

PS: these are some industry famous book online links are more not listed one by one and the same kind of people can read the contrast can be one or two, I roughly read, these are good books, recommended, especially web direction about large sites must know about the technical architecture, can blow water on surface of the project, the feeling is also good

Interview Questions

  1. The size of the nine basic data types, and their encapsulation classes.
  2. Can Switch use string as argument?
  3. Equals ==
  4. What common methods does Object have?
  5. Java four kinds of references, weak and weak virtual, used in the scene
  6. What Hashcode does.
  7. ArrayList, LinkedList, Vector.
  8. The difference between String, StringBuffer and StringBuilder.
  9. Map, Set, List, Queue, Stack features and usage.
  10. Difference between HashMap and HashTable.
  11. The difference between HashMap and ConcurrentHashMap, the underlying source of HashMap.
  12. TreeMap, HashMap, LindedHashMap.
  13. Collection package structure, different from Collections.
  14. Try catch finally, try has a return, is finally executed?
  15. Excption with Error package structure. OOM you have encountered what situation, SOF you have encountered what situation.
  16. Three features and meanings of Java Object orientation.
  17. Override and Overload.
  18. The difference between Interface and abstract classes.
  19. Static class and non-static class.
  20. The implementation principle of Java polymorphism.
  21. There are two ways to implement multithreading: Thread and Runable.
  22. Methods for thread synchronization: sychronized, Lock, reentrantLock, etc.
  23. Lock levels: method lock, object lock, class lock.
  24. Write out the producer-consumer model.
  25. Design concept and function of ThreadLocal.
  26. ThreadPool usage and advantages.
  27. Other things in the Concurrent package: ArrayBlockingQueue, CountDownLatch, and so on.
  28. The difference between wait() and sleep().
  29. Compare the efficiency of foreach with that of normal for loops.
  30. Java IO and NIO.
  31. The action of reflection on principle.
  32. A common feature of generics is whether a List can be converted to a List.
  33. Principles and characteristics of several ways to parse XML: DOM, SAX, PULL.
  34. Java vs. C++.
  35. New features in Java1.7 and 1.8.
  36. Design patterns: singletons, factories, adapters, chains of responsibility, observers, and so on.
  37. Use of JNI. JVM
  38. The memory model and partitions need to be detailed to what is placed in each partition.
  39. Partitions in the heap: Eden, Survival from to, old age, their respective characteristics.
  40. Object creation method, object memory allocation, object access location.
  41. GC is determined by two methods: reference counting and reference chain.
  42. What are the principles and characteristics of GC’s three collection methods: tag clearing, tag collation and copy algorithm? What are your thoughts on how to optimize the collection method?
  43. What are the GC collectors? Features of CMS collector and G1 collector.
  44. When does the Minor and Full GC occur?
  45. Several common memory debugging tools: Jmap, JStack, jConsole.
  46. There are five processes for class loading: loading, validation, preparation, parsing, and initialization.
  47. Parental delegation model: Bootstrap ClassLoader, Extension ClassLoader, ApplicationClassLoader.
  48. Dispatch: Static dispatch and dynamic dispatch. The operating system
  49. The difference between processes and threads.
  50. Deadlock requirements, how to handle deadlocks.
  51. Window memory management: segment storage, page storage, segment page storage.
  52. Several states of a process.
  53. IPC several modes of communication.
  54. What is virtual memory?
  55. The difference between virtual address, logical address, linear address, and physical address. TCP/IP
  56. OSI and TCP/IP each layer of structure and function, what are the protocols.
  57. Differences between TCP and UDP.
  58. TCP packet structure. 4.TCP three-way handshake and four-way wave, each state name and meaning, the function of TIMEWAIT.
  59. TCP congestion control
  60. TCP sliding window with back N pin protocol.
  61. Http packet structure.
  62. Description of the Http status code.
  63. Types of Http requests.
  64. The difference between Http1.1 and Http1.0
  65. Http how to handle long connections.
  66. The principle of Cookie and Session.
  67. DNS, HTTP, TCP, OSPF, IP, ARP.
  68. The whole Ping process. ICMP what is an ICMP packet?
  69. C/S mode using socket communication, several key functions.
  70. IP address classification.
  71. A router is different from a switch. Data structures and algorithms
  72. Linked lists and arrays.
  73. Queue and stack, out and on.
  74. Delete, insert, reverse list.
  75. String manipulation.
  76. Hash function of the Hash table and conflict resolution methods.
  77. Various sorts: bubble, select, insert, hill, merge, fast row, heap row, bucket row, principle of cardinality, average time complexity, worst time complexity, space complexity, stability.
  78. The Merge function and the partition function.
  79. Improvements to bubbling and quick drain.
  80. Binary search, and variant binary search.
  81. Binary tree, B+ tree, AVL tree, red black tree, Huffman tree.
  82. First, middle and subsequent traversal of binary trees: recursive and non-recursive writing, sequential traversal algorithm.
  83. Graph BFS and DFS algorithm, minimum spanning tree Prim algorithm and shortest path Dijkstra algorithm.
  84. KMP algorithm.
  85. Permutation and combination problems.
  86. Dynamic programming, greedy algorithm, divide-and-conquer algorithm. (Usually not asked)
  87. Big data processing: similar to 1 billion pieces of data to find the maximum 1000 number……… Interview questions (from BAT etc.) :

    88. What are the IO models? What is the difference between a process and a thread? What is the difference between a process implemented by an operating system? How does the transaction isolation mechanism SYN differ in method from code blocks? How does memcached differ from other noSQL? How does MVC ThreadLocal explain the role of volatile the difference between heap and stack and the connection between TCP and UDP how does TCP guarantee reliable array and linked list Sorting algorithm Application Scenario Lucene full-text search mechanism

    Dynamic programming Spring transaction memory Thread isolation Sleep () Wait Three handshakes two recycle S1 and S2 RuntimeException Hash Future Callable Clone Load factor binary tree traversal vector in HashMap B+Tree Struts and Spring HttpServlet containers respond to Web client requests as follows: 1) Web clients send Http requests to the Servlet container; 2) Servlet containers parse Http requests from Web clients; 3) The Servlet container creates an HttpRequest object and encapsulates Http request information in this object; 4) The Servlet container creates an HttpResponse object; 5) The Servlet container calls the HttpServlet service Method, which determines whether to execute doGet or doPost based on the request Method. Pass HttpRequest and HttpResponse objects to the HttpServlet object as arguments to the Service method. 6) HttpServlet calls relevant methods of HttpRequest to obtain HTTP request information; 7) HttpServlet calls relevant methods of HttpResponse to generate response data; 8) The Servlet container passes the HttpServlet response results to the Web client.

    DoGet () or doPost() are methods that need to be overridden when creating httpservlets

    Collection classes and collection frameworks; Implementation principle of HashMap and HashTable, thread safety, hash conflict and processing algorithm; ConcurrentHashMap

    The difference between processes and threads; Multithreading and thread pools

    How to ensure data consistency; Synchronized keyword, class lock, method lock, reentrant lock

    Method of synchronization; Multi-process development and multi-process application scenarios

    The server only provides the data receiving interface, in the multi-thread or multi-process condition, how to ensure the orderly arrival of data

    ThreadLocal (ThreadLocal) ¶

    String StringBuilder StringBuffer comparison

    Interfaces and callbacks; The principle of callback; Write a callback demo;

    Generics principle, illustrated by examples; Parsing and dispatching

    Differences between abstract classes and interfaces; Application scenarios; Can an abstract class be without methods and attributes

    Can static properties and methods be inherited? Can it be rewritten? why

    Change the signature of the equals method of object A, which equals method will be called when using HashMap to store instances of the object

    Data structures and algorithms

    What is the difference between heap and stack in memory (data structure vs. actual implementation)

    What’s the fastest sorting algorithm? Which algorithm should be chosen to rank alibaba’s more than 20,000 employees by age? The difference between heap and tree; Write fast typesetting code; List reverse code

    Find the number of daffodils up to 1000 and the number of daffodils up to 4 billion

    Substring contains the problem (KMP algorithm) write code to achieve

    Bit mapping -> Hash grouping -> multi-file read and write efficiency -> Disk addressing and application layer optimization for addressing

    Write down what you know about sorting algorithms and space-time complexity and stability

    Baidu POI how to try to find the latest business function (coordinate mirror +R tree) deadlock four necessary conditions

    Common coding mode; Chinese in UTF-8 encoding takes up several bytes; Int several bytes

    Implement a Json parser (speed up with regex)

    MVC MVP MVVM; Common design patterns; Write the code for observer mode

    TCP’s three handshakes and four waves; Differences between TCP and UDP

    The HTTP protocol. Differences between HTTP1.0 and 2.0; HTTP packet Structure

    Handwritten code

    Enter an incrementally-sorted array and a number s, find two numbers in the array so that their sum is exactly S. If there are multiple pairs of numbers that sum to S, output the smallest product of two numbers. import java.util.ArrayList; public class Solution { public ArrayList FindNumbersWithSum(int [] array,int sum) { ArrayList result=new ArrayList(); if(array==null||array.length==0){ return result; } int i=0; int j=array.length-1;

    while(i! =j){ if(array[i]+array[j]==sum){ result.add(array[i]); result.add(array[j]); return result; } else if(array[i]+array[j]>sum){ j--; } else{ i++; } } return result; }Copy the code

    }

    Public class Solution {public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow=pHead; ListNode fast=pHead; while(fast.next! =null&&slow.next! =null){ fast=fast.next.next; slow=slow.next; if(slow==fast){ fast=pHead; while(fast! =slow){ fast=fast.next; slow=slow.next; } if(slow==fast){ return slow; } } } return null; }Copy the code

    }

    Public ArrayList permutation(String STR){char[] chars= str.tochararray (); char[] chars= str.tochararray (); char[] arrs=new char[chars.length]; int []book=new int[chars.length];

    dfs(strs,0);

    }

    peivate ArrayList dfs(char[] strs,step){

    if(step==strs.length){ String str=””; for(int i=0; i<arrs.length; i++){

          str=str+arrs[i];
Copy the code

    } return str; } for(int i=0; i<strs.length; i++){ if(book[i]==0){ arrs[step]=strs[i]; book[i]=1;

    dfs(strs,step+1);

    book[i]=0; }

    }}

    import java.util.*;

    public class Solution { private char [] seqs; private Integer [] book; Private HashSet result = new HashSet(); /** * Enter a string and print out all permutations of the characters in the string in lexicographical order. * For example, if you enter the string ABC, you print out all the strings ABC, ACb, BAC, BCA, CAB, and CBA that can be arranged by characters A,b, and C *. Please output the results in alphabetical order. * Enter a string of up to 9 characters in length (there may be character duplicates) that contains only upper and lower case letters. * @param str * @return */ public ArrayList Permutation(String str) { ArrayList arrange = new ArrayList(); if(str == null || str.isEmpty()) return arrange; char[] strs = str.toCharArray(); seqs = new char[strs.length]; book = new Integer[strs.length]; for (int i = 0; i < book.length; i++) { book[i] = 0; } dfs(strs, 0); arrange.addAll(result); Collections.sort(arrange); return arrange; }

    Private void DFS (char[] arrs, int step){if(arrs.length == step){String STR = ""; for (int i = 0; i < seqs.length; i++) { str += seqs[i]; } result.add(str); return; For (int I = 0; for (int I = 0; i < arrs.length; Whether i++) {/ / through the if (book [I] = = 0) {seqs [step] = arrs [I]; book[i] = 1; // DFS (arrs, step + 1); // book[I] = 0; }}}Copy the code

    }

    Backtracking import java.util.*; public class Solution { public ArrayList Permutation(String str) { ArrayList re = new ArrayList(); if (str == null || str.length() == 0) { return re; } HashSet set = new HashSet(); fun(set, str.toCharArray(), 0); re.addAll(set); Collections.sort(re); return re; } void fun(HashSet re, char[] str, int k) { if (k == str.length) { re.add(new String(str)); return; } for (int i = k; i < str.length; i++) { swap(str, i, k); fun(re, str, k + 1); swap(str, i, k); } } void swap(char[] str, int i, int j) { if (i ! = j) { char t = str[i]; str[i] = str[j]; str[j] = t; }}}

    5. Binary tree traversal import java.util. / public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

    public TreeNode(int val) {
    this.val = val;


}
Copy the code

    } * /

    public class Solution { public ArrayList PrintFromTopToBottom(TreeNode root) { ArrayList level=new ArrayList();

    if(root==null){ return level; } Queue <TreeNode> bfs=new LinkedList<TreeNode>(); bfs.offer(root); while(! bfs.isEmpty()){ TreeNode r=bfs.poll(); level.add(r.val); if(r.left! =null){ bfs.offer(r.left); } if(r.right! =null){ bfs.offer(r.right); } } return level; }Copy the code

    }

    Public class Queue {private Stack stack1; private Stack stack2;

    public Queue() {
Copy the code

    stack1=new Stack(); stack2=new Stack(); }

    public void Stack1toStack2(){
   while (! stack1.empty()) {
Copy the code

    stack2.push(stack1.pop()); } } public void push(int element) { stack1.push(element);

    }


public int pop() {
    if(stack2.size()==0){
       Stack1toStack2(); 
    }
  return stack2.pop();
}


public int top() {
     if(stack2.size()==0){
       Stack1toStack2(); 
    }
    return stack2.peek();
}
Copy the code

    }

    Layer =(math.min (m,n)-1)/2+1;

    for(int i=0; i<layer; i++){ for(k=i; k<-i; K++) from left to right for(j= I; j<n-i; J++) from top to bottom for(k=m-i-2; k>=i&&(n-i-1! =i); k–) for(j=n-i-2; (j>=i)&&(m-i-1! =i); j–) }

    import java.util.ArrayList; public class Solution { public ArrayList printMatrix(int [][] array) { ArrayList result = new ArrayList (); if(array.length==0) return result; int n = array.length,m = array[0].length; if(m==0) return result; int layers = (Math.min(n,m)-1)/2+1; For (int I =0; i<layers; i++){ for(int k = i; k<m-i; k++) result.add(array[i][k]); For (int j= I +1; j<n-i; j++) result.add(array[j][m-i-1]); For (int k=m-i-2; (k>=i)&&(n-i-1! =i); k–) result.add(array[n-i-1][k]); For (int j=n-i-2; (j>i)&&(m-i-1! =i); j–) result.add(array[j][i]); } return result;

    }
Copy the code

    }

    Public class Solution {public void Mirror(TreeNode root) {

    if(root! =null){ TreeNode temp=root.right; root.right=root.left; root.left=temp; Mirror(root.left); Mirror(root.right); }Copy the code

    }}

    9. Backpack problem this is a typical 01 backpack problem, each type of goods can only choose one item at most. Referring to the solution summarized in Knapsack above, the size of the backpack in this problem can be understood as the weight of the traditional backpack; The size of each backpack can be compared to the value of a traditional backpack. Considering that the array index starts from 0, state BP [I + 1][j] is defined as the maximum value of the total value of the previous I items whose weight does not exceed J. The state transition equation is divided into A[I] > j or not. All initializations are 0, which means nothing is placed. Java

    public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { if (A == null || A.length == 0) return 0;

        final int M = m;
    final int N = A.length;
    int[][] bp = new int[N + 1][M + 1];


    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= M; j++) {
            if (A[i] > j) {
                bp[i + 1][j] = bp[i][j];
            } else {
                bp[i + 1][j] = Math.max(bp[i][j], bp[i][j - A[i]] + A[i]);
            }
        }
    }


    return bp[N][M];
}
Copy the code

    }

    10. Heap sort package edu.princeton.cs.algs4;

    / * *

  • The {@code Heap} class provides a static methods for heapsorting

  • an array.

  • For additional documentation, see Section 2.4 of

  • Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

  • @author Robert Sedgewick

  • @author Kevin Wayne */ public class Heap {

    // This class should not be instantiated. private Heap() { }

    / * *

    • Rearranges the array in ascending order, using the natural order.
    • @param pq the array to be sorted */ public static void sort(Comparable[] pq) { int n = pq.length; for (int k = n/2; k >= 1; k–) sink(pq, k, n); while (n > 1) { exch(pq, 1, n–); sink(pq, 1, n); }}

/*************************************************************************** * Helper functions to restore the heap invariant. ***************************************************************************/

private static void sink(Comparable[] pq, int k, int n) {
    while (2*k <= n) {
        int j = 2*k;
        if (j < n && less(pq, j, j+1)) j++;
        if (!less(pq, k, j)) break;
        exch(pq, k, j);
        k = j;
    }
}
Copy the code

/*************************************************************************** * Helper functions for comparisons and swaps. * Indices are “off-by-one” to support 1-based indexing. ***************************************************************************/ private static boolean less(Comparable[] pq, int i, int j) { return pq[i-1].compareTo(pq[j-1]) < 0; }

private static void exch(Object[] pq, int i, int j) {
    Object swap = pq[i-1];
    pq[i-1] = pq[j-1];
    pq[j-1] = swap;
}


// is v < w ?
private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}
Copy the code

/*************************************************************************** * Check if array is sorted – useful for debugging. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; }

// print array to standard output
private static void show(Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
        StdOut.println(a[i]);
    }
}


/**
 * Reads in a sequence of strings from standard input; heapsorts them; 
 * and prints them to standard output in ascending order. 
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
    String[] a = StdIn.readAllStrings();
    Heap.sort(a);
    show(a);
    assert isSorted(a);
}
Copy the code

}

Public class Solution {/** * @param an integer array * @return void */ public void sortIntegers2(int[] A) { // use a shared temp array, the extra memory is O(n) at least int[] temp = new int[A.length]; mergeSort(A, 0, A.length – 1, temp); }

private void mergeSort(int[] A, int start, int end, int[] temp) { if (start >= end) { return; } int left = start, right = end; int mid = (start + end) / 2; mergeSort(A, start, mid, temp); mergeSort(A, mid+1, end, temp); merge(A, start, mid, end, temp); } private void merge(int[] A, int start, int mid, int end, int[] temp) { int left = start; int right = mid+1; int index = start; // merge two sorted subarrays in A to temp array while (left <= mid && right <= end) { if (A[left] < A[right]) { temp[index++] = A[left++]; } else { temp[index++] = A[right++]; } } while (left <= mid) { temp[index++] = A[left++]; } while (right <= end) { temp[index++] = A[right++]; } // copy temp back to A for (index = start; index <= end; index++) { A[index] = temp[index]; }}Copy the code

}

12. List how quickly the first k node pointer from bottom, pay attention to the first head = = null | | k < = 0 and the if (fastpointer. Next = = null) {return dummy; Public class Solution {public ListNode FindKthToTail(ListNode head,int k) {ListNode dummy=null; if(head==null||k<=0){ return dummy; } ListNode fastpointer=head; ListNode slowpointer=head;

int i=0; while(i<k-1){ if(fastpointer.next==null){ return dummy; } fastpointer=fastpointer.next; i++; }

while(fastpointer.next! =null){ fastpointer=fastpointer.next; slowpointer=slowpointer.next; }

return slowpointer; }}

Public class Solution {public ListNode ReverseList(ListNode head) {ListNode next=null; ListNode pre=null;

while(head! =null){ next=head.next; head.next=pre; pre=head; head=next; } return pre; }Copy the code

}

Public class Solution {ListNode Merge(ListNode list1,ListNode list2) {ListNode Merge(ListNode list1,ListNode list2) {

ListNode dummy=new ListNode(0); ListNode result=dummy; while(list1! =null&&list2! =null){ if(list1.val<list2.val){ result.next=list1; list1=list1.next; } else{ result.next=list2; list2=list2.next; } result=result.next; } if (list1 ! = null) { result.next = list1; } else { result.next = list2; } return dummy.next; }Copy the code

}

15. The biggest and continuous subarray public class Solution {public int FindGreatestSumOfSubArray (int [] array) {if (array. The length = = 0) {return 0; }

int result=array[0]; int sum=array[0]; for(int i=1; i<array.length; i++){ if(sum>=0){ sum=sum+array[i]; } if(sum<0){ sum=array[i]; } if(sum>result){ result=sum; } } return result; }Copy the code

}

Enter an array of positive integers and concatenate all the numbers into a single number. Print the smallest number that can be concatenated. For example, if you enter the array {3,32,321}, the smallest number that can be printed is 321323. import java.util.ArrayList; import java.util.*; public class Solution {

public String PrintMinNumber(int [] numbers) { if(numbers.length==0||numbers==null){ return ""; } String[] str=new String[numbers.length]; StringBuilder sb=new StringBuilder(); for(int i=0; i<numbers.length; i++){ str[i]=String.valueOf(numbers[i]); } Arrays.sort(str,new Comparator<String>(){ public int compare(String s1, String s2) { String c1 = s1 + s2; String c2 = s2 + s1; return c1.compareTo(c2); }}); for(int i = 0; i < str.length; i++){ sb.append(str[i]); } return sb.toString(); }Copy the code

}

Import java.util.HashMap; import java.util. public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode current1 = pHead1; ListNode current2 = pHead2;

HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>(); while (current1 ! = null) { hashMap.put(current1, null); current1 = current1.next; } while (current2 ! = null) { if (hashMap.containsKey(current2)) return current2; current2 = current2.next; } return null; }Copy the code

}

// Method 2:

public ListNode FindFirstCommonNodeII(ListNode pHead1, ListNode pHead2) { ListNode current1 = pHead1; // ListNode current2 = pHead2; / / if chain table 2 (pHead1 = = null | | pHead2 = = null) return null; int length1 = getLength(current1); int length2 = getLength(current2); // The length of two tables is different

If (length1 >= length2) {int length1-length2; Current1 = current1.next; while (len > 0) {current1 = current1.next; len--; If (length1 < length2) {int length2-length1; Current2 = current2.next; while (len > 0) {current2 = current2.next; len--; }} // Start running side by side until the first public node is found 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; } 18. Binary tree depthCopy the code

import java.util.Queue; import java.util.LinkedList;

public class Solution { public int TreeDepth(TreeNode pRoot) { if(pRoot == null){ return 0; } Queue queue = new LinkedList(); queue.add(pRoot); int depth = 0, count = 0, nextCount = 1; while(queue.size()! =0){ TreeNode top = queue.poll(); count++; if(top.left ! = null){ queue.add(top.left); } if(top.right ! = null){ queue.add(top.right); } if(count == nextCount){ nextCount = queue.size(); count = 0; depth++; } } return depth; }}}

import java.lang.Math; public class Solution { public int TreeDepth(TreeNode pRoot) { if(pRoot == null){ return 0; } int left = TreeDepth(pRoot.left); int right = TreeDepth(pRoot.right); return Math.max(left, right) + 1; }}

Import java.util.ArrayList for S; /* * small=1, big=2; *small to big and less than sum, big++; > sum, small++; Public class Solution {public ArrayList<ArrayList> FindContinuousSequence(int sum) {public ArrayList<ArrayList> FindContinuousSequence(int sum) { ArrayList<ArrayList> lists=new ArrayList<ArrayList>(); if(sum<=1){return lists; } int small=1; int big=2; while(small! Int curSum=sumOfList(small,big); int curSum=sumOfList(small,big); if(curSum==sum){ ArrayList list=new ArrayList(); for(int i=small; i<=big; i++){ list.add(i); } lists.add(list); small++; big++; }else if(curSum<sum){ big++; }else{ small++; } } return lists; }

Public int sumOfList(int head,int leap){sum=head; for(int i=head+1; i<=leap; i++){ sum+=i; } return sum; }Copy the code

}

20. Class Solution {public: int LastRemaining_Solution(unsigned int n, unsigned int m) {

if(n <= 0 && m <= 0) return -1; Int t = 0; for(int i = 2; i <= n; i++) t = (t + m) % i; return t; }Copy the code

}; /* F [n] = 0; /* F [n] = 0; /* F [n] = 0; f[i] = (f[i – 1] + m) mod i;

Because of recursion, there is no need to save the status code as follows

* /

/ Joseph, the recurrence formula of the sequence of each round, the final out of sequence number are the same/public int LastRemaining_Solution (int int n, m) {if (n < 1 | | m < 1) return 1; if(n == 1){ return 0; } return (LastRemaining_Solution(n-1, m)+m)%n; }

Public static ListNode deleteDuplication(ListNode pHead) {21. Duplication of duplication

ListNode first = new ListNode(-1); // Set trick first. Next = pHead; ListNode p = pHead; ListNode last = first; while (p ! = null && p.next ! = null) { if (p.val == p.next.val) { int val = p.val; while (p! = null&&p.val == val) p = p.next; last.next = p; } else { last = p; p = p.next; } } return first.next; } 22. Print binary tree in zigzag import java.util.*;Copy the code

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

public TreeNode(int val) {
    this.val = val;


}
Copy the code

} * /

public class Solution{ public ArrayList

Print(TreeNode pRoot) { ArrayList

result = new ArrayList

(); if(pRoot == null){ return result; } boolean leftToRight = true; Queue layer = new LinkedList(); ArrayList layerList = new ArrayList(); layer.add(pRoot); int start = 0, end = 1; while(! layer.isEmpty()){ TreeNode cur = layer.remove(); layerList.add(cur.val); start++; if(cur.left! =null){ layer.add(cur.left); } if(cur.right! =null){ layer.add(cur.right); } if(start == end){ end = layer.size(); start = 0; if(! leftToRight){ result.add(reverse(layerList)); }else{ result.add(layerList); } leftToRight = ! leftToRight; layerList = new ArrayList(); } } return result; } private ArrayList reverse(ArrayList layerList) { int length = layerList.size(); ArrayList reverseList = new ArrayList(); for(int i = length-1; i >= 0; i–){ reverseList.add(layerList.get(i)); } return reverseList; }}


/* public class TreeLinkNode {int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) {this.val = val; } } */ public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode.right! =null){ pNode=pNode.right; while(pNode.left! =null){ pNode=pNode.left; }

return pNode; } else{ if(pNode.next.left==pNode){ return pNode.next; } else{ while(pNode.next.left! =pNode){ pNode=pNode.next; } return pNode; }}}Copy the code

} only 25% above, lack of judgment whether it is the root node, Next public Class Solution {TreeLinkNode GetNext(TreeLinkNode pNode) {if(pNode == null){return null; } if(pNode.right ! = null){ pNode = pNode.right; while(pNode.left ! = null){ pNode = pNode.left; } return pNode; } while(pNode.next ! = null){if(pNode == pNode.next-left) return pNode.next; pNode = pNode.next; } return null; }}

Given a binary search tree, find the KTH smallest node. For example, in 5 /\ 3 7 /\ / 2 4 6 8, the value of the third node in the numerical order is 4. import java.util.Stack; Public class Solution {// int count = 0; TreeNode KthNode(TreeNode pRoot, int k) { if(count > k || pRoot == null) return null; TreeNode p = pRoot; Stack LDRStack = new Stack(); TreeNode kthNode = null; while(p ! = null || ! LDRStack.isEmpty()){ while(p ! = null){ LDRStack.push(p); p = p.left; } TreeNode node = LDRStack.pop(); System.out.print(node.val+”,”); count++; if(count == k){ kthNode = node; } p = node.right; } return kthNode; }}

25. There is an infinite full binary tree whose nodes are numbered layer by layer from left to right by the root node, which is numbered 1. Now we have two nodes a and B. Please design an algorithm to find the number of the nearest common ancestor of points A and B. Given two ints a,b. Is the number of a given node. Return the number of the most recent common ancestor of A and B. Notice that the node itself can also be considered its ancestor. Root = child / 2 root = child / 2 Class LCA {public: a == b; // a == b; int getLCA(int a, int b) { // write code here while(a ! = b) { if(a > b) a /= 2; else b /= 2; } return a; }}

26. Enter a binary tree and an integer. Print out the sum of node values in the binary tree as all paths of the input integers. A path is defined as a path from the root of the tree down to the nodes passed by the leaf. import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<ArrayList> FindPath(TreeNode root, int target) { ArrayList<ArrayList> pathList= new ArrayList<ArrayList>(); if(root==null) return pathList; Stack stack=new Stack(); FindPath(root,target,stack,pathList ); return pathList;

} private void FindPath(TreeNode root, int target, Stack<Integer> path, ArrayList<ArrayList<Integer>> pathList) { if(root==null) return; if(root.left==null&&root.right==null){ if(root.val==target){ ArrayList<Integer> list= new ArrayList<Integer>(); for(int i:path){ list.add(new Integer(i)); } list.add(new Integer(root.val)); pathList.add(list); } } else{ path.push(new Integer(root.val)); FindPath(root.left, target-root.val, path, pathList); FindPath(root.right, target-root.val, path, pathList); path.pop(); }}Copy the code

}

27. For a string, design an algorithm to determine whether it is a valid parenthesis string. Given A string A and its length n, return A bool indicating whether it is A valid parenthesis string. Test sample: “() () ()”, 6 return: true test sample: “a () () (),” seven returned: false test sample: “(() () ()”, 7 returns false

Public Boolean chkParenthesis(String A, int n) {// Write code here /* * 1. If the stack is empty, return false * 2. Return false */ Stack lefts = new Stack(); if(A == null || A.length() ! = n){ return false; } for(int i = 0; i < n; i++){ if(A.charAt(i) == ‘(‘){ lefts.push(A.charAt(i)); }else if(A.charAt(i) == ‘)’){ if(lefts.empty()){ return false; }else{ lefts.pop(); } }else{ return false; } } if(! lefts.empty()){ return false; }else{ return true; }}

28. There are two linked lists of integers, each node containing one digit. The digits are stored backwards, that is, at the head of the list. Write a function to sum the two integers and return the result as a linked list.Copy the code

Given two linked lists ListNode* A, ListNode* B, return the result of A+B (ListNode*). Example: {1,2,3},{3,2,1} return: {4,4,4}

public class Plus { public ListNode plusAB(ListNode a, ListNode b) { if (a == null) { return b; } if (b == null) { return a; } ListNode p1 = a, p2 = b; ListNode head = new ListNode(0); ListNode p = head; int sum = 0; while (p1 ! = null || p2 ! = null || sum ! = 0) { if (p1 ! = null) { sum += p1.val; p1 = p1.next; } if (p2 ! = null) { sum += p2.val; p2 = p2.next; } p.next = new ListNode(sum % 10); sum /= 10; p = p.next; } return head.next; }}

[programming question] Split the linked list into two parts based on the given value x. All nodes less than x are ranked before nodes greater than or equal to x. Given a head pointer of the linked list ListNode* pHead. Note: keep the original data order unchanged after segmentation. Train of thought

Set two list heads, iterate over the original list, one to append decimals, one to append large numbers, and finally glue the decimal list to the front of the large number list.

class Partition { public: ListNode* partition(ListNode* head, int x) { if(head == nullptr){ return nullptr; }//if ListNode *smallList = new ListNode(-1); ListNode *bigList = new ListNode(-1); ListNode *ps = smallList,*pb = bigList,*cur = head; while(cur){ if(cur->val < x){ ps->next = cur; ps = cur; }//if else{ pb->next = cur; pb = cur; }//else cur = cur->next; }//while pb->next = nullptr; ps->next = bigList->next; return smallList->next; }}

There is a node-like data structure called the TreeNode, which contains the val property and Pointers to other nodes. It can be used to represent a binary search tree (where the left pointer represents the left son and the right pointer represents the right son). Write a method that converts a binary lookup tree to a linked list, where the data structure of the binary lookup tree is implemented using TreeNode and the data structure of the linked list is implemented using ListNode. Given the root pointer to the binary lookup tree, return the head pointer to the converted list.

Solution: Provide recursive and non-recursive versions using mid-order traversal.

Dummy =new ListNode(0); dummy=new ListNode(0); ListNode tail=dummy; public ListNode treeToList(TreeNode root) { // write code here if(root==null) return null;

treeToList(root.left); tail.next=new ListNode(root.val); tail=tail.next; treeToList(root.right); return dummy.next; } // Method 2: iterator public ListNode treeToList(TreeNode root) { // write code here if(root==null) return null; ListNode dummy=new ListNode(0); ListNode tail=dummy; Stack<TreeNode> stack=new Stack<TreeNode>(); while(root! =null || ! stack.isEmpty()){Copy the code

while(root! =null){ stack.push(root); root=root.left; }

root=stack.pop(); tail.next=new ListNode(root.val); tail=tail.next; root=root.right; } return dummy.next; } 31. Two digits in an array form an inversion pair if the preceding digit is greater than the following digit. Enter an array and find the total number of inversions P in the array. And output the result of P modulo to 1000000007. That is, output P%1000000007 refer to "Sword Finger offer" with merge sort idea, time complexity O(nlogn)Copy the code

int InversePairs(vector data) { int length = data.size(); return mergeSort(data, 0, length-1); }

Int mergeSort(vector<int>& data, int start, int end) {if(start >= end) {return 0; } // int mid = (start + end) / 2; int leftCounts = mergeSort(data, start, mid); int rightCounts = mergeSort(data, mid+1, end); Vector <int> copy(data); Int foreIdx = mid; Int backIdx = end; Int counts = 0; Int idxCopy = end; While (foreIdx>=start && backIdx >= mid+1) {if(data[foreIdx] > data[backIdx]) {copy[idxCopy--] = data[foreIdx--]; counts += backIdx - mid; } else { copy[idxCopy--] = data[backIdx--]; } } while(foreIdx >= start) { copy[idxCopy--] = data[foreIdx--]; } while(backIdx >= mid+1) { copy[idxCopy--] = data[backIdx--]; } for(int i=start; i<=end; i++) { data[i] = copy[i]; } return (leftCounts+rightCounts+counts); }Copy the code

Void ReverseWord(string & STR, int s, int e) {while(s < e) swap(STR [s++], STR [e–]); }

string ReverseSentence(string str) { ReverseWord(str, 0, str.size() - 1); Int s = 0, e = 0; int i = 0; While (I < STR. The size ()) {while (I < STR. The size () && STR [I] = = ' ') / / space skip i++; e = s = i; While (I < str.size() &&str [I]! {i++; e++; } ReverseWord(str, s, e - 1); } return STR; } 32. Adjust the array in order to make odd in even the front input an integer array, to implement a function to adjust the order of the Numbers in the array, makes all the odd number in the first half of the arrays, and all of the even number is located in located in the second part of the array, and ensure the odd number and odd number, the relative position between the even number and even the same. public void reOrderArray2(int [] a) { if(a==null||a.length==0) return; int i = 0,j; while(i<a.length){ while(i<a.length&&! isEven(a[i])) i++; j = i+1; while(j<a.length&&isEven(a[j])) j++; if(j<a.length){ int tmp = a[j]; for (int j2 = j-1; j2 >=i; j2--) { a[j2+1] = a[j2]; } a[i++] = tmp; }else{// failed to find break; }}Copy the code

} boolean isEven(int n){ if(n%2==0) return true; return false; }

Class Solution {public: void reOrderArray(vector &array) {class Solution {public: void reOrderArray(vector &array) {

for (int i = 0; i < array.size(); i++) { for (int j = array.size() - 1; j>i; J -) {if (array [j] % = = 1 & 2 & array [1] % 2 = = 0) / {before/after accidentally, exchange swap (array [j], array [1]). }}}}Copy the code

};

Class Solution{public: void reOrderArray(vector &array) {

vector<int> array_temp; vector<int>::iterator ib1, ie1; ib1 = array.begin(); for (; ib1 ! = array.end();) If (*ib1%2 == 0) {array_temp.push_back(*ib1); ib1 = array.erase(ib1); } else{ ib1++; } } vector<int>::iterator ib2, ie2; ib2 = array_temp.begin(); ie2 = array_temp.end(); for (; ib2 ! = ie2; Ib2 ++) // Add the number of new arrays to the old array {array.push_back(*ib2); }}Copy the code

};

33. Longest public substring Given two strings, find the longest common substring. Return the length of it. Note The characters in substring should occur continiously in original string. This is different with subsequnce.

public class Solution { /** * @param A, B: Two string. * @return: the length of the longest common substring. */ public int longestCommonSubstring(String A, String B) { // state: f[i][j] is the length of the longest lcs // ended with A[i – 1] & B[j – 1] in A[0..i-1] & B[0..j-1] int n = A.length(); int m = B.length(); int[][] f = new int[n + 1][m + 1];

    // initialize: f[i][j] is 0 by default


    // function: f[i][j] = f[i - 1][j - 1] + 1 or 0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = 0;
            }
        }
    }
    
    // answer: max{f[i][j]}
    int max = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            max = Math.max(max, f[i][j]);
        }
    }
    
    return max;
}
Copy the code

}

34. Find the maximum path sum Given a binary tree. The path may start and end at any node in the tree.

For example: Given the below binary tree, 1 / \ 2 3 Return 6.

Public Class Solution {private Class ResultType {// singlePath: the maximum path from root to any point. This path can contain no points. The maximum path from any point in the tree to any point that contains at least one point int singlePath, maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; }}

private ResultType helper(TreeNode root) {
    if (root == null) {
        return new ResultType(0, Integer.MIN_VALUE);
    }
    // Divide
    ResultType left = helper(root.left);
    ResultType right = helper(root.right);


    // Conquer
    int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
    singlePath = Math.max(singlePath, 0);


    int maxPath = Math.max(left.maxPath, right.maxPath);
    maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);


    return new ResultType(singlePath, maxPath);
}


public int maxPathSum(TreeNode root) {
    ResultType result = helper(root);
    return result.maxPath;
}
Copy the code

}

// Version 2: // SinglePath is also defined to contain at least one point. public class Solution { /** * @param root: The root of binary tree. * @return: An integer. */ private class ResultType { int singlePath, maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; }}

private ResultType helper(TreeNode root) {
    if (root == null) {
        return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
    }
    // Divide
    ResultType left = helper(root.left);
    ResultType right = helper(root.right);


    // Conquer
    int singlePath =
        Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;


    int maxPath = Math.max(left.maxPath, right.maxPath);
    maxPath = Math.max(maxPath,
                       Math.max(left.singlePath, 0) + 
                       Math.max(right.singlePath, 0) + root.val);


    return new ResultType(singlePath, maxPath);
}


public int maxPathSum(TreeNode root) {
    ResultType result = helper(root);
    return result.maxPath;
}
Copy the code

}

35.hashMap public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L; /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.6f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ /** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }Copy the code

/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * *

More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * *

A return value of {@code null} does not necessarily * indicate that the map contains no mapping for the key; it’s also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

/** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n – 1) & hash]) ! = null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key ! = null && key.equals(k)))) return first; if ((e = first.next) ! = null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; }

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don’t change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n – 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD – 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }

/** * Implements Map.remove and related methods * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes  while removing * @return the node, or null if none */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) ! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! = null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) node = p; else if ((e = p.next) ! = null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) ! = null); } } if (node ! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }} 36. Import java.util.*;Copy the code

public class Solution {

HashMap<Character, Integer> map = new HashMap<>(); public int FirstNotRepeatingChar(String str) { if (str==null)return -1; int length = str.length(); int chars[]=new int[256]; for(int i = 0; i<length; i++) { if(map.containsKey(str.charAt(i))){ int value = map.get(str.charAt(i)); map.put(str.charAt(i),value+1); }else{ map.put(str.charAt(i),1); chars[str.charAt(i)]=i; } } for(int i = 0; i<length; i++){ if(map.get(str.charAt(i))==1) return chars[str.charAt(i)]; } return -1; }Copy the code

}

In a two-dimensional array, each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Complete a function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

First, we choose to search from the bottom left corner, (why not start from the top left corner, the top left corner is increasing to the right and down, so for a point, for right and down there will be a fork; If we choose to search from the lower left foot, if greater, to the right, if less, down). public class Solution { public boolean Find(int [][] array,int target) { int len = array.length-1; int i = 0; while((len >= 0)&& (i < array[0].length)){ if(array[len][i] > target){ len–; }else if(array[len][i] < target){ i++; }else{ return true; } } return false; }}

38.LRU CACHE

public int get(int key) { if( ! hs.containsKey(key)) { return -1; } // remove current Node current = hs.get(key); current.prev.next = current.next; current.next.prev = current.prev; // move current to tail move_to_tail(current); return hs.get(key).value; } public void set(int key, int value) { if( get(key) ! = -1) { hs.get(key).value = value; return; } if (hs.size() == capacity) { hs.remove(head.next.key); head.next = head.next.next; head.next.prev = head; } Node insert = new Node(key, value); hs.put(key, insert); move_to_tail(insert); } private void move_to_tail(Node current) { current.prev = tail.prev; tail.prev = current; current.prev.next = current; current.next = tail; }Copy the code

}

39. Top K of big data 40.100 descending array, each group of 500 digits, find the first 3000 digits