剑指offer题解——位运算和哈希表

我就是我 2023-03-01 12:30 17阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 15. 二进制中1的个数
     *   *  解法
     *  剑指 Offer 39. 数组中出现次数超过一半的数字
     *   *  投票法
     *  剑指 Offer 48. 最长不含重复字符的子字符串
     *   *  滑动窗口
     *  剑指 Offer 50. 第一个只出现一次的字符
     *   *  hashmap
         *   *  推荐阅读

## 剑指 Offer 15. 二进制中1的个数 ##

[剑指 Offer 15. 二进制中1的个数][Offer 15. _1]

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：
    
    输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
    示例 2：
    
    输入：00000000000000000000000010000000
    输出：1
    解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
    示例 3：
    
    输入：11111111111111111111111111111101
    输出：31
    解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

### 解法 ###

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            int sum = 0;
            while (n != 0) {
        
                sum++;
                // n & (n - 1)运算，将n的二进制数最后一位1变为0，循环直到n为0
                n = n & (n - 1);
            }
            return sum;
        }
    }

## 剑指 Offer 39. 数组中出现次数超过一半的数字 ##

[剑指 Offer 39. 数组中出现次数超过一半的数字][Offer 39.]

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
    
    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    
    示例 1:
    
    输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2
     
    限制：
    
    1 <= 数组长度 <= 50000

### 投票法 ###

class Solution {
        
        public int majorityElement(int[] nums) {
        
            int x = 0, votes = 0;
            for (int num : nums) {
        
                if (votes == 0) {
        
                    x = num;
                }
                votes += num == x ? 1 : -1;
            }
            return x;
        }
    }

## 剑指 Offer 48. 最长不含重复字符的子字符串 ##

[剑指 Offer 48. 最长不含重复字符的子字符串][Offer 48.]

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:
    
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    示例 2:
    
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    示例 3:
    
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     
    
    提示：
    
    s.length <= 40000

### 滑动窗口 ###

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            if (s.length() == 0) {
        
                return 0;
            }
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            int max = 0;
            int left = 0;
            for (int i = 0; i < s.length(); i++) {
        
                if (map.containsKey(s.charAt(i))) {
        
                    left = Math.max(left, map.get(s.charAt(i)) + 1);
                }
                map.put(s.charAt(i), i);
                max = Math.max(max, i - left + 1);
            }
            return max;
        }
    }

## 剑指 Offer 50. 第一个只出现一次的字符 ##

[剑指 Offer 50. 第一个只出现一次的字符][Offer 50.]

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:
    
    s = "abaccdeff"
    返回 "b"
    
    s = "" 
    返回 " "
     
    
    限制：
    
    0 <= s 的长度 <= 50000

### hashmap ###

class Solution {
        
        public char firstUniqChar(String s) {
        
            Map<Character, Boolean> map = new HashMap<>();
            int length = s.length();
            for (int i = 0; i < length; i++) {
        
                map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
            }
            for (int i = 0; i < length; i++) {
        
                if (map.get(s.charAt(i))) {
        
                    return s.charAt(i);
                }
            }
            return ' ';
        }
    }

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

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

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

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

![format_png][]

[Offer 15. _1]: https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
[Offer 39.]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[Offer 48.]: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
[Offer 50.]: https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-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/20230208/8749f2034f1241b28af4d2f8f3b25b5d.png