用来记录一些leetcode刷题总结
67.二进制求和
题目：
思路：
1，转十进制计算再转回二进制，Integer,Long,BigInteger都有大小限制，而字符串可以是无穷长的，遂取消该做法。
2，二进制计算情况较少，无非就是0+0，0+1/1+0，1+1和上一位的进位，所以用if-else来判断所有情况，通过while循环来遍历每一位。首先将两个字符串长度修改成一致，把短的那个前面加上一堆零，方便计算（这个一开始没想到，惭愧）。然后通过设置一个进位，对所有可能情况进行if-else判断（菜的真实）来一位一位的计算结果，最终返回一个计算完所有位之后的完整字符串。
最终代码：
1 | public String addBinary(String a, String b) { |
2 | String result=""; |
3 | if(a.length()>b.length()){ |
4 | int addLength=(a.length()-b.length()); |
5 | for (int i=0;i<addLength;i++){ |
6 | b="0"+b; |
7 | } |
8 | } |
9 | else if(a.length()<b.length()){ |
10 | int addLength=(b.length()-a.length()); |
11 | for (int i=0;i<addLength;i++){ |
12 | a="0"+a; |
13 | } |
14 | } |
15 | Boolean flag=true; |
16 | Boolean jinwei=false; |
17 | while (flag){ |
18 | if(!a.substring(a.length() - 1, a.length()).equals(b.substring(b.length() - 1, b.length()))){ |
19 | if(jinwei){result="0"+result;} |
20 | else {result="1"+result;} |
21 | a=a.substring(0, a.length()-1); |
22 | b=b.substring(0, b.length()-1); |
23 | } |
24 | else if(a.substring(a.length() - 1, a.length()).equals(b.substring(b.length() - 1, b.length()))){ |
25 | if(a.substring(a.length() - 1, a.length()).equals("1")){ |
26 | if(jinwei){result="1"+result;} |
27 | else {result="0"+result;jinwei=true;} |
28 | a=a.substring(0, a.length()-1); |
29 | b=b.substring(0, b.length()-1); |
30 | }else if (a.substring(a.length() - 1, a.length()).equals("0")){ |
31 | if(jinwei){result="1"+result;jinwei=false;} |
32 | else {result="0"+result;} |
33 | a=a.substring(0, a.length()-1); |
34 | b=b.substring(0, b.length()-1); |
35 | } |
36 | } |
37 | if(a.length()==0&&b.length()==0){ |
38 | if(jinwei){result="1"+result;} |
39 | flag=false; |
40 | } |
41 | } |
42 | return result; |
43 | } |
69. x的平方根
题目：
思路：
1.系统自带的方法（算法鬼才）
2.傻瓜式：令s从1开始循环遍历，每次s+1，当s的平方大于x的时候停止，取s-1为结果
3.二分法(看了题解后琢磨的)：x的平方根必定小于x/2，而且是整数，所以最后当左右节点差值不大于1时，此时的左节点就是要求的结果。
方法2
1 | public int mySqrt(int x) { |
2 | boolean flag=true; |
3 | int s=0; |
4 | while (flag){ |
5 | s++; |
6 | if(x/s<s){flag=false;} |
7 | } |
8 | return s-1; |
9 | } |
方法3
1 | public int mySqrt(int x) { |
2 | if(x<2){return x;} |
3 | int left=0; |
4 | int right=x; |
5 | while (right-left>1){ |
6 | int mid=(left+right)/2; |
7 | if(x/mid<mid){ |
8 | right=mid; |
9 | }else { |
10 | left=mid; |
11 | } |
12 | } |
13 | return left; |
14 | } |
70.爬楼梯
题目：
思路：
1，递归二叉树，根节点为0，两个子节点分别为1和2，然后子节点继续生成加了1或2的子节点，最后爬n阶楼梯的方式就是n出现的次数。（不会实现而且很麻烦，但是是唯一一个自己想出来的）
2，斐波那契数列，到n阶的方法数满足斐波那契数列。到第n阶只有在n-1阶跨1阶或者在n-2阶跨2阶，所以到第N阶的方法=到第N-1的方法+到第N-2的方法，即f(n)=f(n-1)+f(n-2)。用递归来实现，结果超时了…
3，同上，加上记忆性把前面每次的结果放入数组，结果同样超时…可能我的写的有点问题。
4，据说是叫动态规划，就是用循坏来从3开始，通过斐波那契数列的公式算出每一个n的方法数，放入数组，最后返回对应数组里的值。(为啥递归就超时了，加上记忆性更不行了，而这个秒出结果)
5，官方版斐波那契数列，感觉跟动态规划差不多，只是没保存每一个n对应的值放在数组里。
方法2：
1 | public static int climbStairs33(int n) { |
2 | if(n==1){return 1;} |
3 | if(n==2){return 2;} |
4 | return climbStairs33(n-1)+climbStairs33(n-2); |
5 | } |
方法3：
1 | public static int climbStairs2(int n) { |
2 | int memo[]=new int[n+1]; |
3 | memo[0]=1; |
4 | memo[1]=2; |
5 | return climbStairs22(n,memo); |
6 | } |
7 | public static int climbStairs22(int n,int[] memo) { |
8 | if(n==1){return memo[0];} |
9 | if(n==2){return memo[1];} |
10 | memo[n]=climbStairs22(n-1,memo)+climbStairs22(n-2,memo); |
11 | return memo[n]; |
12 | } |
方法4：
1 | public static int climbStairs11(int n) { |
2 | if(n==1){return 1;} |
3 | int dp[]=new int[n+1]; |
4 | dp[1]=1; |
5 | dp[2]=2; |
6 | for (int i = 3; i < n+1; i++) { |
7 | dp[i]=dp[i-1]+dp[i-2]; |
8 | } |
9 | return dp[n]; |
10 | } |
方法5：
1 | public static int climbStairs44(int n) { |
2 | if (n == 1) { |
3 | return 1; |
4 | } |
5 | int first = 1; |
6 | int second = 2; |
7 | for (int i = 3; i <= n; i++) { |
8 | int third = first + second; |
9 | first = second; |
10 | second = third; |
11 | } |
12 | return second; |
13 | } |
83.删除排序链表中的重复元素
题目：
思路：
遍历链表，将每一项与后面项做比较，重复则将当前项的next跳过下一项指向后面。
1 | public static ListNode deleteDuplicates(ListNode head) { |
2 | if(head==null){return null;} |
3 | ListNode node = head; |
4 | while (node.next!=null){ |
5 | if (node.val == node.next.val) { |
6 | node.next = node.next.next; |
7 | }else { node=node.next;} |
8 | } |
9 | return head; |
10 | } |
88.合并两个有序数组
题目：
思路：
先找到最大值位置(第一个0前面)，遍历nums2的每一个数与nums1最大值对比，小于则往前挪。
