UDN-企业互联网技术人气社区

板块导航

浏览  : 4079
回复  : 42

[社区公告] 邀你来战【UDN算法挑战】 现金红包等你来拿

[复制链接]
发表于 2015-12-17 10:52:47 | 显示全部楼层
public void sort2(int[] arr){
          int tmp=0;
           for (int i=0; i!=arr.length;i++){
while (arr[i]!=i+1){
          tmp=arr[arr[i]-1=arr[i];
           arr[i]=tmp;
}
}
}


Public int getNeeNum(int[] arr,int lim){
     int res = 1;
     int stepSum = 0;
     for (int i= 0; i !=arr.length; i++) {
      if (arr[i]>lim) {
           return Integer.MAX_VALUE;
      }
      stepSum +=arr[i];
      }
 }
 Return res;
}
public int solution3(int[] arr,int num){
      if (arr == null || arr.length ==0 || num <1) {
           throw new RuntimeException(“err”);
      }
      If (arr.length < num) {
           Int max = Integer.MIN_VALUE;
           For (int I =0; i != arr .length; i++) {
                 maxSum += arr[i];
           }
          Return max;
} else {
     Int minSum = 0;
     Int maxsum =0;
     For (int I = 0; i< arr.length; i++) {
           maxSum += arr[i];
     }
     While (minsum !=maxSum – 1 ) {
           Int mid = (minSum + maxsum) / 2;
           If (getNeedNum(arr, mid ) > num) {
                minSum = mid;
           } else {
                maxSum = mid;
           }
      }
     Return maxSum;
}
}
使用道具 举报

回复

发表于 2015-12-17 10:53:39 | 显示全部楼层
Public int getNeeNum(int[] arr,int lim){
     int res = 1;
     int stepSum = 0;
     for (int i= 0; i !=arr.length; i++) {
      if (arr[i]>lim) {
           return Integer.MAX_VALUE;
      }
      stepSum +=arr[i];
      }
 }
 Return res;
}
public int solution3(int[] arr,int num){
      if (arr == null || arr.length ==0 || num <1) {
           throw new RuntimeException(“err”);
      }
      If (arr.length < num) {
           Int max = Integer.MIN_VALUE;
           For (int I =0; i != arr .length; i++) {
                 maxSum += arr[i];
           }
          Return max;
} else {
     Int minSum = 0;
     Int maxsum =0;
     For (int I = 0; i< arr.length; i++) {
           maxSum += arr[i];
     }
     While (minsum !=maxSum – 1 ) {
           Int mid = (minSum + maxsum) / 2;
           If (getNeedNum(arr, mid ) > num) {
                minSum = mid;
           } else {
                maxSum = mid;
           }
      }
     Return maxSum;
}
}
使用道具 举报

回复

发表于 2015-12-17 11:17:35 | 显示全部楼层
第一题:public void sort2(int[] arr){
          int tmp=0;
           for (int i=0; i!=arr.length;i++){
while (arr[i]!=i+1){
          tmp=arr[arr[i]-1=arr[i];
           arr[i]=tmp;
}
}
}


第二题:Public int getNeeNum(int[] arr,int lim){
     int res = 1;
     int stepSum = 0;
     for (int i= 0; i !=arr.length; i++) {
      if (arr[i]>lim) {
           return Integer.MAX_VALUE;
      }
      stepSum +=arr[i];
      }
}
Return res;
}
public int solution3(int[] arr,int num){
      if (arr == null || arr.length ==0 || num <1) {
           throw new RuntimeException(“err”);
      }
      If (arr.length < num) {
           Int max = Integer.MIN_VALUE;
           For (int I =0; i != arr .length; i++) {
                 maxSum += arr[i];
           }
          Return max;
} else {
     Int minSum = 0;
     Int maxsum =0;
     For (int I = 0; i< arr.length; i++) {
           maxSum += arr[i];
     }
     While (minsum !=maxSum – 1 ) {
           Int mid = (minSum + maxsum) / 2;
           If (getNeedNum(arr, mid ) > num) {
                minSum = mid;
           } else {
                maxSum = mid;
           }
      }
     Return maxSum;
}
}
使用道具 举报

回复

