# Surrounded Regions

## 题目描述

Given a 2D board containing’X’and’O’, capture all regions surrounded by’X’.A region is captured by flipping all’O’s into’X’s in that surrounded region .

For example,

X X X XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX O X X

## 代码实现

void toS(vector<vector<char>> &board, int i, int j,int rows, int cols){ if (i < 0 || j < 0 || i >= rows || j >= cols) return; if (board[i][j] == 'O') { board[i][j] = 'S'; toS(board, i + 1, j, rows, cols); toS(board, i - 1, j, rows, cols); toS(board, i, j - 1, rows, cols); toS(board, i, j + 1, rows, cols); }}void solve(vector<vector<char>> &board) { int rows = board.size();//行数 int cols = board[0].size();//列数 if (rows <= 2 || cols <= 2) return; //第一行 for (int i = 0; i < cols; i++) { if (board[0][i] == 'O') toS(board, 0, i,rows,cols); } //最后一行 for (int i = 0; i < cols; i++) { if (board[rows - 1][i] == 'O') toS(board, rows - 1, i, rows, cols); } //第一列 for (int i = 1; i < rows - 1; i++) { if (board[i][0] == 'O') toS(board, i, 0, rows, cols); } //最后一列 for (int i = 1; i < rows - 1; i++) { if (board[i][cols - 1]=='O') toS(board, i, cols - 1, rows, cols); } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == 'S') board[i][j] = 'O'; } }}

# Valid-Parentheses

## 题目描述

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

输入: "()"输出: true

输入: "()[]{}"输出: true

输入: "(]"输出: false

输入: "([)]"输出: false

输入: "{[]}"输出: true

## 题目解析

1. 如果字符是左侧符号（如{([）那么我们就向堆栈里面push进去；
2. 当字符不是左侧符号的时候，首先要判断堆栈此时是否为空，若为空返回false，因为左侧符号还未匹配完；如果栈不为空，判断此时栈顶元素是否与当前元素相等，若不相等，也返回flase；若相等，pop出来，继续走下去。
3.当所有字符遍历完，这个时候判断栈是否为空，若为空说明都匹配，返回true，否则返回false。

## 代码实现

bool isValid(string s) { int slen = s.size(); if (slen == 0) return true; if (slen < 2) return false; stack<char>cstack; for (int i = 0; i < slen; i++) { if (s[i] == '(') cstack.push(')'); else if (s[i] == '[') cstack.push(']'); else if (s[i] == '{') cstack.push('}'); else if (cstack.empty() || cstack.top() != s[i]) return false; else cstack.pop(); } return cstack.empty();}

# remove-nth-node-from-end-of-list

## 题目描述

Given a linked list, remove the n th node from the end of list and return its head.

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid.Try to do this in one pass.

## 代码实现

ListNode *removeNthFromEnd(ListNode *head, int n) { if (head == NULL) return head; ListNode *dummy = new ListNode(-1); dummy->next = head; head = dummy; ListNode *pslow = head; ListNode *pfast = head; while (n--) { pfast = pfast->next; } while (pfast->next != NULL) { pslow = pslow->next; pfast = pfast->next; } ListNode *delp = pslow->next; pslow->next = pslow->next->next; delete delp; return dummy->next;}