面试算法题

排序：选择排序，冒泡排序，快排，堆排，希尔排序

//选择，空间复杂度O(1)，时间复杂度为O(n^2)
public static void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
    }

//冒泡，空间复杂度O(1)，时间复杂度为O(n^2)
public static void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }

//快速排序是一种不稳定的排序方法。空间复杂度O(logn) 或 O(n)
//时间复杂度O(nlogn) 或者 O(n^2) 
public static void sort(int[] nums, int low, int hight) {
        int left = low;
        int right = hight;
        int key = nums[left];
        while (left < right) {
            // 先从右往左找到比key小的，有的话就放到key的位置上，当前这个位置后面就可以进行覆盖
            while (left < right && nums[right] >= key) {
                right--;
            }
            nums[left] = nums[right];
            // 再从左往右找到比key大的数，覆盖到刚才那个 right 位上
            while (left < right && nums[left] <= key) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        // 排完后，key左边的数都比key小，key右边的数都比key大，然后就可以分别再把key左右部分进行这样排序
        sort(nums, low, left - 1);
        sort(nums, right + 1, hight);
    }

反转链表

public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    while (null != head) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

// 递归法 1->2->3->4->null
public static ListNode reverseList(ListNode head) {
    if (null == head && head.next == null) {
        return head;
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head;//head.next不为null
    head.next = null;
    return newHead;
}

删除链表的倒数第N个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode(0,head);
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        head = node;
        for (int i = 0; i < len-n; i++) {
            head = head.next;
        }
        ListNode next = head.next;
        head.next = next.next;
        next.next = null;
        return node.next;
    }

数组中第K个最大元素

public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len - k];
    }

翻转数字

static int reverseNum(int num) {
        int res = 0;
        while (num != 0) {
            int i = num % 10;
            res = res * 10 + i;
            num = num / 10;
        }
        return res;
    }

翻转字符串

static String reverseString(String s) {
        char[] chars = s.toCharArray();
        char[] chars2 = new char[chars.length];
        int j = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            chars2[j] = chars[i];
            j++;
        }
        return new String(chars2);
    }

static String reverseString2(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int j = chars.length / 2;
        for (int i = 0; i < j; i++) {
            char tmp = chars[i];
            chars[i] = chars[n - 1 - i];
            chars[n - 1 - i] = tmp;
        }
        return new String(chars);
    }

判断回文数，121，1221

public static boolean isPalindrome(int k) {
        String string = String.valueOf(k);
        int len = string.length();
        int mid = len / 2;
        for (int i = 0; i <= mid; i++) {
            char c1 = string.charAt(i);
            char c2 = string.charAt(len - 1 - i);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }

public static boolean isPalindrome2(int x) {
        if (x < 0) return false;
        int div = 1;
        while (x / div >= 10) {
            div = div * 10;
        }
        while (x > 0) {
            int n1 = x % 10;//个位数
            int n2 = x / div;//高位数
            if (n1 != n2) {
                return false;
            }
            x = x % div;//去除高位
            x = x / 10;//去除个位
            div = div / 100;
        }
        return true;
    }

最长回文字符串
判断有效括号，{[()]}

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '(') {
                stack.push(')');
            } else if (stack.isEmpty() || stack.pop() != c) {//不是 {[( 那就一定得是 )]}
                return false;
            }
        }
        return true;
    }

public boolean isValid2(String s) {
        if (s == null || s.length() == 0) return false;
        while (s.contains("{}") || s.contains("[]") || s.contains("()")) {
            s = s.replace("{}", "");
            s = s.replace("()", "");
            s = s.replace("[]", "");
        }
        return s.isEmpty();
    }

括号的分数(())()

//有效的括号的分数 (())()
    public static int score(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(0);
            } else {
                int v1 = stack.pop();
                int v2 = stack.pop();
                stack.push(v2 + Math.max(1, v1 * 2));
            }
        }
        return stack.pop();
    }

