栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer1-32题思路

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer1-32题思路

剑指 Offer II 002. 二进制加法

给定两个 01 字符串 a 和 b ,请计算它们的和,并以二进制字符串的形式输出。
1、先将 aa 和 bb 转化成十进制数,求和后再转化为二进制数。
但非常简单的实现基于 Python 和 Java 本身的高精度功能,在其他的语言中可能并不适用,并且在 Java 中:
如果字符串超过 3333 位,不能转化为 Integer
如果字符串超过 6565 位,不能转化为 Long
如果字符串超过 500000001500000001 位,不能转化为 BigInteger

方法一 :直接模拟(逢2进1)

伪代码:
使用一个变量 carry 表示上一个位置的进位,初始值为 0
循环次数 n=max{∣a∣,∣b∣} 从最低位开始遍历
当前位置为(ai+bi+carry)mod2
进位为(carry+ai+bi)/2向下取整

可以先反转这个代表二进制数字的字符串,然后低下标对应低位,高下标对应高位

直接模拟代码:
class Solution {
public:
    string addBinary(string a, string b) {
 string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。

输入: n = 2
输出: [0,1,1]
解释:
0 --> 0 数字0对应二进制没有1
1 --> 1 数字1对应二进制有1个1
2 --> 10 数字2对应二进制有1个1
因此数组为[0,1,1]

可以直接每个对int 型的数都可以用 32 位二进制数表示,只要遍历其二进制表示的每一位即可得到 1 的数目。下面可以减少运算

方法一 :Brian Kernighan 算法


代码
class Solution {
public:
    int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    vector countBits(int n) {
        vector bits(n + 1);
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }
};
方法二 动态规划

这个方法是为了使用前面已经得到的值,避免“重复运算”
用一个vector存放以前的数据,满足条件时,从以前存放的数据里面获得当前的值


为了判断一个正整数是不是 2 的整数次幂,可以利用方法一中提到的按位与运算的性质。如果正整数 y 是 2 的整数次幂,则 yy的二进制表示中只有最高位是 1,其余都是 0,因此 y&(y-1)=0。
也就是本来就一个1,而本来就一个1只能在最高位

使用容器存放以前的值,vector刚开始将全部被赋值为0

class Solution {
public:
    vector countBits(int n) {
        vector bits(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
            cout << bits[i]< 
方法三 动态规划 保存最低有效位 

方法二需要维护最高有效位,这里不维护最高有效位了


代码
class Solution {
public:
    vector countBits(int n) {
        vector bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
};
方法四 动态规划 最低设置位

代码
class Solution {
public:
    vector countBits(int n) {
        vector bits(n + 1);
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
};
剑指 Offer II 004. 只出现一次的数字

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

方法一:哈希表映射

哈希映射统计数组中每个元素的出现次数
然后再来个循环统计只有1的元素

方法二:依次确定每一个二进制位


按位数将每个元素的二进制位加起来,然后求模,剩下就是异常的那个
使用位运算 (x >> i) &1得到 x的第 i 个二进制位

代码
class Solution {
public:
    int singleNumber(vector& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3) {
                ans |= (1 << i);
                cout << ans << endl;
            }
        }
        cout << ans << endl;
        return ans;
    }
};
剑指 Offer II 005. 单词长度的最大乘积

给定一个字符串数组 words,请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时,它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串,返回 0。

输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符,且长度的乘积最大。

方法一:


class Solution {
public:
    int maxProduct(vector& words) {
        int length = words.size();
        vector masks(length);
        for (int i = 0; i < length; i++) {
            string word = words[i];
            int wordLength = word.size();
            for (int j = 0; j < wordLength; j++) {
                masks[i] |= 1 << (word[j] - 'a');
            }
        }
        int maxProd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProd = max(maxProd, int(words[i].size() * words[j].size()));
                }
            }
        }
        return maxProd;
    }
};
剑指 Offer II 006. 排序数组中两个数字之和

给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。
输入:numbers = [1,2,4,6,10], target = 8
输出:[1,3]
解释:2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

方法一:二分查找

数组有序,固定一个数,查找这个数的右侧(不需要查左侧,不可能是左侧的,因为当我固定这个数前,就是从左侧那个数固定过来的)

代码
class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int low = i + 1, high = numbers.size() - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    cout << i;
                    cout << mid;
                    return { i, mid };
                }
                else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                }
                else {
                    low = mid + 1;
                }
            }
        }
        return { -1, -1 };
    }
};
方法二:双指针

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
每次计算两个指针指向的两个元素之和,并和目标值比较。
如果两个元素之和等于目标值,则发现了唯一解。
如果两个元素之和小于目标值,则将左侧指针右移一位。
如果两个元素之和大于目标值,则将右侧指针左移一位。
移动指针之后,重复上述操作,直到找到答案。

