常用数据结构总结【Google/FB 面试】

回馈地里， 这是我之前面试的 java数据结构的总结，顺便求点大米 😁





1.  数据结构2. trie —> not only save space, but also allow to iterate through word char by char  —> 642 Autocomplete https://leetcode.com/problems/de ... system/description/
3. LinkedList —> 何时用 dummy(need to return head & tail & traversing an empty linked list & double linked list —>   head<—> tail),  reverse List —>  2 ways ,     swap node (tree)—> val or reference,  find mid —> while(fast!=tail&&fast.next!=tail){ fast = fast.next.next; slow = slow.next; } .. Linkedlist -> levelValues.add(cur.val); levelValues.addFirst(cur.val);
4. circular array problems i —>  The first typical way to solve circular array problems is to extend the original array to twice length,
5.  hashset —>  help deduplicate，  int[] visited
6. Array  —>  cnt[] or index[] —> 何时用 array 来储存， dp  或者 accumulative calculation (储存 位置固定不变) , dp[][] = new int[r + 1][c + 1] —>   start from [1,1],   first row and col are filled with 0.     think about how to align , and 1st and 2nd fill in (decode way)
matrix —>  n * m matrix convert to an array => matrix[x][y] => a[x * m + y] an array convert to n * m matrix => a[x] =>matrix[x / m][x % m];  可以用 boolean[][] 来 储存  distance， 也可用 HashMap<index, distance> = new HashMap<row_len* row + col, distance> 来储存
7. min stack/queue —> stack/queue to keep the indexes of the decreasing subsequence,  need a inner while loop to clean it
9. binary search tree —> swap node —>    // if root is being deleted,  left child should go to right's smallest  // or find right subtree smallest to replace root node // swap val not swap object
10. buildTree —> recursive  重复做一件事  —> 给当前node assign left and right child —> 终止条件是 node 为 null  —> dfs 一边走到底  —>  从上走到下， 却从下往上建 —>   queue <preorder> + recursive     OR      stack pop
11.  tree, graph, matrix —>  traverse( recursion or bfs or linear or hybrid )
12. Cache -> key/val pairs —> same key diff val —> max cap —>  LRU,
14. LFU —> HashMap<key, val> keyToVal; HashMap<key, cnt> KeyToCount; HashMap<cnt, LinkedHashSet<key>> CountToKey; int cap; int min = -1;
15. in-memory-file-system —>
16. reader4 —>  final buffer (char[] finalBuf) + wanna get total n char  -> int count = read4(tmpBuf)  ->   a. read up file b. get n chars ->  copy temp to final
17. reader4-2 —>  can read multiple times —> element in tempBuf is not used up,
18.  TreeSet
19.  TreeMap  --> int sum = (int)treeMap1.keySet().toArray()[left]
20.  binary indexed tree: https://cs.stackexchange.com/que ... ow-was-it-thought-a
21.  Iterator<Integer> iter = hm.keySet().iterator();
22.  serializer/deserializer  —>  bt, bst, n-ary () ,   n Serialize: Not only add val of node, but also add the children size of this node to the result list for(Node child:root.children) ===== pre order No need use # to tell the null child, because you already has children size Use String.join(",",list); to convert String list to String Deserialize: Use a queue just like Serialize and Deserialize binary Tree。 use recursion to build string and build a tree!!
23. Deque<String> nodes = new LinkedList<>();    nodes.addAll(Arrays.asList(data.split(spliter)));
25.  PriorityQueue, 先放后 poll。  min heap or max heap,   295 Find Median from Data Stream
26. ConcurrentHashMap vs.  Hashtable vs. HashMap.

• char
  

String, substring —> substring(int beginIndex) substring(int beginIndex, int endIndex exclusive)
String t = s.substring(0, i) + s.substring(i + 1);
String keyStr = String.valueOf(charArray);
String str = "geekss@for@geekss";  String[] arrOfStr = str.split("@", 2);     —>  {“geekss”, ”for@geekss”}
!Character.isLetterOrDigit(cHead)
sb.reverse().toString();
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
int[] c = new int[26]; for(char t : tasks){ c[t - 'A']++; } Arrays.sort(c);
sb.append(NN).append(spliter);           return sb.reverse().toString();
Arrays.asList(num, num[lo], num[hi])
s.charAt(i) <= '9'
Arrays.fill(next, -1);
Arrays.stream(int[] {1,2,3}).map(new ArrayList() :: add)
for(char c : string.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); }

String reg = "[^a-zA-Z0-9]+";
if (s.matches(reg)) return sb.toString();
String [] str = s.trim().split("\\s+");

