Joyce' Blog
0%

发表于

题目描述

给定一个整数 n，返回 n! 结果尾数中零的数量。

题解

乘积末尾能出现 0 的都是由 2*5 得到的，2的数量肯定比5多，因此只需要关注有多少个5就可以了。

  1. 循环。每隔5个数出现一个5，每隔25个数出现两个5，每隔125个数出现三个5，……，因此5的个数是：$n/5+n/25+n/125+…$，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int trailingZeroes(int n) {
        int res=0;
        while(n>=5)
        {
            n/=5;
            res+=n;
        }
        return res;
    }

  2. 递归。$f(n)=f(n/5)+n/5$，为什么能写成递归的形式？举个栗子，对于阶乘126!而言，数字126最接近的5的倍数是125，且$125 = 25x5$，也就是说对126!分解质因数，其一定能分解成$126! = 25x5 x 24x5 x 23x5 x 22x5 x…x 3x5 x 2x5 x 1x5 x…$形式，该式子中首先已经出现了25个5，但是仍需计算25!的阶乘中总共有多少个五，故可递归。
    链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/172-jie-cheng-hou-de-ling-di-gui-jie-fa-liang-xing/

    1
    2
    3
    4
    int trailingZeroes(int n) {
        if(n<5)return 0;
        return n/5+trailingZeroes(n/5);
    }

发表于

题目描述

给定一个正整数，返回它在 Excel 表中相对应的列名称。

题解

还是数学原理没搞清楚啊……在一个 0 上面卡那么久。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string convertToTitle(int n) {
        //相比于十进制：没有0占位；从右往左增加字符串
        string s="";
        int num=n;
        while(num>0)
        {
            num--;
            s=char('A'+(num%26))+s;
            num=num/26;
        }
        return s;
    }
};

$…+x_3{26}^2+x_2{26}^1+x_1*{26}^0=number$

$x_1$的正常范围是$0-25$，但现在是$1-26$，所以需要进行修正，在两边都减一：

$…+x_3{26}^2+x_2{26}^1+(x_1-1)*{26}^0=number-1$

发表于 更新于

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

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

题解

长除法，循环除法、取模直至余数为零。

特殊情况：被除数为0、最小负数除以-1会溢出、循环小数–需要用一个map来检查当前余数是否已经出现过，如果已经出现过，需要加括号。

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
string fractionToDecimal(int numerator, int denominator) {
	if (numerator == 0)return "0";
	string res = "";
	if ((numerator < 0) ^ (denominator < 0))res.append("-");
	long dividend = abs(numerator), divisor = abs(denominator), remainder = 0;
	res.append(to_string(dividend / divisor));
	remainder = dividend % divisor;
	if (remainder == 0)return res;
	unordered_map<long, int> map;
	res.append(".");
	while (remainder)
	{
		if (map.count(remainder))
		{
			int index = map[remainder];
			res.insert(index, "(");
			res.append(")");
			return res;
		}
		map[remainder] = res.length();
		remainder *= 10;
		res.append(to_string(remainder / divisor));
		remainder %= divisor;
	}
	return res;
}

发表于

题目描述

比较两个版本号 version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。

假设版本字符串非空，并且只包含数字和 . 字符。 . 字符用于分隔数字序列。版本号的每一级的默认修订版号为 0。

题解

先切割，再分段比较。

c++没有split函数，借助strtok函数来切割字符串。char strtok (char str, char * delim); 以delim为分隔符分割字符串str。返回从str开头开始的一个被分割的字符串。当没有被分割时则返回null。

int atoi(const char *str) 返回转换后的长整数，如果没有执行有效的转换，则返回零。

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
int compareVersion(string version1, string version2) {
	vector<int> vec1, vec2;
	char *p, *q;
	p = strtok(&version1[0], ".");
	while (p)
	{
		if (p)vec1.push_back(atoi(p));
		cout << p << endl;
		p = strtok(NULL, ".");
	}
	cout << "--------" << endl;
	q = strtok(&version2[0], ".");
	while (q)
	{
		vec2.push_back(atoi(q));
		cout << q << endl;
		q = strtok(NULL, ".");
	}
	int size1 = vec1.size();
	int size2 = vec2.size();
	int size = size1 < size2 ? size1 : size2;
	for (int i = 0; i < size; i++)
	{
		if (vec1[i] < vec2[i])return -1;
		else if (vec1[i] > vec2[i])return 1;
	}
	if (size == size1)
	{
		for (int i = size; i < size2; i++)
			if (vec2[i] > 0)return -1;
	}
	if (size == size2)
	{
		for (int i = size; i < size1; i++)
			if (vec1[i] > 0)return 1;
	}
	return 0;
}

