【剑指Offer】解题思路拆解Java版——第六期

短命女 2022-11-18 10:55 58阅读 0赞

下面这段时间带来的是对于剑指Offer（第二版）一书中的算法题目进行阅读并分享。原书中一共66道题目，我们就一天11道，用六天的时间来进行讲解，最后一天来个总结，争取在一周的时间内介绍完这66道经典题目。要是喜欢的欢迎关注公众号《Java冢狐》来追更！

今天是剑指Offer的第六期，也是最后一期，我们终于把剑指offer的66道题目给看完了。完结撒花

另外由于原书是C++代码编写而成，这边我们用Java来实现一遍，顺便说一下相关的面试知识点，一起进行面试前的复习。希望大家能够喜欢。

另外有些地方的讲解可能并不是十分到位，在此更推荐更大家去看原书。

那么话不多少，让我们开始今天的解题之路吧！

### 五十六、数组中数字出现的次数 ###

*  问题

一个整型数组 `nums` 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这个问题的难点在于有两个数字只出现了一次，而不是一个，而且还要求了时间复杂度，如果只有一个数字的话，那么我们直接所有数字全部异或即可得到答案。但是两个的话这个问题就没有那么的简单。

但是通过题目的时间复杂度知道我们不能使用暴力法和哈希法，所以说还是要使用上异或这个特性才能解决问题。

所以我们尽可能要把这个数组转化为两个数组，使得这两个元素分别在这两个元素中，这样我们就能简化这个过程来减少时间复杂度。

我们可以知道的是这两个只出现一次的数字的二进制至少有一位不同，根据这个我们可以把数组进行拆分

class Solution {
        public int[] singleNumbers(int[] nums) {
            int x = 0;
            int y = 0;
            int n = 0;
            int m = 1;
            // 遍历亦或
            for (int num : nums)
                n ^= num;
            // 找到那个区分位
            while ((n & m) == 0)
                m <<= 1;
            // 根据区分位分别计算 xy
            for (int num : nums) {
                if ((num & m) != 0)
                    x ^= num;
                else
                    y ^= num;
            }
            return new int[]{x, y};
        }
    }

#### 拓展：数组中唯一只出现一次的数字 ####

在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

这个和上题一样的思路，要考虑数字的二进制形式，对于出现三次的数字，其二进制出现的次数都是三的倍数，因此我们统计所有数字二进制位中1出现的次数，并且对3求余即可

class Solution {
        public int singleNumber(int[] nums) {
            int[] counts = new int[32];
            for (int num : nums) {
                for (int j = 0; j < 32; j++) {
                    counts[j] += num & 1;
                    num >>>= 1;
                }
            }
            int ans = 0;
            for (int i = 0; i < 32; i++) {
                ans <<= 1;
                ans |= counts[31 - i] % 3;
            }
            return ans;
        }
    }

### 五十七、和为s的数字 ###

*  问题

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

本来这个题目就够简单的了，直接哈希表一遍就可以，这次题目告诉了我们递增数列，那就更好了，直接使用双指针搞定

class Solution {
        public int[] twoSum(int[] nums, int target) {
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int s = nums[i] + nums[j];
                if (s < target)
                    i++;
                else if (s > target)
                    j--;
                else
                    return new int[]{nums[i], nums[j]};
            }
            return new int[0];
        }
    }

#### 拓展：和为s的连续正数序列 ####

输入一个正整数 `target` ，输出所有和为 `target` 的连续正整数序列（至少含有两个数）。

既然是连续正整数序列，那么我们可以建立一个滑动窗口来解决问题

class Solution {
        public int[][] findContinuousSequence(int target) {
            int left = 1, right = 2, temp = 3;
            List<int[]> res = new ArrayList<>();
            while(left < right) {
                if(temp == target) {
                    int[] ans = new int[right - left + 1];
                    for(int k = left; k <= right; k++)
                        ans[k - left] = k;
                    res.add(ans);
                }
                if(temp >= target) {
                    temp -= left;
                    left++;
                } else {
                    right++;
                    temp += right;
                }
            }
            return res.toArray(new int[0][]);
        }
    }