String str = "a12.334tyz.78x";
str = str.replaceAll("[^\\d.]", "");
Now str will contain "12.334.78".

Set<String> ban = new HashSet<>(Arrays.asList(String[]));
String[] words = str.replaceAll("\\W+" , " ").toLowerCase().split("\\s+");
for (String s : paragraph.replaceAll("[^a-zA-Z ]", "").toLowerCase().split(" ")) {
String reg = "[^a-zA-Z0-9]+";
if (s.matches(reg)) return sb.toString();

while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
“123”.compareTo(“1”) > 0
String s = new String(char array);
// rear = -1
rear = (rear + 1) % a.length;
private int [] window;
insert = (insert + 1) % window.length;
String.valueOf(char[]);
while(strs[i].indexOf(pre) != 0)
str.startsWith(string, index)
String.join("/",stack);

"A" + n % 26  is not (char)('A' + n % 26)
char board[row][col] = (char)(int_count + '0');

• Matrix
  

public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};       for(int[] dir: dirs) {}
int[][] moves = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
// fill in he 2d array
dp is boolean[][]
    for (int i = 0; i < dp.length; i++) {
        Arrays.fill(dp[i], false);
}
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block

• Map
  

Map <item, latest index>
Map <Location, PriorityQueue<Location>>

Map<Integer, Integer>[] map = new Map[A.length];
Map<Integer, List<Integer>> map = new Map<val, List<nums.size>>();
Map<diff, cnt>[] map = new Map<Integer, Integer>[A.length];

Hashmap<sum[0,i - 1], frequency>

if (map[s.charAt(end++)]-- > 0) count--;   —>      先判断， map再--
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};
double curly:  Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1); put(-1, -2);}};
HashMap<Integer, Integer> preSum   preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
for (Map.Entry<String, JButton> entry : listbouton.entrySet())
{
  String key = entry.getKey();
  JButton value = entry.getValue();

  this.add(value);
}

countToLRUKeys.computeIfAbsent(count, ignore -> new LinkedHashSet<>());
hashmap.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
for(int i = 0; i < words.length; i++) {
    map.computeIfAbsent(words[i], v -> new ArrayList<>()).add(i);
}

• Set
  

public static final Character[] vowelsList = new Character[]{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
public static final HashSet<Character> vowels = new HashSet<Character>(Arrays.asList(vowelsList));
set.addAll(wordDictList);

• PriorityQueue
  

PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);         1.        a[0] is char, a[1] is count

PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>( (a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) :a.getValue()-b.getValue() );
PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (a, b) -> (a.end - b.end));
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
    @Override
    public int compare(ListNode o1,ListNode o2){
        if (o1.val<o2.val)
            return -1;
        else if (o1.val==o2.val)
            return 0;
        else
            return 1;
    }
});

Queue<int[]> queue = new LinkedList<>();
if(! pq.remove(nums[start])) {
q = new PriorityQueue<>(k);
Queue<NestedInteger> queue = new LinkedList<NestedInteger>(nestedList);
PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);               pq.add(new int[] {i, j, forest.get(i).get(j)});

• List
  

List<int[]> nums = new List<int[val, map.get(val).size() - 1}]>();
LinkedList<Iterator> list;

List<Interval> intervals — >intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
Queue<Integer> queue = new LinkedList<>();
String remove = linkedlist.remove();
Deque<Integer> d = new ArrayDeque<>();  d.getFirst()， d.pollFirst()， d.addLast(i)
return new ArrayList<List<String>>(map.values());
LinkedList<String> stack = new LinkedList<String>();    stack.removeLast();

• Comparator
  

strNum.compareTo(strNum) < 0
int compare = Intger1.compareTo(Intger2);
Arrays.sort(intervals, new Comparator<Interval>() {

            @Override
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
Arrays.sort(intervals, (a,b) -> a.start - b.start);


alpbetic oder compare  -->  a. need to compare all the char  b. need compare length
int compare(String s1, String s2) {
    int n = s1.length(), m = s2.length(), cmp = 0;
    for (int i = 0, j = 0; i < n && j < m && cmp == 0; i++, j++) {
        cmp = mapping[s1.charAt(i) - 'a'] - mapping[s2.charAt(j) - 'a'];
    }
    return cmp == 0 ? n - m : cmp;
}

Arrays.sort(points, (a, b) -> a[1] - b[1]);

public String[] reorderLogFiles(String[] logs) {

        Comparator<String> myComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int s1si = s1.indexOf(' ');
                int s2si = s2.indexOf(' ');
                char s1fc = s1.charAt(s1si+1);
                char s2fc = s2.charAt(s2si+1);

                if (s1fc <= '9') {
                    if (s2fc <= '9') return 0;
                    else return 1;
                }
                if (s2fc <= '9') return -1;

                int preCompute = s1.substring(s1si+1).compareTo(s2.substring(s2si+1));
                if (preCompute == 0) return s1.substring(0,s1si).compareTo(s2.substring(0,s2si));
                return preCompute;
            }
        };

        Arrays.sort(logs, myComp);
        return logs;
    }

