只有两个键的键盘

650. 只有两个键的键盘

难度中等357

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

  • Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
  • Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

示例 1：

1
2
3
4
5
6
7
输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。

示例 2：

1
2
输入：n = 1
输出：0

提示：

  • 1 <= n <= 1000

分解质因数

找到一个数字x如果当前的数字n能被x整除，那么需要复制几次x

例如：n = 8, x =2, 计算过程为：

n x ans
4 2 2
2 2 4
1 2 6 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minSteps(int n) {
        int ans = 0 ;
        for(int i=2;i<=n;i++){
            while(n%i==0){
                ans+=i;
                n/=i;
            }
        }   
        return ans;
    }
}

动态规划

设 $f[i]$ 表示打印出 $i $个 $\text{A}$ 的最少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSteps(int n) {
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; ++i) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; ++j) {
                if (i % j == 0) {
                    f[i] = Math.min(f[i], f[j] + i / j);
                    f[i] = Math.min(f[i], f[i / j] + j);
                }
            }
        }
        return f[n];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/2-keys-keyboard/solution/zhi-you-liang-ge-jian-de-jian-pan-by-lee-ussa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

寻找峰值

162. 寻找峰值

难度中等596

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

1
2
3
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

1
2
3
4
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

精炼的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1])
                // 这里是核心，如果找到一个值大于右边的值，那么不往左一个
                r = mid;
            else
                // 如果一个值大于右边的值
                l = mid + 1;
        }
        return l;
    }
}

笨方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0,r=n-1;
        if(n==1)return 0;
        if(n==2)return nums[0]<nums[1]?1:0;

        while(l<r){
            int m = l+(r-l)/2;
            int left = m-1;
            int right = m+1;
            if(left>=0&&right<n&&nums[m-1]<nums[m]&&nums[m]>nums[m+1]){
                return m;
            }else if(left>=0&&nums[m-1]<nums[m]){
                l = m+1;
            }else if(right<n&&nums[m]>nums[m+1]){
                r = m-1;
            }else{
                l++;
            }
        }
        return l;
    }
}

展开全文 >>

树洞202109

2021.09.03

所有的现状都是对过去现实的妥协

2021.09.15

论文初稿交上去了，活了，但还没有完全活，希望能找个合适的工作，要开始认真了小伙子，加油！！！！

2021.09.30

只要站起来的次数比倒下的次数多，就是胜利！狗子加油！！！

Imgur

展开全文 >>

跳跃游戏

55. 跳跃游戏

难度中等1349

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] <= 105

通过次数304,955

提交次数705,795

仔细读题：“数组中的每个元素代表你在该位置可以跳跃的最大长度。”也就是说可以跳到小于等于那个距离，不一定非要跳到那个距离。

解法一

动态规划

设f[i]表示能否跳跃到达位置i, 题目要求的是$f[n-1]$,初始条件，$f[0]=true;$
如果能到达位置$k$, 假设 $0<=a<=nums[k]$， 则$(k+a)$位置也能到达, 即$f[k+nums[k]] = true$，或，$f[i]=f[k] && (k+nums[k]>=i)$

