二分查找

【题目】
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

【解题思路】
图片.png

  • 定义查找的范围 [left,right]，初始查找范围是整个数组。
  • 每次取查找范围的中点 mid，比较 nums[mid] 和 target的大小，如果相等则 mid即为要寻找的下标。
  • 如果不相等则根据 nums[mid]和 target的大小关系将查找范围缩小一半

【代码】

  1. var search = function(nums, target) {
  2.     // 在区间[left,right]中查找元素，左闭右闭
  3.     let left = 0;
  4.     let right = nums.length - 1;
  5.     while (left <= right) {
  6.       // 计算中间点
  7.       let mid = parseInt(left + (right-left)/2);
  8.       if (target == nums[mid]) {
  9.         return mid;
  10.         // 如果target < nums[mid]，表示目标值可能在左半边
  11.       } else if (target < nums[mid]){
  12.         right = mid - 1;
  13.         // 如果target > nums[mid]，表示目标值可能在右半边
  14.       } else if (target > nums[mid]){
  15.         left = mid + 1;
  16.       }
  17.     }
  18.     // 未找到返回-1
  19.     return -1;
  20. };

第一个错误的版本

【题目】
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。

【解题思路】
当一个版本为正确版本，则该版本之前的所有版本均为正确版本；
当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。
【代码】

  1. var solution = function(isBadVersion) {
  2.   return function(n) {
  3.     let left = 1,right = n;
  4.     while (left < right) {
  5.       let mid = Math.floor((right - left)/2 + left);
  6.       if (isBadVersion(mid)) {
  7.         right = mid;
  8.       } else {
  9.         left = mid + 1;
  10.       }
  11.     }
  12.     return left;
  13.   };
  14. };

搜索插入位置

【题目】
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2

示例 2: 输入: nums = [1,3,5,6], target = 2 输出: 1

【思路】

  • 整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid
  • 每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left 右移，nums[mid] > target 则 right 左移
  • 查找结束如果没有相等值则返回 left，该值为插入位置

【代码】

  1. var searchInsert = function(nums, target) {
  2.     let n = nums.length;
  3.     let left = 0, right = n-1 , ans = n;
  4.     while (left <= right) {
  5.         let mid = Math.floor((right - left)/2) + left;
  6.         if (target <= nums[mid]) {
  7.             ans = mid;
  8.             right = mid - 1;
  9.         } else {
  10.             left = mid + 1;
  11.         }
  12.     }
  13.     return ans;
  14. }

有序数组的平方

【题目】
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100]

解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]

【思路】

  • 最简单的方法就是将数组 nums\textit{nums}nums 中的数平方后直接排序。

【代码】

  1. var sortedSquares = function(nums) {
  2.     for(let i=0;i<nums.length;i++){
  3.         nums[i] = nums[i]*nums[i]
  4.     }
  5.     return nums.sort((a,b)=>a-b)
  6. };

轮转数组

【题目】
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2: 输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

【思路】

  • 用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i的元素放至新数组下标为(i+k) mod n 的位置，最后将新数组拷贝至原数组即可。

【代码】

  1. var rotate = function(nums, k) {
  2.      const n = nums.length;
  3.     const newArr = new Array(n);//创建一个与nums长度相同的数组
  4.     for (let i = 0; i < n; ++i) {
  5.         newArr[(i + k) % n] = nums[i];
  6.         //3 % 7 =3  newArr[3]=nums[0]=1
  7.         //4 % 7 = 4  newArr[4]=nums[1]=2
  8.         //...
  9.     }
  10.     for (let i = 0; i < n; ++i) {
  11.         nums[i] = newArr[i];
  12.     }
  13. };

移动零

【题目】
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

【思路】

  • 定义两个指针 left right, left指针始终要指向第一个0所在的位置
  • right则负责去去到数组中的每一个数判断其是否为0，若为0则right++
  • 反正则令nums[left] 和 nums[right] 交换位置，并使 left++(left指针始终要指向第一个0所在的位置),最后再right++，直至right指针找到最后一个数组元素为止

