剑指offer第七天

30.连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //当输入无效时,返回0
        if(array == null || array.length == 0) return 0;
        int[] DP = new int[array.length];
        DP[0] = array[0];
        int max = DP[0];
        for(int i = 1; i < array.length ; i++){
            //DP[i]表示以array[i]为结尾的最大连续子序列
            DP[i] = Math.max(DP[i-1]+array[i],array[i]);
            max = Math.max(max,DP[i]);
        }
        return max;
    }
}

31.1~n整数中1出现的次数

输入一个整数n,求1~ n个整数的十进制表示中1出现的次数,例如:输入13,1~13中包含1的数字有1、10、11、12、13因此共出现6次。

解题思路:

思路: n中每一位数字对整体“1”数量的影响包括一下两个方面:

  1. 若第i位大于1,则该位1的个数位,高于i的位组成的数字+1倍的10^i;
  2. 若第i位等于1,则该位1的个数位,高于i的位组成的数字倍的10^i加上后面各位组成的数字加1;
  3. 若第i位小于1,则该位1的个数位,高于i的位组成的数字倍的10^i; import java.util.ArrayList; public class Solution { public int NumberOf1Between1AndN_Solution(int n) { if(n<=0) return 0; //用于将int的每一位数字保存在int[]数组中 ArrayList<Integer> number = new ArrayList<>(); int totalNums = 0; //已分析过的高位数字组成的乘子 int mult = 0; int temp = n; while(temp!=0){ number.add(temp%10); temp = temp/10; } for(int i = number.size()-1;i>=0;i--){ int nums = (int)(Math.pow(10,i)); if(number.get(i) == 1){ totalNums += (int)(n % Math.pow(10,i) + 1); }else if(number.get(i) > 1){ totalNums += (int)(Math.pow(10,i)); }else if(number.get(i) == 0){ } totalNums += mult * nums; mult = mult * 10 + number.get(i); } return totalNums; } }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

9720
来自专栏尾尾部落

[剑指offer] 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候...

9810
来自专栏小樱的经验随笔

Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

31640
来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

11730
来自专栏WD学习记录

牛客网 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候...

11220
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

22280
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

36850
来自专栏编程理解

动态规划(二):0-1背包

代码中存在两层循环,以二维数组的形式记录中间数据,分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断,分别用于判断空间大小

47510
来自专栏cloudskyme

算法——递推算法

递推算法 给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来...

41880
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

38480

扫码关注云+社区

领取腾讯云代金券