「🦆TSK的博客」

Appearance

On this page

算法 ​

时间复杂度:执行表达式所需要的时间 空间复杂度:执行表达式所需要的内存

常用的算法

排序 ​

冒泡排序 ​

ts
function bubbleSort(arr){
  var len = arr.length;
  for(let i = 0;i<len-1;i++){
    for(let j = 0;j<len-i-1;j++){
      // 元素两两对比,和我后面的元素进行比较
      // 如果我比后面的元素还要大,需要交换位置
      if(arr[j] > arr[j+1]){
        [arr[j+1],arr[j]] = [arr[j],arr[j+1]]
      }
    }
  }
}

快速排序 ​

js
function quickSort(arr){
  if (arr.length <= 1) return arr;
  let left = [],right = [],cur = arr[0];

  for(let i =1;i<arr.length;i++){
    if(arr[i]>cur){
      right.push(arr[i])
    }else {
      left.push(arr[i])
    }
  }
  return quickSort(left).concat(cur,quickSort(right))
}

插入排序 ​

js
function insertedSort(arr) {
	for (let j = 1; j < arr.length; j++) {
		let i = j - 1, curr = arr[j];
		// curr 是 未排序的第一项，i 是拍完序 的最后一项下标
		while (i > 0 && curr < arr[i]) {
			arr[i + 1] = arr[i]
			i--
		}
		arr[i + 1] = curr
	}
}
insertedSort([1, 2, 4, 3]) // [1,2,3,4]

选择排序 ​

找到最小值,然后进行交换

js
function selectedSort(arr) {
      //2. 执行 n - 1 次
      for (let i = 0; i < arr.length; i++) {
     // 1. 选择 最小值，然后把 这个最小值 与头部进行交换，找到的最小值就不再遍歷了
        let minIndex = i;
        for (let j = i; j < arr.length; j++) {
          if (arr[j] < arr[minIndex]) {
            minIndex = j;
          }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
      }
      return arr;
}

字符串 ​

反转字符串 ​

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形 式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额 外空间解决这一问题。输入：["h","e","l","l","o"],输出： ["o","l","l","e","h"]

ts
function reverseString(s: string[]): string[] {
	let length = s.length;
	let left = 0,
		right = length - 1;
	while (left < right) {
    [s[left],s[right]] = [s[right],s[left]]
		left++;
		right--;
	}
  return s
};

反转字符串 II ​

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩 余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样

输入: s = "abcdefg", k = 2 输出: "bacdfeg"

INFO

在遍历字符串的过程中，只要让 i += (2 _ k)，i 每次移动 2 _ k 就可以了，然 后判断是否需要有反转的区间。

所以当需要固定规律一段一段去处理字符串的时候，要想想在在 for 循环的表达式上做 做文章

ts
function reverseStr(s: string, k: number): string {
    let arr = s.split('');
    for(let i=0,len = arr.length;i<len;i+=2*k){
        let l = i-1,r = i+ k > len ? len : i+k;
        while(++l<--r){
            [arr[l],arr[r]] = [arr[r],arr[l]]
        }
    }
    return arr.join('')
};

左旋字符串 ​

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数 实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字 2，该函数将返回左 旋转两位得到的结果"cdefgab"。

  1. 示例 1: 输入: s = "abcdefg", k = 2 输出: "cdefgab"
  2. 示例 2: 输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"

通过局部反转+整体反转 达到左旋转的目的

ts
function reverseWord3(sarr: any,k:number) {
	let arr= sarr.split(''),len = arr.length;

	// k 是 个数, j 需要的是 下标
	reverseWord(0, k-1);
	reverseWord(k, len-1);
	reverseWord(0, len-1);

	function reverseWord(i, j) {
		while (i < j) {
			let temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++
			j--
		}
	}
	return arr.join('');
}

栈 ​

有效的括号 ​

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

ts
function isValid(s: string): boolean {

  type BracketMap = {
    [index: string]: string;
  }

  let helperStack: string[] = [];

  let bracketMap: BracketMap = {
    '(': ')',
    '[': ']',
    '{': '}'
  }

  for (let i of s) {
    if (bracketMap.hasOwnProperty(i)) {
      helperStack.push(bracketMap[i]);
    } else if (i !== helperStack.pop()) {
      return false;
    }
  }
  return helperStack.length === 0;
};

删除字符串中的所有相邻重复项 ​

  1. 输入: "hello",输出:"heo"
  2. 输入: "helol",输出:"helol"
ts
function removeDuplicates(s: string): string {
	const helperStack: string[] = [];
	let i = 0;
  let res = '';

	while (i < s.length) {
		let top = helperStack[helperStack.length - 1];
		if (top === s[i]) {
			helperStack.pop();
		} else {
			helperStack.push(s[i]);
		}

		i++;
	}

	while (helperStack.length > 0) {
		res = helperStack.pop() + res;
	}

	return res;
};

贪心 ​

买卖股票问题 ​

给定一个整数数组，其中第 i 个元素代表了第 i天的股票价格； 非负整数 fee 代表了交易股票的手续费用，求返回获得利润的最大值 输入:arr: [1, 12, 13, 9, 15, 8, 6, 16]； fee: 2
输出: 22

js
/**
 * 贪心算法求解
 * @param {array} list - 股票每天的价格列表
 * @param {number} fee - 手续费
 * */
function buyStock(list, fee) {
  // min为当前的最小值，即买入点
  let min = list[0],
    sum = 0;
  for (let i = 1; i < list.length; i++) {
    // 从1开始，依次判断
    if (list[i] < min) {
      // 寻找数组的最小值
      min = list[i];
    } else {
      // 计算如果当天卖出是否赚钱
      let temp = list[i] - min - fee;
      if (temp > 0) {
        // 赚钱 存数据
        sum += temp;
        // 关键代码：重新计算min，分两种情况，如果后面继续涨，则默认继续持有；若后面跌，则以后面的价格重新买入
        min = list[i] - fee;
      }
    }
  }
  return sum;
}

其他 ​

版本号排序 ​

输入一组版本号，输出从大到小的排序

输入:['2.1.0.1', '0.402.1', '10.2.1', '5.1.2', '1.0.4.5'] 输出 ['10.2.1', '5.1.2', '2.1.0.1', '1.0.4.5', '0.402.1']

js
function versionSort(arr) {
  return arr.sort((a, b) => {
    let i = 0;
    const arr1 = a.split(".");
    const arr2 = b.split(".");
    while (true) {
      // 取出相同位置的数字
      const s1 = arr1[i];
      const s2 = arr2[i];
      i++;
      // 若s1 或 s2 不存在，说明相同的位置已比较完成，接下来比较arr1 与 arr2的长度，长的版本号大
      if (s1 === undefined || s2 === undefined) {
        return arr2.length - arr1.length;
      }
      if (s1 === s2) continue;
      // 比较相同位置的数字大小
      return s2 - s1;
    }
  });
}

Updated at: