一些有意思的算法题目（持续更新）

- 日理万妓 2023-01-18 04:01 160阅读 0赞

## 第一题 ##

> 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
> 
> 示例 1:
> 
> 输入: s = “abcabcbb” 输出: 3  
> 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
> 
> 示例 2:
> 
> 输入: s = “bbbbb” 输出: 1  
> 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
> 
> 示例 3:
> 
> 输入: s = “pwwkew” 输出: 3  
> 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
> 
> 示例 4:
> 
> 输入: s = “” 输出: 0

class Solution { 
    public:
    //滑动窗口方法
        int lengthOfLongestSubstring(string s) { 
            //出现过的字符
           unordered_set<char> unS;
           int n= s.size();
           //窗口最右边的指针 所求的子串长度
           int rP=-1,len=0;
           //i为窗口最左边指针 
           for(int i=0;i<n;i++){ 
               if(i!=0){ 
                   unS.erase(s[i-1]);
               }
               //循环字符串 查看是否有和unS重复的
               //如果没有就往unS里加入一个
               while(rP+1<n&&!unS.count(s[rP+1])){ 
                   unS.insert(s[rP+1]);
                   ++rP;
               }
               len=max(len,rP-i+1);
           }
           return len;
           }
    };

## 第二题 ##

给你一个字符串 s，找到 s 中最长的回文子串。

> 示例 1：
> 
> 输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。
> 
> 示例 2：
> 
> 输入：s = “cbbd” 输出：“bb”
> 
> 示例 3：
> 
> 输入：s = “a” 输出：“a”
> 
> 示例 4：
> 
> 输入：s = “ac” 输出：“a”

**解法一：暴力解法**  
时间复杂度O(n³)  
空间复杂度O(1)

class Solution { 
    public:
       string longestPalindrome(string s) { 
       		//判断是否是回文子串
    		bool isR = true;
    		string aim；
    		if(s.size()<2){ 
    		return s;
    		}
    		//遍历子串
    		//左边界逐个加一
    		for (auto i = s.begin(); i != s.end(); i++){ 
    			//右边界逐个减一
    			for (auto j = s.end(); j > i; j--){ 
    				//判断是否是回文子串
    				for (auto k =i, z = j - 1; k < z; k++, z--)
    				{ 
    					if (*k != *z)
    					{ 
    						isR = false;
    						break;
    					}
    					if (*k == *z&&(z - k == 2||z-k==1)){ 
    						isR = true;
    						break;
    					}
    				}
    				//如果是 比较跟目标字符串的大小
    				if (isR&&aim.size() < j-i){ 
    					aim.assign(i,j);
    				}
    			}
    		}
    		//返回目标字符串
    		return aim;
    	}
    };

解法二：动态规划

class Solution { 
    public:
       string longestPalindrome(string s) { 
    		int n= s.size();
            int len=1;
            int start=0;
            if(n<2){ 
                return s;
            }
            //dp 为二维数组用来表示dp[i][j]是否是回文子串
            //有n行 n列个 （其实有一半是用不到的，因为j一定会大于2）
            vector<vector<int>> dp(n,vector<int>(n));
            //单个长度的子串一定是回文子串
            for(int i=0;i<n;i++){ 
                dp[i][i]=true;
            }
            //遍历子串长度 先从长度为2的子串开始
            for(int L=2;L<=n;L++){ 
                //从左边界开始
                for(int j=0;j<n;j++){ 
                    //右边界 由r-j+1=n得来
                   int r=L+j-1;
                    //超出边界
                    if(r>=n){ 
                        break;
                    }
                    //如果相等
                    if(s[j]==s[r]){ 
                        //见答案详解
                        if(r-j<3){ 
                            dp[j][r]=true;
                        }else{ 
                            //是否是回文取决于里面的子串
                            dp[j][r]=dp[j+1][r-1];
                        }
                    }else{ 
                        dp[j][r]=false;
                    }
                    //如果长度大于之前的最长，则赋值过去
                    if(r-j+1>len&&dp[j][r]){ 
                        start=j;
                        len=r-j+1;
                    }
                }
            }
            //截取字符串
            return s.substr(start,len);
        }
    };

> 思路与算法  
> https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

## 第三题 ##

> 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
> 
> 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
> 
> P A H N A P L S I I G Y I R
> 
> 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
> 
> 请你实现这个将字符串进行指定行数变换的函数：
> 
> string convert(string s, int numRows);
> 
> 示例 1：
> 
> 输入：s = “PAYPALISHIRING”, numRows = 3 输出：“PAHNAPLSIIGYIR”
> 
> 示例 2：
> 
> 输入：s = “PAYPALISHIRING”, numRows = 4 输出：“PINALSIGYAHRPI” 解释： P I  
> N A L S I G Y A H R P I
> 
> 示例 3：
> 
> 输入：s = “A”, numRows = 1 输出：“A”

**解法一：**  
按行读取

