算法部分
算法刷题笔记
目录:
- 剑指offer
- Leetcode
- PAT甲级和乙级的内容
一.慕课网算法面试指南
1.引导
(1)算法面试是什么?
- 不代表能够"正确"回答每一个算法问题,但是合理的思考方向其实很重要,也是正确完成算法面试问题的前提
- 算法面试优秀不意味者技术面试优秀
- 技术面试优秀不意味者能够拿到offer
(2)什么是合理的思考路径
- 展示给面试官你思考问题的方式
- 把面试的过程看做是和面试官一起讨论一个问题的解决方案
- 对于问题的细节和应用的环境,可以和面试官进行沟通
(3)算法面试优秀不意味者技术面试优秀
- 项目经历与项目中遇到的实际问题
- 遇到的印象最深的bug是什么
- 面向对象
- 设计模式
- 网络相关;安全相关;内存相关;并发相关
- 系统设计:scalability
(4)技术面试优秀不意味者能够拿到offer
面试不仅仅是考察技术水平,还是了解你的过去以及形成的思考行为方式
参与项目至关重要
(5)创建自己的项目
- 做自己的小应用:计划表,备忘录,播放器
- 自己解决小问题:爬虫,数据分析,词频统计
- "不是项目"的项目:一本优秀的技术书籍的代码整理
- 分享:自己的技术博客;github等等
(6)通过过去了解你的思考行为方式
- 遇到的最大的挑战
- 犯过的错误
- 遭遇的失败
- 最享受的工作内容
- 遇到冲突的处理方式
- 做的最与众不同的事儿
(7)准备好合适的问题问面试官
- 整个小组的大概运行模式?
- 整个项目的后续规划是如何的?
- 这个产品中的某个问题是如何解决的?
- 为什么会选择某项技术?标准?
- 我对某项技术很感兴趣,在你的小组中我会有怎样的机会深入这种技术
(8)算法面试
- 远远不需要看算法导论(抓大放小)
- 高级数据结构和算法面试提及的概率很低(红黑树,计算几何,B树)
- 远远不需要到达acm水平
- 不要轻视基础算法和数据结构(排序算法,基础数据结构,基础算法,基本算法思想)
(9)注意题目中的条件
- 给定一个有序数组
暗示:
设计一个O(nlogn)的算法
无需考虑额外的空间
数据规模大概是10000
没有思路的时候:
给自己几个简单的测试用例
不要忽视暴力解法,暴力解法通常是思考的起点
优化算法:
遍历常见的的算法思路
遍历常见的数据结构
空间和时间的交换(哈希表)
预处理信息(排序)
在瓶颈处寻找答案
极端条件的判断:
数组为空?字符串为空?数量为0?,指针为NULL?
变量名
模块化,复用性
对于基本问题,白板编程
(10)时间复杂度相关
1s之内:
O(n^2)的算法可以处理10^4的数据
O(n)的算法可以处理10^8的数据
O(nlogn)的算法可以处理10^7的数据
(11)空间复杂度相关(递归调用是有空间代价的)
多开一个辅助空间的数组:O(n)
多开一个辅助的二维数组:O(n^2)
多开常数空间:O(1)
二.Leetcode题目
1.Array类
(1)问题(Leetcode 283 ):
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
2)代码:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
vector<int> nonZero;
for(int i = 0; i < nums.size();i++)
if(nums[i])
nonZero.push_back(nums[i]);
for(int i=0;i<nonZero.size();i++)
nums[i]=nonZero[i];
for(int i=nonZero.size();i<nums.size();i++)
nums[i]=0;
}
};//新增一个vector进行赋值,时空复杂度都是O(n) class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k=0;
for(int i=0;i<nums.size();i++)
if(nums[i])
nums[k++]=nums[i];
for(int i=k;i<nums.size();i++)
nums[i]=0;
}
};//双指针法,时间复杂度为O(n),空间复杂度为o(1) class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k=0;
for(int i=0;i<nums.size();i++)
if(nums[i]){
if(i!=k)
swap(nums[k++],nums[i]);
else
k++;
}
}
};//双指针进行优化(当数组中全部都是非零元素的时候) (2)附属
问题(Leetcode 26)：
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4], Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.
代码：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<=0)
return 0;
int i=0;
for(int j=1;j<nums.size();j++){
if(nums[j]!=nums[i]){
i++;
nums[i]=nums[j];
}
}
return i+1;
}
};//two point 问题（Leetcode 27):
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2. It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2, Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast,slow=0;
for(int i=0;i<nums.size();i++){
if(nums[i]!=val)
nums[slow++]=nums[i];
}
return slow;
}
};//双指针法 问题(Leetcode 80):
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,1,2,3,3], Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively. It doesn't matter what values are set beyond the returned length.
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<3)
return nums.size();
for(int i=0;i<nums.size()-1;i++){
if(nums[i]==nums[i+1]){
while(i+2<nums.size()&&nums[i+2]==nums[i])
nums.erase(nums.begin()+i+2);
}
} 2.排序部分
(1)Leetcode 75 Sort Colors
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Follow up:
- A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. - Could you come up with a one-pass algorithm using only constant space?
代码部分：
class Solution {
public:
void sortColors(vector<int>& nums) {
int zero=-1;
int two=nums.size();//注意初值的设定
for(int i=0;i<two;){
if(nums[i]==1)
i++;
else if(nums[i]==2){
swap(nums[i],nums[--two]);//这个地方i不++的原因为：2可能从后面换回一个0
}
else{
assert(nums[i]==0);
swap(nums[++zero],nums[i++]);
}
}
}
};//双指针法 class Solution {
public:
void sortColors(vector<int>& nums) {
int count[3]={0};
for(int i=0;i<nums.size();i++){
assert(nums[i]>=0&&nums[i]<=2);
count[nums[i]]++;
}
int index=0;
for(int i=0;i<count[0];i++)
nums[index++]=0;
for(int i=0;i<count[1];i++)
nums[index++]=1;
for(int i=0;i<count[2];i++)
nums[index++]=2;
}
};//计数排序的原理，将对应数值放到对应的桶当中，然后分别进行遍历 (2)Leetcode 167
Given an array of integers that is already sorted in ascending order\, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
- Your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
assert(numbers.size()-1);//通过调用 abort 来终止程序运行
int l=0,r=numbers.size()-1;
while(l<r){
if(numbers[l]+numbers[r]==target){
int res[2]={l+1,r+1};
return vector<int>{res,res+2};
}
else if(numbers[l]+numbers[r]<target){
l++;
}
else
r--;
}
throw invalid_argument("The input has no solution");
}
};//对撞指针(3)Leetcode 88
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i=0,j=m;i<n;i++,j++)
nums1[j]=nums2[i];
sort(nums1.begin(),nums1.end());
}
};//直接复制 class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index=m+n-1;
int index1=m-1;
int index2=n-1;
while(index1>=0&&index2>=0){
if(nums1[index1]>nums2[index2])
nums1[index--]=nums1[index1--];
else
nums1[index--]=nums2[index2--];
}
while(index2>=0)
nums1[index--]=nums2[index2--];
}
};//使用双指针，从尾部对比进行插入(数组递增) (4)Leetcode 215 Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2 Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
return nums[nums.size()-k];
}
};
//简单排序 class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> queue;
for(auto num:nums){
queue.push(num);
}
while(k!=1){
queue.pop();
k--;
}
return queue.top();
}
};//使用STL中的priority_queue，默认为从大到小输出 (5)Leetcode 345 Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Input: "hello" Output: "holle"
Example 2:
Input: "leetcode" Output: "leotcede"
Note:
The vowels does not include the letter "y".
class Solution {
public:
bool vowel(char s){
if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u'||s=='A'||s=='E'||s=='I'||s=='O'||s=='U')
return true;
return false;
}
string reverseVowels(string s) {
int l=0,r=s.length()-1;
while(l<r){
while(l<r&&!vowel(s[r]))
r--;
while(l<r&&!vowel(s[l]))
l++;
swap(s[l++],s[r--]);
}
return s;
}
};//使用双指针法进行操作，swap之后要对元素的值进行操作！！！ (6)Leetcode 125 Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama" Output: true
Example 2:
Input: "race a car" Output: false
class Solution {
public:
bool isPalindrome(string s) {
string temp="";
for(int i=0;i<s.length();i++){
if((s[i]>='a'&&s[i]<='z')||(s[i]>='0'&&s[i]<='9'))
temp+=s[i];
else if(s[i]>='A'&&s[i]<='Z')
temp+=(s[i]+=32);
}
string ss=temp;
reverse(ss.begin(),ss.end());
return temp==ss;
}
};//符合的字符放到新的string中，然后判断是否是回文串 Leetcode 668 Valid Palindrome II
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba" Output: True
Example 2:
Input: "abca" Output: True Explanation: You could delete the character 'c'.
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution {
public:
bool validPalindrome(string s) {
int left=0,right=s.size()-1;
while(left<right){
if(s[left]!=s[right])
return isValid(s,left+1,right)||isValid(s,left,right-1);//左边和右边删除一个之后进行判断
left++;
right--;
}
return true;
}
bool isValid(string s,int left,int right){//用于判断是否是对称的图形
while(left<right){
if(s[left]!=s[right])
return false;
left++;
right--;
}
return true;
}
};//双指针法思想 (7)Leetcode 11 Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7] Output: 49
class Solution {
public:
int maxArea(vector<int>& height) {
int m=-1;
int l=0,r=height.size()-1;
while(l<r){
m=max(m,(r-l)*(height[r]>height[l]?height[l]:height[r]));
if(height[l]<height[r])
l++;
else
r--;
}
return m;
}
};//使用双指针法，不断地探测最大值 (8)Leetcode 42 Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
class Solution {
public:
int trap(vector<int>& height) {
int left=0,right=height.size()-1;//双指针法典型特征
int leftmax=0,rightmax=0;
int ans=0;
while(left<right){//singal
if(height[left]<height[right]){
if(height[left]>leftmax)
leftmax=height[left];//更新左侧的最大值
ans+=leftmax-height[left];//算得左侧的最大值与当前值的差值
left++;
}else{
if(height[right]>rightmax)
rightmax=height[right];
ans+=rightmax-height[right];
right--;
}
}
return ans;
}
};//双指针法 (9)Leetcode 238 Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4] Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int s=nums.size();
vector<int> vec(s,1);
int temp=1;
for(int i=0;i<s;i++){
vec[i]*=temp;
temp*=nums[i];
}
temp=1;
for(int i=s-1;i>=0;i--){
vec[i]*=temp;
temp*=nums[i];
}
return vec;
}
};//两遍遍历法 (10)Leetcode 209 Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int left = 0,right = -1;
int res = nums.size() + 1;
int sum = 0;
while( left < nums.size() ){
if( right + 1 < nums.size() && sum < s )
sum += nums[++right];//滑动窗口的思想，向右扩展
else
sum -= nums[left++];//向左扩展
if( sum >= s)//只有当sum大于s的时候
res = min( res , right - left + 1 );//更新最小值
}
if( res == nums.size() + 1 )//进行特判
return 0;
return res;
}
};//利用滑动窗口的思想，时间复杂度O(N),空间复杂度O(1) (11)Leetcode 3 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() < 1)
return 0;//针对条件进行特判
int left = 0,right = -1;
int res = -1;//注意是max还是min来求解
int freq[256] = {0};//标记所有的字符
while(left < s.size()){
if(right + 1 < s.size() && freq[s[right+1]] == 0)//如果可以向右扩展
freq[s[++right]]++;
else//如果可以向左扩展
freq[s[left++]]--;
res = max(res,right - left + 1);//更新最大值
}
return res;
}
};//滑动窗口方法(12)Leetcode 438 Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
assert(s.size()<20101&&p.size()<20101);//断言进行约束
int l=0,r=0;
vector<int> vec={};
int m[256] = {0};
int count=p.size();
for(auto c : p)
m[c]++;
while( r < s.size() ){
if( m[s[r]] > 0 ){
m[s[r]]--;
r++;
count--;
}else{
m[s[l]]++;
l++;
count++;
}
while( count == 0 ){//count会自增，不会一直停留在while循环内
vec.push_back(l);
m[s[l]]++;
l++;
count++;
}
}
return vec;
}
}; 3.Set，Map，List部分
(1)Leetcode 349 Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4]
Note:
- Each element in the result must be unique.
- The result can be in any order.
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> record(nums1.begin(),nums1.end());//将nums1中的值复制到record
set<int> result;
for(int i=0;i<nums2.size();i++)
if(record.find(nums2[i])!=record.end())
result.insert(nums2[i]);
return vector<int>(result.begin(),result.end());//将set中的值复制到vector中
}
};//基本的set使用 (2)Leetcode 350 Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int,int> record;
for(int i = 0 ; i < nums1.size() ; i++)
record[nums1[i]]++;
vector<int> resultVector;
for(int i = 0 ; i < nums2.size() ; i++){
if(record[nums2[i]] > 0){//如果已经存在，则减掉对应的部分
resultVector.push_back(nums2[i]);
record[nums2[i]]--;
}
}
return resultVector;
}
};//map的基本使用 为什么哈希表这么快还要使用平衡搜索树？
失去了数据的顺序性
- 数据集中的最大最小值
- 某个元素的前驱和后继
- 某个元素的floor和ceil
- 某个元素的排位rank
- 选择某个排位的元素select
C++语言中:
- map和set的底层实现为平衡二叉树，时间复杂度为O(nlogn)
- unordered_map和unordered_set的底层实现为哈希表，时间复杂度为O（N）
(3)Leetcode 242 Valid Anagram
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = "anagram", t = "nagaram" Output: true
Example 2:
Input: s = "rat", t = "car" Output: false
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?``
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length()!=t.length())
return false;
int a[26]={0};//开一个大小为26的数组
for(int i=0;i<s.length();i++){
a[s[i]-'a']++;//++
a[t[i]-'a']--;//--
}
for(int i=0;i<26;i++){
if(a[i]!=0)//如果不为0，则说明二者的字母不对应
return false;
}
return true;
}
}; (4)Leetcode 202 Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example:
Input: 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
class Solution {
public:
bool isHappy(int n) {
int sum = 0;
while(n > 0){
sum += pow((n%10),2);
n/=10;
}//进行循环计算平方
if(sum >= 10)
return isHappy(sum);
else if(sum == 1)
return true;
else
return false;
}
}; (5)Leetcode 205 Isomorphic Strings
Given two strings s\ and t\, determine if they are isomorphic.
Two strings are isomorphic if the characters in s\ can be replaced to get t\.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
Example 1:
Input: s = "egg", t = "add" Output: true
Example 2:
Input: s = "foo", t = "bar" Output: false
Example 3:
Input: s = "paper", t = "title" Output: true
Note:
You may assume both s\ and t\ have the same length.
class Solution {
public:
bool isIsomorphic(string s, string t) {
int cs[128] = {0}, ct[128] = {0};
for(int i=0; i<s.size(); i++)
{
if(cs[s[i]] != ct[t[i]]) return false;
else if(!cs[s[i]]) //only record once
{
cs[s[i]] = i+1;
ct[t[i]] = i+1;
}
}
return true;
}
}; (6)Leetcode 290 Word Pattern
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = "abba", str = "dog cat cat dog" Output: true
Example 2:
Input:pattern = "abba", str = "dog cat cat fish" Output: false
Example 3:
Input: pattern = "aaaa", str = "dog cat cat dog" Output: false
Example 4:
Input: pattern = "abba", str = "dog dog dog dog" Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char,int> mp;//建立char与int的映射
unordered_map<string,int> ms;//建立strng和int的映射
istringstream in(str);//将str进行分割，分别复制到in中
int i=0,n=pattern.size();
for(string word;in >> word;++i){//将in中的断复制到word中
if(mp[pattern[i]]!=ms[word])
return false;//如果对应的部分不匹配
mp[pattern[i]]=ms[word]=i+1;
}
return i==n;
}
};//(7)Leetcode 451 Sort Characters By Frequency
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Example 2:
Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.
class Solution {
public:
string frequencySort(string s) {
string res;
unordered_map<char,int> ms;//unordered_map来进行映射存储
for(auto c : s)//使用auto不用担心类型问题
ms[c]++;
priority_queue<pair<int,char>> q;//queue中套pair，按照第一个元素进行排序
for(auto cc : ms)
q.push({cc.second,cc.first});//注意要用{}
while(!q.empty()){
auto tt = q.top();
q.pop();
res.append(tt.first,tt.second);//显示key，存储key和value
}
return res;
}
}; (8)Leetcode 1 Two Sum
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].
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map;
for(int i=0;i<nums.size();i++){
int complement = target - nums[i];//双指针试探
if(map.find(complement)!=map.end()){
int res[2] = {i,map[complement]};
return vector<int>(res,res+2);
}
map[nums[i]]=i;
}
throw invalid_argument("this problem has no solutions");//异常处理
}
}; (9)Leetcode 15 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty())
return result;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(i > 0 && nums[i] == nums[i - 1])
continue;
int target = -nums[i];
int left = i + 1;
int right = nums.size() - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(target == sum){
result.push_back({nums[i],nums[left],nums[right]});
left++;
right--;
while(left < right && nums[left] == nums[left - 1])
left++;
while(left < right && nums[right] == nums[right + 1])
right--;
}
else if(target < sum)
right--;
else
left++;
}
}
return result;
}
};//双指针思想，大致思路与2sum的题目类似 (10)Leetcode 16 3Sum Closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int result = 0;
int diff = 99999;
for(int i = 0 ; i < nums.size() ; i++){
int temp = target - nums[i];
int left = i + 1,right = nums.size() - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(temp == sum){
return target;
}
else{
int absdiff = abs(sum - temp);
if(absdiff < diff){
diff = absdiff;
result = sum + nums[i];
}
if(sum < temp)
left++;
else
right--;
}
}
}
return result;
}
};//本题的基本思想与3sum类似 (11)Leetcode 454 4Sum II
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
assert(A.size() == B.size() && B.size() == C.size() && C.size() == D.size());
unordered_map<int,int> record;
for(int i=0;i<A.size() ;i++)
for(int j=0;j<B.size();j++)
record[A[i] + B[j]]++;
int res = 0;
for(int i=0;i<C.size();i++)
for(int j=0;j<D.size();j++)
if(record.find(- C[i] - D[j])!=record.end())
res += record[ - C[i] - D[j]];
return res;
}
};//时空复杂度均为O(n^2) (12)Leetcode 49 Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> res;
for(auto it : strs){
string t(it);
sort(t.begin(),t.end());//将乱序的部分重新排序
res[t].push_back(it);
}
vector<vector<string>> vec;
for(auto it = res.begin();it!=res.end();it++){
vec.push_back(it->second);//将相同的部分的second部分(value部分)插入vec
}
return vec;
}
}; (13)Leetcode 219 Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1 Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> set;
for(int i=0;i<nums.size();i++){
if(set.find(nums[i]) != set.end())
return true;
set.insert(nums[i]);
if(set.size() == k + 1)
set.erase(nums[i-k]);
}
return false;
}
};//滑动窗口的思想,时间复杂度为O（N），空间复杂度为O（k） (14)Leetcode 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> set;
for(int i=0;i<nums.size();i++){
if(set.lower_bound((long long)nums[i]-(long long)t)!=set.end() && *set.lower_bound((long long)nums[i]-(long long)t)<=(long long)nums[i]+(long long)t)
return true;
set.insert(nums[i]);
if(set.size() == k + 1)
set.erase(nums[i-k]);
}
return false;
}
};//注意long long类型 (15)Leetcode 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> set;
for(int i=0;i<nums.size();i++){
if(set.lower_bound((long long)nums[i]-(long long)t)!=set.end() && *set.lower_bound((long long)nums[i]-(long long)t)<=(long long)nums[i]+(long long)t)
return true;//大于nums[i]-t的最小值只要是小于nums[i]+t就返回true
set.insert(nums[i]);
if(set.size() == k + 1)
set.erase(nums[i-k]);
}
return false;
}
}; 4.链表部分
(1)Leetcode 206 Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* tail = cur->next;
cur->next = pre;
pre = cur;
cur = tail;
}
return pre;
}
};//使用三指针进行标记，然后分别进行逆转，注意不要断链 (2)Leetcode 83 Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2 Output: 1->2
Example 2:
Input: 1->1->2->3->3 Output: 1->2->3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* temp = head;
while(temp != NULL && temp->next != NULL){
if(temp->next->val == temp->val){
ListNode* cur = temp->next;
temp->next = temp->next->next;
delete(cur);//释放掉相应的空间
}
else{
temp=temp->next;
}
}
return head;
}
};//简单的链表删除操作 (3)Leetcode 86 Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head == NULL || head->next == NULL)
return head;//对条件进行特判
ListNode* temp = new ListNode(0);//新建节点
ListNode* temp1 = new ListNode(0);
ListNode* temp2 = temp;//用于保存节点
ListNode* temp3 = temp1;
while(head != NULL){
if(head->val < x){
temp->next = head;
temp = temp->next;
}
else{
temp1->next = head;
temp1 = temp1->next;
}
head = head->next;
}
temp1->next = NULL;//一定要处理好最后的next，卡了很长时间
temp->next = temp3->next;
return temp2->next;
}
}; (4)Leetcode 328 Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example 1:
Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL
Example 2:
Input: 2->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL
Note:
- The relative order inside both the even and odd groups should remain as it was in the input.
- The first node is considered odd, the second node even and so on
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode* temp = new ListNode(0);
ListNode* temp1 = new ListNode(0);
ListNode* temp2 = temp;
ListNode* temp3 = temp1;
int index = 1;
while(head != NULL){
if(index % 2 == 1){
temp->next = head;
temp = temp->next;
}
else if(index % 2 == 0){
temp1->next = head;
temp1 = temp1->next;
}
head = head->next;
index++;
}
temp1->next = NULL;
temp->next = temp3->next;
return temp2->next;
}
};//思路和上面的题目类似，但是本体不可以用这个(题目中规定了) /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;//条件的特判
ListNode* odd = head,*evenhead = head->next,*even = evenhead;
while(even && even->next){
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenhead;//将even和odd部分接起来
return head;
}
}; (5)Leetcode 2 Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
/**
* 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* dummyhead = new ListNode(0);
int carry = 0;
ListNode* p = l1,*q = l2,*cur = dummyhead;
while(p || q){
int temp = (p == NULL) ? 0 : p->val;
int temp1 = (q == NULL) ? 0 : q->val;
int end = carry + temp + temp1;
carry = end / 10;
cur->next = new ListNode(end % 10);
cur = cur->next;
if(p != NULL)
p = p->next;
if(q != NULL)
q = q->next;
}
if(carry > 0)
cur->next = new ListNode(carry);
return dummyhead->next;
}
};//核心为设置carry位 (6)Leetcode 445 Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
/**
* 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) {
stack<int> s1,s2;
while(l1){
s1.push(l1->val);
l1 = l1->next;
}
while(l2){
s2.push(l2->val);
l2 = l2->next;
}
int carry = 0;
ListNode* res = new ListNode(0);
while(!s1.empty() || !s2.empty()){
if(!s1.empty()){
carry += s1.top();
s1.pop();
}
if(!s2.empty()){
carry += s2.top();
s2.pop();
}
res->val = carry % 10;
ListNode* head = new ListNode(carry / 10);
head->next = res;
res = head;
carry /= 10;
}
return res->val == 0 ? res->next : res;
}
};//使用栈这个数据结构，大体思路与上一个题类似，都是设置一个carry位，唯一不同的是这个题需要使用尾插法。 (7)Leetcode 203 Remove Linked List Elements
Remove all elements from a linked list of integers that have value val\.
Example:
Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* temp = dummyhead;
while(temp->next != NULL){
if(temp->next->val == val){
ListNode* cur = temp->next;
temp->next = cur->next;
delete cur;
}
else{
temp = temp->next;
}
}
return dummyhead->next;
}
};//设置虚拟的头节点 (8)Leetcode 21 Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* temp = new ListNode(0);
ListNode* cur = new ListNode(0);
cur = temp;
while(l1 && l2){
if(l1->val >= l2->val){
temp->next = l2;
l2 = l2->next;
}
else{
temp->next = l1;
l1 = l1->next;
}
temp = temp->next;
}
if(l1)
temp->next = l1;
else if(l2)
temp->next = l2;
return cur->next;
}
};//归并算法 (9)Leetcode 82 Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5 Output: 1->2->5
Example 2:
Input: 1->1->1->2->3 Output: 2->3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL)
return head;
ListNode* temp = new ListNode(0);
temp->next = head;
head = temp;
while(head->next && head->next->next){
if(head->next->val == head->next->next->val){
int val = head->next->val;
while(head->next && head->next->val == val)
head->next = head->next->next;
}
else{
head = head->next;
}
}
return temp->next;
}
};//建立虚拟的头节点，思路与上一个题目类似 (10)Leetcode 24 Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* p = dummyhead;
while(p->next && p->next->next){
ListNode* node1 = p->next;
ListNode* node2 = node1->next;
ListNode* next = node2->next;
node2->next = node1;
node1->next = next;
p->next = node2;
p = node1;//提前画好图进行表示
}
return dummyhead->next;
}
};//设置多指针进行翻转 (11)Leetcode 148 Sort List
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* slow = head,*fast = head,*pre = head;
while(fast && fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next=NULL;
return mergeList(sortList(head),sortList(slow));
}
ListNode* mergeList(ListNode* l1,ListNode* l2){
ListNode* dummyhead = new ListNode(0);
ListNode* temp = dummyhead;
while(l1 && l2){
if(l1->val > l2->val){
dummyhead->next = l2;
l2 = l2->next;
}
else{
dummyhead->next = l1;
l1 = l1->next;
}
dummyhead = dummyhead->next;
}
if(l1)
dummyhead->next = l1;
if(l2)
dummyhead->next = l2;
return temp->next;
}
};//使用了归并排序 (12)Leetcode 25 Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(head == NULL)
return head;
ListNode* t =head;
for(int i = 0 ;i < k - 1; i++){
t = t->next;
if(t == NULL)
return head;
}//向后移动k-1个位置
t = reverseKGroup(t->next , k);//进行递归，从后往前处理
ListNode* s;
while(k--){//链表的逆转
s = head;
head = head->next;
s->next = t;
t = s;
}
return t;
}
}; (13)Leetcode 237 Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list -- head = [4,5,1,9], which looks like following:
Example 1:
Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Note:
- The linked list will have at least two elements.
- All of the nodes' values will be unique.
- The given node will not be the tail and it will always be a valid node of the linked list.
- Do not return anything from your function.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
if(node == NULL)
return;
if(node->next == NULL){
delete node->next;
node = NULL;
return;
}
ListNode* temp = node->next;
node->val = node->next->val;
node->next = temp->next;
delete temp;
return;
}
};//将node的next部分的节点进行复制，然后进行节点的删除 (14)Leetcode 234 Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* fast = head,*slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
}//设置快慢指针进行移动
if(fast)
slow = slow->next;//考虑奇数的情况
ListNode* cur(slow),*pre = NULL,*temp = NULL;
while(cur){
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}//对后半部分进行逆转
while(pre){
if(pre->val != head->val)
return false;
pre = pre->next;
head = head->next;
}//分别进行比较
return true;
}
};//整体会断链 (15)Leetcode 19 Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head == NULL)
return head;
ListNode* dummyHead = new ListNode(0);//新建一个虚拟的头节点
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = head;
for(int i = 0 ; i < n ; i++)
fast = fast->next;
while(fast != NULL){
fast = fast->next;
slow = slow->next;
}
ListNode* temp = slow->next;
slow->next = temp->next;
delete temp;
return dummyHead->next;
}
};//使用了双指针的思想 (16)Leetcode 143 Reorder List
Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→L**n-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(head == NULL || head->next == NULL || head->next->next == NULL)
return;//进行特判
ListNode* slow = head,*fast = head;
while(fast && fast->next){//设置快慢指针前进
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
slow->next = NULL;
ListNode* cur(mid),*temp = NULL,*pre = NULL;
while( cur ){//对链表进行逆转
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
temp = NULL;
while( head && pre ){//两个链表进行合并
temp = head->next;
head->next = pre;
pre = pre->next;
head->next->next = temp;
head = temp;
}
}
}; 5.栈和队列部分
(1)Leetcode 20 Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()" Output: true
Example 2:
Input: "()[]{}"
Output: trueExample 3:
Input: "(]" Output: false
Example 4:
Input: "([)]" Output: false
Example 5:
Input: "{[]}"
Output: trueclass Solution {
public:
bool isValid(string s) {
stack<char> stack;
for(int i = 0 ; i < s.size() ; i++){
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
stack.push(s[i]);
else{
if(stack.size() == 0)
return false;
char c = stack.top();
stack.pop();
char match;
if(s[i] == ')')
match = '(';
else if(s[i] == ']')
match = '[';
else{
assert(s[i] == '}');
match = '{';
}
if(c != match)
return false;
}
}
if(stack.size() != 0)
return false;// 保证无其他的字符
return true;
}
}; (2).Leetcode 150 Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
Example 1:
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if(tokens.size() == 1)
return stoi(tokens[0]);
stack<int> stack;
for(int i = 0 ; i < tokens.size() ; i++){
if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/" )
stack.push(stoi(tokens[i]));
else{
int num1 = stack.top(); stack.pop();
int num2 = stack.top(); stack.pop();
if (tokens[i] == "+") stack.push(num2 + num1);
if (tokens[i] == "-") stack.push(num2 - num1);
if (tokens[i] == "*") stack.push(num2 * num1);
if (tokens[i] == "/") stack.push(num2 / num1);
}
}
return stack.top();
}
};// 使用栈进行匹配 (3)Leetcode 71 Simplify Path
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
Example 1:
Input: "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: "/../" Output: "/" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: "/home//foo/" Output: "/home/foo" Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:
Input: "/a/./b/../../c/" Output: "/c"
Example 5:
Input: "/a/../../b/../c//.//" Output: "/c"
Example 6:
Input: "/a//b////c/d//././/.." Output: "/a/b/c"
class Solution {
public:
string simplifyPath(string path) {
string res,t;
stringstream ss(path);// stringstream与getline来进行分割
vector<string> temp;
while(getline(ss,t,'/')){
if(t == "." || t == "")// 如果单纯的是.则继续
continue;
if(t == ".." && !temp.empty())// 只有当为..且非根目录的时候才向后退
temp.pop_back();
else if(t != "..")// 专门匹配(.//.的情况)
temp.push_back(t);
}
for(auto sss : temp)
res += "/" + sss;// 每次遍历都加上/
return res.size() == 0 ? "/" : res;// 如果最后没有元素了，则返回/
}
}; (4)Leetcode 144 Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]Follow up: Recursive solution is trivial, could you do it iteratively?
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
helper(root, res);
return res;
}
void helper(TreeNode* root, vector<int>& res) {// 必须使用&，因为res要进行改变
if(root) {
res.push_back(root->val);
if(root->left) helper(root->left, res);
if(root->right) helper(root->right, res);
}
}
}; (5)Leetcode 102 Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its level order traversal as:
[ [3], [9,20], [15,7] ]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
queue< pair<TreeNode*,int> > q;
q.push(make_pair(root,0));
while(!q.empty()) {
TreeNode* node = q.front().first;
int level = q.front().second;
q.pop();
if(level == res.size())
res.push_back(vector<int>());
res[level].push_back(node->val);
if(node->left)
q.push(make_pair(node->left,level+1));
if(node->right)
q.push(make_pair(node->right,level+1));
}
return res;
}
}; (6) Leetcode 107 Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> vec;
if(root == NULL)
return vec;
queue<pair<TreeNode*,int>> que;
que.push(make_pair(root,0));
while(!que.empty()) {
TreeNode* node = que.front().first;
int level = que.front().second;
que.pop();
if(vec.size() == level)// 表明是新产生的节点
vec.push_back(vector<int>());
vec[level].push_back(node->val);
if(node->left)
que.push(make_pair(node->left,level+1));
if(node->right)
que.push(make_pair(node->right,level+1));
}
reverse(vec.begin(),vec.end());
return vec;
}
};// 本题即在上一题的基础上进行一下vec的逆转即可 (7) Leetcode 103 Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
queue<pair<TreeNode*,int>> queue;
queue.push(make_pair(root,0));
while(!queue.empty()) {
TreeNode* node = queue.front().first;
int level = queue.front().second;
queue.pop();
if(res.size() == level)
res.push_back(vector<int>());
res[level].push_back(node->val);
if(node->left)
queue.push(make_pair(node->left,level+1));
if(node->right)
queue.push(make_pair(node->right,level+1));
}
for(int i = 0 ; i < res.size();i++)
if(i % 2 == 1)
reverse(res[i].begin(),res[i].end());
return res;
}
};// 素质三连--- (8) Leetcode 199 Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<vector<int>> res;
vector<int> temp;
if(root == NULL)
return temp;
queue<pair<TreeNode*,int>> queue;
queue.push(make_pair(root,0));
while(!queue.empty()) {
TreeNode* node = queue.front().first;
int level = queue.front().second;
queue.pop();
if(res.size() == level)
res.push_back(vector<int>());
res[level].push_back(node->val);
if(node->left)
queue.push(make_pair(node->left,level+1));
if(node->right)
queue.push(make_pair(node->right,level+1));
}
for(int i = 0 ; i < res.size() ;i++) {
reverse(res[i].begin(),res[i].end());
temp.push_back(res[i].front());
}
return temp;
}
}; (8)Leetcode 279 Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
class Solution {
public:
int numSquares(int n) {
assert(n > 0);
queue<pair<int,int>> queue;
queue.push(make_pair(n,0));
vector<bool> visited(n+1,false);
visited[n] = true;
while(!queue.empty()) {
int num = queue.front().first;// 第几个数字
int step = queue.front().second;// 经过了几步
queue.pop();
if(num == 0)
return step;
for( int i = 1 ; ; i++ ) {
int a = num - i * i;
if(a < 0)
break;
if(a == 0)
return step + 1;
if(!visited[a]) {
queue.push(make_pair(a , step + 1));
visited[a] = true;
}
}
}
throw invalid_argument("No Solution");
}
}; (9)priority_queue
priority_queue默认为一个最大堆
priority_queue<int,vector<int>,greater<int>> pq;将会改变为最小堆 </int></int>
bool myCmp(int a,int b){ return a%10 < b%10; } priority_queue<int,vector<int>,function<bool(int,int)>> pq3(myCmp);- 自定义堆
(10)Leetcode 347 Top K Frequent Elements
Given a non-empty array of integers, return the k\ most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
assert(k > 0);
unordered_map<int,int> freq;// 底层为哈希表，时间复杂度O(1)
for(int i = 0 ; i < nums.size() ;i++)
freq[nums[i]]++;// 将每一个元素出现的次数插入到freq中
assert(k <= freq.size());
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;// 定义一个最小堆，有助于pop之后重新插入
for(auto temp : freq){
if(pq.size() == k){
if(temp.second >= pq.top().first){// 更新最小堆
pq.pop();
pq.push(make_pair(temp.second,temp.first));
}
}else{
pq.push(make_pair(temp.second,temp.first));// 直接插入
}
}
vector<int> res;
while(!pq.empty()){
res.push_back(pq.top().second);// 将res中的数据全部插入
pq.pop();
}
return res;
}
};// 维护一个最小堆 class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
priority_queue<pair<int, int>> q;
vector<int> res;
for (auto a : nums) ++m[a];
for (auto it : m) q.push({it.second, it.first});
for (int i = 0; i < k; ++i) {
res.push_back(q.top().second); q.pop();
}
return res;
}
};// 直接维护一个最大堆 6.二叉树部分
(1)Leetcode 226 Invert Binary Tree
Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return NULL;
invertTree(root->left);
invertTree(root->right);
swap(root->left,root->right);
return root;
}
};// 递归处理 (2)Leetcode 111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its minimum depth = 2.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL)
return 0;
if(root->left && root->right)
return min(minDepth(root->left),minDepth(root->right)) + 1;
else // 考虑只有一个孩子的情况
return max(minDepth(root->left),minDepth(root->right)) + 1;
}
}; (3)Leetcode 257 Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
if(root != NULL)
recursive(root,"",ans);
return ans;
}
void recursive(TreeNode* root,string path,vector<string>& ans){
if(root->left == NULL && root->right ==NULL)
ans.push_back(path + to_string(root->val));
if(root->left != NULL)
recursive(root->left,path+ to_string(root->val) + "->",ans);
if(root->right != NULL)
recursive(root->right,path+ to_string(root->val) + "->" ,ans);
}
};// 思路类似于前序遍历 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(root == NULL)
return res;
if(root->left == NULL && root->right == NULL){
res.push_back(to_string(root->val));
return res;
}
vector<string> lefts= binaryTreePaths(root->left);
for(int i = 0 ;i < lefts.size();i++)
res.push_back(to_string(root->val) + "->" + lefts[i]);
vector<string> rights= binaryTreePaths(root->right);
for(int i = 0 ;i < rights.size();i++)
res.push_back(to_string(root->val) + "->" + rights[i]);
return res;
}
}; (4)Leetcode 100 Same Tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: trueExample 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: falseExample 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q == NULL)
return true;
if(p == NULL || q == NULL)
return false;
if(q->val != p->val)
return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
}; (5)Leetcode 101 Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == NULL)
return true;
return isSameTree(root->left,root->right);
}
bool isSameTree(TreeNode* root1,TreeNode* root2) {
if(root1 == NULL && root2 == NULL)
return true;
if(root1 == NULL || root2 == NULL)
return false;
if(root1->val != root2->val)
return false;
return isSameTree(root1->right,root2->left)&&isSameTree(root1->left,root2->right);
}
};// easy (6)Leetcode 110 Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4Return false.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == NULL)
return true;
if(abs(Height(root->left) - Height(root->right)) > 1)
return false;// 判断是不是平衡二叉树
return isBalanced(root->left) && isBalanced(root->right);// 递归判断
}
int Height(TreeNode* root){
if(root == NULL)
return 0;
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
return max(leftHeight,rightHeight) + 1;
}
}; (7)Leetcode 112 Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == NULL)
return false;
if(root->left == NULL && root->right == NULL && root->val == sum)
return true;// 只有当加到叶子节点且值为sum的时候才可以返回true
return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
}
}; (8)Leetcode 113 Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1Return:
[ [5,4,11,2], [5,8,4,5] ]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if(root == NULL)
return res;
vector<int> temp;
findPath(root,res,temp,sum);
return res;
}
void findPath(TreeNode* root,vector<vector<int>>& res,vector<int>& temp,int sum) {
if(root == NULL)
return ;
temp.push_back(root->val);
if(sum == root->val && root->left == NULL && root->right == NULL)
res.push_back(temp);
findPath(root->left,res,temp,sum-root->val);
findPath(root->right,res,temp,sum-root->val);
temp.pop_back();
}
};(9)Leetcode 437 Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if(root == NULL)
return 0;
return pathSum(root->left,sum)+pathSum(root->right,sum)+helper(root,sum);
}
int helper(TreeNode* node,int sum) {
int ins = 0;
if(node == NULL)
return 0;
if(node->val == sum)
ins = 1;// 累加总共有几个满足的数字
return helper(node->left,sum-node->val) + helper(node->right,sum-node->val) + ins;
}
}; (10)Leetcode 235 Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the BST.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL)
return root;
if(p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right,p,q);// 递归遍历右侧
if(p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left,p,q);// 递归遍历左侧
return root;// 如果p和q一个大于root，一个小于root，则返回root
}
}; (11)Leetcode 98 Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3 Input: [2,1,3] Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4./**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
int flag = 0;
int tree[10010];
public:
void dfs(TreeNode* root) {// 首先进行先序遍历，得到递增序列
if(root != NULL){
dfs(root->left);
tree[flag++]=root->val;
dfs(root->right);
}
}
bool isValidBST(TreeNode* root) {// dfs一趟之后进行判断
dfs(root);
for(int i = 0 ; i < flag - 1;i++){
if(tree[i + 1] <= tree[i])
return false;
}
return true;
}
}; /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root,LONG_MIN,LONG_MAX);// 注意long类型，使用int处理的位数有限
}
bool isValidBST(TreeNode* root, long min,long max) {// 进行边界判断
if(root == NULL)
return true;
if(root->val <= min || root->val >= max)
return false;
return isValidBST(root->left,min,root->val)&&isValidBST(root->right,root->val,max);
}
};// 递归进行处理 (12)Leetcode 129 Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026./**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int tosum;
public:
void handle(string str,TreeNode* root){
if(root == NULL)
return ;
if(root->left)
handle(str+to_string(root->val),root->left);
if(root->right)
handle(str+to_string(root->val),root->right);
if(!root->left && !root->right)
tosum += stoi(str+to_string(root->val));
}
int sumNumbers(TreeNode* root) {
handle("",root);
return tosum;
}
};// 算法思想与257类似 (13)Leetcode 108 Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums,0,nums.size()-1);
}
TreeNode* helper(vector<int>& nums,int left,int right) {
if(left > right)
return NULL;
int mid = left + (right - left) / 2;// 防止溢出
TreeNode *cur = new TreeNode(nums[mid]);
cur->left = helper(nums, left, mid - 1);
cur->right = helper(nums, mid + 1, right);
return cur;
}
};// 所利用的就是二分的思想，不断的进行二分插入 (14)Leetcode 236 Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the binary tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL)
return NULL;
if(root == p || root == q)// 如果找到了则返回当前的root
return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left && right)// 如果两个节点分别位于root两侧，则共同祖先为root
return root;
else// 否则为left或者是right
return left == NULL ? right : left;
}
};// LCA问题 
投递腾讯等公司10个岗位 >
字节跳动开奖28人在聊