devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣刷题总结c++ 解题报告（持续更新中）_c++刷题

作者：Guff_9hys | 2024-08-22 18:32:55

赞

踩

c++刷题

写这篇的初衷是整理复习一遍自己刷过的题

目录

1. 两数之和

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

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

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

示例 1：

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

题解一：暴力，太慢了

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

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

解法二：哈希
注意：此题中unordered_map的第二个值是 i，而 i 可能是 0 ，所以判断 target - nums[i] 时，不能使用if（ target - nums[i]），需要用到迭代器

class Solution
{
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		unordered_map<int, int>a;
		vector<int>arr;
		for (int i = 0; i < nums.size(); ++i)
		{
			unordered_map<int, int>::iterator it = a.find(target - nums[i]);
			if (it != a.end())
			{
				arr.push_back(it->second);
				arr.push_back(i);
				break;
			}
			else
				a[nums[i]] = i;
		}
		return arr;
	}
};

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

解法三：哈希
为了解决解法二判断 target - nums[i] 时需要用到迭代器，可以令 a[nums[i]] = i+1；

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

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

2. 两数相加

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

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

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

示例 1：

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

参考了官方题解
只要L1或者L2不等于NULL，就一直在循环里
设置三个变量a、b、now、tmp（进位，初值为0）
a:L1的值，若L1为NULL，则为0
b:L2的值，若L2为NULL，则为0
now:a+b+tmp
tmp记录是否进位：now/10

class Solution
{
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
	{
		ListNode* head = NULL;
		ListNode* tail = NULL;
		int tmp = 0;
		int a, b, now;
		while (l1 || l2)
		{
			a = l1 ? l1->val : 0;
			b = l2 ? l2->val : 0;
			now = a + b + tmp;
			tmp = now / 10;
			if (!head)//head为空 
			{
				head = tail = new ListNode(now % 10);
			}
			else
			{
				tail->next = new ListNode(now % 10);
				tail = tail->next;
			}
			if (l1)
			{
				l1 = l1->next;
			}
			if (l2)
			{
				l2 = l2->next;
			}
		}
		if (tmp)
		{
			tail->next = new ListNode(tmp);
		}
		return 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

忽然发现之前用C写的时间、空间效率都好很多很多
但C++那个程序更加简洁，可读性好

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
	int len1 = 0, len2 = 0;
	struct ListNode* p;
	struct ListNode* q;
	struct ListNode* head;
	struct ListNode* r;
	for (p = l1; p->next != NULL; p = p->next)
		len1++;
	for (q = l2; q->next != NULL; q = q->next)
		len2++;
    
	if (len1 > len2)
	{
		p = head = l1;
		q = l2;
	}
	else
	{
		p = head = l2;
		q = l1;
	}
	int tmp = 0;
    int val;
	while (p != NULL)
	{
		if (q != NULL)
		{
            val=p->val;
			p->val = (p->val + q->val + tmp) % 10;
			tmp = (val + q->val + tmp) / 10;
			if (tmp == 1 && p->next == NULL)
			{
				r = (struct ListNode*)malloc(sizeof(struct ListNode));
				p->next = r;
				r->val = tmp;
				r->next = NULL;
                break;
			}
			q = q->next;
		}
        else 
        {
            val=p->val;
            p->val=(p->val+tmp)%10;
            tmp=(val+tmp)/10;
            if (p->next == NULL && tmp == 1)
			{
				r = (struct ListNode*)malloc(sizeof(struct ListNode));
                assert(r != NULL);
				r->val = tmp;
				r->next = NULL;	
                p->next = r;	
                break;
			}           
        }
		p = p->next;
	}
	return 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

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

3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

注意：子串有顺序，子序列无
解法一：哈希，效率极差

class Solution
{
public:
	int lengthOfLongestSubstring(string s)
	{
		unordered_map<char, int>a;
		int max = 0;
		int num = 0;
		int i = 0, j = 0;
		for (i = 0; i < s.length(); i++)
		{
			num = 0;
			a.clear();
			for (j = i; j < s.length(); j++)
			{
				if (a.empty() || a[s[j]] == 0)
				{
					a[s[j]]++;
					num++;
				}
				else
				{
					max = fmax(max, num);
					break;
				}
			}
			if (j == s.length())
			{
				max = fmax(max, num);
				if (max == s.length())
					break;
			}
		}
		return max;
	}
};

  • 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

解法二：哈希+滑动窗口
效率有变好一点

class Solution
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        if (s.size() == 0) 
            return 0;
        unordered_set<char> a;
        int max = 0;
        int left = 0;
        for (int right = 0; right < s.size(); right++) 
        {
            while (a.find(s[right]) != a.end())//迭代器，不等于时，代表找到了
            {
                a.erase(s[left]);
                left++;
            }
            max = fmax(max, right - left + 1);
            a.insert(s[right]);
        }
        return max;

    }
};

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

5. 最长回文子串

5. 最长回文子串

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

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

动态规划，好好看官方题解，多看几遍就能看懂！！！然后多练

