菜鸡的博客 | WTCL

旋转数组中的最小数字

你快乐吗？

旋转数组中的最小数字 C++。二分。。。left表示当前查找范围的左边界，right表示当前查找范围的右边界，mid = (left + right) / 2;。分以下情况：如果rotateArray[mid] >= rotateArray[left]，说明那个旋转点在mid的右边，则有： left = mid; 如果rot...

Posted by bbkgl on September 26, 2019

斐波那契数列

你快乐吗？

斐波那契数列 C++。这题真的没什么好说的了。。。公式：f(n) = f(n-1) + f(n-2)，边界：f(0) = 0, f(1) = 1 代码如下： class Solution { public: int Fibonacci(int n) { int dp[40]; dp[0] = 0; dp[1] = 1; ...

Posted by bbkgl on September 26, 2019

整数中1出现的次数

你快乐吗？

整数中1出现的次数 C++，模拟，经典题。有点像数学题2333。思路：从个位到最高位遍历n，用cur表示当前位的数字，it表示是个位百位千位。。。，left表示左边的数，right表示右边的数，比如n = 12345, it = 100 ，则cur = 3, left = 12, right = 45；以上n = 12015为例，将每个位上1的个数都算出来，然后求和...

Posted by bbkgl on September 26, 2019

数组中重复的数字

你快乐吗？

数组中重复的数字 C++，原数组进行hash。题目中说明了数字范围是[0, length - 1]就很明显有让原数组hash的意思了。可以把被访问过这一信息，直接用原数组记录，具体方法我想到两种，假设当前访问到t = numbers[i]： numbers[t] += length; numbers[t] = -numbers[t]；下次再碰到同样为t的值时，只要...

Posted by bbkgl on September 26, 2019

数组中的逆序对

你快乐吗？

数组中的逆序对 C++，归并排序的分治思想。其实做完以后，不仅求出了逆序对，而且把整个数组也排序了。分治的思想，将整个序列分成近似的两半，再细分，1/2—>1/4。。。直到一个子序列中只有一个元素：不说了，有点烦2333。 class Solution { public: int InversePairs(vector<int> data) { ...

Posted by bbkgl on September 26, 2019

数组中只出现一次的数字

你快乐吗？

数组中只出现一次的数字 C++，位运算，按位异或和按位与。首先就是要知道，一个数a和初始为0的数b一次异或(b = a ^ b)，会得到b = a，两次异或，则b = 0。所以如果一个序列中，只有一个元素a出现次数为奇数，其他序列出现次数为偶数，将数b = 0与序列中所有值进行异或运算，则最终b = a。这道题中给的序列中有两个出现了一次的元素a、b，其他都出现了两次。我们可以把这...

Posted by bbkgl on September 26, 2019

数组中出现次数超过一半的数字

你快乐吗？

数组中出现次数超过一半的数字 C++，我也不知道考点算什么，模拟吧。利用一个数学特点：如果数组中一个数字出现的频次大于数组的一半长度，则出现频次会比其他数字的频次和还大；定义两个整型变量，ans和cnt，前者表示当前记录的数字，后者是数字出现次数： ans = numbers[0]，cnt = 1，遍历整个序列；如果碰到的数字和ans相同，cnt++； ...

Posted by bbkgl on September 26, 2019

数字在排序数组中出现的次数

你快乐吗？

数字在排序数组中出现的次数 C++，二分。 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int index = Find(data, k); if (index == -1) return 0; int left = index...

Posted by bbkgl on September 26, 2019

数值的整数次方

你快乐吗？

数值的整数次方 C++，实现求幂函数power。下面说下思路：如果a>=0：如果b是偶数：a^b = a^(b/2) x a^(b/2); 如果b是奇数：a^b = a^(b/2) x a^(b/2) x a; 边界条件：a^0 = 1, a^1 = a; 如果a<0： ...

Posted by bbkgl on September 26, 2019

把数组排成最小的数

你快乐吗？

把数组排成最小的数 C++，排序，cmp自定义排序规则。这道题很有意思，其实和PAT甲级的一道题差不多。首先把整数数组转化成字符串数组，然后在数组里对所有字符串进行排序。排序的规则是：相邻两元素组成的数字要达到最小。也就是说比较数组[a, b]中是否a + b < b + a，满足这个规则，整个数组连成的字符串就能达到最小。 class Solution { pub...

Posted by bbkgl on September 26, 2019

我太菜了

旋转数组中的最小数字

你快乐吗？

斐波那契数列

你快乐吗？

整数中1出现的次数

你快乐吗？

数组中重复的数字

你快乐吗？

数组中的逆序对

你快乐吗？

数组中只出现一次的数字

你快乐吗？

数组中出现次数超过一半的数字

你快乐吗？

数字在排序数组中出现的次数

你快乐吗？

数值的整数次方

你快乐吗？

把数组排成最小的数

你快乐吗？

FEATURED TAGS

ABOUT ME

FRIENDS