代码
class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return {low, high};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return {-1, -1};
    }
};
剑指 Offer II 007. 数组中和为 0 的三个数 方法一:暴力三层循环

for i=0 to n
for j=i+1 to n
for k=j+1 to n

这样有可能会出现重复的问题,那么先保存下来,再排序,放到哈希表中,判断哈希表中是否存在,如果不存在就放入,否则就不放入

方法二:双指针

先排序,然后用二分查找
排完序后,在i的右边用双指针 一个在头,一个在尾

  for i=0 to n-2:
      left=i+1;
      right=n-2
      while(left 
剑指 Offer II 008. 和大于等于 target 的最短子数组 
方法一:前缀和 + 二分查找 

代码
class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        vector sums(n + 1, 0);
        // 为了方便计算,令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {

            sums[i] = sums[i - 1] + nums[i - 1];
        }

        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            auto bound = lower_bound(sums.begin(), sums.end(), target);
            if (bound != sums.end()) {
                cout << bound - sums.begin();
                ans = min(ans, static_cast((bound - sums.begin()) - (i - 1)));
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};
方法二:滑动窗口

类似双指针

本题

class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};
剑指 Offer II 009. 乘积小于 K 的子数组

给定一个正整数数组 nums和整数 k ,请找出该数组内乘积小于 k 的连续的子数组的个数。
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。、

方法一:前缀和 方法二:滑动窗口

下面这个有问题


剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

方法一:枚举


代码
class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int count = 0;
        int a = 0;
        for (int start = 0; start < nums.size(); ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
};
方法三

剑指 Offer II 011. 0 和 1 个数相同的子数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

方法


代码
class Solution {
public:
    int findMaxLength(vector& nums) {
        int maxLength = 0;
        unordered_map mp;
        int counter = 0;
        mp[counter] = -1;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {
                counter++;
            }
            else {
                counter--;
            }
            if (mp.count(counter)) {
                int prevIndex = mp[counter];
                maxLength = max(maxLength, i - prevIndex);
            }
            else {
                mp[counter] = i;
            }
        }
        return maxLength;
    }
};
剑指 Offer II 012. 左右两边子数组的和相等

给你一个整数数组 nums ,请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。

输入:nums = [1,7,3,6,5,6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

方法:前缀和


代码
class Solution {
public:
    int pivotIndex(vector& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};
剑指 Offer II 013. 二维子矩阵的和


方法一:一维前缀和


代码
class NumMatrix {
public:
    vector> sums;

    NumMatrix(vector>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m, vector(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
};
二维前缀和




代码
class NumMatrix {
public:
    vector> sums;

    NumMatrix(vector>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};
剑指 Offer II 014. 字符串中的变位词

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说,第一个字符串的排列之一是第二个字符串的 子串 。

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

方法1:滑动窗口

既然想找排列,那就是有相同的元素。用哈希表看是否有相同的元素。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }

        vector cnt1(26), cnt2(26);
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1[i] - 'a'];
            ++cnt2[s2[i] - 'a'];
        }

        if (cnt1 == cnt2) {
            return true;
        }

        for (int i = n; i < m; ++i) {
            ++cnt2[s2[i] - 'a'];
            --cnt2[s2[i - n] - 'a'];
            if (cnt1 == cnt2) {
                return true;
            }
        }
        return false;
    }
};
剑指 Offer II 016. 不含重复字符的最长子字符串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长连续子字符串 的长度。

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子字符串是 “abc”,所以其长度为 3。

