31、
剑指 Offer II 031. 最近最少使用缓存
设计一个最近最少使用的缓存数据结构，提供get和put方法
#include <list>
#include <unordered_map>
class LRUCache {
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) {
return -1;
}
// Move the accessed element to the front of the list
list.splice(list.begin(), list, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
// Update the value and move the element to the front of the list
it->second->second = value;
list.splice(list.begin(), list, it->second);
return;
}
if (list.size() == capacity) {
// Remove the least recently used element
int lruKey = list.back().first;
list.pop_back();
cache.erase(lruKey);
}
// Insert the new element at the front of the list
list.emplace_front(key, value);
cache[key] = list.begin();
}
private:
int capacity;
std::list<std::pair<int, int>> list;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache;
};
package main
import "container/list"
type LRUCache struct {
capacity int
cache map[int]*list.Element
list *list.List
}
type entry struct {
key int
value int
}
func NewLRUCache(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
list: list.New(),
}
}
func (this *LRUCache) Get(key int) int {
if elem, ok := this.cache[key]; ok {
this.list.MoveToFront(elem)
return elem.Value.(*entry).value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if elem, ok := this.cache[key]; ok {
elem.Value.(*entry).value = value
this.list.MoveToFront(elem)
return
}
if this.list.Len() == this.capacity {
lastElem := this.list.Back()
delete(this.cache, lastElem.Value.(*entry).key)
this.list.Remove(lastElem)
}
newElem := this.list.PushFront(&entry{key: key, value: value})
this.cache[key] = newElem
}
32、
剑指 Offer II 032. 有效的变位词
判断字符串s和t是否是一组有效的变位词，即元素相同位置不同
#include <string>
#include <vector>
bool isAnagram(const std::string &s, const std::string &t) {
if (s == t) {
return false;
}
std::vector<int> c1(26, 0), c2(26, 0);
for (char ch : s) {
c1[ch - 'a']++;
}
for (char ch : t) {
c2[ch - 'a']++;
}
return c1 == c2;
}
package main
func isAnagram(s, t string) bool {
if s == t {
return false
}
var c1, c2 [26]int
for _, ch := range s {
c1[ch-'a']++
}
for _, ch := range t {
c2[ch-'a']++
}
return c1 == c2
}
33、
剑指 Offer II 033. 变位词组
给定一个字符串数组，将所有是同一类变位词的组合在一起
#include <array>
#include <string>
#include <unordered_map>
#include <vector>
std::vector<std::vector<std::string>>
groupAnagrams(std::vector<std::string> &strs) {
std::unordered_map<std::array<int, 26>, std::vector<std::string>> mp;
for (const auto &str : strs) {
std::array<int, 26> cnt = {0};
for (char ch : str) {
cnt[ch - 'a']++;
}
mp[cnt].push_back(str);
}
std::vector<std::vector<std::string>> ans;
for (auto &[key, group] : mp) {
ans.push_back(std::move(group));
}
return ans;
}
package main
func groupAnagrams(strs []string) [][]string {
mp := map[[26]int][]string{}
for _, str := range strs {
cnt := [26]int{}
for _, b := range str {
cnt[b-'a']++
}
mp[cnt] = append(mp[cnt], str)
}
ans := make([][]string, 0, len(mp))
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
34、
剑指 Offer II 034. 外星语言是否排序
给定一种新的order字符顺序，判断一个字符串数组words中的字符串是否是按照字典序进行排列的
#include <string>
#include <unordered_map>
#include <vector>
bool isAlienSorted(const std::vector<std::string> &words,
const std::string &order) {
std::vector<int> index(26, 0);
for (int i = 0; i < order.size(); ++i) {
index[order[i] - 'a'] = i;
}
for (int i = 1; i < words.size(); ++i) {
const std::string &prev = words[i - 1];
const std::string &curr = words[i];
for (int j = 0; j < std::min(prev.size(), curr.size()); ++j) {
int pre = index[prev[j] - 'a'];
int cur = index[curr[j] - 'a'];
if (pre > cur) {
return false;
}
if (pre < cur) {
goto next_word;
}
}
if (prev.size() > curr.size()) {
return false;
}
next_word:;
}
return true;
}
package main
func isAlienSorted(words []string, order string) bool {
index := [26]int{}
for i, c := range order {
index[c-'a'] = i
}
next:
for i := 1; i < len(words); i++ {
for j := 0; j < len(words[i-1]) && j < len(words[i]); j++ {
pre, cur := index[words[i-1][j]-'a'], index[words[i][j]-'a']
if pre > cur {
return false
}
if pre < cur {
continue next
}
}
if len(words[i-1]) > len(words[i]) {
return false
}
}
return true
}
35、
剑指 Offer II 035. 最小时间差
给定一个字符串列表，其中字符串是以"HH:MM"的24小时时间格式进行表示，找到列表中时间差最小值，并以分钟格式进行表示
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
int getMinutes(const std::string &t) {
return (t[0] - '0') * 10 * 60 + (t[1] - '0') * 60 + (t[3] - '0') * 10 +
(t[4] - '0');
}
int findMinDifference(std::vector<std::string> &timePoints) {
if (timePoints.size() > 1440) {
return 0;
}
std::sort(timePoints.begin(), timePoints.end());
int ans = INT_MAX;
int t0Minutes = getMinutes(timePoints[0]);
int preMinutes = t0Minutes;
for (int i = 1; i < timePoints.size(); ++i) {
int minutes = getMinutes(timePoints[i]);
ans = std::min(ans,
minutes - preMinutes); // Difference between adjacent times
preMinutes = minutes;
}
ans = std::min(ans,
t0Minutes + 1440 -
preMinutes); // Difference between the first and last time
return ans;
}
int min(int a, int b) { return a > b ? b : a; }
package main
import (
"math"
"sort"
)
func getMinutes(t string) int {
return (int(t[0]-'0')*10+int(t[1]-'0'))*60 + int(t[3]-'0')*10 + int(t[4]-'0')
}
func findMinDifference(timePoints []string) int {
if len(timePoints) > 1440 {
return 0
}
sort.Strings(timePoints)
ans := math.MaxInt32
t0Minutes := getMinutes(timePoints[0])
preMinutes := t0Minutes
for _, t := range timePoints[1:] {
minutes := getMinutes(t)
ans = min(ans, minutes-preMinutes) // 相邻时间的时间差
preMinutes = minutes
}
ans = min(ans, t0Minutes+1440-preMinutes) // 首尾时间的时间差
return ans
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
36、
剑指 Offer II 036. 后缀表达式
给定一个token字符串列表，该token列表是逆波兰表达式，用来求该后缀表达式的结果，整数除法只保留整数部分
#include <stack>
#include <stdexcept>
#include <string>
#include <vector>
int evalRPN(const std::vector<std::string> &tokens) {
std::stack<int> stack;
for (const auto &token : tokens) {
if (isdigit(token.back())) {
stack.push(std::stoi(token));
} else {
int b = stack.top();
stack.pop();
int a = stack.top();
stack.pop();
if (token == "+") {
stack.push(a + b);
} else if (token == "-") {
stack.push(a - b);
} else if (token == "*") {
stack.push(a * b);
} else if (token == "/") {
stack.push(a / b);
} else {
throw std::invalid_argument("Invalid operator");
}
}
}
return stack.top();
}
package main
import "strconv"
func evalRPN(tokens []string) int {
stack := make([]int, (len(tokens)+1)/2)
index := -1
for _, token := range tokens {
val, err := strconv.Atoi(token)
if err == nil {
index++
stack[index] = val
} else {
index--
switch token {
case "+":
stack[index] += stack[index+1]
case "-":
stack[index] -= stack[index+1]
case "*":
stack[index] *= stack[index+1]
default:
stack[index] /= stack[index+1]
}
}
}
return stack[0]
}
37、
剑指 Offer II 037. 小行星碰撞
给定一个整数数组用来表示同一行的小行星，绝对值表示大小，正负表示方向，正表示向右移动，负表示向左移动。
当两个行星相遇会进行碰撞，留下大小大的那个，大小相同两个一起爆炸
求解最后的小行星情况
#include <vector>
std::vector<int> asteroidCollision(const std::vector<int> &asteroids) {
std::vector<int> st;
for (int aster : asteroids) {
bool alive = true;
while (alive && aster < 0 && !st.empty() && st.back() > 0) {
alive = st.back() < -aster; // Check if the current asteroid survives
if (st.back() <= -aster) { // Top of the stack asteroid explodes
st.pop_back();
}
}
if (alive) {
st.push_back(aster);
}
}
return st;
}
package main
func asteroidCollision(asteroids []int) (st []int) {
for _, aster := range asteroids {
alive := true
for alive && aster < 0 && len(st) > 0 && st[len(st)-1] > 0 {
alive = st[len(st)-1] < -aster // aster 是否存在
if st[len(st)-1] <= -aster { // 栈顶小行星爆炸
st = st[:len(st)-1]
}
}
if alive {
st = append(st, aster)
}
}
return
}
38、
剑指 Offer II 038. 每日温度
给定一个每天的气温列表，返回最近的一个温度更高的相差的天数
#include <stack>
#include <vector>
std::vector<int> dailyTemperatures(const std::vector<int> &temperatures) {
int length = temperatures.size();
std::vector<int> ans(length, 0);
std::stack<int> stack;
for (int i = 0; i < length; ++i) {
int temperature = temperatures[i];
while (!stack.empty() && temperature > temperatures[stack.top()]) {
int prevIndex = stack.top();
stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
package main
func dailyTemperatures(temperatures []int) []int {
length := len(temperatures)
ans := make([]int, length)
stack := []int{}
for i := 0; i < length; i++ {
temperature := temperatures[i]
for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
prevIndex := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans[prevIndex] = i - prevIndex
}
stack = append(stack, i)
}
return ans
}
39、
剑指 Offer II 039. 直方图最大矩形面积
给定一个整数数组，表示一个二维平面，其中每个元素表示其y轴的高度，返回该二维平面中覆盖的最大的矩形面积
#include <algorithm>
#include <stack>
#include <vector>
int largestRectangleArea(const std::vector<int> &heights) {
int n = heights.size();
std::vector<int> left(n), right(n);
std::stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
left[i] = mono_stack.empty() ? -1 : mono_stack.top();
mono_stack.push(i);
}
while (!mono_stack.empty())
mono_stack.pop();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
right[i] = mono_stack.empty() ? n : mono_stack.top();
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = std::max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
int max(int x, int y) { return x > y ? x : y; }
package main
func largestRectangleArea(heights []int) int {
n := len(heights)
left, right := make([]int, n), make([]int, n)
mono_stack := []int{}
for i := 0; i < n; i++ {
for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
mono_stack = mono_stack[:len(mono_stack)-1]
}
if len(mono_stack) == 0 {
left[i] = -1
} else {
left[i] = mono_stack[len(mono_stack)-1]
}
mono_stack = append(mono_stack, i)
}
mono_stack = []int{}
for i := n - 1; i >= 0; i-- {
for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
mono_stack = mono_stack[:len(mono_stack)-1]
}
if len(mono_stack) == 0 {
right[i] = n
} else {
right[i] = mono_stack[len(mono_stack)-1]
}
mono_stack = append(mono_stack, i)
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, (right[i]-left[i]-1)*heights[i])
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
40、
剑指 Offer II 040. 矩阵中最大的矩形
一个只包含0、1元素的矩阵，找到全部为1的元素的最大矩阵的面积
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int maximalRectangle(vector<string> &matrix) {
if (matrix.empty()) {
return 0;
}
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> left(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0') {
continue;
}
if (j == 0) {
left[i][j] = 1;
} else {
left[i][j] = left[i][j - 1] + 1;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '0') {
continue;
}
int width = left[i][j];
int area = width;
for (int k = i - 1; k >= 0; --k) {
width = min(width, left[k][j]);
if (width == 0) {
break;
}
area = max(area, (i - k + 1) * width);
}
ans = max(ans, area);
}
}
return ans;
}
package main
func maximalRectangle(matrix []string) (ans int) {
if len(matrix) == 0 {
return
}
m, n := len(matrix), len(matrix[0])
left := make([][]int, m)
for i, row := range matrix {
left[i] = make([]int, n)
for j, v := range row {
if v == '0' {
continue
}
if j == 0 {
left[i][j] = 1
} else {
left[i][j] = left[i][j-1] + 1
}
}
}
for i, row := range matrix {
for j, v := range row {
if v == '0' {
continue
}
width := left[i][j]
area := width
for k := i - 1; k >= 0; k-- {
width = min(width, left[k][j])
if width == 0 {
break
}
area = max(area, (i-k+1)*width)
}
ans = max(ans, area)
}
}
return
}
41、
剑指 Offer II 041. 滑动窗口的平均值
给定一个指定大小的窗口，提供数据流并返回这个窗口内的元素的平均值
#include <vector>
class MovingAverage {
public:
MovingAverage(int size) : size(size), sum(0) {}
double next(int val) {
if (q.size() == size) {
sum -= q.front();
q.erase(q.begin());
}
sum += val;
q.push_back(val);
return static_cast<double>(sum) / q.size();
}
private:
int size;
int sum;
std::vector<int> q;
};
package main
type MovingAverage struct {
size, sum int
q []int
}
func Constructor(size int) MovingAverage {
return MovingAverage{size: size}
}
func (m *MovingAverage) Next(val int) float64 {
if len(m.q) == m.size {
m.sum -= m.q[0]
m.q = m.q[1:]
}
m.sum += val
m.q = append(m.q, val)
return float64(m.sum) / float64(len(m.q))
}
42、
剑指 Offer II 042. 最近请求次数
记录请求的时间等，并且返回最近3000ms内的调用次数
#include <deque>
class RecentCounter {
public:
RecentCounter() {}
int ping(int t) {
q.push_back(t);
while (q.front() < t - 3000) {
q.pop_front();
}
return q.size();
}
private:
std::deque<int> q;
};
package main
type RecentCounter []int
func NewRecentCounter() (_ RecentCounter) { return }
func (q *RecentCounter) Ping(t int) int {
*q = append(*q, t)
for (*q)[0] < t-3000 {
*q = (*q)[1:]
}
return len(*q)
}
43、
剑指 Offer II 043. 往完全二叉树添加节点
一个尽量集中在左边的完全二叉树，提供插入以及获取根节点的元素
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class CBTInserter {
public:
CBTInserter(TreeNode *root) : root(root) {
std::queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
if (!node->left || !node->right) {
candidate.push_back(node);
}
}
}
int insert(int val) {
TreeNode *child = new TreeNode(val);
TreeNode *node = candidate.front();
if (!node->left) {
node->left = child;
} else {
node->right = child;
candidate.erase(candidate.begin());
}
candidate.push_back(child);
return node->val;
}
TreeNode *get_root() { return root; }
private:
TreeNode *root;
std::vector<TreeNode *> candidate;
};
package main
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type CBTInserter struct {
root *TreeNode
candidate []*TreeNode
}
func NewCBT(root *TreeNode) CBTInserter {
q := []*TreeNode{root}
candidate := []*TreeNode{}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
if node.Left == nil || node.Right == nil {
candidate = append(candidate, node)
}
}
return CBTInserter{root, candidate}
}
func (c *CBTInserter) Insert(val int) int {
child := &TreeNode{Val: val}
node := c.candidate[0]
if node.Left == nil {
node.Left = child
} else {
node.Right = child
c.candidate = c.candidate[1:]
}
c.candidate = append(c.candidate, child)
return node.Val
}
func (c *CBTInserter) Get_root() *TreeNode {
return c.root
}
44、
剑指 Offer II 044. 二叉树每层的最大值
给定一个二叉树，找出二叉树每一层的最大值
#include <algorithm>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector<int> largestValues(TreeNode *root) {
std::vector<int> ans;
dfs(root, 0, ans);
return ans;
}
private:
void dfs(TreeNode *node, int curHeight, std::vector<int> &ans) {
if (!node) {
return;
}
if (curHeight == ans.size()) {
ans.push_back(node->val);
} else {
ans[curHeight] = std::max(ans[curHeight], node->val);
}
dfs(node->left, curHeight + 1, ans);
dfs(node->right, curHeight + 1, ans);
}
};
int max(int a, int b) { return b > a ? b : a; }
package main
func largestValues(root *TreeNode) (ans []int) {
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, curHeight int) {
if node == nil {
return
}
if curHeight == len(ans) {
ans = append(ans, node.Val)
} else {
ans[curHeight] = max(ans[curHeight], node.Val)
}
dfs(node.Left, curHeight+1)
dfs(node.Right, curHeight+1)
}
dfs(root, 0)
return
}
45、
剑指 Offer II 045. 二叉树最底层最左边的值
给定一个二叉树，找出二叉树最底层，最左边的元素
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int findBottomLeftValue(TreeNode *root) {
int curVal = 0;
int curHeight = 0;
dfs(root, 0, curHeight, curVal);
return curVal;
}
private:
void dfs(TreeNode *node, int height, int &curHeight, int &curVal) {
if (!node) {
return;
}
height++;
dfs(node->left, height, curHeight, curVal);
dfs(node->right, height, curHeight, curVal);
if (height > curHeight) {
curHeight = height;
curVal = node->val;
}
}
};
package main
func findBottomLeftValue(root *TreeNode) (curVal int) {
curHeight := 0
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, height int) {
if node == nil {
return
}
height++
dfs(node.Left, height)
dfs(node.Right, height)
if height > curHeight {
curHeight = height
curVal = node.Val
}
}
dfs(root, 0)
return
}
46、
剑指 Offer II 046. 二叉树的右侧视图
给定一个二叉树，返回其右边的第一层视图，并从上往下打印出来
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector<int> rightSideView(TreeNode *root) {
std::vector<int> ans;
if (!root) {
return ans;
}
dfs(root, 0, ans);
return ans;
}
private:
void dfs(TreeNode *node, int depth, std::vector<int> &ans) {
if (!node) {
return;
}
if (depth == ans.size()) {
ans.push_back(node->val);
}
dfs(node->right, depth + 1, ans);
dfs(node->left, depth + 1, ans);
}
};
package main
func rightSideView(root *TreeNode) []int {
ans := []int{}
if root == nil {
return ans
}
var dfs func(node *TreeNode, depth int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if len(ans) == depth {
ans = append(ans, node.Val)
}
dfs(node.Right, depth+1)
dfs(node.Left, depth+1)
}
dfs(root, 0)
return ans
}
47、
剑指 Offer II 047. 二叉树剪枝
给定一个二叉树，对所有只包含0数据的子树进行剪枝
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *pruneTree(TreeNode *root) {
if (!root) {
return nullptr;
}
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (!root->left && !root->right && root->val == 0) {
return nullptr;
}
return root;
}
};
package main
func pruneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left = pruneTree(root.Left)
root.Right = pruneTree(root.Right)
if root.Left == nil && root.Right == nil && root.Val == 0 {
return nil
}
return root
}
48、
剑指 Offer II 048. 序列化与反序列化二叉树
将二叉树进行序列化和反序列化
#include <queue>
#include <sstream>
#include <string>
#include <vector>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Codec {
public:
// Serializes a tree to a single string.
std::string serialize(TreeNode *root) {
std::ostringstream sb;
serializeHelper(root, sb);
return sb.str();
}
// Deserializes your encoded data to tree.
TreeNode *deserialize(const std::string &data) {
std::vector<std::string> nodes = split(data, ',');
int index = 0;
return deserializeHelper(nodes, index);
}
private:
void serializeHelper(TreeNode *node, std::ostringstream &sb) {
if (!node) {
sb << "null,";
return;
}
sb << node->val << ',';
serializeHelper(node->left, sb);
serializeHelper(node->right, sb);
}
TreeNode *deserializeHelper(const std::vector<std::string> &nodes,
int &index) {
if (index >= nodes.size() || nodes[index] == "null") {
++index;
return nullptr;
}
TreeNode *node = new TreeNode(std::stoi(nodes[index++]));
node->left = deserializeHelper(nodes, index);
node->right = deserializeHelper(nodes, index);
return node;
}
std::vector<std::string> split(const std::string &s, char delimiter) {
std::vector<std::string> tokens;
std::string token;
std::istringstream tokenStream(s);
while (std::getline(tokenStream, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}
};
package main
import (
"strconv"
"strings"
)
type Codec struct{}
func NewCodeC() (_ Codec) {
return
}
func (Codec) serialize(root *TreeNode) string {
sb := &strings.Builder{}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
sb.WriteString("null,")
return
}
sb.WriteString(strconv.Itoa(node.Val))
sb.WriteByte(',')
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return sb.String()
}
func (Codec) deserialize(data string) *TreeNode {
sp := strings.Split(data, ",")
var build func() *TreeNode
build = func() *TreeNode {
if sp[0] == "null" {
sp = sp[1:]
return nil
}
val, _ := strconv.Atoi(sp[0])
sp = sp[1:]
return &TreeNode{val, build(), build()}
}
return build()
}
49、
剑指 Offer II 049. 从根节点到叶节点的路径数字之和
给定一个二叉树，获取从根节点到叶子节点的所有路径所表示的数字之和。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int sumNumbers(TreeNode *root) { return dfs(root, 0); }
private:
int dfs(TreeNode *node, int prevSum) {
if (!node) {
return 0;
}
int sum = prevSum * 10 + node->val;
if (!node->left && !node->right) {
return sum;
}
return dfs(node->left, sum) + dfs(node->right, sum);
}
};
package main
func dfs(root *TreeNode, prevSum int) int {
if root == nil {
return 0
}
sum := prevSum*10 + root.Val
if root.Left == nil && root.Right == nil {
return sum
}
return dfs(root.Left, sum) + dfs(root.Right, sum)
}
func sumNumbers(root *TreeNode) int {
return dfs(root, 0)
}
50、
剑指 Offer II 050. 向下的路径节点之和
给定一个二叉树，返回其中路径和为target的路径个数，其中这路径只能从上往下
#include <unordered_map>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int pathSum(TreeNode *root, int targetSum) {
std::unordered_map<long long, int> preSum;
preSum[0] = 1;
return dfs(root, 0, targetSum, preSum);
}
private:
int dfs(TreeNode *node, long long curr, int targetSum,
std::unordered_map<long long, int> &preSum) {
if (!node) {
return 0;
}
curr += node->val;
int ans = preSum[curr - targetSum];
preSum[curr]++;
ans += dfs(node->left, curr, targetSum, preSum);
ans += dfs(node->right, curr, targetSum, preSum);
preSum[curr]--;
return ans;
}
};
package main
func pathSum(root *TreeNode, targetSum int) (ans int) {
preSum := map[int64]int{0: 1}
var dfs func(*TreeNode, int64)
dfs = func(node *TreeNode, curr int64) {
if node == nil {
return
}
curr += int64(node.Val)
ans += preSum[curr-int64(targetSum)]
preSum[curr]++
dfs(node.Left, curr)
dfs(node.Right, curr)
preSum[curr]--
return
}
dfs(root, 0)
return
}
51、
剑指 Offer II 051. 节点之和最大的路径
给定一个二叉树，返回其最大的路径和，这里的路径可以是任意两个节点之间相连的路径
#include <algorithm>
#include <climits>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxPathSum(TreeNode *root) {
maxSum = INT_MIN;
maxGain(root);
return maxSum;
}
private:
int maxSum;
int maxGain(TreeNode *node) {
if (!node) {
return 0;
}
// Recursively calculate the maximum contribution of the left and right
// subtrees Only consider positive contributions
int leftGain = std::max(maxGain(node->left), 0);
int rightGain = std::max(maxGain(node->right), 0);
// The price to start a new path where `node` is the highest node
int priceNewPath = node->val + leftGain + rightGain;
// Update the maximum sum if the new path is better
maxSum = std::max(maxSum, priceNewPath);
// Return the maximum gain if continuing the same path
return node->val + std::max(leftGain, rightGain);
}
};
package main
import "math"
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
var maxGain func(*TreeNode) int
maxGain = func(node *TreeNode) int {
if node == nil {
return 0
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
leftGain := max(maxGain(node.Left), 0)
rightGain := max(maxGain(node.Right), 0)
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
priceNewPath := node.Val + leftGain + rightGain
// 更新答案
maxSum = max(maxSum, priceNewPath)
// 返回节点的最大贡献值
return node.Val + max(leftGain, rightGain)
}
maxGain(root)
return maxSum
}
52、
剑指 Offer II 052. 展平二叉搜索树
给定一个二叉搜索树，将其进行结构转换，使得没有左节点，只有右节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *increasingBST(TreeNode *root) {
TreeNode *dummyNode = new TreeNode(0);
TreeNode *resNode = dummyNode;
inorder(root, resNode);
return dummyNode->right;
}
private:
void inorder(TreeNode *node, TreeNode *&resNode) {
if (!node) {
return;
}
inorder(node->left, resNode);
// Modify the node pointers during in-order traversal
resNode->right = node;
node->left = nullptr;
resNode = node;
inorder(node->right, resNode);
}
};
package main
func increasingBST(root *TreeNode) *TreeNode {
dummyNode := &TreeNode{}
resNode := dummyNode
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
// 在中序遍历的过程中修改节点指向
resNode.Right = node
node.Left = nil
resNode = node
inorder(node.Right)
}
inorder(root)
return dummyNode.Right
}
53、
剑指 Offer II 053. 二叉搜索树中的中序后继
给定一个二叉搜索树以及一个节点，找到这个节点的中序后继
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *inorderSuccessor(TreeNode *root, TreeNode *p) {
TreeNode *successor = nullptr;
if (p->right) {
successor = p->right;
while (successor->left) {
successor = successor->left;
}
return successor;
}
TreeNode *node = root;
while (node) {
if (node->val > p->val) {
successor = node;
node = node->left;
} else {
node = node->right;
}
}
return successor;
}
};
package main
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
var successor *TreeNode
if p.Right != nil {
successor = p.Right
for successor.Left != nil {
successor = successor.Left
}
return successor
}
node := root
for node != nil {
if node.Val > p.Val {
successor = node
node = node.Left
} else {
node = node.Right
}
}
return successor
}
54、
剑指 Offer II 054. 所有大于等于节点的值之和
给定一个二叉搜索树，将每个节点替换成大于他节点的元素的和
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode *convertBST(TreeNode *root) {
int sum = 0;
dfs(root, sum);
return root;
}
private:
void dfs(TreeNode *node, int &sum) {
if (node != nullptr) {
dfs(node->right, sum);
sum += node->val;
node->val = sum;
dfs(node->left, sum);
}
}
};
package main
func convertBST(root *TreeNode) *TreeNode {
sum := 0
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node != nil {
dfs(node.Right)
sum += node.Val
node.Val = sum
dfs(node.Left)
}
}
dfs(root)
return root
}
55、
剑指 Offer II 055. 二叉搜索树迭代器
给定一个二叉搜素树迭代器，提供next和hasNext两个方法
#include <stack>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BSTIterator {
public:
BSTIterator(TreeNode *root) : cur(root) {}
int next() {
while (cur) {
stack.push(cur);
cur = cur->left;
}
cur = stack.top();
stack.pop();
int val = cur->val;
cur = cur->right;
return val;
}
bool hasNext() { return cur != nullptr || !stack.empty(); }
private:
std::stack<TreeNode *> stack;
TreeNode *cur;
};
package main
type BSTIterator struct {
stack []*TreeNode
cur *TreeNode
}
func NewBSTIterator(root *TreeNode) BSTIterator {
return BSTIterator{cur: root}
}
func (it *BSTIterator) Next() int {
for node := it.cur; node != nil; node = node.Left {
it.stack = append(it.stack, node)
}
it.cur, it.stack = it.stack[len(it.stack)-1], it.stack[:len(it.stack)-1]
val := it.cur.Val
it.cur = it.cur.Right
return val
}
func (it *BSTIterator) HasNext() bool {
return it.cur != nil || len(it.stack) > 0
}
56、
剑指 Offer II 056. 二叉搜索树中两个节点之和
判断二叉搜索树中是否存在两个节点，和为目标值
#include <unordered_set>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool findTarget(TreeNode *root, int k) {
std::unordered_set<int> visit;
bool flag = false;
inorder(root, k, visit, flag);
return flag;
}
private:
void inorder(TreeNode *node, int k, std::unordered_set<int> &visit,
bool &flag) {
if (!node || flag) {
return;
}
inorder(node->left, k, visit, flag);
if (visit.count(k - node->val)) {
flag = true;
return;
}
visit.insert(node->val);
inorder(node->right, k, visit, flag);
}
};
package main
func findTarget(root *TreeNode, k int) bool {
visit := map[int]struct{}{}
flag := false
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil || flag {
return
}
inorder(node.Left)
if _, ok := visit[k-node.Val]; ok {
flag = true
return
}
visit[node.Val] = struct{}{}
inorder(node.Right)
}
inorder(root)
return flag
}
57、
剑指 Offer II 057. 值和下标之差都在给定的范围内
给定一个数组，判断是否存在两个下标i、j，下标差绝对值小于等于k，所对应的值差值小于等于t
#include <cmath>
#include <unordered_map>
#include <vector>
int getID(int x, int w) {
if (x >= 0) {
return x / w;
}
return (x + 1) / w - 1;
}
bool containsNearbyAlmostDuplicate(const std::vector<int> &nums, int k, int t) {
std::unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); ++i) {
int x = nums[i];
int id = getID(x, t + 1);
if (mp.count(id)) {
return true;
}
if (mp.count(id - 1) && std::abs(x - mp[id - 1]) <= t) {
return true;
}
if (mp.count(id + 1) && std::abs(x - mp[id + 1]) <= t) {
return true;
}
mp[id] = x;
if (i >= k) {
mp.erase(getID(nums[i - k], t + 1));
}
}
return false;
}
int abs(int x) { return x < 0 ? -x : x; }
package main
func getID(x, w int) int {
if x >= 0 {
return x / w
}
return (x+1)/w - 1
}
func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
mp := map[int]int{}
for i, x := range nums {
id := getID(x, t+1)
if _, has := mp[id]; has {
return true
}
if y, has := mp[id-1]; has && abs(x-y) <= t {
return true
}
if y, has := mp[id+1]; has && abs(x-y) <= t {
return true
}
mp[id] = x
if i >= k {
delete(mp, getID(nums[i-k], t+1))
}
}
return false
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
58、
剑指 Offer II 058. 日程表
提供一个方法，在添加日程的时候，时间区间为[start, end), 只要这个时间段没有其他安排就能够使用
#include <map>
class MyCalendar {
public:
MyCalendar() {}
bool book(int start, int end) {
if (query(start, end - 1, 0, 1e9, 1)) {
return false;
}
update(start, end - 1, 0, 1e9, 1);
return true;
}
private:
std::map<int, bool> tree, lazy;
bool query(int start, int end, int l, int r, int idx) {
if (r < start || end < l) {
return false;
}
if (lazy[idx]) { // If the interval is already booked, return true
return true;
}
if (start <= l && r <= end) {
return tree[idx];
}
int mid = (l + r) >> 1;
return query(start, end, l, mid, 2 * idx) ||
query(start, end, mid + 1, r, 2 * idx + 1);
}
void update(int start, int end, int l, int r, int idx) {
if (r < start || end < l) {
return;
}
if (start <= l && r <= end) {
tree[idx] = true;
lazy[idx] = true;
} else {
int mid = (l + r) >> 1;
update(start, end, l, mid, 2 * idx);
update(start, end, mid + 1, r, 2 * idx + 1);
tree[idx] = true;
if (lazy[2 * idx] && lazy[2 * idx + 1]) {
lazy[idx] = true;
}
}
}
};
package main
type MyCalendar struct {
tree, lazy map[int]bool
}
func NewMyCalendar() MyCalendar {
return MyCalendar{map[int]bool{}, map[int]bool{}}
}
func (c MyCalendar) query(start, end, l, r, idx int) bool {
if r < start || end < l {
return false
}
if c.lazy[idx] { // 如果该区间已被预订，则直接返回
return true
}
if start <= l && r <= end {
return c.tree[idx]
}
mid := (l + r) >> 1
return c.query(start, end, l, mid, 2*idx) ||
c.query(start, end, mid+1, r, 2*idx+1)
}
func (c MyCalendar) update(start, end, l, r, idx int) {
if r < start || end < l {
return
}
if start <= l && r <= end {
c.tree[idx] = true
c.lazy[idx] = true
} else {
mid := (l + r) >> 1
c.update(start, end, l, mid, 2*idx)
c.update(start, end, mid+1, r, 2*idx+1)
c.tree[idx] = true
if c.lazy[2*idx] && c.lazy[2*idx+1] {
c.lazy[idx] = true
}
}
}
func (c MyCalendar) Book(start, end int) bool {
if c.query(start, end-1, 0, 1e9, 1) {
return false
}
c.update(start, end-1, 0, 1e9, 1)
return true
}
59、
剑指 Offer II 059. 数据流的第 K 大数值
一个数据流结构，在插入元素的时候返回数据中第k大的数。
#include <functional>
#include <queue>
#include <vector>
class KthLargest {
public:
KthLargest(int k, std::vector<int> &nums) : k(k) {
for (int val : nums) {
add(val);
}
}
int add(int val) {
if (minHeap.size() < k) {
minHeap.push(val);
} else if (val > minHeap.top()) {
minHeap.push(val);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.top();
}
private:
int k;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
};
package main
import (
"container/heap"
"sort"
)
type KthLargest struct {
sort.IntSlice
k int
}
func NewKthLargest(k int, nums []int) KthLargest {
kl := KthLargest{k: k}
for _, val := range nums {
kl.Add(val)
}
return kl
}
func (kl *KthLargest) Push(v interface{}) {
kl.IntSlice = append(kl.IntSlice, v.(int))
}
func (kl *KthLargest) Pop() interface{} {
a := kl.IntSlice
v := a[len(a)-1]
kl.IntSlice = a[:len(a)-1]
return v
}
func (kl *KthLargest) Add(val int) int {
heap.Push(kl, val)
if kl.Len() > kl.k {
heap.Pop(kl)
}
return kl.IntSlice[0]
}
60、
剑指 Offer II 060. 出现频率最高的 k 个数字
统计数字数组中元素的出现次数，返回出现频率最高的几个
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>
class IHeap {
public:
bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
return a.second > b.second;
}
};
std::vector<int> topKFrequent(std::vector<int> &nums, int k) {
std::unordered_map<int, int> occurrences;
for (int num : nums) {
occurrences[num]++;
}
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
IHeap>
h;
for (const auto &[key, value] : occurrences) {
h.emplace(key, value);
if (h.size() > k) {
h.pop();
}
}
std::vector<int> ret(k);
for (int i = k - 1; i >= 0; --i) {
ret[i] = h.top().first;
h.pop();
}
return ret;
}
package main
import "container/heap"
func topKFrequent(nums []int, k int) []int {
occurrences := map[int]int{}
for _, num := range nums {
occurrences[num]++
}
h := &IHeap{}
heap.Init(h)
for key, value := range occurrences {
heap.Push(h, [2]int{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
ret := make([]int, k)
for i := 0; i < k; i++ {
ret[k-i-1] = heap.Pop(h).([2]int)[0]
}
return ret
}
type IHeap [][2]int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}