时间复杂度$O(n^2)$，空间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n];
        f[0] = true;
		// 如果能到达位置k, 假设 0<=a<=nums[k]，
		// 则(k+a)位置也能到达, 即f[k+nums[k]] = true
        for (int i = 0; i < n; ++i) {
             if (f[i] == true) {
                 for (int j = 1; j <= nums[i]; ++j) {
                     if (i + j < n) {
                         f[i + j] = true;
                     }
                 }
             }
         }
        
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] f = new boolean[n];
        f[0] = true;
	    // f[i]=f[k] && (k+nums[k]>=i) 
        for (int i = 1; i < n; ++i) {
            f[i] = false;
            for (int j = 0; j < i; ++j) {
                if (f[j] && j + nums[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];
    }
}

解法二

贪心策略

如果能到达的最远位置等于或超过数组的最后一个位置,
则可以到达数组的最后一个位置。
初始化能跳到的最远位置为nums[0],
遍历数组，到达每个位置都判断当前位置能否到达，
并且计算从这个位置能跳到的最远位置，
判断这个最远位置是否比当前的最远位置更远，
若还能跳到更远，则更新可以跳到的最远位置。

时间复杂度O(n)，空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //贪心算法
    public static boolean canJump(int[] nums) {
        int maxDistance = nums[0];//maxDistance表示可以跳到的最远位置
        for (int i = 1; i < nums.length; i++) {
            if (i <= maxDistance) {
                //若i在能跳到的范围
                //判断从i能跳到的最远位置是否比当前的最远位置更远
                //若能跳到更远，则更新可以跳到的最远位置
                maxDistance = Math.max(maxDistance, nums[i] + i);
            } else {
                break;
            }

        }
        //最后能跳到的最远位置等于或超过数组的最后一个位置，则返回true，否则false
        return maxDistance >= nums.length;
    }
}

参考

Clibaba的题解

展开全文 >>

Command_Sequence

Command Sequence

\Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 792 Accepted Submission(s): 279
**

Problem Description

There is a robot that can move by receiving a sequence of commands.

There are four types of command in the command sequence:

  • U: robot moves one unit up.
  • D: robot moves one unit down.
  • L: robot moves one unit left.
  • R: robot moves one unit right.

Now, given a command sequence of length n. You need to find out how many substrings of the command sequence satisfy that if the robot execute the substring command, it can return to the starting position.

A substring is a contiguous sequence of characters within a string. For instance, “the best of” is a substring of “It was the best of times”. For example, “Itwastimes” is a subsequence of “It was the best of times”, but not a substring.

Input

This problem contains multiple test cases.

The first line contains an integer t (1≤t≤20) indicating the number of test cases.

For each test case, the first line contains one integer n (2≤n≤105).

The second line contains a UDLR string of length n.

Output

For each test case, output one line one integer indicating the answer.

Sample Input

1
2
3
1
6
URLLDR

Sample Output

1
2

Source

2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛

Recommend

IceyWang | We have carefully selected several similar problems for you: 7112 7111 7110 7109 7108

解题思路

如果以当前位置为起点，如果可以再次到达当前的位置那么就可以认为从当前位置可以回到当前的位置。

只需要记录从当前的位置到下次当前位置的数量即可知道子数组的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//
// Created by Vector on 2021/8/31.
//

#include <iostream>
#include <map>
# include <string>
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PAIR;

int main() {
    ll t;
    cin >> t;
    while (t--) {
        map<PAIR, ll> mp;
        mp[{0, 0}]++; // 起点(0, 0)也要记录
        ll n;
        string s;
        cin >> n >> s;

        ll res = 0, x = 0, y = 0; // 初始化坐标为(0, 0)
        for (ll i = 0; i < s.length(); i++) { // 遍历整条命令
            if (s[i] == 'U') x++;
            else if (s[i] == 'D') x--;
            else if (s[i] == 'L') y++;
            else if (s[i] == 'R') y--;
            res += mp[{x, y}]; // 累加当前位置(x, y)在前面出现的次数
            mp[{x, y}]++; // 记录当前位置
        }
        cout << res << '\n';
    }
    return 0;
}

展开全文 >>

航班预定统计

1109. 航班预订统计

难度中等166收藏分享切换为英文接收动态反馈

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

1
2
3
4
5
6
7
8
9
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

1
2
3
4
5
6
7
8
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

通过次数29,555

提交次数58,030

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

比如说，我给你输入一个数组 nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，再给…

这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：

1
2
3
4
5
6
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

1
2
3
4
5
6
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

这样构造差分数组 diff**，就可以快速进行区间增减的操作**，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：

参考文献：

小而美的算法技巧：差分数组 - labuladong 的算法小抄 (gitbook.io)

