算法小练#1

Posted by Dany Yang on April 25, 2019

开始记录每周做过的算法题,这是第一周,新的开始

1021. 删除最外层的括号

题目要求如下:

有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,”“,”()”,”(())()” 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + … + P_k,其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1:
输入:"(()())(())"
输出:"()()()"
解释:
输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())",
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2:
输入:"(()())(())(()(()))"
输出:"()()()()(())"
解释:
输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))",
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3:
输入:"()()"
输出:""
解释:
输入字符串为 "()()",原语化分解得到 "()" + "()",
删除每个部分中的最外层括号后得到 "" + "" = ""。

看完题目大概知道,这是在考察栈的问题,每一个括号都是成对出现的,需要将最外层的括号删除,保留里面的括号。

栈的特点就是先进后出。主要思路是关注右括号,如果右括号和左括号相等,说明是一个闭合的串,需要进行分解。如果未闭合就进行搜集起来

JavaScript解决办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var removeOuterParenthese = function (S) {
  let open = 0
  let combine = ''
  for (let c of S) {
    if (c == ')') {
      open --
    }
    if (open > 0) {
      combine += c
    }

    if (c === '(') {
      open ++
    }
  }
  return combine
}

console.log(removeOuterParenthese('(()())(())(()(()))'))

237. 删除链表中的节点

题目要求如下:

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9],它可以表示为:

1
4 --> 5 -->1 --> 9
1
2
3
4
5
6
7
8
9
10
示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
1
2
3
4
5
6
说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

解题思路

最开始看这个也一头雾水,怎么就只给一个节点,链表呢?其实也不必纠结这个,题目中明确说明了,只给你要删除的节点,所以链表的长度,链表的上一个节点都访问不到。

也就是说常规的链表删除节点是没办法用的(使上一个链表的节点的next,指向要删除节点的next),在不知道上一个节点的情况下,按照常规的办法不行,就换另一种解决思路。

这题精妙的地方就是它的解决思路,使用下一个节点的值,赋值给当前节点,然后再将它的next指向下个节点的next–>next,这样要删除的当前节点就消失了。是不是很精妙

JavaScript解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */

var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
}

链接:

Leetcode: 1021. 删除最外层的括号

Leetcode: 237. 删除链表中的节点