【代码】

  1. var moveZeroes = function(nums) {
  2.   let left = 0
  3.   let right = 0
  4.   let len = nums.length
  5.   while (right < len) {
  6.     if (nums[right] !== 0) {
  7.           //交换位置
  8.         let temp = nums[left];
  9.         nums[left] = nums[right];
  10.         nums[right] = temp;
  11.         left++
  12.     }
  13.     right++
  14.   }
  15.   return nums
  16. };

两数之和 II - 输入有序数组

【题目】
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1： 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2： 输入：numbers = [2,3,4], target = 6 输出：[1,3]

示例 3： 输入：numbers = [-1,0], target = -1 输出：[1,2]

【思路】

  • 固定第一个数，利用数组的有序性质，通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

【代码】

  1. var twoSum = function(numbers, target) {
  2.     let left, right = numbers.length - 1, mid;
  3.     // 固定第一个数
  4.     for (let i = 0; i <= numbers.length; i++) {
  5.         left = i + 1;
  6.         // 二 数
  7.         while (left <= right) {
  8.             mid = left + ((right - left)%2);
  9.             if (numbers[i] + numbers[mid] === target) {
  10.                 return [i + 1, mid + 1];
  11.             } else if (numbers[i] + numbers[mid] > target) {
  12.                 right = mid - 1;
  13.             } else {
  14.                 left = mid + 1;
  15.             }
  16.         }
  17.     }
  18. };

反转字符串

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

示例 1： 输入：s = [“h”,”e”,”l”,”l”,”o”] 输出：[“o”,”l”,”l”,”e”,”h”]

示例 2： 输入：s = [“H”,”a”,”n”,”n”,”a”,”h”] 输出：[“h”,”a”,”n”,”n”,”a”,”H”]

【思路】
图片.png

  • 将 left 指向字符数组首元素，right 指向字符数组尾元素。

  • 当 left < right：

    • 交换 s[left] 和 s[right]；
    • left 指针右移一位，即 left = left + 1；
    • right 指针左移一位，即 right = right - 1。

  • 当 left >= right，反转结束，返回字符数组即可。

【代码】

  1. var reverseString = function(s) {
  2.     const n = s.length;
  3.     for (let left = 0, right = n - 1; left < right; ++left, --right) {
  4.         [s[left], s[right]] = [s[right], s[left]];
  5.         /*等同于：
  6.             let temp = s[left];
  7.             s[left] = s[right];
  8.             s[right] = temp;
  9.         */
  10.     }
  11. };

反转字符串中的单词 III

【题目】
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例： 输入：“Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”

提示：

  • 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

【思路】

  • 创建一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。
  • 随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。
  • 如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。

【代码】

  1. var reverseWords = function(s) {
  2.     const ret = [];
  3.     const length = s.length;
  4.     let i = 0;
  5.     while (i < length) {
  6.         let start = i;
  7.         while (i < length && s.charAt(i) != ' ') {
  8.             i++;
  9.         }
  10.         for (let p = start; p < i; p++) {
  11.             ret.push(s.charAt(start + i - 1 - p));
  12.         }
  13.         while (i < length && s.charAt(i) == ' ') {
  14.             i++;
  15.             ret.push(' ');
  16.         }
  17.     }
  18.     return ret.join('');
  19. };

链表的中间结点

【题目】
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

【思路】
我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。
【代码】

  1. var middleNode = function(head) {
  2.   n = 0;
  3.   cur = head;
  4.   //获取节点个数 n
  5.   while (cur != null) {//如果不是最后一个节点，则进行循环
  6.     ++n;
  7.     cur = cur.next;
  8.   }
  9.   k = 0;
  10.   cur = head;
  11.   //Math.trunc将数字的小数部分去掉，只保留整数部分。
  12.   while (k < Math.trunc(n / 2)) {
  13.     ++k;
  14.     cur = cur.next;
  15.   }
  16.   return cur;
  17. };

