代码创作者

这个屌丝很懒，什么也没留下！

热门标签

题海无涯

作者：代码创作者 | 2024-02-05 22:57:12

踩

题海无涯

数组求和统计

牛牛有两个长度为 $n$ 的数组 $a$ , $b$ ，牛牛希望统计有多少数对( $l$ , $r$ )满足
$\leq l \leq r \leq n-1$
$\sum_{i=l}^{r} a_{i}=b_{l}+b_{r}$

//2020.4.13
int countLR(vector<int>& a, vector<int>& b) {
        // write code here
        int ans=0;
        int n=a.size();
        
        for(int i=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum=sum+a[j]; //！！！
                if(sum==b[i]+b[j])
                    ans++;
            }
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

直线上最多的点数

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上

//2020.4.16遍历每一个点，对于其他的点，斜率相同的在一条直线上
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int ans=0;
        for(int i=0;i<points.size();i++)
        {
            int c_count=0; //和当前点垂直点计数
            int repeat=1;   //重复点计数
            map<double,int> m; //斜率和对应次数
            int max_count=0;
            for(int j=0;j!=i && j<points.size();j++)
            {
                if(points[i].x==points[j].x && points[i].y==points[j].y)
                    repeat++;  //重复点
                else if(points[i].x==points[j].x) //垂直
                {
                    c_count++;
                    max_count = max(max_count,c_count);
                }
                else  //有斜率
                {
                    double k=1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x);
                    m[k]++;
                    max_count = max(max_count,m[k]);
                }
            }
            ans = max(ans,max_count+repeat);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

对称的树

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

//2020.4.16
class Solution {
public:
    bool isok(TreeNode *l,TreeNode *r) //递归
    {
        if(!l && !r)
            return true;
        if(l && r)
        {
            if(l->val == r->val)
                return isok(l->left,r->right) && isok(l->right,r->left);
            else
                return false;
        }
        return false;
    }
    bool isSymmetric(TreeNode *root) {
        if(!root)
            return true;
        return isok(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

删除链表中的重复元素

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1->1->2,返回1->2.
给出的链表为1->1->2->3->3,返回1->2->3.

 //2020.4.20
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        
        ListNode* ans = new ListNode(-1);
        ans->next = head;
        ListNode* p = ans;
        
        while(p)
        {
            while(p->next && p->next->next && p->next->val == p->next->next->val)
            {
                p->next = p->next->next;
            }
            p = p->next;
        }
        return ans->next;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

整数反转

将给出的整数x翻转。
例1:x=123，返回321
例2:x=-123，返回-321
例3:x=120，返回21

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [ $2^{31}$ , $2^{31}$ -1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

//2020.4.20
class Solution {
public:
    int reverse(int x) {
        long long ans=0;
        while(x)
        {
            ans = ans*10+x%10;
            x = x/10;
            if(ans>INT_MAX || ans<INT_MIN)
                return 0;
        }
        return ans; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并有序数组

给出两个有序的整数数组A和B，请将数组B合并到数组A中，变成一个有序的数组
注意：
可以假设A数组有足够的空间存放B数组的元素，A和B中初始的元素数目分别为m和n

//2020.4.21
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i=m-1;
        int j=n-1;
        int k=m+n-1;
        for(;i>=0 && j>=0;k--)
           A[k]=A[i]>B[j]?A[i--]:B[j--];
        
        while(j>=0)
            A[k--]=B[j--];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

链表反转

将一个链表m位置到n位置之间的区间反转，要求使用原地算法，并且在一次扫描之内完成反转。力扣

例如：
给出的链表为1->2->3->4->5->NULL, m = 2 ，n = 4,
返回1->4->3->2->5->NULL.
注意：
给出的m，n满足以下条件：
1 ≤ m ≤ n ≤ 链表长度

//2020.4.21
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m==n)
            return head;
        ListNode* H=new ListNode(-1);
        H->next = head;
        ListNode* p=H;
        for(int i=0;i<m-1;i++)
            p = p->next;
        
        ListNode* n1=p;
        ListNode* tail = n1->next;//反转部分链表的尾部
        ListNode* curr = p->next;
        for(int i=m;i<=n;i++)
        {
            ListNode* third = curr->next;
            curr->next = p;
            p = curr;
            curr = third;
        }
        n1->next = p;
        tail->next = curr;
        
        return H->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二叉树层次遍历ii

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3↵ / ↵ 9 20↵ / ↵ 15 7
该二叉树由底层到顶层层序遍历的结果是：[ [15,7] [9,20], [3] ]

//2020.4.21
class Solution {
public:
    vector<vector<int> >ans;
    
    void dfs(TreeNode*node ,int level)
    {
        if(ans.size()==level)
            ans.push_back(vector<int>());
 
        ans[level].push_back(node->val);
        if(node->left)dfs(node->left,level+1);
        if(node->right)dfs(node->right,level+1);
    }
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        if(!root)
            return ans;
        dfs(root,0);
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

将有序链表转为二叉搜索树

给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）

//2020.4.22
//每次通过快慢指针找到链表的中间节点，用中间节点的值初始化树根节点，
//然后将链表从中间分开，分别用于建立树的左右节点。
class Solution {
public:
    TreeNode *fun(ListNode *head, ListNode *tail){
        if(head == tail)
            return nullptr;
        
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=tail && fast->next!=tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode * node = new TreeNode(slow->val);
        node->left = fun(head,slow);
        node->right = fun(slow->next,tail);
        return node;
    }
    
    TreeNode *sortedListToBST(ListNode *head) {
        if(!head)
            return nullptr;
        
        TreeNode * ans = fun(head,nullptr);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

填充每个节点的next指针

给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其右侧节点。如果找不到右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。力扣

要求：
（1）你只能使用常量级额外空间。
（2）使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

//2020.4.22
//因为要求使用常量级空间，所以不能用队列实现层次遍历
class Solution {
public:
    void connect(TreeLinkNode *root) {
      while(root) //每层第一个元素
      {
          while(root && !root->left && !root->right)
              root = root->next;
          if(!root) break;
          
          TreeLinkNode* c = nullptr;
          for(TreeLinkNode* node = root; node; node = node->next){
              if(node->left){
                  if(c) c->next = node->left;
                  c = node->left;
              }
              if(node->right){
                  if(c) c->next = node->right;
                  c = node->right;
              }
          }
          root = root->left?root->left:root->right; //root指向下一层第一个节点
      }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

链表求和

给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。力扣

示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

//2020.4.27
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* ans = new ListNode(-1);
        ListNode* p = ans;
        
        int s=0;
        while(l1 || l2){   
            int sum = s;
            if(l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            ListNode* tem = new ListNode(sum%10);
            s = sum/10;
            p = p->next = tem;
        }
       
        if(s){
             ListNode* tem = new ListNode(s);
             p = p->next = tem;
        }
        return ans->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行
输入: 5
输出:[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

//2020.4.30
class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > ans;
        if(numRows<=0) return ans;

        for(int i=1;i<=numRows;i++){
            vector<int> tem_i(i,1); //第i层有i个数 ,第一个和最后一个为1
            for(int j=1;j<=i-2;j++)
                tem_i[j] = ans.back()[j-1]+ans.back()[j];
            ans.push_back(tem_i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

杨辉三角ii

给出一个索引k，返回杨辉三角的第k行
例如，k=3，
返回[1,3,3,1]

//2020.4.30
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> dp(rowIndex+1,0);
        dp[0]=1;
        for(int i=1;i<=rowIndex;i++){
            for(int j=i;j>=1;j--)
                dp[j]=dp[j]+dp[j-1];  //从后向前迭代，可避免数据覆盖
        }
        return dp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

//2020.4.30
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > ans;
        if(!root) return ans;
        
        queue<TreeNode*>q;
        q.push(root);
        bool flag = true; 
        
        while(!q.empty()){
            int size = q.size();
            vector<int> tem;
            while(size>0){
                size--;
                TreeNode* node = q.front();
                q.pop();
                tem.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);                
            }
            if(!flag) reverse(tem.begin(),tem.end());
            ans.push_back(tem);
            flag = !flag;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。力扣

示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

//2020.5.2
//way1: small链表存放比x小的节点，big链表存放不小于x的节点
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(-1);
        ListNode* p1 = small;
        ListNode* big = new ListNode(-1);
        ListNode* p2 = big;

        while(head){
            if(head->val < x) p1 = p1->next = head;
            else p2 = p2->next = head;
            head = head->next;  
        }
        p1->next = big->next;
        p2->next = nullptr;
        return small->next;        
    }
};

//way2: p指向最后一个小于x的节点，curr->next指向小于x的节点
//把curr->next节点移到p后面，更新p和curr
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode* ans = new ListNode(-1);
        ans->next = head;
        ListNode* p = ans;
        
        ListNode* curr = ans;
        
        while(curr->next){
            if(curr->next->val < x){
                if(curr == p){
                    curr = curr->next;
                    p = p->next;
                }
                else{
                    ListNode* tem = curr->next;
                    curr->next = tem->next;
                    tem->next = p->next;
                    p = p->next = tem;
                }
            }
            else
                curr = curr->next;
        }
        return ans->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？力扣

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
在这里插入图片描述

//2020.5.2
//注意：左右子树的形态数量跟具体的节点值无关，只跟节点数量有关
//n个节点构成的二叉搜索数的数量 = 以 1，2，3...n分别为根节点构成的二叉搜索树之和。
//dp[i]表示由i个节点构成的二叉搜索树数量 dp[i] = dp[0]*dp[i-1]+dp[1]+dp[i-2]+...+dp[i-1]*dp[0]
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=i-1;j++)
                dp[i] += dp[j]*dp[i-1-j];
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

将有序数组转化为平衡二叉搜索树

给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.力扣
注意：大家千万别写成注释掉的方法，啊啊啊
指针root一开始指向nullptr，在dfs函数实参root对应的形参node指向一个新的节点，但是实参root不会有任何变化。

//2020.5.5
class Solution {
public:
    /*
    void dfs(TreeNode* node, vector<int>& num,int begin,int end){
        if(begin>end)
            return;
        int n = (begin+end)/2;
        node = new TreeNode(num[n]);
        dfs(node->left,num,begin,n-1);
        dfs(node->right,num,n+1,end);
    }
    TreeNode *sortedArrayToBST(vector<int> &num) {
        TreeNode* root = nullptr;
        dfs(root,num,0,num.size()-1);
        return root;        
    }
    */
     TreeNode* dfs(vector<int>& num,int begin,int end){
        if(begin>end)
            return nullptr;
        int n = (begin+end+1)/2; 
        //中间节点的确定，其实加1不加1都行，力扣上都能通过，
        //但是牛客上必须加1，也就是牛客上认为 1 2 3 4，3是中间节点
        TreeNode* node = new TreeNode(num[n]);
        node->left = dfs(num,begin,n-1);
        node->right = dfs(num,n+1,end);
        return node;
    }
    TreeNode *sortedArrayToBST(vector<int> &num) {
        TreeNode* root = dfs(num,0,num.size()-1);
        return root;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。力扣

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

//2020.5.5
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0]; //dp表示以当前位置为末尾最大连续子序列的和
        int ans = dp;
        for(int i=1;i<nums.size();i++){
            dp = max(dp+nums[i],nums[i]);
            ans = max(ans,dp);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。力扣

二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

//2020.5.6
//way1:每个节点都有一个上限和下限
    bool isValid(TreeNode *node, int left,int right)
    {
        if(!node)
            return true;
        if(!(node->val > left && node->val < right))
            return false;
    
        return isValid(node->left,left,node->val) && isValid(node->right,node->val,right);
    }
    bool isValidBST(TreeNode *root) {
        if(!root)
            return true;

        return isValid(root->left,INT_MIN,root->val) && isValid(root->right,root->val,INT_MAX);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//2020.5.6
//way2:中序遍历，判断数组是否升序
class Solution {
public:
    vector<int> v;
    void inorder(TreeNode* node)
    {
        if(!node)
            return;

        inorder(node->left);
        v.push_back(node->val);
        inorder(node->right);
    }
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        inorder(root);
        bool flag = true;
        for(int i=1;i<v.size();i++)
        {
            flag = flag && v[i-1]<v[i];
            if(!flag)
                return flag;
        }
        return flag;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

删除链表中的重复元素ii

给出一个排好序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。力扣

例如：
给出的链表为1->2->3->3->4->4->5, 返回1->2->5.
给出的链表为1->1->1->2->3, 返回2->3.

//2020.5.6
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* ans = new ListNode(-1);
        ans->next = head;
        ListNode* p = ans;
        while(p->next && p->next->next)
        {
            if( p->next->val != p->next->next->val)
                p = p->next;
            else //发现重复元素
            {
                ListNode* tem = p->next;
                while(tem && tem->next && tem->val == tem->next->val)
                    tem = tem->next;

                p->next = tem->next;
            }
        }
        return ans->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。力扣

注意:
你可以假设树中没有重复的元素。

//2020.5.6
class Solution {
public:
    TreeNode *build(vector<int> &inorder,int in_l,int in_r,vector<int> &postorder,int po_l,int po_r){
        if(in_l>in_r || po_l>po_r)
            return nullptr;
        
        TreeNode * node = new TreeNode(postorder[po_r]);
        
        int mid; //在中序遍历数组中找到中间节点，把树分为左子树和右子树
        for(mid=in_l;mid<=in_r;mid++){
            if(inorder[mid]==postorder[po_r]){
                break;
            }
        }
        int left_num = mid - in_l; //左子树节点数
        node->left = build(inorder,in_l,mid-1,postorder,po_l,po_l+left_num-1);
        node->right = build(inorder,mid+1,in_r,postorder,po_l+left_num,po_r-1);
        return node;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        TreeNode * root = build(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成力扣

//2020.5.6
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2)
            return nums.size();

        int i=1;
        for(int j=1;j<nums.size();j++)
        {
            if(nums[j]!=nums[j-1])
                nums[i++] = nums[j];
        }
        return i; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

从前序和中序遍历序列构造二叉树

给出一棵树的前序遍历和中序遍历，请构造这颗二叉树力扣
注意：可以假设树中不存在重复的节点

//2020.5.12
class Solution {
public:
    TreeNode* build(vector<int> &preorder, int pre_begin,int pre_end,
                    vector<int> &inorder, int in_begin, int in_end){
        if(pre_begin > pre_end)
            return nullptr;
        TreeNode* node = new TreeNode(preorder[pre_begin]);
        
        int mid = in_begin; //从中序遍历找到根节点
        for(;mid<=in_end;mid++){
            if(inorder[mid]==node->val)
                break;
        }
        int left_num = mid - in_begin; //左子树节点数
       
        node->left = build(preorder,pre_begin+1,pre_begin+left_num,inorder,in_begin,mid-1);
        node->right = build(preorder,pre_begin+left_num+1,pre_end,inorder,mid+1,in_end);
        
        return node;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        
        return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

最长不重复子串

给定一个字符串，找出最长的不具有重复字符的子串的长度。力扣
例如，“abcabcbb”不具有重复字符的最长子串是“abc”，长度为3。
对于“bbbbb”，最长的不具有重复字符的子串是“b”，长度为1。

//2020.5.12
//dp[i]表示以s[i]为结尾的最长不重复子串长度，
//j从i-1遍历到i-dp[i]，如果s[j]不等s[i],dp[i]加1.
//时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()<=0)
            return 0;
        vector<int> dp(s.length(),1);
        int ans = 1;
        for(int i=1;i<s.length();i++){
            for(int j=i-1;j>=i-dp[i-1];j--){ //j不能遍历到0
                if(s[j]!=s[i])
                    dp[i]++;
                else
                    break;
            }
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//利用数组m存储最近一次字符出现的位置，降低时间复杂度
//时间复杂度O(n),空间复杂度O(1)
int lengthOfLongestSubstring(string s) {
        if(s.size()==0) return 0;

        vector<int> m(128,-1); //记录每个字符出现的位姿，一个128个字符
        int dp=1;
        m[s[0]]=0; 
        int ans = 1;

        for(int i=1;i<s.size();i++){
            int dis = i - m[s[i]]; //距离最近一次字符的距离
            if(dis > dp)  
                dp = dp+1;
            else
                dp = dis;
            
            if(dp>ans)ans=dp;
            m[s[i]]=i; //更新m
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后一个单词的长度

给出一个只包含大小写字母和空格的字符串s，请返回字符串中最后一个单词的长度。如果字符串中没有最后一个单词，则返回0。力扣
注意：单词的定义是仅由非空格字符组成的字符序列。
例如： s =“Hello World”, 返回5。

//2020.5.12
int lengthOfLastWord(string s) {
    stringstream ss(s); //ss会将读入的字符串按空格分隔开
    string str;
    while(ss>>str); //while(ss >> str)执行完后，str中保存的是ss中以空格分隔开的最后一个单词。
    return str.length();
}
1
2
3
4
5
6
7

int lengthOfLastWord(const char *s) {
    int end = strlen(s)-1;
    while(s[end]==' ') //去除尾部空格
        end--;

    int begin=end;
    for(;begin>=0;begin--){
        if(s[begin]==' ')
            break;
    }
    return end-begin;
}
1
2
3
4
5
6
7
8
9
10
11
12

全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。力扣
示例: 输入: [1,2,3]，输出:[[1,2,3], [1,3,2], [2,1,3],[2,3,1],[3,1,2],[3,2,1]]

//回溯算法
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tem;

    void backtrack(vector<int>& nums,vector<bool>& flags){
        if(tem.size()==nums.size()){ //终止条件
            ans.push_back(tem);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(flags[i]){  
                tem.push_back(nums[i]); 
                flags[i]=false;
                backtrack(nums,flags);
                tem.pop_back(); //回溯
                flags[i]=true;
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> flags(nums.size(),true);  //标识是否遍历过
        backtrack(nums,flags);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。力扣

//时间复杂度O(logn)
class Solution {
public:
    double pow(double x,long long n){
        if(n==0) return 1;
        if(n==1) return x;
        
        double half = pow(x,n/2);   //指数减半 
        
        if(n%2==0) return half*half;
        else return x*half*half;
    }
    double myPow(double x, int n) {
        long long N=n; 
        if(N<0){
            x=1/x;
            N=-N;  //INT_MIN = -2^31取反超过INT_MAX = 2^31-1
        }     
        return pow(x,N);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

直线上最多的点

对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上

class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int ans=0;
        for(int i=0;i<points.size();i++)
        {
            int c_count=0; //垂直点计数
            int repeat=1;   //重复点计数
            map<double,int> m; //斜率和对应次数
            int max_count=0;
            for(int j=i+1; j<points.size();j++)  //注意j的范围
            {
                if(points[i].x==points[j].x && points[i].y==points[j].y)
                    repeat++;  //重复点
                else if(points[i].x==points[j].x) //垂直
                {
                    c_count++;
                    max_count = max(max_count,c_count);
                }
                else  //有斜率
                {
                    double k=1.0*(points[i].y-points[j].y)/(points[i].x-points[j].x);
                    m[k]++;
                    max_count = max(max_count,m[k]);
                }
            }
            ans = max(ans,max_count+repeat);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

最长不重复子字符串

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)
            return 0;
        map<char,int> m; //记录字符出现的位置
        vector<int> dp(s.size(),0);
        m[s[0]] = 1;
        dp[0] = 1;
        int ans = dp[0];
        for(int i=1;i<s.size();i++)
        {
            if(m[s[i]]==0)   //s[i]没出现过
                dp[i] = dp[i-1]+1; 
            else
            {
                if(i-m[s[i]]+1 > dp[i-1])
                    dp[i] = dp[i-1]+1;
                else
                    dp[i] = i-m[s[i]]+1;
            }
            m[s[i]] = i+1;
            ans = max(ans,dp[i]);    
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
输入: [“flower”,“flow”,“flight”]
输出: “fl”

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans;
        if(!strs.size()) return ans;

        int minsize = strs[0].size();
        for(int i=1;i<strs.size();i++){
            if(strs[i].size() < minsize)
                minsize = strs[i].size();
        }
          
        if(!minsize) return ans;

        for(int i=0;i<minsize;i++)
        {
            bool flag = true;
            for(int j=1;j<strs.size();j++)
            {
                if(strs[j][i] != strs[j-1][i]){
                    flag = false;
                    break;
                }
            }
            if(flag)
                ans.push_back(strs[0][i]);
            else
                break;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//标准答案好简洁，呜呜
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(!strs.size()) return "";
        for(int i=0;i<strs[0].size();i++)
        {
            char a = strs[0][i];
            for(int j=0;j<strs.size();j++){
                if(strs[j].size() == i || strs[j][i]!=a){
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码创作者/article/detail/61952

题海无涯

刷一题记一题，题目来自力扣

数组求和统计

直线上最多的点数

对称的树

删除链表中的重复元素

整数反转

合并有序数组

链表反转

二叉树层次遍历ii

将有序链表转为二叉搜索树

填充每个节点的next指针

链表求和

杨辉三角

杨辉三角ii

二叉树的锯齿形层次遍历

分隔链表

不同的二叉搜索树

将有序数组转化为平衡二叉搜索树

最大子序和

验证二叉搜索树

删除链表中的重复元素ii

从中序与后序遍历序列构造二叉树

删除排序数组中的重复项

从前序和中序遍历序列构造二叉树

最长不重复子串

最后一个单词的长度

全排列

pow(x, n)

直线上最多的点

最长不重复子字符串

最长公共前缀