剑指offer(16-30题) 精解

bigsai

发布于 2020-02-19 12:03:22

3700

发布于 2020-02-19 12:03:22

文章被收录于专栏：bigsaibigsai

声明：如果有效率太低的或者错误还请指正！如果有数据结构问题，可以参考笔者写的系列数据结构文章也可以加我交流哈！ 16 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路： 感觉可行方案还是不止一个的。

比如两个链表你可以用一个list1作为主链表返回。返回另一个list2进行遍历比较插入到主链表适当位置中。有兴趣可以试一试。 当然你还可以直接建立一个新链表头节点value。list1和list2同时遍历，取小的节点添加到value为头节点的链表中。同时小的那个链表向下进行下一轮比较。直到list1和list2都为null为止。

代码为：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
           if(list1==null)return list2;
           else if (list2== null) {return list1;

        }
           ListNode value=new ListNode(0);
           ListNode team=value;
           while(list1!=null&&list2!=null)
           {
               if(list1.val<list2.val)
               {
                   team.next=new ListNode(list1.val);
                   list1=list1.next;
                   team=team.next;
                   if(list1==null)
                   {
                       team.next=list2;
                       break;   
                   }
               }
               else {
                   team.next=new ListNode(list2.val);
                   list2=list2.next;
                   team=team.next;
                   if(list2==null)
                   {
                       team.next=list1;
                       break;   
                   }                   
               }
           }
           value=value.next;
           return value;          
        }
}

参考讨论区： 有个图感觉很精妙，省的画啦，当然我是用用两个节点一直while(这样的比较)，而讨论区有兄弟用递归的方法感觉也很不错的！具体讨论可以到牛客讨论区看得到哈。

17 树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路： 这题当时还卡住了。判断B是不是A的子结构。我最初想着是不是直接在A树上某个节点开始结构一直往下就和B相同。但这显然是错的。因为B是A的子结构。很可能不到叶子节点就是中间的一小部分。但是这个也不难解决。只需要判断B到叶子节点停止一下就可以了。

这题需要一个节点一个节点的进行比较。我才用队列的层序遍历(bfs)。当有相同的就停止返回。执行到最后不停止就说明这个是没有相同的 。

代码为：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.ArrayDeque;
import java.util.Queue;
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {

        Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
        if (root2==null||root1==null)
            return false;
        else {
             q1.add(root1);
            while (!q1.isEmpty()) {
                TreeNode t1=q1.poll();
                if(jud(t1, root2))
                    return true;
                else {
                    if(t1.left!=null)q1.add(t1.left);
                    if(t1.right!=null)q1.add(t1.right);
                }
            }
            return false;
        }
    }
public boolean jud(TreeNode root1,TreeNode root2) {

    if(root2==null)return true;
    else if(root1==null)
    {
        return false;
    }
    else if(root1.val==root2.val) {
        return (jud(root1.left, root2.left)&&jud(root1.right,root2.right));     
    }   
    else {
        return false;
    }
}
}

参考评论区： 主要思想差不多吧，要注重子树和子结构的区别。当然个别大佬把HasSubtree函数用递归写了感觉效率很差，就不贴了有兴趣的可以自己研究哈！

18 二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述

二叉树的镜像定义：源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

思路： 最直观和好想的肯定是递归法。遇到二叉树这种未知结构大部分都可以采用递归求解，只需要交换节点左右子树即可。而上述的递归过程大致如下：

二叉树的镜像定义：源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9  11
        //step1 第三层交换
            8
           /  \
          6   10
         / \  / \
        7  5 11  9
        //step2  第二层交换，第一层不需要交换
            8
           /  \
          10   6
         / \  / \
        11 9 7   5

实现代码为：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     public void Mirror(TreeNode root) {
         if(root==null) return;
        TreeNode teamNode=root.right;
        root.right=root.left;
        root.left=teamNode;
        if(root.left!=null) {Mirror(root.left);}
        if(root.right!=null) {Mirror(root.right);}
    }
}

19 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路： 这题其实方法还是蛮重要的。个人主要两个想法吧： 思路一：模拟

