算法训练营总结

// 删除pre.next = curr.next;// 插入curr.next = pre.next;pre.next = curr;// 反转public ListNode reverseList(ListNode head) {    ListNode pre = null;    ListNode curr = head;    while(curr != null){        ListNode temp = curr.next;        curr.next = pre;        pre = curr;        curr = temp;    }    return pre;}

Comparator<Object> cmp = new Comparator<Object>() {        public int compare(Object o1, Object o2) {            //升序            return o1-o2;            //降序            return o2-o1;        }    };

// 递归public static void preOrderRecur(TreeNode head) {    if (head == null) {        return;    }    System.out.print(head.value + " ");    preOrderRecur(head.left);    preOrderRecur(head.right);}
// 非递归public static void preOrderIteration(TreeNode head) {	if (head == null) {		return;	}	Stack<TreeNode> stack = new Stack<>();	stack.push(head);	while (!stack.isEmpty()) {		TreeNode node = stack.pop();		System.out.print(node.value + " ");		if (node.right != null) {			stack.push(node.right);		}		if (node.left != null) {			stack.push(node.left);		}	}}

// 递归public static void preOrderRecur(TreeNode head) {    if (head == null) {        return;    }    preOrderRecur(head.left);    System.out.print(head.value + " ");    preOrderRecur(head.right);}
// 非递归public static void inOrderIteration(TreeNode head) {	if (head == null) {		return;	}	TreeNode cur = head;	Stack<TreeNode> stack = new Stack<>();	while (!stack.isEmpty() || cur != null) {		while (cur != null) {			stack.push(cur);			cur = cur.left;		}		TreeNode node = stack.pop();		System.out.print(node.value + " ");		if (node.right != null) {			cur = node.right;		}	}}

// 递归public static void postOrderRecur(TreeNode head) {    if (head == null) {        return;    }    postOrderRecur(head.left);    postOrderRecur(head.right);    System.out.print(head.value + " ");}
// 非递归// 左右中-->中右左，按中右左的顺序输出到一个栈中，再把栈输出就是左右中public static void postOrderIteration(TreeNode head) {		if (head == null) {			return;		}		Stack<TreeNode> stack1 = new Stack<>();		Stack<TreeNode> stack2 = new Stack<>();		stack1.push(head);		while (!stack1.isEmpty()) {			TreeNode node = stack1.pop();			stack2.push(node);			if (node.left != null) {				stack1.push(node.left);			}			if (node.right != null) {				stack1.push(node.right);			}		}		while (!stack2.isEmpty()) {			System.out.print(stack2.pop().value + " ");		}	}

class Solution:    def inorderTraversal(self, root: TreeNode) -> List[int]:        WHITE, GRAY = 0, 1        res = []        stack = [(WHITE, root)]        while stack:            color, node = stack.pop()            if node is None: continue            if color == WHITE:                stack.append((WHITE, node.right))                stack.append((GRAY, node))                stack.append((WHITE, node.left))            else:                res.append(node.val)        return res

public List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> res = new ArrayList<List<Integer>>();        if (root == null){            return res;        }        Deque<TreeNode> queue = new LinkedList<TreeNode>();        queue.offer(root);        while (!queue.isEmpty()){            int size = queue.size();            List<Integer> list = new ArrayList<Integer>();            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll();                list.add(node.val);                if (node.left != null){                    queue.offer(node.left);                }                if (node.right != null){                    queue.offer(node.right);                }            }            res.add(list);        }        return res;    }

public void recur(int level, int param) { // terminator if (level > MAX_LEVEL) { // process result return; } // process current logic process(level, param); // drill down recur( level: level + 1, newParam); // restore current status
}

def divide_conquer(problem, param1, param2, ...):# recursion terminatorif problem is None: print_result return# prepare data data = prepare_data(problem) subproblems = split_problem(problem, data)# conquer subproblems subresult1 = self.divide_conquer(subproblems[0], p1, ...) subresult2 = self.divide_conquer(subproblems[1], p1, ...) subresult3 = self.divide_conquer(subproblems[2], p1, ...)...# process and generate the final result result = process_result(subresult1, subresult2, subresult3, …)
 # revert the current level states 

visited = set()def dfs(node, visited):if node in visited: # terminator# already visitedreturn visited.add(node)# process current node here....for next_node in node.children(): if not next_node in visited: dfs(next node, visited)

def BFS(graph, start, end): queue = [] queue.append([start]) visited.add(start)while queue: node = queue.pop() visited.add(node) process(node) nodes = generate_related_nodes(node) queue.push(nodes) 

left, right = 0, len(array) - 1while left <= right: mid = (left + right) / 2 if array[mid] == target: # find the target!! break or return result elif array[mid] < target: left = mid + 1 else: right = mid - 1