灯的个人博客

forever young,forever weeping.

0%

发表于 更新于 分类于

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。

  • 我们可以不考虑输出结果的顺序。
    进阶：

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？

  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？

  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

题解

直觉版

1
2
3
4
5
6
7
8
9
10
11
12
13
function intersect(nums1: number[], nums2: number[]): number[] {
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  return nums1.filter((item) => {
    let index = nums2.findIndex((cItem) => item === cItem);
    if (index === -1) {
      return false;
    }
    nums2.splice(index, 1);
    return true;
  });
}

双指针版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function intersect(nums1: number[], nums2: number[]): number[] {
  nums1 = nums1.sort((a, b) => a - b);
  nums2 = nums2.sort((a, b) => a - b);
  let rightIndex = 0;
  let leftIndex = 0;
  let result = [];
  while (leftIndex < nums1.length && rightIndex < nums2.length) {
    if (nums1[leftIndex] === nums2[rightIndex]) {
      result.push(nums1[leftIndex]);
      leftIndex++;
      rightIndex++;
      continue;
    } else if (nums2[rightIndex] > nums1[leftIndex]) {
      leftIndex++;
      continue;
    } else {
      rightIndex++;
    }
  }
  return result;
}

参考

发表于 更新于 分类于

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4

题解

常规set

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
function singleNumber(nums: number[]): number {
  let numSet: Set<number> = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (numSet.has(nums[i])) {
      numSet.delete(nums[i]);
    } else {
      numSet.add(nums[i]);
    }
  }
  return [...numSet][0];
}
``` 

位运算
- 1 ^ 1 = 0
- 0 ^ 1 = 1;
- 1 ^ 1 ^ 2 = 2;
- 2 ^ 2 ^ 1 = 1
- 相同的数字或运算等于0,0与人气其他数字或运算等于此数字
- 2 ^ 2 ^ 3 ^ 3 ^ 1 =  1
```typescript
function singleNumber(nums: number[]): number {
  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i];
  }
  return result;
}

参考链接

发表于 更新于 分类于

题目

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

题解

1
2
3
4
5
6
7
8
9
10
function containsDuplicate(nums: number[]): boolean {
  let numSet = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (numSet.has(nums[i])) {
      return true;
    }
    numSet.add(nums[i]);
  }
  return false;
}

参考链接

发表于 更新于 分类于

题目

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
4
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

1
2
3
4
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

1
2
3
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1
2
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 贪心算法
 * @param prices 
 * @returns 
 */
function maxProfit(prices: number[]): number {
    let i = 0;
    prices.reduce((current, next) => {
      let val = next - current;
      i += val > 0 ? val : 0;
      return next;
    });
    return i;
  }

参考

发表于 更新于 分类于

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
9

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1
2
3
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

个人题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 个人题解
 * 双层遍历的解法，时间复杂度O(n2)
 * @param nums
 * @returns
 */
function removeDuplicates(nums: number[]): number {
  for (let i = 0; i < nums.length; ) {
    let index = nums.findIndex((cItem, cIndex) => i !== cIndex && nums[i] === cItem);
    if (index !== -1) {
      nums.splice(i, 1);
      continue;
    }
    i++;
  }
  return nums.length;
}

双指针解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/**

 * @param nums
 * @returns
 */
function removeDuplicates(nums: number[]): number {
  let left = 0;
  for (let right = 1; right < nums.length; right++) {
    if (nums[left] !== nums[right]) {
      nums[++left] = nums[right];
    }
  }
  return left + 1;
}
  • 看了题解，双指针办法
  • 因为数组是有序的，右边大于等于左边
  • 初始化左指针等于0，右指针等于1，
  • 循环右指针
  • 当右指针不等于左指针的时候，说明碰到了不一样的数值，将右指针赋值给左指针，左指向前移动一位，右指针继续循环
  • 不重复的值为左指针+1

参考链接

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
use ::std::io;
fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).expect("输入错误");
    let n: i64 = n.trim().parse().expect("不是数字");
    let mut index = 0;
    let mut first = 0;
    let mut second = 1;
    while index <= n {
        if index == 0 || index == 1 {
            println!("count {}", index);
        } else {
            let count: i64 = first + second;
            first = second;
            second = count;
            println!("count {}", count);
        }
        index += 1;
    }
}

发表于 更新于 分类于 
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
use rand::Rng;
use std::cmp::Ordering;
use std::io;
fn main() {
    println!("猜一个数字！");
    println!("输出你猜的数字");
    let secret_number = rand::thread_rng().gen_range(1, 101);
    loop {
        let mut guess = String::new();
        io::stdin().read_line(&mut guess).expect("读取错误");
        let guess: u32 = match guess.trim().parse() {
            Ok(num) => num,
            Err(_) => {
                println!("请输入数字");
                continue;
            }
        };
        match guess.cmp(&secret_number) {
            Ordering::Less => println!("小了"),
            Ordering::Greater => println!("大了"),
            Ordering::Equal => {
                println!("对了");
                break;
            }
        }
    }
}

发表于 更新于 分类于

看到十年前自己写的一些东西，光阴似箭啊。。
一转眼十几年过去了。
好像自己从来没做出过什么emm 不知道该怎么形容。。
没有什么特别出彩的东西？
可能是吧。

感觉浪费了很多时间，但是又没有毅力去改变。。
可怕的就是这种情况吧。

也许可以定一个目标，做点什么东西，在这个世界留下点什么东西。
emmm，如果可以，我想这个东西会是好的。

思绪有点乱。

也有可能。。
emm 大概率。。
碌碌无为一生。

上班，结婚，生子。

快三十了呀。

2008年。。

你觉得很重要的事情。。
可能在大部分人看来。。em 也许都记不住。
人总是渺小的

要做点什么。

随便谢谢，记录一下。

多年以后在看，也许有不一样的感觉。

发表于 更新于 分类于

JS-MAP问题

发现问题

  • 定义了一个MAP,代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

    const QuestuibOptionHandlerMap = new Map([
      [0, getCommonOptions], //单选题
      [1, getCommonOptions], //多选题
      [2, () => {}], //填空题
      [3, getCommonOptions], //下拉题
      [4, () => {}], //日期
      [5, () => {}], //量表题
      [6, () => {}], //AHP 题组
      [7, () => {}], //图片上传题
      [8, () => {}], //文件上传题
      [9, () => {}], //城市
      [1, () => {}], //车型
    ]);

  • 输出MAP

    1
    console.log(QuestuibOptionHandlerMap);

    20210115173433
    然后输出的……..

解决问题.

以后多动动脑子,求你了.
卧槽啊啊啊啊啊啊!!!!!!
第二个,跟最后一个竟然重复了!!!!!!!!!
改行吧