每日编程--leetcode127周竞赛
这次的题目真的是一点都不难,但由于本人太菜了,只做出三道
题目1:K 次取反后最大化的数组和
题目描述:
给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。
示例 1:
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。
示例 2:
输入:A = [3,-1,0,2], K = 3
输出:6
解释:选择索引 (1, 2, 2) ,然后 A 变为 [3,1,0,2]。
示例 3:
输入:A = [2,-3,-1,5,-4], K = 2
输出:13
解释:选择索引 (1, 4) ,然后 A 变为 [2,3,-1,5,4]。
分析:最简单的一道题了,其实就是k此遍历,每次找到最小值取反,最后求和
func largestSumAfterKNegations(A []int, K int) int {
if K!=0{
for i:=0;i<K;i++{
temp:=min(A)
A[temp] *=-1
}
}
return sum(A)
}
func min(A []int) int{
min:=A[0]
j:=0
for i,k:=range A{
if k<min{
min=k
j=i
}
}
return j
}
func sum(A []int) int{
sum:=0
for _,k:=range A{
sum+=k
}
return sum
}
题目2:行相等的最少多米诺旋转
题目描述:
1007. 行相等的最少多米诺旋转 显示英文描述
用户通过次数 203
用户尝试次数 238
通过次数 207
提交次数 517
题目难度 Medium
在一排多米诺骨牌中,A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。(一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。)
我们可以旋转第 i 张多米诺,使得 A[i] 和 B[i] 的值交换。
返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
如果无法做到,返回 -1.
示例 1:
输入:A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
输出:2
解释:
图一表示:在我们旋转之前, A 和 B 给出的多米诺牌。
如果我们旋转第二个和第四个多米诺骨牌,我们可以使上面一行中的每个值都等于 2,如图二所示。
示例 2:
输入:A = [3,5,1,2,3], B = [3,6,3,3,4]
输出:-1
解释:
在这种情况下,不可能旋转多米诺牌使一行的值相等。
分析:我用了最笨的方法,从1到6都进行检查,最后找出符合要求的最小值
代码:
func minDominoRotations(A []int, B []int) int {
flag:=0
n:=len(A)
count:=0
a_has:=make(map[int]int)
b_has:=make(map[int]int)
for i:=1;i<=6;i++{
for j:=0;j<n;j++{
if A[j]!=i && B[j]==i{
a_has[i]++
}else if A[j]!=i && B[j]!=i{
flag=1
break
}else{
count++
continue
}
}
if count==n{
return 0
}else{
count=0
}
if flag==1{
a_has[i]=-1
}
flag=0
}
for i:=1;i<=6;i++{
for j:=0;j<n;j++{
if B[j]!=i && A[j]==i{
b_has[i]++
}else if B[j]!=i && A[j]!=i{
flag=1
break
}else{
continue
}
}
if count==n{
return 0
}else{
count=0
}
if flag==1{
b_has[i]=-1
}
flag=0
}
min:=-1
for _,k:=range a_has{
if min==-1 && k!=-1{
min=k
}
if k!=-1 && k<min{
min=k
}
}
for _,k:=range b_has{
if min==-1 && k!=-1{
min=k
}
if k!=-1 && k<min{
min=k
}
}
return min
}
题目3:先序遍历构造二叉树
题目描述:
1008. 先序遍历构造二叉树 显示英文描述
用户通过次数 169
用户尝试次数 183
通过次数 171
提交次数 247
题目难度 Medium
返回与给定先序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。
(回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left 的任何后代,值总 < node.val,而 node.right 的任何后代,值总 > node.val。此外,先序遍历首先显示节点的值,然后遍历 node.left,接着遍历 node.right。)
示例:
输入:[8,5,1,7,10,12]
输出:[8,5,10,1,7,null,12]
分析:首先确定root,然后循环n-1次,从根节点开始遍历,先确定新节点的位置,然后插入节点
代码:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bstFromPreorder(preorder []int) *TreeNode {
n:=len(preorder)
if n==0{
return nil
}
root:=&TreeNode{
Val:preorder[0],
}
cur:=root
pa:=root
for i:=1;i<n;i++{
p:=&TreeNode{
Val:preorder[i],
}
cur=root
for cur!=nil{
pa=cur
if cur.Val>p.Val{
cur=cur.Left
}else{
cur=cur.Right
}
}
if pa.Val>p.Val{
pa.Left=p
}else{
pa.Right=p
}
}
return root
}
还有一道笨阶乘的题,没写出来,看到题就pass了