1 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1) 即求最大连续子序列的问题
链接：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
来源：牛客网
class Solution:
def FindGreatestSumOfSubArray(self, array):
res =len(array) and max(array) #长度不为零，则reszan定位array的最大值
temp = 0
for i in array:
temp = max(i,temp+i) #如果之前的值加上现在比现在还小，则舍去之前的
res = max(res,temp) #比较最大的res与最新的temp，留存最大值
return res
动态规划https://blog.csdn.net/baidu_28312631/article/details/47418773
https://www.zhihu.com/question/23995189 （推荐）
https://blog.csdn.net/u013309870/article/details/75193592
核心思想：尽量缩小可能解空间。
操作过程 ;一言以蔽之：大事化小，小事化了。
将一个大问题转化成几个小问题；
求解小问题；
推出大问题的解。
重要概念：无后效性（让我想起来控制学过的的马尔科夫过程...）,最优子结构
因此判断能否用动态规划：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质
拓扑排序入门：https://blog.csdn.net/qq_41713256/article/details/80805338
动规的优点：暴力做法是枚举所有的可能解，这是最大的可能解空间。DP是枚举有希望成为答案的解。这个空间比暴力的小得多。
也就是说：DP自带剪枝。
2 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
if n ==0:
return 0
res = []
num = 0
for i in range(n+1):
res.append(str(i))
for j in res:
num = num + j.count('1')
return num
暴力法：转换成str类型，然后分别计算‘1’的个数。注意 str ，count的用法
一定要注意range(len(s))与range(s）的区别，以及对应下 i 的不同含义
也可以写成
链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
来源：牛客网
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
return ''.join(map(str, range(n+1))).count('1') 除开暴力法，要用归纳找规律的方法来解决
链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
来源：牛客网
/*
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位以下（低位）的数字，百位以上（高位）的数字。
① 如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，...，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
② 如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，....，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共114个，等于低位数字（113）+1。
③ 如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，...，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
*/
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;//1的个数
int i = 1;//当前位
int current = 0,after = 0,before = 0;
while((n/i)!= 0){
current = (n/i)%10; //高位数字
before = n/(i*10); //当前位数字
after = n-(n/i)*i; //低位数字
//如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
if (current == 0)
count += before*i;
//如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
else if(current == 1)
count += before * i + after + 1;
//如果大于1,出现1的次数由高位决定,//（高位数字+1）* 当前位数
else{
count += (before + 1) * i;
}
//前移一位
i = i*10;
}
return count;
}
} 2 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers): #类似冒泡排序
# write code here
if not numbers:
return ''
for j in range(len(numbers)):
for i in range(len(numbers)-1):
a = str(numbers[i+1]) + str(numbers[i])
b = str(numbers[i]) + str(numbers[i+1])
if a > b:
tmp = numbers[i]
numbers[i] = numbers[i+1]
numbers[i+1] = tmp
else:
pass
res = ''
for i in range(len(numbers)):
res = str(numbers[i]) + res
res1 = int(res)
return res1
排序算法的升级版，比较的不是两个数的大小，而是组成字符串（数字）的大小，上面使用了冒牌排序来解决。摘录于评论区一段话“所以在这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。突然大悟。”
4 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一开始使用暴力法，即判断每一个数是不是丑数来解决，但是时间超时了（肯定的..）
'''res = []
i = 0
while(len(res) < index):
i = i+1
if i %2 ==0 or i%3 ==0 or i%5 ==0 or i ==1 :
r = self.ugly(i)
if r > 0:
res.append(self.ugly(i))
else:
pass
else:
pass
return res[-1]
def ugly(self,i):
flag = 0
i_old = i
while(flag == 0):
if i%2 == 0:
i = int(i/2)
elif i%3 ==0:
i = int(i/3)
elif i % 5 ==0:
i = int(i/5)
elif i == 1:
flag = 1
else:
flag = 1
if i == 1:
return i_old
else:
return -1''' 应该改用生成法：即通过乘法运算算出丑数序列。这里涉及到一个排序的问题，用一个min函数圆满解决。
if index ==0:
return 0
res = [1]
t2 = t3 = t5 = 0
while (len(res) < index):
r = min(2*res[t2],3*res[t3],5*res[t5])
if r not in res:
res.append(r)
if min(2*res[t2],3*res[t3],5*res[t5]) == 2*res[t2]:
t2 = t2+1
elif min(2*res[t2],3*res[t3],5*res[t5]) == 3*res[t3]:
t3 = t3+1
else:
t5 = t5+1
return res[-1]
t起到类似于指针的作用，用于指示进行运算的res值，每个res只能进行一次2，3，5运算，所以运算完成将t后移。
5 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
一开始的解法：
if not s:
return -1
for i in range(len(s)):
flag = self.findone(s[i],s)
if flag:
return i
return -1
def findone(self,num,s):
fre = 0
for j in range(len(s)):
if s[j] == num:
fre = fre +1
else :
pass
if fre == 1:
return True
else:
return False 但是显然本地可以利用dict来解决啊（正好重温dict用法），即遍历一遍之后把各个数字在数组中的出现次数存储起来
res = dict.fromkeys(s,0)
for i in s:
res[i] = 1 + res[i]
#print(res)
for j in s:
if res[j] == 1:
return s.index(j) 注意dict的fromkeys生成方法，注意初始化值
注意index的用法
6 输入两个链表，找出它们的第一个公共结点。
思路是。利用两个链表之差，来解决，一个很妙的方法是两指针同时遍历，短的肯定先循环完，之后调换指针，显然指针之差正好是长度差，因此减少了计算长度差这一步。当然也可以用栈倒序做，或者先求长度差，然后长链表先跑len的差后再进行比较。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
p1,p2 = pHead1,pHead2
while(p1 != p2 ):
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
''' len1 = len2 = 0
p1 = pHead1
p2 = pHead2
if not pHead1 or not pHead2:
return None
while(p1.next):
len1 = len1 + 1
p1 = p1.next
while(p1.next):
len2 = len2 + 1
p1 = p1.next
dis = abs(len1 - len2)
if len1 > len2:
for i in range(dis):
pHead1 = pHead1.next
for i in range(len1 - dis):
if pHead1 = pHead2:
return pHead1
return None
elif dis == 0:
for i in range(len1 - dis):
if pHead1 = pHead2:
return pHead1
return None
else:
for i in range(len1):
if pHead1 = pHead2:
return pHead1
return None
''' 链表题：注意链表的定义 注意头指针的copy 注意比较跟返回的是val还是结点本身
7 统计一个数字在排序数组中出现的次数。
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
count = 0
Flag = False
if not data:
return 0
for i in range(len(data)):
if data[i] == k:
Flag =True
count = 1
j = 1
while(j+i < len(data)): #不能是小于等于，因为最后一位是 data[n-1],n是长度
print(i+j)
if data[j+i] == data[i]:
count = count + 1
j = j + 1
return count
return count 暴力稍微简化法如上。注意i,j以及data[i],data[j]的区别！
评论区大佬：看见有序，肯定就是二分查找了，算法比较简单，不多说，值得一提的是，不要拘泥于递归，要会循环写法。——这个意思要有，划重点要考的...
链接：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2
来源：牛客网
def GetFirstK(self, data, k):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] < k:
low = mid + 1
elif data[mid] > k:
high = mid - 1
else:
if mid == low or data[mid - 1] != k: #当到list[0]或不为k的时候跳出函数
return mid
else:
high = mid - 1
return -1
def GetLastK(self, data, k):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] > k:
high = mid - 1
elif data[mid] < k:
low = mid + 1
else:
if mid == high or data[mid + 1] != k:
return mid
else:
low = mid + 1
return -1
def GetNumberOfK(self, data, k):
if not data:
return 0
if self.GetLastK(data, k) == -1 and self.GetFirstK(data, k) == -1:
return 0
return self.GetLastK(data, k) - self.GetFirstK(data, k) + 1
基础知识补充：
1 Python ord() 函数 ord() 函数是 chr() 函数（对于8位的ASCII字符串）或 unichr() 函数（对于Unicode对象）的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值，如果所给的 Unicode 字符超出了你的 Python 定义范围，则会引发一个 TypeError 的异常。>>>ord('a') 97 >>> ord('b') 98 >>> ord('c') 99
2 Python 字典(Dictionary) fromkeys()方法 Python 字典 fromkeys() 函数用于创建一个新字典，以序列 seq 中元素做字典的键，value 为字典所有键对应的初始值。
romkeys()方法语法：
dict.fromkeys(seq[, value]) 3 python字典的用法 http://www.runoob.com/python/python-dictionary.html
4 and (逻辑与）的计算法则
在程序设计中，and称为逻辑与运算，也称布尔运算；
1.and是在布尔上下文中从左到右计算表达式的值；
2.0、''、[]、()、{}、None、False在布尔上下文中为假；其它任何东西都为真；
3.如果布尔上下文中的某个值为假，则返回第一个假值；
4.所有值都为真，则返回最后一个真值。
5 通常取模运算也叫取余运算，它们返回结果都是余数 .rem 和 mod 唯一的区别在于:
当 x 和 y 的正负号一样的时候，两个函数结果是等同的；当 x 和 y 的符号不同时，rem 函数结果的符号和 x 的一样，而 mod 和 y 一样。
6 DP，DFS，贪心等等要深入研究，尤其是背包问题跟路径规划之类的题目。
京公网安备 11010502036488号