// 新年第一题
// 新的一年立个 flag → leetcode contest rating 2600+，介于之前 rating 2300+，努努力可以实现。
// 扩展 atcoder or codeforces
func getRow(rowIndex int) []int {
row, idx := make([][]int, 2), 0
row[0], row[1] = make([]int, rowIndex+1), make([]int, rowIndex+1)
row[0][0] = 1
for i := 1; i <= rowIndex; i++ {
row[idx^1][0], row[idx^1][i] = 1, 1
for j := 1; j < i; j++ {
row[idx^1][j] = row[idx][j] + row[idx][j-1]
}
idx ^= 1
}
return row[idx]
}
难度简单579收藏分享切换为英文接收动态反馈
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
func findDisappearedNumbers(nums []int) []int {
tmp := make([]bool, len(nums))
for _, v := range nums {
tmp[v-1] = true
}
res := make([]int, 0)
for i, v := range tmp {
if !v {
res = append(res, i+1)
}
}
return res
}
/*
* @Description:
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-13 11:26:49
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-13 11:34:08
* @FilePath: /448findDisappearedNumbers/find_disappeared_numbers/src/lib.rs
*/
pub struct Solution;
impl Solution {
pub fn find_disappeared_numbers(nums: Vec<i32>) -> Vec<i32> {
let mut tmp = vec![false;nums.len()];
let mut res = Vec::new();
for v in nums{
tmp[v as usize -1]=true
}
for i in 0..tmp.len(){
if !tmp[i]{
res.push(i as i32 +1);
}
}
res
}
}
#[cfg(test)]
mod tests {
use crate::Solution;
#[test]
fn it_works() {
assert_eq!(Solution::find_disappeared_numbers(vec![4,3,2,7,8,2,3,1]),vec![5,6]);
}
}
/*
移形换影
把数组中的value放入到index为value-1的位置上
然后找出数组中index != nums[index]-1 的index+1
这种写法就有点像换座位，A换到B的座位，B暂时先搬到一个临时位置，然后B搬到C的位置，C搬到临时位置
*/
func findDisappearedNumbers2(nums []int) []int {
for i := range nums {
if i == nums[i]-1 {
continue
}
ch := nums[i]
nextID := ch - 1
//注意这里的终止条件 有可能回到i，也有可能在其他地方就提前遇到 nextID == nums[nextID]-1
for nextID != i && nextID != nums[nextID]-1 {
nums[nextID], ch = ch, nums[nextID]
nextID = ch - 1
}
nums[i] = ch
}
res := make([]int, 0)
for i, v := range nums {
if i != v-1 {
res = append(res, i+1)
}
}
return res
}
/*
参考了 DDY1024 https://talkgo.org/t/topic/1495/43 的写法 太漂亮了
这种写法就是 ，A要换到B的座位，A就和B互相换位置，这样A就换好了；然后B要搬到C的位置，B就和C换位置，B就换好了
A->B
B->C
C->A
原来的位置 |A|B|C|
然后A和B互换 |B|A|C|
然后B和C互换 |C|A|B|
*/
func findDisappearedNumbers(nums []int) []int {
i := 0
for i < len(nums) {
rightPos := nums[i] - 1 //表示nums[i]要放入的新位置
/*这里特别巧妙，
如果当前i已经是要放入的新位置，就原地不动; 也就是 rightPos == i
如果在rightPos上的value和 当前 nums[i] 相同，那么也没有必要再进行移动了
nums[rightPos] == nums[i] 直接就可以覆盖上面的两种情况
*/
if nums[rightPos] == nums[i] {
i++
} else {
nums[rightPos], nums[i] = nums[i], nums[rightPos]
//注意，这里i是要保持不变的
}
}
res := make([]int, 0)
for i, v := range nums {
if i != v-1 {
res = append(res, i+1)
}
}
return res
}
func findDisappearedNumbers(nums []int) []int {
n, i := len(nums), 0
for i < n {
if nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
continue
}
i++
}
ans := make([]int, 0)
for i := 0; i < n; i++ {
if nums[i] != i+1 {
ans = append(ans, i+1)
}
}
return ans
}
// 442
// 该归位的归位，剩下的单独再做判断
func findDuplicates(nums []int) []int {
n, i := len(nums), 0
for i < n {
if nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
continue
}
i++
}
ans := make([]int, 0)
for i := 0; i < n; i++ {
if nums[i] != i+1 && nums[nums[i]-1] == nums[i] {
ans = append(ans, nums[i])
}
}
return ans
}
// 并查集
func findSet(x int, parent []int) int {
if parent[x] < 0 {
return x
}
parent[x] = findSet(parent[x], parent)
return parent[x]
}
func unionSet(x, y int, parent []int) {
r1, r2 := findSet(x, parent), findSet(y, parent)
if r1 == r2 {
return
}
if parent[r1] < parent[r2] {
parent[r1] += parent[r2]
parent[r2] = r1
} else {
parent[r2] += parent[r1]
parent[r1] = r2
}
}
func minSwapsCouples(row []int) int {
n := len(row)
parent := make([]int, n/2)
for i := 0; i < n/2; i++ {
parent[i] = -1
}
for i := 0; i < n; i += 2 {
unionSet(row[i]/2, row[i^1]/2, parent)
}
ret := 0
for i := 0; i < n/2; i++ {
if parent[i] < 0 {
ret += -parent[i] - 1
}
}
return ret
}
这个写法好棒
// 2021.2.18
// 力扣
// 1. 对于当前位置为 0 果断反转
// 2. 对于当前位置为 1 反转两次没有任何意义
// 因此，原题目变成从左向右依次消除当前位置的 0 需要多少次？
// 目前，先采用 树状数组或线段树维护一次区间操作，提交后发现排名并不优，存在更优解法
// 1. 线段树
func minKBitFlips(A []int, K int) int {
n, ans := len(A), 0
add := make([]int, (n<<2)+10)
build(0, n-1, 1, add, A)
for i := 0; i < n; i++ {
ai := query(i, 0, n-1, 1, add)
if ai%2 == 0 && i + K - 1 < n {
ans++
update(i, i+K-1, 0, n-1, 1, 1, add)
}
}
ok := true
for i := 0; i < n; i++ {
if query(i, 0, n-1, 1, add) % 2 == 0 {
ok = false
break
}
}
if !ok {
return -1
}
return ans
}
func build(l, r, idx int, add []int, A []int) {
if l == r {
add[idx] = A[l]
return
}
mid := (l + r) >> 1
build(l, mid, idx<<1, add, A)
build(mid+1, r, (idx<<1)|1, add, A)
}
func push_down(idx int, add []int) {
if add[idx] > 0 {
add[idx<<1] += add[idx]
add[(idx<<1)|1] += add[idx]
add[idx] = 0
}
}
func query(p, l, r, idx int, add []int) int {
if l == r {
return add[idx]
}
push_down(idx, add)
mid := (l+r)>>1
if p <= mid {
return query(p, l, mid, idx<<1, add)
}
return query(p, mid+1, r, (idx<<1)|1, add)
}
func update(L, R, l, r, c, idx int, add []int) {
if L <= l && r <= R {
add[idx] += c
return
}
push_down(idx, add)
mid := (l + r) >> 1
if L <= mid {
update(L, R, l, mid, c, idx<<1, add)
}
if R > mid {
update(L, R, mid+1, r, c, (idx<<1)|1, add)
}
}
// 2. 树状数组
// 树状数组 + 差分数组性质搞搞即可
// 3. 更优解法
// 二分
func minKBitFlips(A []int, K int) int {
n, ans := len(A), 0
add := make([]int, 0, n)
var calcDelta = func(idx int) int {
return len(add) - sort.SearchInts(add, idx)
}
for i := 0; i < n; i++ {
A[i] += calcDelta(i)
if A[i]%2 == 0 && i+K-1 < n {
ans++
add = append(add, i+K-1)
A[i]++
}
}
ok := true
for i := 0; i < n; i++ {
if A[i]%2 == 0 {
ok = false
break
}
}
if !ok {
return -1
}
return ans
}
// 二分再优化下: 滑动窗口
func minKBitFlips(A []int, K int) int {
n, ans, ok := len(A), 0, true
add, curIdx := make([]int, 0, n), 0
for i := 0; i < n; i++ {
for curIdx < len(add) && add[curIdx] < i {
curIdx++
}
A[i] += len(add) - curIdx
if A[i]&1 == 0 && i+K-1 < n {
ans++
add = append(add, i+K-1)
A[i]++
}
if A[i]&1 == 0 {
ok = false
break
}
}
if !ok {
return -1
}
return ans
}
// 利用一个方法：给定一系列操作区间 [l, r]，求解经过一系列操作后，最终每个索引 idx 的最终值
// 维护一个增量数组 add，对于每次 [l,r] 操作 add[l]+=c, add[r]-=c，最终 add 数组前缀和即为位置 i
// 处的增量
// O(n) 解法
func minKBitFlips(A []int, K int) int {
n, ans, ok := len(A), 0, true
add := make([]int, n+1)
for i := 0; i < n; i++ {
if i-1 >= 0 {
add[i] += add[i-1]
}
A[i] += add[i]
if A[i]&1 == 0 && i+K-1 < n {
ans++
add[i]++
add[i+K]--
A[i]++
}
if A[i]&1 == 0 {
ok = false
break
}
}
if !ok {
return -1
}
return ans
}
// addPreSum[i], 从0到i 有多少个位置加过了
// sum(i-1- K+1+1 , i-1) 代表在i之前有哪些加过并且会影响到i
var addPreSum []int
func addSum(x, val int) {
if x == 0 {
addPreSum[x] = val
} else {
addPreSum[x] = addPreSum[x-1]+val
}
}
func getSum(i, j int) int{
if j<0 {return 0}
if i<=0 {
return addPreSum[j]
}
return addPreSum[j]-addPreSum[i-1]
}
func minKBitFlips(A []int, K int) int {
n, ans := len(A), 0
addPreSum = make([]int, n)
for i := 0; i < n-K+1; i++ {
A[i] += getSum(i-K+1, i-1)
if A[i]%2 == 0 {
ans++
A[i]++
addSum(i, 1)
}else {
addSum(i,0)
}
}
for i := n-K+1; i < n; i++ {
A[i] += getSum(i-K+1, i-1)
if A[i]%2 == 0 {
return -1
}
addSum(i,0)
}
return ans
}
// 2.19 每日一题
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func longestOnes(A []int, K int) int {
n, c0, sidx, ret := len(A), 0, 0, 0
for i := 0; i < n; i++ {
if A[i] == 0 {
c0++
}
for c0 > K && sidx <= i {
if A[sidx] == 0 {
c0--
}
sidx++
}
ret = maxInt(ret, i-sidx+1)
}
return ret
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func longestOnes(A []int, K int) int {
best := 0
for i, j:=0,0 ;i<len(A);i++ {
if A[i]==0 {K--}
for ;K<0;j++ {
if A[j]==0 {K++}
}
best = max(best, i-j+1)
}
return best
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func findShortestSubArray(nums []int) int {
n, maxC := len(nums), 0
cnt := make([]int, 50000)
for i := 0; i < n; i++ {
cnt[nums[i]]++
maxC = maxInt(maxC, cnt[nums[i]])
}
for i := 0; i < 50000; i++{
cnt[i] = 0
}
lidx, ret := 0, n
for i := 0; i < n; i++ {
cnt[nums[i]]++
if cnt[nums[i]] == maxC {
for lidx <= i && cnt[nums[i]] == maxC {
cnt[nums[lidx]]--
lidx++
}
ret = minInt(ret, i - lidx + 2)
}
}
return ret
}
难度简单240收藏分享切换为英文接收动态反馈
给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
type Value struct {
Beg, End int
Count int
}
func findShortestSubArray(nums []int) int {
if len(nums) <= 1 {
return len(nums)
}
m := make(map[int]Value, 0)
for i, n := range nums {
v, ok := m[n]
if !ok {
m[n] = Value{Beg: i, End: i, Count: 1}
continue
}
v.Count++
v.End = i
m[n] = v
}
res := Value{}
for _, v := range m {
if v.Count > res.Count {
res = v
} else if v.Count == res.Count && (v.End-v.Beg) < (res.End-res.Beg) {
res = v
}
}
return res.End - res.Beg + 1
}
//4ms 2.6MB
impl Solution {
pub fn find_shortest_sub_array(nums: Vec<i32>) -> i32 {
let mut num_map = std::collections::HashMap::new();
for i in 0..nums.len() {
let e = num_map.entry(&nums[i]).or_insert((i, i, 0));
e.1 = i; //记录最后一次出现的位置
e.2 += 1; //记录出现的个数
}
let mut res = (0, 0, 0);
for (_, v) in &num_map {
if v.2 > res.2 {
res = (v.0, v.1, v.2);
continue;
}
if (v.2 == res.2) && (v.1 - v.0) < (res.1 - res.0) {
res = (v.0, v.1, v.2);
}
}
(res.1 - res.0 + 1) as i32
}
}
// xxx
func gcd(x, y int) int {
if y == 0 {
return x
}
return gcd(y, x%y)
}
func getCoprimes(nums []int, edges [][]int) []int {
n, m := len(nums), len(edges)
adj := make([][]int, n)
for i := 0; i < m; i++ {
u, v := edges[i][0], edges[i][1]
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
gg := make([][]int, 51)
dp := make([]int, 51)
for i := 1; i <= 50; i++ {
dp[i] = -1
for j := 1; j <= 50; j++ {
if gcd(i, j) == 1 {
gg[i] = append(gg[i], j)
}
}
}
depth := make([]int, n)
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = -1
}
var dfs func(u, p int)
dfs = func(u, p int) {
for _, x := range gg[nums[u]] {
if dp[x] == -1 {
continue
}
if ans[u] == -1 {
ans[u] = dp[x]
} else if depth[dp[x]] > depth[ans[u]] {
ans[u] = dp[x]
}
}
tmp := dp[nums[u]]
dp[nums[u]] = u
for i := 0; i < len(adj[u]); i++ {
v := adj[u][i]
if v == p {
continue
}
depth[v] = depth[u] + 1
dfs(v, u)
}
dp[nums[u]] = tmp
}
dfs(0, -1)
return ans
}
//
// https://leetcode-cn.com/problems/maximum-score-from-performing-multiplication-operations/
//
/*
n == nums.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000
*/
// 1. 很容易想到一种解法是记忆化搜索 --> 每次选左边或右边
// 状态转移 dp(l, r, i) = max(dp(l+1, r, i+1), dp(l, r-1, i+1))
// 但是这样定义状态转移状态空间未 o(1000*1000*1000) 铁定是超时的，我们换种思路来考虑这个问题。
//
// 2. 由于 mul 长度最多未 1000，我们考虑在前 i 次操作中从左边的数选取了 j 个，则右边自然对应 i - j 个，
// 我们最终要求的答案是 m 次操作中左边选了 0, ..., m 次情况下的最大值是多少。
//
// 假设 dp[i][j] (0<=j<=i)，表示前 i 次操作中从左边选取了 j 个数的情况下的最大值。由于是依次拿取，因此这 j 次拿取操作
// 对应的便是 nums[0], ..., nums[j-1] 这些数；同理右边即 nums[n-i-j], ..., nums[n-1]
// 状态转移方程如下所示:
// 为了方便处理 i 下标从 1 开始
// dp[i][0] = dp[i-1][0] + nums[n-i] * mul[i-1]
// dp[i][i] = dp[i-1][i-1] + nums[i-1] * mul[i-1]
// dp[i][j] = max(
// dp[i-1][j]+ mul[i-1] * nums[n-i+j], // 从右边取总共 i-j 个，因此取 n-(i-j)
// dp[i-1][j-1] + mul[i-1] * nums[i-1] // 从左边取总共 i 个，因此取 i-1
// )
// ans = max(dp[m][0] ... dp[m][m])
//
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
// 这题没想到实属遗憾
func maximumScore(nums []int, multipliers []int) int {
n, m := len(nums), len(multipliers)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, m+1)
for j := i + 1; j <= m; j++ {
dp[i][j] = -0x3f3f3f3f3f3f3f3f
}
}
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] + multipliers[i-1]*nums[i-1]
dp[i][i] = dp[i-1][i-1] + multipliers[i-1]*nums[n-i]
for j := 1; j < i; j++ {
dp[i][j] = maxInt(dp[i-1][j-1]+nums[n-j]*multipliers[i-1], dp[i-1][j]+nums[i-j-1]*multipliers[i-1])
}
}
ans := -0x3f3f3f3f
for i := 0; i <= m; i++ {
ans = maxInt(ans, dp[m][i])
}
return ans
}
// https://leetcode-cn.com/problems/maximize-palindrome-length-from-subsequences/
// 首先我们需要知道一个结论，如何求解一个字符串的最长回文子序列，通过 O(n^2) 动态规划预处理求解
// dp(i, j) = dp(i+1, j-1) + 1 (s[i] == s[j])
// dp(i, j) = max(dp(i+1, j), dp(i, j-1)) (s[i] != s[j])
// 这样我们便预处理出 (i, j) 区间最长回文子序列了
// 由于最终要求解回文子序列需要两个原始字符串共同贡献，因此我们只需要枚举最终的回文子序列的左右端点在两个串中的哪个位置，然后通过
// 预处理结果直接 O(1) 求解最长回文子序列的长度即可。
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func longestPalindrome(word1 string, word2 string) int {
n1, n2 := len(word1), len(word2)
dp := make([][]int, n1+n2)
for i := 0; i < n1+n2; i++ {
dp[i] = make([]int, n1+n2)
}
word := make([]byte, 0, n1+n2)
word = append(word, []byte(word1)...)
word = append(word, []byte(word2)...)
n := n1 + n2
for i := 0; i < n; i++ {
dp[i][i] = 1
}
for l := 2; l <= n; l++ {
for i := 0; i+l-1 < n; i++ {
j := i + l - 1
if word[i] == word[j] {
if i == j {
dp[i][j] = dp[i+1][j-1] + 1
} else {
dp[i][j] = dp[i+1][j-1] + 2
}
} else {
dp[i][j] = maxInt(dp[i+1][j], dp[i][j-1])
}
}
}
ans := 0
for i := 0; i < n1; i++ {
for j := 0; j < n2; j++ {
if word1[i] == word2[j] {
ans = maxInt(ans, dp[i][n1+j])
}
}
}
return ans
}
难度中等155收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
func longestSubarray(nums []int, limit int) int {
if len(nums) == 0 {
return 0
}
moreThanNums := []int{nums[0]} //
lessThanNums := []int{nums[0]}
beg := 0
end := 0
res := 1
for end < len(nums) && beg <= end {
if abs(moreThanNums[0]-lessThanNums[0]) <= limit {
if end-beg+1 > res {
res = end - beg + 1
}
end++
if end == len(nums) {
break
}
for len(moreThanNums) > 0 && moreThanNums[len(moreThanNums)-1] < nums[end] {
moreThanNums = moreThanNums[0 : len(moreThanNums)-1]
}
moreThanNums = append(moreThanNums, nums[end])
for len(lessThanNums) > 0 && lessThanNums[len(lessThanNums)-1] > nums[end] {
lessThanNums = lessThanNums[0 : len(lessThanNums)-1]
}
lessThanNums = append(lessThanNums, nums[end])
} else {
if nums[beg] >= moreThanNums[0] {
moreThanNums = moreThanNums[1:]
}
if nums[beg] <= lessThanNums[0] {
lessThanNums = lessThanNums[1:]
}
beg++
}
}
return res
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
/*
* @Description:
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-22 09:16:09
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-22 09:45:25
* @FilePath: \1438longestSubarray\longest_subarray\src\lib.rs
*/
pub struct Solution;
impl Solution {
//376 ms 3.7MB
pub fn longest_subarray_slow(nums: Vec<i32>, limit: i32) -> i32 {
if nums.len() <= 1 {
return nums.len() as i32;
}
let mut res = 1;
//双指针滑窗
let mut beg = 0;
let mut end = 0;
let mut monoMax = vec![nums[0]]; //维护窗口中的最大值，因为从左边移除元素，所以最大值在最左边
let mut monoMin = vec![nums[0]]; //维护窗口中的最小值，因为从左边移除元素，所以最小值在最左边
while end < nums.len() && beg <= end {
//窗口中最大值 最小值之差满足条件
if (monoMax[0] - monoMin[0]) <= limit {
if end - beg + 1 > res {
res = end - beg + 1
}
end += 1;
if end == nums.len() {
return res as i32;
}
//更新 monoMax，最大值要在最左边
while let Some(e) = monoMax.last() {
if *e >= nums[end] {
break;
}
monoMax.pop();
}
monoMax.push(nums[end]);
//更新 monoMin，最小值要在最左边
while let Some(e) = monoMin.last() {
if *e <= nums[end] {
break;
}
monoMin.pop();
}
monoMin.push(nums[end]);
} else {
//移除 beg
if nums[beg] >= monoMax[0] {
monoMax.remove(0);
}
if nums[beg] <= monoMin[0] {
monoMin.remove(0);
}
beg += 1;
}
}
res as i32
}
pub fn longest_subarray(nums: Vec<i32>, limit: i32) -> i32 {
if nums.len() <= 1 {
return nums.len() as i32;
}
let mut res = 1;
//双指针滑窗
let mut beg = 0;
let mut end = 0;
let mut monoMax = std::collections::VecDeque::new(); //维护窗口中的最大值，因为从左边移除元素，所以最大值在最左边
monoMax.push_back(nums[0]);
let mut monoMin = std::collections::VecDeque::new(); //维护窗口中的最小值，因为从左边移除元素，所以最小值在最左边
monoMin.push_back(nums[0]);
while end < nums.len() && beg <= end {
//窗口中最大值 最小值之差满足条件
if (monoMax[0] - monoMin[0]) <= limit {
if end - beg + 1 > res {
res = end - beg + 1
}
end += 1;
if end == nums.len() {
return res as i32;
}
//更新 monoMax，最大值要在最左边
while let Some(e) = monoMax.back(){
if *e >= nums[end] {
break;
}
monoMax.pop_back();
}
monoMax.push_back(nums[end]);
//更新 monoMin，最小值要在最左边
while let Some(e) = monoMin.back() {
if *e <= nums[end] {
break;
}
monoMin.pop_back();
}
monoMin.push_back(nums[end]);
} else {
//移除 beg
if nums[beg] >= monoMax[0] {
monoMax.pop_front();
}
if nums[beg] <= monoMin[0] {
monoMin.pop_front();
}
beg += 1;
}
}
res as i32
}
}
#[cfg(test)]
mod tests {
use crate::Solution;
#[test]
fn it_works_slow() {
assert_eq!(Solution::longest_subarray_slow(vec![8, 2, 4, 7], 4), 2);
assert_eq!(Solution::longest_subarray_slow(vec![10, 1, 2, 4, 7, 2], 5), 4);
assert_eq!(
Solution::longest_subarray_slow(vec![4, 2, 2, 2, 4, 4, 2, 2], 0),
3
);
}
fn it_works() {
assert_eq!(Solution::longest_subarray(vec![8, 2, 4, 7], 4), 2);
assert_eq!(Solution::longest_subarray(vec![10, 1, 2, 4, 7, 2], 5), 4);
assert_eq!(
Solution::longest_subarray(vec![4, 2, 2, 2, 4, 4, 2, 2], 0),
3
);
}
}
// 2021.02.22
func isToeplitzMatrix(matrix [][]int) bool {
n, m := len(matrix), len(matrix[0])
for i := 0; i < m; i++ {
x, y, val := 0, i, matrix[0][i]
for x < n && y < m {
if matrix[x][y] != val {
return false
}
x++
y++
}
}
for i := 0; i < n; i++ {
x, y, val := i, 0, matrix[i][0]
for x < n && y < m {
if matrix[x][y] != val {
return false
}
x++
y++
}
}
return true
}
难度简单172收藏分享切换为英文接收动态反馈
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
/*
* @Description: 766
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-22 09:53:17
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-22 10:05:53
* @FilePath: \766isToeplitzMatrix\766.go
*/
package leetcode
func isToeplitzMatrix(matrix [][]int) bool {
if len(matrix) <= 1 {
return true
}
if len(matrix[0]) == 1 {
return true
}
for rowID := 0; rowID < len(matrix); rowID++ {
x := rowID
y := 0
for x < len(matrix) && y < len(matrix[0]) {
if matrix[x][y] != matrix[rowID][0] {
return false
}
x++
y++
}
}
for colID := 1; colID < len(matrix[0]); colID++ {
x := 0
y := colID
for x < len(matrix) && y < len(matrix[0]) {
if matrix[x][y] != matrix[0][colID] {
return false
}
x++
y++
}
}
return true
}
难度中等74收藏分享切换为英文接收动态反馈
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
/*
* @Description: 1052
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-23 09:04:46
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-23 09:30:57
* @FilePath: \1052maxSatisfied\1052.go
*/
package leetcode
/*
- 计算不考虑X时候所能得到的满意
- 滑动窗口 计算这个区间所能得到额外满意度
*/
func maxSatisfied(customers []int, grumpy []int, X int) int {
//不考虑X的满意度
totalSum := 0
for i := range customers {
if grumpy[i] == 0 { //没有生气
totalSum += customers[i]
}
}
resDelta := 0
tmp := 0
for i := 0; i < X; i++ {
if grumpy[i] == 1 { //这个时刻本来是生气，变为了不生气
tmp += customers[i]
}
}
resDelta = tmp
for i := X; i < len(customers); i++ {
if grumpy[i] == 1 { //这个时刻本来是生气，变为了不生气
tmp += customers[i]
}
if grumpy[i-X] == 1 {
tmp -= customers[i-X]
}
if tmp > resDelta {
resDelta = tmp
}
}
return resDelta + totalSum
}
impl Solution {
pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, x: i32) -> i32 {
let x = x as usize;
let total_sum = customers
.iter()
.zip(grumpy.iter())
.fold(0, |acc, x| acc + x.0 * (1 - x.1));
//满意提升度
let mut tmp = customers
.iter()
.zip(grumpy.iter())
.take(x)
.fold(0, |acc, x| acc + x.0 * x.1);
let mut max_delta = tmp;
for i in x..customers.len(){
if grumpy[i]==1{
tmp+=customers[i];
}
if grumpy[i-x]==1{
tmp-=customers[i-x];
}
if tmp>max_delta{
max_delta = tmp;
}
}
total_sum+max_delta
}
}
// 2021.02.23
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func maxSatisfied(customers []int, grumpy []int, X int) int {
n, ans := len(customers), 0
c0 := 0
for i := 0; i < n; i++ {
if grumpy[i] == 0 {
c0 += customers[i]
}
}
pc := 0
for i := 0; i < X; i++ {
pc += customers[i]
if grumpy[i] == 0 {
c0 -= customers[i]
}
}
ans = maxInt(ans, c0+pc)
for i := X; i < n; i++ {
pc += customers[i]
pc -= customers[i-X]
if grumpy[i] == 0 {
c0 -= customers[i]
}
if grumpy[i-X] == 0 {
c0 += customers[i-X]
}
ans = maxInt(ans, c0+pc)
}
return ans
}
难度简单210收藏分享切换为英文接收动态反馈
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
/*
* @Description: 832
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-02-24 09:07:07
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-02-24 09:24:00
* @FilePath: \832flipAndInvertImage\832.go
*/
package leetcode
func flipAndInvertImage(A [][]int) [][]int {
if len(A) == 0 {
return A
}
cols := len(A[0])
for i := 0; i < len(A); i++ {
for beg, end := 0, cols-1; beg <= end; beg, end = beg+1, end-1 {
if beg != end {
A[i][beg], A[i][end] = A[i][end], A[i][beg]
A[i][beg] ^= 1
}
A[i][end] ^= 1
}
}
return A
}