手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

淼淼刷力扣

时间:2021/5/30 21:55:51|来源:|点击: 次

【努力刷力扣】第三十二天 --- 力扣477+1528(string)

  • 引言
  • 题目一(1528)要求:
    • 整体思路一:
    • 具体代码一(内附注释):
    • 整体思路二:
    • 具体代码二(内附注释):
  • 题目二(477)要求:
    • 必备知识
    • 解法一:暴力破解(c++必超时,Java可以过)
    • 整体按位计数法
      • 第一:
      • 具体代码(附有注释)

引言

本人初次尝试写博客,希望各位看官大佬多多包容
有错误希望巨巨们提出来,我一定会及时改正,谢谢大家
在自己最好的年纪,找到了未来的目标
还有1年奋斗刷题,明年去面试实习,加油!
博主最近要参加竞赛,所以暂时调整训练计划。

题目一(1528)要求:

在这里插入图片描述

整体思路一:

基于排序的调整方案,这一点是很好想的,通过观察题目我们可以发现,string的真实顺序其实就是上方数组从0到n-1的递增顺序,所以排序即可
五种排序(快速排序,堆排序,归并排序,希尔排序和c++库函数sort排序)见我另一篇博客[五种排序]。(https://blog.csdn.net/qq_45678698/article/details/117226919)

具体代码一(内附注释):

这里一定要注意的是,在第一个数组移动的时候,对应的string一定要跟着一起动!!!!

class Solution {
public:
	string restoreString(string s, vector<int>& indices) {
		this->indices = indices;
		this->s = s;
		QuickSort(0, s.size() - 1);
		return this->s;
	}
private:
	string s;
	vector<int> indices;
	//快速排序,记住一个核心,让基准数左边都小于它,右边都大于它
	void QuickSort(int i, int j) {
		if (i > j) {
			return;
		}
		int item = indices[i];//设定基数
		int left = i;//左哨兵
		int right = j;//右哨兵,因为基数取得左侧,所以右哨兵先动
		while (left != right) {//写的时候一定时时刻刻检测退出条件,即哨兵相遇
			while (right != left && indices[right] >= item) {
				right--;
			}
			while (right != left && indices[left] <= item) {
				left++;
			}
			swap(indices[left], indices[right]);
			swap(s[left], s[right]);
		}
		swap(indices[left], indices[i]);
		swap(s[left], s[i]);
		QuickSort(i, left - 1);
		QuickSort(left + 1, j);
	}
};

(所有代码均已在力扣上运行无误)

经测试,该代码运行情况是(经过多次测试所得最短时间):

在这里插入图片描述

整体思路二:

通过上述方法也可知道,上方给的数组就是对下方string正确位置,即给别人的一种"导航",所以我们另开空间,按照"导航"指示重新填写一个全新的string即可。

具体代码二(内附注释):

class Solution {
public:
	string restoreString(string s, vector<int>& indices) {
		int len = s.size();
		string result(len, 0);
		for (int i = 0; i < len; i++) {
			result[indices[i]] = s[i];//按照导航重新填写string
		}
		return result;
	}
};

(所有代码均已在力扣上运行无误)

经测试,该代码运行情况是(经过多次测试所得最短时间):
在这里插入图片描述
时间复杂度:O(N),其中 N 为字符串 s 的长度。我们只需对字符串 s 执行一次线性扫描即可。

题目二(477)要求:

汉明距离广泛应用于多个领域。在编码理论中用于错误检测,在信息论中量化字符串之间的差异。

两个整数之间的汉明距离是对应位置上数字不同的位数。
在这里插入图片描述

必备知识

1、我们有a个冰棍一,b个冰棍二,现在我们要比较有多少个不同的冰棍。冰棍一之间和冰棍二之间没有比较的意义,必定是相同的,所以任意一个冰棍一,进入到了冰棍二的那堆里,发现了b个不同,a个冰棍一都去了一遍,所以总共a*b个不同。
2、二进制位数的比较是互不影响的,完全可以分开比较!

解法一:暴力破解(c++必超时,Java可以过)

我之前做过一道两个数计算汉明距离,可以用很有技巧的算法,详情见两个数汉明距离,这道题偷懒了,就想着直接用现成的函数,在添加任意两个数计算的模块即可。但是!!!!!!!!本体数据量极大并且每个数都很大,这样的话计算量将达到N!次,如果N很大,数也很大,直接超时。

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = i+1;j < nums.length; j++){
                res += getHamm(nums[i],nums[j]);
            }
        }
        return res;
    }
    private int getHamm(int x,int y){
        return Integer.bitCount(x^y);
    }
}

(所有代码均已在力扣上运行无误)

经测试,该代码运行情况是(经过多次测试所得最短时间):

在这里插入图片描述
由此可见此题数据量之庞大,以及这个算法的局限性,这种算法针对数据量小还可以,一旦卡数据就完蛋了。

整体按位计数法

第一:

经验:
1、针对两个数字求汉明距离的时候,最佳的选择是先取异或突出差异(即有差异为1,反之为0),在调用库函数或者不断地 s&s-1,不要按位查找。
2、但是一但像本题这样,拥有大量的数据并且数据还很大,我们就可以直接一位一位的统计,因为不同比特位之间毫无关系,互不影响,所以我直接一位一位比较,比如第一位时,看零的个数,再看一的个数,二者相乘即为不同的位数,是汉明距离一部分,即是换个角度去看待汉明距离,不是横着看,一旦数据量大了,我就把所有数据并列写,竖着按照一个一个比特位这样计数。

具体代码(附有注释)

注:
1、在统计每一个数的最右侧位一的个数时,我不希望别的位打扰我,并且只保留最右侧位(因为最右侧位对应十进制0或者1),每次只处理这一位,保证了处理完的数是0、1,直接加就行,因为我统计的就是0和1的个数(二进制为0、1),这样直接相加就行了,我先统计1的个数,发现是1就加,是0也加(因为没影响),综上在提取最右侧的位的时候&1,只保留了最右侧位。
2、当该数统计完最右侧位的时候,最右侧位没用了,所以右移干掉它。所以每一次在计算的时候,i是控制查询的位数,就得把查询的位数对准最右侧,所以先移位对准,在统计。
3、每次只能是&1,不可以不移位而去每次把1右移1位,因为这样对不准最右侧,得到的数不是0或1,无法直接加。

class Solution {
public:
	int totalHammingDistance(vector<int>& nums) {
		int num = nums.size();
		int ans = 0;
		for (int i = 0; i < 30; i++) {//最外层控制位数,经计算最大的数不超过2^30,所以外层控制查找30位即可。
			int num_one = 0;//统计1的个数,这样的话取得最右侧不论0还是1直接加就完了,
			for (int val : nums) {//加强for循环
				num_one += (val >> i) & 1;//解释在上面
			}
			ans += num_one * (num - num_one);
		}
		return ans;
	}
};

所有代码均已在力扣上运行无误)

经测试,该代码运行情况是(经过多次测试所得最短时间):超过99%提交
在这里插入图片描述
时间复杂度:O(n⋅L)。其中 n 是数组 nums 的长度,L=30。

Copyright © 2002-2019 某某自媒体运营 版权所有