剑指offer2

21.反转链表

题目描述

输入链表，反转链表后，输出新链表的表头。

解题思路

这里借用leetcode中的视频

code

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null,cur = head;
        while (cur!=null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

22.矩形覆盖

题目描述

可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。用n个2*1的小巨星无重叠的覆盖一个2*n的大矩形，有多少种方法。

解题思路

动态规划。

code

import java.util.*;
public class Solution {
    public int rectCover(int target) {
        int[] dp = new int[target+10];
        if(targer == 0){
            return 0;
        }
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i<=target;i++){
            dp[i] = dp[i-2]+dp[i-1];
        }
        return dp[target];
    }
}

23.数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和ex不同时为0，不使用函数库，不考虑大数问题。、

解题思路

就是一个简单的数学题吧

code

public static double Power(double base, int exponent) {
    if(exponent==0)return 1;
    double res = base;
    for(int i = 0;i<Math.abs(exponent)-1;i++){
        res = res*base;
    }
    if(exponent>0){
        return res;
    }else{
        return (double) 1.0000/res;
    }
}

24.栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否可能是弹出序列。假设入栈的数字不相等。

解题思路

这里是模拟的。代码及其垃圾。

code

public static boolean IsPopOrder(int [] pushA,int [] popA) {
    if(Arrays.stream(pushA).sum()!= Arrays.stream(popA).sum())return false;
    //记录当前进栈的元素下标
    int test = 0;
    Stack<Integer> stack1 = new Stack<>();
    for(int i = 0;i<popA.length;i++){
        int out = popA[i];
        //元素在栈中，出栈。这里的逻辑没毛病。
        if(stack1.contains(out)){
            int index = stack1.pop();
            if(index!=out){
                return false;
            }else {
                continue;
            }
        }else {
            //进栈
            for(int j = test;j<pushA.length;j++){
                if(pushA[j]!=out){
                    stack1.push(pushA[j]);
                    test++;
                }else {
                    test++;
                    break;
                }
            }
        }
    }
    return true;
}

25.二叉搜索树与双向链表

题目描述

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

解题思路

水题

code

import java.util.*;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;
        //中序遍历然后修改指针指向
        List<TreeNode> list = new ArrayList<TreeNode>();
        Convert(pRootOfTree,list);
        //修改指针指向
        for(int i = 0;i<list.size()-1; i++){
            list.get(i).right = list.get(i+1);
            list.get(i+1).left = list.get(i);      
        }
        return list.get(0);
    }

    //今天终于看到，这好像就是多态
    public void Convert(TreeNode tree,List<TreeNode> res){
        //中序遍历
        if(tree.left!=null){
            Convert(tree.left, res);
        }
        res.add(tree);
        if(tree.right != null){
            Convert(tree.right, res);
        }
    }
}

26.包含min函数的栈

题目描述

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

解题思路

一个正常栈，一个辅助栈。重点的逻辑是进栈逻辑，每次进栈都在辅助栈保存栈的最小值。

code

import java.util.Stack;

public class Solution {

    Stack<Integer> data = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();
    Integer temp = null;
    public void push(int node) {
        if(temp != null){
            if(node <= temp ){
                temp = node;
                min.push(node);
            }
            data.push(node);
        }else{
            temp = node;
            data.push(node);
            min.push(node);
        }
    }
     
    public void pop() {
        int num = data.pop();
        int num2 = min.pop();
        if(num != num2){
           min.push(num2);
        }
    }
     
    public int top() {
        int num = data.pop();
        data.push(num);
        return num;
    }
     
    public int min() {
        int num = min.pop();
        min.push(num);
        return num;
    }
}

27.两个链表的第一个公共节点

题目描述

输入两个无环的单链表，找出他们的第一个公共节点。(因为传入数据是链表，所以错误数据的数据的提示是用其他方式显示的，保证传入数据是正确的)。

解题思路

想到的第一个方法是用set，先把第一个链表逐个进去，然后遍历第二个链表进去，遇到入的时候为false，则表示是公共节点

code

import java.util.*;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>();
        Boolean status = true;
        while (pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null){
            status = set.add(pHead2);
            if(status == false){
                return pHead2;
            }else {
                pHead2 = pHead2.next;
            }
        }
        return null;
    }
}

28.扑克牌顺子

题目描述

2副扑克牌，随机抽出五张，判断一下是不是顺子。规则如下：

A为1，J为11，Q为12，K为13，A不能视为14。

大、小王为 0，0可以看作任意牌。

如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。

解题思路

简化一下就是，输入0-13的数组，检查是不是顺子，0可以当做任何数，最多四个0.

有重复数字的false，然后就是最大值和最小值之间，万能0能不能填满的问题了，最大和最小的差值，应该是小于5的，不然顺子的话，就是6+个数字了。代码有些啰嗦了。

code