发表于 2015-12-17 13:47:12 | 显示全部楼层
所用语言:c、c++
第一题答案:
void sort(int *vec, int vec_size){
    int tmp = 0;
    for (int i = 0;  i < vec_size; ++i) {
        while (vec != i + 1) {
             tmp = vec[vec  - 1] ;             vec[vec  - 1]  = vec;
              vec = tmp;
     }
}

第二题答案:
int getValidNum(int * vec, int mid, int vec_size){
     int result = 1;
     int total_num = 0;
     for (int i = 0; i != vec_size; i++) {
         if (vec > mid) {
             return MAX_INT;
         }
         total_num += vec;
         if (total_num  > mid) {
             ++result;
              total_num = vec;
         }
     }
     return result ;
}


int process(int *vec, int num, int vec_size){
      if (NULL == vec || 0 == vec_size || num < 1) {
          printf("errror input!\n");
          return -1;
      }

      if (vec_size < num) {
           int max = INT_MIN;
           for (int i = 0; i != vec_size ;++i ) {
               if (max < vec) {
                   max = vec;
               }
           }
          return max;
       } else {
         int minSum = 0;
         int maxSum =0;
         for (int i = 0; i < vec_size; ++) {
             maxSum += vec;
         }
         while (minSum != maxSum – 1 ) {
             int mid = (minSum + maxSum)  /  2;
             if (getValidNum(vec, mid, vec_size) > num) {
                minSum = mid;
             } else {
                maxSum = mid;
             }
         }
         return maxSum;
      }
}




使用道具 举报

回复

发表于 2015-12-17 20:47:32 | 显示全部楼层
本帖最后由 yezhang989 于 2015-12-17 20:57 编辑

题目1

算法思路
数组arr在排序的情况下,满足的条件是“arr=i+1, i是数组下标”。
设v是数组arr的其中某个元素,对数组arr的排序过程,等价于将v移动到arr的v-1位置处,使其满足 arr[v-1]=v。

复杂度分析
数组arr每个元素最多经历一次遍历和一次位置移动,时间复杂度为 O(N)。
算法需要额外的内存空间,记录下一个将被移动的元素下标和值,空间复杂度为 O(1)。

Java实现
/**
* arr数组包含[1,arr.length].
*
* @param arr
*/
public static void sort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int v = arr; //当前值
        int k = v - 1; //目标索引
        int kv; //目标值
        while (k != i) {
            k = v - 1;
            kv = arr[k];
            arr[k] = v;
            v = kv;
        }
    }
}



题目2

算法思路
根据题目要求,“完成所有的画作需要的时间最少”,等价于“最耗时画家的时间最小”。
进一步分析得到,只需要保证所有画家耗时所形成的概率分布中,均方差最小即可。
采用递归的思路,实现动态规划算法。不但可以求出题目要求的最小时间,还可以计算每个画家的分工。

Java实现
(为了方便验证算法,给出了带有Main函数的完整代码)
---------------------------------------------------------------------
package com.udn;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.IntStream;

/**
* 画匠问题.
* 求数组最大值时用到了java8语法.
* <code>
*     IntStream.of(arr).max()
* </code>
*/
public class PainterAlgorithm {

    public static void main(String[] args) {
        int arr[] = {1, 1, 1, 4, 3};
        int num = 3;

        int t = minTime(arr, num);
        System.out.println(t);
    }

    /**
     * 采用递归方式实现动态规划.
     * 如果保证最耗时画匠的时间最小, 那么需要使得所有画匠的耗时分布的均方差最小.
     * 根据均方差最小的原理, 求出最优划分.
     * 根据最优划分, 求出最小时间.
     *
     * @param arr 原始输入数组.
     * @param num 分组数目, 即画匠数目.
     * @return 最小时间.
     */
    static int minTime(final int arr[], int num) {
        //如果画匠数目比画作数目还多, 那么返回最大耗时画作即可.
        if(num >= arr.length){
            return IntStream.of(arr).max().getAsInt(); //Collections.max(Arrays.asList(arr));
        }

        //如果只有一个画匠
        if(num == 1){
            return IntStream.of(arr).sum();
        }

        //没有画匠, 无法完成.
        if(num <= 0){
            return Integer.MAX_VALUE;
        }

        int sum[] = new int[arr.length + 1]; //从1到i的线段分数之和

        int res[][][] = new int[num + 1][arr.length + 1][arr.length + 1];
        

        //slice,记录一次划分的坐标, 该坐标属于左侧划分段.
        int slice[][][] = new int[num + 1][arr.length + 1][arr.length + 1];

        initSum(arr, sum);
        initRes(res);
        initRes(slice);

        dispatch(num, 1, arr.length, res, slice, sum);

        List<Integer> path = new LinkedList<Integer>();

        //输出slice
        printPath(num, slice, 1, arr.length, path);

        Collections.sort(path);

        //计算最大耗时
        int start = 1;
        int maxSliceTime = 0; //画匠的耗时

        //计算前 num-1 个画匠耗时
        for (int end : path) {
            int t = calSum(sum, start, end);
            if (t > maxSliceTime) {
                maxSliceTime = t;
            }

            start = end + 1;
        }

        //计算最后一个画匠耗时
        int t = calSum(sum, start, arr.length);
        if (t > maxSliceTime) {
            maxSliceTime = t;
        }

        return maxSliceTime;
    }

