剑指Offer题解——随机刷题(二)

阳光穿透心脏的1/2处 2022-11-27 12:17 168阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 51. 数组中的逆序对
     *   *  分治算法
     *  剑指 Offer 56 - I. 数组中数字出现的次数
     *   *  位运算
     *  剑指 Offer 56 - II. 数组中数字出现的次数 II
     *   *  位运算
     *  剑指 Offer 57. 和为s的两个数字
     *   *  双指针
     *  剑指 Offer 57 - II. 和为s的连续正数序列
     *   *  双指针
         *   *  推荐阅读

## 剑指 Offer 51. 数组中的逆序对 ##

[剑指 Offer 51. 数组中的逆序对][Offer 51.]

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:
    
    输入: [7,5,6,4]
    输出: 5
     
    
    限制：
    
    0 <= 数组长度 <= 50000

### 分治算法 ###

详解见[leetcode][]

class Solution {
        
        public int reversePairs(int[] nums) {
        
            int len = nums.length;
            if (len < 2) {
        
                return 0;
            }
            // 如果不能在nums修改，就copy一下nums
            int[] copy = new int[len];
            for (int i = 0; i < len; i++) {
        
                copy[i] = nums[i];
            }
            int[] temp = new int[len];
            return reversePairs(copy, 0, len - 1, temp);
        }
        private int reversePairs(int[] nums, int left, int right, int[] temp) {
        
            if (left == right) {
        
                return 0;
            }
            int mid = left + ((right - left) >> 1);
            int leftPairs = reversePairs(nums, left, mid, temp);
            int rightPairs = reversePairs(nums, mid + 1, right, temp);
            if (nums[mid] <= nums[mid + 1]) {
        
                return leftPairs + rightPairs;
            }
            int crossPairs = mergeAndCount(nums, left, mid, right, temp);
            return crossPairs + leftPairs + rightPairs;
        }
        private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        
            for (int i = left; i <= right; i++) {
        
                temp[i] = nums[i];
            }
            int i = left;
            int j = mid + 1;
            int count = 0;
            for (int k = left; k <= right; k++) {
        
                if (i == mid + 1) {
        
                    nums[k] = temp[j];
                    j++;
                } else if (j == right + 1) {
        
                    nums[k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
        
                    nums[k] = temp[i];
                    i++;
                } else {
        
                    nums[k] = temp[j];
                    j++;
                    count += mid - i + 1;
                }
            }
            return count;
        }
    }

## 剑指 Offer 56 - I. 数组中数字出现的次数 ##

[剑指 Offer 56 - I. 数组中数字出现的次数][Offer 56 - I.]

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

示例 1：
    
    输入：nums = [4,1,4,6]
    输出：[1,6] 或 [6,1]
    示例 2：
    
    输入：nums = [1,2,10,4,1,4,3,3]
    输出：[2,10] 或 [10,2]
     
    
    限制：
    
    2 <= nums.length <= 10000

### 位运算 ###

异或满足交换律，第一步异或，相同的数其实都抵消了，剩下两个不同的数。这两个数异或结果肯定有某一位为1，不然都是0的话就是相同数。找到这个位，不同的两个数一个在此位为0，另一个为1。按此位将所有数分成两组，分开后各自异或，相同的两个数异或肯定为0（而且分开的时候，两个数必为一组）。剩下的每组里就是我门要找的数。

class Solution {
        
        public int[] singleNumbers(int[] nums) {
        
            // 用于将所有的数异或起来
            int k = 0;
            for (int num : nums) {
        
                k ^= num;
            }
            // 获得k中最低位的1
            int mask = 1;
            while ((k & mask) == 0) {
        
                mask <<= 1;
            }
            // first、second为两个不同的数
            int first = 0;
            int second = 0; 
            // first、second中有一个数的二进制形式最后一个1和mask相同，所有可以将这两个数分开
            for (int num : nums) {
        
                if ((num & mask) == 0) {
        
                    first ^= num;
                } else {
        
                    second ^= num;
                }
            }
            return new int[]{
        first, second};
        }
    }

## 剑指 Offer 56 - II. 数组中数字出现的次数 II ##

[剑指 Offer 56 - II. 数组中数字出现的次数 II][Offer 56 - II. _ II]

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

示例 1：
    
    输入：nums = [3,4,3,3]
    输出：4
    示例 2：
    
    输入：nums = [9,1,7,9,7,9,7]
    输出：1
     
    
    限制：
    
    1 <= nums.length <= 10000
    1 <= nums[i] < 2^31

### 位运算 ###

如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;

上述思路同样适用于数组中一个数字出现一次，其他数字出现奇数次问题(如果是偶数次，直接用异或就可)。

class Solution {
        
        public int singleNumber(int[] nums) {
        
            if (nums.length == 0) {
        
                return -1;
            }
            int[] bitSum = new int[32];
            int res = 0;
            for (int num : nums) {
        
                int bitMask = 1;
                for (int i = 31; i >= 0; i--) {
        
                    if ((num & bitMask) != 0) {
        
                        bitSum[i]++;
                    }
                    bitMask = bitMask << 1;
                }
            }
            for (int i = 0; i < 32; i++) {
        
                res = res << 1;
                res += bitSum[i] % 3;
            }
            return res;
        }
    }

## 剑指 Offer 57. 和为s的两个数字 ##

[剑指 Offer 57. 和为s的两个数字][Offer 57. _s]

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

示例 1：
    
    输入：nums = [2,7,11,15], target = 9
    输出：[2,7] 或者 [7,2]
    示例 2：
    
    输入：nums = [10,26,30,31,47,60], target = 40
    输出：[10,30] 或者 [30,10]
     
    
    限制：
    
    1 <= nums.length <= 10^5
    1 <= nums[i] <= 10^6

### 双指针 ###

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];
        }
    }

## 剑指 Offer 57 - II. 和为s的连续正数序列 ##

[剑指 Offer 57 - II. 和为s的连续正数序列][Offer 57 - II. _s]

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

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
    
    输入：target = 9
    输出：[[2,3,4],[4,5]]
    示例 2：
    
    输入：target = 15
    输出：[[1,2,3,4,5],[4,5,6],[7,8]]
     
    
    限制：
    
    1 <= target <= 10^5

### 双指针 ###

left 到 right之间的和sum

*  sum < target, right++
 *  sum > target, left++
 *  sum == target, 添加结果，left++，因为从left开始只有一个符号条件。

class Solution {
        
        public int[][] findContinuousSequence(int target) {
        
            List<int[]> res = new ArrayList<>();
            for (int left = 1, right = 2; left < right;) {
        
                int sum = (left + right) * (right - left + 1) / 2;
                if (sum == target) {
        
                    int[] tmp = new int[right - left + 1];
                    for (int i = left; i <= right; i++) {
        
                        tmp[i - left] = i;
                    }
                    res.add(tmp);
                    left++;
                } else if (sum < target) {
        
                    right++;
                } else {
        
                    left++;
                }
            }
            return res.toArray(new int[res.size()][]);
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Offer 51.]: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
[leetcode]: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
[Offer 56 - I.]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
[Offer 56 - II. _ II]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[Offer 57. _s]: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
[Offer 57 - II. _s]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20221124/b4f93699f6f94d3fad1a637f28a814a0.png