题目

233. 数字 1 的个数 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

1
2

输入：n = 13
输出：6

示例 2：

1
2

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 10^9

思路

是一个递推的问题。

方法一：直接递推

假设输入为 a*10^n^+b

中间情况：

只要递归：$$ f( a*10^n+b ) = f(b) + f ( a * 10^n-1 ) $$即可。

边界条件：

$$ f(x)=\left{ \begin {aligned} & 0,x<1\&1,1<=x<10 } \end {aligned} \right. $$

本方法会超时

方法二：避免重复计算

在
$$a*10^n+b$$
中，

• 如果a>2，在计算完b之后，需要计算a*10^n^-1。

  容易发现：

  当a>2 的时候，在2~a之间由于最高位都不是1，因此都是计算10^n-1^，可以合并为计算一次10^n-1^，之后乘上a-2 倍。

  当a==2的时候，计算2*10^n-1^，即计算与$$a*10^n+b$$ 相同位数，不过最高为是1时候的总的1的个数。

  计算a-2个b可以合并为计算一个b之后乘上a-2，之后在计算2*10^n-1^即可。

• 如果a==1：

  数字为$$10^n+b$$ ，首先有b+1个数字至少包含一个1，也就是不小于$$10^n$$的部分最高位包含1的个数，之后递归计算b，算出来不小于10^n^部分包含的所有的1，在计算10^n^-1内的1的个数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countDigitOne(int n) {
        if(n<1) return 0;
        if(n<10) return 1;
        int a = n,e=1;
        while(a/10){
            a/=10;
            e*=10;
        }
        int b = n - a*e;
        if(a==1) return b+1+countDigitOne(b)+countDigitOne(e-1);
        return countDigitOne(b)+countDigitOne(2*e-1)+(a-2)*countDigitOne(e-1);
    }
};

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路

1. 最简单的暴力，复杂度O(N^2)
2. 使用Hash，复杂度O(NlogN)。使用unordered_map来实现已经logN级别的搜索。

代码

1. 暴力解法

   1 2 3 4 5 6 7 8 9 10 11 12 13

   class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i=0;i<nums.size();i++){ for(int j=nums.size()-1;j>i;j--){ if(nums[i]+nums[j]==target){ return {i,j}; } } } return {}; } };

1. Hash解法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> m; for(int i=0;i<nums.size();i++){ auto f = m.find(target-nums[i]); if(f!=m.end()){ return {min(i,f->second),max(i,f->second)}; } m[nums[i]]=i; } return {}; } };

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

​ 思路比较简单，就是从末尾开始相加，设置一个进位符op，循环结束条件为两个指针都为NULL并且进位符为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* point = head;
        int op = 0;
        while(l1!=NULL||l2!=NULL||op==1){
            int v1 = l1==NULL?0:l1->val;
            int v2 = l2==NULL?0:l2->val;
            int v = v1 + v2 + op;
            op = v / 10;
            head->next = new ListNode(v%10);
            head=head->next;
            l1 = l1==NULL?NULL:l1->next;
            l2 = l2==NULL?NULL:l2->next;
        }
        return point->next;
    }
};

题目

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

 3
/ \\
2   3
\   \
 3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

思路

dp真的不会啊，用了层次遍历。为了防止TLE用一个unordered_map来存储已经遍历过的节点,如果直接存在就使用，不存在则将当前的node算出以其为root的最大值，加入到map中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    unordered_map<TreeNode*,int> m;
    inline int get(TreeNode* node){
        if(node==NULL) return 0;
        if(m.find(node)!=m.end()){
            return m[node];
        }
        m[node]=rob(node);
        return m[node];
    }
    int rob(TreeNode* root) {
        if(root==NULL) return 0;
        m[root]=max(get(root->left)+get(root->right),
        root->val+
        (root->left==NULL?0:get(root->left->left)+get(root->left->right))+
        (root->right==NULL?0:get(root->right->left)+get(root->right->right)));
        return m[root];
    }
};

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

• 你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

思路

就是暴力
1.先通过两个从头开始的指针，一个一次走一步，一个一次走两步，看两者能不能相遇，以此来确定有没有环，如果没有环直接返回NULL，有环则记录下两个指针相等的位置n1.
2.如果有环，那么环的头节点一定在head到n1之间，那么只需要再head和n1之间便利，从head往后一个一个开始，看看循环1~2圈只能能不能回到起始节点，如果可以那么证明事头节点，如果不行就往后。直到找到。

