技术教程 python基础编程和c++的对比语法 正文

python基础编程和c++的对比语法

2022-08-10,,,

文章目录

    • 1. 两数之和
    • 2. 两数相加
    • 3. 无重复字符的最长子串
    • 4. 寻找两个正序数组的中位数
    • 5. 最长回文子串
    • 6. Z 字形变换
    • 未完待续。。。

1. 两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例: 

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解:
第一种做法：循环俩次，依次遍历查找，时间复杂度为O(n2)O(n^2)
第二种方法：使用哈希表，将出现过的数全部存到哈希表中，然后依次遍历哈希表中的值 x ，
判断目标值减去x的值target - x是否存在即可，时间复杂度为O(n)O(n)

c++版 

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> mp; for(int i = 0; i < nums.size(); i++){ int r = target - nums[i]; if(mp.count(r)) return {mp[r], i}; mp[nums[i]] = i; } return {}; } };

python版 

class Solution(object): def twoSum(self, nums, target): """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """ mp = {} for i, x in enumerate(nums): r = target - x if r in mp: return [mp[r], i] mp[x] = i return [];

2. 两数相加

题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解
(模拟人工加法) O(n)
这是道模拟题，模拟我们小时候列竖式做加法的过程：
从最低位至最高位，逐位相加，如果和大于等于10，则保留个位数字，同时向前一位进1.
如果最高位有进位，则需在最前面补1.
做有关链表的题目，有个常用技巧：添加一个虚拟头结点：ListNode *head = new ListNode(-1);，可以简化边界情况的判断。
时间复杂度：由于总共扫描一遍，所以时间复杂度是 O(n).

c++版 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode * p = new ListNode(-1); ListNode * cur = p; int t = 0; while(l1 || l2 || t){ if(l1) t += l1->val, l1 = l1->next; if(l2) t += l2->val, l2 = l2->next; cur->next = new ListNode(t % 10); cur = cur->next; t /= 10; } return p->next; } };

python版 

# Definition for singly-linked list. # class ListNode(object): #     def __init__(self, x): #         self.val = x #         self.next = None class Solution(object): def addTwoNumbers(self, l1, l2): """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """ p = ListNode(-1) cur = p
        t = 0 while(l1 or l2 or t): if l1: t += l1.val
                l1 = l1.next if l2: t += l2.val
                l2 = l2.next cur.next = ListNode(t % 10) cur = cur.next t /= 10 return p.next

3. 无重复字符的最长子串

题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1: 

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2: 

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3: 

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题解
(双指针扫描) O(n)
定义两个指针 i,j(i<=j)，表示当前扫描到的子串是 [i,j] (闭区间)。
扫描过程中维护一个哈希表unordered_map<char,int> hash，表示 [i,j]中每个字符出现的次数。
线性扫描时，每次循环的流程如下：
指针 j 向后移一位, 同时将哈希表中 s[j] 的计数加一: hash[s[j]]++;
假设 j 移动前的区间 [i,j]中没有重复字符，则 j 移动后，只有 s[j] 可能出现2次。
因此我们不断向后移动 i，直至区间 [i,j]中 s[j] 的个数等于1为止；
复杂度分析：由于 i,j 均最多增加n次，且哈希表的插入和更新操作的复杂度都是 O(1)，
因此，总时间复杂度 O(n).

c++版 

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> mp; int ans = 0; for(int i = 0, j = 0; i < s.size(); i++){ mp[s[i]]++; while(mp[s[i]] > 1)mp[s[j++]]--; ans = max(ans, i - j + 1); } return ans; } };

python版 

class Solution(object): def lengthOfLongestSubstring(self, s): """
        :type s: str
        :rtype: int
        """ mp = {} ans = 0 j = 0 for i in range(len(s)): if s[i] in mp: mp[s[i]] += 1 else: mp[s[i]] = 1 while(mp[s[i]] > 1): mp[s[j]] -= 1 j += 1 ans = max(ans, i - j + 1) return ans

4. 寻找两个正序数组的中位数

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例 1: 

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2: 

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

题解
使用二分的做法求解
交换顺序
为了减少思考，我们先假定一个序列的长度总不大于第二个。如果大于了，那么就交换一下。
怎么二分查找呢？
假设两个序列按顺序合并了，那么中间点的位置就在(len1 + len2 + 1) // 2
假定这个理想中位数为x
考虑一般情况下，第一个序列存在一个数，其左边都是小于x，右边都大于。
对第二个序列也是一样。
我们对这两个数在各自序列的位置分别称作mid1和mid2。
所以我们首先先对第一个序列二分查找。
记录左边界，右边界为第一个序列的左右边界。
而查找的中间就是左右边界的中间点。
对于mid2，便是(len1 + len2 + 1) // 2减去mid1
更新二分查找的条件
mid1左侧和mid2左侧的数都应该比mid1和mid2对应的数小。
所以可以肯定，如果mid2左侧的数比mid1对应的数都大，那么第一行的中间太靠左了。
可以这么想，如果mid2左侧的数比mid1对应的都大，那不如第二行的数选小一点而第一行的数选大一点，这样两个数会更接近。
要把第一行的中间往右，即二分查找的更新left。
反之更新right。套用模板。
记得mid1不要越过上限！

