设计循环列表
type MyCircularQueue struct {
Data []int
Head int
Tail int
Size int
}
/** Initialize your data structure here. Set the size of the queue to be k. */
func Constructor(k int) MyCircularQueue {
data := make([]int , k)
return MyCircularQueue{data , -1 , -1 , k}
/**
queue := new(MyCircularQueue)
queue.Data = make([]int , k)
queue.Head = -1
queue.Tail = -1
queue.Size = k
return queue
*/
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
//if the queue is empty , we need to set head to 0
if this.IsEmpty() {
this.Head = 0
}
this.Tail = (this.Tail + 1) % this.Size
this.Data[this.Tail] = value
return true
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
//this means there is only one value in the queue
if this.Head == this.Tail {
this.Head = -1
this.Tail = -1
return true
}
this.Head = (this.Head + 1) %this.Size
return true
}
/** Get the front item from the queue. */
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.Data[this.Head % this.Size]
}
/** Get the last item from the queue. */
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
return this.Data[this.Tail % this.Size]
}
/** Checks whether the circular queue is empty or not. */
func (this *MyCircularQueue) IsEmpty() bool {
return this.Head == -1
}
/** Checks whether the circular queue is full or not. */
func (this *MyCircularQueue) IsFull() bool {
if (this.Tail + 1) % this.Size == this.Head {
return true
}
return false
//return (this.Tial + 1) % this.Size == this.Head
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.EnQueue(value);
* param_2 := obj.DeQueue();
* param_3 := obj.Front();
* param_4 := obj.Rear();
* param_5 := obj.IsEmpty();
* param_6 := obj.IsFull();
*/
岛屿的数量
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
ret := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == '1' {
helper(grid, i, j)
ret++
}
}
}
return ret
}
func helper(grid [][]byte, i, j int) {
if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
return
}
if grid[i][j] == '1' {
grid[i][j] = '0'
helper(grid, i-1, j)
helper(grid, i, j-1)
helper(grid, i+1, j)
helper(grid, i, j+1)
}
}
最小栈
type MinStack struct {
cur int
min []int
data []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
min, data := []int{}, []int{}
return MinStack{
cur: -1,
min: min,
data: data,
}
}
func (this *MinStack) Push(x int) {
this.cur++
this.data = append(this.data, x)
if this.cur > 0 {
if x > this.min[this.cur-1] {
this.min = append(this.min, this.min[this.cur-1])
} else {
this.min = append(this.min, x)
}
} else {
this.min = append(this.min, x)
}
fmt.Println(this.min)
}
func (this *MinStack) Pop() {
this.cur--
}
func (this *MinStack) Top() int {
return this.data[this.cur]
}
func (this *MinStack) GetMin() int {
return this.min[this.cur]
}
有效的括号
func isValid(s string) bool {
str := []byte(s)
stack := []byte{}
for _, v := range str {
if '(' == v || '{' == v || '[' == v {
stack = append(stack, v)
}
if len(stack) == 0 {
return false
}
if ')' == v {
if stack[len(stack)-1] != '(' {
return false
} else {
stack = stack[:len(stack)-1]
}
}
if '}' == v {
if stack[len(stack)-1] != '{' {
return false
} else {
stack = stack[:len(stack)-1]
}
}
if ']' == v {
if stack[len(stack)-1] != '[' {
return false
} else {
stack = stack[:len(stack)-1]
}
}
}
return len(stack) == 0
}
每日温度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
stack<int> st;
for (int i = 0; i < temperatures.size(); ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
auto t = st.top(); st.pop();
res[t] = i - t;
}
st.push(i);
}
return res;
}
};
逆波兰表达式求值
class Solution {
public:
int stack[10005];
int pos=0;
int evalRPN(vector<string>& tokens) {
int l = tokens.size();
for(int i=0;i<l;i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{
int value1 = stack[--pos];
int value2 = stack[--pos];
if(tokens[i]=="+")
{
stack[pos++]=value1+value2;
}
else if(tokens[i]=="-")
{
stack[pos++]=value2-value1;
}
else if(tokens[i]=="*")
{
stack[pos++]=value2*value1;
}
else if(tokens[i]=="/")
{
stack[pos++]=value2/value1;
}
}
else
{
int value = atoi(tokens[i].c_str());
stack[pos++]=value;
}
}
return stack[0];
}
};
克隆图
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node) return NULL;
unordered_map<Node*, Node*> m;
queue<Node*> q{{node}};
Node *clone = new Node(node->val);
m[node] = clone;
while (!q.empty()) {
Node *t = q.front(); q.pop();
for (Node *neighbor : t->neighbors) {
if (!m.count(neighbor)) {
m[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
m[t]->neighbors.push_back(m[neighbor]);
}
}
return clone;
}
};
目标和
func findTargetSumWays(nums []int, S int) int {
S = myabs(S)
sum := 0
for _, v := range nums {
sum += v
}
if sum < S || (S+sum)%2 != 0 {
return 0
}
target := (S + sum) / 2
dp := make([]int, target+1)
dp[0] = 1
for _, num := range nums {
for i := target; i >= num; i-- {
dp[i] += dp[i-num]
}
}
return dp[target]
}
func myabs(x int) int {
if x >= 0 {
return x
}
return -x
}
用栈实现队列
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) {
_new.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
shiftStack();
int val = _old.top(); _old.pop();
return val;
}
/** Get the front element. */
int peek() {
shiftStack();
return _old.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return _old.empty() && _new.empty();
}
void shiftStack() {
if (!_old.empty()) return;
while (!_new.empty()) {
_old.push(_new.top());
_new.pop();
}
}
private:
stack<int> _old, _new;
};
用栈实现队列
class MyStack {
public:
MyStack() {}
void push(int x) {
q2.push(x);
while (q2.size() > 1) {
q1.push(q2.front()); q2.pop();
}
}
int pop() {
int x = top(); q2.pop();
return x;
}
int top() {
if (q2.empty()) {
for (int i = 0; i < (int)q1.size() - 1; ++i) {
q1.push(q1.front()); q1.pop();
}
q2.push(q1.front()); q1.pop();
}
return q2.front();
}
bool empty() {
return q1.empty() && q2.empty();
}
private:
queue<int> q1, q2;
};
字符串解码
class Solution {
public:
string decodeString(string s) {
int i = 0;
return decode(s, i);
}
string decode(string s, int& i) {
string res = "";
int n = s.size();
while (i < n && s[i] != ']') {
if (s[i] < '0' || s[i] > '9') {
res += s[i++];
} else {
int cnt = 0;
while (s[i] >= '0' && s[i] <= '9') {
cnt = cnt * 10 + s[i++] - '0';
}
++i;
string t = decode(s, i);
++i;
while (cnt-- > 0) {
res += t;
}
}
}
return res;
}
};
图像渲染
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
color := image[sr][sc]
if color != newColor {
dfs(image, sr, sc, color, newColor)
}
return image
}
func dfs(image [][]int, r, c, color, newColor int) {
if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) || image[r][c] != color {
return
}
image[r][c] = newColor
dfs(image, r-1, c, color, newColor)
dfs(image, r, c-1, color, newColor)
dfs(image, r+1, c, color, newColor)
dfs(image, r, c+1, color, newColor)
}
01矩阵
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) q.push({i, j});
else matrix[i][j] = INT_MAX;
}
}
while (!q.empty()) {
auto t = q.front(); q.pop();
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[t.first][t.second] + 1) continue;
matrix[x][y] = matrix[t.first][t.second] + 1;
q.push({x, y});
}
}
return matrix;
}
};
网友评论