leetcode解题思路分析（一）1-7题

朴灿烈づ我的快乐病毒、 2023-06-18 06:00 8阅读 0赞

### 简介 ###

本文leetcode刷题前7道题，分享思路和答案以及优化方案

### 题目 ###

1.  两数之和  
    给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。  
    你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**（1）最简单的办法是遍历操作，但是十分笨重，会超过时间限制**

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> result;
            map<int, int> mapNums;
            size_t count = nums.capacity();
    
            for (int i = 0; i < count; i++)
            { 
                mapNums[i] = nums[i];
            }
    
            for (int i = 0; i < count; i++)
            { 
                for (int j = i + 1; j < count; j++)
                { 
                    if (mapNums[i] + mapNums[j] == target)
                    { 
                        result.push_back(i);
                        result.push_back(j);
                        return result;
                    }
                }
            }
    
            return result;
        }
    };

**（2）改用map存储和查找，时间复杂度较低**

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> result;
            map<int, int> mapNums;
            size_t count = nums.capacity();
    
            for (int i = 0; i < count; i++)
            { 
                mapNums[nums[i]] = i;
            }
    
            for (int i = 0; i < count; i++)
            { 
                int complete = target - nums[i];
                if (mapNums.find(complete) != mapNums.end() && mapNums[complete] != i)
                {                
                    result.push_back(i);
                    result.push_back(mapNums[complete]);
                    return result;
                }
            }
    
            return result;
        }
    };

**（3）改用unordered\_map存储，即哈希表，并且不一次性存储，而是边检查边存储，少一遍遍历时间**

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            //Key是数字，value是该数字的index
            unordered_map<int, int> hash;
            vector<int> result;
            int numsSize = int(nums.size());
            for (int i = 0; i < numsSize; i++)
            { 
                int numberToFind = target - nums[i];
    
                //如果找到numberToFind，就return
                if (hash.find(numberToFind) != hash.end())
                { 
                    result.push_back(hash[numberToFind]);
                    result.push_back(i);
                    return result;
                }
    
                //如果没有找到，把该数字的index放到hash表中
                hash[nums[i]] = i;
            }
            return result;
        }
    };

1.  两数相加  
    给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。  
    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。  
    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**直接链表操作即可，考察基本的链表遍历、插入操作**

/** * 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) { 
            int count = 0;
            ListNode *num = new ListNode(-1);
            ListNode *ptr = num;
            
            while (l1 || l2)
            { 
                int sum=0;
                if(l1)
                { 
                    sum += l1->val;
                    l1 = l1->next;
                }
                if(l2)
                { 
                    sum += l2->val;
                    l2 = l2->next;
                }
    
                sum += count;
                if (sum >= 10)
                { 
                    count = 1;
                }
                else
                { 
                    count = 0;
                }
    
                ptr = ptr->next = new ListNode(sum % 10) ;
            }
    
            if (count)
                 ptr = ptr->next = new ListNode(1) ;           
    
            return num->next;
        }
    };

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

**本题采用滑动窗口解决**

class Solution { 
    public:
        int lengthOfLongestSubstring(string s) { 
    
            int start, end, size, maxSubString, len;
            char val; 
    
            start = end = len = maxSubString = 0;
            size = s.size();
    
            while (end < size)
            { 
                val = s[end];
                for (int i = start; i < end; i++)
                { 
                    if (s[i] == val)
                    { 
                        start = i + 1;
                        len = end - start;
                        break;
                    }
                }
    
                end++;
                len++;
                maxSubString = max(maxSubString, len);
            }
    
            return maxSubString;
        }
    };

**改用哈希表、堆之后效果反而不佳，建议还是使用滑动窗口解决**

class Solution
    { 
    public:
        int lengthOfLongestSubstring(string s)
        { 
            //s[start,end) 前面包含 后面不包含
            int start(0), end(0), length(0), result(0);
            int sSize = int(s.size());
            unordered_map<char, int> hash;
            while (end < sSize)
            { 
                char tmpChar = s[end];
                //仅当s[start,end) 中存在s[end]时更新start
                if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
                { 
                    start = hash[tmpChar] + 1;
                    length = end - start;
                }
                hash[tmpChar] = end;
    
                end++;
                length++;
                result = max(result, length);
            }
            return result;
        }
    };

class Solution
    { 
    public:
        int lengthOfLongestSubstring(string s)
        { 
            //s[start,end) 前面包含 后面不包含
            int start(0), end(0), length(0), result(0);
            int sSize = int(s.size());
            vector<int> vec(128, -1);
            while (end < sSize)
            { 
                char tmpChar = s[end];
                //仅当s[start,end) 中存在s[end]时更新start
                if (vec[int(tmpChar)] >= start)
                { 
                    start = vec[int(tmpChar)] + 1;
                    length = end - start;
                }
                vec[int(tmpChar)] = end;
    
                end++;
                length++;
                result = max(result, length);
            }
            return result;
        }
    };

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

**本题规定时间复杂度为Log，因此使用二分法可满足要求**

class Solution { 
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
    		int n = nums1.size();
    		int m = nums2.size();
    
    		if (n > m)  //保证数组1一定最短
    		{ 
    			return findMedianSortedArrays(nums2, nums1);
    		}
    
    		// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
    		int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度
    
    		while (lo <= hi)   //二分
    		{ 
    			c1 = (lo + hi) / 2;  //c1是二分的结果
    			c2 = m + n - c1;
    
    			LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
    			RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
    			LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
    			RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
    
    			if (LMax1 > RMin2)
    				hi = c1 - 1;
    			else if (LMax2 > RMin1)
    				lo = c1 + 1;
    			else
    				break;
    		}
    		return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
        }
    };

1.  最长回文子串  
    给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。  
    示例 1：  
    输入: “babad”  
    输出: “bab”  
    注意: “aba” 也是一个有效答案。  
    示例 2：  
    输入: “cbbd”  
    输出: “bb”

**本题采用动态规划解决：`P(i, j) = (P(i + 1, j − 1) and S i == S j )`**

class Solution { 
    public:
        string longestPalindrome(string s) { 
    
            int len = s.size();
    
            if (len == 0 || len == 1)
                return s;
    
            int start = 0, max = 1;
            int isPalin[len][len] = { 0};
    
            for (int i = 0; i < len; i++)
            { 
                isPalin[i][i] = 1;
                if (i < len -1 && s[i] == s[i + 1])
                { 
                    isPalin[i][i + 1] = 1;
                    max = 2;
                    start = i;
                }
            }
    
            for (int l = 3; l <= len; l++)
            { 
                for (int i = 0; i + l - 1 < len; i++)
                { 
                    int end = i + l - 1;
                    if (s[i] == s[end] && isPalin[i + 1][end - 1] == 1 )
                    { 
                        isPalin[i][end] = 1;
                        max = l;
                        start = i;
                    }
                }
            }
    
            return s.substr(start, max);
            
        }
    };

**更优解法是中心扩展法：回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1 个这样的中心。此处n表示插入元素间隔的个数：因为偶数回文会在字母之间。执行时间可减少300%，内存消耗增大。**

//采用内联追求极限性能
    inline 	int expandAroundCenter(string s, int left, int right)
    	{ 
    		int L = left, R = right;
    		while (L >= 0 && R < s.length() && s[L] == s[R])
    		{ // 计算以left和right为中心的回文串长度
    			L--;
    			R++;
    		}
    		return R - L - 1;
    	}
    
    class Solution{ 
            public:
        string longestPalindrome(string s) 
    	{ 
    		if (s.length() < 1)
    		{ 
    			return "";
    		}
    		int start = 0, end = 0;
    		for (int i = 0; i < s.length(); i++)
    		{ 
    			int len1 = expandAroundCenter(s, i, i);//一个元素为中心
    			int len2 = expandAroundCenter(s, i, i + 1);//两个元素为中心
    			int len = max(len1, len2);
    			if (len > end - start)
    			{ 
    				start = i - (len - 1) / 2;
    				end = i + len / 2;
    			}
    		}
    		return s.substr(start, end - start + 1);
    	}
    
    };

**最优解法：Manacher 算法。时间空间复杂度均极优。**

class Solution{ 
    public:
    string longestPalindrome(string s)
    { 
    	int len = s.length();
    	if (len < 1)
    	{ 
    		return "";
    	}
    
    	// 预处理
    	string s1;
    	for (int i = 0; i < len; i++)
    	{ 
    		s1 += "#";
    		s1 += s[i];
    	}
    	s1 += "#";
    
    	len = s1.length();
    	int MaxRight = 0;				// 当前访问到的所有回文子串，所能触及的最右一个字符的位置
    	int pos = 0;					// MaxRight对应的回文串的对称轴所在的位置
    	int MaxRL = 0;					// 最大回文串的回文半径
    	int MaxPos = 0;					// MaxRL对应的回文串的对称轴所在的位置
    	int RL[len] = { 0};			// RL[i]表示以第i个字符为对称轴的回文串的回文半径
    
    	for (int i = 0; i < len; i++)
    	{ 
    		if (i < MaxRight)
    		{ // 1) 当i在MaxRight的左边
    			RL[i] = min(RL[2 * pos - i], MaxRight - i);
    		}
    		else
    		{ // 2) 当i在MaxRight的右边
    			RL[i] = 1;
    		}
    
    
    		// 尝试扩展RL[i]，注意处理边界
    		while (i - RL[i] >= 0  // 可以把RL[i]理解为左半径,即回文串的起始位不能小于0
    			&& i + RL[i] < len // 同上,即回文串的结束位不能大于总长
    			&& s1[i - RL[i]] == s1[i + RL[i]]// 回文串特性，左右扩展，判断字符串是否相同
    			)
    		{ 
    			RL[i] += 1;
    		}
    
    		// 更新MaxRight, pos
    		if (RL[i] + i - 1 > MaxRight)
    		{ 
    			MaxRight = RL[i] + i - 1;
    			pos = i;
    		}
    
    		// 更新MaxRL, MaxPos
    		if (MaxRL <= RL[i])
    		{ 
    			MaxRL = RL[i];
    			MaxPos = i;
    		}
    	}
    	return s.substr((MaxPos - MaxRL + 1) / 2, MaxRL - 1);
    }
    
    };

1.  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);

**本题重点在于不要定时思维：我们并不需要一个row \* coloum的数组，我们需要的仅仅是row个vector即可，每个存储一行，连起来就是答案。存储的时候只需要循环考虑当前读取顺序：要么向下要么向上**

class Solution { 
    public:
        string convert(string s, int numRows) { 
    
            if (numRows == 1) return s;
    
            vector<string> rows(min(numRows, int(s.size())));
            int curRow = 0;
            bool goingDown = false;
    
            for (char c : s) { 
                rows[curRow] += c;
                if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
                curRow += goingDown ? 1 : -1;
            }
    
            string ret;
            for (string row : rows) ret += row;
            return ret;
        }
    };

**除了上下循环以外，其实我们可以计算int cycleLen = 2 \* numRows - 2，即找到存储的规律，直接循环存储即可，更利于理解，实际性能相差不大**

class Solution { 
    public:
        string convert(string s, int numRows) { 
    
            if (numRows == 1) return s;
    
            string ret;
            int n = s.size();
            int cycleLen = 2 * numRows - 2;
    
            for (int i = 0; i < numRows; i++) { 
                for (int j = 0; j + i < n; j += cycleLen) { 
                    ret += s[j + i];
                    if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                        ret += s[j + cycleLen - i];
                }
            }
            return ret;
        }
    };

1.  整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

**本题并无太多花样，仅仅是边界条件的考虑而已，记住就好**

class Solution { 
    public:
        int reverse(int x) { 
            int rev = 0;
            while (x != 0) { 
                int pop = x % 10;
                x /= 10;
                if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
                if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
                rev = rev * 10 + pop;
            }
            return rev;
        }
    };