c++版 

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int total = nums1.size() + nums2.size(); if (total % 2 == 0) { int left = findKthNumber(nums1, 0, nums2, 0, total / 2); int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1); return (left + right) / 2.0; } else { return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1); } } int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) { if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k); if (nums1.size() == i) return nums2[j + k - 1]; if (k == 1) return min(nums1[i], nums2[j]); int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2; if (nums1[si - 1] > nums2[sj - 1]) { return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2); } else { return findKthNumber(nums1, si, nums2, j, k - (si - i)); } } };

python版 

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n1 = len(nums1) n2 = len(nums2) if n1 > n2: return self.findMedianSortedArrays(nums2,nums1) k = (n1 + n2 + 1)//2 left = 0 right = n1 while left < right : m1 = left +(right - left)//2 m2 = k - m1 if nums1[m1] < nums2[m2-1]: left = m1 + 1 else: right = m1
        m1 = left
        m2 = k - m1 
        c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") ) if (n1 + n2) % 2 == 1: return c1
        c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf")) return (c1 + c2) / 2

5. 最长回文子串

题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1： 

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2： 

输入: "cbbd"
输出: "bb"

题解：
（暴力枚举） O(n2)
由于字符串长度小于1000，因此我们可以用 O(n2) 的算法枚举所有可能的情况。
首先枚举回文串的中心 i，然后分两种情况向两边扩展边界，直到遇到不同字符为止:
回文串长度是奇数，则依次判断 s[i−k]==s[i+k],k=1,2,3,…
回文串长度是偶数，则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…
如果遇到不同字符，则我们就找到了以 ii 为中心的回文串边界。
时间复杂度分析：一共两重循环，所以时间复杂度是 O(n2)。

c++版 

class Solution { public: string longestPalindrome(string s) { int n = s.size(); string ans; int l = 0; for(int i = 0; i < n; i++){ for(int j = 0; i - j >= 0 && i + j < n; j++){ if(s[i - j] != s[i + j]) break; if((2 * j + 1) > l){ ans = s.substr(i - j,2 * j + 1); l = 2 * j + 1; } } for(int j = 0; i - j >= 0 && i + j + 1 < n; j++){ if(s[i - j] != s[i + j + 1]) break; if((2 * (j + 1)) > l){ ans = s.substr(i - j,2 *( j + 1)); l = 2 * (j + 1); } } } return ans; } };

python版 

class Solution: def longestPalindrome(self, s: str) -> str: ans = "" n = len(s) for i in range(n): for j in range(n): if i - j < 0 or i + j >= n or s[i - j] != s[i + j]: break if(2 * j + 1 > len(ans)): ans = s[i - j:i + j + 1] for j in range(n): if i - j < 0 or i + j + 1 >= n or s[i - j] != s[i + j + 1]: break if(2 * (j + 1) > len(ans)): ans = s[i - j:i + j + 2] return ans

6. Z 字形变换

题目描述
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下： 

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数： 

string convert(string s, int numRows);

示例 1: 

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2: 

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

c++题解：
(找规律) O(n)O(n)
这种按某种形状打印字符的题目，一般通过手画小图找规律来做。
我们先画行数是4的情况：
0    6    12
1  5 7  11 …
2 4  8 10
3    9
从中我们发现，对于行数是 n 的情况：
    1.对于第一行和最后一行，是公差为 2(n−1) 的等差数列，首项是 0 和 n−1；
    2.对于第 i 行(0<i<n−1)，是两个公差为 2(n−1) 的等差数列交替排列，首项分别是 i 和 2n−i−2；
所以我们可以从上到下，依次打印每行的字符。
时间复杂度分析：每个字符遍历一遍，所以时间复杂度是O(n).

c++版 

class Solution { public: string convert(string s, int numRows) { string ans; if(numRows == 1) return s; for(int i = 0; i < numRows; i++){ if(i == 0 || i == numRows - 1) for(int j = i; j < s.size(); j += 2 * numRows - 2) ans += s[j]; else{ for(int j = i, k = 2 * numRows - 2 - i; j < s.size() || k < s.size(); j += 2 * numRows - 2, k += 2 * numRows - 2){ if(j < s.size())ans += s[j]; if(k < s.size()) ans += s[k]; } } } return ans; } };

python题解：
字符串 s 是以 Z 字形为顺序存储的字符串，目标是按行打印。
设 numRows 行字符串分别为s1,s2,...,sns_1, s_2 ,..., s_n ，则容易发现：按顺序遍历字符串 s 时，
每个字符 c 在 Z 字形中对应的 行索引 先从 s1s_1 增大至 sns_n ,再从 sns_n 减小至 s1s_1 …… 如此反复。
因此，解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i] 。
算法流程: 按顺序遍历字符串 s；
1.res[i] += c： 把每个字符 c 填入对应行 sis_i；
2.i += flag： 更新当前字符 c 对应的行索引；
3.flag = - flag： 在达到 ZZ 字形转折点时，执行反向。 

class Solution: def convert(self, s: str, numRows: int) -> str: if numRows < 2: return s
        ans = ["" for _ in range(numRows)] i, flag = 0, -1 for c in s: ans[i] += c if i == 0 or i == numRows - 1: flag = -flag
            i += flag return "".join(ans)

本文地址：https://blog.csdn.net/qq_43328040/article/details/107099753

《python基础编程和c++的对比语法.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!