精华内容
下载资源
问答
  • 用来记录我们刷LeetCode题目时候的心酸...编程语言使用Golang,代码风格上面并没有强制的采用什么编码规范,毕竟是算法解题,只需要代码清晰易懂就可以了。 鉴于个人精力时间有限,可能并不会完全最优解,请多多见谅。
  • Android面试算法题

    2012-03-12 18:06:40
    该资源为Android开发工程师面试算法题,为基础知识具备比较好的人提供。
  • 面试算法题总结
  • 大厂面试算法100

    2020-10-31 15:23:04
    收集来自微软,百度,腾讯等一线互联网企业关于算法的100道面试题,希望对大家有帮助.更多面试相关资料也可以找我.我设置的是0积分,但是老被系统改,如果需要积分才能下载可以私信我.....
  • 面试常见算法题

    2018-05-17 17:20:12
    这是在面试中遇到的一些常见算法题,笔试面试经常遇到,所以总结了一下,方面以后查看,分享给大家。
  • c语言面试算法题

    2017-08-30 05:17:02
    面试中遇到的算法题,不是算法的总结
  • 2017年12月份头条技术(实习)算法面试题,三道任选其二,40分钟内bugfree撸出来,能执行
  • 排序 比较排序 冒泡排序 归并排序 快速排序 线性排序 计数排序 桶排序 二叉树 顺序遍历 层次遍历 左右翻转 最大值 最大深度 最小深度 平衡二叉树 链表 删除节点 翻转链表 ...堆 / 优先队.
     
    

    排序

    比较排序

    冒泡排序

    重复地走访过要排序的数列,每次比较相邻两个元素,如果它们的顺序错误就把它们交换过来,越大的元素会经由交换慢慢“浮”到数列的尾端。

    public void bubbleSort(int[] arr) {
        int temp = 0;
        boolean swap;
        for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
            // 增加一个swap的标志,当前一轮没有进行交换时,说明数组已经有序
            swap = false;
            for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap){
                break;
            }
        }
    }
    

    归并排序

    分解待排序的数组成两个各具 n/2 个元素的子数组,递归调用归并排序两个子数组,合并两个已排序的子数组成一个已排序的数组。

    public void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        internalMergeSort(arr, temp, 0, arr.length - 1);
    }
    
    private void internalMergeSort(int[] arr, int[] temp, int left, int right) {
        // 当left == right时,不需要再划分
        if (left < right) {
            int mid = (left + right) / 2;
            internalMergeSort(arr, temp, left, mid);
            internalMergeSort(arr, temp, mid + 1, right);
            mergeSortedArray(arr, temp, left, mid, right);
        }
    }
    
    // 合并两个有序子序列
    public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 把temp数据复制回原数组
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
    

    快速排序

    在待排序的数组选取一个元素作为基准,将待排序的元素进行分区,比基准元素大的元素放在一边,比其小的放另一边,递归调用快速排序对两边的元素排序。选取基准元素并分区的过程采用双指针左右交换。

    public void quickSort(int[] arr){
        quickSort(arr, 0, arr.length-1);
    }
    
    private void quickSort(int[] arr, int low, int high){
        if (low >= high)
            return;
        int pivot = partition(arr, low, high);        //将数组分为两部分
        quickSort(arr, low, pivot - 1);                   //递归排序左子数组
        quickSort(arr, pivot + 1, high);                  //递归排序右子数组
    }
    
    private int partition(int[] arr, int low, int high){
        int pivot = arr[low];     //基准
        while (low < high){
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];             //交换比基准大的记录到左端
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];           //交换比基准小的记录到右端
        }
        //扫描完成,基准到位
        arr[low] = pivot;
        //返回的是基准的位置
        return low;
    }
    

    线性排序

    计数排序

    根据待排序的数组中最大和最小的元素,统计数组中每个值为i的元素出现的次数,存入数组C的第i项,对所有的计数累加,然后反向填充目标数组。

    public void countSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
    
        int[] b = new int[arr.length]; // 存储数组
        int[] count = new int[max - min + 1]; // 计数数组
    
        for (int num = min; num <= max; num++) {
            // 初始化各元素值为0,数组下标从0开始因此减min
            count[num - min] = 0;
        }
    
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            count[num - min]++; // 每出现一个值,计数数组对应元素的值+1
            // 此时count[i]表示数值等于i的元素的个数
        }
    
        for (int i = min + 1; i <= max; i++) {
            count[i - min] += count[i - min - 1];
            // 此时count[i]表示数值<=i的元素的个数
        }
    
        for (int i = 0; i < arr.length; i++) {
                int num = arr[i]; // 原数组第i位的值
                int index = count[num - min] - 1; //加总数组中对应元素的下标
                b[index] = num; // 将该值存入存储数组对应下标中
                count[num - min]--; // 加总数组中,该值的总和减少1。
        }
    
        // 将存储数组的值替换给原数组
        for(int i=0; i < arr.length;i++){
            arr[i] = b[i];
        }
    }
    

    桶排序

    找出待排序数组中的最大值max、最小值min,数组ArrayList作为桶,桶里放的元素用ArrayList存储。计算每个元素 arr[i] 放的桶,每个桶各自排序,遍历桶数组,把排序好的元素放进输出数组。

    public static void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 桶数
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                arr[j] = bucketArr.get(i).get(j);
            }
        }
    }
    

    二叉树

    class TreeNode {
        public TreeNode left, right;
        public int val;
    
        public TreeNode(int val) {
            this.val = val;
        }
    }
    

    顺序遍历

    先序遍历: 根->左->右
    中序遍历: 左->根->右
    后序遍历: 左->右->根

    // 先序遍历
    public void preTraverse(TreeNode root) {
        if (root != null) {
            System.out.println(root.val);
            preTraverse(root.left);
            preTraverse(root.right);
        }
    }
    
    // 中序遍历
    public void inTraverse(TreeNode root) {
        if (root != null) {
            inTraverse(root.left);
            System.out.println(root.val);
            inTraverse(root.right);
        }
    }
    
    // 后序遍历
    public void postTraverse(TreeNode root) {
        if (root != null) {
            postTraverse(root.left);
            postTraverse(root.right);
            System.out.println(root.val);
        }
    }
    

    层次遍历

    // 层次遍历(DFS)
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        
        dfs(root, res, 0);
        return res;
    }
    
    private void dfs(TreeNode root, List<List<Integer>> res, int level) {
        if (root == null) {
            return;
        }
        if (level == res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        
        dfs(root.left, res, level + 1);
        dfs(root.right, res, level + 1);
    }
    
    // 层次遍历(BFS)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List result = new ArrayList();
    
        if (root == null) {
            return result;
        }
    
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
    
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode head = queue.poll();
                level.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                }
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            result.add(level);
        }
    
        return result;
    }
    
    // "Z"字遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (root == null){
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isFromLeft = false;
        while(!queue.isEmpty()){
            int size = queue.size();
            isFromLeft = !isFromLeft;
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode node;
                if (isFromLeft){
                    node = queue.pollFirst();
                }else{
                    node = queue.pollLast();
                }
                list.add(node.val);
                
                if (isFromLeft){
                    if (node.left != null){
                        queue.offerLast(node.left);
                    }
                    if (node.right != null){
                        queue.offerLast(node.right);
                    }
                }else{
                    if (node.right != null){
                        queue.offerFirst(node.right);
                    }
                    if (node.left != null){
                        queue.offerFirst(node.left);
                    }
                }
            }
            result.add(list);
        }
        
        return result;
    }
    

    左右翻转

    public void invert(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        invert(root.left);
        invert(root.right);
    }
    

    最大值

    public int getMax(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        } else {
            int left = getMax(root.left);
            int right = getMax(root.right);
            return Math.max(Math.max(left, rigth), root.val);
        }
    }
    

    最大深度

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
    
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
    

    最小深度

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        
        if (left == 0) {
            return right + 1;
        } else if (right == 0) {
            return left + 1;
        } else {
            return Math.min(left, right) + 1;
        }
    }
    

    平衡二叉树

    平衡二叉树每一个节点的左右两个子树的高度差不超过1

    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) != -1;
    }
    
    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
    
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
    

    链表

    public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) {
             val = x;
             next = null;
        }
    }
    

    删除节点

    public void deleteNode(ListNode node) {
        if (node.next == null){
            node = null;
            return;
        }
        // 取缔下一节点
        node.val = node.next.val
        node.next = node.next.next
    }
    

    翻转链表

    public ListNode reverse(ListNode head) {
        //prev表示前继节点
        ListNode prev = null;
        while (head != null) {
            //temp记录下一个节点,head是当前节点
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    

    中间元素

    public ListNode findMiddle(ListNode head){
        if(head == null){
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // fast.next = null 表示 fast 是链表的尾节点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    

    判断是否为循环链表

    public Boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
    
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != slow) {
            if(fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        } 
        return true;
    }
    

    合并两个已排序链表

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode lastNode = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                lastNode.next = l1;
                l1 = l1.next;
            } else {
                lastNode.next = l2;
                l2 = l2.next;
            }
            lastNode = lastNode.next;
        }
        
        if (l1 != null) {
            lastNode.next = l1;
        } else {
            lastNode.next = l2;
        }
        
        return dummy.next;
    }
    

    链表排序

    可利用归并、快排等算法实现

    // 归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
    
        ListNode mid = findMiddle(head);
    
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
    
        return mergeTwoLists(left, right);
    }
    
    // 快速排序
    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }
    
    private void quickSort(ListNode start, ListNode end) {
        if (start == end) {
            return;
        }
        
        ListNode pt = partition(start, end);
        quickSort(start, pt);
        quickSort(pt.next, end);
    }
    
    private ListNode partition(ListNode start, ListNode end) {
        int pivotKey = start.val;
        ListNode p1 = start, p2 = start.next;
        while (p2 != end) {
            if (p2.val < pivotKey) {
                p1 = p1.next;
                swapValue(p1, p2);
            }
            p2 = p2.next;
        }
        
        swapValue(start, p1);
        return p1;
    }
    
    private void swapValue(ListNode node1, ListNode node2) {
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
    

    删除倒数第N个节点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode preDelete = dummy;
        for (int i = 0; i < n; i++) {
            if (head == null) {
                return null;
            }
            head = head.next;
        }
        // 此时head为正数第N个节点
        while (head != null) {
            head = head.next;
            preDelete = preDelete.next;
        }
        preDelete.next = preDelete.next.next;
        return dummy.next;
    }
    

    两个链表是否相交

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
    
        ListNode currA = headA;
        ListNode currB = headB;
        int lengthA = 0;
        int lengthB = 0;
    
        // 让长的先走到剩余长度和短的一样
        while (currA != null) {
            currA = currA.next;
            lengthA++;
        }
        while (currB != null) {
            currB = currB.next;
            lengthB++;
        }
    
        currA = headA;
        currB = headB;
        while (lengthA > lengthB) {
            currA = currA.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            currB = currB.next;
            lengthB--;
        }
        
        // 然后同时走到第一个相同的地方
        while (currA != currB) {
            currA = currA.next;
            currB = currB.next;
        }
        // 返回交叉开始的节点
        return currA;
    }
    

    栈 / 队列

    带最小值操作的栈

    实现一个栈, 额外支持一个操作:min() 返回栈中元素的最小值

    public class MinStack {
        private Stack<Integer> stack;
        private Stack<Integer> minStack; // 维护一个辅助栈,传入当前栈的最小值
        
        public MinStack() {
            stack = new Stack<Integer>();
            minStack = new Stack<Integer>();
        }
    
        public void push(int number) {
            stack.push(number);
            if (minStack.isEmpty()) {
                minStack.push(number);
            } else {
                minStack.push(Math.min(number, minStack.peek()));
            }
        }
    
        public int pop() {
            minStack.pop();
            return stack.pop();
        }
    
        public int min() {
            return minStack.peek();
        }
    }
    

    有效括号

    给定一个字符串所表示的括号序列,包含以下字符: ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, 判定是否是有效的括号序列。括号必须依照 “()” 顺序表示, “()[]{}” 是有效的括号,但 “([)]” 则是无效的括号。

    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (Character c : s.toCharArray()) {
            if ("({[".contains(String.valueOf(c))) {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && isValid(stack.peek(), c)) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    
    private boolean isValid(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
            || (c1 == '[' && c2 == ']');
    }
    

    用栈实现队列

    public class MyQueue {
        private Stack<Integer> outStack;
        private Stack<Integer> inStack;
    
        public MyQueue() {
           outStack = new Stack<Integer>();
           inStack = new Stack<Integer>();
        }
        
        private void in2OutStack(){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        
        public void push(int element) {
            inStack.push(element);
        }
    
        public int pop() {
            if(outStack.isEmpty()){
                this.in2OutStack();
            }
            return outStack.pop();
        }
    
        public int top() {
            if(outStack.isEmpty()){
                this.in2OutStack();
            }
            return outStack.peek();
        }
    }
    

    逆波兰表达式求值

    在反向波兰表示法中计算算术表达式的值, [“2”, “1”, “+”, “3”, “*”] -> (2 + 1) * 3 -> 9

    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack<Integer>();
        String operators = "+-*/";
        for (String token : tokens) {
            if (!operators.contains(token)) {
                s.push(Integer.valueOf(token));
                continue;
            }
    
            int a = s.pop();
            int b = s.pop();
            if (token.equals("+")) {
                s.push(b + a);
            } else if(token.equals("-")) {
                s.push(b - a);
            } else if(token.equals("*")) {
                s.push(b * a);
            } else {
                s.push(b / a);
            }
        }
        return s.pop();
    }
    

    二分

    二分搜索

    public int binarySearch(int[] arr, int start, int end, int hkey){
        if (start > end) {
            return -1;
        }
    
        int mid = start + (end - start) / 2;    //防止溢位
        if (arr[mid] > hkey) {
            return binarySearch(arr, start, mid - 1, hkey);
        }
        if (arr[mid] < hkey) {
            return binarySearch(arr, mid + 1, end, hkey);
        } 
        return mid;  
    }
    

    X的平方根

    public int sqrt(int x) {
        if (x < 0)  {
            throw new IllegalArgumentException();
        } else if (x <= 1) {
            return x;
        }
    
        int start = 1, end = x;
        // 直接对答案可能存在的区间进行二分 => 二分答案
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (mid == x / mid) {
                return mid;
            }  else if (mid < x / mid) {
                start = mid;
            } else {
                end = mid;
            }  
        }
        if (end > x / end) {
            return start;
        }
        return end;
    }
    

    哈希表

    两数之和

    给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。需要实现的函数twoSum需要返回这两个数的下标。

    用一个hashmap来记录,key记录target-numbers[i]的值,value记录numbers[i]的i的值,如果碰到一个
    numbers[j]在hashmap中存在,那么说明前面的某个numbers[i]和numbers[j]的和为target,i和j即为答案

    public int[] twoSum(int[] numbers, int target) {
    
        HashMap<Integer,Integer> map = new HashMap<>();
    
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                return new int[]{map.get(numbers[i]), i};
            }
            map.put(target - numbers[i], i);
        }
    
        return new int[]{};
    }
    

    连续数组

    给一个二进制数组,找到 0 和 1 数量相等的子数组的最大长度

    使用一个数字sum维护到i为止1的数量与0的数量的差值。在loop i的同时维护sum并将其插入hashmap中。对于某一个sum值,若hashmap中已有这个值,则当前的i与sum上一次出现的位置之间的序列0的数量与1的数量相同。

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> prefix = new HashMap<>();
        int sum = 0;
        int max = 0;
        prefix.put(0, -1); // 当第一个0 1数量相等的情况出现时,数组下标减去-1得到正确的长度
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num == 0) {
                sum--;
            } else {
                sum++;
            }
            
            if (prefix.containsKey(sum)) {
                max = Math.max(max, i - prefix.get(sum));
            } else {
                prefix.put(sum, i);
            }
        }
        
        return max;
    }
    

    最长无重复字符的子串

    用HashMap记录每一个字母出现的位置。设定一个左边界, 到当前枚举到的位置之间的字符串为不含重复字符的子串。若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int max = Integer.MIN_VALUE;
        int start = -1; // 计算无重复字符子串开始的位置
        int current = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                int tmp = map.get(s.charAt(i));
                if (tmp >= start) { // 上一次的位置在左边界右边, 则需要向右移动左边界
                    start = tmp;
                }
            } 
            
            map.put(s.charAt(i), i);
            max = Math.max(max, i - start);
        }
        return max;
    }
    

    最多点在一条直线上

    给出二维平面上的n个点,求最多有多少点在同一条直线上

    class Point {
        int x;
        int y;
        Point() { 
            x = 0; y = 0; 
        }
        Point(int a, int b) { 
            x = a; y = b; 
        }
    }
    

    通过HashMap记录下两个点之间的斜率相同出现的次数,注意考虑点重合的情况

    public int maxPoints(Point[] points) {
        if (points == null) {
            return 0;
        }
        
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Double, Integer> map = new HashMap<>();
            int maxPoints = 0;
            int overlap = 0;
            for (int j = i + 1; j < points.length; j++) {
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    overlap++; // 两个点重合的情况记录下来
                    continue;
                }
                double rate = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
                if (map.containsKey(rate)) {
                    map.put(rate, map.get(rate) + 1);
                } else {
                    map.put(rate, 2);
                }
                maxPoints = Math.max(maxPoints, map.get(rate));
            }
            if (maxPoints == 0) maxPoints = 1;
            max = Math.max(max, maxPoints + overlap);
        }
        return max;
    }
    

    堆 / 优先队列

    前K大的数

    // 维护一个 PriorityQueue,以返回前K的数
    public int[] topk(int[] nums, int k) {
        int[] result = new int[k];
        if (nums == null || nums.length < k) {
            return result;
        }
        
        Queue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.add(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.poll(); 
        }
        
        return result;
    }
    

    前K大的数II

    实现一个数据结构,提供下面两个接口:1.add(number) 添加一个元素 2.topk() 返回前K大的数

    public class Solution {
        private int maxSize;
        private Queue<Integer> minheap;
        public Solution(int k) {
            minheap = new PriorityQueue<>();
            maxSize = k;
        }
    
        public void add(int num) {
            if (minheap.size() < maxSize) {
                minheap.offer(num);
                return;
            }
            
            if (num > minheap.peek()) {
                minheap.poll();
                minheap.offer(num);
            }
        }
    
        public List<Integer> topk() {
            Iterator it = minheap.iterator();
            List<Integer> result = new ArrayList<Integer>();
            while (it.hasNext()) {
                result.add((Integer) it.next());
            }
            Collections.sort(result, Collections.reverseOrder());
            return result;
        }
    }
    

    第K大的数

    public int kthLargestElement(int k, int[] nums) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
            return -1;
        }
        return partition(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int partition(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[k];
        }
        
        int left = start, right = end;
        int pivot = nums[(start + end) / 2];
        
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        
        if (k <= right) {
            return partition(nums, start, right, k);
        }
        if (k >= left) {
            return partition(nums, left, end, k);
        }
        return nums[k];
    }    
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    

    二叉搜索树

    验证二叉搜索树

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long min, long max){
        if (root == null) {
            return true;
        }
        
        if (root.val <= min || root.val >= max){
            return false;
        }
        
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
    

    第K小的元素

    增加getCount方法来获取传入节点的子节点数(包括自己),从root节点开始判断k值和子节点数的大小决定递归路径是往左还是往右。

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        
        int leftCount = getCount(root.left);
        if (leftCount >= k) {
            return kthSmallest(root.left, k);
        } else if (leftCount + 1 == k) {
            return root.val;
        } else {
            return kthSmallest(root.right, k - leftCount - 1);
        }
    }
    
    private int getCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return getCount(root.left) + getCount(root.right) + 1;
    }
    

    数组 / 双指针

    加一

    给定一个非负数,表示一个数字数组,在该数的基础上+1,返回一个新的数组。该数字按照数位高低进行排列,最高位的数在列表的最前面。

    public int[] plusOne(int[] digits) {
        int carries = 1;
        for(int i = digits.length - 1; i >= 0 && carries > 0; i--){  
            int sum = digits[i] + carries;
            digits[i] = sum % 10;
            carries = sum / 10;
        }
        if(carries == 0) {
            return digits;
        }
            
        int[] rst = new int[digits.length + 1];
        rst[0] = 1;
        for(int i = 1; i < rst.length; i++){
            rst[i] = digits[i - 1];
        }
        return rst;
    }
    

    删除元素

    给定一个数组和一个值,在原地删除与值相同的数字,返回新数组的长度。

    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int index = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != elem) {
                A[index++] = A[i];
            } 
        }
        
        return index;
    }
    

    删除排序数组中的重复数字

    在原数组中“删除”重复出现的数字,使得每个元素只出现一次,并且返回“新”数组的长度。

    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int size = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != A[size]) {
                A[++size] = A[i];
            }
        }
        return size + 1;
    }
    

    我的日程安排表 I

    实现MyCalendar类来存储活动。如果新添加的活动没有重复,则可以添加。类将有方法book(int start,int end)。这代表左闭右开的间隔[start,end)有了预定,范围内的实数x,都满足start <= x < end,返回true。 否则,返回false,并且事件不会添加到日历中。

    TreeMap 是一个有序的key-value集合,它通过 红黑树 实现,继承于AbstractMap,所以它是一个Map,即一个key-value集合。TreeMap可以查询小于等于某个值的最大的key,也可查询大于等于某个值的最小的key。
    元素的顺序可以改变,并且对新的数组不会有影响。

    class MyCalendar {
        TreeMap<Integer, Integer> calendar;
    
        MyCalendar() {
            calendar = new TreeMap();
        }
    
        public boolean book(int start, int end) {
            Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);
            if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {
                calendar.put(start, end);
                return true;
            }
            return false;
        }
    }
    

    合并排序数组

    合并两个排序的整数数组A和B变成一个新的数组。可以假设A具有足够的空间去添加B中的元素。

    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        int i = m - 1, j = n - 1, index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }
        while (i >= 0) {
            A[index--] = A[i--];
        }
        while (j >= 0) {
            A[index--] = B[j--];
        }
    }
    

    贪心

    买卖股票的最佳时机

    假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
    
        int min = Integer.MAX_VALUE;  //记录最低的价格
        int profit = 0;
        for (int price : prices) {
            min = Math.min(price, min);
            profit = Math.max(price - min, profit);
        }
    
        return profit;
    }
    

    买卖股票的最佳时机 II

    给定一个数组 prices 表示一支股票每天的价格。可以完成任意次数的交易, 不过不能同时参与多个交易,设计一个算法求出最大的利润。

    贪心:只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润。

    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            int diff = prices[i + 1] - prices[i];
            if (diff > 0) {
                profit += diff;
            }
        }
        return profit;
    }
    

    最大子数组

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        //max记录全局最大值,sum记录区间和,如果当前sum>0,那么可以继续和后面的数求和,否则就从0开始
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
    
        return max;
    }
    

    主元素

    给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一(可以假设数组非空,且数组中总是存在主元素)。

    public int majorityNumber(List<Integer> nums) {
        int currentMajor = 0;
        int count = 0;
    
        for(Integer num : nums) {
            if(count == 0) {
                currentMajor = num;
            }
            
            if(num == currentMajor) {
                count++;
            } else {
                count--;
            }
        }
        return currentMajor;
    }
    

    字符串处理

    生成括号

    给定 n,表示有 n 对括号, 请写一个函数以将其生成所有的括号组合,并返回组合结果。

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(n, n, "", res);
        return res;
    }
    
    // DFS
    private void helper(int nL, int nR, String parenthesis, List<String> res) {
        // nL 和 nR 分别代表左右括号剩余的数量
        if (nL < 0 || nR < 0) {
            return;
        }
        
        if (nL == 0 && nR == 0) {
            res.add(parenthesis);
            return;
        }
        helper(nL - 1, nR, parenthesis + "(", res);
        if (nL >= nR) {
            return;
        }
        helper(nL, nR - 1, parenthesis + ")", res);
    }
    

    Excel表列标题

    给定一个正整数,返回相应的列标题,如Excel表中所示。如1 -> A,2 -> B…26 -> Z,27 -> AA

    public String convertToTitle (int n) {
        StringBuilder str = new StringBuilder();
    
        while (n > 0) {
            n--;
            str.append ( (char) ( (n % 26) + 'A'));
            n /= 26;
        }
        return str.reverse().toString();
    }
    

    翻转游戏

    翻转游戏:给定一个只包含两种字符的字符串:+和-,你和你的小伙伴轮流翻转"++“变成”–"。当一个人无法采取行动时游戏结束,另一个人将是赢家。编写一个函数,计算字符串在一次有效移动后的所有可能状态。

    public List<String> generatePossibleNextMoves (String s) {
        List list = new ArrayList();
        for (int i = -1; (i = s.indexOf ("++", i + 1)) >= 0;) {
            list.add (s.substring (0, i) + "--" + s.substring (i + 2));
        }
        return list;
    }
    

    翻转字符串中的单词

    给定一个字符串,逐个翻转字符串中的每个单词。

    public String reverseWords(String s) {
        if(s.length() == 0 || s == null){
            return " ";
        }
        //按照空格将s切分
        String[] array = s.split(" ");
        StringBuilder sb = new StringBuilder();
        //从后往前遍历array,在sb中插入单词
        for(int i = array.length - 1; i >= 0; i--){
            if(!array[i].equals("")) {
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                
                sb.append(array[i]);
            }
        }
        return sb.toString();
    }
    

    转换字符串到整数

    实现atoi这个函数,将一个字符串转换为整数。如果没有合法的整数,返回0。如果整数超出了32位整数的范围,返回INT_MAX(2147483647)如果是正整数,或者INT_MIN(-2147483648)如果是负整数。

    public int myAtoi(String str) {
        if(str == null) {
            return 0;
        }
        str = str.trim();
        if (str.length() == 0) {
            return 0;
        }
            
        int sign = 1;
        int index = 0;
    
        if (str.charAt(index) == '+') {
            index++;
        } else if (str.charAt(index) == '-') {
            sign = -1;
            index++;
        }
        long num = 0;
        for (; index < str.length(); index++) {
            if (str.charAt(index) < '0' || str.charAt(index) > '9') {
                break;
            }
            num = num * 10 + (str.charAt(index) - '0');
            if (num > Integer.MAX_VALUE ) {
                break;
            }
        }   
        if (num * sign >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (num * sign <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int)num * sign;
    }
    

    最长公共前缀

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++) {
            int j = 0;
            while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
                j++;
            }
            if( j == 0) {
                return "";
            }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
    

    回文数

    判断一个正整数是不是回文数。回文数的定义是,将这个数反转之后,得到的数仍然是同一个数。

    public boolean palindromeNumber(int num) {
        // Write your code here
        if(num < 0){
            return false;
        }
        int div = 1;
        while(num / div >= 10){
            div *= 10;
        }
        while(num > 0){
            if(num / div != num % 10){
                return false;
            }
            num = (num % div) / 10;
            div /= 100;
        }
        return true;
    }
    

    动态规划

    单词拆分

    给定字符串 s 和单词字典 dict,确定 s 是否可以分成一个或多个以空格分隔的子串,并且这些子串都在字典中存在。

    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here
        int maxLength = getMaxLength(dict);
        
        // 长度为n的单词 有n + 1个切割点 比如: _l_i_n_t_
        boolean[] canBreak = new boolean[s.length() + 1];
        // 当s长度为0时
        canBreak[0] = true;
        
        for(int i = 1; i < canBreak.length; i++){
            for(int j = 1; j <= maxLength && j <= i; j++){
                //i - j 表示从 i 点开始往前j个点的位置
                String str = s.substring(i - j,i);
                //如果此str在词典中 并且 str之前的 字符串可以拆分     
                if(dict.contains(str) && canBreak[i - j]){
                    canBreak[i] = true;
                    break;
                }
            }
        }
        
        return canBreak[canBreak.length - 1];
    }
    
    private int getMaxLength(Set<String> dict){
        int max = 0;
        for(String s : dict){
            max = Math.max(max,s.length());
        }
        return max;
    }
    

    爬楼梯

    假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

    public int climbStairs(int n) {
        if (n == 0) return 0;
        int[] array = new int[n + 1];
        array[0] = 1;
        if (array.length > 1) {
            array[1] = 1;
        }
        
        for(int i = 2; i < array.length; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }
    

    打劫房屋

    假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警。给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,在不触动报警装置的情况下, 你最多可以得到多少钱 。

    public long houseRobber(int[] A) {
        if (A.length == 0) return 0;
        long[] res = new long[A.length + 1];
        res[0] = 0;
        res[1] = A[0];
        for (int i = 2; i < res.length; i++) {
            res[i] = Math.max(res[i - 2] + A[i - 1], res[i - 1]);
        }
        return res[A.length];
    }
    

    编辑距离

    给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。你总共三种操作方法:插入一个字符、删除一个字符、替换一个字符。

    public int minDistance(String word1, String word2) {
        // write your code here
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++){
            dp[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++){
            dp[0][j] = j;
        }
        for (int i = 1; i< n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return  dp[n][m];
    }
    

    乘积最大子序列

    public int maxProduct(List<Integer> nums) {
        // 分别记录正数最大值和负数最小值
        int[] max = new int[nums.size()];
        int[] min = new int[nums.size()];
        
        min[0] = max[0] = nums.get(0);
        int result = nums.get(0);
        for (int i = 1; i < nums.size(); i++) {
            min[i] = max[i] = nums.get(i);
            if (nums.get(i) > 0) {
                max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
                min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
            } else if (nums.get(i) < 0) {
                max[i] = Math.max(max[i], min[i - 1] * nums.get(i));
                min[i] = Math.min(min[i], max[i - 1] * nums.get(i));
            }
            
            result = Math.max(result, max[i]);
        }
        
        return result;
    }
    

    矩阵

    螺旋矩阵

    给定一个包含 m x n 个要素的矩阵,(m 行, n 列),按照螺旋顺序,返回该矩阵中的所有要素。

    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> rst = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0) {
            return rst;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;
        while(count * 2 < rows && count * 2 < cols){
            for (int i = count; i < cols - count; i++) {
                rst.add(matrix[count][i]);
            }
            
            for (int i = count + 1; i < rows - count; i++) {
                rst.add(matrix[i][cols - count - 1]);
            }
            
            if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列
                break;
            }
                
            for (int i = cols - count - 2; i >= count; i--) {
                rst.add(matrix[rows - count - 1][i]);
            }
                
            for (int i = rows - count - 2; i >= count + 1; i--) {
                rst.add(matrix[i][count]);
            }
            
            count++;
        }
        return rst;
    }
    

    判断数独是否合法

    请判定一个数独是否有效。该数独可能只填充了部分数字,其中缺少的数字用 . 表示。

    维护一个HashSet用来记同一行、同一列、同一九宫格是否存在相同数字

    public boolean isValidSudoku(char[][] board) {
        Set seen = new HashSet();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                char number = board[i][j];
                if (number != '.')
                    if (!seen.add(number + " in row " + i) ||
                        !seen.add(number + " in column " + j) ||
                        !seen.add(number + " in block " + i / 3 + "-" + j / 3))
                        return false;
            }
        }
        return true;
    }
    

    旋转图像

    给定一个N×N的二维矩阵表示图像,90度顺时针旋转图像。

    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
    
        int length = matrix.length;
    
        for (int i = 0; i < length / 2; i++) {
            for (int j = 0; j < (length + 1) / 2; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[length - j - 1][i];
                matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
                matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
                matrix[j][length - i - 1] = tmp;
            }
        }   
    }
    

    二进制 / 位运算

    落单的数

    给出 2 * n + 1个数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。

    异或运算具有很好的性质,相同数字异或运算后为0,并且具有交换律和结合律,故将所有数字异或运算后即可得到只出现一次的数字。

    public int singleNumber(int[] A) {
        if(A == null || A.length == 0) {
            return -1;
        }
        int rst = 0;
        for (int i = 0; i < A.length; i++) {
            rst ^= A[i];
        }
        return rst;
    }
    

    格雷编码

    格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个二进制的差异。给定一个非负整数 n ,表示该代码中所有二进制的总数,请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始,并覆盖所有的 2n 个整数。例子——输入:2;输出:[0, 1, 3, 2];解释: 0 - 00,1 - 01,3 - 11,2 - 10

    格雷码生成公式:G(i) = i ^ (i >> 2)

    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < (1 << n); i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
    

    其他

    反转整数

    将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 (标记为 32 位整数)。

    public int reverseInteger(int n) {
        int reversed_n = 0;
        
        while (n != 0) {
            int temp = reversed_n * 10 + n % 10;
            n = n / 10;
            if (temp / 10 != reversed_n) {
                reversed_n = 0;
                break;
            }
            reversed_n = temp;
        }
        return reversed_n;
    }
    

    LRU缓存策略

    为最近最少使用(LRU)缓存策略设计一个数据结构,它应该支持以下操作:获取数据(get)和写入数据(set)。获取数据get(key):如果缓存中存在key,则获取其数据值(通常是正数),否则返回-1。 写入数据set(key, value):如果key还没有在缓存中,则写入其数据值。当缓存达到上限,它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。

    public class LRUCache {
        private class Node{
            Node prev;
            Node next;
            int key;
            int value;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
                this.prev = null;
                this.next = null;
            }
        }
    
        private int capacity;
        private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
        private Node head = new Node(-1, -1);
        private Node tail = new Node(-1, -1);
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            tail.prev = head;
            head.next = tail;
        }
    
        public int get(int key) {
            if( !hs.containsKey(key)) {    		//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);			//每次get,使用次数+1,最近使用,放于尾部
    
            return hs.get(key).value;
        }
    
        public void set(int key, int value) {			//数据放入缓存
            // get 这个方法会把key挪到最末端,因此,不需要再调用 move_to_tail
            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;
        }
    }
    
    展开全文
  • 点击上方“五分钟学算法”,选择“星标”公众号重磅干货,第一时间送达前几天我去面试字节跳动,面试官问了一道链表相关的算法题,不过我第一时之间没做出来,就回来看了一下,感觉这道题还不错,拿来...

    点击上方“五分钟学算法”,选择“星标”公众号

    重磅干货,第一时间送达

    前几天我去面试字节跳动,面试官问了一道链表相关的算法题,不过我第一时之间没做出来,就回来看了一下,感觉这道题还不错,拿来讲一讲。

    题目

    这其实是一道变形的链表反转题,大致描述如下

    给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每K个节点之间为一组进行逆序,并且从链表的尾部开始组起,头部剩余节点数量不够一组的不需要逆序。(不能使用队列或者栈作为辅助)

    例如:
    链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8,3->4->5,1->2各位一组。调整后:1->2->5->4->3->8->7->6->null。其中 1,2不调整,因为不够一组。

    解答

    这道题的难点在于,是从链表的尾部开始组起的,而不是从链表的头部,如果是头部的话,那我们还是比较容易做的,因为你可以遍历链表,每遍历 k 个就拆分为一组来逆序。但是从尾部的话就不一样了,因为是单链表,不能往后遍历组起。不过这道题肯定是用递归比较好做,对递归不大懂的建议看我之前写的一篇文章身为技术专家的我,面试居然还要靠刷题?这篇文章写了关于递归的一些套路。

    先做一道类似的反转题

    在做这道题之前,我们不仿先来看看如果从头部开始组起的话,应该怎么做呢?例如:链表:1->2->3->4->5->6->7->8->null, K = 3。调整后:3->2->1->6->5->4->7->8->null。其中 7,8不调整,因为不够一组。

    这道题我们可以用递归来实现,假设方法reverseKNode()的功能是将单链表的每K个节点之间逆序(从头部开始组起的哦);reverse()方法的功能是将一个单链表逆序。

    那么对于下面的这个单链表,其中 K = 3。

    我们把前K个节点与后面的节点分割出来:

    temp指向的剩余的链表,可以说是原问题的一个子问题。

    我们可以调用reverseKNode()方法将temp指向的链表每K个节点之间进行逆序。

    再调用reverse()方法把head指向的那3个节点进行逆序,结果如下:

    接着,我们只需要把这两部分给连接起来就可以了。最后的结果如下:

    代码如下:

        //k个为一组逆序
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode temp = head;
            for (int i = 1; i < k && temp != null; i++) {
                temp = temp.next;
            }
            //判断节点的数量是否能够凑成一组
            if(temp == null)
                return head;
    
            ListNode t2 = temp.next;
            temp.next = null;
            //把当前的组进行逆序
            ListNode newHead = reverseList(head);
            //把之后的节点进行分组逆序
            ListNode newTemp = reverseKGroup(t2, k);
            // 把两部分连接起来
            head.next = newTemp;
    
            return newHead;
        }
    
        //逆序单链表
        private static ListNode reverseList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            ListNode result = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return result;
        }
    
    

    回到本题

    这两道题可以说是及其相似的了,只是一道从头部开始组起,这道从头部开始组起的,也是 leetcode 的第 25 题。而面试的时候,经常会进行变形,例如这道字节跳动的题,它变成从尾部开始组起,可能你一时之间就不知道该怎么弄了。当然,可能有人一下子就反应出来,把他秒杀了。

    其实这道题很好做滴,你只需要先把单链表进行一次逆序,逆序之后就能转化为从头部开始组起了,然后按照我上面的解法,处理完之后,把结果再次逆序即搞定。两次逆序相当于没逆序。

    例如对于链表(其中 K = 3)

    我们把它从尾部开始组起,每 K 个节点为一组进行逆序。

    步骤如下:

    1、先进行逆序

    逆序之后就可以把问题转化为从头部开始组起,每 K 个节点为一组进行逆序。

    2、处理后的结果如下

    3、接着在把结果逆序一次,结果如下

    代码如下:

    public ListNode solve(ListNode head, int k) {
        // 调用逆序函数
        head = reverse(head);
        // 调用每 k 个为一组的逆序函数(从头部开始组起)
        head = reverseKGroup(head, k);
        // 在逆序一次
        head = reverse(head);
        return head;
    
    }
    
    

    类似于这种需要先进行逆序的还要两个链表相加,这道题字节跳动的笔试题也有出过,如下图的第二题:

    这道题就需要先把两个链表逆序,再节点间相加,最后在合并了。

    总结

    关于链表的算法题,在面试的时候听说是挺常考的,大家可以多注意注意。


    推荐阅读

    •   吴师兄实名吐槽 LeetCode 上的一道题目。。。•   面试字节跳动时,我竟然遇到了原题……•   计算机专业的学生怎样练习编程才能把编程学精通?•   为什么 MySQL 使用 B+ 树•   一道简简单单的字节跳动算法面试题


    欢迎关注我的公众号“五分钟学算法”,如果喜欢,麻烦点一下“在看”~

    展开全文
  • 常见面试算法题

    2011-10-13 07:00:14
    招聘时常见的面试、笔试的算法数据结构、智力型问题。。。。。
  • 阿里云面试算法题

    千次阅读 2020-03-27 00:40:47
    面试题往往是让你写一个函数,实现某一个算法,往往是Leetcode的原,但是由于环境问题,有时候面试的题目并不能运行,是所谓的白板写。通常面试官也不会帮你写出函数头,所以难度提高了一些。 这看上去很简单...

    面试题往往是让你写一个函数,实现某一个算法,往往是Leetcode的原题,但是由于环境问题,有时候面试的题目并不能运行,是所谓的白板写。通常面试官也不会帮你写出函数头,所以难度提高了一些。

    这题看上去很简单,实际上暗藏玄机,如果在不能调试的情况下,第一次做这道题可能会陷入很多bug中。

    首先,一定要用一个数来处理进位,加1只在个位上进行,其他位置只处理进位。

    而且遍历的时候需要倒着遍历,这一点比较烦人。

    Python代码

    class Solution:
        def plusOne(self, digits: List[int]) -> List[int]:
            n = len(digits)
            add = 0
            for i in range(0,n):
                if i==0:
                    digits[n-i-1]+=1
                digits[n-i-1]+= add
                if digits[n-i-1]==10:
                    digits[n-i-1]=0
                    add = 1
                else:
                    add = 0
                    break
            
            if add==1:
                digits.insert(0,1)
    
            return digits

    当时面试官让我处理的是字符串加1,这个时候,最好是使用C语言的方式来写,因为这时候字符串运算比较好处理。

     

     

    class Solution:
        def numSquares(self, n: int) -> int:
            dp = [n for i in range(n+1)]
            dp[0] = 0
            dp[1] =1
            for i in range(1,n+1):
                for j in range(1,i+1):
                    if i>=j*j:
                        dp[i]=min(dp[i],dp[i-j*j]+1)
                    else:
                        break
            return dp[n]
    
    
    #dp[1]=1
    #dp[2]=2

     思考,输出这些完全平方数

     

    展开全文
  • 富途面试算法题

    千次阅读 2020-04-24 13:02:49
    判断数组是否是出栈顺序 #include <iostream> using namespace std; #include <vector> #include <stack>...//判断数组是否是出栈顺序 bool isStackOutRight(vector<...sOut, int ...

    判断数组是否是出栈顺序

    #include <iostream>
    using namespace std;
    #include <vector>
    #include <stack>
    //判断数组是否是出栈顺序
    bool isStackOutRight(vector<int>&sIn, vector<int>&sOut, int length) {
    	//辅助栈
    	stack<int>stackdata;
    	int index = 0;
    	for (int i = 0; i < length; i++) {
    		if (!stackdata.empty() && stackdata.top() == sOut[i]) {
    			stackdata.pop();
    		}
    		else {//辅助栈为空,或者不等于首元素,指向压栈操作
    			while (index < length && sIn[index] != sOut[i]) {
    				stackdata.push(sIn[index++]);
    			}
    			if (index == length) {
    				return false;
    			}
    			else {
    				index++;
    			}
    		}
    	}
    	return true;
    }
    

    股票的最大利润

    //一个数组找收益最大的买入和卖出点(股票的最大利润)
    int Maxdiff(vector<int>&v) {
    	int length = v.size();
    	if (v.empty() || length < 2) {
    		return 0;
    	}
    	int min = v[0];
    	int Maxdiff = v[1] - v[0];
    	int m = 0, n = 1;
    	for (int i = 2; i < length; i++) {
    		if (v[i - 1] < min) {
    			min = v[i - 1];
    			m = i - 1;
    		}
    		if (v[i] - min > Maxdiff) {
    			Maxdiff = v[i] - min;
    			n = i;
    		}
    	}
    	cout << m << " " << n << endl;
    	return Maxdiff;
    }
    
    int main() {
    	vector<int>v = { 9,11,8,5,7,12,16,14 };
    	int res = Maxdiff(v);
    	cout << res << endl;
    	system("pause");
    	return 0;
    }
    

    二叉排序树插入

    //二叉排序树插入
    struct TreeNode {
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int val) :val(val) {};
    };
    
    bool Insert(TreeNode *head, int key) {
    	if (head == nullptr) {
    		TreeNode *tmp = new TreeNode(key);
    		tmp->left = nullptr;
    		tmp->right = nullptr;
    	}
    	if (head->val < key) {
    		Insert(head->right, key);
    	}
    	else if (head->val > key) {
    		Insert(head->left, key);
    	}
    	else {
    		return false;
    	}
    	return true;
    }
    

    括号的匹配

    bool isValid(string s) {
    		map<char, char>mp;
    		mp.insert(make_pair(')', '('));
    		mp.insert(make_pair('}', '{'));
    		mp.insert(make_pair(']', '['));
    		stack<char>stk;
    		for (int i = 0; i < s.size(); i++) {
    			if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
    				stk.push(s[i]);
    			}
    			else if (s[i] == '}' || s[i] == ')' || s[i] == ']') {
    				if (stk.top() == mp[s[i]]) {
    					stk.pop();
    				}
    				else {
    					return false;
    				}
    			}
    		}
    		if (stk.empty()) {
    			return true;
    		}
    	}
    };
    

    死锁的例子

    #include <iostream>
    #include <thread>
    #include <mutex>
    //#include <unistd.h>
    #include <windows.h>
    using namespace std;
    mutex mt1, mt2;
    static int data1 = 1, data2 = 1;
    void a2() {
    	mt2.lock();
    	data1++;
    	cout << " a2 " << data1 << endl;
    	Sleep(1);
    	mt1.lock();  //此时a1已经对mt1上锁,所以要等待
    	data2++;
    	mt1.unlock();
    	mt2.unlock();
    }
    void a1() {
    	mt1.lock();
    	data2++;
    	cout << " a1 " << data2 << endl;
    	Sleep(1);
    	mt2.lock();  //此时a2已经对mt2上锁,所以要等待
    	data1++;
    	mt2.unlock();
    	mt1.unlock();
    }
    
    int main() {
    	//int data = 1;
    	thread t2(a2);
    	thread t1(a1);
    	t1.join();
    	t2.join();
    	cout << "main here" << endl;  //要t1线程、t2线程都执行完毕后才会执行
    	system("pause");
    	return 0;
    }
    

    随机打乱有序数组

    洗牌算法
    https://blog.csdn.net/qq_26399665/article/details/79831490

    //方法一  抽牌
    #include <algorithm>
    #include <ctime>
    void Fisher_Yates_Shuffle1(vector<int>&nums, vector<int>&res) {
    	// 时间复杂度为O(n^2),空间复杂度O(n)
    	int k;
    	while (!nums.empty()) {
    		srand((unsigned)time(NULL));
    		k = rand() % nums.size();
    		res.push_back(nums[k]);
    		nums.erase(nums.begin() + k);
    	}
    }
    int main() {
    	vector<int>nums = { 1,2,3,4,5,6,7,8,9 };
    	vector<int>res;
    	Fisher_Yates_Shuffle1(nums, res);
    	for (int i = 0; i < res.size(); i++) {
    		cout << res[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }
    
    //方法二
    #include <algorithm>
    #include <ctime>
    int main() {
    	vector <int>nums = { 1,2,3,4,5,6,7,8,9 };
    	srand((unsigned)time(NULL));
    	random_shuffle(nums.begin(), nums.end());
    	for (int i = 0; i < nums.size(); i++) {
    		cout << nums[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }
    
    // 洗牌算法
    1. 建立一个数组大小为 n 的数组 arr,分别存放 1 到 n 的数值;
    2. 生成一个从 0 到 n - 1 的随机数 x;
    3. 输出 arr 下标为 x 的数值,即为第一个随机数;
    4. 将 arr 的尾元素和下标为 x 的元素互换;
    5.2,生成一个从 0 到 n - 2 的随机数 x;
    6. 输出 arr 下标为 x 的数值,为第二个随机数;
    7. 将 arr 的倒数第二个元素和下标为 x 的元素互换;
       ……
    如上,直到输出 m 个数为止
    #include <algorithm>
    #include <ctime>
    
    int main() {
    	vector <int>nums = { 1,2,3,4,5,6,7,8,9 };
    	int n = nums.size();
    	int k = n - 1;
    	while (k >= 1) {
    		srand((unsigned)time(NULL));
    		int m = rand() % (k+1);
    		swap(nums[m], nums[k]);
    		k--;
    	}
    	for (int i = 0; i < n; i++) {
    		cout << nums[i] << " ";
    	}
    	cout << endl;
    	system("pause");
    	return 0;
    }
    

    给定一个非负整数的列表,安排它们形成最大的数字

    bool compare(int item1, int item2) {
    	//使用 to_string 把 int 转换成为 string
    	string m = to_string(item1);
    	string n = to_string(item2);
    	string mn = m + n;
    	string nm = n + m;
    	return mn > nm; // 〉降序 生成最大的数; < 升序 生成最小的数 
    }
    string PrintMinNumber(vector<int>nums) {
    	string res = "";
    	if (nums.size() == 0) {
    		return res;
    	}
    	sort(nums.begin(), nums.end(), compare);
    	for (int i = 0; i < nums.size(); i++) {
    		res += to_string(nums[i]);
    	}
    	return res;
    }
    int main() {
    	vector<int>nums = { 2,32,321 };
    	string res = PrintMinNumber(nums);
    	cout << res << endl;
    	system("pause");
    	return 0;
    }
    

    判断栈的出栈顺序是否正确

    #include <iostream>
    using namespace std;
    #include <vector>
    #include <stack>
    #include <string>
    
    bool isStackOutRight(vector<int>&sIn, vector<int>sOut, int length) {
    	stack<int>stackdata;//辅助栈 需要用到一个辅助栈stackdata来存储压入栈而尚未出栈的元素
    	int index = 0;
    	for (int i = 0; i < length; i++) {
    		if (!stackdata.empty() && stackdata.top() == sOut[i]) {
    			stackdata.pop();
    		}
    		else { //辅助栈为空,或者不等于首元素,指向压栈操作
    			while (index < length && sIn[index] != sOut[i]) {
    				stackdata.push(sIn[index++]);
    			}
    			if (index == length) {
    				return false;
    			}
    			else {
    				index++;
    			}
    		}
    	}
    	return true;
    }
    

    原地移除字符串中空格

    void trimAllSpace(string &str) {
    	string s = " ";
    	int pos = str.find(s, 0);
    	while (pos != -1) {
    		str.erase(pos, 1);
    		pos = str.find(s, 0);
    	}
    }
    int main() {
    	string str = "fdsf fgfg  ggfdg ";
    	trimAllSpace(str);
    	cout << str << endl;
    
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 来源公众号:苦逼的码农作者:帅地前阵子面试的时候,在 shopee 的一面中,问了我一道最小栈的问题,关于最小栈的问题,我以前是做过的,以为是送分,最结果最优解没写出来...
  • 排序算法 function bubbleSort(arr) { for(let i = 0,l=arr.length;iarr[j]) { let tem = arr[i]; arr[i] = arr[j]; arr[j] = tem; } } } return arr; } 6.判断js中的数据类型方法 js中共有七种数据类型 ES6新增...
  • 虽然说在前端很少有机会接触到算法,大多都交互性的操作,然而从各大公司面试来看,算法依旧是考察的一方面。下面这篇文章就给大家总结了在前端JS面试中常见的算法问题,有需要的朋友们可以参考借鉴,下面来一起看看...
  • 面试常见的js算法题

    2020-10-20 03:41:10
    本文主要介绍了面试常见的js算法题。具有很好的参考价值。下面跟着小编一起来看下吧
  • 互联网公司最常见的面试算法题有哪些?|3.TOP INTERVIEW QUESTIONS (热门面试问题)|4.模拟|1)加油站|2)LRU缓存机制|3)快乐数|4)生命游戏|5)两整数之和|6)FIZZ BUZZ|5.数组|1)乘积最大子序列|2)求众数|3)旋转数组|4...
  • 经典面试算法题N道

    2018-06-29 20:50:19
    经典面试算法题N道,经典面试算法题N道,经典面试算法题N道,经典面试算法题N道
  • 2019阿里巴巴-阿里云算法面试题,希望能助你成长,找到满意的工作。
  • ”13:21 在看|星标|留言, 真爱来源公众号:苦逼的码农 编辑:可可前几天我去面试字节跳动,面试官问了一道链表相关的算法题,不过我第一时之间没做出来,就回来看了一下,感觉这道题还不错,拿来讲一讲。...
  • 2017美团面试算法题

    千次阅读 2016-10-10 10:15:45
    9月份去参加美团的面试,遇到一个挺有意思的,哈哈哈,现摘录如下: 问题描述: 将1到9九个数字填入上图,每个数字能且仅能使用一次,使得三条边的四个数字之和相等。 解答:将a1到a9排成一排,...
  • 常见的80道面试算法题

    万次阅读 2017-06-23 11:18:57
    面试算法数据结构structgoogle微软 2011-12-14 15:11 99059人阅读 评论(5) 收藏 举报 本文章已收录于: 分类: 算法与数据结构(37) 作者同类文章X 转自:...
  • 腾讯面试算法题——编码

    千次阅读 2018-05-08 17:37:07
    题目描述 假定一种编码的编码范围是a ~ y的25个字母,从1位到4位的编码,如果我们把该编码按字典序排序,形成一个数组如下: a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx...
  • IT公司笔试算法题 面试 笔试 经典体型。可以改。 非常使用。算法。数据结构
  • 互联网公司常见面试算法题

    万次阅读 多人点赞 2017-04-21 21:22:54
    1、假设淘宝一天有5亿条成交数据,求出销量最高的100个商品并给出算法的时间复杂度。 先用哈希,统计每个商品的成交次数,然后再用在N个数中找出前K大个数的方法找出成交次数最多的前100个商品。 优化方法:可以把...
  • 完整版所有关于python面试,目前最新,最完整!加油
  • PHP面试题算法

    2014-10-21 17:21:59
    PHP面试题
  • web前端开发面试算法题(应届生)-- js篇

    万次阅读 多人点赞 2018-03-31 15:48:51
    这是本人参加应聘时做过的面试题目,还有一些是网上收集的在面试时出现率比较高的算法题,现在拿出来跟大家一起分享,希望对一些前端开发应聘者能带来一些帮助,面试时即使做的题目跟这些不一样,但是这些做题的思想...
  • 这里收集了很多大公司的面试算法题,很不错、很经典,在准备面试时很有参考价值。
  • iOS 面试必看算法题

    2019-05-07 23:30:27
    iOS 面试的要求正在逐步提高,对于算法的要求也在逐步提升,这个文件带领你学习iOS 算法。让你直通BATJ

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 224,277
精华内容 89,710
关键字:

面试算法题