LeetCode 剑指offer 简单篇（更新中）
我有信心，这篇帖子一定连更，绝对不鸽！！
5.6 元气满满第一天
[ 剑指offer03. 数组中重复的数字 ]
class Solution {
public int findRepeatNumber(int[] nums) {
//我的的思路：把nums放进hash表中，nums[i]是否在hash表中，在的话，返回nums[i]
//知识点：关于hashset和hashmap
//HashMap实现了Map接口 HashSet实现了Set接口
//HashMap储存键值对 HashSet仅仅存储对象
//使用put(key,value)方法将元素放入map中 使用add(value)方法将元素放入set中
//不允许key重复，但允许value重复 不允许value重复，重复元素放不进去
//在hashmap中
//获取key所对应的value值，没有就获取defaultValue;hash.getOrDefault(key,defaultValue)
//判断是否包含元素是由containsKey()
//hashSet判断是否包含元素使用 contains()
Set<Integer> hash=new HashSet<Integer>();
hash.add(nums[0]);
for(int i=1;i<nums.length;i++){
if(hash.contains(nums[i])){
return nums[i];
}else{
hash.add(nums[i]);
}
}
return -1;
}
} 复杂度分析：
时间复杂度：遍历数组O(n),向hash中添加元素O（1）,所以时间复杂度O（n）
空间复杂度：不重复的元素每个都有可能存入集合，O（n）
[ 剑指offer 05.替换空格 ]
class Solution {
public String replaceSpace(String s) {
//K神思路：在java中 String是字符串常量，不可变对象，无法直接修改字符串的某一位，需要新建一个可以修改的字符串对象进行替换。遍历字符串，放入res中，如果某个字符为' ',append("%20")
//知识点：
//关于StringBUffer 和StringBuilder
//StringBuffer字符串变量，线程安全，支持多线程，若需要经常对字符串进行改变，用它，转换为string对象使用toString()方法，append(E)在末端添加元素，insert(index,E)在指定地点添加元素。相当于全局变量。
//StringBuilder 一般用在内部，线程不安全，相当于'+',用完可以丢弃。
//关于char和character
//char是基本数据类型，Character是其包装器类，实例化出来的叫对象。
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c==' '){
sb.append("%20");
}else{
sb.append(c);
}
}
return sb.toString();
}
} 复杂度分析：
时间复杂度：遍历字符串O（n),向sb后边添加字符O（1），所以时间复杂度为O（n)
空间复杂度:一个可变的字符串，最多可能存放3n个元素，空间复杂度O（n）。
[ 剑指Offer 06.从尾到头打印链表 ]
方法一：辅助栈
class Solution {
public int[] reversePrint(ListNode head) {
//我的思路：一涉及到反转，一般都会用到栈这个数据结构，后进先出。
Deque <Integer> stack=new LinkedList<>();
while(head!=null){
stack.push(head.val);
head=head.next;
}
int []res=new int[stack.size()];
for(int i=0;i<res.length;i++){
res[i]=stack.pop();
}
return res;
}
} 复杂度分析： 时间复杂度：两次循环，出栈入栈共使用O（n）
空间复杂度：既有构造stack,也有构造数组，O（n）
方法二：不用栈不递归，怎样都是扫描两遍，不额外消耗空间倒叙存放，直接倒着构造所需返回的数组即可。
方法二：不用栈不递归，怎样都是扫描两遍，不额外消耗空间倒叙存放，直接倒着构造所需返回的数组即可。
class Solution {
public int[] reversePrint(ListNode head) {
//把head当哨兵，让node去走循环，得到链表的长度len
ListNode node=head;
int len=0;
while(node!=null){
node=node.next;
len++;
}
//定义res,倒叙构造res
int [] res=new int[len];
for(int i=len-1;i>=0;i--){
res[i]=head.val;
head=head.next;
}
return res;
}
} 复杂度分析：
时间复杂度：两次循环O（n）
空间复杂度：构造数组O（n)
[ 剑指Offer 09.用两个栈实现队列 ]
这题拿捏住一个关键：删除元素的原则：只有当删除栈为空时，才把输入栈的元素导入。
class CQueue {
//我的思路：先定义两个栈，栈是后进先出的，实现队列，先进先出，前出后进，然后实现插入删除方法
//不要直接用stack做，速度慢。原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。
//可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
//s1,s2放外边大家都能用
Deque<Integer> s1;
Deque<Integer> s2;
public CQueue() {
//实例化对象
s1=new LinkedList<>();
s2=new LinkedList<>();
}
public void appendTail(int value) {
//放入第一个栈
s1.push(value);
}
public int deleteHead() {
/*删除元素的原则：只有当输出栈为空时候，才将输入栈的元素导入，否则先输出输出栈中的元素 */
//当输出栈为空,且输入栈不为空时
if(s2.isEmpty()&& !s1.isEmpty()){//判断栈空的方法isEmpty()
while(!s1.isEmpty()){
s2.push(s1.pop());
}
return s2.pop();
}else if(s1.isEmpty() && s2.isEmpty()){//输出栈为为空，输入栈为空
return -1;
}else {//输出栈不为空
return s2.pop();
}
}
} 第一次做时候的一些小笔记：其实以前做的就很好了，一定多多反思总结。
class CQueue {
// 栈（stack）：先进后出
// 队列(queue)：先进先出
// Deque接口，是queue接口的子接口，是指队列两端的元素，既能入队（offer）也能出队。
// 如果将Deque限制为只能从一端进行入队，和出队，就是栈的数据结构的实现。对于栈而言，有入栈（push）和出栈（pop），遵循先进后出的规则
//Java的集合类并没有单独的Stack接口，因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。
// 当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，那样会破坏栈的本质。
// 用两个栈实现队列时，使用deque
// 这道题中定义栈的方法
// Deque <Integer> stack=new LinkedList<>();
// java语言不使用这种方法普通定义栈的方法
// Stack<Integer> stack=new Stack<>()
// 普通定义队列的方法
// Queue <Integer> queue=new LinkedList<>();
// 这道题的解题思路
// 两个栈s1,s2 因为栈的特性是先进后出，队列的特性是后进先出
// 一个栈s1实现插入，一个栈s2实现删除
// s1直接入栈 s1.push()一个元素
// s2删除元素，s1入栈直接压到栈底了，所以会后出，将s1中的元素一个个的pop到s2中，后进s1的元素就被压到s2栈底了
// 有一个问题是，当s2中有元素，又向s1push 了新的元素，但是按理说应该s2中的元素按先进先出的规则先走，要注意的是，当s2不为空时，s1不许向里压栈，只有s2空了，才允许向里填s1中的所有元素
// 判断为空s.isEmpty(),是true,否false
// 定义两个栈
//定义两个公共变量s1,s2
Deque<Integer> s1;
Deque<Integer> s2;
public CQueue(){
s1=new LinkedList<>();
s2=new LinkedList<>();
}
public void appendTail(int value){
s1.push(value);
}
public int deleteHead(){
//当s2不为空时
//栈的判空isEmpty()
if(!s2.isEmpty()){
return s2.pop();
}
//当s2为空时 当s1不为空时
if(s2.isEmpty() &&!s1.isEmpty() ){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
return s2.pop();
}
//当s1s2为空，返回-1
return -1;
}
} 复杂度分析： 时间复杂度：appendTail()的只需要一次添加元素，时间复杂度为O（1）；deleteHead()在最坏情况下输出栈可能要添加N个元素，所以时间复杂度为O（n）。
空间复杂度：在最差情况下，输入输出栈可能要添加N个元素。
5.8
[ 剑指Offer 10-Ⅰ.斐波那契数列 ]
class Solution {
public int fib(int n) {
//我的思路：迭代的思路在里边，最后一个元素的值与前两个元素的有关，那么我把前俩个元素的值存起来即可。
//特殊情况先输出
if(n==0){
return 0;
}
if(n==1 || n==2){
return 1;
}
int [] res=new int[3];
res[0]=0;
res[1]=1;
res[2]=1;
for(int i= 3;i<=n;i++){
res[0]=res[1];
res[1]=res[2];
res[2]=(res[0]+res[1])%1000000007;//记得题目要求的取余
}
return res[2];
}
} 复杂度分析：
时间复杂度：f(n)需要进行n次循环，O(N)
空间复杂度：开辟了一个长度为常数的数组，O（1)
以前的思路：
class Solution {
public int fib(int n) {
//方法一、动态规划
if(n==0){
return 0;
}
if(n==1){
return 1;
}
//字符串长度是可以变化的
int [] dp= new int [n+1];
dp[0]=0;
dp[1]=1;
//取余符号%
for(int i=2;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2])%(1000000007);
}
return dp[n];
// //方法二、递归
// //如果n=1或者2时
// if(n==1 || n==2){
// return 1;
// }
// //把最开始两个数组存储起来
// int a=0,b=1;
// int ans=0;
// for(int i=2;i<=n;i++){
// ans=(a+b)%(1000000007);
// a=b;
// b=ans;
// }
// return ans;
}
} [ 剑指Offer 10-Ⅱ.青蛙跳台阶问题 ] 
这题跟上边异曲同工
class Solution {
public int numWays(int n) {
//我的思***蛙的最后一跳有两种情况，跳一阶或者跳两阶，所以只要求出青蛙跳倒数第一阶之前的方法+跳倒数第二阶之前的方法之和，即可获得青蛙跳台阶的方法。还是一个递归的问题，最后一跳需要前边跳法递归而来。f(n)=f(n-1)+f(n-2),跟斐波那契数列一模一样。
int []dp=new int[n+1];//把0阶台阶也算上，对应着好看
if(n==0||n==1){
return 1;
}
//0阶台阶，1种；一阶台阶，1中；二阶台阶，2种
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
} 复杂度分析：
时间复杂度：f(n)需要进行n次循环，O(N)
空间复杂度：开辟了一个长度为n+1数组，O（n)
5.9 不要偷懒
[ 剑指Offer 11.旋转数组的最小数字 ]
class Solution {
public int minArray(int[] numbers) {
//思路：旋转数组最开始是一个升序数组，当这个数组整个进行旋转时返回原数组。第一个值就是最小值（特殊情况）。
//部分旋转：当后边的一个值小于前边的值时，说明后边那个值就是最小值，返回后边那个值即可。
int res=-1;
//部分旋转
for(int i=0;i<numbers.length-1;i++){
if(numbers[i]>numbers[i+1]){
res=numbers[i+1];
return res;
}
}
//完全旋转
return numbers[0];
}
} 复杂度分析： 时间复杂度：遍历数组，O(N)
空间复杂度:只用了1个变量，O（1）
官方、K、liweiwei都说二分法，贴一个二分的上来
class Solution {
public int minArray(int[] numbers) {
//二分法思路：双指针i,j指向数组两端，其中mid=i+(j-i)/2。
//当numbers[mid]>numbers[j]时，m在大数组中，所求最小的值在[mid+1,j]中，令i=mid+1
//当numbers[mid]<numbers[j]时，m在小数组中，所求最小值在[i,m],令j=mid;
//当numbers[mid]=numbers[j]时，最小值不能确定在哪边，比如[5,4,4,4,4]和[1,2,2,2,2]，执行j=j-1,打破这个平衡,然后继续比较。
//当i=j时跳出循环，返回numbers[j]即可。
int i=0,j=numbers.length-1;
while(i<j){
int mid=i+(j-i)/2;//如果是(i+j)/2,可能会出现越界问题
if(numbers[mid]>numbers[j]){
i=mid+1;
}else if(numbers[mid]<numbers[j]){
j=mid;
}else{
j=j-1;
}
}
return numbers[j];
}
} 复杂度分析： 时间复杂度： 二分法，没有完全的遍历数组 O(logN) 。在数组全部旋转情况下，为O（N）
空间复杂度：i,j，m使用常数个额外空间 O(1)
5.10 新到的这个组可真卷呀，快乐的摸鱼时光一去不复返了~
[ 剑指Offer 15.二进制中1的个数 ]
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
//思路：题干说32位的二进制数，遍历这个二进制数32次，用二进制数最后一位进行异或操作，如果等于1，cnt++;二进制数进行右移，进行下次循环
int cnt=0;
for(int i=0;i<32;i++){
if((n&1)==1){//判断当前位是否为1，&运算都为1才等于1
cnt++;
}
//n进行右移1位，比较下一位,前边缺少的用0补上
n=n>>>1;
}
return cnt;
}
} 以前的做法：
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
//二进制中的与 或 非 异或
//与& 全1则1
//或| 有1则1
//非~ 按位取反 ~10000 =01111
//异或^ 相同取0，不同取1
//位移运算：常见有左位移（<<<），与右位移（>>>）简单说就是将一个二级制数中的1向左或向右移动若干位，多余的位用0补齐
//若 n& 1 = 0,则 n 二进制 最右一位 为 0；
//若 n & 1 = 1,则 n 二进制 最右一位 为 1 。
//&只能比较最后一位的，然后需要进行右移，移过的位置用0补齐
int cnt=0;
for(int i=0;i<32;i++){
//用小括号括起来
if((n &1) ==1){
cnt++;
}
//比较完一次之后，将n右移一位，比较下一位，格式如下
n=n>>>1;
}
return cnt;
}
} 复杂度分析： 时间复杂度：O（K）,K为二进制数的位数，32
空间复杂度：O(1)，我们只需要常数的空间保存若干变量。
[ 剑指Offer 17.打印从1到最大的n位数 ]
这题学到一个函数Math.pow(底数，次方数)，这个数出来是double类型，注意转换类型
class Solution {
public int[] printNumbers(int n) {
//Math.pow(底数,几次方)
// 如：int a=3;
//int b=3;
//int c=(int)Math.pow(a,b);
//就是3的三次方是多少；a、b及函数值都是double型,强制装换成int类型的
int len=(int)Math.pow(10,n)-1;
int [] res=new int[len];
for(int i=0;i<len;i++){
res[i]=i+1;
}
return res;
}
} 复杂度分析： 时间复杂度：O(10^n) ： 生成长度为 10^n 的列表需使用 O(10^n) 时间。
空间复杂度：列表的长度固定，需要O（1）大小的额外空间。
投递快手等公司10个岗位 >