import java.util.*;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int min = 50;
        int max = -1;
        Set<Integer> set = new HashSet<>();
        //数组除0以外没重复，且最大值和最小值的差值小于5
        //一个循环统计是否重复和最大值最小值
        for(int i = 0;i<numbers.length; i++){
            if(numbers[i] !=0) {
                //先更新最大最小值
                if(numbers[i] >max){
                    max = numbers[i];
                }
                if(numbers[i] <min){
                    min = numbers[i];
                }
                //再判重
                Boolean status = set.add(numbers[i]);
                if(status==false){
                    return false;
                }
            }
        }
        if(max-min<5){
            return true;
        }else {
            return false;
        }
    }
}

29.重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树。遍历结果中不包含重复数字。

解题思路

树算法采用递归是最简单的，前序和终须确定二叉树的具体流程是：

• 前序的第一个节点时根节点
• 根据节点在中序的位置，分为左右序列
• 对左右子树递归使用相同的方法即可

这里使用了Arrays.copyOfRange，是一个左闭右开的函数，避免代码中过多的赋值来构造新的实参。

code

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0)return null;
        TreeNode root = new TreeNode(pre[0]);
        //在中序中找到根节点
        for(int i = 0;i<in.length;i++){
            if(in[i] == pre[0]){
                //递归遍历左子树,Arrays.copyOfRange左闭右开函数
                reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                //递归遍历右子树
        reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return root;
    }
}

30.调整数组顺序使奇数在偶数前面

题目描述

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

解题思路

遍历两次数组，第一次只添加奇数，第二次只添加偶数

code

public class Solution {
    public int[] reOrderArray (int[] array) {
        int[] res = new int[array.length];
        int temp = 0;
        //遍历两次数组，第一次只添加奇数，第二次只添加偶数
        for (int i = 0;i<array.length;i++){
            if(array[i] %2 != 0){
                res[temp++] = array[i];
            }
        }
        for(int i = 0;i<array.length; i++){
            if(array[i] % 2 == 0){
                res[temp++] = array[i];
            }
        }
        return res;
    }
}

31.二叉搜索树与双向链表

题目描述

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

解题思路

二叉搜索树：左边比根小，右边比根大。

二叉搜索树，中序遍历是有序的，先终须遍历存放在list中，然后遍历list修改指针指向。树的题目，先判断树是不是null，是的话，直接返回。

code

import java.util.*;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;
        //存放中序遍历的结果
        List<TreeNode> list = new ArrayList<TreeNode>();
        Convert(pRootOfTree,list);
        //修改指针指向
        for(int i = 0;i<list.size()-1; i++){
            list.get(i+1).left = list.get(i);
            list.get(i).right = list.get(i+1);
        }
        return list.get(0);
    }

    //这两个函数就是对多态的解释
    public void Convert(TreeNode tree,List<TreeNode> res){
        //中序遍历
        if(tree.left!=null){
            Convert(tree.left, res);
        }
        res.add(tree);
        if(tree.right != null){
            Convert(tree.right, res);
        }
    }
}

32.最小的K个数

题目描述

给定一个数组，找出其中最小的K个数。如果K>数组长度，则返回一个空数组。

解题思路

选择排序，但是只进行K轮。

code

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList();
        if(k> input.length)return res;
        for(int i = 0;i<k;i++){
            //进行K轮的选择排序,记录下标
            int min = i;
            for(int j = i+1;j<input.length; j++){
                if(input[j]<input[min])min = j;
            }
            //交换当前i和最小值
            int temp = input[i];
            input[i] = input[min];
            input[min] = temp;
            //加入结果集
            res.add(input[i]);

        }
        return res;
    }
}

33.从1到n整数中1出现的次数

题目描述

输入一个整数n，求1-n这n个整数的十进制表示中1出现的次数。例如：1-13包含1的数字有1,10,11,12,13，总共出现6次。

解题思路

将数字转化成字符串，然后遍历字符串统计。

code

public class Solution {
    //判断有几个1的函数
    public int count(int n){
        int count = 0;
        String str = String.valueOf(n);
        for(int i = 0;i<str.length(); i++){
            if(str.charAt(i) == '1'){
                count++;
            }
        }
        return count;
    }
    public int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        for(int i = 0;i<=n;i++){
            sum +=count(i);
        }
        return sum;
    }
    
}

34.数字在升序数组中出现的次数

题目描述

统计一个数字在升序数组中出现的次数。

输入：[1,2,3,3,3,3,4,5],3

返回：4

解题思路

似乎没什么规律。先找到K，然后双指针遍历，写的有点烂。

code

public class Solution {
    public int search(int[] nums, int target) {
        int pivot, left = 0, right = nums.length - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target) return pivot;
            if (target < nums[pivot]) right = pivot - 1;
            else left = pivot + 1;
        }
        return -1;
    }

    public int GetNumberOfK(int [] array , int k) {
        int index = search(array,k);
        int left = index-1;
        int right = index+1;
        int sum = 1;
        while (true){
            //往左找
            if(left<0)break;
            if(array[left]==k){
                sum++;
                left--;
            }else {
                break;
            }
        }
        while (true){
            //往右找
            if(right>array.length-1)break;
            if(array[right] == k){
                sum++;
                right++;
            }else {
                break;
            }

        }
        return sum;
    }
}

