LeetCode算法学习总结-简单

旋转图像leetcode48

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度(必须在原地旋转图像)。

解决类似的顺时针或者逆时针旋转的方法:

• 顺时针旋转:首先上下交换,这里是指第一行和最后一行交换，第二行和倒数第二行，依次类推, 然后交换对角线的数字
• 逆时针旋转:首先左右交换,这里是指第一列和最后一列交换，第二列和倒数第二列，依次类推, 然后交换对角线的数字

const rotate = (matrix) => {
  const len = matrix.length;
  let low = 0;
  let high = len - 1;
  while (low < high) {
    for (let i = 0; i < len; i++) {
      const temp = matrix[low][i];
      matrix[low][i] = matrix[high][i];
      matrix[high][i] = temp;
    }
    low++;
    high--;
  }
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
};
const matrix = [
 [1,2,3],
 [4,5,6],
 [7,8,9]
]
rotate(matrix)

最大子序和leetcode53

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

var maxSubArray = function(nums) {
  let max = nums[0]
  let curMax = max
  for (let i = 1; i < nums.length; i++) {
    const totle = curMax + nums[i]
    curMax = Math.max(totle, nums[i])
    max = Math.max(curMax, max)
  }
  return max
    
}

爬楼梯问题leetcode70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

可以分成多个子问题，爬第n阶台阶的方法由前两种之和：爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶；爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶；因此可得 dp[n] = dp[n-1] + dp[n-2]

//动态规划
var climbStairs = function(n) {
  let pre1 = 1  //爬上上层需要的方法
  let pre2 = 2  // 爬上层需要的方法
  if (n ===1) return 1
  if (n === 2) return 2
  for (let i = 3; i <= n; i++) {
    [pre1, pre2] = [pre2, pre1 + pre2]
  }
  return pre2
}

合并两个有序数组leetcode88

方法一：将nums1的长度扩展到m+n;然后将nums1和nums2从后往前遍历；一边遍历一边将最大的值放在nums1最后面的指针；复杂度为O(m+n)

let len = m + n -1 // nums1扩展后的总长度
  let len1 = m - 1
  let len2 = n - 1
  while(len2 >= 0) {
    if (len1 < 0) {
      nums1[len--] = nums2[len2--]
      continue;
    }
    nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--]
  }
  return nums1

方法二：采用双指针；从前往后遍历

打家劫舍leetcode198

一个专业的小偷，沿街打家劫舍；每个房间都方有不同数量的现金；唯一影响偷窃的因素就是不能偷相邻房间的钱；计算能够偷盗的最大金额

此题和上面的爬楼梯类似，到达第n个房间能获得的最大金额和它n-1个房间和n-2个房间的有关;在当前房间能获得对最大金额就是dp[n-2] + dp[n]和dp[n-1]中的那个最大值

// 动态规划
var rob = function(nums) {
  let pre1 = 0  // 上上个值
  let pre2 = 0 // 上个值
  let max = 0 //当前最大
  for (let i = 0; i < nums.length; i++) {
    max = Math.max(pre1+nums[i], pre2);
    [pre1, pre2] = [pre2, max]
  }
  return max
}

只出现一次的数字leetcode136

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

var singleNumber = function(nums) {
    let result = 0
    for (let i = 0; i<nums.length; i++){
      result = result^nums[i]
    }
    return result
}
console.log(singleNumber([4,1,2,1,2]))

三数只和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

• 对数组进行排序
• 从0到length-2(防止越界)遍历数组
• 采用双指针的方式(i,left= i+1, right=length-1)
  • 如果当前数等于前一个数,则跳过(去重)
  • 当三个值的和大于0.则right--
  • 当三个值的和小于0.则left++
  • 如果正好相等则加入数组

相交链表

// 方案一:双指针
// 指针`a`和`b`分别指向两个链表,`a`从头遍历到位,然后切换到b链表,`b`从头遍历到尾,然后切换到a,
var getIntersectionNode = function(headA, headB) {
  // 边界判断
  if (headA == null || headB == null) return null;
  
  let hA = headA, hB = headB;
  
  //指针 hA 和 指针 hB 不断向后遍历，直到找到相交点
  while (hA != hB) {
      // 指针 hA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上 
      hA = hA == null ? headB : hA.next;
      // 指针 hB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上 
      hB = hB == null ? headA : hB.next;
  }
  return hA;
};
// 方案二:哈希表
// 先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点

小红包免费领

小礼物走一走