快手 获得最多的奖金
题目描述
小明在越南旅游，参加了当地的娱乐活动。小明运气很好，拿到了大奖， 到了最后的拿奖金环节。小明发现桌子上放着一列红包，每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀，将这一列红包“切”成3组，并且第一组的奖金之和等于最后一组奖金和（允许任意一组的红包集合是空）。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少，你能帮他算算吗。
举例解释：桌子上放了红包 1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀，将红包分成3组 [1, 2, 3, 4] [7] [10]，其中第一组奖金之和=第三组奖金之和=10，所以小明可以拿到10越南盾。
输入描述:
第一行包含一个正整数n，(1<=n<= 200 000)，表示有多少个红包。
第二行包含n个正整数d[i]，表示每个红包包含的奖金数额。其中1<= d[i] <= 1000 000 000
5
1 3 1 1 4
5
思路是先将红包求出 sum数组，依次求和，sum[i] = sum[n] - sum[j]
如果直接暴力O(n) 查找的话，时间超出，所以改为二分查找， 这里的二分一定要查出相等的值
其次，注意每一个红包 最大可以 1000 000 000 ，所有红包之和可能超出整数范围，所以采用long进行存储
import java.util.*;
public class Main {
// 思路先求缓存和，然后 sum[i] = sum[n] - sum[k] ,使用 max来保存最大值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
long[] sums = new long[n+1];
for(int i=0;i<n;i++){
nums[i] = in.nextInt();
sums[i+1] = sums[i] + nums[i];
}
long max = 0;
for(int i=1;i<n;i++){
/// 这里可以改为二分查找
long ans = sums[n] - sums[i];
int left = 0,right = i;
while (left <= right){
int mid = left + (right - left)/2;
if(sums[mid] == ans){
max = Math.max(max,ans);
break;
}else if(sums[mid] < ans){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
System.out.println(max);
}
}
快手 将满二叉树转换为求和树
给满出二叉树，编写算法将其转化为求和树
什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。
二叉树：
10
/
-2 6
/ \ / \
8 -4 7 5
求和树：
20(4-2+12+6)
/
4(8-4) 12(7+5)
/ \ / \
0 0 0 0
二叉树给出前序和中序输入，求和树要求中序输出；
所有处理数据不会大于int；
输入描述:
2行整数，第1行表示二叉树的前序遍历，第2行表示二叉树的中序遍历，以空格分割
输出描述:
1行整数，表示求和树的中序遍历，以空格分割
10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5
0 4 0 20 0 12 0
思路很简单就是代码比较多，但是题还是比较常规
首先通过先序和中序创建二叉树
然后通过后序在原树上求和
最后中序遍历输出
import java.util.*;
public class Main {
// 思路先通过前序遍历 和 中序遍历 创建二叉树，然后进行后序遍历
static class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
static List<Integer> res = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] preOrder = in.nextLine().split(" ");
String[] inOrder = in.nextLine().split(" ");
int[] preArray = new int[preOrder.length];
int[] inArray = new int[preOrder.length];
for (int i=0;i<preArray.length;i++){
preArray[i] = Integer.parseInt(preOrder[i]);
}
for (int i=0;i<preArray.length;i++){
inArray[i] = Integer.parseInt(inOrder[i]);
}
// 完成树的建立
TreeNode root = rebuildTree(preArray, inArray, 0, preArray.length - 1, 0, inArray.length - 1);
sumTree(root);
inOrder(root);
for (int i=0;i<res.size();i++){
if(i == res.size()-1){
System.out.print(res.get(i));
}else{
System.out.print(res.get(i) + " ");
}
}
}
private static void inOrder(TreeNode root) {
if (root == null){
return;
}
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}
private static int sumTree(TreeNode root) {
if(root == null){
return 0;
}
int left = sumTree(root.left);
int right = sumTree(root.right);
int res = root.val;
int lval = root.left == null?0:root.left.val;
int rval = root.right == null?0:root.right.val;
root.val = left + right + lval + rval;
return res;
}
private static TreeNode rebuildTree(int[] preArray, int[] inArray, int l1, int r1,int l2,int r2) {
if(r1 < l1 || r2 <l2){
return null;
}
int val = preArray[l1];
TreeNode root = new TreeNode(val);
int index = getIndex(inArray,val,l2,r2);
int leftLen = index - l2;
root.left = rebuildTree(preArray,inArray,l1+1,l1+leftLen,l2,index-1);
root.right = rebuildTree(preArray,inArray,l1+leftLen+1,r1,index+1,r2);
return root;
}
private static int getIndex(int[] inArray, int val, int l2, int r2) {
for (int i=l2;i<=r2;i++){
if (val == inArray[i]){
return i;
}
}
return -1;
}
}
本题当然可以另一个解法，就是满二叉树的话，只需中序遍历就可以确定整颗树
满二叉树是奇数个，中间节点就是树的根节点，所以不用创建树，直接操作数组即可
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
sc.nextLine();//满二叉树应该只需要中序遍历就可以确定唯一的树，所以不保存第一行输入
String zhong = sc.nextLine();
String[] split = zhong.split(" ");
int[] a = new int[split.length];//中序遍历保存到数组a中
for(int i=0;i<a.length;i++) {
a[i] = Integer.parseInt(split[i]);
}
int[] ans = new int[a.length];//保存中序遍历的输出结果
fun(a,0,a.length-1,ans);
for(int i:ans){
System.out.print(i+" ");
}
sc.close();
}
private static int fun(int[] a,int left,int right,int[] ans) {
int mid = (right+left)/2;//中间元素不参与这一轮的计算
if(right-left==2) {//出口条件
ans[mid] = a[right] + a[left];
ans[left] = 0;
ans[right] = 0;
return a[mid]+ans[mid];
}else {
ans[mid] = fun(a,left,mid-1,ans) + fun(a,mid+1,right,ans);
return a[mid]+ans[mid];
}
}
}
搭积木
小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000.
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。
输入描述:
第一行为积木的总个数 N
之后一共有N行，分别对应于每一个积木的宽W和长L
输出描述:
输出总共可以搭的层数
5
2 2
2 4
3 3
2 5
4 5
4
思路是最长递增子序列的解法，使用动态规划解法，时间复杂度太高，采用二分查找进行插入的解法，这题只是把最长递增子序列改为了二维，所以我们在插入时只插入其的索引数组
import java.util.*;
public class Main {
// 思路是先排序，然后解法依然类似与找零钱的dp,来进行求最大值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
List<int[]> list = new ArrayList<>();
for(int i=0;i<n;i++){
list.add(new int[]{in.nextInt(),in.nextInt()});
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]){
return o1[1] - o2[1];
}
return o1[0] - o2[0];
}
});
int max = 1;
int[] tmp = new int[n];
int end = 0;
// 这里可以使用二分法插入来加快时间复杂度
for (int i=0;i<n;i++){
int left = 0,right = end;
while (left < right){
int mid = left + (right - left)/2;
if (list.get(tmp[mid])[0] <= list.get(i)[0] && list.get(tmp[mid])[1] <= list.get(i)[1]){
left = mid + 1;
}else{
right = mid;
}
}
if(left == end){
end = end + 1;
}
tmp[left] = i;
}
System.out.println(end);
}
}
魔法深渊
前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。
由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。
已知深渊有N层台阶构成（1 <= N <= 1000)，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊
输入描述:
输入共有M行，(1<=M<=1000)
第一行输入一个数M表示有多少组测试数据，
接着有M行，每一行都输入一个N表示深渊的台阶数
输出描述:
输出可能的爬出深渊的方式
4
1
2
3
4
1
2
3
6
dp 生成1 到最大值 爬出方式的次数
import java.util.*;
public class Main {
// 思路是先排序，然后解法依然类似与找零钱的dp,来进行求最大值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
// 动态规划问题
int max = 0;
int[] nums = new int[m];
for (int i=0;i<m;i++){
nums[i] = in.nextInt();
max = Math.max(nums[i],max);
}
int len = (int)Math.sqrt(max);
int[] square = new int[len+1];
for(int i=0;i<=len;i++){
square[i] = (int) Math.pow(2,i);
}
int[] dp = new int[max+1];
dp[0] = 1;
for(int i=1;i<=max;i++){
int count = 0;
for (int j=0;j<square.length && square[j] <= i;j++){
count += dp[i-square[j]];
count = count % 1000_000_003;
}
dp[i] = count;
}
for (int i=0;i<nums.length;i++){
System.out.println(dp[nums[i]]);
}
}
}
网友评论