算法小练#1 - Dany Yang
开始记录每周做过的算法题，这是第一周，新的开始
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大专栏 算法小练#1 - Dany Yangspan class="p">(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
}
链接：
最新文章
- Go - 数组 和 切片（array、slice）
- iOS网络通讯——监测网络状态：Reachability(可达性)
- NSarray 赋值 拷贝 等问题记录
- extensible_index
- Xilinx------BUFG,IBUFG,BUFGP,IBUFGDS等含义以及使用
- TCP 三次握手原理，你真的理解吗？
- A1100. Mars Numbers
- Excel 整个列数字转换成文本
- python之图像识别
- ElasticSearch 学习记录之Text keyword 两种基本类型区别
- maven工程插件配置
- 22.OGNL与ValueStack(VS)-默认类Math的访问
- 基于FPGA的4x4矩阵键盘驱动调试
- android 布局的两个属性 dither 和 tileMode
- 12个值得关注的顶级可视化JS库 涉及图表、动画、时间处理，表格操作
- Animate a custom Dialog,自定义Dialog动画
- Ad Exchange基本接口和功能
- Azure 中 Linux 虚拟机的大小
- Yiic执行php脚本
- MVC controller序列化下拉框给view