20180606 qzd
每日一题10——Two Sum
(Tag:列表)
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
from:https://leetcode.com/problems/two-sum/description/
答案：
- 数据结构解题
class Solution(object):
def twoSum(self, nums, target):
#hash用于建立数值到下标的映射
hash = {}
#循环nums数值，并添加映射
for i in range(len(nums)):
if target - nums[i] in hash:
return [hash[target - nums[i]], i]
hash[nums[i]] = i
#无解的情况
return [-1, -1]
- 内置函数解题
class Solution:
"""
@param numbers: An array of Integer
@param target: target = numbers[index1] + numbers[index2]
@return: [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, nums, target):
for i, a in enumerate(nums):
for j, b in enumerate(nums[i + 1:]):
if a + b == target:
return [i, j + i + 1]
return [-1, -1]
每日一题11——Toeplitz Matrix
(Tag:数组)
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
注意事项
matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].
样例
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512
In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
Example 2:
Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.
from:https://www.lintcode.com/zh-cn/old/problem/toeplitz-matrix/
解题：
class Solution:
"""
@param matrix: the given matrix
@return: True if and only if the matrix is Toeplitz
"""
def isToeplitzMatrix(self, matrix):
# Write your code here
for i in range(len(matrix)-1):
for j in range(len(matrix)-1):
if matrix[i][j]!=matrix[i+1][j+1]:
print(False)
print(True)
每日一题12
- 有四个数字：1、2、3、4，能组成多少个互不相同且无重复数字的三位数？各是多少？
程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。
code:
for i in range(1,5):
for j in range(1,5):
for k in range(1,5):
if(i!=j)and(i!=k)and(j!=k):
print(i,j,k)
- 企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？
程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。
code:
i= int(input('jinlirun:'))
arr = [1000000,600000,400000,200000,100000,0]
rat = [0.01,0.015,0.03,0.05,0.075,0.1]
r=0
for idx in range(6):
if i >arr[idx]:
r+=(i-arr[idx])*rat[idx]
#print((i-arr[idx])*rat[idx])
i=arr[idx]
print(r)
每日一题13
- 一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？
程序分析：
假设该数为 x。
1、则：x + 100 = n2, x + 100 + 168 = m2
2、计算等式：m2 - n2 = (m + n)(m - n) = 168
3、设置： m + n = i，m - n = j，i * j =168，i 和 j 至少一个是偶数
4、可得： m = (i + j) / 2， n = (i - j) / 2，i 和 j 要么都是偶数，要么都是奇数。
5、从 3 和 4 推导可知道，i 与 j 均是大于等于 2 的偶数。
6、由于 i * j = 168， j>=2，则 1 < i < 168 / 2 + 1。
7、接下来将 i 的所有数字循环计算即可。
code:
for i in range(1,85):
if 168 %i==0:
j=168/i;
if i>j and(i+j)%2==0 and(i-j)%2==0:
m=(i+j)/2
n=(i+j)/2
x=n*n-100
print(x)
- 输入某年某月某日，判断这一天是这一年的第几天？
程序分析：以3月5日为例，应该先把前两个月的加起来，然后再加上5天即本年的第几天，特殊情况，闰年且输入月份大于2时需考虑多加一天：
code:
year = int(input('year:\n'))
month = int(input('month:\n'))
day = int(input('day:\n'))
months = (0,31,59,90,120,151,181,212,243,273,304,334)
if 0 < month <= 12:
sum = months[month - 1]
else:
print('data error')
sum+=day
leap=0
if (year %400 ==0)or((year%4==0)and (year %100!=0)):
leap=1
if(leap==1)and (mounth>2):
sum+=1
print('it is the %dth day,'%sum)