大家都知道是顺时针进行旋转式的输出。那么这本身就是一次运动，那么我们就可以模拟这个光标的运动，一直到结束。
想法虽然简单，但是实现起来很麻烦！比如，你可能需要用参数标记当前的方向，还可能需要用个boolean数组判断是否走过和是否越界问题。还可能需要多个if else当判定当前结束选择下一个方向。想想这个代码一定是很臃肿的。虽然可以实现，有兴趣的可以尝试。

思路二：数学计算(不一定说的很好可以自行理解) 正常情况下：一个顺时针是进行四次！但是每次走的位置咱们是可以确定的。咱么假设竖的为X,横的为Y。

先不考虑走完的问题。每次走的四次开始的坐标和结束的坐标是可以算出来的！因为相当于每走一圈横纵坐标都减二。而开始和结束位置分别加1和减1。所以每次走的结束位置可以准确表示出来。

考虑走完的问题。肯定是根据窄的走完。问题还有奇偶的问题。如果偶数的话可以刚好走完，而奇数需要特殊判断一下省略最后一次循环一些步骤才行！

其他注意点。当循环添加一轮的时候，实际上当前的坐标是有变化的。需要手动修正一下

实现代码为：

import java.util.ArrayList;
public class Solution {
     public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        int xlen=matrix.length;
        int ylen=matrix[0].length;
        int min=Math.min(xlen, ylen);
        int x=0;//上下 纵坐标
        int y=0;//左右 横坐标
        for(int i=0;i<(min+1)/2;i++)
        {
          for(;y<ylen-i;y++) {list.add(matrix[x][y]);}y--;x++;
           for(;x<xlen-i;x++) {list.add(matrix[x][y]);}x--;y--;
           if(i==xlen/2)continue;
           for(;y>=i;y--) {list.add(matrix[x][y]);}y++;x--;
            if(i==ylen/2)continue;
           for(;x>i;x--) {list.add(matrix[x][y]);}x++;y++;
            }
        return list;
}
}

20 包含main函数的栈

题目描述

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

思路： 这题感觉这样要求返回栈中最小元素为O(1),那么说明需要有个常数min来维护这个最小值，可以直接返回。而这个min维护的时候只需要注意两点：

push加入的时候是不是更小，如果更小的话需要更新这个min。
pop元素是不是和min一样大。如果比min大不需要管。但是如果和min一样大那么就需要遍历重新确定min。当然整个函数的最大开销也就在这里了。

实现代码为：

import java.util.Stack;
public class Solution {
private int a[]=new int [1000];
    private int index=0 ;
    private int min=Integer.MAX_VALUE;
    public void push(int node) {
       a[index]=node;
       if(a[index]<min)min=a[index];
       index++;
    }   
    public void pop() {
        if(a[--index]==min)
        {
            min=Integer.MAX_VALUE;
            for(int i=0;i<index;i++)
            {
                if(a[i]<min)
                {
                    min=a[i];
                }
            }
        }       
    }   
    public int top() {
        return a[index-1];        
    }    
    public int min() {
        return min;
    }
}

21 栈的压入、弹出序列

题目描述

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

思路： 这题核心思想是模拟吧。给了压入序列看是不是弹出序列。我们假设这就是个弹出序列。然后根据这个弹出序列的顺序。将第一个数组的数据一个一个压入栈。当遇到在弹出序列当前位置的值时候就弹出。最终如果栈为空那么说明假设成立，如果不为空说明这个假设失败，就不是弹出序列。

在这里插入图片描述

实现代码为：

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
        public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        for (int i = 0; i < pushA.length; i++) {// 找到第一个push元素的位置
            stack.push(pushA[i]);
            //while (!stack.isEmpty()) {
                while (!stack.isEmpty()&&stack.peek() == popA[index]) {
                    stack.pop();
                    index++;
                //}
                //break;
            }
        }
        if (stack.size() == 0)
            return true;
        else {
            return false;
        }
    }
}

22 从下往上打印二叉树

题目描述

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

