leetcode解题思路分析（三）15-21题

墨蓝 2023-06-22 08:22 9阅读 0赞

1.  三数求和

**最简单的做法就是三重循环判断：**

int length=nums.length;
        for(int i=0;i<length;i++){ 
            for(int j=i+1;j<length;j++){ 
                for(int k=j+1;k<length;k++){ 
                    if(nums(i)+nums[j]+nums[k]==0){ 
                        ...
                    }
                }
            }  
        }

**在此基础上，对第三次查找其实可以做优化：只需要找指定的数字即可，所以可以通过哈希、排序等方式获得，通过二分法降低时间复杂度**

**更优的做法是将内部二层循环改为首尾双指针滑动判断：因为内层双循环寻找固定的值，而且要求不重复，因此排序之后从首尾开始判断并滑动得出结果即可。时间复杂度NlogN**

class Solution { 
    public:
    	vector<vector<int>> threeSum(vector<int>& nums) { 
    		int target = 0, val = 0, begin, end;
            int size = nums.size();
    		vector<int> tmp;
    		vector<int>::iterator beginIter, endIter;
    		vector<vector<int>> ret;
    
    		if (size <= 2)
    			return ret;
    
    		sort(nums.begin(), nums.end());
    		for (int i = 0; i < size - 2; i++)
    		{ 
    			target = 0 - nums[i];
    			if (target < 0)
    				break;
    
    			beginIter = nums.begin() + i + 1;
    			endIter = nums.end() - 1;
    
    			while (beginIter < endIter)
    			{ 
    				begin = *beginIter;
                    end = *endIter;
    				val = begin + end;
    				if (val == target)
    				{ 
    					tmp.push_back(nums[i]);
    					tmp.push_back(*beginIter);
    					tmp.push_back(*endIter);
    					ret.push_back(tmp);
    					tmp.clear();
    					while (beginIter < endIter && *beginIter == begin)
    						beginIter++;
    					while (beginIter < endIter && *endIter == end)
    						endIter--;
    
    				}
    				else if (val < target)
    				{ 
    					beginIter++;
    				}
    				else
    				{ 
    					endIter--;
    				}
    			}
    
    			while (i < size - 2 && nums[i] == nums[i + 1])
    				i++;
    		}
    
    		return ret;
    	}
    };

1.  最接近的三数之和  
    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

在做完上题之后这题变得异常简单，只需要增加一个绝对值判断即可。

class Solution { 
    public:
        int threeSumClosest(vector<int>& nums, int target) { 
    		int val = 0, begin, end, ret = 0, inTarget, gap;
    		int size = nums.size();
    		vector<int>::iterator beginIter, endIter;
    
    		if (size <= 2)
    			return 0;
    
    		gap = INT_MAX;
    
    		sort(nums.begin(), nums.end());
    		for (int i = 0; i < size - 2; i++)
    		{ 
    			inTarget = target - nums[i];
    
    			beginIter = nums.begin() + i + 1;
    			endIter = nums.end() - 1;
    
    			while (beginIter < endIter)
    			{ 
    				begin = *beginIter;
    				end = *endIter;
    				val = begin + end;
    				if (val == inTarget)
    				{ 
    					return target;
    				}
    				else if (val < inTarget)
    				{ 
    					beginIter++;
    				}
    				else
    				{ 
    					endIter--;
    				}
    
    				if (abs(val - inTarget) < gap)
    				{ 
    					gap = abs(val - inTarget);
    					ret = val + nums[i];
    				}
    			}
    		}
    
    		return ret; 
        }
    };

1.  电话号码的字母组合  
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。  
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

**比较便于理解的做法是采用递归，即深度优先的方式解决，代码也比较简洁易懂。先考虑最后的情况，通过递归回溯完成**

class Solution
    { 
        vector<string> result;
        string digits;
        unordered_map<char, string> store;
    
    public:
        vector<string> letterCombinations(string digits)
        { 
            if (digits.empty())
            { 
                return result;
            }
            this->digits = digits;
            //储存字典
            store = unordered_map<char, string>{ 
                { '2', "abc"}, { '3', "def"}, { '4', "ghi"}, { '5', "jkl"}, { '6', "mno"}, { '7', "pqrs"}, { '8', "tuv"}, { '9', "wxyz"}};
            dfs("", 0);
            return result;
        }
    
        void dfs(string resultStr, int index)
        { 
            int digitsSize = int(this->digits.size());
            if (digitsSize == index)
            { 
                result.push_back(resultStr);
                return;
            }
            char targetChar = this->digits[index];
            string targetStr = store[targetChar];
            for (auto tmpChar : targetStr)
            { 
                dfs(resultStr + tmpChar, index + 1);//递归调用
            }
            return;
        }
    };

**另一种做法当然就是广度优先，从第一位开始顺序向后判断，直至输入结束**

