Tag Archives: 数学

剑指 Offer 17. 打印从1到最大的n位数

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明:

  • 用返回一个整数列表来代替打印
  • n 为正整数

简单解法如下:

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ans;
        int m = pow(10, n) - 1;
        for(int i = 1; i <= m; ++i) ans.push_back(i);
        return ans;
    }
};

本代码提交AC,用时12MS。

如果只是这么解的话,就太easy了。这题是要考察大数越界的问题,这就需要用到string来表示数字了,然后使用递归的方法求解,具体可以看题解: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/


本题是上一题(剑指 Offer 14- I. 剪绳子 LCOF)的升级版,即n的范围变大了,导致次方超过int和long long的范围,需要在求pow的过程中取mod。使用快速幂的方法,代码如下:

typedef long long LL;

class Solution {
private:
    LL FastPow(LL x, LL y) {
        LL ans = 1;
        while(y != 0) {
            if(y % 2 == 1) {
                ans = ans * x % 1000000007;
            }
            x = x * x % 1000000007;
            y >>= 1;
        }
        return ans % 1000000007;
    }
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int m = n / 3;
        if(n % 3 == 0) {
            return FastPow(3, m) % 1000000007;
        } else if(n % 3 == 1) {
            return (FastPow(3, m - 1) % 1000000007) * 4 % 1000000007;
        } else {
            return (FastPow(3, m) % 1000000007) * 2 % 1000000007;
        }
    }
};

本代码提交AC,用时0MS。

剑指 Offer 14- I. 剪绳子 LCOF

剑指 Offer 14- I. 剪绳子 LCOF

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示:

2 <= n <= 58
注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一根长为n的绳子,剪成m段,使得m段长度的乘积最大。问最大乘积是多少。

看题解,把长度切分为3,乘积最大。需要用到算术几何平均不等式,以及求导求极值等数学知识。

完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int m = n / 3;
        if(n % 3 == 0) {
            return pow(3, m);
        } else if(n % 3 == 1) {
            return pow(3, m - 1) * 4;
        } else {
            return pow(3, m) * 2;
        }
    }
};

本代码提交AC,用时0MS。

另一个通用解法是DP,假设dp[i]是长度为i,切分之后的最大乘积。则对于dp[j],可以把[1,…,j]切分为[1,…,k]和[k+1,…,j],因为切分之后两段的长度都小于j,所以之前已经求解过了,可直接得到乘积。题解如下: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/shu-xue-zhi-shi-he-dong-tai-gui-hua-liang-chong-fa/ 。完整代码如下:

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            for(int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
};

本代码提交AC,用时4MS。

LeetCode Last Moment Before All Ants Fall Out of a Plank

5453. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

  • 1 <= n <= 10^4
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • All values of left and right are unique, and each value can appear only in one of the two arrays.

很有意思的一个题。一块长木板上,放了若干只蚂蚁,有的蚂蚁向左走,有的蚂蚁向右走。当两个蚂蚁碰头时,会各自掉头走。问所有蚂蚁走出木板的时间。

有点像智力题,分析了半天,发现挺简单的。想象一下,如果蚂蚁A向右走,蚂蚁B向左走,它们在坐标0点碰头了,则A掉头向左走,B掉头向右走。对于A和B来说,虽然它们的方向变了,但是对于整个木板来说,并没有差别,依然是有一只蚂蚁从0点向右走,有一只蚂蚁从0点向左走。相当于A和B交换了身份,各自帮对方走了剩下的流程。但是从宏观分析看,A和B不管掉不掉头,效果是一样的。

综上所述,完全不用考虑碰头掉头的问题,直接对向左走和向右走的蚂蚁单独分析。对于向左走的蚂蚁,最右边的蚂蚁要走最长的时间。对于向右走的蚂蚁,最左边的蚂蚁要走最长的时间。总时间就是这两种情况的最大值。代码如下:

class Solution {
public:
	int getLastMoment(int n, vector<int>& left, vector<int>& right) {
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());
		int ans = 0;
		if (!left.empty())ans = max(ans, left.back());
		if (!right.empty())ans = max(ans, n - right.front());
		return ans;
	}
};

本代码提交AC。

LeetCode Number of Ways to Paint N × 3 Grid

5383. Number of Ways to Paint N × 3 Grid

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: RedYellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2
Output: 54

Example 3:

Input: n = 3
Output: 246

Example 4:

Input: n = 7
Output: 106494

Example 5:

Input: n = 5000
Output: 30228214

Constraints:

  • n == grid.length
  • grid[i].length == 3
  • 1 <= n <= 5000