class Solution 
{
public:
    string longestPalindrome(string s)
    {
        int n = s.length();
        if (n < 2)
            return s;
        vector<vector<int>>dp(n, vector<int>(n));
        for (int i = 0; i < n; i++)
        {
            dp[i][i] = true;
        }
        int begin = 0;
        int maxlen = 1;
        for (int len = 2; len <= n; len++)
        {
            for (int left = 0; left < n; left++)
            {
                int right = len + left - 1;
                if (right >= n)
                    break;
                if (s[left] != s[right])
                {
                    dp[left][right] = false;
                }
                else
                {
                    if (right - left < 3)
                    {
                        dp[left][right] = true;
                    }
                    else
                    {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
                if (dp[left][right] && right - left + 1 > maxlen)
                {
                    maxlen = right - left + 1;
                    begin = left;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};

  • 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

以下是一个我很喜欢的博主：代码随想录 的题解

**定义dp[i] [j]：**范围[i,j] 的子串是否是回文子串，是为true，否则为false

**初始化：**false

当s[i]与s[j]相等时，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。

情况三是根据dp[i + 1] [j - 1]是否为true，再对dp[i] [j]进行赋值true的。

dp[i + 1] [j - 1] 在 dp[i] [j]的左下角

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1] [j - 1]都是经过计算的。

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        int maxlenth = 0;
        int left = 0;
        int right = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1;
                    left = i;
                    right = j;
                }
            }

        }
        return s.substr(left, right - left + 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
  • 28
  • 29

6. Z 字形变换

6. Z 字形变换

将一个给定字符串 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”

这个题说来还有一个故事，我秋招投的第一家公司的笔试题就是这个

class Solution {public:	string convert(string s, int numRows)	{		if (numRows == 1)			return s;		int tmp = 2 * (numRows - 1);		string s1;		for (int k = 0; k < numRows; k++)		{			for (int j = 0; j < s.length(); j++)			{				if ((j % tmp == k) || (j % tmp == tmp - k))				{					s1.push_back(s[j]);				}			}		}		return s1;	}};

  • 1

感觉整理题解比之前写都要难，这次在评论区发现一个新思路，来源于 Krahets

先创建一个numRows行的二维数组，初始化 i=0，flag=-1 （这个-1就很妙了）

思路是：先按顺序给每行一维数组赋值，Z字形在0行和numRows行会转变方向，所以i0||inumRows-1时flag=-flag来转换方向，也因此flag的初值为-1

eg.1,2,3,4,5,6,7 numRows=3

1给第一行，2给第二行，3给第三行，转变方向，

i又来到了第二行，4给第二行，5给第一行，转变方向，

6给第二行，7给第三行

（第一行对应下标0，第三行对应下标numRows-1）

class Solution {public:	string convert(string s, int numRows)	{		if (numRows == 1)			return s;		vector<vector<char>>a(numRows);        int i=0;        int flag=-1;        for(auto n:s)        {            a[i].push_back(n);            if(i==0||i==numRows-1)flag=-flag;            i+=flag;        }        string s1;        for(auto n:a)        {            for(auto m:n)            {                s1.push_back(m);            }        }		return s1;	}};

  • 1

7. 整数反转

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

终于来到了一个简单题

不过，我之前的代码真的是不忍直视，又臭又长,贴出来图一乐，哈哈

当时沉迷于swap、字符串的reverse、atoi、itoa不能自拔

class Solution 
{
public:
    void swap(char& a, char& b)
    {
        char tmp = a;
        a = b;
        b = tmp;
    }
    int reverse(int x) 
    {
        if(x==0)return 0;
        int left = 0;
        string s = to_string(x);
        int right = s.size()-1;
        if (x < 0)
        {
            left++;
        }
        while (s[right] == '0')
        {
            right--;
            
        }
        string s1(s.begin() + left, s.begin() + right+1);
        left=0;
        right=s1.length()-1;
        while (left <= right)
        {
            swap(s1[left], s1[right]);
            left++;
            right--;
        }
        long long num = 0;

        for (int i = 0; i < s1.length(); i++)
        {
            num = num*10+s1[i] - '0';
        }
        if (x < 0)
            num = -num;
        if (num > -1 + pow(2, 31) || num < -pow(2, 31))
            return 0;
        return num;
    }
};

  • 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

因为可能越界，所以x1的类型为long long 型，return之前判断一下就行

清晰明了、赏心悦目

class Solution{public:	int reverse(int x)	{		long long x1 = 0;		while (x)		{			x1 = 10 * x1 + x % 10;			x /= 10;		}		if (x1 > INT_MAX || x1 < INT_MIN)			return 0;		return x1;	}};

  • 1

8. 字符串转换整数 (atoi)

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  • 读入字符串并丢弃无用的前导空格

  • 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。

  • 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
    将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。

  • 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。

  • 返回整数作为最终结果。

    注意：

    本题中的空白字符只包括空格字符 ’ ’ 。

    除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

非常见得的字符串转数字：

条件1：前导空格跳过

条件2：+ - 符号可在最前边有（前导空格后）

条件3：后续只要不是数字就返回，只要超过int型范围就返回INT_MAX或者INT_MIN

class Solution{public:    int myAtoi(string s)    {        int len = s.length();        int i = 0;        while (s[i] == ' ')        {            i++;        }        int flag = 1;        if (s[i] == '-')        {            flag = -flag;            i++;        }        else if (s[i] == '+')        {            i++;        }        long long x = 0;        while (i < len)        {            if (!isdigit(s[i]) || x > INT_MAX)                break;            x = x * 10 + (s[i] - '0');            i++;        }        x = x * flag;        if (x > INT_MAX)        {            return INT_MAX;        }        else if (x < INT_MIN)        {            return INT_MIN;        }        return x;    }};

  • 1

9. 回文数

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

class Solution{public:    bool isPalindrome(int x)    {        if (x < 0)            return false;        int x1 = x;        long long x2 = 0;        while (x1)        {            x2 = x2 * 10 + x1 % 10;            x1 /= 10;        }        if (x2 == x)            return true;        return false;    }};

  • 1

11. 盛最多水的容器

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

img

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

c++写两个for循环超时

class Solution
{
public:
	int maxArea(vector<int>& height)
	{
		int left = 0;
		int right = height.size() - 1;
		int max = INT_MIN;
		for (int i = 0; i < right; i++)
		{
			for (int j = i + 1; j <= right; j++)
			{
				int min = height[i] > height[j] ? height[j] : height[i];
				max = fmax(max, min * (j - i));
			}
		}
		return max;
	}
};

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

双指针法:总是移动较小的那端

容纳的水量 = 两个指针指向的数字中较小值 ∗ 指针之间的距离

核心在于：如果移动较大端，y->y1，当y1>y时，计算容量时取的两端最小值x依然不会变，并且二者间距变小，容量变小；y1<=y时，容量必然变小，所以移动较小端；

也就是说：我们排除掉了较小段的这根柱子，以它为边界的容量在之后只会比当前少，不会比当前多

class Solution{public:	int maxArea(vector<int>& height)	{		int left = 0;		int right = height.size() - 1;		int max = INT_MIN;		while(left<right)        {            if(height[left]<=height[right])            {                max=fmax(max,height[left]*(right-left));                left++;            }            else            {                max=fmax(max,height[right]*(right-left));                right--;            }        }		return max;	}};

  • 1

12. 整数转罗马数字

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: “III”

非常简单的if…else…

把特殊情况都考虑进去就可以

class Solution {public:    string intToRoman(int num)     {        string s;        while (num)        {            if (num >= 1000)            {                s.push_back('M');                num -= 1000;            }            else if (num >= 900)            {                s.append("CM");                num -= 900;            }            else if (num >= 500)            {                s.push_back('D');                num -= 500;            }            else if (num >= 400)            {                s.append("CD");                num -= 400;            }            else if (num >= 100)            {                s.push_back('C');                num -= 100;            }            else if (num >= 90)            {                s.append("XC");                num -= 90;            }            else if (num >= 50)            {                s.push_back('L');                num -= 50;            }            else if (num >= 40)            {                s.append("XL");                num -= 40;            }            else if (num >= 10)            {                s.push_back('X');                num -= 10;            }            else if (num >= 9)            {                s.append("IX");                num -= 9;            }            else if (num >= 5)            {                s.push_back('V');                num -= 5;            }            else if (num >= 4)            {                s.append("IV");                num -= 4;            }            else if (num >= 1)            {                s.push_back('I');                num -= 1;            }        }        return s;    }};

  • 1

13. 罗马数字转整数

13. 罗马数字转整数

写个switch…case…用来累加，之后再判断6中特殊情况，注意是-2，-20，-200，而不是-1，-10，-100，因为在之前累加的时候多加了一次！！！

class Solution{public:    int num(char s)    {        int a;        switch (s)        {        case 'I':a = 1; break;        case 'V':a = 5; break;        case 'X':a = 10; break;        case 'L':a = 50; break;        case 'C':a = 100; break;        case 'D':a = 500; break;        case 'M':a = 1000; break;        }        return a;    }    int romanToInt(string s)    {        int sum = 0;        for (auto n : s)        {            sum += num(n);        }        for (int i = 0; i < s.size() - 1; i++)        {            if (s[i] == 'I' && (s[i + 1] == 'V' || s[i + 1] == 'X'))                sum -= 2;            else if (s[i] == 'X' && (s[i + 1] == 'L' || s[i + 1] == 'C'))                sum -= 20;            else if (s[i] == 'C' && (s[i + 1] == 'D' || s[i + 1] == 'M'))                sum -= 200;        }        return sum;    }};

  • 1

14. 最长公共前缀

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

写一个返回值为string类型的longest函数，用来返回两个字符串之间的公共前缀

在longestCommonPrefix函数中进行遍历，s用来保存目前最短的公共前缀，s1保存相邻字符串的公共前缀，最后返回s即可

class Solution 
{
public:
    string longest(string a, string b)
    {
        string s;
        for (int i = 0; i < a.length(); i++)
        {
            if (a[i] == b[i])
                s.push_back(a[i]);
            else
                break;
        }
        return s;
    }
    string longestCommonPrefix(vector<string>& strs) 
    {
        if (strs.size() == 1)
            return strs[0];
        string s;
        string s1;
        for (int i = 0; i < strs.size()-1; i++)
        {
            if(i==0)
                s= longest(strs[i], strs[i + 1]);
            else
            {
                s1 = longest(strs[i], strs[i + 1]);
                s = s<s1 ? s : s1;
            }
        }
        return s;
    }
};

  • 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

15. 三数之和

15. 三数之和

给你一个包含 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]]

好长的代码

排序，固定i，如果nums[i]>0,退出循环，令left=i+1，right=nums.size()-1,遍历查找nums[i]+nums[left]+nums[right]==0的数组

注意：重复数组的情况

