【一天一大 lee】反转字符串 (难度:简单) - Day20201008

前端小书童

发布于 2020-10-26 11:18:23

2780

发布于 2020-10-26 11:18:23

文章被收录于专栏：前端小书童

题目:

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例：

示例1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

抛砖引玉

思路

对数组翻转：javascript实现的翻转方法reverse

循环数组长度的一半，从前到后替换指定元素（借助解构赋值替换）

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
 let len = s.length
 for (let i = 0; i < parseInt(len / 2, 10); i++) {
  [s[i], s[len - i - 1]] = [s[len - i - 1], s[i]]
 }
};

【一天一大 lee】环形链表 (难度:简单) - Day20201009

题目:

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例：

示例1：

示例1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

示例2

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：

示例3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示:

链表中节点的数目范围是 [0,

10^5

]

-10^5

<= Node.val <=

10^5

pos 为 -1 或者链表中的一个有效索引。

抛砖引玉

思路

哈希表

遍历链表一个节点就将遍历的节点作为哈希存放到（map、set、object）中
后续又遇到则说明存在环，否则不存在

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  let map = new Map();
  while(head!== null){
    if(map.has(head)) return true
    map.set(head,true)
    head = head.next;
  }
  return false 
};

快慢指针

声明两个指针，两个指针一快一慢（每次next是存在间隔）
如果链表内有环，则两个指针一定会在环内相遇（快指针超过慢指针x圈）
如果最终两指针均遇到终点则说明无环

 var hasCycle = function (head) {
  if (head == null || head.next == null) return false
  let slow = head,
   fast = head.next;
  while (slow != fast) {
   if (fast == null || fast.next == null) return false
   slow = slow.next;
   fast = fast.next.next;
  }
  return true;
 };

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自前端小书童微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度