给定3种颜色,要求涂满N*3的网格,且相邻网格的颜色不能一样,问有多少种涂法。

首先,如果只有一行的话。如果涂3种颜色,则因为3种颜色各不相同,所以有3种排列的方法,共3!=6种。如果涂2种颜色,则相同的颜色涂两边,不同的颜色涂中间,首先从3种颜色中选2种,为$C_3^2$,2种颜色决定哪个放中间有2种方法,所以也有6种涂法。

对于涂3种颜色的一行,其下一行可以涂2种颜色,有2种涂法;也可以涂3种颜色,也有2种涂法。

对于涂2种颜色的一行,其下一行可以涂2种颜色,有3种涂法;也可以涂3种颜色,有2种涂法。

综合上面两种情况,下一行是2种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*3,类似的,下一行是3种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*2。根据递推公式,最终的情况数是两者相加,代码如下:

class Solution {
public:

	int numOfWays(int n) {
		if (n == 1)return 12;
		long long pre_two_colors = 6, pre_three_colors = 6;
		long long mod = 1e9 + 7;
		for (int i = 2; i <= n; ++i) {
			long long next_two_colors = 3 * pre_two_colors + 2 * pre_three_colors;
			long long next_three_colors = 2 * pre_two_colors + 2 * pre_three_colors;
			pre_two_colors = next_two_colors % mod;
			pre_three_colors = next_three_colors % mod;
		}
		return (pre_two_colors + pre_three_colors) % mod;
	}
};

本代码提交AC,用时0MS。

参考:

LeetCode Four Divisors

1390. Four Divisors

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

  • 1 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^5

给定一个数组,问其中哪些数只有4个因子,把只有4个因子的数对应的所有因子加起来。

也是很无聊的一个题,按题意照做即可,注意求解因子的时候只需要循环到sqrt(v)即可,因为如果一个因子大于sqrt(v)的话,其对应的另一个因子肯定小于sqrt(v),也就是之前已经遍历过了。

完整代码如下:

class Solution {
public:
	void FindDivisors(int v, vector<int>& ans) {
		int mid = sqrt(v);
		for (int i = 1; i <= mid; ++i) {
			if (v%i == 0) {
				ans.push_back(i);
				if (v / i != i)ans.push_back(v / i);
			}
		}
	}
	int sumFourDivisors(vector<int>& nums) {
		int ans = 0;
		for (int i = 0; i < nums.size(); ++i) {
			vector<int> divs;
			FindDivisors(nums[i], divs);
			if (divs.size() == 4) {
				for (int j = 0; j < divs.size(); ++j)ans += divs[j];
			}
		}
		return ans;
	}
};

本代码提交AC,用时440MS。

LeetCode Closest Divisors

1362. Closest Divisors

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:

Input: num = 123
Output: [5,25]

Example 3:

Input: num = 999
Output: [40,25]

Constraints:

  • 1 <= num <= 10^9

给定一个数num,找出所有a*b等于num+1或num+2的(a,b)组合中,a和b的差最小的那个组合。

子问题就是给定一个数num,找出a*b==num的(a,b)组合中,a和b的差最小的组合。根据反证法,a和b必定有一个小于等于sqrt(num),另一个大于等于sqrt(num)。所以我最开始的做法是,用之前快速求sqrt的方法,计算sqrt(num),令left和right都等于sqrt(num),然后判断left*right的积,如果大于num,则–right;否则++left。这样虽然能得到正确结果,但提交后TLE。

百思不得其解,后来看别人的解答,才理解为什么我会TLE。我的解法设置了left和right两个指针,根据乘积的大小关系,left和right都在移动,在某些情况总的移动数会很大。而正确解法是,只设置一个移动指针i,i从sqrt(num)递减,然后判断num是否能整除i,如果能整除,则肯定找到一个因式分解。这种方法相当于我的方法中只移动了left,速度快了不少。在这种解法下,用不用快速sqrt都能AC。

完整代码如下:

class Solution {
public:
	int mySqrt(int x)
	{
		long long y = x;
		while (y*y > x)
		{
			y = (y + x / y) / 2;
		}
		return y;
	}

	vector<int> work(int num) {
		for (int i = mySqrt(num) + 1; i >= 1; --i) {
			if (num%i == 0) {
				return { i,num / i };
			}
		}
		return { 1,num };
	}
	vector<int> closestDivisors(int num) {
		vector<int> plus1 = work(num + 1);
		vector<int> plus2 = work(num + 2);
		if (abs(plus1[1] - plus1[0]) < abs(plus2[1] - plus2[0]))return plus1;
		else return plus2;
	}
};

hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在玩一个拼图游戏。如下图所示,整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标,你能找出缺失的那块小矩形的顶点坐标吗?

输入

第一行包含一个整数,N。 第二行包含四个整数,(X0, Y0), (X0, Y0),代表大矩形左下角和右上角的坐标。 以下N-1行每行包含四个整数,(Xi, Yi), (Xi, Yi),代表其中一个小矩形的左下角和右上角坐标。 对于30%的数据, 1 <= N <= 1000 对于100%的数据,1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X, Y)代表缺失的那块小矩形的左下角和右上角的坐标。
样例输入
5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5
样例输出
2 1 3 2

一个矩形由N个小矩形拼接而成,现在丢了一个小矩形,怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。 这一题也很有意思,丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数,如果出现偶数次,则这个点所在的矩形是出现过的,否则这个点就是缺失矩形的某个顶点。最后,从缺失的4个顶点中找出左下角坐标和右上角坐标。 完整代码如下: [cpp] #include<algorithm> #include<vector> #include<iostream> #include<unordered_map> #include<unordered_set> #include<string> #include<set> #include<map> #include<queue> using namespace std; typedef long long ll; typedef pair<int, int> Point; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); map<Point, int> hash; int a, b, c, d; while (n–) { Point left_bottom, right_top; scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second); Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second); ++hash[left_bottom]; ++hash[right_top]; ++hash[left_top]; ++hash[right_bottom]; } set<Point> ans; for (auto p : hash) { if (p.second % 2 == 1) { ans.insert(p.first); } } a = c = ans.begin()->first; b = d = ans.begin()->second; for (auto p : ans) { a = min(a, p.first); b = min(b, p.second); c = max(c, p.first); d = max(d, p.second); } printf("%d %d %d %d\n", a, b, c, d); return 0; } [/cpp] 本代码提交AC,用时432MS。]]>

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。 小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。 以下 T 行每行一个正整数N。 对于30%的数据,1 ≤ N ≤ 1000 对于80%的数据,1 ≤ N ≤ 100000 对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。
样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。 要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。 完整代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<unordered_set> #include<string> #include<unordered_map> #include<queue> using namespace std; typedef long long ll; ll t, n; int main() { freopen("input.txt", "r", stdin); scanf("%lld", &t); while (t–) { scanf("%lld", &n); if (n == 1 || n == 2) { printf("1\n"); } else { ll i = 1, j = 2; ll sum = i + j, ans = 0; while (true) { while (j <= n && sum < n) { ++j; sum += j; } if (j > n)break; while (i < j && sum > n) { sum -= i; ++i; } if (sum == n) { //printf("%d\n", j – i + 1); ans = max(ans, j – i + 1); break; } } printf("%lld\n", ans); } } return 0; } [/cpp] 无奈,提交后TLE,只过了80%的数据。 实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。 后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。 举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。 所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。 完整代码如下: [cpp] #include<iostream> #include<vector> #include<algorithm> #include<unordered_set> #include<string> #include<unordered_map> #include<queue> using namespace std; typedef long long ll; ll t, n; int main() { freopen("input.txt", "r", stdin); scanf("%lld", &t); while (t–) { scanf("%lld", &n); if (n == 1 || n == 2) { printf("1\n"); } else { ll ans = 1; for (ll i = 1; i < n; ++i) { ll sum = (1 + i)*i / 2; if (sum > n)break; ll left = sum – n; if (left%i == 0) { ans = max(ans, i); } } printf("%lld\n", ans); } } return 0; } [/cpp] 本代码提交AC,用时10MS。]]>

LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard Imagine you have a special keyboard with the following keys: Key 1: (A): Prints one ‘A’ on screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen. Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A
Example 2:
Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Note:
  1. 1 <= N <= 50
  2. Answers will be in the range of 32-bit signed integer.

给定四个按键,有四种操作:
  • A: 打印一个字符A
  • Ctrl-A: 全选
  • Ctrl-C: 复制
  • Ctrl-V: 粘贴
问通过n次按键操作,最多可以打印出多少个字符。 稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。 假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。 当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。 完整代码如下: [cpp] class Solution { public: int maxA(int N) { if (N <= 6)return N; vector<int> dp(N + 1, 0); for (int i = 1; i <= 6; ++i)dp[i] = i; for (int i = 7; i <= N; ++i) { for (int b = i – 3; b >= 1; –b) { dp[i] = max(dp[i], dp[b] + dp[b] * (i – b – 2)); } } return dp[N]; } }; [/cpp] 本代码提交AC,用时0MS。]]>