文章目錄
- 21.合并兩個連結清單
-
- C++版本
- Python
- 22.括号生成
-
- C++ 版本
- Python 版本
- 23.合并k個有序連結清單
-
- C++版本
- Python版本
- 24.兩兩交換連結清單中的節點
-
- C++版本
- Python版本
- 25. k個一組翻轉連結清單
-
- C++版本
- Python
- 26.删除排序數組中的重複項
-
- C++版本
- Python版本
- 27.移除元素
-
- C++版本
- Python版本
- 28.實作strStr()函數
-
- C++版本
- Python版本
- 29.兩數相除
-
- C++ 版本
- Python版本
- 30.與所有單詞相關聯的子串
-
- C++版本
- Python 版本
21.合并兩個連結清單
将兩個有序連結清單合并為一個新的有序連結清單并傳回
算法思想：按部就班寫吧？
C++版本
struct ListNode{
int val;
ListNode* next;
};
ListNode *merge2node(ListNode *head1, ListNode *head2){
if(head1==NULL||head2==NULL) {
return head1? head1:head2;
}
ListNode *start = (ListNode*)malloc(sizeof(ListNode));
start->val = 0;
ListNode *end = start;
ListNode *h1 = head1->next;
ListNode *h2 = head2->next;
while (h1||h2) {
if(h1==NULL||h2==NULL){
end->next = h1 ? h1:h2;
if(h1==NULL) h2 = h2->next;
else h1 = h1->next;
end = end->next;
continue;
}
if (h1->val <= h2->val) {
end->next = h1;
h1 = h1->next;
}
else{
end->next= h2;
h2 = h2->next;
}
end = end->next;
}
end->next = NULL;
return start;
}
void printListNode(ListNode *head){
if(head==NULL) return;
ListNode *tmp = head;
while (tmp!=NULL) {
cout<<tmp->val<<"->";
tmp = tmp->next;
}
cout<<endl;
}
ListNode *createListNode(vector<int> nums){
ListNode *head,*end,*node;
head = (ListNode*)malloc(sizeof(ListNode));
end = head;
for(int i=0;i<nums.size();i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
end->next = node;
end = node;
}
end->next = NULL;
return head;
}
int main(){
vector<int> nums1 = {1,2,4};
vector<int> nums2 = {1,3,4,5};
ListNode *head1 =createListNode(nums1);
ListNode *head2 =createListNode(nums2);
printListNode(head1);
printListNode(head2);
ListNode *head = merge2node(head1, head2);
printListNode(head);
}
//我嘗試将一個連結清單的值賦給另一個連結清單的值報錯
//Debug: thread 1: EXC_BAD_ACCESS (code=1, address=0x500000004)
//int main(){
// vector<int> nums1 = {1,2,4};
// ListNode *head1 =createListNode(nums1);
// ListNode *head2=head1;
// head2->val = head1->val;
//
// printListNode(head2);
//
//}
Python
class ListNode(object):
def __init__(self,val):
self.val = val
self.next = None
def createListNode(l):
"""
:param l: list
:return: ListNode
"""
head = ListNode(0)
end = head
for i in l:
end.next = ListNode(i)
end = end.next
end.next = None
return head
def printListNode(head):
"""
:param head: ListNode
:return:
"""
tmp =head.next
while(tmp!=None):
print(tmp.val,end="->")
tmp = tmp.next
print("")
print("列印完成!")
def merge2ListNode(h1,h2):
"""
:param head1: ListNode
:param head2: ListNode
:return: ListNode
"""
h = ListNode(0)
head = h
head1 = h1.next
head2 = h2.next
while(head1 or head2):
if head1==None or head2==None:
head.next = head1 if not head2 else head2
head = head.next
if head1==None:
head2 = head2.next
else:
head1 = head1.next
continue
if head1.val>=head2.val:
head.next = head2
head2 = head2.next
else:
head.next = head1
head1 = head1.next
head = head.next
return h
l1 = [1,4,5,7]
l2 = [2,3,6]
head1 = createListNode(l1)
head2 = createListNode(l2)
printListNode(head1)
printListNode(head2)
head = merge2ListNode(head1,head2)
printListNode(head)
22.括号生成
給定一個數字n，傳回所有可能生成的有效的n個括号組合。
算法思想：采用回溯算法，通過兩個條件擷取我們想要的括号組合。C++和Python算法一緻。
C++ 版本
void generator(vector<vector<char>> &res,vector<char> path, int left, int n){
if(path.size()==2*n){
if(left==0) res.push_back(path);
return;
}
if(left<n){
path.push_back('(');
generator(res, path, left+1,n);
path.pop_back();
}
if(left>0){
path.push_back(')');
generator(res, path, left-1, n);
path.pop_back();
}
}
vector<vector<char>> generatorParenthesis(int n){
vector<vector<char>> res;
int left=0;
vector<char> path;
generator(res, path, left, n);
return res;
}
void printres(vector<vector<char>> res){
long n = res.size();
long m = res[0].size();
for(int i=0;i<n;i++){
for (int j=0; j<m; j++) {
cout<<res[i][j];
}
if(i < n-1) cout<<',';
else cout<<endl;
}
}
int main(){
int n = 3;
vector<vector<char>> res;
res = generatorParenthesis(n);
printres(res);
}
Python 版本
def genParenthesis(n):
def dfs(left,path,res,n):
if len(path) == 2*n:
if left == 0:
res.append("".join(path))
return
if left < n:
path.append("(")
dfs(left+1,path,res,n)
path.pop()
if left > 0:
path.append(')')
dfs(left-1,path,res,n)
path.pop()
return res
res = []
path = []
left = 0
r = dfs(left,path,res,n)
return r
print(genParenthesis(3))
23.合并k個有序連結清單
給定k個有序連結清單，傳回合并後的排序連結清單，請分析和描述算法複雜度。
算法思想：python暫時采用調用合并兩個連結清單；C++我嘗試将連結清單中的所有值取出來，排序後建構一個新連結清單。
C++版本
struct ListNode{
int val;
ListNode* next;
};
ListNode *mergeKListNode(vector<ListNode *> ll){
vector<int> nums;
ListNode *lnext;
for(int i=0;i<ll.size();i++){
lnext = ll[i];
while (lnext->next) {
nums.push_back(lnext->next->val);
lnext = lnext->next;
}
}
cout<<nums.size()<<endl;
sort(nums.begin(), nums.end());
ListNode *head,*end,*tmp;
head = (ListNode*)malloc(sizeof(ListNode));
end = head;
head->val = 0;
for(int i=0;i<nums.size();i++){
tmp = (ListNode*)malloc(sizeof(ListNode));
tmp->val = nums[i];
end->next = tmp;
end = end->next;
}
end->next = NULL;
return head;
}
void printListNode(ListNode *head){
if(head==NULL) return;
ListNode *tmp = head;
while (tmp!=NULL) {
cout<<tmp->val<<"->";
tmp = tmp->next;
}
cout<<endl;
}
ListNode *createListNode(vector<int> nums){
ListNode *head,*end,*node;
head = (ListNode*)malloc(sizeof(ListNode));
end = head;
for(int i=0;i<nums.size();i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
end->next = node;
end = node;
}
end->next = NULL;
return head;
}
int main(){
vector<int> v1 = {1,4,5};
vector<int> v2 = {1,3,4};
vector<int> v3 = {2,6};
ListNode *head1 = createListNode(v1);
ListNode *head2 = createListNode(v2);
ListNode *head3 = createListNode(v3);
vector<ListNode *> ll;
ll.push_back(head1);
ll.push_back(head2);
ll.push_back(head3);
ListNode *head = mergeKListNode(ll);
printListNode(head);
}
Python版本
class ListNode(object):
def __init__(self,val):
self.val = val
self.next = None
def createListNode(l):
"""
:param l: list
:return: ListNode
"""
head = ListNode(0)
end = head
for i in l:
end.next = ListNode(i)
end = end.next
end.next = None
return head
def printListNode(head):
"""
:param head: ListNode
:return:
"""
tmp =head.next
while(tmp!=None):
print(tmp.val,end="->")
tmp = tmp.next
print("")
print("列印完成!")
def merge2ListNode(h1,h2):
"""
:param head1: ListNode
:param head2: ListNode
:return: ListNode
"""
h = ListNode(0)
head = h
head1 = h1.next
head2 = h2.next
while(head1 or head2):
if head1==None or head2==None:
head.next = head1 if not head2 else head2
head = head.next
if head1==None:
head2 = head2.next
else:
head1 = head1.next
continue
if head1.val>=head2.val:
head.next = head2
head2 = head2.next
else:
head.next = head1
head1 = head1.next
head = head.next
return h
def mergeKListNode(ll):
"""
:param l: [ListNode]
:return: ListNode
"""
return reduce(merge2ListNode,ll)
l1 = [1,4,5]
l2 = [1,3,4]
l3 = [2,6]
ll = []
ll.append(createListNode(l1))
ll.append(createListNode(l2))
ll.append(createListNode(l3))
res = mergeKListNode(ll)
printListNode(res)
24.兩兩交換連結清單中的節點
給定一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後的連結清單
算法思想：直接周遊通過雙指針做轉換，也可以嘗試遞歸的方法。
C++版本
struct ListNode{
int val;
ListNode* next;
};
ListNode *changeALLNode(ListNode *l){
ListNode *ll = l->next;
if(l->next && l->next->next){
l->next = l->next->next;
}
ListNode *tmp1,*tmp2;
while (ll && ll->next) {
tmp1 = ll->next; //tmp1 = 2
ll->next = tmp1->next;
tmp1->next = ll;
tmp2 = ll;
ll = ll->next;
if (ll && ll->next){
tmp2->next = ll->next;
}
else if(ll){
tmp2->next = ll;
}
else {}
}
return l;
}
void printListNode(ListNode *head){
if(head==NULL) return;
ListNode *tmp = head;
while (tmp!=NULL) {
cout<<tmp->val<<"->";
tmp = tmp->next;
}
cout<<endl;
}
ListNode *createListNode(vector<int> nums){
ListNode *head,*end,*node;
head = (ListNode*)malloc(sizeof(ListNode));
end = head;
for(int i=0;i<nums.size();i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
end->next = node;
end = node;
}
end->next = NULL;
return head;
}
int main(){
vector<int> nums = {1,2,3,4,5,6,7,8};
ListNode *l = createListNode(nums);
printListNode(l);
ListNode *head = changeALLNode(l);
printListNode(head);
}
Python版本
class ListNode(object):
def __init__(self,val):
self.val = val
self.next = None
def createListNode(l):
"""
:param l: list
:return: ListNode
"""
head = ListNode(0)
end = head
for i in l:
end.next = ListNode(i)
end = end.next
end.next = None
return head
def printListNode(head):
"""
:param head: ListNode
:return:
"""
tmp =head.next
while(tmp!=None):
print(tmp.val,end="->")
tmp = tmp.next
print("")
print("列印完成!")
def changeALLNode(head):
h = head.next
head.next = h.next
def change2Node(h):
if(h and h.next):
tmp1 = h.next
h.next = tmp1.next
tmp1.next = h
tmp2 = h
h = h.next
if(h and h.next):
tmp2.next = h.next
change2Node(h)
elif(h):
tmp2.next = h
return
else:
return
else:
return
change2Node(h)
l = [1,2,3,4,5]
head1 = createListNode(l)
printListNode(head1)
changeALLNode(head1)
printListNode(head1)
25. k個一組翻轉連結清單
給定一個連結清單，每k個節點一組進行翻轉，并傳回翻轉後的連結清單。如果節點綜述不是k的整數倍，那麼将剩餘節點保留原有順序。
算法思想：可以采用遞歸，也可以直接寫。
C++版本
struct ListNode{
int val;
ListNode* next;
};
ListNode *nextN(ListNode *head,int n){
ListNode *start,*end;
start = head;
for(int i=0;i<n;i++){
end = start;
if(start->next){
start = start->next;
}
else return NULL;
}
return end;
}
ListNode *reverseKNode(ListNode *l,int n){
ListNode *ll = l->next;
ListNode *nextn = nextN(ll, n);
if(nextn){
l->next = nextn;
}
else return l;
ListNode *ptr[n];
while (ll && nextn) {
for (int i=0; i<n; i++) {
ptr[i] = ll;
ll = ll->next; // ll指向第n+1個元素
}
for(int i=0;i<n-1;i++){
ptr[n-1-i]->next = ptr[n-2-i];
}
nextn = nextN(ll, n);
if (ll && nextn){
ptr[0]->next = nextn;
}
else if(ll){
ptr[0]->next = ll;
}
else {}
}
return l;
}
void printListNode(ListNode *head){
if(head==NULL) return;
ListNode *tmp = head->next;
while (tmp!=NULL) {
cout<<tmp->val<<"->";
tmp = tmp->next;
}
cout<<endl;
}
ListNode *createListNode(vector<int> nums){
ListNode *head,*end,*node;
head = (ListNode*)malloc(sizeof(ListNode));
end = head;
for(int i=0;i<nums.size();i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = nums[i];
end->next = node;
end = node;
}
end->next = NULL;
return head;
}
int main(){
vector<int> nums = {1,2,3,4,5,6,7,8};
ListNode *l = createListNode(nums);
printListNode(l);
ListNode *head = reverseKNode(l, 3);
printListNode(head);
}
Python
class ListNode(object):
def __init__(self,val):
self.val = val
self.next = None
def createListNode(l):
"""
:param l: list
:return: ListNode
"""
head = ListNode(0)
end = head
for i in l:
end.next = ListNode(i)
end = end.next
end.next = None
return head
def printListNode(head):
"""
:param head: ListNode
:return:
"""
tmp =head.next
while(tmp != None):
print(tmp.val,end="->")
tmp = tmp.next
print("")
print("列印完成!")
def nextN(ll,n):
start = ll
nextn = start
for i in range(n):
nextn = start
if start.next:
start = start.next
else: return None
return nextn
def reverseKNode(head,n):
"""
:param head: ListNode
:param n: int
:return: ListNode
"""
h = head.next
nextn = nextN(h,n)
if nextn:
head.next = nextn
else: return head
def reverseNode(h,nextn):
listNode = []
for i in range(n):
listNode.append(h)
h = h.next
for i in range(n-1):
listNode[n-1-i].next = listNode[n-2-i]
nextn = nextN(h,n)
if nextn:
listNode[0].next = nextn
reverseNode(h,nextn)
else:
listNode[0].next = h
reverseNode(h,nextn)
l = [1,2,3,4,5,6,7,8]
head1 = createListNode(l)
printListNode(head1)
reverseKNode(head1,3)
printListNode(head1)
26.删除排序數組中的重複項
給定一個排序數組，原地删除重複出現的元素，傳回移除後數組的新長度。不适用額外的數組空間。
算法思想：設定一個指針表示未重複元素的終點，可以通過周遊與該指針相比較，也可以周遊元素與相鄰元素比較。
C++版本
int removeDuplicates(int a[],int n){
int tmp = 0;
for (int i=1; i<n; i++) {
if(a[tmp] != a[i]){
tmp++;
a[tmp] = a[i];
}
}
return tmp+1;
}
int main(){
int a[] = {0,1,1,2,2,2,3,4};
int n = 8;
int tmp = removeDuplicates(a, n);
cout<<"tmp:"<<tmp<<endl;
}
Python版本
def remvoeDuplicates(nums):
tmp = 0
for i in range(1,len(nums)):
if(nums[i] != nums[tmp]):
tmp += 1
nums[tmp] = nums[i]
return tmp + 1
print(remvoeDuplicates([0,1,1,1,2,2,3,4]))
27.移除元素
給定一個數組nums和一個值val，原地移除所有數值等于val的元素，傳回移除後數組的長度。
算法思想：雙指針的思想，一個指針指向更新後的數組，另外一個指針周遊數組，操作都是在同一個數組。
C++版本
int removeElement(vector<int> &nums,int val){
int i=0;
int j=0;
while (j<nums.size()) {
if(nums[j]==val){
j++;
}
else{
nums[i]=nums[j];
i++;
j++;
}
}
return i;
}
void printnums(vector<int> nums,int n){
for(int i=0;i<n;i++){
cout<<nums[i]<<"->";
}
}
int main(){
vector<int> nums = {0,0,1,1,2,3,3,4};
int val = 3;
int n = removeElement(nums, val);
printnums(nums,n);
cout<<endl;
}
Python版本
def removeElement(nums,val):
tmp = 0
for i in range(len(nums)):
if nums[i]==val:
continue
else:
nums[tmp] = nums[i]
tmp += 1
return tmp
nums = [1,2,3,3,4]
n = removeElement(nums,3)
print(nums[:n])
28.實作strStr()函數
給定一個haystack字元串和needle字元串，在haystack字元串找出needle字元串出現的第一個位置。如果不存在，則傳回-1。
算法思想：暴力解法，此外，算法還有優化的空間KMP算法。
C++版本
int strStr(char *hay,char *need){
if(!need||!hay) return NULL;
char *ph,*pn;
ph = hay;
int j = 0;
while (*ph) {
char *tmp = ph;
for(pn=need;*pn;pn++){
if(*tmp != *pn) {
break;
}
tmp++;
}
if(!*pn){
return j;
}
ph++;
j++;
}
return -1;
}
int main(){
const char* hay = "hello";
const char* need = "lo";
int i = strStr((char*)hay,(char*)need);
cout<<i<<endl;
}
Python版本
def strStr(s1,s2):
for i in range(len(s1)):
tmp = i
for j in range(len(s2)):
if s1[tmp]==s2[j]:
tmp += 1
continue
else:
break
if len(s2)==tmp-i:
return i
return -1
print(strStr("hello","ll"))
29.兩數相除
給定一個被除數和除數，将兩數相除，要求不使用乘法、除法和mod運算符
算法思想：通過位運算來轉化，有點像進制的轉換。
C++ 版本
int div1(int dividend,int divisor){
int sign = (float)dividend/divisor>0 ? 1:-1;
unsigned int dvd = dividend > 0? dividend: -dividend;
unsigned int dvs = divisor >0? divisor: -divisor;
unsigned int bit_num[32];
unsigned int i = 0;
long long d = dvs;
bit_num[i] = d;
while (dvd >= d) {
bit_num[++i] = d = d<<1;
}
int sum = 0;
while (dvd >= dvs) {
if(dvd >= bit_num[i]){
sum =sum + (1<<i);
dvd = dvd - bit_num[i];
}
i--;
}
return sum*sign;
}
int main(){
cout<<div1(100, 3)<<endl;
cout<<div1(9, 3)<<endl;
cout<<div1(38, 3)<<endl;
}
Python版本
def div(dividend,divisor):
if divisor==0:
return 0x7fffffff
sign = 1
if dividend*divisor<0:
sign = -1
ans = 0
dividend = abs(dividend)
divisor = abs(divisor)
subsum = 0
while(dividend>divisor):
cnt = 1
if dividend < 2*divisor:
ans += 1
return ans
tmp = dividend
while(tmp>divisor):
tmp >>= 1
cnt <<= 1
cnt >>= 1
subsum = cnt*divisor
ans += cnt
dividend -= subsum
return max(min(sign*ans,0x7fffffff),-2147483648)
print(div(91,3))
30.與所有單詞相關聯的子串
給定一個字元串和一些長度相同的單詞words，在s中找到可以恰好傳來words中所有單詞的子串的起始位置。
算法思想：Python版本（我審題有問題，安裝長度不同的單詞來考慮，而且沒有考慮單詞重複的情況）分為兩部分，首先生成一個包含單詞首字母索引的字典，其次根據生成的字典做比對，主要滿足：目前單詞首字母的索引 + 單詞長度 = 下一個不重複的單詞的索引
C++版本的思想就是從結果入手，正确的結果必然是單詞長度組合，是以可以通過不同的初始尺寸去卡(周遊單詞長度)，在卡的過程中，當不滿足條件則遞增初始值(單詞長度)。總體來說，C++版本的思想很好很好，值得學習。
C++版本
vector<int> findSubstring(string S,vector<string> &L){
vector<int> result;
if(S.size()<=0 || L.size()<=0){
return result;
}
int n = S.size(), m = L.size(), l = L[0].size();
//單詞可能為多個，是以通過一個字典存儲下
map<string,int> expected;
for(int i=0;i<m;i++){
if(expected.find(L[i])!=expected.end()){
expected[L[i]]++;
}else{
expected[L[i]] = 1;
}
}
// 固定長度的單詞，注意審題
for(int i=0;i<l;i++){
map<string,int> actual;
int count = 0;
int winLeft = i;
for(int j=i;j<n-l;j+=l){
string word = S.substr(j,l);
if(expected.find(word)==expected.end()){
actual.clear();
count = 0;
winLeft = j+l;
continue;
}
count++;
if(actual.find(word)==actual.end()){
actual[word] = 1;
}else{
actual[word]++;
}
if(actual[word]>expected[word]){
string tmp;
do{
tmp = S.substr(winLeft,l);
count--;
actual[tmp]--;
winLeft += l;
}while (tmp!=word);
}
if(count==m){
result.push_back(winLeft);
string tmp = S.substr(winLeft,l);
actual[tmp]--;
winLeft += l;
count--;
}
}
}
return result;
}
int main(int argc,char**argv){
string s = "barfoothefoobarman";
vector<string> l;
l.push_back("foo");
l.push_back("bar");
vector<int> indics = findSubstring(s, l);
for (int i=0; i<indics.size(); i++) {
cout<<indics[i]<<" ";
}
cout<<endl;
}
Python 版本
def findSubString(s,words):
n = len(words)
d = {} # 單詞-索引清單 鍵值對
l = [] # 提取的單詞索引清單
wordl = [] # 單詞防重
res = []
for word in words:
for i in range(len(s)):
tmp = i
for j in range(len(word)):
if s[tmp] == word[j]:
if j == len(word)-1:
if word in d.keys():
d[word].append(i)
else:
d[word] = []
d[word].append(i)
tmp += 1
continue
else:
break
newd = {}
tmpkey = 0
for key,value in d.items():
l = l + value
for val in value:
newd[val] = key
l = sorted(l)
for i in range(len(l)):
tmp = i
while(tmp<len(l)):
if tmp == i:
wordl.append(newd[l[tmp]])
tmpkey = l[tmp] + len(newd[l[tmp]])
elif newd[l[tmp]] not in wordl and tmpkey == l[tmp]:
wordl.append(newd[l[tmp]])
tmpkey = l[tmp] + len(newd[l[tmp]])
else:
break
if len(wordl)==n:
res.append(l[i])
break
tmp += 1
i += 1
return res
print(findSubString("viewfilexxfileedit",["edit","file"]))
enjoy！
本文代碼可能有bug，還請各位看官指正，或者小夥伴們有更好的算法，歡迎評論~
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)