剑指offer
题库链接: https://leetcode.cn/problem-list/e8X3pBZi/
整数除法
剑指 Offer II 001. 整数除法
给定整数a、b，求得商的结果
条件:
1、不能使用除法、取余数等运算
2、只能存储32位有符号整数(范围是[-2^31,2^31-1])，如果溢出了就返回2^31-1
解法
- 处理边界条件，当a是最小值，判断b是1或者-1；当b是最小值，a是最小值则为1，其他都为0
- 使用二分法+快速乘来判断是否满足
#include <iostream>
#include <limits>
using namespace std;
// 快速乘
// x 和 y 是负数，z 是正数
// 判断 z * y >= x 是否成立
bool quickAdd(int y, int z, int x) {
int result = 0, add = y;
while (z > 0) { // 不能使用除法
if (z & 1) {
// 需要保证 result + add >= x
if (result < x - add) {
return false;
}
result += add;
}
if (z != 1) {
// 需要保证 add + add >= x
if (add < x - add) {
return false;
}
add += add;
}
z >>= 1;
}
return true;
}
int divide(int a, int b) {
if (a == numeric_limits<int>::min()) { // 考虑被除数为最小值的情况
if (b == 1) {
return numeric_limits<int>::min();
}
if (b == -1) {
return numeric_limits<int>::max();
}
}
if (b == numeric_limits<int>::min()) { // 考虑除数为最小值的情况
if (a == numeric_limits<int>::min()) {
return 1;
}
return 0;
}
if (a == 0) { // 考虑被除数为 0 的情况
return 0;
}
// 一般情况，使用二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
bool rev = false;
if (a > 0) {
a = -a;
rev = !rev;
}
if (b > 0) {
b = -b;
rev = !rev;
}
int ans = 0;
int left = 1, right = numeric_limits<int>::max();
while (left <= right) {
int mid = left + ((right - left) >> 1); // 注意溢出，并且不能使用除法
if (quickAdd(b, mid, a)) {
ans = mid;
if (mid == numeric_limits<int>::max()) { // 注意溢出
break;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return rev ? -ans : ans;
}
int main() {
std::cout << divide(4, 3) << std::endl;
return 0;
}
package main
import "math"
// 快速乘
// x 和 y 是负数，z 是正数
// 判断 z * y >= x 是否成立
func QuickAdd(y, z, x int) bool {
for result, add := 0, y; z > 0; z >>= 1 { // 不能使用除法
if z&1 > 0 {
// 需要保证 result + add >= x
if result < x-add {
return false
}
result += add
}
if z != 1 {
// 需要保证 add + add >= x
if add < x-add {
return false
}
add += add
}
}
return true
}
func divide(a, b int) int {
if a == math.MinInt32 { // 考虑被除数为最小值的情况
if b == 1 {
return math.MinInt32
}
if b == -1 {
return math.MaxInt32
}
}
if b == math.MinInt32 { // 考虑除数为最小值的情况
if a == math.MinInt32 {
return 1
}
return 0
}
if a == 0 { // 考虑被除数为 0 的情况
return 0
}
// 一般情况，使用二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
rev := false
if a > 0 {
a = -a
rev = !rev
}
if b > 0 {
b = -b
rev = !rev
}
ans := 0
left, right := 1, math.MaxInt32
for left <= right {
mid := left + (right-left)>>1 // 注意溢出，并且不能使用除法
if QuickAdd(b, mid, a) {
ans = mid
if mid == math.MaxInt32 { // 注意溢出
break
}
left = mid + 1
} else {
right = mid - 1
}
}
if rev {
return -ans
}
return ans
}
2、
剑指 Offer II 002. 二进制加法
给定两个01字符串，求得加法字符串
解法
- 相对应下标(len-i-1)不断相加，计算商继续作为carry、模作为当前下标的值。
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
// 二进制字符串相加
string addBinary(string a, string b) {
string ans = "";
int carry = 0;
int lenA = a.size(), lenB = b.size();
int n = max(lenA, lenB);
// 从后往前逐位相加
for (int i = 0; i < n; i++) {
if (i < lenA) {
carry += a[lenA - i - 1] - '0';
}
if (i < lenB) {
carry += b[lenB - i - 1] - '0';
}
ans = char(carry % 2 + '0') + ans;
carry /= 2;
}
// 如果最后有进位，补上一个1
if (carry > 0) {
ans = '1' + ans;
}
return ans;
}
int main() {
std::cout << addBinary("11", "1") << std::endl;
std::cout << addBinary("11", "1001") << std::endl;
return 0;
}
package main
import "strconv"
func AddBinary(a string, b string) string {
ans := ""
carry := 0
lenA, lenB := len(a), len(b)
n := max(lenA, lenB)
for i := 0; i < n; i++ {
if i < lenA {
carry += int(a[lenA-i-1] - '0')
}
if i < lenB {
carry += int(b[lenB-i-1] - '0')
}
ans = strconv.Itoa(carry%2) + ans
carry /= 2
}
if carry > 0 {
ans = "1" + ans
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
3、
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
给定一个数字n，从[0,n]中计算出二进制表示中1的个数
解法
- 计算一个数的二进制表示中有多少个1，
x>0的循环条件中，能有多少次x&=x-1满足条件
#include <iostream>
#include <vector>
using namespace std;
// 计算一个整数的二进制表示中1的个数
int onesCount(int x) {
int ones = 0;
while (x > 0) {
x &= (x - 1); // 消除最低位的1
ones++;
}
return ones;
}
// 返回从0到n的每个整数的二进制表示中1的个数
vector<int> countBits(int n) {
vector<int> bits(n + 1);
for (int i = 0; i <= n; ++i) {
bits[i] = onesCount(i);
}
return bits;
}
int main() {
vector<int> bits = countBits(5);
for (int i = 0; i < bits.size(); ++i) {
cout << bits[i] << " ";
}
cout << endl;
return 0;
}
package main
func onesCount(x int) (ones int) {
for ; x > 0; x &= x - 1 {
ones++
}
return
}
func CountBits(n int) []int {
bits := make([]int, n+1)
for i := range bits {
bits[i] = onesCount(i)
}
return bits
}
4、
剑指 Offer II 004. 只出现一次的数字
给定一个整数数组，其中一个元素出现了一次，其他元素出现了三次，找到那个只出现了一次的元素
要求: O(n)时间复杂度, O(1)空间复杂度
解法
- 将数组中的数字看成二进制格式，对于出现了三次的数字，他们对应的比特位数字和为0或者3，对于出现一次的数字，对应的比特位数字和为1或者4，将每一位的和取余所得到的余数就是结果对应的元素对应的位置。
#include <iostream>
#include <vector>
using namespace std;
int singleNumber(const vector<int>& nums) {
int ans = 0; // 32位整数，保存结果
for (int i = 0; i < 32; ++i) {
int total = 0; // 记录第i位的1的个数
for (int num : nums) {
total += (num >> i) & 1; // 取出num的第i位并累加
}
if (total % 3 > 0) { // 如果该位上的1的个数不是3的倍数
ans |= (1 << i); // 将该位设置为1
}
}
return ans;
}
int main() {
vector<int> nums = { 1,1,1,2,2,2,3,3,3,4 };
int ans = singleNumber(nums);
cout << ans << endl;
return 0;
}
package main
func SingleNumber(nums []int) int {
ans := int32(0)
for i := 0; i < 32; i++ {
total := int32(0)
for _, num := range nums {
total += int32(num) >> i & 1
}
if total%3 > 0 {
ans |= 1 << i
}
}
return int(ans)
}
5、
剑指 Offer II 005. 单词长度的最大乘积
一个字符串数组，寻找满足 不包含相同字符 的两个字符串的长度乘积，找到满足条件的最大长度
解法
- 将字符串转为int类型mask来表示哪些字母是出现了的
- 使用位运算来判断是否存在相同的字符
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int maxProduct(const vector<string> &words) {
int ans = 0;
int n = words.size();
vector<int> masks(n, 0); // 用于存储每个单词的掩码
// 计算每个单词的字母掩码
for (int i = 0; i < n; ++i) {
for (char ch : words[i]) {
masks[i] |= (1 << (ch - 'a')); // 将字母对应的位标记为1
}
}
// 两两比较掩码，找出没有公共字母的单词组合，并计算其乘积
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if ((masks[i] & masks[j]) == 0) { // 判断是否没有公共字母
int product = words[i].size() * words[j].size();
if (product > ans) {
ans = product;
}
}
}
}
return ans;
}
int main() {
vector<string> words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
int ans = maxProduct(words);
cout << ans << endl;
return 0;
}
package main
func MaxProduct(words []string) (ans int) {
masks := make([]int, len(words))
for i, word := range words {
for _, ch := range word {
masks[i] |= 1 << (ch - 'a')
}
}
for i, x := range masks {
for j, y := range masks[:i] {
if x&y == 0 && len(words[i])*len(words[j]) > ans {
ans = len(words[i]) * len(words[j])
}
}
}
return
}
6、
剑指 Offer II 006. 排序数组中两个数字之和
一个升序数组，找到其中的两个元素和为目标值，返回其目标下标。同一个数字不能使用两次，并且题目要求一定会存在满足条件的答案。
#include <vector>
std::vector<int> TwoSum(const std::vector<int> &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};
}
package main
func TwoSum(numbers []int, target int) []int {
low, high := 0, len(numbers)-1
for low < high {
sum := numbers[low] + numbers[high]
if sum == target {
return []int{low, high}
} else if sum < target {
low++
} else {
high--
}
}
return []int{-1, -1}
}
7、
剑指 Offer II 007. 数组中和为 0 的三个数
给定一个整数数组，返回其中和为0的三元组，并且需要答案不能重复
解法
- 先进行排序，优化搜索条件
- 记得跳过相同的值，即相同的一段，只计算第一个进行剪枝。
#include <algorithm>
#include <vector>
std::vector<std::vector<int>> ThreeSum(std::vector<int> &nums) {
std::vector<std::vector<int>> ans;
std::sort(nums.begin(), nums.end());
int n = nums.size();
for (int first = 0; first < n; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int third = n - 1;
int target = -nums[first];
for (int second = first + 1; second < n; ++second) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while (second < third && nums[second] + nums[third] > target) {
--third;
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
package main
import "sort"
func ThreeSum(nums []int) [][]int {
n := len(nums)
sort.Ints(nums)
ans := make([][]int, 0)
// 枚举 a
for first := 0; first < n; first++ {
// 需要和上一次枚举的数不相同
if first > 0 && nums[first] == nums[first-1] {
continue
}
// c 对应的指针初始指向数组的最右端
third := n - 1
target := -1 * nums[first]
// 枚举 b
for second := first + 1; second < n; second++ {
// 需要和上一次枚举的数不相同
if second > first+1 && nums[second] == nums[second-1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
for second < third && nums[second]+nums[third] > target {
third--
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third {
break
}
if nums[second]+nums[third] == target {
ans = append(ans, []int{nums[first], nums[second], nums[third]})
}
}
}
return ans
}
8、
剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个整数数组，寻找满足数组和大于target的一个最短连续子数组
解法
- 滑动窗口: 计算满足和大于目标值的最短子数组长度
#include <algorithm>
#include <climits>
#include <vector>
int minSubArrayLen(int s, const std::vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0, sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = std::min(ans, end - start + 1);
sum -= nums[start];
++start;
}
++end;
}
return (ans == INT_MAX) ? 0 : ans;
}
package main
import "math"
func MinSubArrayLen(s int, nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
ans := math.MaxInt32
start, end := 0, 0
sum := 0
for end < n {
sum += nums[end]
for sum >= s {
ans = min(ans, end-start+1)
sum -= nums[start]
start++
}
end++
}
if ans == math.MaxInt32 {
return 0
}
return ans
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
9、
剑指 Offer II 009. 乘积小于 K 的子数组
给定一个数组，寻找其中满足数组乘积小于k的子数组的个数
#include <vector>
int numSubarrayProductLessThanK(const std::vector<int> &nums, int k) {
if (k <= 1)
return 0;
int prod = 1, ans = 0, i = 0;
for (int j = 0; j < nums.size(); ++j) {
prod *= nums[j];
while (prod >= k) {
prod /= nums[i++];
}
ans += j - i + 1;
}
return ans;
}
package main
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
prod, i := 1, 0
for j, num := range nums {
prod *= num
for ; i <= j && prod >= k; i++ {
prod /= nums[i]
}
ans += j - i + 1
}
return
}
10、
剑指 Offer II 010. 和为 k 的子数组
给定一个数组，寻找其中满足数组和为k的子数组的个数
解法
- 数组和在计算过程中需要记录下来，并且同时计算该数组和对应的个数
#include <unordered_map>
#include <vector>
int subarraySum(const std::vector<int> &nums, int k) {
int count = 0, pre = 0;
std::unordered_map<int, int> m;
m[0] = 1;
for (int i = 0; i < nums.size(); ++i) {
pre += nums[i];
if (m.find(pre - k) != m.end()) {
count += m[pre - k];
}
m[pre]++;
}
return count;
}
package main
func subarraySum(nums []int, k int) int {
count, pre := 0, 0
m := map[int]int{}
m[0] = 1
for i := 0; i < len(nums); i++ {
pre += nums[i]
if _, ok := m[pre-k]; ok {
count += m[pre-k]
}
m[pre] += 1
}
return count
}
11、
剑指 Offer II 011. 0 和 1 个数相同的子数组
给定一个只包含0和1的数组，找到其中含有相同0和1数量的最大长度的子数组
解法
- 使用map记录某个前缀和最左边的下标是多少
#include <algorithm>
#include <unordered_map>
#include <vector>
int FindMaxLength(const std::vector<int> &nums) {
std::unordered_map<int, int> mp = {{0, -1}};
int maxLength = 0, counter = 0;
for (int i = 0; i < nums.size(); ++i) {
counter += (nums[i] == 1) ? 1 : -1;
if (mp.find(counter) != mp.end()) {
maxLength = std::max(maxLength, i - mp[counter]);
} else {
mp[counter] = i;
}
}
return maxLength;
}
package main
func FindMaxLength(nums []int) (maxLength int) {
mp := map[int]int{0: -1}
counter := 0
for i, num := range nums {
if num == 1 {
counter++
} else {
counter--
}
if prevIndex, has := mp[counter]; has {
maxLength = max(maxLength, i-prevIndex)
} else {
mp[counter] = i
}
}
return
}
12、
剑指 Offer II 012. 左右两边子数组的和相等
找到数组的最左边的中心下标，中心下标是指以该下标为分界，左右数组元素和相同的下标
解法
- 判断
2 * 前缀和 + 当前值是否等于数组总和
#include <vector>
int pivotIndex(const std::vector<int> &nums) {
int total = 0;
for (int v : nums) {
total += v;
}
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
if (2 * sum + nums[i] == total) {
return i;
}
sum += nums[i];
}
return -1;
}
package main
func pivotIndex(nums []int) int {
total := 0
for _, v := range nums {
total += v
}
sum := 0
for i, v := range nums {
if 2*sum+v == total {
return i
}
sum += v
}
return -1
}
13、
剑指 Offer II 013. 二维子矩阵的和
给定一个二维矩阵，提供多次查询，计算子矩阵的和
解法
- 预处理(0,0)到(i,j)的子数组的和
#include <vector>
class NumMatrix {
public:
NumMatrix(const std::vector<std::vector<int>> &matrix) {
int m = matrix.size();
if (m == 0)
return;
int n = matrix[0].size();
sums.resize(m + 1, std::vector<int>(n + 1, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
sums[i + 1][j + 1] =
sums[i + 1][j] + sums[i][j + 1] - 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];
}
private:
std::vector<std::vector<int>> sums;
};
package main
type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m := len(matrix)
if m == 0 {
return NumMatrix{}
}
n := len(matrix[0])
sums := make([][]int, m+1)
sums[0] = make([]int, n+1)
for i, row := range matrix {
sums[i+1] = make([]int, n+1)
for j, v := range row {
sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + v
}
}
return NumMatrix{sums}
}
func (nm *NumMatrix) SumRegion(row1, col1, row2, col2 int) int {
return nm.sums[row2+1][col2+1] - nm.sums[row1][col2+1] - nm.sums[row2+1][col1] + nm.sums[row1][col1]
}
14、
剑指 Offer II 014. 字符串中的变位词
给定两个字符串，判断字符串的排列之一是否是另一个字符串的子串
解法
- 使用26长度的数组来保存字符情况
#include <string>
#include <vector>
bool checkInclusion(const std::string &s1, const std::string &s2) {
int n = s1.size(), m = s2.size();
if (n > m)
return false;
std::vector<int> cnt(26, 0);
for (char ch : s1) {
cnt[ch - 'a']--;
}
int left = 0;
for (int right = 0; right < m; ++right) {
int x = s2[right] - 'a';
cnt[x]++;
while (cnt[x] > 0) {
cnt[s2[left] - 'a']--;
left++;
}
if (right - left + 1 == n) {
return true;
}
}
return false;
}
package main
func checkInclusion(s1, s2 string) bool {
n, m := len(s1), len(s2)
if n > m {
return false
}
cnt := [26]int{}
for _, ch := range s1 {
cnt[ch-'a']--
}
left := 0
for right, ch := range s2 {
x := ch - 'a'
cnt[x]++
for cnt[x] > 0 {
cnt[s2[left]-'a']--
left++
}
if right-left+1 == n {
return true
}
}
return false
}
15、
剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串，返回一个子串的所有变位形式判断在另一个字符串中是子串的话，就返回其起始下标
解法
- 26位长度数组
- 滑动窗口
#include <string>
#include <vector>
std::vector<int> findAnagrams(const std::string &s, const std::string &p) {
std::vector<int> ans;
int sLen = s.size(), pLen = p.size();
if (sLen < pLen)
return ans;
std::vector<int> sCount(26, 0), pCount(26, 0);
for (int i = 0; i < pLen; ++i) {
sCount[s[i] - 'a']++;
pCount[p[i] - 'a']++;
}
if (sCount == pCount) {
ans.push_back(0);
}
for (int i = 0; i < sLen - pLen; ++i) {
sCount[s[i] - 'a']--;
sCount[s[i + pLen] - 'a']++;
if (sCount == pCount) {
ans.push_back(i + 1);
}
}
return ans;
}
package main
func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen {
return
}
var sCount, pCount [26]int
for i, ch := range p {
sCount[s[i]-'a']++
pCount[ch-'a']++
}
if sCount == pCount {
ans = append(ans, 0)
}
for i, ch := range s[:sLen-pLen] {
sCount[ch-'a']--
sCount[s[i+pLen]-'a']++
if sCount == pCount {
ans = append(ans, i+1)
}
}
return
}
16、
剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串，返回不包含重复字符的最长子字符串长度
解法
- 滑动窗口，记录在窗口中字符的个数
#include <algorithm>
#include <string>
#include <unordered_map>
int lengthOfLongestSubstring(const std::string &s) {
std::unordered_map<char, int> m;
int n = s.length();
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
m.erase(s[i - 1]);
}
while (rk + 1 < n && m[s[rk + 1]] == 0) {
m[s[++rk]]++;
}
ans = std::max(ans, rk - i + 1);
}
return ans;
}
package main
func lengthOfLongestSubstring(s string) int {
// 哈希集合，记录每个字符是否出现过
m := map[byte]int{}
n := len(s)
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans := -1, 0
for i := 0; i < n; i++ {
if i != 0 {
// 左指针向右移动一格，移除一个字符
delete(m, s[i-1])
}
for rk+1 < n && m[s[rk+1]] == 0 {
// 不断地移动右指针
m[s[rk+1]]++
rk++
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk-i+1)
}
return ans
}
17、
剑指 Offer II 017. 含有所有字符的最短字符串
给定两个字符串s和t，找到s中的一个最短字符串，包含t的所有字符，如果不存在这样的子字符串，则返回空字符串
#include <climits>
#include <string>
#include <unordered_map>
std::string minWindow(const std::string &s, const std::string &t) {
std::unordered_map<char, int> ori, cnt;
for (char c : t) {
ori[c]++;
}
int sLen = s.length();
int minLen = INT_MAX;
int ansL = -1, ansR = -1;
auto check = [&]() -> bool {
for (const auto &[k, v] : ori) {
if (cnt[k] < v) {
return false;
}
}
return true;
};
for (int l = 0, r = 0; r < sLen; ++r) {
if (ori.find(s[r]) != ori.end()) {
cnt[s[r]]++;
}
while (check() && l <= r) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
ansL = l;
ansR = l + minLen;
}
if (ori.find(s[l]) != ori.end()) {
cnt[s[l]]--;
}
++l;
}
}
if (ansL == -1) {
return "";
}
return s.substr(ansL, ansR - ansL);
}
package main
import "math"
func minWindow(s string, t string) string {
ori, cnt := map[byte]int{}, map[byte]int{}
for i := 0; i < len(t); i++ {
ori[t[i]]++
}
sLen := len(s)
len := math.MaxInt32
ansL, ansR := -1, -1
check := func() bool {
for k, v := range ori {
if cnt[k] < v {
return false
}
}
return true
}
for l, r := 0, 0; r < sLen; r++ {
if r < sLen && ori[s[r]] > 0 {
cnt[s[r]]++
}
for check() && l <= r {
if r-l+1 < len {
len = r - l + 1
ansL, ansR = l, l+len
}
if _, ok := ori[s[l]]; ok {
cnt[s[l]] -= 1
}
l++
}
}
if ansL == -1 {
return ""
}
return s[ansL:ansR]
}
18、
剑指 Offer II 018. 有效的回文
给定一个字符串，验证是否是回文字符串, 只考虑字母和数字字符，可以忽略字母的大小写。
#include <algorithm>
#include <cctype>
#include <string>
bool isalnum(char ch) {
return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') ||
(ch >= '0' && ch <= '9');
}
bool isPalindrome(const std::string &s) {
std::string sgood;
for (char ch : s) {
if (isalnum(ch)) {
sgood += std::tolower(ch);
}
}
int n = sgood.length();
for (int i = 0; i < n / 2; ++i) {
if (sgood[i] != sgood[n - 1 - i]) {
return false;
}
}
return true;
}
package main
import "strings"
func isPalindrome(s string) bool {
var sgood string
for i := 0; i < len(s); i++ {
if isalnum(s[i]) {
sgood += string(s[i])
}
}
n := len(sgood)
sgood = strings.ToLower(sgood)
for i := 0; i < n/2; i++ {
if sgood[i] != sgood[n-1-i] {
return false
}
}
return true
}
func isalnum(ch byte) bool {
return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}
19、
剑指 Offer II 019. 最多删除一个字符得到回文
给定一个字符串，删除其中一个字符判断是否是回文
#include <string>
bool validPalindrome(const std::string &s) {
int low = 0, high = s.length() - 1;
while (low < high) {
if (s[low] == s[high]) {
++low;
--high;
} else {
bool flag1 = true, flag2 = true;
for (int i = low, j = high - 1; i < j; ++i, --j) {
if (s[i] != s[j]) {
flag1 = false;
break;
}
}
for (int i = low + 1, j = high; i < j; ++i, --j) {
if (s[i] != s[j]) {
flag2 = false;
break;
}
}
return flag1 || flag2;
}
}
return true;
}
package main
func validPalindrome(s string) bool {
low, high := 0, len(s)-1
for low < high {
if s[low] == s[high] {
low++
high--
} else {
flag1, flag2 := true, true
for i, j := low, high-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
flag1 = false
break
}
}
for i, j := low+1, high; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
flag2 = false
break
}
}
return flag1 || flag2
}
}
return true
}
20、
剑指 Offer II 020. 回文子字符串的个数
计算一个字符串中有多少个回文子字符串
#include <string>
int countSubstrings(const std::string &s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2;
int r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
++ans;
}
}
return ans;
}
package main
func countSubstrings(s string) int {
n := len(s)
ans := 0
for i := 0; i < 2*n-1; i++ {
l, r := i/2, i/2+i%2
for l >= 0 && r < n && s[l] == s[r] {
l--
r++
ans++
}
}
return ans
}
21、
剑指 Offer II 021. 删除链表的倒数第 n 个结点
给定一个链表，删除链表的倒数第n个节点，并且返回头节点
解法
- 快慢指针
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *dummy = new ListNode(0);
dummy->Next = head;
ListNode *first = head;
ListNode *second = dummy;
for (int i = 0; i < n; ++i) {
first = first->Next;
}
while (first != nullptr) {
first = first->Next;
second = second->Next;
}
second->Next = second->Next->Next;
ListNode *newHead = dummy->Next;
delete dummy; // Free the allocated memory for dummy node
return newHead;
}
package main
type ListNode struct {
Val int
Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{0, head}
first, second := head, dummy
for i := 0; i < n; i++ {
first = first.Next
}
for ; first != nil; first = first.Next {
second = second.Next
}
second.Next = second.Next.Next
return dummy.Next
}
22、
剑指 Offer II 022. 链表中环的入口节点
给定一个数组形式的链表，数组中每个元素对应着下一个节点的下标，如果该链表没有环，就返回-1，如果有环，则返回环入口的下标
解法
- 快慢指针，当相遇了之后从当前以及初始位置以相同速度前进，当再次相遇就是环的入口
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
ListNode *detectCycle(ListNode *head) {
if (!head)
return nullptr;
ListNode *slow = head;
ListNode *fast = head;
while (fast != nullptr && fast->Next != nullptr) {
slow = slow->Next;
fast = fast->Next->Next;
if (slow == fast) {
ListNode *p = head;
while (p != slow) {
p = p->Next;
slow = slow->Next;
}
return p;
}
}
return nullptr;
}
package main
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil {
slow = slow.Next
if fast.Next == nil {
return nil
}
fast = fast.Next.Next
if fast == slow {
p := head
for p != slow {
p = p.Next
slow = slow.Next
}
return p
}
}
return nil
}
23、
剑指 Offer II 023. 两个链表的第一个重合节点
给定两个链表，题目保证该链式结构没有环，找到该两个链表的相交节点，如果不存在相交节点，就返回空
解法
- 链表走完了之后到另外一个上，这样到达相交节点的节点数相同，是会相遇的
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pa = headA;
ListNode *pb = headB;
while (pa != pb) {
pa = (pa == nullptr) ? headB : pa->Next;
pb = (pb == nullptr) ? headA : pb->Next;
}
return pa;
}
package main
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
pa, pb := headA, headB
for pa != pb {
if pa == nil {
pa = headB
} else {
pa = pa.Next
}
if pb == nil {
pb = headA
} else {
pb = pb.Next
}
}
return pa
}
24、
剑指 Offer II 024. 反转链表
给定一个链式结构，反转后返回其头节点
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
ListNode *reverseList(ListNode *head) {
if (head == nullptr || head->Next == nullptr) {
return head;
}
ListNode *newHead = reverseList(head->Next);
head->Next->Next = head;
head->Next = nullptr;
return newHead;
}
package main
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
25、
剑指 Offer II 025. 链表中的两数相加
使用两个链表表示非负整数，尾节点为个位数，返回两个链表的相加结果，并以链表形式返回
解法
- 将链表转为数组，然后计算完后进行重新构造成链表
#include <vector>
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
std::vector<int> s1, s2;
while (l1 != nullptr) {
s1.push_back(l1->Val);
l1 = l1->Next;
}
while (l2 != nullptr) {
s2.push_back(l2->Val);
l2 = l2->Next;
}
int carry = 0;
ListNode *head = nullptr;
while (!s1.empty() || !s2.empty() || carry != 0) {
int sum = 0;
if (!s1.empty()) {
sum += s1.back();
s1.pop_back();
}
if (!s2.empty()) {
sum += s2.back();
s2.pop_back();
}
sum += carry;
ListNode *node = new ListNode(sum % 10);
node->Next = head;
head = node;
carry = sum / 10;
}
return head;
}
package main
func addTwoNumbers(l1 *ListNode, l2 *ListNode) (head *ListNode) {
var s1, s2 []int
for l1 != nil {
s1 = append(s1, l1.Val)
l1 = l1.Next
}
for l2 != nil {
s2 = append(s2, l2.Val)
l2 = l2.Next
}
carry := 0
for len(s1) > 0 || len(s2) > 0 || carry > 0 {
sum := 0
if len(s1) > 0 {
sum += s1[len(s1)-1]
s1 = s1[:len(s1)-1]
}
if len(s2) > 0 {
sum += s2[len(s2)-1]
s2 = s2[:len(s2)-1]
}
sum += carry
node := &ListNode{Val: sum % 10}
node.Next = head
head = node
carry = sum / 10
}
return
}
26、
剑指 Offer II 026. 重排链表
给定一个链表结构，原始为'1 2 3 4 5 6 ... n-1 n' 修改为'1 n 2 n-1 3 n-2 ...'
#include <vector>
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
void reorderList(ListNode *head) {
if (head == nullptr) {
return;
}
std::vector<ListNode *> nodes;
for (ListNode *node = head; node != nullptr; node = node->Next) {
nodes.push_back(node);
}
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes[i]->Next = nodes[j];
++i;
if (i == j) {
break;
}
nodes[j]->Next = nodes[i];
--j;
}
nodes[i]->Next = nullptr;
}
package main
func reorderList(head *ListNode) {
if head == nil {
return
}
nodes := []*ListNode{}
for node := head; node != nil; node = node.Next {
nodes = append(nodes, node)
}
i, j := 0, len(nodes)-1
for i < j {
nodes[i].Next = nodes[j]
i++
if i == j {
break
}
nodes[j].Next = nodes[i]
j--
}
nodes[i].Next = nil
}
27、
剑指 Offer II 027. 回文链表
给定一个链表结构，判断该链表是否是回文
#include <vector>
struct ListNode {
int Val;
ListNode *Next;
ListNode(int x) : Val(x), Next(nullptr) {}
};
bool isLinkListPalindrome(ListNode *head) {
std::vector<int> vals;
for (ListNode *node = head; node != nullptr; node = node->Next) {
vals.push_back(node->Val);
}
int n = vals.size();
for (int i = 0; i < n / 2; ++i) {
if (vals[i] != vals[n - 1 - i]) {
return false;
}
}
return true;
}
package main
func isLinkListPalindrome(head *ListNode) bool {
vals := []int{}
for ; head != nil; head = head.Next {
vals = append(vals, head.Val)
}
n := len(vals)
for i, v := range vals[:n/2] {
if v != vals[n-1-i] {
return false
}
}
return true
}
28、
剑指 Offer II 028. 展平多级双向链表
将多级双向链表展平
这里多级双向链表就是包含前后指针，还包含子链表的指针，(其实就相当于链表)
struct Node {
int Val;
Node *Prev;
Node *Next;
Node *Child;
Node(int x) : Val(x), Prev(nullptr), Next(nullptr), Child(nullptr) {}
};
Node *dfs(Node *node) {
Node *cur = node;
Node *last = nullptr;
while (cur != nullptr) {
Node *next = cur->Next;
if (cur->Child != nullptr) {
Node *childLast = dfs(cur->Child);
cur->Next = cur->Child;
cur->Child->Prev = cur;
if (next != nullptr) {
childLast->Next = next;
next->Prev = childLast;
}
cur->Child = nullptr;
last = childLast;
} else {
last = cur;
}
cur = next;
}
return last;
}
Node *flatten(Node *root) {
dfs(root);
return root;
}
package main
type LinkNode struct {
Val int
Next *LinkNode
Prev *LinkNode
Child *LinkNode
}
func dfs(node *LinkNode) (last *LinkNode) {
cur := node
for cur != nil {
next := cur.Next
// 如果有子节点，那么首先处理子节点
if cur.Child != nil {
childLast := dfs(cur.Child)
next = cur.Next
// 将 node 与 child 相连
cur.Next = cur.Child
cur.Child.Prev = cur
// 如果 next 不为空，就将 last 与 next 相连
if next != nil {
childLast.Next = next
next.Prev = childLast
}
// 将 child 置为空
cur.Child = nil
last = childLast
} else {
last = cur
}
cur = next
}
return
}
func flatten(root *LinkNode) *LinkNode {
dfs(root)
return root
}
29、
剑指 Offer II 029. 排序的循环链表
给定一个循环链表，它的值是单调非递减的，提供一个元素插入的方法，使得元素插入之后值依然是单调非递减的
解法
- 第一种情况
cur.val <= val <= next.val, 直接插入到这里 - 第二种情况
cur.val > next.val, 说明是链表遍历完了，break，直接加入到cur的后面
struct Node {
int Val;
Node *Next;
Node(int x) : Val(x), Next(nullptr) {}
};
Node *insert(Node *head, int insertVal) {
Node *node = new Node(insertVal);
if (head == nullptr) {
node->Next = node;
return node;
}
if (head->Next == head) {
head->Next = node;
node->Next = head;
return head;
}
Node *curr = head;
Node *next = head->Next;
while (next != head) {
if (insertVal >= curr->Val && insertVal <= next->Val) {
break;
}
if (curr->Val > next->Val) {
if (insertVal > curr->Val || insertVal < next->Val) {
break;
}
}
curr = curr->Next;
next = next->Next;
}
curr->Next = node;
node->Next = next;
return head;
}
package main
func insert(head *ListNode, insertVal int) *ListNode {
node := &ListNode{Val: insertVal}
if head == nil {
node.Next = node
return node
}
if head.Next == head {
head.Next = node
node.Next = head
return head
}
curr, next := head, head.Next
for next != head {
if insertVal >= curr.Val && insertVal <= next.Val {
break
}
if curr.Val > next.Val {
if insertVal > curr.Val || insertVal < next.Val {
break
}
}
curr = curr.Next
next = next.Next
}
curr.Next = node
node.Next = next
return head
}
30、
剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
创造一个数据结构，它的插入、删除、随机访问都是O(1)时间复杂度
解法
- 由于需要随机访问，所以将数据存储到数组中，通过对下标进行随机来进行访问
- 插入和删除也需要O(1), 使用map来存储值与下标
- 当删除的时候，将末尾的一个移动到要删除的位置并且更新下对应下标，然后数组只需要减一个长度即可
#include <cstdlib>
#include <unordered_map>
#include <vector>
class RandomizedSet {
public:
RandomizedSet() {}
bool insert(int val) {
if (indices.find(val) != indices.end()) {
return false;
}
indices[val] = nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
auto it = indices.find(val);
if (it == indices.end()) {
return false;
}
int last = nums.back();
nums[it->second] = last;
indices[last] = it->second;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand() % nums.size();
return nums[randomIndex];
}
private:
std::vector<int> nums;
std::unordered_map<int, int> indices;
};
package main
import "math/rand"
type RandomizedSet struct {
nums []int
indices map[int]int
}
func NewRandomizedSet() RandomizedSet {
return RandomizedSet{
[]int{}, map[int]int{},
}
}
func (rs *RandomizedSet) Insert(val int) bool {
if _, ok := rs.indices[val]; ok {
return false
}
rs.indices[val] = len(rs.nums)
rs.nums = append(rs.nums, val)
return true
}
func (rs *RandomizedSet) Remove(val int) bool {
id, ok := rs.indices[val]
if !ok {
return false
}
last := len(rs.nums) - 1
rs.nums[id] = rs.nums[last]
rs.indices[rs.nums[id]] = id
rs.nums = rs.nums[:last]
delete(rs.indices, val)
return true
}
func (rs *RandomizedSet) GetRandom() int {
return rs.nums[rand.Intn(len(rs.nums))]
}