括号分数升级版 {()}()[]
最长有效括号
判断链表是否有环

public static boolean hasCycle(ListNode node) {
        Set<ListNode> set = new HashSet<>();
        while (node != null) {
            boolean sus = set.add(node);
            if (!sus) {//HashSet有重复的添加会返回false
                return true;
            }
            node = node.next;
        }
        return false;
    }

//判断是否是环链，快慢指针
    private static boolean hasCycle2(ListNode head) {
        if (head == null || head.getNext() == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.getNext();
        while (slow != fast) {
            if (fast == null || fast.getNext() == null) {
                return false;
            }
            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }
        return true;
    }

二叉树前序，中序，后序遍历

public void preOrder(ListNode node) {
        if (node == null) return;
        System.out.println(node.getVal());
        preOrder(node.left);
        preOrder(node.right);
    }

public void inOrder(ListNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.println(node.getVal());
        inOrder(node.right);
    }

public void postOrder(ListNode node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.getVal());
    }

层序遍历

public static void levelSort(ListNode node) {
        Queue<ListNode> queue = new LinkedList<>();
        queue.add(node);
        int size = queue.size();

        StringBuilder levelPath = new StringBuilder();
        while (!queue.isEmpty()) {
            size--;
            ListNode n = queue.remove();
            levelPath.append(n.getVal().toString());
            if (n.left != null) {
                queue.add(n.left);
            }
            if (n.right != null) {
                queue.add(n.right);
            }
            if (size == 0) {
                size = queue.size();
                System.out.println(levelPath.toString());
                levelPath = new StringBuilder();
            }
        }
    }

打印所有树路径

public static void printAllPath(ListNode node) {
        Queue<ListNode> queue = new LinkedList<>();
        queue.add(node);

        Queue<String> pathQ = new LinkedList<>();
        pathQ.add(node.getVal().toString());

        List<String> pathList = new ArrayList<>();
        while (!queue.isEmpty()) {
            ListNode n = queue.remove();
            String path = pathQ.remove();
            
            if (n.left == null && n.right == null) {
                pathList.add(path);//叶子节点
            } else {
                if (n.left != null) {
                    queue.add(n.left);
                    pathQ.add(path + n.left.val);
                }
                if (n.right != null) {
                    queue.add(n.right);
                    pathQ.add(path + n.right.val);
                }
            }
        }

        System.out.println(pathList.toString());
    }

一个字符串里最长不重复子串
一个字符串里最长不重复子串的长度
最大连续数之和
最大子序和
买卖股票的最佳时机
不用Math函数实现开根
接雨水
数组里两数之和等于给定的值

static int[] twoNumSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{nums[i], nums[j]};
                }
            }
        }
        return new int[]{};
    }

static int[] twoNumSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer num = target - nums[i];
            Integer n = map.get(num);
            if (n != null) {
                return new int[]{nums[i], n};
            } else {
                map.put(nums[i], nums[i]);
            }
        }
        return new int[]{};
    }

三数之和

public static void threeSum(int[] nums, int k) {
        if (nums == null || nums.length < 3) {
            return;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int target = k - nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    System.out.println(nums[i] + "+" + nums[left] + "+" + nums[right] + "=" + k);
                    break;
                } else if (nums[left] + nums[right] > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }
    }

柱形图最大面积
最大矩形面积
最大正方形面积
二分查找法

//时间复杂度O(log2n)
static int binarySerach(int[] nums, int key) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (key > nums[mid]) {
                left = mid + 1;
            } else if (key < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
    }

爬楼梯
将两个升序链表合并为一个新的 升序 链表并返回
两线程分别打印奇偶数
三线程顺序打印ABC
10个线程打印1~100，打印要从小到大
字符串转数值
环形数组，数组里从第n个位置开始往往后移动，n最终到数组的第一位置
LinkedHashMap 实现 LRU
滑动窗口代码实现
漏桶、令牌桶代码实现
分发糖果
不用Math函数开根

设计个抢红包算法