c#网站购物车怎么做,做公司网站都需要付什么费用,一家网站建设公司需要什么资质,网站建设层级图本篇博客是用Go语言编写的详尽简洁代码#xff0c;这里没有写算法思路#xff0c;若要看具体思路#xff0c;请移步力扣官网查看相关高赞题解。本篇博客的特点是代码简洁明了#xff0c;包含多种写法#xff0c;适合读者后期复盘巩固#xff0c;加深理解。这一百题是面试…本篇博客是用Go语言编写的详尽简洁代码这里没有写算法思路若要看具体思路请移步力扣官网查看相关高赞题解。本篇博客的特点是代码简洁明了包含多种写法适合读者后期复盘巩固加深理解。这一百题是面试高频题建议读者认真阅读背诵记忆。欢迎点赞收藏关注~~
LC201 数字范围按位与
func rangeBitwiseAnd(l int, r int) int {i : 0for l r {l 1r 1i }return l i
}func rangeBitwiseAnd(l int, r int) int {for l r {r r (r - 1)}return r // 注意是返回r而不能是返回l
}LC202 快乐数
func get(n int) int {ans : 0for n 0 {ans (n % 10) * (n % 10)n / 10}return ans
}func isHappy(n int) bool {slow, fast : n, get(n)for slow ! fast {slow get(slow)fast get(get(fast))}return slow 1
}func get(n int) int {ans : 0for n 0 {ans (n % 10) * (n % 10)n / 10}return ans
}func isHappy(n int) bool {slow, fast : n, nfor {slow get(slow)fast get(get(fast))if slow fast {break}}return slow 1
}LC203 移除链表元素
func removeElements(head *ListNode, x int) *ListNode {if head nil {return nil}head.Next removeElements(head.Next, x)if head.Val x {return head.Next}return head
}func removeElements(head *ListNode, x int) *ListNode {if head nil {return nil}dummy : ListNode{-1, head}var cur *ListNode dummyfor cur.Next ! nil {if cur.Next.Val x {cur.Next cur.Next.Next} else {cur cur.Next}}return dummy.Next
}LC204 计数质数
func countPrimes(n int) int {st : make([]bool, n 1)primes : []int{}for i : 2; i n; i {if !st[i] {primes append(primes, i)}for j : 0; j len(primes) primes[j] n / i; j {st[i * primes[j]] trueif i % primes[j] 0 {break}}}return len(primes)
}LC205 同构字符串
func isIsomorphic(s string, t string) bool {n, m : len(s), len(t)if n ! m {return false}st, ts : make(map[byte]byte), make(map[byte]byte)for i : 0; i n; i {x, y : s[i], t[i]if (st[x] ! 0 st[x] ! y) || (ts[y] ! 0 ts[y] ! x) {return false}st[x] yts[y] x}return true
}LC206 反转链表
func reverseList(head *ListNode) *ListNode {if head nil || head.Next nil {return head}last : reverseList(head.Next)head.Next.Next headhead.Next nilreturn last
}func reverseList(head *ListNode) *ListNode {if head nil || head.Next nil {return head}var pre, cur *ListNode nil, headfor cur ! nil {nxt : cur.Nextcur.Next prepre curcur nxt}return pre
}LC207 课程表
func canFinish(n int, edges [][]int) bool {d : make([]int, n)g : make([][]int, n)for _, e : range edges {a, b : e[1], e[0]g[a] append(g[a], b)d[b] }q : []int{}for i : 0; i n; i {if d[i] 0 {q append(q, i)}}cnt : 0for len(q) 0 {t : q[0]q q[1:]cnt for _, i : range g[t] {d[i] --if d[i] 0 {q append(q, i)}}}return cnt n
}LC208 实现Trie前缀树
type Trie struct {isEnd booltr [26]*Trie
}func Constructor() Trie {return Trie{}
}func (root *Trie) Insert(word string) {p : rootfor _, c : range word {u : c - aif p.tr[u] nil {p.tr[u] Trie{}}p p.tr[u]}p.isEnd true
}func (root *Trie) Search(word string) bool {p : rootfor _, c : range word {u : c - aif p.tr[u] nil {return false}p p.tr[u]}return p.isEnd
}func (root *Trie) StartsWith(prefix string) bool {p : rootfor _, c : range prefix {u : c - aif p.tr[u] nil {return false}p p.tr[u]}return true
}LC209 长度最小的子数组
func minSubArrayLen(target int, nums []int) int {n : len(nums)if n 0 {return 0}l, sum, ans : 0, 0, math.MaxInt32for r, x : range nums {sum xfor sum target {ans min(ans, r - l 1)sum - nums[l]l }}if ans math.MaxInt32 {return 0}return ans
}LC210 课程表II
func findOrder(n int, edges [][]int) []int {d : make([]int, n)g : make([][]int, n)for _, e : range edges {a, b : e[1], e[0]d[b] g[a] append(g[a], b)}q : []int{}for i : 0; i n; i {if d[i] 0 {q append(q, i)}}ans : []int{}for len(q) 0 {t : q[0]q q[1:]ans append(ans, t)for _, i : range g[t] {d[i] --if d[i] 0 {q append(q, i)}}}if len(ans) n {return []int{}}return ans
}LC211 添加与搜索单词
type Trie struct {isEnd booltr [26]*Trie
}type WordDictionary struct {root *Trie
}func Constructor() WordDictionary {return WordDictionary{Trie{}}
}func (w *WordDictionary) AddWord(word string) {p : w.rootfor _, c : range word {u : c - aif p.tr[u] nil {p.tr[u] Trie{}}p p.tr[u]}p.isEnd true
}func (w *WordDictionary) Search(word string) bool {return dfs(w.root, word, 0)
}func dfs(p *Trie, word string, i int) bool {if p nil {return false}if i len(word) {return p.isEnd}if word[i] ! . {return dfs(p.tr[word[i] - a], word, i 1)} else {for u : 0; u 26; u {if dfs(p.tr[u], word, i 1) {return true}}}return false
}LC212 单词搜索II
type Node struct {word stringtr [26]*Node
}var (dx []int{-1, 0, 1, 0}dy []int{0, 1, 0, -1}g [][]bytes map[string]struct{}root *Noden, m int
)func ins(word string) {p : rootfor _, c : range word {u : c - aif p.tr[u] nil {p.tr[u] Node{}}p p.tr[u]}p.word word
}func dfs(p *Node, x int, y int) {if p.word ! {s[p.word] struct{}{}}t : g[x][y]g[x][y] #for i : 0; i 4; i {a : x dx[i]b : y dy[i]if a 0 a n b 0 b m g[a][b] ! # {u : g[a][b] - aif p.tr[u] ! nil {dfs(p.tr[u], a, b)}}}g[x][y] t
}func findWords(board [][]byte, words []string) []string {g boardn, m len(g), len(g[0])s make(map[string]struct{})root Node{} for _, word : range words {ins(word)}for i : 0; i n; i {for j : 0; j m; j {u : board[i][j] - aif root.tr[u] ! nil {dfs(root.tr[u], i, j)}}}var ans []stringfor word : range s {ans append(ans, word)}return ans
}LC213 打家劫舍II
func rob(nums []int) int {n : len(nums)if n 0 {return 0}if n 1 {return nums[0]}if n 2 {return max(nums[0], nums[1])}f : make([]int, n)ans : 0f[0], f[1] nums[0], max(nums[0], nums[1])for i : 2; i n - 1; i {f[i] max(f[i - 1], f[i - 2] nums[i])}ans max(ans, f[n - 2])f[0], f[1] 0, nums[1]for i : 2; i n; i {f[i] max(f[i - 1], f[i - 2] nums[i])}ans max(ans, f[n - 1])return ans
}func max(x, y int) int {if x y {return x}return y
}func rob(nums []int) int {n : len(nums)if n 0 {return 0}if n 1 {return nums[0]}if n 2 {return max(nums[0], nums[1])}one : robRange(nums, 0, n - 2)last : robRange(nums, 1, n - 1)return max(one, last)
}func robRange(nums []int, l, r int) int {a, b : nums[l], max(nums[l], nums[l 1])for i : l 2; i r; i {tmp : bb max(b, a nums[i])a tmp}return b
}func max(x, y int) int {if x y {return x}return y
}LC214 最短回文串
func reverse(str string) string {s : []rune(str)for i, j : 0, len(s) - 1; i j; i, j i 1, j - 1 {s[i], s[j] s[j], s[i]}return string(s)
}func shortestPalindrome(s string) string {n : len(s)t : reverse(s)str : ss s # tne : make([]int, 2 * n 2)for i, j : 2, 0; i 2 * n 1; i {for j 0 s[i] ! s[j 1] {j ne[j]}if s[i] s[j 1] {j }ne[i] j}x : ne[2 * n 1] // 最长公共回文前后缀的长度xfront : reverse(s[x 1 : n 1]) // 反转从起点x1开始长度为n-x的这段子串return front str
}func reverse(str string) string {s : []rune(str)for i, j : 0, len(s) - 1; i j; i, j i 1, j - 1{s[i], s[j] s[j], s[i]}return string(s)
}func shortestPalindrome(s string) string {n, pos : len(s), -1var left, right, mul uint64 0, 0, 1const base 13331for i : 0; i n; i {left left * base uint64(s[i])right uint64(s[i]) * mulif left right {pos i}mul * base}t : s[pos 1 : ]front : reverse(t)return front s
}LC215 数组中的第K个最大元素
// 使用优先队列时间复杂度是O(nlogn)但其实并不符合题意
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint, vectorint, greaterint q;for (auto x : nums) {if (q.size() k || q.top() x) q.push(x);if (q.size() k) q.pop();}return q.top();}
};// 快速选择时间复杂度是O(n)符合题意
class Solution {
public:int quick_select(vectorint nums, int l, int r, int k) {if (l r) return nums[r];swap(nums[l], nums[l rand() % (r - l 1)]);int i l - 1, j r 1, x nums[l];while (i j) {while (nums[ i] x) ;while (nums[ -- j] x) ;if (i j) swap(nums[i], nums[j]); }int s j - l 1;if (k s) return quick_select(nums, l, j, k);return quick_select(nums, j 1, r, k - s);}int findKthLargest(vectorint nums, int k) {return quick_select(nums, 0, nums.size() - 1, k);}
};LC216 组合总和III
var (ans [][]intpath []intk, n int
)func dfs(start, sum int) {if sum n {return }if len(path) (9 - start 1) k {return }if len(path) k sum n {tmp : make([]int, len(path))copy(tmp, path)ans append(ans, tmp)return}for i : start; i 9; i {sum ipath append(path, i)dfs(i 1, sum)sum - ipath path[: len(path) - 1]}
}func combinationSum3(_k int, _n int) [][]int {k, n _k, _nans, path [][]int{}, []int{}dfs(1, 0)return ans
}LC217 存在重复元素
func containsDuplicate(nums []int) bool {S : map[int]bool{}for _, x : range nums {if S[x] {return true}S[x] true}return false
}LC218 天际线问题
class Solution {
public:vectorvectorint getSkyline(vectorvectorint buildings) {vectorvectorint ans;vectorpairint, int height;/*正负用于判别是左端点还是右端点同时保证排序后1. 左端点相同时最高的楼排在前面insert的一定是相同左端点中最大的高度2. 右端点相同时最低的楼排在前面erase的时候不会改变最大高度*/for (auto b : buildings) { height.push_back({b[0], -b[2]}); // 左端点height.push_back({b[1], b[2]}); // 右端点}sort(height.begin(), height.end()); // 排序multisetint S; // 维护当前最大高度/*由于题目中最后的x轴的点算入了答案中所以可以认为x轴这个也是一个楼所以这里把x轴也加入到高度里面也就是在高度的multiset里加入0*/S.insert(0); // 保证端点全部删除之后能得到当前最大高度为 0// preMaxHeight 表示遇到一个端点之前的最大高度// curMaxHeight 表示遇到一个端点之后的当前最大高度int preMaxHeight 0, curMaxHeight 0;for (auto h : height) {// 左端点if (h.second 0) S.insert(-h.second);// 右端点else S.erase(S.find(h.second));curMaxHeight *S.rbegin();// 最大高度发生改变一定是一个关键点即一个水平线段的左端点if (curMaxHeight ! preMaxHeight) {ans.push_back({h.first, curMaxHeight});preMaxHeight curMaxHeight;}}return ans;}
};LC219 存在重复元素II
func containsNearbyDuplicate(nums []int, k int) bool {mp : map[int]int{}for i, x : range nums {_, ok : mp[x]if ok abs(i - mp[x]) k {return true}mp[x] i}return false
}func abs(x int) int {if x 0 {return -x}return x
}LC220 存在重复元素III
class Solution {
public:using LL long long;bool containsNearbyAlmostDuplicate(vectorint nums, int k, int t) {multisetLL S;for (int i 0; i nums.size(); i) {LL x nums[i];auto it S.lower_bound(x - t);if (it ! S.end() *it x t) return true;S.insert(x);// 窗口区间是[i-k, i-1], 所以移除左端点元素就是nums[i - k]if (i k ) S.erase(S.find(nums[i - k]));}return false;}
};LC221 最大正方形
func solve(h []int) int {n : len(h)l, r : make([]int, n), make([]int ,n)stk : []int{}for i : 0; i n; i {for len(stk) 0 h[stk[len(stk) - 1]] h[i] {stk stk[: len(stk) - 1]}if len(stk) 0 {l[i] -1} else {l[i] stk[len(stk) - 1]}stk append(stk, i)}stk []int{}for i : n - 1; i 0; i -- {for len(stk) 0 h[stk[len(stk) - 1]] h[i] {stk stk[: len(stk) - 1]}if len(stk) 0 {r[i] n} else {r[i] stk[len(stk) - 1]}stk append(stk, i)}ans : 0for i : 0; i n; i {// 区别这边找到高h[i]宽r[i] - l[i] -1 中最小的作为正方形的边长x : min(h[i], r[i] - l[i] - 1)ans max(ans, x * x)}return ans
}func maximalSquare(g [][]byte) int {n, m : len(g), len(g[0])if n 0 || m 0 {return 0}s : make([][]int, n)for i : 0; i n; i {s[i] make([]int, m)}for i : 0; i n; i {for j : 0; j m; j {if g[i][j] 1 {if i 0 {s[i][j] s[i - 1][j] 1} else {s[i][j] 1}}}}ans : 0for i : 0; i n; i {ans max(ans, solve(s[i]))}return ans
}func maximalSquare(g [][]byte) int {n, m, len : len(g), len(g[0]), 0if n 0 || m 0 {return 0}f : make([][]int, n 1)for i : 0; i n 1; i {f[i] make([]int, m 1)}for i : 1; i n; i {for j : 1; j m; j {if g[i - 1][j - 1] 1 {f[i][j] min(min(f[i - 1][j - 1], f[i - 1][j]), f[i][j - 1]) 1len max(len, f[i][j])}}}return len * len
}LC222 完全二叉树的节点个数
// 时间复杂度O(logn * logn) 空间复杂度O(logn)
func countNodes(root *TreeNode) int {if root nil {return 0}x, y, l, r : 1, 1, root.Left, root.Rightfor l ! nil {l l.Leftx }for r ! nil {r r.Righty }if x y {return (1 x) - 1}return countNodes(root.Left) 1 countNodes(root.Right)
}// 时间复杂度O(logn * logn) 空间复杂度O(1)
func check(root *TreeNode, h, k int) bool {bits : 1 (h - 1)for root ! nil bits ! 0 {if bits k ! 0 {root root.Right} else {root root.Left}bits 1}return root ! nil
}func countNodes(root *TreeNode) int {if root nil {return 0}h, t : 0, rootfor t.Left ! nil {h t t.Left}if h 0 {return 1}l, r : 1 h, (1 (h 1)) - 1for l r {mid : (l r 1) 1if check(root, h, mid) {l mid} else {r mid - 1}}return l
}LC223 矩形面积
func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {x : max(0, min(ax2, bx2) - max(ax1, bx1))y : max(0, min(ay2, by2) - max(ay1, by1))return (ax2 - ax1) * (ay2 - ay1) (bx2 - bx1) * (by2 - by1) - x * y
}LC224 基本计算器
class Solution {
public:stackint nums; // 操作数栈stackchar op; // 操作符栈 保存 ( - * / 注意右括号)是不会入栈的unordered_mapchar, int pr { // 操作符的优先级{(, 0}, {, 1}, {-, 1}, {*, 2}, {/, 2}};void eval() {int b nums.top(); nums.pop();int a nums.top(); nums.pop();char c op.top(); op.pop();if (c ) a b;else if (c -) a - b;else if (c *) a * b;else if (c /) a / b;nums.push(a);}int calculate(string str) {string s;for (auto c : str) // 先去除空格if (c ! )s c;for (int i 0; i s.size(); i) {char c s[i];if (isdigit(c)) { // 数字int j i;while (j s.size() isdigit(s[j])) j;int x stoi(s.substr(i, j - i));nums.push(x);i j - 1;} else if (c () { // 左括号op.push(c);} else if (c )) { // 右括号while (!op.empty() op.top() ! () eval();op.pop(); // 弹出左括号} else { // 符号 比如 - / *// 这里很坑注意细节// !i处理情况5-6 添加0使其成为05-6这种形式让成为加法而不是正号// s[i-1](处理情况1-(-2) 添加0使其成为1-(0-2)然-成为减法而不是负号if (!i || s[i - 1] () nums.push(0);while (!op.empty() pr[op.top()] pr[c]) eval();op.push(c);}}while (!op.empty()) eval();return nums.top();}
};LC225 用队列实现栈
// 两个队列实现栈
type MyStack struct {q, tmp []int
}func Constructor() MyStack {return MyStack{}
}func (this *MyStack) Push(x int) {this.q append(this.q, x)
}func (this *MyStack) Pop() int {s : len(this.q)for i : 1; i s; i {this.tmp append(this.tmp, this.q[0])this.q this.q[1:]}ans : this.q[0]this.q this.q[1:]this.q, this.tmp this.tmp, this.qreturn ans
}func (this *MyStack) Top() int {return this.q[len(this.q) - 1]
}func (this *MyStack) Empty() bool {return len(this.q) 0
}// 一个队列实现栈
type MyStack struct {q []int
}func Constructor() MyStack {return MyStack{}
}func (this *MyStack) Push(x int) {this.q append(this.q, x)
}func (this *MyStack) Pop() int {s : len(this.q)for i : 1; i s; i {this.q append(this.q, this.q[0])this.q this.q[1:]}ans : this.q[0]this.q this.q[1:]return ans
}func (this *MyStack) Top() int {return this.q[len(this.q) - 1]
}func (this *MyStack) Empty() bool {return len(this.q) 0
}LC226 翻转二叉树
func invertTree(root *TreeNode) *TreeNode {if root nil {return nil}root.Left, root.Right root.Right, root.LeftinvertTree(root.Left)invertTree(root.Right)return root
}LC227 基本计算器II
// LC224的弱化版可以直接把LC224的题解交上去下面给出针对这题的简易写法
class Solution {
public:stackint nums; // 操作数栈stackchar op; // 操作符栈unordered_mapchar, int pr {{(, 0}, {, 1}, {-, 1}, {*, 2}, {/, 2}};void eval() {int b nums.top(); nums.pop();int a nums.top(); nums.pop();char c op.top(); op.pop();if (c ) a b;else if (c -) a - b;else if (c *) a * b;else if (c /) a / b;nums.push(a);}int calculate(string str) {string s;for (auto c : str)if (c ! )s c;for (int i 0; i s.size(); i) {char c s[i];if (isdigit(c)) { // 数字int j i, x 0;// 题目数据保证答案是一个 32-bit 整数所以可以用x x * 10 (s[j ] - 0);while (j s.size() isdigit(s[j])) x x * 10 (s[j ] - 0);nums.push(x);i j - 1;} else { // 操作符 - * /while (!op.empty() pr[op.top()] pr[c]) eval();op.push(c); // 操作符入栈op}}while (!op.empty()) eval();return nums.top();}
};LC228 汇总区间
func summaryRanges(nums []int) []string {n : len(nums)ans : []string{}for i : 0; i n; i {j : i 1for j n nums[j] - nums[j - 1] 1 {j }if j - i 1 {ans append(ans, strconv.Itoa(nums[i]))} else {ans append(ans, strconv.Itoa(nums[i]) - strconv.Itoa(nums[j - 1]))}i j - 1}return ans
}LC229 多数元素II
func majorityElement(nums []int) []int {p1, p2, c1, c2, n : 0, 0, 0, 0, len(nums)for _, x : range nums {if c1 ! 0 p1 x {c1 } else if c2 ! 0 p2 x {c2 } else if c1 0 {p1 xc1 } else if c2 0 {p2 xc2 } else {c1 --c2 --}}c1, c2 0, 0for _, x : range nums {if x p1 {c1 } else if x p2 {c2 }}ans : []int{}if c1 n / 3 {ans append(ans, p1)}if c2 n / 3 {ans append(ans, p2)}return ans
}// 这里给出一种通用扩展解法给定一个大小为 n 的整数数组找出其中所有出现超过 ⌊ n/k ⌋ 次的元素。
class Solution {
public:vectorint nums, ans;int n;void solve(int k) {// 使用一个unordered_map来映射每个候选人及其计数。unordered_mapint, int mp; // key:候选人 value:该候选人的出现次数// 抵消阶段遍历数组更新或者抵消候选人的计数。for (auto x : nums) {if (mp.count(x)) { // 如果x已经是候选人则增加计数 mp[x];} else if (mp.size() k - 1) { // 如果x不是候选人但候选人名额未满则添加候选人mp[x] 1;} else { // 如果不是候选人且候选人名额已满则抵消所有候选人计数for (auto it mp.begin(); it ! mp.end(); ) {if (-- (it-second) 0) {it mp.erase(it);} else { it;}}}}// 计数阶段重新计算每个候选人的计数以验证是否满足超过n/k的条件。for (auto it : mp) {it.second 0; // 重置计数}for (auto x : nums) {if (mp.count(x)) { mp[x];}}// 收集结果返回满足条件的所有候选人。for (auto it : mp) {if (it.second n / k) {ans.push_back(it.first);}}}vectorint majorityElement(vectorint nums) {this-nums nums;this- n nums.size();solve(3);return ans;}
};LC230 二叉搜索树中第K小的元素
var k, ans intfunc dfs(root *TreeNode) {if root nil {return}dfs(root.Left)k --if k 0 {ans root.Valreturn }dfs(root.Right)
}func kthSmallest(root *TreeNode, _k int) int {k _kdfs(root)return ans
}LC231 2的幂
func isPowerOfTwo(n int) bool {// return n 0 (n (-n) n)return n 0 (n (n - 1) 0)
}LC232 用栈实现队列
type MyQueue struct {a, b []int
}func Constructor() MyQueue {return MyQueue{}
}func (this *MyQueue) solve() {for len(this.a) 0 {n : len(this.a)this.b append(this.b, this.a[n - 1])this.a this.a[ : n - 1]}
}func (this *MyQueue) Push(x int) {this.a append(this.a, x)
}func (this *MyQueue) Pop() int {if len(this.b) 0 {this.solve()}n : len(this.b)x : this.b[n - 1]this.b this.b[ : n - 1]return x
}func (this *MyQueue) Peek() int {if len(this.b) 0 {this.solve()}return this.b[len(this.b) - 1]
}func (this *MyQueue) Empty() bool {return len(this.a) 0 len(this.b) 0
}LC233 数字1的个数
class Solution {
public:int solve(int n) {string s to_string(n);int m s.size(), f[m][m];memset(f, -1 ,sizeof f);functionint(int, int, bool) dfs [](int i, int cnt, bool isLimit) - int {if (i m) return cnt;if (!isLimit ~f[i][cnt]) return f[i][cnt];int up isLimit ? s[i] - 0 : 9, ans 0;for (int d 0; d up; d) {ans dfs(i 1, cnt (d 1), isLimit d up);}if (!isLimit) f[i][cnt] ans;return ans;};return dfs(0, 0, true);}int countDigitOne(int n) {return solve(n);}
};LC234 回文链表
func isPalindrome(head *ListNode) bool {if head nil || head.Next nil {return true}ppre, pre, slow, fast : (*ListNode)(nil), head, head, headfor fast ! nil fast.Next ! nil {pre slowslow slow.Nextfast fast.Next.Nextpre.Next ppreppre pre}if fast ! nil {slow slow.Next}for pre ! nil slow ! nil {if pre.Val ! slow.Val {return false}pre, slow pre.Next, slow.Next}return true
}LC235 二叉搜索树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {ancestor : rootfor {if p.Val ancestor.Val q.Val ancestor.Val {ancestor ancestor.Left} else if p.Val ancestor.Val q.Val ancestor.Val {ancestor ancestor.Right} else {break}}return ancestor
}func getPath(root, target *TreeNode) []*TreeNode{path : []*TreeNode{}for root ! target {path append(path, root)if target.Val root.Val {root root.Left} else {root root.Right}}path append(path, target)return path
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {path_p, path_q : getPath(root, p), getPath(root, q)n : min(len(path_p), len(path_q))for i : n - 1; i 0; i -- {if path_p[i] path_q[i] {return path_p[i]}}return nil
}func dfs(root, target *TreeNode, path *[]*TreeNode) bool {if root nil {return false}*path append(*path, root)if root target {return true}if dfs(root.Left, target, path) || dfs(root.Right, target, path) {return true}*path (*path)[:len(*path) - 1]return false
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var path_p, path_q []*TreeNodedfs(root, p, path_p)dfs(root, q, path_q)n : min(len(path_p), len(path_q))for i : n - 1; i 0; i -- {if path_p[i] path_q[i] {return path_p[i]}}return nil
}func dfs(root, target *TreeNode, path *[]*TreeNode) bool {if root nil {return false}if root target {*path append(*path, target)return true}if dfs(root.Left, target, path) || dfs(root.Right, target, path) {*path append(*path, root)return true}return false
}func reverse(path []*TreeNode) {for i, j : 0, len(path) - 1; i j; i, j i 1, j - 1 {path[i], path[j] path[j], path[i]}
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var path_p, path_q []*TreeNodedfs(root, p, path_p)dfs(root, q, path_q)reverse(path_p)reverse(path_q)n : min(len(path_p), len(path_q))for i : n - 1; i 0; i -- {if path_p[i] path_q[i] {return path_p[i]}}return nil
}LC236 二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root nil || root p || root q {return root}left : lowestCommonAncestor(root.Left, p, q)right : lowestCommonAncestor(root.Right, p, q)if left nil {return right}if right nil {return left}return root
}func dfs(root, target *TreeNode, path *[]*TreeNode) bool {if root nil {return false}*path append(*path, root)if root target {return true}if dfs(root.Left, target, path) || dfs(root.Right, target, path) {return true}*path (*path)[:len(*path) - 1]return false
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var path_p, path_q []*TreeNodedfs(root, p, path_p)dfs(root, q, path_q)n : min(len(path_p), len(path_q))for i : n - 1; i 0; i -- {if path_p[i] path_q[i] {return path_p[i]}}return nil
}func dfs(root, target *TreeNode, path *[]*TreeNode) bool {if root nil {return false}if root target {*path append(*path, target)return true}if dfs(root.Left, target, path) || dfs(root.Right, target, path) {*path append(*path, root)return true}return false
}func reverse(path []*TreeNode) {for i, j : 0, len(path) - 1; i j; i, j i 1, j - 1 {path[i], path[j] path[j], path[i]}
}func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var path_p, path_q []*TreeNodedfs(root, p, path_p)dfs(root, q, path_q)reverse(path_p)reverse(path_q)n : min(len(path_p), len(path_q))for i : n - 1; i 0; i -- {if path_p[i] path_q[i] {return path_p[i]}}return nil
}LC237 删除链表中的节点
func deleteNode(node *ListNode) {node.Val node.Next.Valnode.Next node.Next.Next
}LC238 除自身以外数组的乘积
// 时间复杂度O(n) 空间复杂度O(n) 因为开了L,R这两个额外数组
func productExceptSelf(nums []int) []int {n : len(nums)L, R, ans : make([]int, n), make([]int, n), make([]int, n)L[0] 1for i : 1; i n; i {L[i] L[i - 1] * nums[i - 1]}R[n - 1] 1for i : n - 2; i 0; i -- {R[i] R[i 1] * nums[i 1]}for i : 0; i n; i {ans[i] L[i] * R[i]}return ans
}// 时间复杂度O(n) 空间复杂度O(1) 省去了L、R两个数组的空间
func productExceptSelf(nums []int) []int {n : len(nums)ans : make([]int, n)ans[0] 1for i : 1; i n; i {ans[i] ans[i - 1] * nums[i - 1]}R : 1for i : n - 1; i 0; i -- {ans[i] * RR * nums[i]}return ans
}LC239 滑动窗口最大值
func maxSlidingWindow(nums []int, k int) []int {n : len(nums)q : make([]int, n)ans : []int{}hh, tt : 0, -1for i : 0; i n; i {if hh tt q[hh] i - k 1 {hh }for hh tt nums[i] nums[q[tt]] {tt --}tt q[tt] iif i k - 1 {ans append(ans, nums[q[hh]])}}return ans
}LC240 搜索二维矩阵II
func searchMatrix(g [][]int, target int) bool {n, m : len(g), len(g[0])if n 0 || m 0 {return false}for i : 0; i n; i {l, r : 0, m - 1for l r {mid : (l r 1) 1if g[i][mid] target {l mid} else {r mid - 1}}if g[i][l] target {return true}}return false
}func searchMatrix(g [][]int, target int) bool {n, m : len(g), len(g[0])if n 0 || m 0 {return false}x, y : 0, m - 1for x n y 0 {if g[x][y] target {y --} else if g[x][y] target {x } else {return true}}return false
} LC241 为运算表达式设计优先级
var s stringfunc dfs(l, r int) []int {if l r {return []int{}}var ans []intisNum : truefor i : l; i r; i {if !unicode.IsDigit(rune(s[i])) {isNum falsebreak}}if isNum {num, _ : strconv.Atoi(s[l : r 1])ans append(ans, num)return ans}for i : l; i r; i {if s[i] || s[i] - || s[i] * {left : dfs(l, i - 1)right : dfs(i 1, r)for _, a : range left {for _, b : range right {x : 0if s[i] {x a b} else if s[i] - {x a - b} else if s[i] * {x a * b}ans append(ans, x)}}}}return ans
}func diffWaysToCompute(expression string) []int {s expressionreturn dfs(0, len(s) - 1)
}LC242 有效的字母异位词
func isAnagram(s, t string) bool {if len(s) ! len(t) {return false}mp : make(map[rune]int)for _, c : range s {mp[c] }for _, c : range t {mp[c] --if mp[c] 0 {return false}}return true
}LC257 二叉树的所有路径
var ans []stringfunc dfs(root *TreeNode, path string) {if root nil {return}path strconv.Itoa(root.Val)if root.Left nil root.Right nil {ans append(ans, path)return}if root.Left ! nil {dfs(root.Left, path -)}if root.Right ! nil {dfs(root.Right, path -)}
}func binaryTreePaths(root *TreeNode) []string {if root nil {return nil}ans []string{}dfs(root, )return ans
}LC258 各位相加
func addDigits(n int) int {if n 0 {return 0}if n % 9 ! 0 {return n % 9}return 9
}LC260 只出现一次的数字III
func singleNumber(nums []int) []int {sum : 0for _, x : range nums {sum ^ x}var pos intfor i : 0; i 32; i {if (sum i) 1 1 {pos ibreak}}s0, s1 : 0, 0for _, x : range nums {if (x pos) 1 1 {s1 ^ x} else {s0 ^ x}}return []int{s0, s1}
}LC263 丑数
func isUgly(n int) bool {if n 0 {return false}for n % 2 0 {n / 2}for n % 3 0 {n / 3}for n % 5 0 {n / 5}return n 1
}LC264 丑数II
func nthUglyNumber(n int) int {f : make([]int, n 1)f[1] 1p2, p3, p5 : 1, 1, 1for i : 2; i n; i {t : min(min(2 * f[p2], 3 * f[p3]), 5 * f[p5])f[i] tif t 2 * f[p2] {p2 }if t 3 * f[p3] {p3 }if t 5 * f[p5] {p5 }}return f[n]
}LC268 丢失的数字
func missingNumber(nums []int) int {ans, n : 0, len(nums)for _, x : range nums {ans ^ x}for i : 0; i n; i {ans ^ i}return ans
}class Solution {
public:int missingNumber(vectorint nums) {int s 0, n nums.size(), tot n * (n 1) / 2;for (auto x : nums) s x;return tot - s;}
};LC273 整数转换英文表示
class Solution {
public:string num0_19[20] {Zero, One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Eleven, Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen};string num20_90[10] {, , Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety};string num2str_large [4] {Billion, Million, Thousand, };string get(int x) { // 返回1~999的英文表示string ans ;if (x 100) {ans num0_19[x / 100] Hundred ;x % 100;}if (x 20) {ans num20_90[x / 10] ;x % 10;}if (x ! 0) ans num0_19[x] ;return ans;}string numberToWords(int num) {if (!num) return num0_19[0];string ans ;for (int i 1e9, j 0; i 1; i / 1000, j) {if (num i) {ans get(num / i) num2str_large [j] ;num % i;}}// 去掉末尾多余的空格while (ans.back() ) ans.pop_back();return ans;}
};LC274 H指数
// 时间复杂度O(nlogn) 空间复杂度O(1)
var c []intfunc check(h int) bool{cnt : 0for _, x : range c {if x h {cnt }if cnt h {return true}}return false
}func hIndex(citations []int) int {c citationsn : len(c)l, r : 0, nfor l r {mid : (l r 1) 1if check(mid) {l mid} else {r mid - 1}}return l
}// 时间复杂度O(n) 空间复杂度O(n)
func hIndex(c []int) int {tot, n : 0, len(c)cnt : make([]int, n 1)for i : 0; i n; i {if c[i] n {cnt[n] } else {cnt[c[i]] }}for i : n; i 0; i -- {tot cnt[i]if tot i {return i}}return 0
}LC275 H指数II
func hIndex(c []int) int {n : len(c)l, r : 0, nfor l r {mid : (l r 1) 1if c[n - mid] mid {l mid} else {r mid - 1}}return l
}LC278 第一个错误的版本
func firstBadVersion(n int) int {l, r : 1, nfor l r {mid : (l r) 1if isBadVersion(mid) {r mid} else {l mid 1}}return l
}LC279 完全平方数
func numSquares(m int) int {var v []intn : 0v append(v, 0)for i : 1; i int(math.Sqrt(float64(m))); i {v append(v, i * i)n}f : make([]int, m 1)for i : range f {f[i] 0x3f3f3f3f}f[0] 0for i : 1; i n; i {for j : v[i]; j m; j {f[j] min(f[j], f[j - v[i]] 1)}}return f[m]
}LC282 给表达式添加运算符
class Solution {
public:using LL long long;vectorstring ans;string path, s;void dfs(int u, int len, LL a, LL b, LL target) {if (u s.size()) {// 最后是 a 1 * () len减去1是因为要减掉我们在后面添加的号if (a target) ans.push_back(path.substr(0, len - 1));return;}LL c 0;for (int i u; i s.size(); i) {// 去掉前导0if (i u s[u] 0) break;c c * 10 s[i] - 0;path[len ] s[i];path[len] ;dfs(i 1, len 1, a b * c, 1, target);if (i 1 s.size()) {path[len] -;dfs(i 1, len 1, a b * c, -1, target);}if (i 1 s.size()) {path[len] *;dfs(i 1, len 1, a, b * c, target);}}}vectorstring addOperators(string num, int target) {this-s num;path.resize(100);dfs(0, 0, 0, 1, target);return ans;}
};LC283 移动零
func moveZeroes(nums []int) {k, n : 0, len(nums)for _, x : range nums {if x ! 0 {nums[k] xk }}for k n {nums[k] 0k }
}LC284 窥视迭代器
class PeekingIterator : public Iterator {
public:int cur;bool ok;PeekingIterator(const vectorint nums) : Iterator(nums) {ok Iterator::hasNext();if (ok) cur Iterator::next();}int peek() {return cur;}int next() {int t cur;ok Iterator::hasNext();if (ok) cur Iterator::next();return t;}bool hasNext() const {return ok;}
};LC287 寻找重复数
// 二分答案 时间复杂度O(nlogn) 空间复杂度O(1)
func findDuplicate(nums []int) int {l, r : 1, len(nums) - 1 // 二分答案区间[1, len(nums)-1]for l r {cnt, mid : 0, (l r) 1for _, x : range nums {if x l x mid {cnt }}if cnt mid - l 1 {r mid} else {l mid 1}}return l
}// 快慢指针 时间复杂度O(n) 空间复杂度O(1)
func findDuplicate(nums []int) int {slow, fast : 0, 0for {slow nums[slow]fast nums[nums[fast]]if slow fast {break}}slow 0for slow ! fast {slow nums[slow]fast nums[fast]}return slow
}LC289 生命游戏
func gameOfLife(g [][]int) {n, m : len(g), len(g[0])if n 0 || m 0 {return}dx : []int{-1, -1, -1, 0, 0, 1, 1, 1}dy : []int{-1, 0, 1, -1, 1, -1, 0, 1}for i : 0; i n; i {for j : 0; j m; j {cnt : 0for k : 0; k 8; k {a, b : i dx[k], j dy[k]if a 0 a n b 0 b m {if g[a][b] 1 1 {cnt }}}if g[i][j] 1 {if cnt 2 || cnt 3 {g[i][j] 1} else {g[i][j] 3}} else {if cnt 3 {g[i][j] 2} else {g[i][j] 0}}}}for i : 0; i n; i {for j : 0; j m; j {g[i][j] 1}}
}LC290 单词规律
class Solution {
public:bool wordPattern(string pattern, string s) {stringstream ss(s);vectorstring words;string w;while (ss w ) words.push_back(w);if (words.size() ! pattern.size() ) return false;unordered_mapchar, string PS;unordered_mapstring, char SP;for (int i 0; i words.size(); i) {char x pattern[i];string y words[i];if ((PS.count(x) PS[x] ! y) || (SP.count(y) SP[y] ! x)) return false;PS[x] y, SP[y] x;} return true;}
};LC292 Nim游戏
func canWinNim(n int) bool {return n 3 ! 0 // return n % 4 ! 0
}LC295 数据流的中位数
class MedianFinder {
public:priority_queueint a; // 大根堆priority_queueint, vectorint, greaterint b; // 小根堆MedianFinder() {}void addNum(int x) {if (a.empty() || x a.top()) {a.push(x);if (a.size() b.size() 1) {b.push(a.top());a.pop();}} else {b.push(x);if (b.size() a.size()) {a.push(b.top());b.pop();}}}double findMedian() {if ((a.size() b.size()) 1) return a.top();return (a.top() b.top()) / 2.0;}
};LC297 二叉树的序列化与反序列化
class Codec {
public:void dfs_s(TreeNode* root, string s) { // 序列化if (!root) {s #;return ;}s to_string(root-val) !;dfs_s(root-left, s);dfs_s(root-right, s);}// Encodes a tree to a single string.string serialize(TreeNode* root) {string s;dfs_s(root, s);return s;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if (data #) return nullptr;int i 0;return dfs_d(data, i);}TreeNode* dfs_d(string s, int i) { // 反序列化if (s[i] #) { i;return nullptr;}int k i;while (i s.size() s[i] ! !) i;auto root new TreeNode(stoi(s.substr(k, i - k)));if (i s.size()) return root;else i;root-left dfs_d(s, i);root-right dfs_d(s, i);return root;}};LC299 猜数字游戏
func getHint(secret string, guess string) string {mp : make(map[byte]int)tot : 0for _, c : range secret {mp[byte(c)] }for _, c : range guess {if mp[byte(c)] 0 {mp[byte(c)] --tot }}bulls : 0for i : 0; i len(secret); i {if secret[i] guess[i] {bulls }}return fmt.Sprintf(%dA%dB, bulls, tot - bulls)
}LC300 最长递增子序列
func lengthOfLIS(nums []int) int {d : []int{}for _, x : range nums {if len(d) 0 || x d[len(d) - 1] {d append(d, x)} else if x d[len(d) - 1] {continue} else {l, r : 0, len(d) - 1for l r {mid : (l r) 1if d[mid] x {r mid} else {l mid 1}}d[l] x}}return len(d)
}
