java的集合类使用方法
栈
Stack<ListNode> stack = new Stack<ListNode>();stack.push(temp);stack.pop()stack.size()
哈希表
HashMap<Integer,Integer> dic = new HashMap<>();
dic.put(inorder[i],i);
int i = dic.get(po[pre_root]);
常见模板
快速幂模板
快速幂用于求解a^b的大量数据的时候
int x // 是底数
int exp // exp是指数
int res // 结果
while(exp>0){
if((exp&1) == 1){ // 位运算判断奇偶
res*=x;
}
x *=x;
exp>>=1; // 位运算 /2
}
GCD
private int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
数组
数组中重复的数字
思路1： 利用自身的特性，一共是n个数字，包含（1-n-1）= = 懒得解释了。
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length ==0 || numbers== null)return false;
for(int i=0;i<length-1;i++)
{
while (i != numbers[i]){
if(numbers[i] == numbers[numbers[i]]){
duplication[0]= numbers[i];
return true;
}
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
}return false;
}
}
思路2： 直接排序，遍历一下。复杂度nlogn+n
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length==0|| numbers == null) return false;
Arrays.sort(numbers);
for(int i =1;i<length;i++){
if(numbers[i] ==numbers[i-1]){
duplication[0] = numbers[i];
return true;
}
}
return false;
思路3： 哈希表，把数据放在哈希表里面，要是不在里面就放进去，在里面就返回结果。
public boolean duplicate(int numbers[],int length,int [] duplication) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < length; i++){
if(map.containsKey(numbers[i])){
duplication[0] = numbers[i];
return true;
}
map.put(numbers[i],i);
}
return false;
}
}
2020年1月10日
不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但是不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
思路1: 使用哈希表，或者一个数组来已经有的数字。遇到已经有的就跳出。
public int find_dup_num(int[] nums){
int len = nums.length;
Map<Integer,Integer> tmp = new HashMap<>();
for(int i=0;i<len;i++){
if(tmp.containsKey(nums[i])){
return nums[i];
}
else {
tmp.put(nums[i],i);
}
}
return -1;
思路2： 利用题目的特性，1-n的范围，我们把从1n的数字从中间的数字m分为两部分，前面一半为1m，后面一半为m+1n。如果1m的数字的数目等于m，则不能直接判断这一半区间是否包含重复的数字，反之，如果大于m，那么这一半的区间一定包含重复的数字；如果小于m，另一半m+1~n的区间里一定包含重复的数字。接下来，我们可以继续把包含重复的数字的区间一分为二，直到找到一个重复的数字。
由于如果1~m的数字的数目等于m，则不能直接判断这一半区间是否包含重复的数字，我们可以逐步减少m，然后判断1~m之间是否有重复的数，即，我们可以令m=m-1，然后再计算1~m的数字的数目是否等于m，如果等于m，再令m=m-1，如果大于m，则说明1~m的区间有重复的数，如果小于m，则说明m+1~n有重复的数，不断重复此过程。 代码
public int getDuplication(int[] nums,int length){
if(nums.length<=0 || nums == null) return -1;
int start = 1;
int end = length -1;
while (end>=start){
int mid = start+(end -start)/2;
int count = countRange(nums,length,start,mid);
if(end == start){
if(count >1){
return start;
}else break;
}
if(count> (mid-start+1)){
end = mid;
}else {
start = mid+1;
}
}
return -1;
}
public int countRange(int[] nums,int length,int start,int end){
int count = 0;
for(int i:nums){
if(i>=start&& i<= end){
++count;
}
}
return count;
}
04-二维数组中的查找
思路1： 暴力枚举
思路2： 
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
boolean found = false;
int cows = matrix.length;
int columns = matrix[0].length;
int cow = 0;
int column = columns-1;
while(cow<cows&&column>=0){
if(matrix[cow][column] == target){
found = true;
break;
}
else if(matrix[cow][column]<target){
++cow ;
}else if(matrix[cow][column]>target){
--column;
}
}
return found;
}
}
011-旋转数组的最小数字
思路： 二分的方法，假如mid 大于index1的话，说明在后半段。不然就是在前半段，index2 = mid。
两种例外的情况
- 是排序好的数组，返回第一个
mid index1 index2 指向的对象是一样的。逐个遍历。
class Solution { public int minArray(int[] numbers) { if(numbers==null) return -1; int index1 = 0; int index2 = numbers.length-1; while(index2-index1!=1){ int mid = (index2+index1)/2; if(numbers[index1]==numbers[index2]&&numbers[mid]==numbers[index2]){ int result = numbers[index1]; for(int i=0;i<numbers.length;i++){ result = result>numbers[i]?numbers[i]:result; } return result; } if(numbers[mid]>=numbers[index1]){ index1 = mid; }else{ index2 = mid; } } if(numbers[index2]>=numbers[index1]){ return numbers[0]; } return numbers[index2]; } }021-调整数组顺序使奇数位于偶数前面
思路： 使用两个指针，一个在前一个在后。 假如前面的遇到了偶数，后面的遇到了奇数，swap一下。2020年3月10日 class Solution { public int[] exchange(int[] nums) { if(nums == null || nums.length<1) return nums; int head = 0; int end = nums.length-1; while(head<end){ while(head<end && (nums[head]&1)!=0){ ++head; } while(head<end && (nums[end]&1)!=1){ --end; } int tmp = nums[head]; nums[head] = nums[end]; nums[end] = tmp; } return nums; } }面试题29. 顺时针打印矩阵
算法流程：空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
- 初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
- 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印中做以下三件事 （各方向的具体信息见下表） ；
- 根据边界打印，即将元素按顺序添加至列表 res 尾部；
- 边界向内收缩 11 （代表已被打印）；
- 判断是否打印完毕（边界是否相遇），若打印完毕则跳出。
- 返回值： 返回 res 即可。
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int left = 0, right = matrix[0].length-1;
int top = 0, bottom = matrix.length-1;
int[] res = new int[(bottom+1)*(right+1)];
int x = 0;
while (true){
for(int i=left;i<=right;i++) res[x++] = matrix[left][i];
if(++top>bottom) break;
for(int i=top;i<=bottom;i++) res[x++] = matrix[i][right];
if(--right<left) break;
for(int i=right;i>=left;i--) res[x++] = matrix[bottom][i];
if(--bottom<top) break;
for(int i=bottom;i>=top;i--) res[x++] = matrix[i][left];
if(++left>right) break;
}
return res;
}
}
链表
006 从尾到头打印链表
思路：从头到尾打印说明是先进后出，可以使用一个栈的结构来辅助。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<>();
if(head == null) return new int[0];
while(head!=null){
stack.push(head);
head = head.next;
}
int count = stack.size();
int[] result = new int[count];
for(int i=0;i<count;i++){
result[i] = stack.pop().val;
}
return result;
}
}
018-删除链表的节点
思路： 使用双指针，处理一下，第一个是target的情况。cur指向head，pre指向null。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return null;
ListNode cur = head;
ListNode pre = null;
if(head.val == val){
return head.next;
}
while(cur.val!=val){
pre = cur;
cur = cur.next;
}
pre.next = cur.next;
return head;
}
}
022 链表中倒数第k个节点
思路： 使用双指针，前面的指针先走k-1步，之后p1 = head。注意，k==0，和head ==null 的情况。
还要注意k可能取不到，要在for里面做一个判断。
版本1：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head;
ListNode low = head;
if(k==0)return null;
if(head ==null) return null;
while(k>1){
fast = fast.next;
if(fast == null)
return null;
k--;
}
while(fast.next != null){
fast = fast.next;
low = low.next;
}
return low;
}
}
版本2：
/** 2020年3月10日
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(k==0|| head ==null) return null;
ListNode p1;
ListNode p2 = head;
for(int i=0;i<k-1;i++){
if(p2.next != null){
p2 = p2.next;
}else{
return null;
}
}
p1 = head;
while(p2.next!=null){
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
}
023 链表中环的入口节点
思路： 在倒数k个元素有点像，是这个的前步骤。 
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead ==null || pHead.next == null) return null;
ListNode fast = pHead.next;
ListNode low = pHead;
while(fast != low){
if(fast == null || fast.next == null){
return null;
}
fast = fast.next.next;
low = low.next;
}
ListNode meeting = fast;
int count = 1;
low = low.next;
while(meeting != low){
low = low.next;
count++;
}
fast = pHead;
low = pHead;
while(count>0){
fast = fast.next;
count--;
}
while(fast!=low){
fast = fast.next;
low = low.next;
}
return low;
}
}
024 反转链表
容易出错的点
- 输入的链表头指针为null 或者只有一个节点。
- 链表出现断裂
- 返回之后的头节点不是尾节点
在提交以前，早点准备测试用例。
- 链表只有一个，两个，多个。
链表为空
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode node = head; ListNode reverseHead = null; while(node != null){ ListNode p_next = node.next; if(p_next ==null) reverseHead = node; node.next = prev; prev = node; node = p_next; } return reverseHead; } }思路2： 使用两个指针，pre指向head，cur指向null。 开始的时候我们先获得pre的next，将pre的next指向cur，cur=pre，pre = next
最后pre.next = cur 返回这个结果。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head ==null) return null; ListNode cur = null; ListNode pre = head; ListNode reverseHead = null; while(pre.next!=null){ ListNode next = pre.next; pre.next = cur; cur = pre; pre = next; } pre.next = cur; reverseHead = pre; return reverseHead; } }025-合并两个有序的链表
思路 使用一个哨兵节点，如果l1大于l2，将ret的下一个指向l2，l2向后挪一位。ret也向后挪一位。最后剩余的东西判断一下，接上去就可以了。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode flag = new ListNode(1); ListNode ret = flag; ListNode p1 = l1; ListNode p2 = l2; if(l1==null) return l2; if(l2 == null) return l1; while(l1!=null && l2!=null){ if(l1.val>l2.val){ ret.next = l2; l2 = l2.next; ret = ret.next; }else{ ret.next = l1; l1 = l1.next; ret = ret.next; } } ret.next = l1==null?l2:l1; return flag.next; } }栈，队列
09-用两个栈实现队列
思路： stack1 只放进去， pop方法时，假如stack2中有东西，pop，没有的话吧stack1 的倒到stack2中去。再pop一下。class CQueue { Stack<Integer> stack1; Stack<Integer> stack2; public CQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void appendTail(int value) { stack1.push(value); } public int deleteHead() { if(stack1.empty()&& stack2.empty()){ return -1; } if(stack2.empty()){ putsome(); } return stack2.pop(); } private void putsome(){ if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */面试题31. 栈的压入、弹出序列
模拟一下这个操作。 我们首先向栈里面加入push的值，并且开始做判断，栈顶的元素是不是和pop的第一个元素相同，如果相同的话，那就popindex++ 而且push栈弹出，继续进行一个对比。所以这里我们是使用while来做这个循环。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int m = pushed.length;
int n = popped.length;
Stack<Integer> stack = new Stack<>();
int j=0;
for(int i=0;i<m;i++){
stack.push(pushed[i]);
while (!stack.isEmpty()&& j<n&& stack.peek() == popped[j]){
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
树
07-重建二叉树
思路： https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/
根据前序遍历可以确定根的数值，中序遍历可以确定下标。获得左右的位置之后，递归进行。 
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<Integer,Integer> dic = new HashMap<>();
int po[];
public TreeNode buildTree(int[] preorder, int[] inorder) {
po = preorder;
for(int i=0;i<preorder.length;i++){
dic.put(inorder[i],i);
}
return recur(0,0,inorder.length-1);
}
TreeNode recur(int pre_root,int in_left,int in_right){
if(in_left>in_right) return null;
TreeNode root = new TreeNode(po[pre_root]);
int i = dic.get(po[pre_root]);
root.left = recur(pre_root+1,in_left,i-1);
root.right = recur(pre_root+i-in_left+1, i+1, in_right);
return root;
}
}
08-二叉树的下一个节点
思路：有两种情况
- 节点有右子树， 下一个节点就是右子树的最左节点 例如b》h
- 节点无右子树
- 是父节点的左节点 d-b
- 是父节点的右节点 i-a。向上找节点，找到一个父节点是他父节点的左节点为止
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null)return null;
TreeLinkNode pNext = null;
if(pNode.right != null){
TreeLinkNode pRight = pNode.right;
while(pRight.left != null){
pRight = pRight.left;
}
pNext = pRight;
}else if(pNode.next != null){
TreeLinkNode cur = pNode;
TreeLinkNode par = pNode.next;
while(par!= null&&cur == par.right){
cur = par;
par = par.next;
}
pNext = par;
}
return pNext;
}
}
026-树的子结构
思路： 首先需要需要找到根节点一致的地方。找到之后开始判断是不是同一个结构。
如何找根节点一致？
其实是将A的节点和B不断进行对比，看看又没有重合。 找到之后判断一下是不是子结构。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
boolean res = false;
if(A!=null && B!=null){
if(A.val == B.val){
res = doesTreeHavaTree2(A,B);// 假如一致的话，判断是不是子结构
}
if(!res){
res = isSubStructure(A.left,B);// 递归判断左右子树。
}
if(!res){
res = isSubStructure(A.right,B);
}
}
return res;
}
private boolean doesTreeHavaTree2(TreeNode a,TreeNode b){
if(b ==null) return true; // 假如b 遍历完了，说明数据匹配
if(a ==null) return false;// a先空了，说明不匹配
if(a.val !=b.val) return false;//数值不对，返回false
return doesTreeHavaTree2(a.left,b.left)&&doesTreeHavaTree2(a.right,b.right);//一定要左右子树都一样
}
}
027-二叉树的镜像
思路： 交换节点的左右节点，递归下去他的左节点和右节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
if(root.left == null&& root.right ==null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
if(root.right!= null){
mirrorTree(root.right);
}
if(root.left != null){
mirrorTree(root.left);
}
return root;
}
}
面试题28. 对称的二叉树
思路： 使用递归的方法来进行一个对比。 可以定义一个根-后-前的遍历方法来进行一个对比。
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root,root);
}
private boolean isSymmetric(TreeNode root1, TreeNode root2){
if(root1==null&&root2==null){
return true;
}else if(root1==null||root2==null){
return false;
}else if(root1.val!=root2.val){
return false;
}
return isSymmetric(root1.left,root2.right)&&isSymmetric(root1.right,root2.left);
}
}
面试题32 - I. 从上到下打印二叉树
其实这道题就是一个层序的遍历，看到这样的题目第一个想到的就是队列这种数据结构。或者说是BFS吧，借助一个队列，首先把里面的root放到里面去。每次把他的左右孩子再放进去。
class Solution {
public int[] levelOrder(TreeNode root) {
if(root== null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode tmp = queue.poll();
res.add(tmp.val);
if(tmp.left!=null){
queue.add(tmp.left);
}
if(tmp.right!=null){
queue.add(tmp.right);
}
}
int[] ans = new int[res.size()];
for(int i=0;i<res.size();i++){
ans[i] = res.get(i);
}
return ans;
}
}
面试题32 - II. 从上到下打印二叉树 II
这道题和原来的那道题有一点像。需要改的是，这次是一层放一个list里面。再放入一个大的list中。
所以我们再每次的循环的时候，建立一个list，每次遍历一下队列里面的数据，放到里面。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()){
ArrayList<Integer> node = new ArrayList<>();
for(int i=queue.size();i>0;i--){
TreeNode tmp = queue.poll();
node.add(tmp.val);
if(tmp.left!=null){
queue.add(tmp.left);
}
if(tmp.right!=null){
queue.add(tmp.right);
}
}
res.add(node);
}
return res;
}
}
面试题32 - III. 从上到下打印二叉树 III
这个就是需要根据层数，奇偶性遍历，奇数是前往后，偶数是后往前来计算。所以我们需要一个标识符来记录一下是基础还是偶数。如何倒着打印呢？可以使用双向队列的一个方法，每一次都把元素插入到最前面。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
boolean flag= true;
while (!queue.isEmpty()){
ArrayList<Integer> node = new ArrayList<>();
for(int i=queue.size();i>0;i--){
TreeNode tmp = queue.poll();
if(flag) node.add(tmp.val);
else node.add(0,tmp.val);
if(tmp.left!=null){
queue.add(tmp.left);
}
if(tmp.right!=null){
queue.add(tmp.right);
}
}
flag=!flag;
res.add(node);
}
return res;
}
}
面试题33. 二叉搜索树的后序遍历序列
主要就是要吧数组分成好几部分，左子树，右子树，根节点。对其中的数做一个比较。以及递归的终止条件是啥需要搞清楚。
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder.length<1|| postorder== null) return true;
return recur(postorder,0,postorder.length-1);
}
private boolean recur(int[] postorder,int i,int j){
if(i>=j)return true;
int p = i;
while (postorder[p]<postorder[j])p++;
int m = p;
while (postorder[m]>postorder[j])m++;
return m==j&&recur(postorder,i,p-1)&&recur(postorder,p,j-1);
}
}
回溯
012-矩阵中的路径（未做）
013-机器人的运动路径（未做）
动态规划
014-1-剪绳子
思路： 动态规划的四个特点
- 问题能够分解成多了子问题
- 整体依赖局部最优解
- 小问题之间有重叠
- 从上到下分析问题
从下往上解决这个问题。先算出n=3的，把之前的最优解都存储到一个数组里面。不断增加n的数值。最后得到结果。
class Solution {
public int cuttingRope(int n) {
if(n <2)return 0;
else if(n==2)return 1;
else if(n==3)return 2;
int[] res = new int[n+1];
res[0] = 0;
res[1] = 1;
res[2] = 2;
res[3] = 3;
int max = 0;
for(int i=4;i<=n;++i){
max=0;
for(int j=1;j<=i/2;++j){
int rope = res[j]*res[i-j];
if(max<rope){
max = rope;
}
res[i] = max;
}
}
return res[n];
}
}
贪心
014-2-剪绳子
将可能多的剪3的绳子，去幂的话，诗快速幂来进行加速。
class Solution {
public int cuttingRope(int n) {
if(n<2)return 0;
else if(n==2)return 1;
else if(n==3) return 2;
int p = 1000000007;
int timeOf3 = n/3;
if(n%3 ==1){
timeOf3-=1;
}
int timeOf2 = (n-timeOf3*3)/2;
long ans =1;
long a = 3;
while(timeOf3!=0){
if(timeOf3%2==1){
ans = (ans*a)%p;
}
timeOf3/=2;
a = (a*a)%p;
}
if(timeOf2 ==0)return (int)ans;
else if(timeOf2 ==1) return (int) (ans*2%p);
else return (int)(ans*4%p) ;
}
}
滑动窗口
位运算
015-二进制中1的个数
思路:
- 用1来按位与过去，每一次都将1左移一位。
将n-1和n进行与运算。每次可以去掉一个二进制中的1。这个思路挺有用的。
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count =0; while(n!=0){ ++count; n = (n-1)&n; } return count; } }其他
10-1 斐波那契数列
思路： 从底而上，一个一个加过来。class Solution { public int fib(int n) { int[] res = new int[]{0,1}; if(n<2) return res[n]; int fibMinusOne = 1; int fibMinusTwo = 0; int fibN = 0; for(int i=2;i<=n;i++){ fibN = (fibMinusOne+fibMinusTwo)% 1000000007; fibMinusTwo = fibMinusOne; fibMinusOne = fibN; } return fibN; } }10-2青蛙跳台阶问题
思路： 分解问题 f（n） = f（n-1）+f（n-2）
f（1） = 1
f（2） = 2 其实就是斐波那契数列class Solution { public int numWays(int n) { int[] res = new int[]{1,1,2}; if(n<3)return res[n]; int a = 1; int b = 2; int sum = 0; for(int i=2;i<n;i++){ sum = (a+b)%1000000007; a = b; b = sum; } return sum; } }016-数值的整数次方
思路：
需要注意 0的时候底数是负数的情况。需要作处理。
指数为负数的时候，需要取绝对值。将x = 1/x 。int的最小值为[−2147483648,2147483647] 所以需要一个long才能将最小值转换为正数。 ``` class Solution { boolean vaildInput = false; public double myPow(double x, int n) {if(x==0.0&& x<0){ vaildInput = true; return 0.0; } long exp = n; if(n<0) { exp = -exp; x = 1/x; } double res=1.0; while(exp>0){ if((exp&1) == 1){ res*=x; } x *=x; exp>>=1; } return res;}
}
<a name="ot1qM"></a>
### 017-打印从1到最大的n位数
 思路：<br />使用快速幂，来获取最大值数值。建立一个数组，遍历完里面塞东西。
class Solution { public int[] printNumbers(int n) { int len =1; int base = 10; while(n>0){ if((n&1)==1){ len = base; } base =base; n>>=1; } int[] res = new int[len-1]; for(int i=0;i<res.length;++i){ res[i] = i+1; } return res; } } ```
若有收获，就点个赞吧
0 人点赞