还是双指针厉害，但是我不会，并且现在不想写。

发表于 更新于

题目描述

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

说明:

  • 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
  • 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

题解

太难了嘤，看了题解都还是不会写。总的来说就是用了桶排序和鸽笼原理吧。用桶将元素分类，不用比较每两个元素，而只需要比较这些桶即可。

  • 鸽笼原理：n 个物品放入 m 个容器中，如果 n > m 那么一定有一个容器装有至少两个物品。

若有 n 个元素，最大值为 max，最小值为 min，那么间距 t 最小为：( max - min ) / ( n - 1 )。

最关键的在于桶的大小。桶的大小是可以容纳的最大区间的范围，桶内实际区间范围大小等于桶内最大值减最小值，桶的大小 b 应该小于最小间距 t 且不小于 1 。比较相邻桶的时候，只需要比较前一个痛的最大值和后一个桶的最小值。桶的个数 k 为$⌈(max−min)/b⌉$。第 i 个桶保存的值区间为： $[min+i∗b, min+(i+1)∗b)$，由$\lfloor (num - min)/b$ 可以算出 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
class Bucket{
public:
    bool used=false;
    int min=INT_MAX;
    int max=INT_MIN;
};
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size=nums.size();
        if(size<2)return 0;
        int maxElem=*max_element(nums.begin(),nums.end());
        int minElem=*min_element(nums.begin(),nums.end());
        int bucketSize=max(1,(maxElem-minElem)/(size-1));
        int bucketNum=(maxElem-minElem)/bucketSize+1;
        vector<Bucket> buckets(bucketNum);
        for(int i=0;i<size;i++)
        {
            int k=nums[i];
            int index=(k-minElem)/bucketSize;
            buckets[index].used=true;
            buckets[index].min=min(k,buckets[index].min);
            buckets[index].max=max(k,buckets[index].max);
        }
        int maxGap=buckets[0].max-buckets[0].min;
        int lastMax=buckets[0].max;
        for(int i=1;i<bucketNum;i++)
        {
            if(buckets[i].used)
            {
                maxGap=max(buckets[i].min-lastMax,maxGap);
                lastMax=buckets[i].max;
            }
        }
        return maxGap;
    }
};

执行用时：16 ms, 在所有 C++ 提交中击败了54.55%的用户

内存消耗：8.9 MB, 在所有 C++ 提交中击败了54.67%的用户

时间复杂度：$O(n + b) \approx O(n))$。

线性遍历一遍数组中的元素，复杂度为 $O(n)$。找到桶之间的最大间距需要线性遍历一遍所有的桶，复杂度为$O(b)$。所以总复杂度是线性的。

空间复杂度：$O(2 \cdot b) \approx O(n)$的额外空间。

每个桶只需要存储最大和最小元素，因此额外空间和桶个数线性相关。

链接：https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<limits.h>//INT_MAX与INT_MIN的头文件
using namespace std;
void minNote()
{
	int imax = 0x7fffffff;
	int imin = 0x80000000;
	cout << imax << endl << imin << endl << INT_MAX << endl << INT_MIN << endl;
	int maxLimit = numeric_limits<int>::max();
	int minLimit = numeric_limits<int>::min();
	cout << maxLimit << endl << minLimit << endl;
	cout << 0x7fffffff << endl << 0x80000000 << endl;
}

//输出：
2147483647
-2147483648
2147483647
-2147483648
2147483647
-2147483648
2147483647
2147483648
1
2
#include<algorithm>// std::min_element, std::max_element
max_element()与min_element()返回区间 [first,last)中第一个最大值和第一个最小值对应的迭代器。
1
vector(size_type Count);	创建一个大小为Count的向量vect

发表于 更新于

题目描述

值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

题解

线性扫描

1
2
3
4
5
int findPeakElement(vector<int>& nums) {
    int index=0;
    while(index+1<nums.size()&&nums[index]<nums[index+1])index++;
    return index;
}

二分法

nums可视为交替的升序和降序序列。与右边相邻元素比较，可以知道当前是在上升坡度还是下降坡度。找到中间元素mid，若mid位于下降坡度，则峰值在左边；若mid位于上升坡度，则峰值在右边。

