不想写第二遍的刷题笔记

世界级打野都是rush大龙的

用两个栈实现队列

剑指Offer 9

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

push和pop两种操作都先清空其中一个栈

class Solution {
public:
void push(int node) {
while (!stack2.empty()) {
stack1.push(stack2.top());
stack2.pop();
}
stack1.push(node);
}

int pop() {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
int node = stack2.top();
stack2.pop();
return node;
}

private:
stack<int> stack1;
stack<int> stack2;
};

两个队列实现一个栈

一般情况下放在其中一个队列中,栈pop时,把这个队列里的放入另一个队列,最后一个元素就是要pop的元素

斐波那契数列

剑指Offer 10

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
n<=39

使用递归会影响性能

class Solution {
public:
int Fibonacci(int n) {
if (n==1 || n==2) {
return 1;
}
int a=1,b=1, ans=0;
for (int i=0; i<n-2; i++) {
ans = a+b;
a = b;
b = ans;
}
return ans;
}
};

也可以通过数学归纳得到公式

求an时,可以基于递归用O(logn)时间求出aa/2再得到n次方。

跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

对于每一个f(n),有两种可能,即f(n) = f(n-1) + f(n-2)

class Solution {
public:
int jumpFloor(int number) {
if (number==1) {
return 1;
}
if (number==2) {
return 2;
}
return jumpFloor(number-1) + jumpFloor(number-2);
}
};

变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

数学归纳法

通过f(n) = f(n-1) + f(n-2) + … + f(1) + 1得出f(n) = 2 n-1

#include <math.h>

class Solution {
public:
int jumpFloorII(int number) {
return exp2(number-1);
}
};

两数之和

LeetCode 1 LintCode 56

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

BruteForce

class Solution(object):
def twoSum(self, nums, target):
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
return [i, j]

Hash表

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i, num in enumerate(numbers):
if target-num in dic:
return [dic[target-num], i]
else:
dic[num] = i
object Solution {
import scala.collection.mutable
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val hashMap = mutable.HashMap[Int,Int]()
def loop(n: Int): Array[Int] = {
if ((n<=nums.length) && (hashMap contains (target-nums(n)))) {
Array(hashMap(target-nums(n)), n)
}
else {
hashMap.put(nums(n), n)
loop(n+1)
}
}
loop(0)
}
}
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i=0;i<nums.length;i++) {
if (hashMap.containsKey(target - nums[i])) {
return new int[]{hashMap.get(target-nums[i]), i};
}else{
hashMap.put(nums[i], i);
}
}
return new int[]{-1, -1};
}
}

Best Time to Buy and Sell Stock

LeetCode上的一个系列题

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

把sell固定在buy的右边

class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)==0:
return 0
buy = sell = prices[0]
ans = 0
for i in prices:
buy = min(buy, i)
sell = max(buy, i)
ans = sell-buy if sell-buy>ans else ans
return ans

122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

找到峰值和谷值

class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices)==0:
return 0
ans = 0
sell = buy = prices[0]
i = 0
while i < len(prices)-1:
while i<len(prices)-1 and prices[i]>=prices[i+1]:
i+=1
buy = prices[i]
while i<len(prices)-1 and prices[i]<=prices[i+1]:
i+=1
sell = prices[i]
ans += sell - buy
return ans

try to decrypt

从WeChall找到的站,https://www.trytodecrypt.com

easy

这个站的题好像都是给一个加密的函数,可以直接给明文返回密文然后破解。

Text 1

131017171A48221A1D170F

这一题非常简单,就是从从0-9a-zA-Z到数字的类似ASC码的简单的映射替换

import sys

c = '131017171A48221A1D170F'

i = 0
while i<len(c):
t = int(c[i:i+2], 16)
if t == 0x48:
sys.stdout.write(' ')
elif t <= 0x0B:
sys.stdout.write(chr(t-2+48))
elif t <= 0x25:
sys.stdout.write(chr(t-0x0C+97))
else:
sys.stdout.write(chr(t-0x26+65))
i += 2

Winter Sleep

http://solveme.safflower.kr/

<?php
error_reporting(0);
require __DIR__.'/lib.php';

if(isset($_GET['time'])){

if(!is_numeric($_GET['time'])){
echo 'The time must be number.';

}else if($_GET['time'] < 60 * 60 * 24 * 30 * 2){
echo 'This time is too short.';

}else if($_GET['time'] > 60 * 60 * 24 * 30 * 3){
echo 'This time is too long.';

}else{
sleep((int)$_GET['time']);
echo $flag;
}

echo '<hr>';
}

highlight_file(__FILE__);

一道关于PHP科学计数法表示的题

通过构造这样的time即可,/prob/winter_sleep/?time=5.19e6