相交链表（leetcode160）
C++
// 相交链表
using namespace std;
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *l1 = headA;ListNode *l2 = headB;while (l1 != l2) {l1 = l1 ? l1->next : headB;l2 = l2 ? l2->next : headA;}return l1;}
};Python
from typing import Optional
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:l1 = headAl2 = headBwhile l1 != l2:l1 = l1.next if l1 else headBl2 = l2.next if l2 else headAreturn l1字符串相加（leetcode 415）
C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 字符串相加
class Solution {
public:string addStrings(string num1, string num2) {// 定义m指向nums1的尾字符位置int m = num1.length()-1;// 定义n指向nums2的尾字符位置int n = num2.length()-1;// 定义一个数组存储已处理的部分,初始一位0后续使用vector<char> ans{'0'};// 定义index标记当前处理位置(倒序位置)int index = 0;// 处理while(index<=m && index<=n){int num = (num1[m-index]-'0') + (num2[n-index]-'0') + (ans.back()-'0');int first = num/10; //十位int second = num%10; // 个位ans.back() = second+'0';ans.push_back(first+'0');index++;}// 如果num1未处理完while(index<=m){int num = (num1[m-index]-'0') + (ans.back()-'0');int first = num/10;int second = num%10;ans.back() = second+'0';ans.push_back(first+'0');index++;}// 如果num2未处理完while(index<=n){int num = (num2[n-index]-'0') + (ans.back()-'0');int first = num/10;int second = num%10;ans.back() = second+'0';ans.push_back(first+'0');index++;}// ans最后一个为最高位，为零则去除，不为零则保留if(ans.back()=='0'){ans.pop_back();}// 将结果拼接成字符串string resrult;for(int i=ans.size()-1;i>=0;i--){resrult+=ans[i];}return resrult;}
};int main(){string num1 = "11";string num2 = "123";Solution s;string ans = s.addStrings(num1,num2);cout<<ans<<endl;return 0;
}Python
# 字符串相加
class Solution:def addStrings(self, num1: str, num2: str) -> str:res = [0]index = 0m = len(num1) - 1n = len(num2) - 1while index <= m and index <= n:num = int(num1[m - index]) + int(num2[n - index]) + res[-1]# 个位first = num % 10# 十位second = num // 10res[-1] = firstres.append(second)index += 1# 如果num1还有while index <= m:num = int(num1[m - index]) + res[-1]# 个位first = num % 10# 十位second = num // 10res[-1] = firstres.append(second)index += 1# 如果num2还有while index <= n:num = int(num2[n - index]) + res[-1]# 个位first = num % 10# 十位second = num // 10res[-1] = firstres.append(second)index += 1s = ""# 末尾为最高位，非零则保留，是零则去除end = len(res) - 2 if res[-1] == 0 else len(res) - 1for i in range(end, -1, -1):s += str(res[i])return sif __name__ == '__main__':solution = Solution()num1 = "584"num2 = "18"res = solution.addStrings(num1, num2)print(res)二叉树的中序遍历（leetcode94）
C++
#include <vector>
#include <stack>
#include <iostream>
using namespace std;// 二叉树的中序遍历
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:vector<int> inorderTraversal(TreeNode *root) {// 定义结果数组vector<int> ans;if (root == nullptr) return ans;// 定义栈stack<TreeNode *> st;// 定义当前节点TreeNode *cur = root;while(cur || !st.empty()){// 当前节点存在，则进栈while(cur){st.push(cur);cur = cur->left;}// 当前节点不存在则出栈cur = st.top();st.pop();ans.push_back(cur->val);cur = cur->right;}return ans;}
};int main(){TreeNode *root = new TreeNode(1, nullptr, new TreeNode(2, new TreeNode(3), nullptr));Solution solution;vector<int> ans = solution.inorderTraversal(root);for(auto elem:ans){cout<< elem;}cout<<endl;return 0;
}Python
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
# 非递归版
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []# 定义结果列表ans = []# 定义一个栈stack = []# 定义cur指向当前处理节点cur = rootwhile cur or stack:# 当前节点进栈，向左子树遍历while cur:stack.append(cur)cur = cur.left# 当前节点不存在，则出栈顶元素访问节点cur = stack.pop(-1)ans.append(cur.val)cur = cur.rightreturn ansif __name__ == '__main__':root = TreeNode(1,None,TreeNode(2,TreeNode(3)))solution = Solution()res = solution.inorderTraversal(root)print(res)接雨水（leetcode42）
C++
#include <vector>
using namespace std;class Solution {
public:int trap(vector<int>& height) {// 定义结果变量int ans=0;// 定义左侧最大值数组vector<int> left(height.size(),0);// 定义左侧最大值int left_max = height[0];// 定义右侧最大值数组vector<int> right(height.size(),0);// 定义右侧最大值‘int right_max = height.back();for(int i=0; i<height.size();i++){left_max = max(left_max,height[i]);left[i] = left_max;}for(int i=height.size()-1;i>=0;i--){right_max = max(right_max, height[i]);right[i] = right_max;}for(int i=0; i<height.size();i++){ans+=min(left[i],right[i])-height[i];}return ans;}
};双指针法
#include <vector>
using namespace std;
class Solution {
public:int trap(vector<int>& height) {// 定义结果变量int ans = 0;// 记录左边最大值int left_max = height[0];// 记录右边最大值int right_max = height.back();// 定义左右双指针int left = 0;int right = height.size()-1;while (left<=right){left_max = max(height[left],left_max);right_max = max(height[right],right_max);if(left_max<right_max){ans+=left_max-height[left];left++;}else{ans+=right_max-height[right];right--;}}return ans;}
};Python
# 接雨水
class Solution:def trap(self, height: List[int]) -> int:ans = 0n = len(height)# 记录左侧最大值left = [0]*nleft_max = height[0]# 记录右侧最大值right = [0]*nright_max = height[-1]for i in range(n):if height[i]>left_max:left_max = height[i]left[i] = left_maxfor i in range(n-1,-1,-1):if height[i]>right_max:right_max = height[i]right[i] = right_maxfor i in range(n):tmp =min(left[i],right[i])-height[i]if tmp>0:ans+=tmpreturn ansif __name__ == '__main__':height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]solution = Solution()res = solution.trap(height)print(res)双指针法
# 接雨水（双指针法）
class Solution:def trap(self, height: List[int]) -> int:# 定义结果变量ans = 0# 定义左右最大值left_max = height[0]right_max = height[-1]# 定义双指针left = 0right = len(height)-1while left<=right:left_max = max(left_max,height[left])right_max = max(right_max,height[right])if left_max< right_max:ans+=left_max-height[left]left+=1else:ans+=right_max-height[right]right-=1return ansif __name__ == '__main__':height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]solution = Solution()res = solution.trap(height)print(res)二分查找（leetcode704）
C++
#include <vector>
using namespace std;class Solution {
public:int search(vector<int>& nums, int target) {// 定义左右指针int left = 0;int right = nums.size()-1;while (left<=right){if(nums[left]==target) return left;if(nums[right]==target) return right;int mid = left + (right-left) / 2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right = mid-1;} else{left = mid+1;}}return -1;}
};Python
from typing import List
# 二分查找
class Solution:def search(self, nums: List[int], target: int) -> int:# 定义左右指针left = 0right = len(nums)-1while left<right:if nums[left] == target:return leftif nums[right] == target:return rightif nums[(left+right)//2]== target:return (left+right)//2elif nums[(left+right)//2] > target:right = (left+right)//2else:left = (left+right)//2return -1
)