### 五十八、翻转单词顺序 ###

*  问题

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

还是使用双指针来解决

class Solution {
        public String reverseWords(String s) {
            // 删除首尾空格
            s = s.trim();
            int j = s.length() - 1, i = j;
            StringBuilder res = new StringBuilder();
            while (i >= 0) {
                // 搜索首个空格
                while (i >= 0 && s.charAt(i) != ' ')
                    i--;
                // 添加单词
                res.append(s.substring(i + 1, j + 1) + " ");
                // 跳过单词间空格
                while (i >= 0 && s.charAt(i) == ' ')
                    i--;
                // j 指向下个单词的尾字符
                j = i;
            }
            // 转化为字符串并返回
            return res.toString().trim();
        }
    }

#### 拓展：左旋转字符串 ####

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

额有点过于简单，直接切片即可

class Solution {
        public String reverseLeftWords(String s, int n) {
            return s.substring(n, s.length()) + s.substring(0, n);
        }
    }

### 五十九、队列的最大值 ###

*  问题

给定一个数组 `nums` 和滑动窗口的大小 `k`，请找出所有滑动窗口里的最大值。

这个题目要是简单处理的话，就暴力算法即可

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (k == 0)
                return new int[0];
            int ans[] = new int[nums.length - k + 1];
            int len = ans.length;
            for (int i = 0; i < len; i++) {
                int max = nums[i];
                for (int j = i + 1; j < i + k; j++) {
                    max = Math.max(max, nums[j]);
                }
                ans[i] = max;
            }
            return ans;
        }
    }

但是这个题目还存在着优化的空间，就是关于获取窗口内最大值得时间复杂度从O（k）降低到O（1）

这个就需要使用到单调队列来完成了

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k == 0)
                return new int[0];
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[nums.length - k + 1];
            for (int j = 0, i = 1 - k; j < nums.length; i++, j++) {
                if (i > 0 && deque.peekFirst() == nums[i - 1])
                    // 删除 deque 中对应的 nums[i-1]
                    deque.removeFirst();
                while (!deque.isEmpty() && deque.peekLast() < nums[j])
                    // 保持 deque 递减
                    deque.removeLast();
                deque.addLast(nums[j]);
                if (i >= 0)
                    // 记录窗口最大值
                    res[i] = deque.peekFirst();
            }
            return res;
        }
    }

#### 拓展：队列的最大值 ####

请定义一个队列并实现函数 `max_value` 得到队列里的最大值，要求函数`max_value`、`push_back` 和 `pop_front` 的**均摊**时间复杂度都是O(1)。

若队列为空，`pop_front` 和 `max_value` 需要返回 -1。

由于最大值可能出栈导致无法找到次大值，所需需要维护一个递减列表。

class MaxQueue {
        Queue<Integer> queue;
        Deque<Integer> deque;
    
        public MaxQueue() {
            queue = new LinkedList<>();
            deque = new LinkedList<>();
        }
    
        public int max_value() {
            return deque.isEmpty() ? -1 : deque.peekFirst();
        }
    
        public void push_back(int value) {
            queue.offer(value);
            while (!deque.isEmpty() && deque.peekLast() < value)
                deque.pollLast();
            deque.offerLast(value);
        }
    
        public int pop_front() {
            if (queue.isEmpty())
                return -1;
            if (queue.peek().equals(deque.peekFirst()))
                deque.pollFirst();
            return queue.poll();
        }
    }

### 六十、n个骰子的点数 ###

*  问题

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

还是老方法，动态规划，把n个骰子的问题分解成n-1个

class Solution {
        public double[] dicesProbability(int n) {
            double pre[]={1/6d,1/6d,1/6d,1/6d,1/6d,1/6d};
            for(int i = 2;i <= n;i++){
                //为n的数组概率
                double mid[] = new double[6*i - i + 1];
                for(int j = 0;j < pre.length;j++){
                    for(int a = 0;a < 6;a++){
                        //为(n-1)和1的数组概率计算
                        mid[j + a] += pre[j] * (1 / 6d);
                    }
                }
                //为n-1的数组概率
                pre = mid;
            }
            return pre;
        }
    }

