重要题目代码

algorithm

链表的两个题目

package com.sort;
public class LinkedListSolution {
    // 测试逆置链表函数的功能是否正确
    public static void main(String[] args) {
        LinkedListSolution lns = new LinkedListSolution();
        ListNode [] larray = new ListNode[]{new ListNode(1),new ListNode(2),new ListNode(3)};
        for(int i = 0 ;i < larray.length - 1; i++) {
            larray[i].next = larray[i+1];
        }
        printLinkedList(larray[0]);
        printLinkedList(lns.ReverseList(larray[0]));
    }
    public static void printLinkedList(ListNode head) {
        while(head != null) { // 循环条件
            System.out.printf("%d ", head.val);
            head = head.next; // 向后一个节点移动
        }
        System.out.println();
    }
//  链表逆置
    public ListNode ReverseList(ListNode head) {
        ListNode empty = new ListNode(0);// 一个虚拟的头节点，临时接收逆序的链表节点
        ListNode p;// 临时变量
        while(head != null) {
            p = head.next; // 把head的下一个节点存储下来，以防丢失，此时，empty->empty.next 后面将head插入到中间
            head.next = empty.next; // 让head的next指向empty的next节点
            empty.next = head; // 让empty的next节点指向head节点，这样形成empty ->head -> empty.next
            head = p;// head节点向后移动
        }
        return empty.next;// 返回逆序节点的第一个节点地址
    }
//  合并两个有序链表
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode empty = new ListNode(0);// 一个虚拟的头节点，临时接收合并后的链表节点
        ListNode p = empty;         //临时变量，循环中，始终指向empty的链表的最后一个节点
        while(list1 != null && list2 != null) {
            if( list1.val < list2.val ) {
                p.next = list1;     // 把list1 接到empty最后一个节点p的后面
                p = list1;          // 更新：p指向empty所在链表的最后一个节点，等待接收下一个节点
                list1 = list1.next; // 向后移动list1
                p.next = null;      // 置空empty最后一个节点，暂时作为链表结束的标记
            }else {
                 p.next = list2;    // 把list2 接到empty最后一个节点p的后面
                 p = list2;         // 更新：p指向empty所在链表的最后一个节点，等待接收下一个节点
                 list2 = list2.next;// 向后移动list2
                 p.next = null;      // 置空empty最后一个节点，暂时作为链表结束的标记
            }
        }
//        下面两个if语句最多只有一个会执行，1.因为两个链表最多有一个是非空的，上面while条件
        if( list1 != null ){// 如果list1还有后续节点，把后续节点组成的链表，直接放到p的后面
            p.next = list1;
        }
        if( list2 != null ){// 如果list2还有后续节点，把后续节点组成的链表，直接放到p的后面
            p.next = list2;
        }
        return empty.next;
    }
}
// 链表定义
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

二分查找及其变种