35.数字中只出现一次的两个数字

题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现两次，找出只出现一次的数字。

解题思路

第一眼就是哈希

code

import java.util.*;


public class Solution {
    public static int[] FindNumsAppearOnce (int[] array) {
        int[] hash = new int[100000];
        int[] res = new int[2];
        int index = 0;
        for(int i = 0;i<array.length; i++){
            hash[array[i]]++;
        }
        for(int i = 0;i<hash.length; i++){
            if(hash[i] == 1){
                res[index] = i;
                i++;
                if(i==2)break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,4,3,6,3,2,5,5};
        int[] res = FindNumsAppearOnce(arr);
        for(int i = 0;i<res.length; i++){
            System.out.println(res[i]);
        }
    }
}

36.和为S的连续正数序列

题目描述

输出所有和为S的连续正数序列。序列内按照从小到大的顺序，序列间按照开始数字从小到大的顺序。

解题思路

滑动窗口：首先是一个窗口，需要左边界i和右边界j来唯一表示一个窗口，滑动则意味着窗口始终从左往右移动，表明左边界i和右边界j始终往后移动，不会往左移动。滑动窗口主要应用在数组和字符串的场景。为了编程方便，滑动窗口一般是一个左闭右开的区间。

这题的解法可以这么理解：左指针表示循环，右指针找范围，左指针指向1的时候，右指针往后找，找到存，假如找到6超过范围，说明1开头找不到，这时候左指针指向2往右找。

code

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int low = 1,high = 2;
        while (high>low){
            //计算窗口内的和
            int index = (low+high)*(high-low+1)/2;
            if(index==sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = low;i<=high;i++){
                    list.add(i);
                }
                result.add(list);
                low++;
            }else if(index>sum){
                low++;
            }else {
                high++;
            }
        }
        return result;
    }
}

37.和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

解题思路

本来以为可以用滑动窗口，但是并不能。这题应该用的是双指针，但是不是滑动窗口的思想。左右夹逼的方法。

但是有一个问题，怎么保证最先找到的答案的乘积就是最小的呢：

假设b>a，现在a+b=k，然后(a-m)+(b+m)=ab-(b-a)m-m*m<ab，所以肯定是越往外越小，所以最外层是最小的。

code

import java.util.*;
public class Solution {
    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int low = 0,high = array.length-1;
        ArrayList<Integer> res = new ArrayList<>();
        if(array==null || array.length==0)return res;
        while (low < high){
            int index = array[low]+array[high];
            if(index == sum){
                res.add(array[low]);
                res.add(array[high]);
                return res;
            }else if(index < sum){
                low++;
            }else {
                high--;
            }
        }
        return res;
    }
}

38.左旋字符串

题目描述

给定字符串S，输出循环左移K位后的结果。

输入：”abcXYZdef”，3

返回值：”XYZdefabc”

解题思路

就是把前K位子串接下来拼接到后面吗。

substring()是左闭右开的函数，例如：

String test = "ascDEFxyz123";
System.out.println(test.substring(0,3));
System.out.println(test.substring(5));

输出是：

• asc
• Fxyz123

code

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str.length()<n || str==null)return str;
        return str.substring(n)+str.substring(0,n);
    }
}

39.圆圈中最后剩下的数

题目描述

0到n-1成环，然后按照0…m-1报数，每次喊道m-1的数离开，问最后剩下的是哪个数，如果没有小朋友，返回-1。

解题思路

这里直接采用的是模拟的思路。

code

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n == 0 || m == 0)return -1;
        // n对标I，m对标step
        //三个变量，一个记录步数，记录长度，一个记录次数
        int[] stu = new int[n];
        int step = 0,i = 0,count = 0;
        while (true){
            if(stu[i]==-1){
                //已经淘汰了
                if(++i==n)i = 0;
            }else {
                //没淘汰，判断是不是相等
                if(step==m-1){
                    stu[i] = -1;
                    count++;
                    if(count==n-1){
                        //返回最后一个不是-1的下标
                        for(int j = 0;j<stu.length; j++){
                            if(stu[j] != -1){
                                return j;
                            }
                        }
                    }
                }
                if(++step==m)step=0;
                if(++i==n) i = 0;
            }
        }
    }
}

40.求1+2+…+n

题目描述

求1+2+...+n，要求不能使用乘除法、for、while、if、else、Switch、case等关键字和条件判断语句(A?B:C)

解题思路

用递归的时候，需要判断终止条件，这个时候可以用与运算的短路效应来巧妙的避免掉if判断。

code

class Solution {
public:
    int Sum_Solution(int n) {
        bool x = n > 1 && (n += Sum_Solution(n-1)); // bool x只是为了不报错
        return n;
    }
};