提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

小小码民前来刷题——万人千题

2023-02-18 16:26:26 时间

文章目录

我回来了

?博客主页：秋名山码民的主页 ?欢迎关注?点赞?收藏⭐️留言? ?本文由秋名山码民原创，CSDN首发！ ✉️坚持和努力一定能换来诗与远方！ ?参考在线编程网站： ?作者水平很有限，如果发现错误，一定要及时告知作者

最近好长时间没有发文了，细心的彦祖已经发现，码神的名字换了，变成了码民，哈哈，普通人，如果给我一年的时间来刷算法，我相信我会变成码神的，秋名山的路很长，我还年轻，我还年轻……

刷题

今天聊啥呢？想了一下最近好像什么也没有做，就刷题了，力扣，洛谷，算法导论，啥都刷，那么我就来给各位彦祖分享一下最近刷题的心得，及我刷题过程中感觉对我有一定价值的题吧。

题目

单词合并：力扣

思路：

一开始是想用代码来实现俩个字符串之间的规律，后来发现行不通，只能一个一个比较了，用双指针+哈希来实现 

bool wordPattern(string pattern, string str) {
        unordered_map<string, char> str2ch;
        unordered_map<char, string> ch2str;
        int m = str.length();
        int i = 0;
        for (auto ch : pattern) {
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str[j] != ' ') j++;
            const string &tmp = str.substr(i, j - i);
            if (str2ch.count(tmp) && str2ch[tmp] != ch) {
                return false;
            }
            if (ch2str.count(ch) && ch2str[ch] != tmp) {
                return false;
            }
            str2ch[tmp] = ch;
            ch2str[ch] = tmp;
            i = j + 1;
        }
        return i >= m;
    }

pow(n,n) 幂的计算 

#define ll long long
/*double myPow(double x, int n)
{
	ll N = n;
	if (N < 0)
	{
		x = 1 / x;
		N = -N;
	}
	double ans = 1;
	for (ll i = 0; i < N; i++)
	{
		ans = ans * x;
	}
	return ans;
}暴力*/
/*
快速幂+递归
减少一半的计算量，导致logn
*/
class digui
{
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;
	}
};

数论中的丑数计算， 丑数：把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。 

#include<iostream>
using namespace std;
bool IsChou(int numbur)
{
	while (numbur % 2 == 0)
		numbur /= 2;
	while (numbur % 3 == 0)
		numbur /= 3;
	while (numbur % 5 == 0)
		numbur /= 5;
	return numbur == 1 ? true : false;
}
int GetUglyNumbur(int n)
{
	if (n <= 0)
		return 0;
	int numbur=0;
	int uglyFound = 0;
	while (uglyFound < n)
	{
		++numbur;
		if (IsChou)
			++uglyFound;
	}
	return numbur;
}
int main()
{
	cout << GetUglyNumbur(1500);
	
	return 0;
}

暴力解法，但是如果在秋名山不用排水渠过弯，能赢？ 所以说我们还应该来一个优化 

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int Min(int number1, int number2, int number3);
int GetUglyNumber2(int n)
{
	if (n <= 0)
		return 0;
	int *pUglyNumber = new int[n];
	pUglyNumber[0] = 1;
	int nextUglyNumber = 1;//下一个
	int *pMulitiply2 = pUglyNumber;
	int *pMulitiply3 = pUglyNumber;
	int *pMulitiply5 = pUglyNumber;

	while (nextUglyNumber < n)
	{
		int mmin = Min(*pMulitiply2 * 2, *pMulitiply3 * 3, *pMulitiply5 * 5);
		pUglyNumber[nextUglyNumber] = mmin;

		while (*pMulitiply2 * 2 <= pUglyNumber[nextUglyNumber])
			++pMulitiply2;
		while (*pMulitiply3 * 3 <= pUglyNumber[nextUglyNumber])
			++pMulitiply3;
		while (*pMulitiply5 * 5 <= pUglyNumber[nextUglyNumber])
			++pMulitiply5;

	}
	int ugly = pUglyNumber[nextUglyNumber - 1];
	delete[]pUglyNumber;
	return ugly;
}
int Min(int number1, int number2, int number3)
{
	int min = (number1 < number2) ? number1 : number2;
	min = (min < number3) ? min : number3;

	return min;
}

int main()
{
	cout << GetUglyNumber2(1500);
	return 0;
}

求多个元素的中位数 看题，其实吧我感觉这些统计数据的，先来一个排序，会方便很多，就比如这个题 

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //排序比较
        sort(nums.begin(),nums.end());
        //求一个中位数
        return nums[nums.size() / 2];
    }
};

汉诺塔 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。

递归：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        move(n, A, B, C);
    }

    void move(int n, vector<int>& A, vector<int>& B, vector<int>& C){
        if (n == 1){
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        move(n-1, A, C, B);    // 将A上面n-1个通过C移到B
        C.push_back(A.back());  // 将A最后一个移到C
        A.pop_back();          // 这时，A空了
        move(n-1, B, A, C);     // 将B上面n-1个通过空的A移到C
    }
};

重排？？？

这个题实属把我整不会了，打乱排序，然后让我比较，我直接给他排回去 

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        //排列后比较
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        if(s1 == s2)
            return true;
        else
            return false;
    }
};

相关文章