思路： 用队列，就是二叉树的层序遍历。bfs的思想。

实现代码：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

            ArrayList<Integer>list=new ArrayList<Integer>();
            if(root==null)return list;
            Queue<TreeNode>q1=new ArrayDeque<>();
            q1.add(root);
            while (!q1.isEmpty()) {
                TreeNode node=q1.poll();
                list.add(node.val);
                if(node.left!=null) {q1.add(node.left);}
                if(node.right!=null) {q1.add(node.right);}
            }
            return list;
        }
}

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

题目描述

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

思路： 这个题和前面的前中确定构造二叉树那题思想很想。后序遍历顺序为左区域右区域根，其中每个节点的左区域肯定小于根，右区域全部大于根。同样里面的每个小区域也满足这个要求，再考虑一下边界和特殊情况，合理使用递归即可！

在这里插入图片描述

实现代码：

public class Solution {
  public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0)
            return false;
        return jud(sequence, 0, sequence.length - 1);
    }
    public boolean jud(int a[],int left,int right)//左右包含左和右
    {
        int index=0;int mid=0;
        if(left>=right)return true;
        for(;index<right;index++)
        {
            if(a[index]>a[right])
                break;
        }
        mid=index;
        for(;index<right;index++)
        {
            if(a[index]<a[right])break;
        }
        if(index!=right)return false;
        else {
            return jud(a, left, mid-1)&&jud(a, mid, right-1);
        }
    }
}

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

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路： dfs深度优先遍历。要注意的是要遍历到叶子节点的路径。如果有中途遍历的时候路径满足而非叶子节点是不停止的。

dfs(TreeNode root, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> list2

而这样一个dfs函数target是个参数，每到达一个点会减去对应值。list是当前遍历的路径存储列表。而这个dfs是一个回溯的过程，list根据递归过程元素是不断变化的。所以这个list不能直接加到list2中。当遍历到根节点的时候满足条件要用新的list3复制list的值加入到list2中。如果对这个地方不理解请百度深度优先搜索或者回溯法 。当然更多还需要自己理解的。

另外，要求路径中较长的路径在前面。这里我就实现了个Comparator排个序就行了。

实现代码为：

import java.util.ArrayList;

import java.util.Comparator;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     public  ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<Integer> team = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return list;
        }
        dfs(root, target, team, list);
        return list;
    }

    static Comparator<ArrayList<Integer>> comparator = new Comparator<ArrayList<Integer>>() {

        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            // TODO Auto-generated method stub
            return o2.size() - o1.size();
        }
    };

    public  void dfs(TreeNode root, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> list2) {
        if (target < 0) {// 停止
        } else {
            list.add((Integer) root.val);
            target -= root.val;
            if (root.left != null)
                dfs(root.left, target, list, list2);

            if (root.right != null)
                dfs(root.right, target , list, list2);
             if (root.left==null&&root.right==null&&target == 0) {//叶子节点
                ArrayList<Integer> list3 = new ArrayList<Integer>();
                list3.addAll(list);
                list2.add(list3);
            }
            target+=root.val;
            list.remove((Integer) root.val);
        }
    }
}

参考评论区 评论区看到有个递归写的非常好，比我的要精简很多，但是没有保证最短的在前面(需要自己排序一下，为了更好实现可以写个新函数代替这个只能在返回的函数中只需进行一次排序)。但是过了说明这个数据还是很水的。大家可以参考这个过程。

25 复杂链表的复制

题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路： 说实话，这题自己还卡了不少时间。刚开始一直没想到该怎么处理。后面经过自己不断思考终于克服了！——你虽然是链表，但我想怎么搞怎么搞(搞个数组)。

首先明确，他让我们克隆，也就是不能引用原链表的任何一个节点。也就是要100%的创造和克隆。大致分析思路如下：