### 六十一、扑克牌中的顺子 ###

*  问题

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

首先我们要简化题目，什么样的组合满足题目，首先除大小王外无重复，且最大值和最小值的差小于5.

那么基于这两个条件我们可以使用集合set+遍历的方法搞定

class Solution {
        public boolean isStraight(int[] nums) {
            Set<Integer> repeat = new HashSet<>();
            int max = 0, min = 14;
            for (int num : nums) {
                // 由于大小王可以变成任何数字所以没影响继续走
                if (num == 0)
                    continue;
                max = Math.max(max, num);
                min = Math.min(min, num);
                if (repeat.contains(num))
                    return false;
                repeat.add(num);
            }
            return max - min < 5;
        }
    }

### 六十二、圆圈最后剩下的数字 ###

*  问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

这个在我们的一行代码解决问题的文章中已经讲解过了，所以在此不过多阐述

class Solution {
        public int lastRemaining(int n, int m) {
            if(n==1)
                return 0;
            return (lastRemaining(n-1,m)+m)%n;
        }
    }

### 六十三、股票的最大利润 ###

*  问题

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

题目中限定了只能买卖一次，所以我们要使用动态规划来解决问题。首要就是找到状态转移方程：

由于只能卖出一次，所以关键点在于何时买和何时卖，所以第n天的利润等于前n-1天的利润和第n天卖出利润的最大值

class Solution {
        public int maxProfit(int[] prices) {
            int min = Integer.MAX_VALUE, max = 0;
            for (int price : prices) {
                min = Math.min(min, price);
                max = Math.max(max, price - min);
            }
            return max;
        }
    }

### 六十四、求1+2+3+…+n ###

*  问题

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

由于限制了很多，所以我们能用的也就加减法、赋值、位运算以及逻辑运算符。要是没有限制的话，直接使用递归就完事了，但是现在使用递归无法判断递归出口，所以需要用逻辑运算符的短路性质来解决问题

class Solution {
        public int sumNums(int n) {
            boolean falg = n > 0 && (n += sumNums(n - 1)) > 0;
            return n;
        }
    }

### 六十五、不用加减乘除做加法 ###

*  问题

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

class Solution {
        public int add(int a, int b) {
            // 当进位为0退出
            while (b != 0) {
                // c为进位
                int c = (a & b) << 1;
                // a为非进位和
                a ^= b;
                // b为进位
                b = c;
            }
            return a;
        }
    }

### 六十六、构建乘积数组 ###

*  问题

给定一个数组 `A[0,1,…,n-1]`，请构建一个数组 `B[0,1,…,n-1]`，其中 `B[i]` 的值是数组 `A` 中除了下标 `i` 以外的元素的积, 即 `B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]`。不能使用除法。

由于不能使用除法，只能使用乘法，所以我们可以构建两个数组分别取维护i左侧和右侧的乘积和

class Solution {
        public int[] constructArr(int[] a) {
            if (a == null || a.length == 0)
                return a;
            int len = a.length;
            int[] left = new int[len];
            int[] right = new int[len];
            left[0] = right[len - 1] = 1;
            for (int i = 1; i < len; i++)
                left[i] = left[i - 1] * a[i - 1];
            for (int i = len - 2; i >= 0; i--)
                right[i] = right[i + 1] * a[i + 1];
            int[] ans = new int[len];
            for (int i = 0; i < len; i++) {
                ans[i] = left[i] * right[i];
            }
            return ans;
        }
    }

### 总结 ###

至此我们就把所有的六十六道题目给看完了、分析完了，是不是有些意犹未尽？

接来下我会结合我的面试经历系统的总结下这剑指Offer的六十六道算法题目，其中有哪些思想和思路是我们应该去学习和掌握的。

### 最后 ###

*  如果觉得看完有收获，希望能关注一下，顺便给我点个赞，这将会是我更新的最大动力，感谢各位的支持
 *  欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
 *  求一键三连：点赞、转发、在看。
 *  如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。

——我是冢狐，和你一样热爱编程。

![image][]

[image]: /images/20221022/9f21fd4320df4d68a9cea99dd038386d.png