1
2
3
4
5
6
7
8
9
10
11
12
int findPeakElement(vector<int>& nums) {
    int left=0;int right=nums.size()-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]<nums[mid+1])
            left=mid+1;
        else
            right=mid;
    }
    return left;
}

发表于

题目描述

编写一个程序，找到两个单链表相交的起始节点。

题解

这就有点魔幻了。为啥连续做的两道题都是字节面试的编程题。。。带我缓缓，下午再做。

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
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A,*B;
        A=headA;B=headB;
        while(A!=B)
        {
            if(!A&&!B)
            {
                A=headB;
                B=headA;
            }
            else if(!A)
            {
                A=headB;
                B=B->next;
            }
            else if(!B)
            {
                B=headA;
                A=A->next;
            }
            else
            {
                A=A->next;
                B=B->next;
            }
        }
        return A;
    }

两个指针把两条链表都走一遍就会相遇了。

发表于

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

提示：

  • pop、top 和 getMin 操作总是在 非空栈 上调用。

题解

用了一个栈来进行 pop, push 和 top 操作，一个整型用来保存最小值。pop 操作时需要借助另一个临时的栈，来处理最小值被弹出的情况。

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
class MinStack {
    stack<int> st;
    int minItem;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        if(st.empty())minItem=x;
        st.push(x);
        if(x<minItem)minItem=x;
    }
    
    void pop() {
        int k=st.top();
        st.pop();
        if(k==minItem&&!st.empty())
        {
            minItem=st.top();
            stack<int> tmp;
            while(!st.empty())
            {
                int t=st.top();
                minItem=t<minItem?t:minItem;
                tmp.push(t);
                st.pop();
            }
            while(!tmp.empty())
            {
                st.push(tmp.top());
                tmp.pop();
            }
        }
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minItem;
    }
};

执行用时：48 ms, 在所有 C++ 提交中击败了51.38%的用户

内存消耗：14.7 MB, 在所有 C++ 提交中击败了41.60%的用户

发表于 更新于

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。请找出其中最小的元素。

注意数组中可能存在重复的元素。

题解

（我好像做过……但是我又不会了）

把所有可能的情况都列一遍也是能解出来的：

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
int findMin(vector<int>& nums) {
    int left=0;
    int right=nums.size()-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[left]<nums[right])return nums[left];
        if(nums[left]==nums[right])right--;
        //nums[left]>nums[right]
        else if(nums[mid]<nums[left])
        {
            right=mid;
        }
        else if(nums[mid]>nums[left])
        {
            left=mid+1;
        }
        //nums[mid]==nums[left]
        else if(nums[mid]>nums[right])
        {
            left=mid+1;
        }
        else{
            left++;
        }
    }
    return nums[left];
}

但是效率也太低了：

执行用时：20 ms, 在所有 C++ 提交中击败了6.72%的用户

内存消耗：12.1 MB, 在所有 C++ 提交中击败了55.20%的用户

如果直接遍历一遍：

1
2
3
4
5
6
int findMin(vector<int>& nums) {
    int min=nums[0];
    for(int i=1;i<nums.size();i++)
        min=min<nums[i]?min:nums[i];
    return min;
}

执行用时：8 ms, 在所有 C++ 提交中击败了93.60%的用户

内存消耗：12 MB, 在所有 C++ 提交中击败了92.74%的用户

暴力求解效率居然这么高？？那还做个毛线。

还是要多学习：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMin(vector<int>& nums) {
        int left=0;
        int right=nums.size()-1;
        while(left<right)
        {
            int mid=(left+right)/2;
            if (nums[mid] > nums[right])
                left = mid + 1;
            else if(nums[mid] < nums[right])
                right = mid;
            else
                right = right - 1 ;
        }
        return nums[left];
    }

执行用时：4 ms, 在所有 C++ 提交中击败了99.66%的用户

内存消耗：12 MB, 在所有 C++ 提交中击败了92.74%的用户

唉，应该是和右端点做比较啊！

发表于 更新于

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

题解

1
2
3
4
5
6
7
8
9
10
11
12
int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            if(nums[left]<nums[right])return nums[left];
            int mid=(left+right)/2;
            if(nums[mid]>nums[left])left=mid+1;
            else if(nums[mid]<nums[left])right=mid;
            else return nums[right];
        }
        return nums[left];
    }