方法一:滑动窗口

用两个指针维护一个滑动窗口
用一个哈希表存放滑动窗口里的元素
右指针向右移动,当遇到重复元素就停止,让左指针向右移动

有个优化的方法就是哈希表存放元素的下标,当右指针碰到重复的元素,让左指针移动到哈希表中元素的下标+1,可以减少运算

代码
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合,记录每个字符是否出现过
        unordered_set occ;
        int n = s.size();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置,初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};
剑指 Offer II 017. 含有所有字符的最短字符串

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串,则返回空字符串 “” 。

如果 s 中存在多个符合条件的子字符串,返回任意一个。

注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

思路一:滑动窗口

维护一个滑动窗口

剑指 Offer II 018. 有效的回文

给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。

本题中,将空字符串定义为有效的 回文串 。

输入: s = “A man, a plan, a canal: Panama”
输出: true
解释:“amanaplanacanalpanama” 是回文串

可以看到标点符合不需要保留

方法一:筛选和判断

首先遍历一遍字符串,然后保留字母和数字到另一个字符串里
然后或者反转字符串判断两者是否一样
或者使用双指针,左边一个右边一个,然后向中间移动

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;
    }
};
方法二:直接在原字符串上判断

使用上面双指针,但是移动时忽略标点符号

剑指 Offer II 019. 最多删除一个字符得到回文

给定一个非空字符串 s,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
输入: s = “aba”
输出: true

方法一:贪心和双指针


