Object's Blog

算法刷题记录(第一周整合)

字数统计: 8.8k阅读时长: 38 min
2019/10/21 分享

前言

原先是一天一发,发现这样会有大量的篇幅,所以以后就将一周的算法题做一个整合。当然,记录还是每天来记录的,毕竟刚刷完题热腾腾的解题思路是必须得写下来的。

第一天题目汇总

第一题:二维数组中的查找

  • 题目描述

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

  • 解题思路

    从左下找,由于该数组有从左到右依次增大,从上到下依次增大的特点,所以左下的元素一定是该行最小的元素,却是该列最大的元素,所以如果target<该元素,则指针向上移,如果target>该元素,则指针向右移,如果相等,返回true。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public class Solution {
    public boolean Find(int target, int [][] array) {
    int rowCount = array.length-1;
    int columnCount = 0;
    if(rowCount<0)
    return false;
    while(rowCount>=0&&columnCount<array[0].length) {
    if(target>array[rowCount][columnCount]) {
    columnCount++;
    }else if(target<array[rowCount][columnCount]) {
    rowCount--;
    }else {
    return true;
    }
    }
    return false;
    }
    }

第二题:替换空格

  • 题目描述

    请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  • 解题思路

    ?????这个题????? 反正是可以调用jdk自带方法,也通过了。

  • 代码

    1
    2
    3
    public String replaceSpace(StringBuffer str) {
    return str.toString().replace(" ", "%20");
    }

第三题:从尾到头打印链表

  • 题目描述

    输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

  • 解题思路

    本来想着暴力求解,发现时间复杂度实在太大,其实这题可以用堆栈的思想,既然这个不是双向链表,只能正序遍历不能反序便利,但题目要求我们反向输出,那么就可以一次放入堆栈,先进后出,就完成了反序,ArrayList中有一个add(int index,T value)方法,可以在任意位置插入元素,所以可以一直往0号位置插入正在遍历的链表元素,最后返回的就是反向链表了。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    /**
    * public class ListNode {
    * int val;
    * ListNode next = null;
    *
    * ListNode(int val) {
    * this.val = val;
    * }
    * }
    *
    */
    import java.util.ArrayList;
    public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    if(listNode==null) {
    return new ArrayList<Integer>();
    }
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    while(listNode!=null) {
    arrayList.add(0, listNode.val);
    listNode = listNode.next;
    }
    return arrayList;
    }
    }

第四题:重建二叉树

  • 题目描述

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

  • 解题思路

    1.确定先序遍历的第一个元素为根节点。

    2.在中序遍历序列中找到该元素的位置,该元素位置的左侧为该元素的左子树,右侧为该元素的右子树。

    3.为该元素的左右子树分别执行1、2两部操作。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /**
    * Definition for binary tree
    * public class TreeNode {
    * int val;
    * TreeNode left;
    * TreeNode right;
    * TreeNode(int x) { val = x; }
    * }
    */
    import java.util.Arrays;
    public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if(pre.length<=0||in.length<=0)
    return null;
    if(pre.length==1||in.length==1)
    return new TreeNode(pre[0]);
    TreeNode root = new TreeNode(pre[0]);
    for(int i=0;i<in.length;i++) {
    if(root.val == in[i]) {
    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1,pre.length), Arrays.copyOfRange(in, i+1,in.length));
    break;
    }
    }
    return root;
    }
    }

第五题:用两个栈实现队列

  • 题目描述

    用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

  • 解题思路

    栈的特点是先入后出,队列的特点是先入先出,所以要用两个栈来实现队列,还是比较简单的,只需要将一个栈的元素重新pop,然后push到另一个栈中,再pop,就可以得到队列的结果。

    根据该思路,可以设计如下步骤:

    1.push时,就正常push到stack1中

    2.pop时,如果stack2中有元素则直接pop,如果stack2中没有元素,则将stack1中的所有元素pop,然后push进stack2中,然后将stack2栈顶元素pop。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    import java.util.Stack;

    public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
    stack1.push(node);
    }

    public int pop() {
    if (stack2.size() <= 0) {
    while (stack1.size() > 0) {
    int i = stack1.pop();
    stack2.push(i);
    }
    }
    return stack2.pop();
    }
    }

