【剑指offer】41-50题

痛定思痛。 2022-05-14 15:00 113阅读 0赞

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

思路：定义两个指针，分别递增，寻找和为s的序列。

代码实现：

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
            ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
            ArrayList<Integer> list = new ArrayList<>();
            if (sum < 3)
                return arrayList;
            int small = 1;
            int big = 2;
            while (small < (sum + 1) / 2) {
                int s = 0;
                for (int i = small; i <= big; i++) {
                    s += i;
                }
                if (s == sum) {
                    for (int i = small; i <= big; i++) {
                        list.add(i);
                    }
                    arrayList.add(new ArrayList<>(list));
                    list.clear();
                    small++;
                } else {
                    if (s > sum) {
                        small++;
                    } else {
                        big++;
                    }
                }
            }
            return arrayList;
        }

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

思路：定义两个指针，分别从前面和后面进行遍历。间隔越远乘积越小，所以是最先出现的两个数乘积最小

代码实现：

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if (array == null )
            return list;
        int left = 0;
        int right = array.length - 1;
    
        while (left < right) {
            int s = array[left] + array[right];
            if (s == sum) {
                list.add(array[left]);
                list.add(array[right]);
                return list;
            }else {
                if (s > sum) {
                    right--;
                }else {
                    left++;
                }
            }
        }
        return list;
    }

42.翻转字符串

思路：先将整个字符串翻转，然后将每个单词翻转。

代码实现：

public String ReverseSentence(String str) {
        if (str == null || str.length() == 0)
            return str;
        if (str.trim().length() == 0)
            return str;
        StringBuilder sb = new StringBuilder();
        String re = reverse(str);
        String[] s = re.split(" ");
        for (int i = 0; i < s.length - 1; i++) {
            sb.append(reverse(s[i]) + " ");
        }
        sb.append(reverse(s[s.length-1]));
        return String.valueOf(sb);
    }
    
    public String reverse(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = str.length() - 1; i >= 0 ; i--) {
            sb.append(str.charAt(i));
        }
        return String.valueOf(sb);
    }

42.1对于一个给定的字符序列S，请你把其循环左移K位后的序列输出

思路：拼接或反转三次字符串

代码实现：

public String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0)
            return str;
        String s1 = reverse(str.substring(0,n));
        String s2 = reverse(str.substring(n,str.length()));
        return reverse(s2)+reverse(s1);
    }

43.把n个骰子扔在地上，所有骰子朝上一面的点数之和为s,输入n,打印出s的所有可能出现的概率

思路：递归一般是自顶向下的分析求解，而循环则是自底向上，占用更少的空间和更少的时间，性能较好。定义一个二维数组，第一次掷骰子有6种可能，第一个骰子投完的结果存到probabilities\[0\]；第二次开始掷骰子，在下一循环中，我们加上一个新骰子，此时和为n的骰子出现次数应该等于上一次循环中骰子点数和为n-1,n-2,n-3, n-4,n-5，n-6的次数总和，所以我们把另一个数组的第n个数字设为前一个数组对应n-1,n-2,n-3,n-4,n-5，n-6之和

代码实现：

public void printProbability(int number) {
        if(number<1)
            return ;
        int g_maxValue=6;
        int[][] probabilities=new int[2][];
        probabilities[0]=new int[g_maxValue*number+1];
        probabilities[1]=new int[g_maxValue*number+1];
        int flag=0;
    
        // 当第一次抛掷骰子时，有6种可能，每种可能出现一次
        for(int i=1;i<=g_maxValue;i++)
            probabilities[0][i]=1;
    
        //从第二次开始掷骰子，假设第一个数组中的第n个数字表示骰子和为n出现的次数，
        for(int k=2;k<=number;++k) {
            for(int i=0;i<k;++i)
                // 第k次掷骰子，和最小为k，小于k的情况是不可能发生的,令不可能发生的次数设置为0！
                probabilities[1-flag][i]=0;
            // 第k次掷骰子，和最小为k，最大为g_maxValue*k
            for(int i=k;i<=g_maxValue*k;++i) {
                // 初始化，因为这个数组要重复使用，上一次的值要清0
                probabilities[1-flag][i]=0;
                for(int j=1;j<=i && j<=g_maxValue;++j)
                    probabilities[1-flag][i]+=probabilities[flag][i-j];
            }
            flag=1-flag;
        }
    
        double total=Math.pow(g_maxValue, number);
        for(int i=number;i<=g_maxValue*number;i++) {
            double ratio=(double) probabilities[flag][i]/total;
            System.out.println(i);
            System.out.println(ratio);
        }
    }

