Hexo
0%

Array

Posted on

删除一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[1,2,3,4] 2 ,返回length
function deleteNum(arr,val){
  let k = 0
  for (let i =0;i<arr.length;i++){
    if(arr[i]!=val){
      arr[k++] = arr[i]
    }
  }
  return k
}

[1,2,3,4]  2



二分法查找 注意区间[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: (nums = [-1, 0, 3, 5, 9, 12]), (target = 9);
输出: 4;

function search(nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let mid = (l + r) >> 1; // 00101  -> 0010
    let isShort = nums[mid] < target; // target 右区间
    l = isShort ? mid + 1 : l; // 在右区间 【middle+1,right】
    r = isShort ? r : mid - 1; // 在左区间 【left,middle-1】
  }
  return -1;
}

有序数组平方排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[-4, -2, 0, 1, 2];
const sortedSquares = function (nums) {
  let res = [];
  for (let i = 0, j = nums.length - 1; i <= j; ) {
    const left = Math.abs(nums[i]);
    const right = Math.abs(nums[j]);
    if (right > left) {
      res.unshift(right * right);
      j--;
    } else {
      res.unshift(left * left);
      i++;
    }
  }
  return res;
};

最小连续数组满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let minSubArrayLen = function (target, nums) {
  const len = nums.length;
  let l = (r = sum = 0),
    res = len + 1; // 子数组最大不会超过自身
  while (r < len) {
    sum += nums[r++];
    // 窗口滑动
    while (sum >= target) {
      // r始终为开区间 [l, r)
      res = res < r - l ? res : r - l;
      sum -= nums[l++];
    }
  }
  return res > len ? 0 : res;
};
let result = minSubArrayLen(7, [2, 3, 1, 2, 4, 3]);

矩阵

1

字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let str = "My name is yhq";
const reverseStr = (s) => {
  let left = 0;
  let right = s.length - 1;
  let quene = [];
  let word = "";
  while (s.charAt(left) === " ") left++;
  while (s.charAt(right) === " ") right--;
  while (left <= right) {
    let char = s.charAt(left);
    if (char === " " && word) {
      quene.unshift(word);
      word = "";
    } else if (char !== " ") {
      word += char;
    }
    left++;
  }
  quene.unshift(word);
  return quene.join(" ");
};
reverseStr(str);

括号

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
29
30
31
32
33
34
35
class Stack {
  constructor() {
    this.items = [];
  }
  push(value) {
    this.items.push(value);
  }
  pop(value) {
    if (!this.isEmpty()) {
      this.items.pop(value);
    }
  }
  isEmpty() {
    return this.items?.length === 0;
  }
  size() {
    return this.items.length;
  }
}

const isPairing = (str) => {
  const stack = new Stack();
  for (let i of str) {
    if (i === "(") {
      stack.push(i);
    } else if (i === ")") {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.size() === 0;
};

s = “abaccdeff” 字符出现一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const recordFirstUnit = (str) => {
  if (!str) return "";
  const mapData = new Map();
  for (let i of str) {
    if (mapData.has(i)) {
      mapData.set(i, mapData.get(i) + 1);
    } else {
      mapData.set(i, 1);
    }
  }
  for (let j of mapData.keys()) {
    if (mapData.get(j) === 1) {
      return j;
    }
  }

  return " ";
};