第二天题目汇总

第一题:旋转数组的最小数字

  • 题目描述

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
    例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
    NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

  • 解题思路

    刚开始没看懂题意,这不就是找最小值吗,嗯真的是找最小值。剑指Offer刚开始题目的难度真的很适合入门者练习。。。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import java.util.ArrayList;
    import java.util.Arrays;
    public class Solution {
    public int minNumberInRotateArray(int [] array) {
    if(array.length==0)
    return 0;
    Arrays.sort(array);
    return array[0];
    }
    }

第二题:斐波那契数列

  • 题目描述

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

    n<=39

  • 解题思路

    斐波那契数列:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)

    SO。。。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class Solution {
    public int Fibonacci(int n) {
    if(n==0)
    return 0;
    if(n==1)
    return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
    }
    }

第三题:跳台阶

  • 题目描述

    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

  • 解题思路

    另一种形式的斐波那契数列。

    首先:

    跳一级台阶的跳法为1(只能跳1阶)

    跳两级台阶的方法为2(跳1阶两次,跳2阶1次)

    跳三级台阶的方法为3(跳1阶三次,跳1阶一次跳2阶一次,跳2阶一次跳1阶一次)

    跳四级台阶的方法为5(1111、211、121、112、22)

    ……

    所以:

    跳n阶台阶的方法数量等于,跳n-1次的方法数量+跳n-2次的方法数量

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    public class Solution {
    public int JumpFloor(int target) {
    if(target==1) return 1;
    if(target==2) return 2;
    if(target==3) return 3;
    return JumpFloor(target-1)+JumpFloor(target-2);
    }
    }

第四题:变态跳台阶

  • 题目描述

    一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  • 解题思路

    首先先抓住不变的,跳一级一定只有一种跳法,跳两级一定只有两种跳法。

    那么跳3级呢?

    1+1+1,1+2,2+1,3,一共有四种跳法。

    跳三级可以分解为跳两级的所有跳法+跳两级的所有跳法+加上一次跳3级的一种跳法。所以是1+2+1=4种跳法。

    那么跳4级呢?

    1+1+1+1,2+1+1,1+2+1,1+1+2,2+2,3+1,1+3,4。一共八种跳法。

    跳四级可以分解为,跳一级的所有跳法(1)+跳两级的所有跳法(2)+跳三级的所有跳法(4)+一次性跳4级的所有跳法(1)。

    所以,跳n级的跳法就等于:本身一次性跳n级的1种跳法,加上跳n-1级的所有跳法,加上跳n-2级的所有跳法…….

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public class Solution {
    public int JumpFloorII(int target) {
    if(target==1)
    return 1;
    else if(target==2)
    return 2;
    else{
    //关键
    int count = 1;
    while(target>1){
    count+=JumpFloorII(target-1);
    target-=1;
    }
    return count;
    }
    }
    }

第五题:矩形覆盖

  • 题目描述

    我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形,总共有多少种方法?

  • 解题思路

    还是斐波那契数列,和第三题很相似。

    首先,

    用1个2 * 1的小矩形覆盖一个2 * 1的大矩形 只有一种方法。

    用2个2 * 1的小矩形覆盖一个2 * 2的大矩形 只有两种方法。

    用3个2 * 1的小矩形覆盖一个2 * 3的大矩形 只有三种方法。

    覆盖2 * 3 的大矩形,可以分解为,一个2 * 1的大矩形和一个2 * 2的大矩形。而这两个,一个方法是1种,一个方法是2种.

    那么大概可以知道,覆盖一个2 * n的大矩形,可以分解为,覆盖一个2 * n-1的大矩形和覆盖一个2 * n-2的大矩形的所有方法相加。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class Solution {
    public int RectCover(int target) {
    if(target==0) return 0;
    else if(target==1) return 1;
    else if(target==2) return 2;
    else if(target==3) return 3;
    return RectCover(target-1)+RectCover(target-2);
    }
    }