  1. i > 0 && nums[i] == nums[i - 1] 时contine
  2. sum == 0时，判断nums[left]与nums[left+1]，nums[right]与nums[right - 1]的情况
class Solution {public:    vector<vector<int>> threeSum(vector<int>& nums)    {        vector<vector<int>>arr;        if (nums.size() < 3)        {            return arr;        }        sort(nums.begin(), nums.end());        int left;        int right;        int sum;        for (int i = 0; i < nums.size(); i++)        {            if (nums[i] > 0)                break;            if (i > 0 && nums[i] == nums[i - 1])            {                continue;            }            left = i + 1;            right = nums.size() - 1;            while (left < right)            {                sum = nums[i] + nums[left] + nums[right];                if (sum == 0)                {                    arr.push_back({ nums[i],nums[left],nums[right] });                    while (left < right && nums[left] == nums[left + 1])                    {                        left++;                    }                    while (left < right && nums[right] == nums[right - 1])                    {                        right--;                    }                    left++;                    right--;                }                else if (sum > 0)                {                    right--;                }                else                {                    left++;                }            }        }        return arr;    }};

  • 1

16. 最接近的三数之和

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

和上一题思路基本上是一样的，在最接近target这块，新设了mina和minb分别保存abs(sum-target)、sum,当abs(sum-target)<mina时，要同步更新mina和minb的值

class Solution 
{
public:
    int threeSumClosest(vector<int>& nums, int target) 
    {
        if (nums.size() == 3)
        {
            return nums[0] + nums[1] + nums[2];
        }
        sort(nums.begin(), nums.end());
        int mina= INT_MAX, minb=INT_MAX;
        int left, right, sum;
        for (int i = 0; i < nums.size(); i++)
        {
            left = i + 1;
            right = nums.size() - 1;
            while (left < right)
            {
                sum = nums[i] + nums[left] + nums[right];
                if (sum == target)
                {
                    return target;
                }
                else if (sum < target)
                {
                    if (target-sum < mina)
                    {
                        mina = target - sum;
                        minb = sum;
                    }
                    left++;
                }
                else
                {
                    if (sum- target < mina)
                    {
                        mina = sum - target;
                        minb = sum;
                    }
                    right--;
                }
            }
        }
        return minb;
    }
};