package com.sort;
public class BinarySearchSolution {
    public static void main(String[] args) {
        int[] A = new int[] { -1, 0, 3, 5, 9, 12 };
        int target = 8;
        int res = search2(A, target);
        System.out.println(res);
    }
    // 二分查找：[0,A.length-1]，区间的查找,这里查找区间内所有元素都是有意义的
    public static int search(int[] nums, int target) {
        int l = 0; // 指向数据的最小元素，left缩写
        int r = nums.length - 1; // 指向数组的最后一个元素，right缩写
        while (l <= r) { // l <= r ，按照上面l,r的定义，等号一定要取到，假设只有一个元素，循环需要执行
            int mid = (l + r) / 2; // 中间元素所在的索引
            if (nums[mid] == target) { // 这个时候找到了target元素所在索引
                return mid;
            } else if (nums[mid] < target) { // target比中间元素还要大，如果target存在，[l,mid] 元素一定小于target，所以不需要在这个区间内查找
                l = mid + 1;
            } else { // 否则，nums[mid] > target 那么target如果不可能存在于[mid,r] 之间，所以在[l,mid-1]之间搜索
                r = mid - 1;
            }
        }
        return -1;
    }
    // 二分查找：[0,A.length]，区间的查找,这里查找区间最右边的元素时没有意义的，只作为查找区间标记
    // 作闭右开的查找
    public static int search2(int[] nums, int target) {
        int l = 0; // 指向数据的最小元素，left缩写
        int r = nums.length; // 指向数组的最后一个元素的下一地址，right缩写，这里r不作为元素取值计算，只作为区间的标记
        while (l < r) { // l < r ，按照上面l,r的定义，等号取不到，假设只有一个元素，循环只需要执行一次，就能判断是否存在
            int mid = (l + r) / 2; // 中间元素所在的索引，利用整数除法向下取整
            if (nums[mid] == target) { // 这个时候找到了target元素所在索引
                return mid;
            } else if (nums[mid] < target) { // target比中间元素还要大，如果target存在，[l,mid] 元素一定小于target，所以不需要在这个区间内查找
                l = mid + 1;
            } else { // 否则，nums[mid] > target 那么target如果不可能存在于[mid,r) 之间，所以在[l,mid-1]之间搜索
                r = mid;
            }
        }
        return -1;
    }
    public static int GetNumberOfK(int[] array, int k) {
        return upper_bound(array, k) - lower_bound(array, k);
    }
    // 查找：不大于k的位置，返回的结果，如果k存在，返回第一个k所在索引，如果不存在，返回k应该插入的位置
    public static int lower_bound(int[] array, int k) {
        int l = 0;  // 应该插入的位置
        int r = array.length; // 查找区间的右边
        while (l < r) { // 由于不包含array.length 所以这里等号取不到，而且，只有一个元素只需要循环一次
            int mid = (l + r) / 2; // 中间节点
            if (array[mid] < k) { // k 比中间节点要大，说明，插入的位置应该在mid之后的一个位置，更新l=mid+1
                l = mid + 1;
            } else {    // 否则：k == array[mid] 说明插入的位置在mid之前，由于r取不到，所以，r=mid,
                        //     k < array[mid] 说明插入的位置，不是mid之后
                r = mid;
            }
        }
        return l;
    }
    public static int upper_bound(int[] array, int k) {
        int l = 0;
        int r = array.length;
        while (l < r) {
            int mid = (l + r) / 2;
            if (array[mid] > k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}

二叉树的题目

// 二叉树的最大深度
//  二叉树的深度
    public int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int l = TreeDepth(root.left);
        int r = TreeDepth(root.right);
        return Math.max(l, r) + 1;
    }
    // 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        in_order(root, res);
        return res;
    }
    void in_order(TreeNode root, ArrayList<Integer> res) {
        if (root == null)
            return;
        in_order(root.left, res); // 左子树
        res.add(root.val);     // 跟节点
        in_order(root.right, res); // 右子树
    }

排序的题目

// 奇偶排序：奇数在前，偶数在后
    public static void sort_odd_event(int[] A) {
        ArrayList<Integer> even = new ArrayList<Integer>(); // 临时存放所有的偶数
        int oddi = 0;  // 奇数在原来数组A中的下标
        for (int i = 0; i < A.length; ++i) {
            if (A[i] % 2 == 0)
                even.add(A[i]); // 临时存放偶数
            else {
                if (oddi != i) { // 存放奇数
                    A[oddi++] = A[i];
                } else
                    oddi++; // 说明一直是奇数
            }
        }
        for (int i = 0; i < even.size(); ++i) { // 复制偶数到原来数组A中
            A[oddi++] = even.get(i);
        }
    }

栈的题目

// 检查是否是有效的括号匹配
public boolean isValid(String s) {
        HashMap<Character, Character> mappings = new HashMap<Character, Character>();
        mappings.put(')', '(');
        mappings.put('}', '{');
        mappings.put(']', '[');
        // Initialize a stack to be used in the algorithm.
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If the current character is a closing bracket.
            if (mappings.containsKey(c)) {
                // Get the top element of the stack. If the stack is empty, set a dummy value of
                // '#'
                char topElement = stack.empty() ? '#' : stack.pop();
                // If the mapping for this bracket doesn't match the stack's top element, return
                // false.
                if (topElement != mappings.get(c)) {
                    return false;
                }
            } else {
                // If it was an opening bracket, push to the stack.
                stack.push(c);
            }
        }
        // If the stack still contains elements, then it is an invalid expression.
        return stack.isEmpty();
    }