第三天题目汇总

第一题:二进制中1的个数

  • 题目描述

    输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

  • 解题思路

    将传入的参数右移,每次判断最后一位是否为1,如果为1count++即可。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public class Solution {
    public int NumberOf1(int n) {
    int count = 0;
    while(n!=0){
    count+=n&1;//判断最后一位是否为1 1=000000...001 &运算只能判断最后一位
    n = n>>>1;
    }
    return count;
    }
    }

第二题:数值的整数次方

  • 题目描述

    给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
    保证base和exponent不同时为0

  • 解题思路

    循环解,需要注意的是 exponent有可能小于0

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Solution {
    public double Power(double base, int exponent) {
    double result = 1;
    boolean isNegative = false;
    if(exponent<0){
    exponent *= -1;
    isNegative = true;
    }
    for(int i = 0;i < exponent;i++){
    result *= base;
    }
    if(isNegative)
    result = 1/result;
    return result;
    }
    }

第三题:调整数组顺序使奇数位于偶数前面

  • 题目描述

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

  • 解题思路

    开辟两个辅助数组,分别存奇数和偶数,最后按顺序回写到array中

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    import java.util.ArrayList;
    import java.util.List;
    public class Solution {
    public void reOrderArray(int [] array) {
    List<Integer> odd= new ArrayList<>();
    List<Integer> even = new ArrayList<>();

    for(int i=0;i<array.length;i++) {
    if(array[i]%2!=0)
    odd.add(array[i]);
    else
    even.add(array[i]);
    }
    int count = 0;
    for(Integer i:odd) {
    array[count] = i;
    count++;
    }
    for(Integer i :even) {
    array[count] = i;
    count++;
    }
    for(int i=0;i<array.length;i++) {
    System.out.println(array[i]);
    }
    }
    }

第四题:链表中倒数第k个结点

  • 题目描述

    输入一个链表,输出该链表中倒数第k个结点。

  • 解题思路

    和前几天做的链表逆序输出想法相同,用栈的思想。先把数组入栈,然后pop出倒数第n个数。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    /*
    public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
    this.val = val;
    }
    }*/
    import java.util.Stack;
    public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null) return null;
    Stack<ListNode> nodeStack = new Stack<ListNode>();
    ListNode pointer = head;
    while(pointer!=null) {
    nodeStack.push(pointer);
    pointer = pointer.next;
    }
    for(int i = 0;i<k;i++) {
    if(nodeStack.size()==0) return null;
    pointer = nodeStack.pop();
    }
    return pointer;
    }
    }

第五题:反转链表

  • 题目描述

    输入一个链表,反转链表后,输出新链表的表头。

  • 解题思路

    依旧用栈的思想来反转链表,然后构建新链表输出表头。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public ListNode ReverseList(ListNode head) {
    ListNode pointer = head;
    Stack<Integer> nodeStack = new Stack<Integer>();
    while(pointer!=null) {
    nodeStack.push(pointer.val);
    pointer = pointer.next;
    }
    pointer = head;
    while(!nodeStack.empty()) {
    pointer.val = nodeStack.pop();
    System.out.println(pointer.val);
    pointer = pointer.next;
    }
    return head;
    }

第四天题目汇总