它每个节点有一个next，有一个random。也就是一个指向后面，一个瞎指的。如果两个指针同时考虑真的太复杂了，那我先分开考虑。只看next他就是一个链表。对吧(先不考虑循环)
我们用个RandomListNode list[]遍历链表将链表各个节点存进去。RandomListNode clone[]是我们想克隆的数组。至于克隆数组每个对应位子应该和list是相似的。并且每个next应该指向下一位clone[i].next=clone[i+1],至于每个random的位置。我们可以挨个遍历list中random的相对位置，然后clone的random也指向相应位置。这个是开销最大的部分，时间复杂度为O(n^2^).但是我自己没想到更好的方法，后面参考题解如果有更好方法会进行更新吧。

实现代码为：

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
        //step1 计算有多少个
        int count=0;
        RandomListNode team=pHead;
        while(team!=null)
        {count++;team=team.next;if(team==pHead)break;}//先不考虑是否会是循环链表
        //step2 将每个位置的指针存在
        RandomListNode list[]=new RandomListNode[count+1];
        RandomListNode clone[]=new RandomListNode[count+1];
        team=pHead;
        count=0;
        while(team!=null)
        {
            clone[count]=new RandomListNode(team.label);
            list[count++]=team;
            team=team.next;
            if(team==pHead)break;           
        }
        //step3 克隆指针

        for(int i=0;i<count;i++)
        {
            clone[i].next=clone[i+1];
            for(int j=0;j<count;j++)
            {
                if(list[i].random==list[j])
                {
                    clone[i].random=clone[j];
                    break;
                }
            }
        }

        return clone[0];
    }
}

参考讨论区： 这题在讨论区发现很多人再用的非常巧妙的效率很高的方法(谁是原创也不知道)。

实现代码为：