44.扑克牌的顺子

思路：用数组记录五张扑克牌，将数组调整为有序的，若0出现的次数>=顺子的差值，即为顺子。

代码实现：

public boolean isContinuous(int [] numbers) {
        if (numbers == null || numbers.length == 0)
            return false;
        int count = 0;
        int diff = 0;
        Arrays.sort(numbers);
    
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] == 0) {
                count++;
                continue;
            }
    
            if (numbers[i] != numbers[i+1]) {
                diff += numbers[i+1] - numbers[i] - 1;
            } else {
                return false;
            }
        }
    
        if (diff <= count)
            return true;
        return false;
    }

45.圆圈中最后剩下的数字（约瑟夫环）

思路：利用循环链表实现

代码实现：

public int LastRemaining_Solution(int n, int m) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        int bt = 0;
    
        for (int i = 0; i < n; i ++) {
            list.add(i);
        }
    
        while (list.size() > 1) {
            bt = (bt + m - 1) % list.size();
            list.remove(bt);
        }
        return list.size() == 1 ? list.get(0) : -1;
    }

46.求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：巧用递归（返回值类型为Boolean）

代码实现：

public int Sum_Solution(int n) {
        int sum = n;
        boolean result = (n > 0) && ((sum += Sum_Solution(n-1)) > 0);
        return sum;
    }

47.写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

思路：利用位运算

代码实现：