第一题:

  • 题目描述

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

  • 解题思路

    新建一个新链表,命名为mergeList,对两个已有链表分别遍历,将节点值小的加入新链表。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1==null) return list2;
    if(list2==null) return list1;
    ListNode cur = null;
    ListNode mergeList = null;
    while(list1!=null&&list2!=null) {
    if(list1.val<=list2.val) {
    if(mergeList==null) mergeList = cur = list1;
    else {
    cur.next = list1;
    cur = cur.next;
    }
    list1 = list1.next;
    }else {
    if(mergeList==null) mergeList = cur = list2;
    else {
    cur.next = list2;
    cur = cur.next;
    }
    list2 = list2.next;
    }
    }
    if(list1!=null) cur.next = list1;
    if(list2!=null) cur.next = list2;
    return mergeList;
    }

第二题:树的子结构

  • 题目描述

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

  • 解题思路

    1.判断A和B是否为空,如果有一个为空直接返回false。

    2.进入isSubTree判断B是否为null,如果B为null则返回true。

    3.判断A是否为null,如果A为null则返回false。

    4.判断根节点是否和B一致,如果不一致则判断A的左子树和B是否一致,如果不一致则继续找下一个左子树,如果一致则对左右子树进行比对。如果A为null则直接返回false

    5.判断右子树的方式和4相同

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if(root1==null||root2==null) return false;
    return isSubtree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }
    public boolean isSubtree(TreeNode root1,TreeNode root2) {
    if(root2==null) return true;
    if(root1==null) return false;
    if(root1.val!=root2.val) return false;

    return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
    }

第三题:二叉树的镜像

  • 题目描述

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

  • 解题思路

    如果给的树为空,则直接返回。

    如果给的子树左子树或者右子树不为空则交换左右子树。

    对完成操作的左右子树分别再做交换操作。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class Solution {
    public void Mirror(TreeNode root) {
    change(root);
    }
    public void change(TreeNode root){
    if(root==null) return;
    if(root.left!=null||root.right!=null){
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    }
    change(root.left);
    change(root.right);
    }
    }

第四题:顺时针打印矩阵

  • 题目描述

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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.

  • 解题思路

    画了个图,可以将矩阵分为左侧,右侧,上侧,下侧,这四个边界,分别用left,right,top,buttom标识。

    程序从左上开始向右遍历,当遍历到right边界时,表示第一行遍历结束,那么这一行之后就不会再遍历到了。所以将上边界下移一行,再开始遍历右边界,当遍历到buttom时表示右边界遍历结束。那么将right向左移一列。以这个思想,一直遍历下去。

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public ArrayList<Integer> printMatrix(int[][] matrix) {
    int left = 0;
    int top = 0;
    int right = matrix[0].length - 1;
    int buttom = matrix.length - 1;
    ArrayList<Integer> res = new ArrayList<>();
    while (true) {
    for (int i = left; i <= right; i++)
    res.add(matrix[top][i]);
    top++;
    if (top > buttom)
    break;
    for (int i = top; i <= buttom; i++)
    res.add(matrix[i][right]);
    right--;
    if (right < left)
    break;
    for (int i = right; i >= left; i--)
    res.add(matrix[buttom][i]);
    buttom--;
    if (buttom < top)
    break;
    for (int i = buttom; i >= top; i--)
    res.add(matrix[i][left]);
    left++;
    if (left > right)
    break;
    }
    return res;
    }

第五题:包含min()函数的栈

  • 题目描述:

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

  • 解题思路:

    因为要自己定义栈的数据结构,所以我第一次在栈中定义了一个min属性来在push时记录最小元素,然后min方法只需要把min返回就可以了,但是我发现我把问题想简单了,因为如果最小值被pop,栈中元素并不会被min记录。所以我用了另一种方法,用两个堆栈,一个堆栈放正常数据,另一个堆栈放最小值,当每次入栈被判定为最小值的那个属性,再入这个最小值栈,每次出栈被判定为最小值的那个属性,被最小值栈pop,min属性刷新为最小值栈的栈顶属性值。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public class Solution {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minStack = new Stack<Integer>();
    int min = Integer.MAX_VALUE;
    public void push(<