本题解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int len = bookings.length;

        int [] diff = new int [n+1];

        for(int []book:bookings){
            // 原本应该是   
            // diff[book[0]]+=book[2];
            // diff[book[1]+1]-=book[2];
            // 因为下标是从1开始的，所以每个减去1
            diff[book[0]-1]+=book[2];
            diff[book[1]]-=book[2];
        }
        
        int []res = new int [n];
        res[0] = diff[0];
        for(int i=1;i<n;i++){
            res[i] = res[i-1]+diff[i];
        } 
        return res;
    }
}

展开全文 >>

使用最小花费爬楼梯

746. 使用最小花费爬楼梯

难度简单628收藏分享切换为英文接收动态反馈

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

1
2
3
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2：

1
2
3
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

提示：

  • cost 的长度范围是 [2, 1000]。
  • cost[i] 将会是一个整型数据，范围为 [0, 999] 。

通过次数122,519

提交次数210,979

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int [] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];

        for (int i = 2; i < n; i++) {
            // 走一步和走两步的最小值加上当前的cost
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}

展开全文 >>

按权重随机选择

528. 按权重随机选择

难度中等143收藏分享切换为英文接收动态反馈

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

示例 1：

1
2
3
4
5
6
7
8
输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

提示：

  • 1 <= w.length <= 10000
  • 1 <= w[i] <= 10^5
  • pickIndex 将被调用不超过 10000 次

通过次数19,031

提交次数39,362

二分查找

利用了数字是正数，他们的和是单调递增的特性，来判断一个值落在哪里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    int[] pre;
    int total;
    
    public Solution(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        
        // 计算前缀和
        for (int i = 1; i < w.length; ++i) {
            pre[i] = pre[i - 1] + w[i];
        }
        
        //total = Arrays.stream(w).sum();
        // 二分查找的右边界
        total = pre[w.length-1];
    }
    
    public int pickIndex() {
        // 计算一个随机值，使用随机值乘以总和，就是其中的一部分和
        int x = (int) (Math.random() * total) + 1;
        // 查找这个随机值所在的区间
        return binarySearch(x);
    }

    private int binarySearch(int x) {
        int low = 0, high = pre.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
 
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/random-pick-with-weight/solution/an-quan-zhong-sui-ji-xuan-ze-by-leetcode-h13t/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

所有技术长度的子数组的和

1588. 所有奇数长度子数组的和

难度：简单

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：

1
2
3
输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例 3：

1
2
输入：arr = [10,11,12]
输出：66

提示：

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

通过次数29,833

提交次数36,014

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        int sum = 0;
        for (int start = 0; start < n; start++) {
            for (int length = 1; start + length <= n; length += 2) {
                int end = start + length - 1;
                sum += prefixSums[end + 1] - prefixSums[start];
            }
        }
        return sum;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/solution/suo-you-qi-shu-chang-du-zi-shu-zu-de-he-yoaqu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        
        int n = arr.length,ans = 0;
        for(int i = 0; i < n; ++i){
            int left = i+1, right = n-i-1;
            //左边为偶数 * 右边为奇数
            ans += (left/2)*((right+1)/2)*arr[i];
            //左边为奇数 * 右边为偶数
            ans += ((left+1)/2)*(right/2+1)*arr[i];
            //--------------------------^--------- 
            //尤其注意这个+1，他表示左边为奇数时不需要右边也能组成符合答案条件的数组
            //因此在图中我用了空数组来表示这种情况。看上图红色箭头部分
            //如果你不明白为什么第一种情况时不需要 +1, 那是因为第一种情况的右边数组不包含当前的数啊！
        }
        return ans;
    }
}

展开全文 >>

github的ssh登录

生成秘钥

使用命令生成秘钥：

1
ssh-keygen -t ed25519 -C "2523511898@qq.com"

一直enter到结束

复制秘钥的内容到github

1
C:\Users\xxx\.ssh

进入

1
https://github.com/settings/keys

new SSH key

复制 id_ed25519.pub文件中的内容到github的公钥框中

测试是否成功

1
ssh -T git@github.com

成功显示:

1
Hi XXX! You've successfully authenticated, but GitHub does not provide shell access.

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走