  • 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

19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

写链表、二叉树这类给了初始化的习题时，一定要自己实现一下初始化过程！！不然面试笔试会吃亏

之后的每个链表题，我都会在题解里强调一下

初始化的C实现

struct ListNode{	int val;	struct ListNode* next; };

  • 1

初始化的C++实现

 struct ListNode 
 {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}	
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

先遍历一遍求出链表长度len，n=len-n，将n变为正序的顺序

分为两种情况，新n==0时，直接令head=head->next； return head； 即可

另一种 i从0开始遍历，当i+1==n时，跳过该节点的下个节点即可

 class Solution 
 {
 public:
     ListNode* removeNthFromEnd(ListNode* head, int n) 
     {
         int len = 0;
         for (ListNode* p = head; p != NULL; p = p->next)
         {
             len++;
         }
         n = len - n;
         if (n==0)
         {
             head = head->next;
             return head;
         }
         int i = 0;
         for (ListNode* p = head; p != NULL; p = p->next)
         {
             if (i + 1 == n)
             {
                 ListNode* q = p->next;
                 p->next = q->next;
                 break;
             }
             i++;
         }
         return 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

做过一些链表的题，发现官解一般都设置了哑结点（dummy node）,它的next 指针指向链表的头节点，这样一来，我们就不需要对头节点进行特殊的判断。

因为平时实现链表习惯用C写，所以贴上C和C++官方代码

C

int getLength(struct ListNode* head) 
{
    int length = 0;
    while (head) 
    {
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);
    struct ListNode* cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) 
    {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    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

C++

class Solution 
{
public:
    int getLength(ListNode* head) 
    {
        int length = 0;
        while (head) 
        {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 0; i < length - n; ++i) 
        {
            cur = cur->next;
        }
        cur->next = cur->next->next;
       
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
        //return dummy->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

20.有效的括号

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

学栈的时候的入门习题：括号匹配

class Solution 
{
public:
    bool isValid(string s) 
    {
        if (s.size() % 2)
        {
            return false;
        }
        stack<char>a;
        for (auto n : s)
        {
            if (n == '(' || n == '[' || n == '{')
            {
                a.push(n);
            }
            else
            {
                if (a.empty())
                {
                    return false;
                }
                if (n == ')' && a.top() == '(')
                {
                    a.pop();
                }
                else if (n == ']' && a.top() == '[')
                {
                    a.pop();
                }
                else if (n == '}' && a.top() == '{')
                {
                    a.pop();
                }
                else
                {
                    return false;
                }
            }
        }
        if (a.empty())
            return true;
        else
            return false;
    }
};

  • 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

21. 合并两个有序链表

21. 合并两个有序链表

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

示例 1：

img

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

写链表、二叉树这类给了初始化的习题时，一定要自己实现一下初始化过程！！不然面试笔试会吃亏

之后的每个链表题，我都会在题解里强调一下

初始化的C实现

struct ListNode
{
	int val;
	struct ListNode* next; 
};

  • 1
  • 2
  • 3
  • 4
  • 5

初始化的C++实现

 struct ListNode 
 {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}	
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

真的是唯手熟尔！！今天写的时候居然一遍过，执行的时候也完全没卡

最后if…else…这块可以简化下 p->next=list1?list1:list2;

class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode* p =new ListNode(0);
        ListNode* q = p;
        while (list1 && list2)
        {
            if (list1->val <= list2->val)
            {
                p->next = list1;
                p = p->next;
                list1 = list1->next;
            }
            else
            {
                p->next = list2;
                p = p->next;
                list2 = list2->next;
            }
        }
        
        /*if (list1 != NULL)
        {
            p->next = list1;
        }
        else
        {
            p->next = list2;
        }*/
        p->next=list1?list1:list2;
        return q->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

23. 合并K个升序链表

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

采用了21题的思路，先两两排序，再接着排序

还有分治、优先队列的解法，之后再来填坑吧
class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        ListNode* p = new ListNode(0);
        ListNode* q = p;
        while (list1 && list2)
        {
            if (list1->val <= list2->val)
            {
                p->next = list1;
                p = p->next;
                list1 = list1->next;
            }
            else
            {
                p->next = list2;
                p = p->next;
                list2 = list2->next;
            }
        }
        p->next = list1 ? list1 : list2;
        return q->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        if (lists.size() == 0)
        {
            return NULL;
        }
        else if (lists.size() == 1)
        {
            return lists[0];
        }
        for (int i = 0; i < lists.size()-1; i++)
        {
            lists[i + 1] = mergeTwoLists(lists[i], lists[i + 1]);
        }
        return lists[lists.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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

29. 两数相除

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

先附上 超时 的代码（用了long）

流程：

1.被除数为0返回0

2.判断除数、被除数的正负，只有当其一为负，才会在都变为绝对值除之后的结果变号

3.除数为1返回被除数，在此就会有溢出的问题，INT_MIN/1会溢出

4.循环（被除数>=除数）：被除数不停的减除数

5.return 结果

class Solution
{
public:
	int divide(int dividend, int divisor)
	{
		if (dividend == 0)
			return 0;
		long a = dividend;
		long b = divisor;
		int tmp = 0;
		if (dividend < 0 || divisor < 0)
		{
			if (!(dividend < 0 && divisor < 0))
				tmp = 1;
			a = abs(a);
			b = abs(b);
		}

		if (b == 1)
		{
			if (tmp == 1)
			{
				return -a;
			}
			return a > INT_MAX ? INT_MAX : a;
		}

		int num = 0;
		while (a >= b)
		{
			a -= b;
			num++;
		}
		return tmp ? -num : num;
	}
};

  • 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

33. 搜索旋转排序数组

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

利用二分法+旋转排序数组的性质查找

旋转排序数组：较大->最大->最小->较小

用if…else…语句：

条件判断语句一：

nums[mid] >= nums[0] 代表mid及mid左是有序的，即mid在最大数即最大数的左侧

else 即mid在最小数即最小数的右侧

条件判断语句二：

nums[mid] > target && target >= nums[0] 划分了target的范围就在 [nums[0],nums[mid-1])之间

class Solution
{
public:
	int search(vector<int>& nums, int target)
	{
		int left = 0;
		int right = nums.size()-1;
		int mid; 
		while (left <= right)
		{
			mid = left + (right - left) / 2;
			if (nums[mid] == target)
			{
				return mid;
			}
			if (nums[mid] >= nums[0])//mid左有序
			{
				if (nums[mid] > target && target >= nums[0])//在有序的范围内
				{
					right = mid - 1;
				}
				else
				{
					left = mid + 1;
				}
			}
			else//mid右有序
			{
				if (nums[mid] < target && target < nums[0])
                //在有序的范围内，target <= nums[nums.size()-1]也可
				{
                    left = mid + 1;					
				}
				else
				{
					right = mid - 1;
				}
			}
		}
		return -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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

50. Pow(x, n)]

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即x^n）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

自己想的是 x*myPow(x, n-1) ，结果stack-overflow

法一 ：

评论区看到的一个绝妙思路

和官解二类似

每个二进制数位都有一个权值，权值如下图所示，最终结果就等于所有二进制位为1的权值之积，, 例如上述 x^77次方对应的二进制 (1001101) 和每个二进制位的权值如下

 1	      0	      0	     1	    1	 0	   1
x^64	x^32	x^16	x^8	   x^4	x^2	  x^1

最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77

  • 1
  • 2
  • 3
  • 4

而且我们不必预先把每一个二进制位的权值计算出来，我们可以一边计算结果，一边计算权值

class Solution
{
public:
    double myPow(double x, int n)
    {
        if (x == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return x;
        }

        long power = n;// 为了保证-n不溢出->INT_MIN，先转换成long类型
        if (n < 0)
        {         // 如果n小于0， 求1/x的-n次方
            power = abs(power);
            x = 1 / x;
        }
        double weight = x;  // 权值初值为x, 即二进制位第1位的权值为x^1
        double res = 1;//保存结果
        while (power)
        {
            // 如果当前二进制位为1， 让结果乘上这个二进制位上的权值, 
            // 该位权值在上一轮迭代中已经计算出来了
            if ((power & 1) == 1)
            {
                res *= weight;
            }
            weight *= weight;   // 计算下一个二进制位的权值
            power >>= 1;
        }
        return res;
    }
};

  • 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

法二：

官方题解:快速幂 + 递归

如果我们要计算 x^77，我们可以按照：
x→x ^2→x ^4 →x ^9 →x ^19 →x 38→x 77的顺序

在 x→x ^2，x ^2→x ^4 ，x ^19→x ^38 这些步骤中，我们直接把上一次的结果进行平方；

而在 x4→x9 ，x^9 →x 19 ，x38→x77 这些步骤中，把上一次的结果进行平方后，还要额外乘一个x。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了：

  • 当我们要计算 x^n 时，我们可以先递归地计算出 y = x^⌊n/2⌋，其中 ⌊a⌋ 表示对 a 进行下取整；

  • 根据递归计算的结果，如果 n为偶数，那么 x^n = y^2x n=y2；

    如果 n 为奇数，那么 x^n = y^2 * x；

  • 递归的边界为 n=0，任意数的 0 次方均为 1。

class Solution
{
public:
    double quickMul(double x, long long N)
    {
        if (N == 0)
        {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n)
    {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

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

法三：

官解：快速幂 + 迭代

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘 x。但我们不妨找一找规律，看看哪些地方额外乘了 x，并且它们对答案产生了什么影响。

我们还是以 x^77 作为例子：x→x ^2→x ^4 →x ^9 →x ^19 →x 38→x 77并且把需要额外乘 x的步骤打上了 + 标记。

可以发现：

QQ图片20211210174447

我们把这些贡献相乘，x* x^4* x8*x64恰好等于 x^77 。

而这些贡献的指数部分又是什么呢？

它们都是 2的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1，4，8 和64，恰好就对应了 77 的二进制表示 (1001101) 中的每个 1！

因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 n 的二进制拆分为

QQ图片20211210175020

class Solution
{
public:
    double quickMul(double x, long long N)
    {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0)
        {
            if (N % 2 == 1) 
            {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n)
    {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

  • 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

69. Sqrt(x)]

69. Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

二分法查找符合mid^2<x的最大m的值

因为要返回的是<x的mid最大值，所以要在mid^2<x时用ans记录下此刻mid的值，以免mid增大后不符合

class Solution 
{
public:
    int mySqrt(int x) 
    {
        int left = 1;
        int right = x;
        int mid;
        int ans;
        while (left <= right)
        {
            mid= left + (right - left) / 2;
            long tmp = (long)mid * mid;
            if (tmp == x)
            {
                return mid;
            }
            if (tmp > x)
            {
                right = mid-1;
            }
            else
            {
                ans=mid;
                left = mid + 1;
            }
        }
        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

70. 爬楼梯

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

dp[i]： 爬到第i层楼梯，有dp[i]种方法

因为n是一个正整数，所以不需考虑0的情况，初始化：n=1有一种，n=2有两种

当i>=3时，从dp[i]可以看出，dp[i] 可以有两个方向推出

（1）dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶就是dp[i]

（2）dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]

所以dp[i] = dp[i - 1] + dp[i - 2]

class Solution 
{
public:
    int climbStairs(int n)
    {
        if(n<3)
            return n;
        vector<int>dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        } 
        return dp[n];       
    }
};

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

二次写题解：

第一想法就是递归

climbStairs(int n)=climbStairs(n - 2) + climbStairs(n - 1);

不过超时了

class Solution
{
public:
	int climbStairs(int n)
	{
		if (n <= 0)
			return 0;
		if (n <= 2)
			return n;
		return climbStairs(n - 2) + climbStairs(n - 1);
	}
};

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

用数组迭代实现上述想法

class Solution 
{
public:
	int climbStairs(int n) 
	{
		if (n <= 2)
			return n;
		vector<int>arr(n);
		arr[0] = 1;
		arr[1] = 2;
		for (int i = 2; i < n; ++i)
		{
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr[n - 1];
	}
};

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

81. 搜索旋转排序数组 II

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

法一

本题与33题的区别是：本题是非降序->有重复元素，可能出现nums[0]==nums[nums.size()-1]等的情况

与33题相比加上了条件语句：nums[left] == nums[mid] && nums[mid] == nums[right]，避免形如{1,0,1,1,1,1,1}的数组出现时不能确定到底是mid左有序，还是mid右有序

不同点：判断target范围是从target >= nums[0]变为了target >= nums[left]，在此刻可以看做：数组范围由[nums[0],nums[nums.size()-1]]变为了[nums[left],nums[right]],边界数据均被删去的情况，依旧是为了避免旋转数组重复数存在时的区间判断问题（也可在33题中这么做）

相较于法一，个人认为法二更容易理解、易写

class Solution 
{
public:
    bool search(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                return true;
            }
			if (nums[left] == nums[mid] && nums[mid] == nums[right])
			{
				left++;
				right--;
			}
			else if (nums[mid]>=nums[left])//mid左有序
            {
                if (nums[mid] > target && target >= nums[left])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

  • 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

法二

简化：在二分之前“去掉”尾端重复元素

注意：left<=right-1（因为后续要执行right–）

二分代码和33题一样

class Solution
{
public:
    bool search(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (nums[left] == nums[right] && left <= right - 1)
        {
            right--;
        }
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                return true;
            }
            if (nums[mid] >= nums[0])//mid左有序
            {
                if (nums[mid] > target && target >= nums[0])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                if (nums[mid] < target && target < nums[0])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

  • 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

image-20211212164729214

153. 寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

先写一个投机取巧的解法

设置一个min，其他就按二分格式写，每次比较nums[mid]和min的值，最后return min；

class Solution 
{
public:
    int findMin(vector<int>& nums)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        int min = INT_MAX;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            min = fmin(min, nums[mid]);
            if (nums[mid] > nums[right])//mid左边有序,最小值在mid右边
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return min;
    }
};

  • 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

法二

普遍解法

我自己写二分习惯用left<=right,left=mid+1,right=mid-1,所以这道题两个两次，两次都错

class Solution
{
public:
	int findMin(vector<int>& nums)
	{
		int left = 0;
		int right = nums.size() - 1;
		int mid;
		while (left < right)
		{
			mid = left + (right - left) / 2;
			if (nums[mid] > nums[right])
			{
				left = mid + 1;
			}
			else
			{
				right = mid;
			}
		}
		return nums[left];
	}
};

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

最后贴上一个保存在自己笔记里的二分相关知识点

（本来忘记是谁总结的了，看到了“「二分」的本质是两段性”这句，是宫水三叶的总结的）

二分搜索

1.有序队列查值，用二分。

2.「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足，就可以用「二分」。

二分搜索有两种模板：

  • if ( left < right )时，缩减范围用left = mid + 1和right = mid
    • right边界始终维护语义nums[right] >= target（以普通二分搜索举例），这条语义通过检测if ( nums[mid] >= target )来实现，所以right = mid而非right = mid - 1
    • 循环退出后需要检测right维护的语义是否正确，即if ( nums[right] >= target )，因为right的位置可能一直没动处于右边界且该位置从未被检测过语义，因为我们设置的循环条件是if ( left < right )，如果设置成if ( left <= right )的话，最后left == right == mid可能致死循环
  • if ( left <= right)时，缩减范围用left = mid + 1和right = mid - 1
    • 中间直接检测if ( nums[mid] == target ) return mid，如果从未执行该语句而推出循环则说明未搜索到target
    • 条件检测用if ( left <= right )从而可以检测右边界的语义，从而就应该使用right = mid- 1而非right = mid

231. 2 的幂

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

法一

特判n<=0的情况

2的幂有一个特点：二进制中只有一位为1

class Solution 
{
public:
    bool isPowerOfTwo(int n) 
    {
        if (n <= 0)
            return false;
        int sum = 0;
        while (n)
        {
            if (n & 1)
                sum++;
            n >>= 1;
        }
        return sum == 1 ? true : false;
    }
};

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

法二

2的幂的特点：n&(n-1)==0

class Solution 
{
public:
    bool isPowerOfTwo(int n) 
    {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

300. 最长递增子序列

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution
{
public:
	int lengthOfLIS(vector<int>& nums)
	{
		vector<int> dp(nums.size(), 1);
		int min;
		for (int i = 1; i < nums.size(); i++)
		{
			for (int j = 0; j < i; j++)
			{
				if ((nums[i] > nums[j]))
				{
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
		}
		return *max_element(dp.begin(), dp.end());
	}
};

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

326. 3 的幂

326. 3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

依旧是一个递归

这个递归比较特殊：(n % 3)==0?isPowerOfThree(n / 3):false；

当n%3==0时，才进行下一步递归，否则返回false

退出条件同上题

class Solution 
{
public:
    bool isPowerOfThree(int n) 
    {
        if (n <= 0)
            return false;
        if (n == 1)
            return true;
        return (n % 3)==0?isPowerOfThree(n / 3):false;
    }
};

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

342. 4的幂

342. 4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true

法一

直接套上一题的模板

class Solution
{
public:
    bool isPowerOfFour(int n)
    {
        if (n <= 0)
            return false;
        if (n == 1)
            return true;
        return (n % 4) == 0 ? isPowerOfFour(n / 4) : false;
    }
};

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

法二

在2的幂（法二）的基础上（4的幂也是2的幂）增加了一个条件n & 0xaaaaaaaa==0

0xaaaaaaaa格式是1010 1010 1010 1010（从右至左：偶数位为1）

4的幂是 （从右至左：奇数位为1） eg.1 100 10000

class Solution
{
public:
    bool isPowerOfFour(int n)
    {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

367. 有效的完全平方数

367. 有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

二分法查找完全平方数

注意：为了避免溢出，tmp取long类型

class Solution 
{
public:
    bool isPerfectSquare(int num) 
    {
        int left = 1;
        int right = num;
        int mid;
        long tmp;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            tmp =(long) mid * mid;
            if (tmp == num)
                return true;
            else if (tmp > num)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }
};

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

371. 两整数之和

371. 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

循环之前：

c=a ^ b 用c记录a与b异或的值（不进位的和）

tmp = a & b 用tmp记录a与b的值 （进位时的和，因为有进位，计算的时候记得左移一位）

进入循环（有进位）：

用x记录下c的值，再去更新c的值

c = c ^ (tmp << 1) 更新c：记录c与进位tmp<<1异或的值（不进位的和）

tmp = x & (tmp << 1) 更新进位tmp：记录x与进位tmp<<1与的值（进位的和）

tmp必须设置成无符号型整数：如果左移的数的最高位是符号位，有的编译器会报错

runtime error: left shift of negative value -2147483648 (solution.cpp)

int getSum(int a, int b)
{
	int c = a ^ b;
	unsigned int tmp = a & b;
	int x = c;
	while (tmp)
	{
		x = c;
		c = c ^ (tmp << 1);
		tmp = x & (tmp << 1);
	}
	return c;
}

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

理解上述过程后，简化得以下结果

int getSum(int a, int b)
{
	while (b)
	{
		unsigned int carry = a & b;
		a = a ^ b;
		b = carry << 1;
	}
	return a;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

509. 斐波那契数

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

  • 1
  • 2

给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

递归：效率很慢（因为该题0 <= n <= 30，所以编译可以通过）

可以说是70题是斐波那契数的一个变形

class Solution 
{
public:
    int fib(int n)
    {
        if (n < 0)
            return 0;
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
};

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

数组迭代

class Solution
{
public:
	int fib(int n)
	{
		if (n <= 1)
			return n;
		vector<int>arr(n + 1);
		arr[0] = 0;
		arr[1] = 1;
		for (int i = 2; i <= n; i++)
		{
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr[n];
	}
};

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

1108. IP 地址无效化

1108. IP 地址无效化

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。

所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。

示例 1：

输入：address = “1.1.1.1”
输出：“1[.]1[.]1[.]1”

一个比较笨的写法

class Solution 
{
public:
    string defangIPaddr(string address) 
    {
        string s = "[.]";
        string s1;
        for (auto n : address)
        {
            if (n != '.')
            {
                s1.push_back(n);
            }
            else
                s1.append(s);
        }
        return s1;
    }
};

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

1137. 第 N 个泰波那契数

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

迭代走一波

class Solution
{
public:
    int tribonacci(int n) 
    {
        if (n == 0)
            return 0;
        else if (n <= 2)
            return 1;
        vector<int>arr(n + 1);
        arr[0] = 0;
        arr[1] = arr[2] = 1;
        for (int i = 3; i <= n; ++i)
        {
            arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
        }
        return arr[n];
    }
};

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

1365. 有多少小于当前数字的数字

1365. 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

朴素方法：两层循环

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

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

1389. 按既定顺序创建目标数组

1389. 按既定顺序创建目标数组

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

  • 目标数组 target 最初为空。
  • 按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
  • 重复上一步，直到在 nums 和 index 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1：

输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出：[0,4,1,3,2]
解释：
nums index target
0 0 [0]
1 1 [0,1]
2 2 [0,1,2]
3 2 [0,1,3,2]
4 1 [0,4,1,3,2]

insert函数：insert(where, value)

class Solution 
{
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index)
    {
        vector<int>target;
        for (int i = 0; i < nums.size(); ++i)
        {
            target.insert(target.begin() + index[i], nums[i]);
        }
        return target;
    }
};

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

1470. 重新排列数组

1470. 重新排列数组

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

示例 1：

输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7]
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]

找规律

class Solution
{
public:
	vector<int> shuffle(vector<int>& nums, int n)
	{
		vector<int>ret(nums.size());
		for (int i = 0; i < nums.size(); ++i)
		{
			if (i & 1)
			{
				ret[i] = nums[i / 2 + n];
			}
			else
				ret[i] = nums[i / 2];
		}
		return ret;
	}
};

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

1480. 一维数组的动态和

1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

nums[i] += nums[i - 1]

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

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

1492. n 的第 k 个因子

1492. n 的第 k 个因子

给你两个正整数 n 和 k 。

如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。

考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。

示例 1：

输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。

对于标记数k，每当n%i0，执行k–，当k0时，即此时的i为第k个因子

class Solution
{
public:
    int kthFactor(int n, int k)
    {
        for (int i = 1; i <= n; i++)
        {
            if (n % i == 0)
            {
                k--;
            }
            if(k==0)
            {
                return i;
            }
        }
        return -1;
    }
};

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

1920. 基于排列构建数组

1920. 基于排列构建数组

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

示例 1：

输入：nums = [0,2,1,5,3,4]
输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
= [0,1,2,4,5,3]

按照题意写

class Solution
{
public:
	vector<int> buildArray(vector<int>& nums)
	{
		vector<int>ret(nums.size());
		for (int i = 0; i < nums.size(); ++i)
		{
			ret[i] = nums[nums[i]];
		}
		return ret;
	}
};

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

1929. 数组串联

1929. 数组串联

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标 从 0 开始计数 ，对于所有 0 <= i < n 的 i ，满足下述所有要求：

  • ans[i] == nums[i]
  • ans[i + n] == nums[i]

具体而言，ans 由两个 nums 数组 串联 形成。

返回数组 ans 。

示例 1：

输入：nums = [1,2,1]
输出：[1,2,1,1,2,1]
解释：数组 ans 按下述方式形成：

  • ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
  • ans = [1,2,1,1,2,1]

法一：新建数组

class Solution
{
public:
    vector<int> getConcatenation(vector<int>& nums)
    {
        vector<int>ret(nums.size() * 2);
        for (int i = 0; i < nums.size(); i++)
        {
            ret[i] = ret[i + nums.size()] = nums[i];
        }
        return ret;
    }
};

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

发现效率很慢，就跑去瞥了一眼题解

法二：直接在nums后边push就行

class Solution
{
public:
	vector<int> getConcatenation(vector<int>& nums)
	{
		int n = nums.size();
		for (int i = 0; i < n; ++i)
		{
			nums.push_back(nums[i]);
		}
		return nums;
	}
};

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

2006. 差的绝对值为 K 的数对数目

2006. 差的绝对值为 K 的数对数目

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。

|x| 的值定义为：

  • 如果 x >= 0 ，那么值为 x 。
  • 如果 x < 0 ，那么值为 -x 。

示例 1：

输入：nums = [1,2,2,1], k = 1
输出：4
解释：差的绝对值为 1 的数对为：

  • [1,2,2,1]
  • [1,2,2,1]
  • [1,2,2,1]
  • [1,2,2,1]

按题意写

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

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

剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

和1108题一样

class Solution 
{
public:
    string replaceSpace(string s) 
    {
        string s1 = "%20";
        string s2;
        for (auto n : s)
        {
            if (n == ' ')
            {
                s2.append(s1);
            }
            else
                s2.push_back(n);
        }
        return s2;
    }
};

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

剑指 Offer 17. 打印从1到最大的n位数

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

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

注意点：n位数+从1开始

class Solution
{
public:
	vector<int> printNumbers(int n)
	{
		vector<int>ret;
		for (int i = 0; i < pow(10,n)-1; i++)
		{
			ret.push_back(i + 1);
		}
		return ret;
	}
};

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

剑指 Offer 58 - II. 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

这个题在C++里直接调用函数就行

class Solution 
{
public:
    string reverseLeftWords(string s, int n) 
    {
        string s1;
        s1.append(s.begin() + n, s.end());
        s1.append(s.begin(), s.begin() + n);
        return s1;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

剑指 Offer 64. 求1+2+…+n

剑指 Offer 64. 求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6

写了一个递归

递归注意事项：要有退出条件

class Solution
{
public:
    int sumNums(int n)
    {
        if (n == 1)
            return 1;
        return n + sumNums(n - 1);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

剑指 Offer 65. 不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

同371

int add(int a, int b)
{
	while (b)
	{
		unsigned int carry = a & b;
		a ^= b;
		b = carry << 1;
	}
	return a;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

面试题 08.05. 递归乘法

面试题 08.05. 递归乘法

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

输入：A = 1, B = 10
输出：10

A、B两数相乘（均非0）的实质就是A相加B次

采用递归实现

class Solution
{
public:
	int multiply(int A, int B)
	{
		if (A == 0 || B == 0)
			return 0;
		return A + multiply(A, B - 1);
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

面试题 17.01. 不用加号的加法

面试题 17.01. 不用加号的加法

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

输入: a = 1, b = 1
输出: 2

剑指offer65

int add(int a, int b)
{
	while (b)
	{
		unsigned int carry = a & b;
		a ^= b;
		b = carry << 1;
	}
	return a;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

LCP 01. 猜数字

LCP 01. 猜数字

小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？

输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。

示例 1：

输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。

过分水的一道题

class Solution
{
public:
    int game(vector<int>& guess, vector<int>& answer) 
    {
        int tmp = 0;
        for (int i = 0; i < 3; i++)
        {
            if (guess[i] == answer[i])
            {
                tmp++;
            }
        }
        return tmp;
    }
};

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

LCP 06. 拿硬币

LCP 06. 拿硬币

桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。

示例 1：

输入：[4,2,1]

输出：4

解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。

法一

总之就是尽量每次拿两枚，只在每堆原始个数为奇数个情况下有一次拿一枚的机会

所以可以直接利用int的特性（个数+1）/2

class Solution
{
public:
	int minCount(vector<int>& coins)
	{
		int tmp = 0;
		for (int i = 0; i < coins.size(); i++)
		{
			tmp += (coins[i] + 1) / 2;
		}
		return tmp;
	}
};

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

不过法一效率有点低，可以利用奇数的二进制&1==1的前提优化

法二

注意事项：注意&的优先级，要给coins[i] & 1加括号

class Solution
{
public:
	int minCount(vector<int>& coins)
	{
		int tmp = 0;
		for (int i = 0; i < coins.size(); i++)
		{
			tmp += coins[i] / 2 + (coins[i] & 1);
		}
		return tmp;
	}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/1017541?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号