class Solution { 
    public:
        string convert(string s, int numRows) { 
            //目标字符串
            string aim;
            //当前列
            int curC=0;
            int len=s.size();
            if(numRows==1){ 
                return s;
            }
            //遍历每一列
            for(int i=0;i<=numRows-1;i++){ 
                //当为第一和最后一列时
                if(i==0||i==numRows-1){ 
                    curC=0;
                    //每(2*current-2)个字符串取一个数字
                    while(curC+i<len){ 
                       aim.push_back(s[curC+i]);
                        curC+=2*numRows-2;
                   }    
                }else{ 
                    curC=0;
                    //当不为第一和最后一行时
                    while(curC+i<len){ 
                        //每(2*current-2)个字符串取一个数字
                        aim.push_back(s[curC+i]);
                        int temp=2*(numRows-i)-2+curC+i;
                        //每(2*(current-i)-2)个字符串取一个数字
                        temp<len ? aim.push_back(s[temp]):break;
                        curC+=2*numRows-2;
                    }
                }
            }
            return aim;
        }
    };

**解法二：**  
官方的解法，个人感觉很有意思

> 按行排序 思路
> 
> 通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。
> 
> 算法
> 
> 我们可以使用 `min(numRows,len(s))` 个列表来表示 Z 字形图案中的非空行。
> 
> 从左到右迭代 sss，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。
> 
> 只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。

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;
        }
    };

## 第四题 ##

题目：

> 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
> 
> 注意：答案中不可以包含重复的三元组。
> 
> 示例 1：
> 
> 输入：nums = \[-1,0,1,2,-1,-4\] 输出：\[\[-1,-1,2\],\[-1,0,1\]\]
> 
> 示例 2：
> 
> 输入：nums = \[\] 输出：\[\]
> 
> 示例 3：
> 
> 输入：nums = \[0\] 输出：\[\]

**解法：排序+双指针**  
个人认为这题最让人惊艳的是能够想到使用排序。从根本上解决了最后数组会重复的问题，且减少了循环的次数

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            int len=nums.size();
            sort(nums.begin(),nums.end());
            vector<vector<int>> aim;
            for(int first=0;first<len;first++){ 
                if(first>0&&nums[first]==nums[first-1]){ 
                    continue;
                }
                int third=len-1;
                int target=-nums[first];
                for(int second=first+1;second<len;second++){ 
                    if(second>first+1&&nums[second]==nums[second-1]){ 
                        continue;
                    }
                    while(third>second){ 
                        if(nums[second]+nums[third]>target){ 
                            third--;
                        }else{ 
                            break;
                        }
                    }
                    if(second==third)
                        break;
                    if(nums[second]+nums[third]==target){ 
                        aim.push_back({ nums[first],nums[second],nums[third]});
                    }
                }
            }
            return aim;
        }
    };

## 第五题 ##

**题目：**

> 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
> 
> 示例：
> 
> 输入：nums = \[-1,2,1,-4\], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 +  
> 1 = 2) 。

**答案：用的还是双指针加排序**

class Solution { 
    public:
        int threeSumClosest(vector<int>& nums, int target) { 
            sort(nums.begin(), nums.end());
            int len=nums.size();
            int min=1e7;
            for(int i=0;i<len;i++){ 
                if(i!=0&&nums[i]==nums[i-1])
                    i++;    
                int left=i+1;
                int right=len-1;
                while(left<right){ 
                    int sum=nums[i]+nums[left]+nums[right];
                    if(sum==target)
                        return sum;
                    if(abs(min-target)>abs(sum-target)){ 
                        min=sum;
                    }
                    if(sum>target){ 
                        right--;
                        if(right!=len-1&&nums[right]==nums[right+1]){ 
                            right--;
                        }
                    }else{ 
                        left++;
                        if(left!=i+1&&nums[left]==nums[left-1])
                            left++;
                    }
                } 
            }
            return min;
        }
    };

## 第五题 ##

> 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
> 
> 例如，给出
> 
> 前序遍历 preorder = \[3,9,20,15,7\] 中序遍历 inorder = \[9,3,15,20,7\]
> 
> 返回如下的二叉树：
> 
>     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:
        unordered_map<int,int> index;
    
        TreeNode* MyTree(vector<int>& preorder,vector<int>& inorder,int preorder_left,
        int preorder_right,int inorder_left,int inorder_right){ 
            if(preorder_left>preorder_right){ 
                return NULL;
            }
            // -- 前序遍历中的第一个节点一定是根节点
            //中序遍历中，根节点的位置
            int root_index = index[preorder[preorder_left]];
            //计算左子树的大小
            int remain = root_index - inorder_left;
            //创建跟节点树
            TreeNode* headNode = new TreeNode(preorder[preorder_left]);
            //创建左子树
            headNode->left = MyTree(preorder,inorder,preorder_left+1,preorder_left+remain,inorder_left,root_index-1);
            //创建右子树
            headNode->right = MyTree(preorder,inorder,preorder_left+1+remain,preorder_right,root_index+1,inorder_right);
            return headNode;
        }
    
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
           for(int i =  0 ;i <inorder.size();i++){ 
               index[inorder[i]]=i;
           }
           int n = preorder.size();
           return MyTree(preorder,inorder,0,n-1,0,n-1);
    
        }
    };

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum-closest  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。