LeetCode-2
492 构造矩形
刷题时间:2021-10-23
过于简单,开根号,然后慢慢查找就行
func constructRectangle(area int) []int {
var i int = int(math.Sqrt(float64(area)))
for area%i > 0 {
i--
}
return []int{area / i, i}
}
638 大礼包
刷题时间:2021-10-24
我一眼就看出来用dfs来写,不过我不会写,最后还是抄网上的人,理一下思路然后自己再敲一遍。
就计算所有需要的原价,然后循环special,每次减去其中一个大礼包的,然后在dfs,只不过needs变少了一个大礼包的量,钱是dfs+大礼包的钱,再和原价格相比,算出最低的价格。
func shoppingOffers(price []int, special [][]int, needs []int) int {
minPrice := 0
//计算原价
for i, v := range needs {
minPrice += price[i] * v
}
//每次计算大礼包
loop:
for _, s := range special {
newNeeds := make([]int, len(needs))
copy(newNeeds, needs)
for i := range newNeeds {
newNeeds[i] -= s[i]
if newNeeds[i] < 0 {
continue loop
}
}
curPrice := shoppingOffers(price, special, newNeeds) + s[len(price)]
if minPrice > curPrice {
minPrice = curPrice
}
}
return minPrice
}
还有个是背包解法,不看了,早忘了,刷到最简单的再说吧。
240 搜索二维矩阵 II
刷题时间:2021-10-25
暴力法就不说了,二分法也不说了,没想到是每一行二分法,直接说取巧的方法
就是从右上角开始搜索,就这
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
x, y := 0, n-1
for x < m && y >= 0 {
if target == matrix[x][y] {
return true
} else if target > matrix[x][y] {
x++
} else {
y--
}
}
return false
}
26 删除有序数组中的重复项
刷题时间: 2021-10-25
初级算法数组的第一题,唉,我可真笨啊,双指针我又给忘了
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
res := 0
for i := 1; i < len(nums); i++ {
if nums[i] != nums[res] {
res++
nums[res] = nums[i]
}
}
return res + 1
}
js版本,还是一如既往的笨啊
var removeDuplicates = function (nums) {
let left = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] != nums[left]) {
left++;
nums[left] = nums[i];
}
}
return left + 1;
};
121 买卖股票的最佳时机
就正常写法,一次遍历就行了
func maxProfit(prices []int) int {
res := 0
low := prices[0]
for _, p := range prices {
if p-low > res {
res = p - low
} else if p-low < 0 {
low = p
}
}
return res
}
js版本的动态规划,这个简单题目的动态规划可真的难,
dp[i][0]表示第i天持有股票所得最多现金 ,这里可能有同学疑惑,本题中只能买卖一次,持有股票之后哪还有现金呢?其实一开始现金是0,那么加入第i天买入股票现金就是 -prices[i], 这是一个负数。
dp[i][1]表示第i天不持有股票所得最多现金
这个方法真的是又长又臭啊,而且方法效果极差。
var maxProfit = function (prices) {
const n = prices.length;
const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], -prices[i])
dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0])
}
return dp[n - 1][1];
};
122 买卖股票的最佳时机 II
和上面那题差不多,稍微改改就行,但是没有下面这个简略,感觉这应该算是中等题
这是贪心算法,只贪心正利润的一天,然后加起来
func maxProfit(prices []int) (ret int) {
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
ret += prices[i] - prices[i-1]
}
}
return
}
js版本的动态规划,和上面那题差不多一样,但是有一处需要修改,因为所持有的现金除了这次买入的,还可能有之前卖过的利润
var maxProfit = function (prices) {
const n = prices.length;
const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + -prices[i])
dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0])
}
return dp[n - 1][1];
};
496 下一个更大元素 I
刷题时间:2021-10-26
自己只会暴力解法,然后想了有一个进阶的想法,可惜是错误的。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> v;
for (int& i : nums1) {
bool flag = false;
int res = -1;
for (int& j : nums2) {
// cout << i << " " << j << endl;
if (i == j) {
flag = true;
} else if (i < j && flag == true) {
res = j;
break;
}
}
v.push_back(res);
}
return v;
}
};
进阶的解法是用单调栈+哈希表的方式,
一但要求下一个更大的元素,就是用单调栈解,力扣题库相似的题目都是这个解法
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> hashmap;
stack<int> st;
for (int i = nums2.size() - 1; i >= 0; --i) {
int num = nums2[i];
while (!st.empty() && num >= st.top()) {
st.pop();
}
hashmap[num] = st.empty() ? -1 : st.top();
st.push(num);
}
vector<int> res(nums1.size());
for (int i = 0; i < nums1.size(); ++i) {
res[i] = hashmap[nums1[i]];
}
return res;
}
};
js版本
var nextGreaterElement = function (nums1, nums2) {
const res = new Array(nums1.length).fill(-1);
const map = new Map();
const st = [];
for (let i = 0; i < nums2.length; i++) {
while (st.length && nums2[i] > nums2[st[st.length - 1]]) {
const index = st.pop();
// key=数字,value=右侧第一个大的数字
map.set(nums2[index], nums2[i]);
}
st.push(i);
}
for (let i = 0; i < nums1.length; i++) {
res[i] = map.get(nums1[i]) || -1;
}
return res;
};
704 二分查找
刷题时间:2021-10-26
就是纯粹的练一下二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size();
while (r > l) {
int mid = (r - l) / 2 + l;
if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid;
} else {
return mid;
}
}
return -1;
}
};
js版本,二分法,左闭右闭[left,right]
- while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle – 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle – 1
var search = function (nums, target) {
const n = nums.length;
let l = 0,
r = n - 1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (nums[mid] > target) {
r = mid - 1;
} else if (nums[mid] == target) {
return mid;
} else {
l = mid + 1;
}
}
return -1;
};
左闭右开,不同之处就是r的初始值,判断条件没有等于号,以及r=mid
var search = function (nums, target) {
const n = nums.length;
let l = 0,
r = n;
while (l < r) {
const mid = Math.floor((l + r) / 2);
if (nums[mid] > target) {
r = mid;
} else if (nums[mid] == target) {
return mid;
} else {
l = mid + 1;
}
}
return -1;
};
278 第一个错误的版本
刷题时间:2021-10-26
func firstBadVersion(n int) int {
l, r := 0, n
for l < r {
m := int(uint(l+r) >> 1)
if !isBadVersion(m) {
l = m + 1
} else {
r = m
}
}
return l
}
或者一句话的事情
return sort.Search(n, func(version int) bool { return isBadVersion(version) })
35 搜索插入位置
刷题时间:2021-10-26
就是查找第一个大于等于目标值的下标
var searchInsert = function (nums, target) {
const n = nums.length;
let left = 0,
right = n;
while (left < right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
977 有序数组的平方
刷题时间:2021-10-27
双指针的方法,两头开始,然后添加最大的,我犯得错误是从vector从左添加,应该是从右添加,这样子就不用置换了,干。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
int i = 0, j = n - 1;
vector<int> v(n);
for (int pos = n - 1; pos >= 0; pos--) {
if (abs(nums[i]) > abs(nums[j])) {
v[pos] = (nums[i] * nums[i]);
i++;
} else {
v[pos] = (nums[j] * nums[j]);
j--;
}
}
return v;
}
};
js版本
var sortedSquares = function (nums) {
const n = nums.length;
let l = 0;
r = n - 1;
const res = new Array(n).fill(0);
let i = n - 1;
while (i >= 0) {
if (Math.abs(nums[l]) > Math.abs(nums[r])) {
res[i--] = nums[l] * nums[l];
l++;
} else {
res[i--] = nums[r] * nums[r];
r--;
}
}
return res;
};
还有一种是
从左到右依次求平方,负值的平方值就是从大到小,正的平方值是从小到大。然后归并排序就行了。算法就不写了,我没写。
189 旋转数组
法一:当然是用额外的数组空间了,小学生想法。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> newArr(n);
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
nums.assign(newArr.begin(), newArr.end());
}
};
法二:翻转数组,翻三次,先翻转整个,然后翻转前面和后面
const reverse = (nums, start, end) => {
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
};
var rotate = function (nums, k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
};
法三:环状数组。
求得最小公约数,也就是循环到每次起点的次数,然后每次大循环内的小循环就会无限下去,直到遇上了大循环的原点,那么大循环的原点就+1。
小循环的逻辑就是往后k个替换,重复以往,直到回到原点。
可能有点绕,确实有点
func rotate(nums []int, k int) {
n := len(nums)
k %= n
// 最外面的循环为最小公约数的次数,也就是循环到原点的次数
for start, count := 0, gcd(k, n); start < count; start++ {
// cur此轮次数的起点
pre, cur := nums[start], start
for ok := true; ok; ok = cur != start {
next := (cur + k) % n
nums[next], pre, cur = pre, nums[next], next
}
}
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
217 存在重复元素
排序,然后查找
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
};
哈希表,go写法有点变态
func containsDuplicate(nums []int) bool {
set := map[int]struct{}{}
for _, v := range nums {
if _, has := set[v]; has {
return true
}
set[v] = struct{}{}
}
return false
}
53 最大子序和
有点不会写,想的有点复杂,看了一下解析,牛逼的很
func maxSubArray(nums []int) int {
// 这个真的有点强无敌了
max := nums[0]
for i := 1; i < len(nums); i++ {
// 如果加入原来的,发现还弱,那就不加入
// 如果比原来的强,那就加入
if nums[i]+nums[i-1] > nums[i] {
nums[i] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}
js版本的贪心算法,每次都贪大于0的
var maxSubArray = function (nums) {
let count = 0;
let res = -Infinity;
for (let i of nums) {
count += i;
if (count > res) {
res = count;
}
if (count <= 0) count = 0;
}
return res;
};
动态规划
var maxSubArray = function (nums) {
const n = nums.length;
const dp = new Array(n).fill(0);
let res = nums[0];
dp[0] = nums[0];
for (let i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > res) res = dp[i];
}
return res;
};
46 全排列
刷题时间:2021-10-28
全排列,用到dfs,需要背一下,脑子不好使。
这个for循环的,有点金字塔的味道。
class Solution {
public:
void backtrack(vector<vector<int>>& res, int start, vector<int>& nums) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); i++) {
swap(nums[start], nums[i]);
backtrack(res, start + 1, nums);
swap(nums[start], nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
backtrack(res, 0, nums);
return res;
}
};
还有个STL的方法
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans = {nums};
while (next_permutation(nums.begin(), nums.end()))
ans.push_back(nums); return ans;
}
重新回来用js写一遍,还是不免参考了一下官解,速度也只能说一般般吧,这里不额外的空间来保存状态。
var permute = function (nums) {
const res = [];
const len = nums.length;
const backtrace = (nums, index) => {
if (index == len) {
res.push(nums);
return;
}
for (let i = index; i < len; i++) {
[nums[i], nums[index]] = [nums[index], nums[i]];
backtrace(nums.slice(), index + 1);
[nums[i], nums[index]] = [nums[index], nums[i]];
}
};
backtrace(nums.slice(), 0);
return res;
};
但我发现大家都是用O(n)的空间来保存使用过的状态,那么循环也是不一样的,这样子有利于后面全排列2的去重,所以这种方法更适合掌握
// 填数字,如果填过了,那么就跳过,如果没填过,就往里面填写
var permute = function (nums) {
let res = [],
path = [],
used = [];
const dfs = () => {
if (path.length == nums.length) {
res.push(Array.from(path));
return;
}
for (let i = 0; i < nums.length; i++) {
// 填过了
if (used[i]) continue;
// 没填过,填一下
path.push(nums[i]);
used[i] = true;
dfs();
// 填完了记得变回去
path.pop();
used[i] = false;
}
};
dfs();
return res;
};
47 全排列 II
有一种比较赖的做法就是改成set,然后剪枝一部分的内容
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
set<vector<int>> res;
sort(nums.begin(), nums.end());
backtrack(res, 0, nums);
return vector<vector<int>>(res.begin(), res.end());
;
}
void backtrack(set<vector<int>>& res, int start, vector<int>& nums) {
if (start >= nums.size()) res.insert(nums);
for (int i = start; i < nums.size(); i++) {
if (i != start && nums[i] == nums[start]) continue;
swap(nums[start], nums[i]);
backtrack(res, start + 1, nums);
swap(nums[start], nums[i]);
}
}
};
或者通过这种方法
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
backtrack(res, 0, nums);
return res;
;
}
void backtrack(vector<vector<int>>& res, int start, vector<int> nums) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); i++) {
if (i != start && nums[i] == nums[start]) continue;
swap(nums[start], nums[i]);
backtrack(res, start + 1, nums);
}
}
};
在原来的全排列的基础上改进,非常的抽象,我看不懂
当 start = 0, i = 2 时,nums 被还原成了 start = 0, i = 1 的交换前的状态 {1, 2, 2},这个状态已经被处理过了,再去处理一定会产生重复,怎么才知道这被处理过了呢,当前的 i = 2,需要往前去找是否有重复出现,由于数组已经排序过了,如果有重复,那么前面数一定和当前的相同,所以用一个 while 循环,往前找和 nums[i] 相同的数字,找到了就停下,当然如果小于 start 了也要停下,那么如果没有重复数字的话,j 一定是等于 start-1 的,那么如果不等于的话,就直接跳过就可以了,这样就可以去掉所有的重复啦
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
backtrack(res, 0, nums);
return res;
}
void backtrack(vector<vector<int>>& res, int start, vector<int>& nums) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); i++) {
int j = i - 1;
while (j >= start && nums[j] != nums[i]) --j;
if (j != start - 1) continue;
swap(nums[start], nums[i]);
backtrack(res, start + 1, nums);
swap(nums[start], nums[i]);
}
}
};
我又回来了,这次写一个js版本的,看看能不能写出来
事实证明还是写不出来,但是思路理清一点了,使用全排列O(n)来保存使用过没的思想更好写,就在上面多加一条语句,具体的理解思路查看这篇博文
var permuteUnique = function (nums) {
nums.sort((a, b) => a - b);
let res = [],
path = [],
used = [];
const dfs = () => {
if (path.length == nums.length) {
res.push(Array.from(path));
return;
}
for (let i = 0; i < nums.length; i++) {
// 填过了,或者是使用过了,这里注意used[i-1]==false是使用过了因为被复原回了false了,属于同一层的使用
// used[i-1]==true是正在使用,属于递归上的树枝
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
// 没填过,填一下
path.push(nums[i]);
used[i] = true;
dfs();
// 填完了记得变回去
path.pop();
used[i] = false;
}
};
dfs();
return res;
};
231 2 的幂
之前的写法
class Solution {
public:
bool isPowerOfTwo(int n) {
while (n > 0) {
if (n == 1) return true;
if (n % 2 != 0) return false;
n /= 2;
}
return false;
}
};
现在的高级写法,一眼的事情
return n > 0 && (n & (n - 1)) == 0;
或者这种操作
return n > 0 && (n & -n) == n;
或者这种操作
class Solution {
private:
static constexpr int BIG = 1 << 30;
public:
bool isPowerOfTwo(int n) {
return n > 0 && BIG % n == 0;
}
};
869 重新排序得到 2 的幂
暴力法。
由于N给定了范围,在 [1, 1e9] 之间,所以其调换位数能组成的二进制数也是有范围的,为 [2^0, 2^30] 之间,这样的话,一个比较直接的解法就是,现将整数N转为字符串,然后对字符串进行排序。然后遍历所有可能的2的指数,将每个2的指数也转为字符串并排序,这样只要某个排序后的字符串跟之前由N生成的字符串相等的话,则表明整数N是符合题意的,参见代码如下:
class Solution {
public:
bool reorderedPowerOf2(int N) {
string str = to_string(N);
sort(str.begin(), str.end());
for (int i = 0; i < 31; ++i) {
string t = to_string(1 << i);
sort(t.begin(), t.end());
if (t == str) return true;
}
return false;
}
};
官方是利用哈希表和预处理
class Solution {
public:
unordered_set<string> powerOf2Digits;
bool reorderedPowerOf2(int n) {
init();
return powerOf2Digits.count(countDigits(n));
}
void init() {
for (int n = 1; n <= 1e9; n <<= 1) {
powerOf2Digits.insert(countDigits(n));
}
}
string countDigits(int n) {
string cnt(10, 0);
while (n) {
++cnt[n % 10];
n /= 10;
}
return cnt;
}
};
搜索回溯弄不来,草了
283 移动零
单指针,多次移动,O(n)
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
for (int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
}
js版本
var moveZeroes = function (nums) {
let index = 0;
for (let i of nums) {
if (i != 0) {
nums[index++] = i;
}
}
for (let i = index; i<nums.length; i++) {
nums[i] = 0;
}
};
167 两数之和-II-输入有序数组
双指针
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
if (numbers[l] + numbers[r] == target) {
return vector<int>{l + 1, r + 1};
} else if (numbers[l] + numbers[r] < target) {
l++;
} else {
r--;
}
}
return {};
}
};
js版本
var twoSum = function (numbers, target) {
let l = 0,
r = numbers.length - 1;
while (l < r) {
if (numbers[l] + numbers[r] == target) {
return [l + 1, r + 1];
} else if (numbers[l] + numbers[r] < target) {
l++;
} else {
r--;
}
}
return [];
};
1 两数之和
暴力法就不说了,直接哈希表
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++) {
auto it = m.find(target - nums[i]);
if (it != m.end()) {
return {it->second, i};
}
m[nums[i]] = i;
}
return {};
}
};
88 合并两个有序数组
排序我是真没有想到啊。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
还有就是常规合并,需要单独开一个数组
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums(n + m);
int p = 0, p1 = 0, p2 = 0;
while (p1 < m && p2 < n) {
if (nums1[p1] > nums2[p2]) {
nums[p++] = nums2[p2++];
} else {
nums[p++] = nums1[p1++];
}
}
while (p1 < m) {
nums[p++] = nums1[p1++];
}
while (p2 < n) {
nums[p++] = nums2[p2++];
}
for (int i = 0; i < m + n; ++i) {
nums1[i] = nums[i];
}
}
};
逆向双指针解法
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
nums1[p--] = nums2[p2] > nums1[p1] ? nums2[p2--] : nums1[p1--];
}
while (p2 >= 0) {
nums1[p--] = nums2[p2--];
}
}
};