代码
class Solution {
public:
    bool checkPalindrome(const string& s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    bool validPalindrome(string s) {
        int low = 0, high = s.size() - 1;
        while (low < high) {
            char c1 = s[low], c2 = s[high];
            if (c1 == c2) {
                ++low;
                --high;
            }
            else {
                return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
            }
        }
        return true;
    }
};
剑指 Offer II 020. 回文子字符串的个数

给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

输入:s = “abc”
输出:3
解释:三个回文子串: “a”, “b”, “c”

暴力法:枚举所有可能,O(n^2)再去判断,那就是O(n)

方法一:中心扩展


奇数时aba可以直接一个
偶数时为俩

剑指 Offer II 021. 删除链表的倒数第 n 个结点

链表操作,一种常用的技巧是添加一个哑节点(dummy node)
本题是删除倒数第n个结点

方法一:计算链表长度

第一遍获取链表长度
第二遍删除

方法二:栈

先入栈,然后出栈时查是第几个

方法三:双指针

左指针比右指针超前n个元素,当右指针到达末尾(空),左指针正好为那个元素

剑指 Offer II 022. 链表中环的入口节点

给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

方法一:哈希表

定义一个哈希表,用于存放已经访问的节点,

方法二:快慢指针

设置fast和slow指针,fast每次走两步,slow每次走一步。

为什么两个指针会相遇?
因为运动是相对的。
将慢指针视作参照系,考虑快指针相对于慢指针的速度,如果慢指针每次走一步,快指针每次走两步,那么等于慢指针不变,快指针相对于慢指针每次走一步。
那么问题转换为一个指针一步步走,假如list有环的话一定能回环的原点

fast一定比slow多走了k步,这多走的k步其实就是fast指针在环里转圈圈,所以k的值就是环长度的「整数倍」,为什么是整数倍?

假设在蓝点相遇,两者同时走了a的距离,然后在蓝点相遇了,快的减去慢的一定是环长度的整数倍
f为快指针走的路程,s是慢指针走的路程,由下面前两个得出第三个式子

剑指 Offer II 023. 两个链表的第一个重合节点

给定两个单链表的头节点 headA 和 headB ,请找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:


方法一:哈希表

方法二:双指针

思路:

简单来说,如果pA指针到了末尾,让它去B的开头,如果pB指针到了末尾,让它去A的开头,这样一定会同时到达相交节点
下面证明下:

剑指 Offer II 024. 反转链表

给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

方法一:正常迭代

方法二:递归

不用看了

剑指 Offer II 025. 链表中的两数相加

给定两个 非空链表 11和 12 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外,这两个数字都不会以零开头。

方法一:栈

将两列元素压到栈里,然后开始每次谈两个,让他们相加,如果有一个栈里为空,那么设置其为0,然后需要注意进位,将进位想加

附加题:反转链表 方法一:迭代


方法二:递归 剑指 Offer II 026. 重排链表


方法一:利用线性表

利用线性表存储链表的各个节点,然后利用线性表可以下标访问的特点然后直接通过下标访问修改它的next值。

寻找链表中间节点

快慢指针,快指针每次走两步,慢指针每次走一步,当快指针不能移动了(下一个为空,或者下下个为空)此时的慢指针指向的就为中间节点

偶数位置

奇数位置

合并链表

假设两个链表元素相等,或者第一个链表比第二个链表多一个元素


方法二:

目标链表是原链表的左半端和反转后的右半端合并后的结果

所以任务变为
1、找到原链表的中点,这里用上面那个寻找链表中间节点方法
2、将原链表的右半端反转,这里用上面题的迭代
3、将原链表的两端合并

剑指 Offer II 027. 回文链表

给定一个链表的 头节点 head ,请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

方法一:辅助空间

1、将值复制到数组列表中
2、使用双指针法判断是否为回文

方法二 :递归

递归是最后一个运行的,用一个全局指针指向元素,将这两个对比
递归过程建议看图解
图解

方法三:特点

剑指 Offer II 028. 展平多级双向链表

多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。

给定位于列表第一级的头节点,请扁平化列表,即将这样的多级双向链表展平成普通的双向链表,使所有结点出现在单级双链表中。

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

方法 插入

删除

删除元素先判断字典里存在吗
如果存在,那么将要删除元素,将被删除元素和最后一个元素交换,这样就避免移动很多元素了

得到任意值
 srand((unsigned)time(NULL));
 int randomIndex = rand() % nums.size();
 return nums[randomIndex];
剑指 Offer II 031. 最近最少使用缓存


解法

缓存用双向链表存储
而快速得到用一个unordered_map来实现,这个map存储值和节点(这个节点就是链表上的节点,也就是通过key能快速定位到这个节点)


得到值
1、在map中根据key确定是否存在
2、如果存在,那么返回节点对应的值,并且处理影响也即移到头部
放值
分为key存在和不存在

当key存在,根据哈希表定位,修改它的值,并移动到头部
当key不存在
创建一个新的节点
将这个节点加入哈希表
将这个节点添加到链表的头部
更新链表的总数
如果链表的长度超过了容量,那么删除尾部元素,这个删除需要返回被删除的节点,然后在哈希表中删除这个节点,修改链表的总数

定义几个函数
注意有俩哑节点 head和tail,head->next是第一个节点,tail->prev是倒数第一个节点

addToHead 将节点加到头部
对node俩指针初始化,node前指针指向head,后指针指向第一个节点
修改原第一个节点前指针,修改哑节点的后指针
removeNode 删除一个节点
修改当前节点的前一个节点的后指针
修改当前节点的后一个节点的前指针
moveToHead 移动到开头
调用删除节点函数 removeNode
调用添加节点函数 addToHead
removeTail 删除尾节点
找到尾节点
调用删除节点函数
将被删除节点返回

代码

class LRUCache {
private:
    unordered_map cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在,先通过哈希表定位,再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在,创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量,删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963958.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号