    /**
     * 打印x到y之间的分割点.
     *
     * @param layer 划分次数
     * @param slice 划分记录
     * @param x     开始下标
     * @param y     结束下标
     */
    static void printPath(int layer, int[][][] slice, int x, int y, List<Integer> list) {
        int path = slice[layer][x][y];
        if (path <= 0 || layer < 1) {
            return;
        }

        list.add(path);

        //输出左侧
        printPath(layer - 1, slice, x, path, list);

        //输出右侧
        printPath(layer - 1, slice, path + 1, y, list);

    }

    static int dispatch(int m, int x, int y, int[][][] res, int[][][] slice, int[] sum) {
        if (res[m][x][y] != -1) {
            return res[m][x][y];
        }

        if (m == 1) {
            int t = calSum(sum, x, y);
            res[m][x][y] = t * t;
            return t * t;
        }

        int MIN = Integer.MAX_VALUE;
        int sliceIndex = 0;

        for (int i = x; i < y; i++) {
            int right = calSum(sum, i + 1, y);
            int left = calSum(sum, x, i);
            int t = Math.min(dispatch(m - 1, x, i, res, slice, sum) + right * right,
                    dispatch(m - 1, i + 1, y, res, slice, sum) + left * left);
            if (t < MIN) {
                MIN = t;
                sliceIndex = i;
            }
        }

        slice[m][x][y] = sliceIndex;
        res[m][x][y] = MIN;

        return MIN;
    }

    /**
     * 全部初始化为-1;
     *
     * @param res
*/
    static void initRes(int[][][] res) {
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res.length; j++) {
                for (int k = 0; k < res[j].length; k++) {
                    res[j][k] = -1;
                }
            }
        }
    }

    /**
     * sum.length = arr.length + 1
     *
     * @param arr 输入数组
     * @param sum 输出参数, 表示数组arr前i个数的和, 即 sum = sum of arr[0,i).
     */
    static void initSum(int arr[], int sum[]) {
        for (int i = 0; i < sum.length; i++) {
            sum = 0;
        }

        for (int i = 1; i <= arr.length; i++) {
            sum = sum[i - 1] + arr[i - 1];
        }
    }

    /**
     * 记录从x到y的线段之和.
     *
     * @param x 数组开始下标
     * @param y 数组结束下标
     * @return 闭区间[x, y]的和.
     */
    static int calSum(int[] sum, int x, int y) {
        return sum[y] - sum[x - 1];
    }
}

---------------------------------------------------------------------






使用道具 举报

回复

sunyani的头像 楼主
发表于 2015-12-21 14:08:27 | 显示全部楼层
一等奖:@junbao  @chen1001
二等奖@范姐 @yezhang989
其余奖项落空,由于参与人数y有限,特等奖落空
使用道具 举报

回复

sunyani的头像 楼主
发表于 2015-12-21 14:14:26 | 显示全部楼层
sunyani 发表于 2015-12-21 14:08
一等奖:@junbao  @chen1001
二等奖@范姐 @yezhang989
其余奖项落空,由于参与人数y有限,特等奖落空 ...

获奖人员请提供有效个人信息地址,一周内不提供作废
使用道具 举报

回复

发表于 2015-12-21 23:00:33 | 显示全部楼层
sunyani 发表于 2015-12-21 14:14
获奖人员请提供有效个人信息地址,一周内不提供作废

已通过站内消息发送,请查看,谢谢!
使用道具 举报

回复

发表于 2015-12-22 09:53:27 | 显示全部楼层
本帖最后由 junbao 于 2015-12-22 09:56 编辑
sunyani 发表于 2015-12-21 14:08
一等奖:@junbao  @chen1001
二等奖@范姐 @yezhang989
其余奖项落空,由于参与人数y有限,特等奖落空 ...

以发
使用道具 举报

回复

sunyani的头像 楼主
发表于 2015-12-22 09:54:54 | 显示全部楼层
junbao 发表于 2015-12-22 09:53
地址:广东省 深圳市 宝安区 深圳市宝安国际机场
            机场海关附属楼五洲海盛楼四楼
手机:13319 ...

额,私信我就好了,你这个太不注重隐私了
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部