删除链表的倒数第 N 个结点

【题目】
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
图片.png
【思路】

  • 将链表节点依次存入数组stack栈.
  • 再将栈的后n个元素弹出，暴露出链表倒数第n个数的前一个节点
  • 将其与倒数第n个数的后一个节点相连

【代码】

  1. var removeNthFromEnd = function(head, n) {
  2.     const dummy = new ListNode(0, head)
  3.     const stack = new Array()
  4.     let pushList = dummy
  5.     while (pushList != null) {
  6.         stack.push(pushList)
  7.         pushList = pushList.next
  8.     }
  9.     for (let i = 0; i < n; i++) {
  10.         stack.pop()
  11.     }
  12.     let peek = stack[stack.length - 1]
  13.     peek.next = peek.next.next
  14.     return dummy.next
  15. };

【题目】

【思路】
可以使用「滑动窗口」来解决这个问题了：

  • 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的rk；

  • 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

  • 在枚举结束后，我们找到的最长的子串的长度即为答案。

【代码】

  1. var lengthOfLongestSubstring = function(s) {
  2.     // 哈希集合，记录每个字符是否出现过
  3.     const hashValue = new Set();
  4.     const n = s.length;
  5.     // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  6.     let rk = -1, ans = 0;
  7.     for (let i = 0; i < n; ++i) {
  8.         if (i != 0) {
  9.             // 左指针向右移动一格，移除一个字符
  10.             hashValue.delete(s.charAt(i - 1));
  11.         }
  12.         while (rk + 1 < n && !hashValue.has(s.charAt(rk + 1))) {
  13.             // 不断地移动右指针
  14.             hashValue.add(s.charAt(rk + 1));
  15.             ++rk;
  16.         }
  17.         // 第 i 到 rk 个字符是一个极长的无重复字符子串
  18.         ans = Math.max(ans, rk - i + 1);
  19.     }
  20.     return ans;
  21. };

合并二叉树

【题目】
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

输入: Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7

【思路】
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

  • 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；

  • 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；

  • 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

【代码】

  1. var mergeTrees = function(root1, root2) {
  2.     if(!root1) return root2
  3.     if(!root2) return root1
  4.     root1.val = root1.val + root2.val
  5.     root1.left = mergeTrees(root1.left, root2.left)
  6.     root1.right = mergeTrees(root1.right, root2.right)
  7.     return root1
  8. };

n的幂次方

【题目】
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1： 输入：n = 1 输出：true 解释：20 = 1

示例 2： 输入：n = 16 输出：true 解释：24 = 16

进阶：你能够不使用循环/递归解决此问题吗？
【思路】
n为0时，20 = 1为true;n为1时为false;
当n%2==0时，那n一定是2的倍数
普通写法可以使用循环，一直除2，最终结果为1那就是true

【代码】

  1. var isPowerOfTwo = function(n) {
  2.     if(n==0) return false
  3.     if (n==1) return true
  4.     while(n%2==0){
  5.         n=n/2
  6.     }
  7.     return n==1
  8. };

只出现一次的数字

【题目】
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

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

【思路】
异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
如果a、b两个值不相同，则异或结果为1；如果a、b两个值相同，异或结果为0。
异或同时也满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
一个数和0做异或，结果是他本身

也就是说将数组里的数全部做异或，因为相同所以为0,那么就剩最后0与最后一个数做运算，结果就等于只出现一次的元素
2⊕3⊕5⊕7⊕2⊕3⊕5 就相当于 0⊕7=7
图片.png
【代码】

  1. var singleNumber = function(nums) {
  2.     let ans = 0;
  3.   //遍历nums
  4.     for(const num of nums) {
  5.       //0异或第一个数，就等于这第一个数,获得的结果与下一个数异或
  6.         ans =ans ^ num;
  7.     }
  8.     return ans;
  9. };