class Solution
    { 
        vector<string> result;
        string digits;
        unordered_map<char, string> store;
    
    public:
        vector<string> letterCombinations(string digits)
        { 
            if (digits.empty())
            { 
                return result;
            }
            this->digits = digits;
            //储存字典
            store = unordered_map<char, string>{ 
                { '2', "abc"}, { '3', "def"}, { '4', "ghi"}, { '5', "jkl"}, { '6', "mno"}, { '7', "pqrs"}, { '8', "tuv"}, { '9', "wxyz"}};
    
            queue<string> workQueue;
            workQueue.push("");
            for (auto targetChar : digits)
            { 
                string targetStr = store[targetChar];
                int queueSize = int(workQueue.size());
                //当前层，进行添加字符
                for (int i = 0; i < queueSize; ++i)
                { 
                    string tmpStr = workQueue.front();
                    workQueue.pop();
                    for (auto tmpChar : targetStr)
                    { 
                        workQueue.push(tmpStr + tmpChar);
                    }
                }
            }
            while (!workQueue.empty())
            { 
                string tmpStr = workQueue.front();
                workQueue.pop();
                result.push_back(tmpStr);
            }
            return result;
        }
    };

1.  四数之和  
    给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

**在前面做完三数之和后，本题显得简单无比，只要在外面再加一层循环嵌套即可**

class Solution { 
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) { 
            if (nums.size() < 4) return { };
            sort(nums.begin(), nums.end());
            int N = nums.size();
            int maxSum3 = nums[N - 3] + nums[N - 2] + nums[N - 1];
            int maxSum2 = nums[N - 2] + nums[N - 1];
            vector<vector<int> > res;
            for (int i = 0; i < N - 3; ++i) { 
                if (4 * nums[i] > target) break;
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                if (nums[i] + maxSum3 < target) continue;
                for (int j = i + 1;j < N - 2; ++j) { 
                    if (2 * (nums[i] + nums[j]) > target) break;
                    if (j > i + 1 && nums[j - 1] == nums[j]) continue;
                    if (nums[i] + nums[j] + maxSum2 < target) continue;
                    int t = target - nums[i] - nums[j];
                    int l = j + 1;
                    int r = N - 1;
                    while (l < r) { 
                        if (nums[l] + nums[r] > t) { 
                            --r;
                        } else if (nums[l] + nums[r] < t) { 
                            ++l;
                        } else { 
                            res.push_back({ nums[i], nums[j], nums[l], nums[r]});
                            while (l < r && nums[l] == nums[++l]);
                            while (l < r && nums[r] == nums[--r]);
                        }
                    }
                }
            }
            return res;
        }
    };

1.  删除链表的倒数第N个节点  
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

**很简单的一种做法是采用一个vector存储每个节点的指针，然后去掉第N个指针即可**

/** * 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) { 
            vector<ListNode*> list;
            ListNode *ptr = head;
            while (ptr != NULL)
            { 
                list.push_back(ptr);
                ptr = ptr->next;
            }
    
            int locate = list.size() - n;
    
            if (locate == 0)
            { 
                return head->next;
            }
    
            ptr = list[locate - 1];
            if (n == 0)
                ptr->next = NULL;  
            else    
                ptr->next = ptr->next->next;
    
            return head;
        }
    };

**更巧妙的做法是采用双指针的方式：两个指针相距为n，则尾指针到底了就表示首指针是要删除的那个节点**

/** * 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) { 
            ListNode *front = head;
            ListNode *rear = head;
    
            if(head->next == NULL) 
                return NULL;
    
            while(n >= 0)
            { 
                if(rear == NULL) 
                    return head -> next;
                rear = rear->next;
                n --;
            }
    
            while(rear)
            { 
                rear = rear -> next;
                front = front -> next;
            }
            
            front->next = front->next->next;
            return head;
        }
    };

1.  有效的括号  
    给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。  
    有效字符串需满足：  
    左括号必须用相同类型的右括号闭合。  
    左括号必须以正确的顺序闭合。  
    注意空字符串可被认为是有效字符串。

**本题采用栈比较容易解决：对左半边括号采取入栈操作，右半边括号和栈顶进行对比，如果不一致则说明有问题**

class Solution { 
    public:
        bool isValid(string s) { 
        if (s.size() == 0) 
            return true;
        char *stack = (char*)malloc(s.size()); 
        int top =0;
        for (int i = 0; s[i]; ++i) { 
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack[top++] = s[i];
            else { 
                if ((--top) < 0) //先减减，让top指向栈顶元素 
                    return false;
                if (s[i] == ')' && stack[top] != '(') 
                    return false;
                if (s[i] == ']' && stack[top] != '[') 
                    return false;
                if (s[i] == '}' && stack[top] != '{') 
                    return false;
            }
        }
        free(stack);
        return (!top);
        }
    };

1.  合并两个有序链表  
    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**本题相对容易，仅需要一个前置指针用于返回，一个滑动指针用于指向目前位置，然后依次判断l1和l2的val大小来赋值即可**

/** * 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 *preHead, *ptr;
    
            preHead = new ListNode(-1);
            ptr = preHead;
    
            while (l1 != NULL && l2 != NULL)
            { 
                if (l1->val <= l2->val)
                {          
                    ptr->next = l1;    
                    l1 = l1->next;                                 
                }
                else
                { 
                    ptr->next = l2;
                    l2 = l2->next;
                }
                ptr = ptr->next;
            }
    
            ptr->next = (l1 == NULL? l2 : l1);
    
            return preHead->next;
        }
    };