链接：https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba?f=discussion
来源：牛客网
/*
*解题思路：
*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;
    }
}

26 二叉搜索树与双向链表

题目描述

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

思路：关于二叉树搜索(排序树)需要我们转换成一个排序的双链表。我们知道二叉树有left和right。用来表示树的左右结构，但是它要求我们将树形结构转换成链式，并且还是有序的，并且还不能建立新的节点。二叉搜索树(排序树)我们知道它的中序序列是有序的，所以我们可以使用非递归的中序遍历，先想办法将节点按照中序的规则进行释放。根据释放的顺序，记录前一个节点互相记住左右就好了。

对于二叉树各种遍历以及递归非递归方式，笔者以前都梳理过，大家可以看看。

利用栈记录一下节点，用一个prenode记录前一个节点指针，当抛出当前节点两个节点左右互指以下就OK了。当然，要有个headnode记录第一个节点返回。有使用递归版本的过也可以，可以自行尝试。

实现代码为：

import java.util.Stack;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {

         Stack<TreeNode> q1 = new Stack();  
         TreeNode preNode=null;//前
         TreeNode headNode=null;
            while(!q1.isEmpty()||pRootOfTree!=null)
            {
                if (pRootOfTree!=null) {
                    q1.push(pRootOfTree);
                    pRootOfTree=pRootOfTree.left;

                }
                else {
                    pRootOfTree=q1.pop();//弹出
                    if(preNode==null){preNode=pRootOfTree;headNode=preNode;}
                    else 
                    {
                        preNode.right=pRootOfTree;
                        pRootOfTree.left=preNode;
                    }
                    preNode=pRootOfTree;
                    pRootOfTree=pRootOfTree.right;
                }
            }
        return headNode;
        }
}

27 字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：这题我不知道别人有啥方法，但是我的第一感觉就是全排列问题。当然我知道的全排列有两种实现方法。一种是dfs回溯法，另一种是普通递归+排序才能过这题，因为dfs的全排列是有序的，而普通递归交换的全排列是没序的。这题两者效率可能相差不大，但就全排列的序列而言。掌握递归的全排列效率更高。当然这也是笔者所采用的。至于全排列笔者以前虽然记录过但写的一般有兴趣可以参考其他讲解。两种方式实现全排列。

当然，这题它可能有相同的字母，所以需要用个Hash去重下更好，但我懒直接用list判断存不存在了。

实现代码为：

import java.util.ArrayList;
public class Solution {
     public ArrayList<String> Permutation(String str) {
         ArrayList<String> list=new ArrayList<String>();
         char a[]=str.toCharArray();
         arrange(a, 0, a.length - 1,list);
         list.sort(null);
         return list;
        }

    private void arrange(char[] a, int start, int end, ArrayList<String> list) {
        // TODO Auto-generated method stub
        if (start == end) { 
            String team=getstr(a);
            if(!list.contains(team))list.add(getstr(a));
            return;
        }
        for (int i = start; i <= end; i++) {
            swap( i, start,a);
            arrange(a, start + 1, end,list);
            swap( i, start,a);
        }   
    }
    private String getstr(char[] a) {
        String str="";
        for(int i=0;i<a.length;i++)
            str+=a[i];
        return str;
    }
    private void swap(int i, int j, char a[]) {
        char team=a[i];
        a[i]=a[j];
        a[j]=team;  
    }
}

28 数字中出现次数超过一半的数字(待优化)★

题目描述

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

思路：这题是一道经典题。我只知道有一个更好方法但是我还没消化。二轮吸收讨论区的时候肯定会加上的。而我采用笨方法就是hashmap存入判断。有则返回。这样就是开了更大的内存。这题后面还会优化。

实现代码为：

import java.util.HashMap;
import java.util.Map;
public class Solution {
  public int MoreThanHalfNum_Solution(int[] array) {
        if(array.length==1)return array[0];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = array.length  / 2;
        int team = 0;
        for (int a : array) {
            if (map.containsKey(a)) {
                team = map.get(a);
                if (team >= len)
                    return a;
                else {
                    map.put(a, team + 1);
                }
            } else {
                map.put(a, 1);
            }
        }
        return 0;
    }
}

参考讨论区： 这题是经典面试题，很多情况会问不允许开更大的空间完成这个要求，这就要根据数据的特点来完成：

如果有大于一半的数！那么假设所有数争夺一个猎物！同样的聚成群，不一样的1v1同归于尽,那么最后剩的一群或者一个那么就是大于一半的(如果存在一半的话)！

在具体实现就是设两个数，一个数num等于遍历的数，另一个count就是出现的次数。
如果遍历的数等于num，那么count++；
如果不等于，那么消灭一个num，count--，如果count被减成0，那么就换个数，同时count变成1.

实现代码为：

public int MoreThanHalfNum_Solution(int[] array) {
        int num=array[0];int count=0;
        for(int i=0;i<array.length;i++)
        {
            if(num==array[i])count++;
            else {
                if(--count==0)
                {
                    num=array[i];
                    count=1;
                }
            }
        }
        if(count==0)return 0;
        count=0;
        for(int i=0;i<array.length;i++)
        {
            if(num==array[i])count++;
        }
        if(count>array.length/2)
            return num;
        return 0;
    }

29 最小的K个数

题目描述

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

思路：排序取前K个数字，当然需要讨论下特殊情况。

实现代码：

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

30 连续子数组最大和

题目描述

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

思路： dp动态规划问题问题，最长递增子序列（LIS），和最长公共子串(LCS)都是经典问题。此题大家可以了解LIS。至于这种dp问题，要掌握它们的初始化+动态方程，至于这个动态方程。用dp[i]表示第i个节点的最大序列和。

而本题的dp方程为：dp[i]=max(array[i],array[i]+dp[i-1])

我们不考虑整个串串，只考虑连个点之间的关系。1、串串连续 2、串串长度任意可以为一.对于第i个节点，他想要最长的连续序列。那么有两种情况。第一种就是和前面连在一起然后加上自己。当然前面的是多少我们不管，我们只知道前面的最大时dp[i-1].或者自立门户长度为1不和前面的接起来。当然这需要两者比较取最大。

实现代码为：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max=0;
        int dp[]=new int[array.length];
        dp[0]=array[0];max=dp[0];
        for(int i=1;i<array.length;i++)
        {

            dp[i]=max(dp[i-1]+array[i],array[i]);
            max=max>dp[i]?max:dp[i];
        }
        return max;
    }
    static int max(int a,int b)
    {
        return a>b?a:b;
    }
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-02-02，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自 bigsai 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度