✅ 412. Fizz Buzz
https://leetcode-cn.com/problems/fizz-buzz
描述
写一个程序，输出从 1 到 n 数字的字符串表示。
1. 如果 n 是3的倍数，输出“Fizz”；
2. 如果 n 是5的倍数，输出“Buzz”；
3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
示例：
n = 15,
返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fizz-buzz
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
按照题意直接 for + if 吧
c数字转字符：
itoa
int num = 100;
char str[25];
itoa(num, str, 10);
printf("The number 'num' is %d and the string 'str' is %s.
" ,
num, str);
sprintf
int num = 100;
char str[25];
sprintf(str, " %d" , num);
printf ("The number 'num' is %d and the string 'str' is %s.
" ,
num, str);
other's c
char ** fizzBuzz(int n, int* returnSize){
*returnSize=n;
char **ans=(char**)malloc(n*sizeof(char*));
int i,temp,count;
for(i=0;i<n;i++)
{
if((i+1)%3==0)
{
if((i+1)%5==0)
{
ans[i]=(char*)malloc(9*sizeof(char));
ans[i]="FizzBuzz";
}
else
{
ans[i]=(char*)malloc(5*sizeof(char));
ans[i]="Fizz";
}
}
else if((i+1)%5==0)
{
ans[i]=(char*)malloc(5*sizeof(char));
ans[i]="Buzz";
}
else
{
count=0;
temp=i+1;
while(temp)
{
count++;
temp/=10;
}
ans[i]=(char*)malloc((count+1)*sizeof(char));
ans[i][count]=' ';
count--;
temp=i+1;
while(temp)
{
ans[i][count]=temp%10+'0';
temp/=10;
count--;
}
}
}
return ans;
}
my c tdo
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char ** fizzBuzz(int n, int* returnSize){
char **my_vec;
my_vec = (char **) malloc (sizeof(char *) * n);
//tt3 line
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 == 0) {
my_vec[i-1]= "FizzBuzz";
} else if (i % 3 == 0) {
my_vec[i-1]= "Fizz";
} else if (i % 5 == 0) {
my_vec[i-1]= "Buzz";
} else {
char *tmp = (char *) malloc (sizeof(char *));//tt dont declare `tmp` at tt3 line
sprintf(tmp, "%d", i);//tt rev sprintf; good helper
my_vec[i-1] = tmp;
}
}
*returnSize = n;
return my_vec;
}
/*执行用时 :
8 ms
, 在所有 C 提交中击败了
88.31%
的用户
内存消耗 :
8.2 MB
, 在所有 C 提交中击败了
77.50%
的用户*/
py
class Solution:
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
for i in range(1,n+1):
res.append('Fizz'[i%3*len('Fizz')::]+'Buzz'[i%5*len('Buzz')::] or str(i))# todo 奇技淫巧 【：：】
return res
✅ 235. 二叉搜索树的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答
一次 dfs 中 找到 p 和 q
找到 谁 比如，q的时候，就把当然dfs经历中的 路径上的 点， 都放在一个 数组a中
找到 p 的时候，就把 path 上的node ，放在 一个数组 b 中
看 a b 某个点之后的node 不一致 了，那么这个 ： 某个点， 就是 公共祖先
评价者 思路：
使用BST 的搜索 特性
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode *re = NULL;
while(root)
{
if(root->val > p->val&&root->val > q->val)
root = root->left;
else if(root->val < p->val&&root->val < q->val)
root = root->right;
else
{
re = root;
break;
}
}
return re;
}
c
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode *re;
while(root) {
if (root->val > q->val && root->val > p->val) {
root = root-> left;
}
else if (root->val < q->val && root->val < p->val) {
root = root->right;
} else {
re = root;
break;
}
}
return re;
}
/*执行用时 :
52 ms
, 在所有 C 提交中击败了
36.92%
的用户
内存消耗 :
30.2 MB
, 在所有 C 提交中击败了
83.07%
的用户*/
py
使用了自己的dfs 思路, failed todo
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
print(p.val)
print(q.val)
print("----")
q_path = []
p_path = []
# each param must not null
def dfs(root: 'TreeNode', backArr: List[TreeNode]):
if root is None:
return
backArr.append(root)
if root.val == q.val:
# now we find q node
q_path = backArr[:]
print(">>>",q_path)
# return as we finished
return
if root.val == p.val:
p_path = backArr.copy()
# return as we finished
return
# otherwise, we conti dfs
if root.left:
dfs(root.left, backArr)
if root.right:
dfs(root.right, backArr)
dfs(root, [])
# as we got p_path and q_path
# we can now compare them
print(q_path)
print(p_path)
for i in range(0, min(len(q_path), len(p_path))):
if q_path[i].val == p_path[i].val:
continue
else: # q_path[i] != p_path[i]
return q_path[i - 1].val
'''
执行用时: 32 ms
输入
[6,2,8,0,4,7,9,null,null,3,5]
2
8
输出
null
预期结果
6
stdout
2
8
----
>>> [TreeNode{val: 6, left: TreeNode{val: 2, left: TreeNode{val: 0, left: None, right: None}, right: TreeNode{val: 4, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 5, left: None, right: None}}}, right: TreeNode{val: 8, left: TreeNode{val: 7, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}}, TreeNode{val: 2, left: TreeNode{val: 0, left: None, right: None}, right: TreeNode{val: 4, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 5, left: None, right: None}}}, TreeNode{val: 8, left: TreeNode{val: 7, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}]
[]
[]
'''