Eric's Blogs

连续子数组的最大和

发表于 2020-05-26 分类于剑指Offer
本文字数： 588 阅读时长 ≈ 1 分钟

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

解答

动态规划，dp[i]=max(dp[i-1]+array[i],array[i])

public int FindGreatestSumOfSubArray(int[] array) {
    if (array==null||array.length==0){
        return 0;
    }
    int[] dp=new int[array.length];
    dp[0]=array[0];int max=dp[0];
    for (int i = 1; i < array.length; i++) {
        dp[i]=Math.max(dp[i-1]+array[i],array[i]);
        if (dp[i]>max){
            max=dp[i];
        }
    }
    return max;
}

最小的K个数

发表于 2020-05-25 分类于剑指Offer
本文字数： 900 阅读时长 ≈ 1 分钟

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

方法一

无脑排序，输出前k个数。不得不说牛客网的测试用例太弱了。

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    Arrays.sort(input);
    ArrayList<Integer> list = new ArrayList<>();
    if (k > input.length) {
        return list;
    }
    for (int i = 0; i < k; i++) {
        list.add(input[i]);
    }
    return list;
}

方法二

借助TreeSet记录最小的k个值

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    ArrayList<Integer> list = new ArrayList<>();
    if (k > input.length || k <= 0) {
        return list;
    }
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < input.length; i++) {
        if (set.size() < k) {
            set.add(input[i]);
        } else {
            if (set.last() > input[i]) {
                set.remove(set.last());
                set.add(input[i]);
            }
        }
    }
    for (Integer i : set) {
        list.add(i);
    }
    return list;
}

二叉搜索树与双向链表

发表于 2020-05-25 分类于剑指Offer
本文字数： 659 阅读时长 ≈ 1 分钟

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

后序遍历，最后来改根节点的指针，递归的思路

public TreeNode Convert(TreeNode pRootOfTree) {
    TreeNode head = null;
    if (pRootOfTree == null) {
        return head;
    }

    TreeNode leftHead = Convert(pRootOfTree.left);
    TreeNode rightHead = Convert(pRootOfTree.right);


    pRootOfTree.left = null;
    if (rightHead != null) {
        pRootOfTree.right = rightHead;
        rightHead.left = pRootOfTree;
    } else {
        pRootOfTree.right = null;
    }
    head = pRootOfTree;

    if (leftHead != null) {
        TreeNode tn = leftHead;
        for (; tn.right != null; tn = tn.right) {
        }
        tn.right = pRootOfTree;
        pRootOfTree.left = tn;
        head = leftHead;
    }
    return head;
}

复杂链表的复制

发表于 2020-05-25 分类于剑指Offer
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

先按照next遍历复制链表，再对复制后的radom指针赋值。

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public RandomListNode Clone(RandomListNode pHead) {
    if (pHead == null) {
        return null;
    }
    RandomListNode cloneHead = new RandomListNode(pHead.label);
    RandomListNode pre = cloneHead;
    RandomListNode p = pHead.next;
    while (p != null) {
        pre.next = new RandomListNode(p.label);
        pre = pre.next;
        p = p.next;
    }
    for (RandomListNode pt = pHead, cp = cloneHead; pt != null; pt = pt.next, cp = cp.next) {
        if (pt.random != null) {
            cp.random = findNode(pt.random.label, cloneHead);
        }
    }
    return cloneHead;
}

