1
给你一根长度为 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
解：
由于将绳子 以相等的长度等分为多段 ，得到的乘积最大
可将问题转化为求 y = x 的极大值
易得驻点为
所以尽可能将绳子以长度 3 等分为多段时，乘积最大
切分规则：
最优： 3
次优： 2
最差： 1
2+2优于3+1 (2x2 > 3x1)
C++
class Solution {
public:int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
int a = n / 3;
int b = n % 3;
// ans * 3 可能在求余之前超出int32的值，所以用long类型
long ans = 1;
switch(b) {
case 0 :
for(int i = 0; i < a; i++) {
ans = ans * 3 % 1000000007 ;
}
break;
case 1 :
for(int i = 0; i < a - 1; i++) {
ans = ans * 3 % 1000000007 ;
}
ans = ans * 4 % 1000000007;
break;
case 2 :
for(int i = 0; i < a; i++) {
ans = ans * 3 % 1000000007 ;
}
ans = ans * 2 % 1000000007;
break;
}
return (int)ans;
}
};
python
# 由于语言特性，Python 可以不考虑大数越界问题
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3: return n - 1
a, b, p = n // 3, n % 3, 1000000007
if b == 0: return 3 ** a % p
if b == 1: return 3 ** (a - 1) * 4 % p
return 3 ** a * 2 % p
2
Method1
C++
class Solution {
public:
bool check(vector>& board, vector>& visited, int i, int j, string& s, int k) {
if (board[i][j] != s[k]) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
vector> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool result = false;
for (const auto& dir: directions) {
int newi = i + dir.first, newj = j + dir.second;
if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
if (!visited[newi][newj]) {
bool flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
bool exist(vector>& board, string word) {
int h = board.size(), w = board[0].size();
vector> visited(h, vector(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
bool flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
};
Python
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def check(i: int, j: int, k: int) -> bool:
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
visited.add((i, j))
result = False
for di, dj in directions:
newi, newj = i + di, j + dj
if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
if (newi, newj) not in visited:
if check(newi, newj, k + 1):
result = True
break
visited.remove((i, j))
return result
h, w = len(board), len(board[0])
visited = set()
for i in range(h):
for j in range(w):
if check(i, j, 0):
return True
return False
Method2
C++
class Solution {
public:
bool exist(vector>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector>& board, string word, int i, int j, int k) {
if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
if(k == word.size() - 1) return true;
board[i][j] = ' ';
bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
};
C++ 一看就懂版
class Solution {
public:
bool check(vector>& board, vector>& visited, int i, int j, string& s, int k) {
if (board[i][j] != s[k]) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
vector> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool result = false;
for (const auto& dir: directions) {
int newi = i + dir.first, newj = j + dir.second;
if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
if (!visited[newi][newj]) {
bool flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
bool exist(vector>& board, string word) {
int h = board.size(), w = board[0].size();
vector> visited(h, vector(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
bool flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
};
Python
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
if k == len(word) - 1: return True
board[i][j] = ''
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = word[k]
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0): return True
return False
3
C++
class Solution {
public:
int fib(int n) {
int MOD=1000000007;
if(n<2){
return n;
}
int p=0,q=0,r=1;
for(int i=2;i<=n;i++){
p=q;
q=r;
r=(p+q)%MOD;
}
return r;
}
};
Python
class Solution:
def fib(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n < 2:
return n
p, q, r = 0, 0, 1
for i in range(2, n + 1):
p = q
q = r
r = (p + q) % MOD
return r
4
C++
class Solution {
public:
int numWays(int n) {
vector jump;
jump.push_back(1);
jump.push_back(1);
for(int i=2;i<=n;i++){
jump.push_back((jump[i-1]+jump[i-2])%1000000007);
}
return jump[n];
}
};
C++ 一看就懂版
class Solution {
public:
int numWays(int n) {
int MOD=1000000007;
if(n==0||n==1){
return 1;
}
if(n==2){
return 2;
}
int p=1,q=1,r=2;
for(int i=2;i
Python
class Solution:
def numWays(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a % 1000000007
5
C++
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++)
dic[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector preorder;
unordered_map dic;
TreeNode* recur(int root, int left, int right) {
if(left > right) return nullptr; // 递归终止
TreeNode* node = new TreeNode(preorder[root]); // 建立根节点
int i = dic[preorder[root]]; // 划分根节点、左子树、右子树
node->left = recur(root + 1, left, i - 1); // 开启左子树递归
node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
};
C++ 一看就懂版
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder, int preorderL, int preorderR, int inorderL, int inorderR) {
printf("PL: %d, PR: %d, IL: %d, IR: %dn", preorderL, preorderR, inorderL, inorderR);
if (preorderR - preorderL == 0) {
return nullptr;
}
/
int root_val = preorder[preorderL];
TreeNode* tn = new TreeNode(root_val);
//
int offset = 0;
while(root_val != inorder[inorderL + offset]) {
offset++;
}
// cout << offset << endl;
//
tn->left = buildTree(preorder, inorder, preorderL + 1, preorderL + 1 + offset, inorderL, inorderL + offset);
tn->right = buildTree(preorder, inorder, preorderL + 1 + offset, preorderR, inorderL + offset + 1, inorderR);
return tn;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
return buildTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}
};
Python
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def recur(root, left, right):
if left > right: return # 递归终止
node = TreeNode(preorder[root]) # 建立根节点
i = dic[preorder[root]] # 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1) # 开启左子树递归
node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
return node # 回溯返回根节点
dic, preorder = {}, preorder
for i in range(len(inorder)):
dic[inorder[i]] = i
return recur(0, 0, len(inorder) - 1)
6
cpp
class Solution {
public:
string replaceSpace(string s) {
string a;
for(char& c : s){
if(c!=' '){
a.push_back(c);
}
else{
a.push_back('%');
a.push_back('2');
a.push_back('0');
}
}
return a;
}
};
python
class Solution:
def replaceSpace(self, s: str) -> str:
res = []
for c in s:
if c == ' ': res.append("%20")
else: res.append(c)
return "".join(res)