代码

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL) return head;
        ListNode* n1,*n2;
        n1=head;
        n2=head->next;
        // if(n1==NULL||n2==NULL||n2->next==NULL) return NULL;
        while(n1!=n2){
            // printf("n1:%d n2:%d\n",n1->val,n2->val);
            if(n2==NULL||n2->next==NULL) return NULL;
            n2=n2->next->next;
            n1=n1->next;
        };
        //再head和n1之间存在环，从一个节点开始，到n1结束
        ListNode* h=head;
        //h肯定在h~n1之间，看h到n1之前的节点是不是一样，前面有就在前面，前面没有就是n1
        while(h!=n1){
            bool finded=false;
            ListNode* ch=h->next;
            while(ch!=h){
                if(ch==n1){
                    if(finded){
                        break;
                    }else{
                        finded=true;
                    }
                }
                ch=ch->next;
            }
            if(ch==h) return h;
            else h=h->next;
        }
        return h;
    }
};

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

别无他长，用暴力吧。
从1-9进行遍历，每次遍历从当前遍历到的元素的下一个开始，然后k-1，n-i传入到下次遍历之中。当k=1并且n比当前遍历的元素大而且比9小的时候，返回这个vector>。
上层遍历拿到返回的vector>之后，把本层遍历的元素放到首位，然然后加入到自己的结果队列之中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        return getsum(1,k,n);
    }
    vector<vector<int>> getsum(int s,int k,int n){
        if(k<=0||k>n||s>n) return {};
        if(n>=s&&k==1&&n<=9) return {{n}};
        vector<vector<int>> v;
        for(int i=s;i<=9;i++){
            vector<vector<int>> temp=getsum(i+1,k-1,n-i);
            for(vector<int> t:temp){
                t.insert(t.begin(),i);
                v.push_back(t);
            }
        }
        return v;
    }
};

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

思路

首先找到第一个开始的反转节点
反转一个链表须要三个半节点：反转链表的第一个（算半个）pre->next，反转链表过程中的第一个head，反转链表过程中未反转部分的第一个nxt，反转链表未反转部分的第二个aft。
每次让nxt的next只想head，之后head变为nxt，这样即实现了一个节点反转到头节点的过程。之后nxt转为未反转部分的第一个，也即原来的aft，aft后移。
全部移动完成后，须要将原来反转链表的第一个pre->next的next设置为nxt，以此实现反转后的尾节点与后续节点链接。之后pre的next节点设置为反转后的第一个节点head。返回第一个节点即可。
为了方便返回第一个节点，这里在头节点前插入新节点。

代码

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n) return head;
        int cnt = 1;
        ListNode* pre = new ListNode(0);
        pre->next = head;
        ListNode* h = pre;
        while(cnt<m){
            pre=head;
            head=head->next;
            cnt++;
        }
        ListNode* nxt=head->next,*aft=head->next->next,*lst = head;
        while(cnt<n){
            nxt->next = head;
            head=nxt;
            nxt=aft;
            if(aft)aft=aft->next;
            cnt++;
        }
        pre->next->next = nxt;
        pre->next = head;
        return h->next;
    }
};

题目

516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列.

实例1:

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

思路

• 马拉车

  马拉车算法用来解决最长回文字串的问题是最先想到的思路，但是本地比较特殊的一点在于，可以删除。如果分别删除，复杂度会太大，因此排除使用马拉车算法的思路。

• 动态规划

  设置数组dp，dp[i][j]代表从s[i] 到s[j] 的最长回文字串长度。

  初始状态： dp[i][i]=1

  中间状态：对于任意i,j 0<=i<j<n，其中任意字串的长度都已经通过循环获得。这里让j从0开始循环的，因此0~j-1内的所有字串的最大回文长度都已经知道，从0~j相当于在此基础上在最后一位上加上了s[j]。令i从j-1开始向0 循环，这样整体的长度才是从小往大：

  • 如果s[i]==s[j]，那么就是i+1~j-1内最大的回文字串长度加上2：

    dp[i][j]=dp[i+1][j-1]+2 如果`s[i]==s[j]`但是`dp[i+1][j-1]`并不是从`i+1`开始到`j-1`结束的回文字串呢？没有关系，中间的可以都删除，因此只需要保存最长的长度即可。

• 如果s[i]!=s[j]，那么只需要dp[i][j]设置为i~j-1和i+1~j中的最长回文字串长度即可：

  dp[i][j]=max(dp[i][j-1],dp[i+1][j])

由于是从头往后开始遍历的，因此遍历到i的时候再将dp[i][j]设置为1即可。

结果： dp[i][j]代表从s[i] 到s[j] 的最长回文字串长度。因此s从0到n-1的最长回文字串长度就是dp[0][n-1]。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        int dp[n][n];
        memset(dp,0,sizeof(int)*n*n);
        for(int i=0;i<n;i++){
            dp[i][i] = 1;
            for(int j=i-1;j>=0;j--){
                if(s[i]==s[j]){
                    dp[j][i] = dp[j+1][i-1]+2;
                }else{
                    dp[j][i] = max(dp[j][i-1],dp[j+1][i]);
                }
            }
        }
        return dp[0][n-1];
    }
};