描述：一群孩子做游戲，現在請你根據游戲得分來發糖果，要求如下：
給定一個數組 arrarr 代表得分數組，請返回最少需要多少糖果
描述：有 n 個活動即將舉辦，每個活動都有開始時間與活動的結束時間，第 i 個活動的開始時間是 starti ,第 i 個活動的結束時間是 endi ,舉辦某個活動就需要為該活動准備一個活動主持人。
一位活動主持人在同一時間只能參與一個活動。並且活動主持人需要全程參與活動，換句話說，一個主持人參與了第 i 個活動，那麼拿薯該主持人在 (starti,endi) 這個時間段不能參與其他任何活動。求為了成功舉辦這 n 個活動，最少需要多少名主持人。
輸入：
2,[[1,2],[2,3]]
返回值：
1
說明：
只需要一個主持人就能成功舉辦這兩個活動
輸入：
2,[[1,3],[2,4]]
返回值：
2
說明：
需要兩個主持人才能成功舉辦這兩個活動
描述：假設你有一個數組prices，長度為n，其中prices[i]是股票在第i天的價格，請根據這個價格數組，返回買賣股票能獲得的最大收益
1.你可以買入一次股票和賣出一次股票，並非每天都可以蠢敏輪買入或賣出一次，總共只能買入帶信和賣出一次，且買入必須在賣出的前面的某一天
2.如果不能獲取到任何利潤，請返回0
3.假設買入賣出均無手續費
數據范圍： 0 <= n <= 10^5 , 0 <= val <= 10^4
要求：空間復雜度 O(1)，時間復雜度 O(n)
描述：假設你有一個數組prices，長度為n，其中prices[i]是某隻股票在第i天的價格，請根據這個價格數組，返回買賣股票能獲得的最大收益
描述：描述
假設你有一個數組prices，長度為n，其中prices[i]是某隻股票在第i天的價格，請根據這個價格數組，返回買賣股票能獲得的最大收益
這里的buy2以及profit2如何更新？
1.只有一個數出現奇數次，其它數出現偶數次
2.共有兩個數出現奇數次，其它數目出現偶數次
#一個數&與自己的取反加1就是得到該數最右位置的1
eor&(~eor+1)
⑵ python中有哪些簡單的演算法
你好：
跟你詳細說一下python的常用8大演算法：
1、插入排序
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入演算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。
2、希爾排序
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
3、冒泡排序
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
4、快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5、直接選擇排序
基本思想：第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。
6、堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序演算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
7、歸並排序
歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
歸並過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，並令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素復制到r中從下標k到下標t的單元。歸並排序的演算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸並操作合並成有序的區間[s,t]。
8、基數排序
基數排序(radix sort)屬於「分配式排序」(distribution sort)，又稱「桶子法」(bucket sort)或bin sort，顧名思義，它是透過鍵值的部分資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。
⑶ python求解線性規劃問題，百度後發現了scipy模塊，optimize，新手希望大神能寫個實例，例子如下：
scipy做線性規劃不是很方便，推薦用pulp來做，這個模塊不屬於python的內置模塊，需要先安裝，pip install pulp
from pulp import *
# 設置對象
prob = LpProblem('myProblem', LpMinimize)
# 設置三個變數，並設置變數最小取值
x1 = LpVariable('x1', 0)
x2 = LpVariable('x2', 0)
x3 = LpVariable('x3', 0)
x4 = LpVariable('x4')
# 載入目標函數，默認是求最小值，因此這次對原目標函數乘以-1
prob += 3*x1 - 4*x2 + 2*x3 -5*x4
# 載入約束變數
prob += 4*x1 - x2 + 2*x3 -x4 == -2
prob += x1 + x2 -x3 + 2*x4 <= 14
prob += -2*x1 + 3*x2 + x3 -x4 >= 2
# 求解
status = prob.solve()
# 顯示結果
for i in prob.variables():
print(i.name + "=" + str(i.varValue))
計算結果為：
x1=0.0
x2=2.0
x3=4.0
x4=8.0
⑷ python非線性規劃用什麼模塊
python非線性規劃用什麼模塊本文使用SciPy的optimize模塊來求解非線性規劃問題，結合實際例子，引入非線性規劃問題的求解演算法及相應函數的調用。
本文提綱一維搜索／單變數優化問題
無約束多元優化問題
非線性最小二乘問題
約束優化問題
非線性規劃問題的目標函數或約束條件是非線性的。本文使用SciPy的optimize模塊來求解非線性規劃問題。
目標函鎮滾數和約束搏清條件是否連續光滑是非常重要的性質，這是因為如果光滑，則所有決策變數可微，多變數函數的偏導數組成的向量為梯度，梯度是指向目標函數增長最快的方向。將目標函數梯度作為搜索方向，對非線性規劃問題的求解具有重要的意義。這些函數或其導數\梯度的不基旅前連續性給許多現有的非線性優化問題的求解帶來了困難。在下文中，我們假設這些函數是連續且光滑的。
# Importing Moles
from scipy import optimize
import matplotlib.pyplot as plt
import numpy as np
import sympy
1、一維搜索／單變數優化問題(Univariate Optimization)
無約束非線性規劃最簡單的形式是一維搜索。一維搜索通常作為多維優化問題中的一部分出現，比如梯度下降法中每次最優迭代步長的估計。求解一維搜索常用的兩類方法是函數逼近法和區間收縮法。其中函數逼近法是指用較簡單的函數近似代替原來的函數，用近似函數的極小點來估計原函數的極小點，比如牛頓法；區間收縮法對於一個單谷函數通過迭代以不斷縮小該區間的長度，當區間長度足夠小時，可將該區間中的一點作為函數的極小點，比如黃金分割法。
e.g. 最小化一個單位體積的圓柱體的表面積。
r, h = sympy.symbols("r, h")
Area = 2 * sympy.pi * r**2 + 2 * sympy.pi * r * h
Volume = sympy.pi * r**2 * h
⑸ python中有哪些簡單的演算法
演算法都是第三方庫才有的
如果要自帶的，只有排序了，是timsort
⑹ python解決jacob迭代法求解線性方程組
題主好. 經典的 Jacobi 迭代演算法如下:
設 A = D - E, 則 x = D^{-1}*b + D^{-1}*E*x = C + T*x
可以參考如下代碼(復制代碼後請注意縮進):
import numpy as np
def linalg_solve_jacobi(A, b, x0, max_it, tol=1.0e-7):
# 判斷 A, b 的維數是否正確
if A.shape[0]!=A.shape[1] or A.shape[0]!= b.shape[0]:
raise Exception('A must be square or A and b must be compatible!')
D = np.diag(A)
# 判斷對角元素是否含零
if np.amin(np.absolute(D)) < 1e-14:
raise Exception('Diagonal elements of A must not be zeros!')
# 設置初始迭代步數為0
n = 0
#
# Jacobi 演算法:
# 設 A = D - E, 則 x = D^{-1}*b + D^{-1}*E*x = C + T*x
#
invD = np.diag(1.0/D) # invD is inv(D)
C = np.dot(invD,b) # C is inv(D)*b
T = np.dot(invD, np.diag(D)-A) # T is inv(D)*E
while n < max_it:
x = C + np.dot(T, x0)
if np.linalg.norm(x-x0)<tol:
break
x0[:] = x
n+=1
# 如果超過最大迭代步數, 迭代失敗
if n>max_it:
raise Exception('Failed to converge within {} steps!'.format(max_it))
# 成功, 返回
return x, n
if __name__ == "__main__":
A = np.array([[10, -1, 2, 0],[-1, 11, -1, 3],
[2, -1, 10, -1], [0, 3, -1, 8]], dtype=np.float64)
b = np.array([6, 25, -11, 15], dtype=np.float64)
x0 = np.array([0,0,0,0], dtype=np.float64)
max_it = 100
tol = 1.0e-7
x,n=linalg_solve_jacobi(A, b, x0, max_it, tol)
print(x,n)
⑺ python求解多解問題怎麼讓方程數量多於未知數值
目錄
一、多元多次方程
1.1 定義
我們常見的方程組有一元一次方程組，比如x+3=5這種，很簡單很好解。
二元一次方程組，即方程組中有兩個未知數，未知數的最高次數為1.
二元二次方程組：方程組中有兩個未知數，未知數的最高次數為2.。此類方程組均有公式解法或者成形的解法。
但是面臨多元多次方程組，解法錯綜復雜，是數學家們研究的內容。為了更好的解決此類問題，我們可以用python來實現。
1.2 例子
多元多次方程組例如下面這種，三元二次方程組：
下面這種，二元二次方程組。
第二個方程組實在比較復雜，因此需要藉助python。
二、python求解工具包
python求解方程組的工具包較多。例如：
numpy：numpy.linalg.solve 可以直接求解線性方程組，numpy是python非常常用的包，解的方程也較為初級。
scipy：from scipy.optimize import fsolve，可以求解非線性方程組，使用較為方便，但是解集並不完備，可能漏掉一下解(後文會給個例子)scipy可以用於數學、科學、工程領域的常用軟體包,可以處理插值、積分、優化，相對較初級易用
sympy：此廳嫌工具包功能相對強大，支持符號計算、高精度計算、解方程、微積分、組合數學、離散數學、幾何學、概率與統計、物理學等方面的功能。github地址：
https://github.com/sympy/sympy
sage，不支持位運算，z3約束求解器，等其他工具包，本文不詳述，感興趣的可以查找相應的內容。
本文詳細講述scipy以及sympy求解多次方程的方法。
三、scipy方法
3.1 使用scipy的鉛春fsolve求解
我們只將求解方程的部分。
用fsolve相對初級，也相對簡單易操作，代碼較為簡單，只用將方程的表達式寫出運行即可。fsolve近似看作用最小二乘法求解。不夠很強大，很多情況下解集不完備或者無法解出。
例如對於
，首先要定義相應的函數：
def solve_function(unsolved_value):
x,y,z=unsolved_value[0],unsolved_value[1],unsolved_value[2]
return [
x**2+y**2-10,
y**2+z**2-34,
x**2+z**2-26,
]
求解函數三個公式都為0時候的解，中括弧內為初值[0, 0, 0]
solved=fsolve(solve_function,[0, 0, 0])
全部代碼：
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
python解方程
"""
from scipy.optimize import fsolve
def solve_function(unsolved_value):
x,y,z=unsolved_value[0],unsolved_value[1],unsolved_value[2]
return [
x**2+y**2-10,
y**2+z**2-34,
x**2+z**2-26,
]
solved=fsolve(solve_function,[0, 0, 0])
print(solved)
print("Program done!")
"""
運行結果：
[-1. 3. 5.]
Program done!
"""
看出運行結果來看，此結果並非完備解集。因為x，y，z都是可正可負。例如1或者-1，3或者-3，5或者-5，但是此工具包只能解出一個解。
3.2 非完備解
顯而易見，x**2-9=0的解為3或者-3
def solve_function(unsolved_value):
x=unsolved_value[0]
return [
x**2-9,
]
solved=fsolve(solve_function,[0])
但是程序只能得出一扮激手個結果3，但是得不到-3
3.3 非線性方程的解
最簡單的sin(x)=0.5,則x可能為π/6或者 5π/6
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
python解方程
"""
from scipy.optimize import fsolve
from math import sin,cos
def solve_function(unsolved_value):
x=unsolved_value[0]
return [
sin(x)-0.5
]
solved=fsolve(solve_function,[3.14])
print(solved)
solved=fsolve(solve_function,[0])
print(solved)
print("Program done!")
運行結果為：
[2.61799388]
[0.52359878]
Program done!
可以解出π/6或者 5π/6，中括弧內為初始迭代的值。
3.4 無法求解
部分較難情況無法求解
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
python解方程
"""
from scipy.optimize import fsolve
def solve_function(unsolved_value):
x,y=unsolved_value[0],unsolved_value[1]
return [
x*x+2*x*y,
2*x*y-2*y*y
]
solved=fsolve(solve_function,[6, -3])
print(solved)
print("Program done!")
無法求解會給出報錯，和用最小二乘法迭代得到明顯錯誤的解。
[1.64526700e-115 1.33665018e-115]
A:\python\python\lib\site-packages\scipy\optimize\minpack.py:162: RuntimeWarning: The number of calls to function has reached maxfev = 600.
Program done!
warnings.warn(msg, RuntimeWarning)
四、sympy工具包求解
沒安裝可以在teiminal中pip install sympy，此工具包涉及支持符號計算、高精度計算、模式匹配、繪圖、解方程、微積分、組合數學、離散 數學、幾何學、概率與統計、物理學等方面的功能。功能較為強大，解方程組時性能也較好。
4.1 二元一次方程組
較為簡單，
from sympy import *
# 二元一次方程
x = Symbol('x')
y = Symbol('y')
solved_value=solve([2*x+y-1, x-2*y], [x, y])
print(solved_value)
此方法較為簡單，但是相應的自變數應當寫成符號的形式，x=Symbol('x')
求解後有分數解：
{x: 2/5, y: 1/5}
Program done!
4.2 多解
多解情況與復數解
例如，多個解的情況，sympy可以很好的進行求解
x = Symbol('x')
solved_value=solve([x**2-9], [x])
print(solved_value)
輸出結果：
[(-3,), (3,)]
4.3 復數解
復數解也可以很好解出：
# 復數解
solved_value = solve([x ** 2 + 9], [x])
print(solved_value)
solved_value = solve([x ** 4 - 9], [x])
print(solved_value)
"""
運行結果：
[(-3*I,), (3*I,)]
[(-sqrt(3),), (sqrt(3),), (-sqrt(3)*I,), (sqrt(3)*I,)]
"""
復數解也能較好解出
4.4 非線性求解
比如三角函數：
程序均能較好解出
# 非線性解
solved_value = solve([sin(x) - 0.5], [x])
print(solved_value)
solved_value = solve([sin(x) - 1], [x])
print(solved_value)
"""
[(0.523598775598299,), (2.61799387799149,)]
[(pi/2,)]
"""
4.5 較為復雜的二元二次方程
此題較難，無論人來算，很難算出，用scipy工具包也迭代不出解。但是sympy強大的功能可以很好的解出此方程。
# 二元二次方程組
x = Symbol('x')
y= Symbol('y')
solved_value=solve([x**2+2*x*y-6,2*x*y-2*y**2+3], [x,y])
print(solved_value)
有四組實數解：
[(-(-3 + sqrt(13))*sqrt(sqrt(13)/2 + 2), -sqrt(sqrt(13)/2 + 2)),
((-3 + sqrt(13))*sqrt(sqrt(13)/2 + 2), sqrt(sqrt(13)/2 + 2)),
(-sqrt(2 - sqrt(13)/2)*(-sqrt(13) - 3), -sqrt(2 - sqrt(13)/2)),
(sqrt(2 - sqrt(13)/2)*(-sqrt(13) - 3), sqrt(2 - sqrt(13)/2))]
復雜的問題終於解出，有四組實數解！
五、全部代碼
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
python解方程
created by xingxinagrui on 2020.2.24
"""
from scipy.optimize import fsolve
from math import sin,cos
from sympy import *
# 1-4 scipy
# 5-7 sympy
part=7
if part==1:
# 求解非線性方程組
def solve_function(unsolved_value):
x=unsolved_value[0]
return [
sin(x)-0.5
]
solved=fsolve(solve_function,[3.14])
print(solved)
solved=fsolve(solve_function,[0])
print(solved)
if part==2:
# 求解三元二次方程組
def solve_function(unsolved_value):
x, y, z = unsolved_value[0], unsolved_value[1], unsolved_value[2]
return [
x ** 2 + y ** 2 - 10,
y ** 2 + z ** 2 - 34,
x ** 2 + z ** 2 - 26,
]
solved = fsolve(solve_function, [0, 0, 0])
print(solved)
if part==3:
#解的非完備性
def solve_function(unsolved_value):
x = unsolved_value[0]
return [
x ** 2 - 9,
]
solved = fsolve(solve_function, [0])
print(solved)
if part == 4:
# 較難無法求解
def solve_function(unsolved_value):
x, y = unsolved_value[0], unsolved_value[1]
return [
x * x + 2 * x * y,
2 * x * y - 2 * y * y
]
solved = fsolve(solve_function, [6, -3])
print(solved)
if part == 5:
# 二元一次方程
x = Symbol('x')
y = Symbol('y')
solved_value=solve([2*x+y-1, x-2*y], [x, y])
print(solved_value)
if part == 6:
# 多解情況
x = Symbol('x')
solved_value=solve([x**2-9], [x])
print(solved_value)
# 復數解
solved_value = solve([x ** 2 + 9], [x])
print(solved_value)
solved_value = solve([x ** 4 - 9], [x])
print(solved_value)
# 非線性解
solved_value = solve([sin(x) - 0.5], [x])
print(solved_value)
solved_value = solve([sin(x) - 1], [x])
print(solved_value)
if part == 7:
# 二元二次方程組
x = Symbol('x')
y= Symbol('y')
solved_value=solve([x**2+2*x*y-6,2*x*y-2*y**2+3], [x,y])
print(solved_value)
print("Program done!")
⑻ python的pulp庫解決線性規劃問題
戰術決策問題，某戰略轟炸機隊指揮官得到了摧毀敵方坦克生產能力的命令. 根據情報, 敵方有四個生產坦克部件的工廠, 位於不同的地方. 只要破壞其中任一工廠的生產設施就可以有效地停止敵方坦克的生產. 根據分析, 執行該任務的最大因素是汽油短缺, 為此項任務只能提供48000加侖汽油.而對於任何一種轟炸機來說, 不論去轟炸哪一個工廠都必須有足夠往返的燃料和100加侖備余燃料.該轟炸機隊現有重型和中型兩種轟炸機, 其燃油消耗量及數量見下表
編號 飛機類型 每千米耗油量 飛機駕數
1 重型 1/2 48
2 中型 1/3 32
各工廠距離空軍基地的距離和摧毀目標的概率見下表
工廠 距離/千米 摧毀目標概率(重型/中型)
1 450 0.10 0.08
2 480 0.20 0.16
3 540 0.15 0.12
4 600 0.25 0.20
所以應該去2號工廠1駕重型和1駕中型機，去4號工廠45駕重型機和31駕中型機。
⑼ Python 演算法
什麼是演算法
「演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。」
「在談到演算法時，我們不得不去了解一下什麼是時間復雜度和空間復雜度這兩個概念」
計算機科學中，演算法的時間復雜度是一個函數，它定量描述了該演算法的運行時間,時間復雜度常用大O符號（大O符號（Big O notation）是用於描述函數漸進行為的數學符號。
空間復雜度：它是用來評估演算法內存佔用大小的一個式子。
Python 演算法的幾大重要特徵
Python演算法除了具有以上特徵，還和時間和空間有關系，不同的演算法可能用不同的時間、空間或效率來完成同樣的任務，因此， 一個Python演算法的優劣可以用空間復雜度與時間復雜度來衡量。
通過實例加深對演算法的理解
如題所示：
要求x,y,z的1000以內取值滿足x x+y y=z*z，同時x+y+z=1000,求解出所以x,y,z的組合情況？
求解過程如下
這里使用了一個waste_time方法作為裝飾器來計算裝飾過的方法的執行時間，這里有兩種演算法來求解這個問題
代碼如下：
總結：
通過這個示例，對於同一個問題給出兩種不同的演算法，兩種演算法在執行過程中我增加了對程序執行時間的統計，通過時間上的對比發現兩個演算法的執行時間相差非常的大，如響應結果所示。
由此我們可以得出一個結論，就是實現不同的演算法程序執行的時間可以反應出演算法的效率，即演算法有優劣之分，好的演算法可以節約時間，提高效率，反之則不然。