public RandomListNode findNode(int label, RandomListNode head) {
    for (RandomListNode p = head; p != null; p = p.next) {
        if (p.label == label) {
            return p;
        }
    }
    return null;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba?answerType=1&f=discussion
来源：牛客网

不用开辟新的Map，但是其实需要多次遍历。

/*
*解题思路：
*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }

        RandomListNode currentNode = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while(currentNode != null){
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }

        currentNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while(currentNode != null) {
            currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while(currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            currentNode = currentNode.next;
        }

        return pCloneHead;
    }
}

二叉树中和为某一值的路径

发表于 2020-05-25 分类于剑指Offer
本文字数： 868 阅读时长 ≈ 1 分钟

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

深度优先遍历二叉树，走到叶子结点判断一次。

ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
int target;

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    this.target = target;
    if (root == null) {
        return ans;
    }
    getPath(root, new Stack<>());
    return ans;
}

void getPath(TreeNode root, Stack<Integer> tmpPath) {
    tmpPath.add(root.val);

    if (root.right == null && root.left == null) {//叶子结点
        int sum = 0;
        ArrayList list = new ArrayList();
        for (Integer i : tmpPath) {
            sum += i;
            list.add(list.size(), i);
        }
        if (sum == target) {
            ans.add(list);
        }
    } else {
        if (root.left != null) {
            getPath(root.left, tmpPath);
        }
        if (root.right != null) {
            getPath(root.right, tmpPath);
        }
    }
    tmpPath.pop();
}

二叉搜索树的后序遍历序列

发表于 2020-05-25 分类于剑指Offer
本文字数： 788 阅读时长 ≈ 1 分钟

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

递归判断左右子树是否满足二叉搜索树的条件，即左子树都比root小，右子树都比root大。

public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence == null || sequence.length == 0) {
        return false;
    }
    int left = 0, root = sequence[sequence.length - 1];
    for (; left < sequence.length - 1; left++) {
        if (sequence[left] > root) {
            break;
        }
    }
    for (int i = left; i < sequence.length - 1; i++) {
        if (sequence[i] < root) {
            return false;
        }
    }
    boolean leftOk = true;
    if (left > 2) {
        leftOk = VerifySquenceOfBST(Arrays.copyOf(sequence, left));
    }
    boolean rightOk = true;
    if (sequence.length - 1 - left > 2) {
        rightOk = VerifySquenceOfBST(Arrays.copyOfRange(sequence, left, sequence.length - 1));
    }
    return leftOk && rightOk;
}

数组中出现次数超过一半的数字

发表于 2020-05-24 分类于剑指Offer
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

简单的做法，hash表记录出现次数。

public int MoreThanHalfNum_Solution(int [] array) {
    int len=array.length;
    Map<Integer,Integer> map=new HashMap<>();
    for (int i : array) {
        if (!map.containsKey(i)) {
            map.put(i,1);
        }else {
            map.put(i,map.get(i)+1);
        }
    }
    for (Integer integer : map.keySet()) {
        if (map.get(integer)>len/2){
            return integer;
        }
    }
    return 0;
}

用tmp记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count–，count减到0的时候就要更换新的tmp值了。如果存在超过数组长度一半的值tmp，那么最后一定会使count大于0。

public int MoreThanHalfNum_Solution(int[] array) {
    if (array == null || array.length == 0) {
        return 0;
    }
    if (array.length == 1) {
        return array[0];
    }
    int tmp = array[0], count = -1;
    for (int i = 1; i < array.length; i++) {
        if (count == -1) {
            count = 0;
        }
        if (array[i] == tmp) {
            count++;
        } else {
            count--;
        }
        if (count == 0) {
            tmp = array[i];
            count = -1;
        }
    }
    return count <= 0 ? 0 : tmp;
}

从上往下打印二叉树

发表于 2020-05-24 分类于剑指Offer
本文字数： 489 阅读时长 ≈ 1 分钟

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

二叉树的层次遍历

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> ans=new ArrayList<>();
    if (root==null){
        return ans;
    }
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode tmp=queue.poll();
        ans.add(tmp.val);
        if (tmp.left != null) {
            queue.add(tmp.left);
        }
        if (tmp.right != null) {
            queue.add(tmp.right);
        }
    }
    return ans;
}

栈的压入、弹出序列

发表于 2020-05-24 分类于剑指Offer
本文字数： 996 阅读时长 ≈ 1 分钟

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

用一个栈来模拟出栈序列.

public boolean IsPopOrder(int[] pushA, int[] popA) {
    Stack<Integer> pushStack = new Stack<>();
    int k = 0;
    for (int i = 0; i < pushA.length; i++) {
        if (pushA[i] != popA[k]) {
            pushStack.push(pushA[i]);
        } else {
            k++;
            while (!pushStack.empty() && pushStack.peek() == popA[k]) {
                pushStack.pop();
                k++;
            }
        }
    }
    for (int i = k; i < popA.length; i++) {
        if (popA[i] != pushStack.pop()) {
            return false;
        }
    }
    return true;
}

更简化的思路:新建一个栈，将pushA依次压入栈中，当栈顶元素等于数组B时，就将其出栈. 当循环结束时，判断栈是否为空，若为空则返回true

public boolean IsPopOrder(int[] pushA, int[] popA) {
    Stack<Integer> stack = new Stack<>();
    int k = 0;
    for (int i = 0; i < pushA.length; i++) {
        stack.push(pushA[i]);

        while (!stack.empty() && stack.peek() == popA[k]) {
            stack.pop();
            k++;
        }
    }
    return stack.empty();
}

包含min函数的栈

发表于 2020-05-24 分类于剑指Offer
本文字数： 579 阅读时长 ≈ 1 分钟

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

使用最小值辅助栈.

Stack<Integer> stack = new Stack();
/**
 * 与上面的栈同步,存储栈中最小元素的值
 */
Stack<Integer> minStack = new Stack();

public void push(int node) {
    stack.push(node);
    if (minStack.isEmpty() || minStack.peek() > node) {
        minStack.push(node);
    } else {
        minStack.push(minStack.peek());
    }
}

public void pop() {
    minStack.pop();
    stack.pop();
}

public int top() {
    return stack.peek();
}

public int min() {
    return minStack.peek();
}