• Integer
  

if (divisor == 0 || //divide by zero
        dividend == Integer.MIN_VALUE && divisor == -1 //overflow check
        ) {
    return Integer.MAX_VALUE;
}
int sign = 1;
if (dividend < 0 ^ divisor < 0) { //XOR if either is negative, but not both
    sign = -1;
}
// Convert to Long or else abs(-2147483648) overflows
long num = Math.abs((long)dividend);
long den = Math.abs((long)divisor);


int sum = carry;
if (j >= 0) sum += b.charAt(j--) - '0';
if (i >= 0) sum += a.charAt(i--) - '0';

Integer.parseInt

int idx(int key) { return Integer.hashCode(key) % nodes.length;}
Integer.valueOf(s.substring(j, i + 1))
// even or odd
    if ((sum & 1) == 1) {
        return false;
    }

• Trie
  

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

• Tree
  

return left == null ? right : right == null ? left : root;

• UnionFind
  

private class UnionFind {
    private int[] parents;
    public int count;
    UnionFind(int n) {
        parents = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        count = n;
    }

    private int find(int i) {
        if (parents[i] == i) {
            return i;
        }
        parents[i] = find(parents[i]);
        return parents[i];
    }

    public void union(int i, int j) {
        int a = find(i);
        int b = find(j);
        if (a != b) {
            parents[a] = b;
            count--;
        }
    }
}

private String find(String s, Map<String, String> p) {
    return p.get(s) == s ? s : find(p.get(s), p);
}

• Bit
  

"&" AND operation, for example, 2 (0010) & 7 (0111) => 2 (0010)
"^" XOR operation, for example, 2 (0010) ^ 7 (0111) => 5 (0101)
"~" NOT operation, for example, ~2(0010) => -3 (1101)
e.g. 1110 is -2, which is ~2 + 1, ~0010 => 1101, 1101 + 1 = 1110 => 2
n = n >>> 1;      
denCopy <<= 1; // << denCopy is multiply by 2

use integer to store two states
[2nd bit, 1st bit] = [next state, current state]

- 00  dead (next) <- dead (current)
- 01  dead (next) <- live (current)  
- 10  live (next) <- dead (current)  
- 11  live (next) <- live (current)


//  i <= j doesn’t works  ,  i < j works !!!
static void swap(char[] arr, int i, int j) {
    arr[i] ^= arr[j];
    arr[j] ^= arr[i];
    arr[i] ^= arr[j];
}

• Loop
  

for (; node != null; stack.push(node), node = node.left);
for (int i = 0; i < numbers.length; map.put(numbers[i], i++))  {}
for (int len = 1; !q.isEmpty(); len++) {
while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9')

// for loop with index,   the if is at beginning  not at end
        for (String word : S.split(" ")) {
            if (wordIndex != 1) {
                answer.append(" ");
            }
            wordIndex++;
        }

• Probability
  

final Random random = new Random();    r = random.nextInt(ind + 1);

• binary search
  

int i = Arrays.binarySearch(dp, 0, len, x);

• Iteratoor
  

Iterator<Integer> iter = hashmap.keySet().iterator();

• TreeMap
  

treeMap.floorKey(left); // Returns the greatest key less than or equal to the given key, or null if there is no such key.
treemap.higherKey()

• Random
  

this is a way to randomly shuffle a array
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] rand = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
            int r = (int) (Math.random() * (i+1));
            rand[i] = rand[r];
            rand[r] = nums[i];
        }
        return rand;
    }

int randomWithRange(int min, int max)
{
   int range = (max - min) + 1;     
   return (int)(Math.random() * range) + min;
}

rand.nextInt(nums.size())




[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

谢谢！总觉得很到位～

   谢谢分享！

吐血mark，LZ这个总结太宝贵了

mark一下

火钳刘明.

不错不错，多谢楼主分享

不错不错

感谢楼主分享

总结的不错~加米了

不错不错，多谢楼主分享

谢谢楼主，好人一生平安