public int Add(int num1,int num2) {
        while (num2 != 0) {
            // 计算个位
            int temp = num1 ^ num2;
            // 计算进位（1+1）
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }

48.不能被继承的类

思路：私有构造器的类不能继承

49.将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

思路：若为负数，则输出负数，字符0对应48,9对应57，不在范围内则返回false。

代码实现：

public int StrToInt(String str) {
        if (str == null || str.length() == 0)
            return 0;
        int mark = 0;
        int number = 0;
        char[] chars = str.toCharArray();
    
        if (chars[0] == '-')
            mark = 1;
    
        for (int i = mark; i < chars.length; i++) {
            if (chars[i] == '+') {
                continue;
            }
            if (chars[i] < 48 || chars[i] > 57) {
                return 0;
            }
            number = number * 10 + chars[i] - 48;
        }
        return mark == 0 ? number : -number;
    }

50.求树中两个节点的最低公共祖先

（1）树是二叉搜索树

思路：从树的根节点开始遍历，如果根节点的值大于其中一个节点，小于另外一个节点，则根节点就是最低公共祖先。否则如果根节点的值小于两个节点的值，则递归求根节点的右子树，如果大于两个节点的值则递归求根的左子树。如果根节点正好是其中的一个节点，那么说明这两个节点在一条路径上，所以最低公共祖先则是根节点的父节点，时间复杂度是O(logn)，空间复杂度是O(1)

代码实现：

public static BinaryTreeNode getLowestCommonAncestor(BinaryTreeNode rootParent,BinaryTreeNode root,
                                                         BinaryTreeNode node1,BinaryTreeNode node2){
        if(root == null || node1 == null || node2 == null){
            return null;
        }
    
        if((root.value - node1.value)*(root.value - node2.value) < 0){
            return root;
        }else if((root.value - node1.value)*(root.value - node2.value) > 0){
            BinaryTreeNode newRoot = ((root.value > node1.value) && (root.value > node2.value))
                    ? root.leftNode : root.rightNode;
            return getLowestCommonAncestor(root,newRoot, node1, node2);
        }else{
            return rootParent;
        }
    }

（2）若树是普通树，但有指向父节点的指针

思路：两个节点如果在两条路径上，类似于求两个链表的第一个公共节点。由于每个节点的深度最多为logn，所以时间复杂度为O(logn),空间复杂度O(1)

代码实现：

public static BinaryTreeNode  getLowestCommonAncestor1(BinaryTreeNode root,BinaryTreeNode node1,
                                                           BinaryTreeNode node2){
        if(root == null || node1 == null || node2 == null){
            return null;
        }
        int depth1 = findTheDepthOfTheNode(root, node1, node2);
        if(depth1 == -1){
            return node2.parentNode;
        }
        int depth2 = findTheDepthOfTheNode(root, node2, node1);
        if(depth2 == -1){
            return node1.parentNode;
        }
        //p指向较深的节点q指向较浅的节点
        BinaryTreeNode p = depth1 > depth2 ? node1 : node2;
        BinaryTreeNode q = depth1 > depth2 ? node2 : node1;
        int depth =  Math.abs(depth1 - depth2);
    
        while(depth > 0){
            p = p.parentNode;
            depth --;
        }
        while(p != q){
            p = p.parentNode;
            q = q.parentNode;
        }
        return p;
    }
    //求node1的深度，如果node1和node2在一条路径上，则返回-1，否则返回node1的深度
    public static int findTheDepthOfTheNode(BinaryTreeNode root,BinaryTreeNode node1,
                                            BinaryTreeNode node2){
        int depth = 0;
        while(node1.parentNode != null){
            node1 = node1.parentNode;
            depth ++;
            if(node1 == node2){
                return -1;
            }
        }
        return depth;
    }

（3）若树是普通树，并没有指向父节点的指针

思路：用栈来实现类似于指向父节点指针的功能，获取node节点的路径时间复杂度为O(n),所以总的时间复杂度是O(n),空间复杂度是O(logn)

代码实现：

public static BinaryTreeNode getLowestCommonAncestor2(BinaryTreeNode root, BinaryTreeNode node1,
                                                          BinaryTreeNode node2){
        if(root == null || node1 == null || node2 == null){
            return null;
        }
        Stack<BinaryTreeNode> path1 = new Stack<BinaryTreeNode>();
        boolean flag1 = getThePathOfTheNode(root, node1,path1);
        if(!flag1){//树上没有node1节点
            return null;
        }
        Stack<BinaryTreeNode> path2 = new Stack<BinaryTreeNode>();
        boolean flag2 = getThePathOfTheNode(root, node2,path2);
        if(!flag2){//树上没有node2节点
            return null;
        }
    
        if(path1.size() > path2.size()){ //让两个路径等长
            while(path1.size() !=  path2.size()){
                path1.pop();
            }
        }else{
            while(path1.size() !=  path2.size()){
                path2.pop();
            }
        }
    
        if(path1 == path2){//当两个节点在一条路径上时
            path1.pop();
            return path1.pop();
        }else{
            BinaryTreeNode p = path1.pop();
            BinaryTreeNode q = path2.pop();
            while(q != p){
                p = path1.pop();
                q = path2.pop();
            }
            return p;
        }
    }
    
    //获得根节点到node节点的路径
    public static boolean getThePathOfTheNode(BinaryTreeNode root,BinaryTreeNode node,
                                              Stack<BinaryTreeNode> path){
        path.push(root);
        if(root == node){
            return true;
        }
        boolean found = false;
        if(root.leftNode != null){
            found = getThePathOfTheNode(root.leftNode, node, path);
        }
        if(!found && root.rightNode != null){
            found = getThePathOfTheNode(root.rightNode, node, path);
        }
        if(!found){
            path.pop();
        }
        return found;
    }

未完待续。。。。。。