11 二进制种1的个数★
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。。
思路：
这题感觉应该还会有很多思路和解法，单身笔者自身只写了两个方法吧，后面讨论看题解会进行补充。
法一：直接转成二进制字符串。然后进行比较里面的1的个数。
法二： 大家知道每个类型的数据它的背后实际都是二进制操作。大家知道int的数据类型的范围是(-231,231-1)。并且int有32位。但是并非32位全部用来表示数据。真正用来表示数据大小的也是31位。最高位用来表示正负。
首先大家要知道：
1<<0=1 =00000000000000000000000000000001
1<<1=2 =00000000000000000000000000000010
1<<2=4 =00000000000000000000000000000100
1<<3=8 =00000000000000000000000000001000
. . . . . .
1<<30=230 =01000000000000000000000000000000
1<<31=-231 =10000000000000000000000000000000
其次还要知道位运算&与。两个十进制与运算.每一位同1为1。所以我们用2的正数次幂与知道的数分别进行与。如果结果不为0，那么就说明这位为1.(前面31个都是大于0的最后一个与结果是负数但是如果该位为1那么结果肯定不为0)
代码：
public int NumberOf1(int n) { int va=0; String num=Integer.toBinaryString(n); for(int i=0;i<num.length();i++) { if(num.charAt(i)=='1') { va++; } } return va; } public int NumberOf2(int n) { int va=0; for(int i=0;i<32;i++) { if((n&(1<<i))!=0) { va++; } } return va; } public int NumberOf3(int n) {//上面的差不多，可能慢一点 int va=0; int num=1; for(int i=0;i<32;i++) { if((n&num)!=0) { va++; } num*=2; } return va; }
评论区参考：
看了评论区，发现前面的方法很多人采用，但是也有些有差别的：我那个是用这个数分别和2,4,8,16等进行位运算计算，还有事用位运算右移每次和1进行位运算比较。其实本质一样的，就是选的静止参照物不同而已。
而还有一种非常棒的方法，确实没想到，就是运用n&(n-1)。n如果不为0，那么n-1就是二进制第一个为1的变为0，后面全为1.这样的n&(n-1)一次运算就相当于把最后一个1变成0.这样一直到运算的数为0停止计算次数就好了。
实现代码为：
public class Solution { public int NumberOf1(int n) { int count=0; while (n!=0) { n=n&(n-1); count++; } return count; } }
12 数值的正数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
思路：
法1：直接利用数学包求。或者直接进行exponent次相乘。复杂度为O(n);
法2：快速幂求法。首先快速幂思想可以参考以前写的一个记录快速幂模板。但是这题有点不同就是不需要求余。也就是说数值不会越界，数值可能较小。
还有一点快速幂适合正数次幂这里可能为负数次幂。假设a,b大于0.但是a-b可以转化为(1/a)b然后进行快速幂！时间复杂度为O(logn).
代码：
public double Power(double base, int exponent) { return Math.pow(base, exponent); } public double Power(double base, int exponent) { if(base==0)return 0; if(exponent<0) {exponent=-exponent;base=1/base;} if(exponent==0)return 1; else if (exponent % 2 == 0) { return Power(base*base, exponent/ 2) ; } else return base*Power(base*base, (exponent-1)/ 2); }
13 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：
题目要求1、奇数位于偶数前面2、奇数之间相对位置不变。
注意事项： void函数，注意对象克隆，深浅拷贝。如果是java最好先了解java函数调用参数(指针)问题。
需要新开数组team复制(克隆)array数组。
进行两次遍历team，一次从左向右找奇数从左向右赋值给array对应位置。
一次从右向左遍历team将数值从右往左赋值给array对应位置。
public class Solution { public void reOrderArray(int [] array) { int team[]=array.clone(); int index=0; for(int i=0;i<team.length;i++) { if((team[i]&1)==1)//如果为奇数 array[index++]=team[i]; } index=team.length-1; for(int i=team.length-1;i>=0;i--) { if((team[i]&1)==0) array[index--]=team[i]; } } }
参考讨论区：
我是基于开辟新空间数组跑两遍实现的，但是有的讨论区不开辟新空间的话那就只能考虑一些排序(插入排序)。当然，在vx打卡交流群中有个小姐姐曾经用两个队列跑一遍储存感觉思想也很棒！还没想到用队列呢！
14 链表中倒数第K个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路：
感觉这题可以搞得实现方式比较多吧。
比如你可以借助一个Arraylist之类集合将链表遍历加入。根据集合大小和K直接取值(自行ac)。
比如你还可以不借助外部集合，第一次遍历到尾获得链表长度l。根据长度l和倒数第k个节点获得正数的序号。再遍历一次取该节点的值即可！
代码：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head, int k) { int count = 0; ListNode team = head; while (team != null) { count++; team = team.next; } int value = count - k; int index = 0; while (head!= null) { if (index == value) { return head; } index++; head = head.next; } return head; } }
参考讨论区
这题参考了讨论区发现了一些其他也很不错的解法：
比如递归先到头，返回的时候对整型数值叠加符合题意返回，判断处理即可！
还有就是定义快慢指针。这个思想就像两辆车中间拖个绳子，前车走的如果超过绳子长度就拉着后车保持绳子长度跑。如果绳子没拉直那就肯定不符合题意哒！
15 反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
思路：
法一：最简单的想法是遍历整个链表，head用来遍历。team用来作为新链表返回。每次遍历时候新建一个listNode指向前面的team。
实现代码：
public static class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public ListNode ReverseList(ListNode head) { if (head == null) return head; ListNode team = new ListNode(head.val);// head的第一个当作team的最后一个 while (head != null) { head = head.next; if (head != null) { ListNode listNode = new ListNode(head.val); listNode.next = team;// 将它指向lsitNode team = listNode;// team指向listnode } } return team; }
法二(参考)：参考了评论区一个递归的方案，感觉很巧妙，至于理解就像图所画。
实现代码为：
public static ListNode ReverseList(ListNode head) { if (head == null||head.next==null) return head; else { ListNode node=ReverseList(head.next); head.next.next = head; head.next = null; return node; }
理解为：
16 合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：
感觉可行方案还是不止一个的。
比如两个链表你可以用一个list1作为主链表返回。返回另一个list2进行遍历比较插入到主链表适当位置中。有兴趣可以试一试。
当然你还可以直接建立一个新链表头节点value。list1和list2同时遍历，取小的节点添加到value为头节点的链表中。同时小的那个链表向下进行下一轮比较。直到list1和list2都为null为止。
代码为：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; else if (list2== null) {return list1; } ListNode value=new ListNode(0); ListNode team=value; while(list1!=null&&list2!=null) { if(list1.val<list2.val) { team.next=new ListNode(list1.val); list1=list1.next; team=team.next; if(list1==null) { team.next=list2; break; } } else { team.next=new ListNode(list2.val); list2=list2.next; team=team.next; if(list2==null) { team.next=list1; break; } } } value=value.next; return value; } }
参考讨论区：
有个图感觉很精妙，省的画啦，当然我是用用两个节点一直while(这样的比较)，而讨论区有兄弟用递归的方法感觉也很不错的！具体讨论可以到牛客讨论区看得到哈。
17 树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
这题当时还卡住了。判断B是不是A的子结构。我最初想着是不是直接在A树上某个节点开始结构一直往下就和B相同。但这显然是错的。因为B是A的子结构。很可能不到叶子节点就是中间的一小部分。但是这个也不难解决。只需要判断B到叶子节点停止一下就可以了。
这题需要一个节点一个节点的进行比较。我才用队列的层序遍历(bfs)。当有相同的就停止返回。执行到最后不停止就说明这个是没有相同的 。
代码为：
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.ArrayDeque; import java.util.Queue; public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { Queue<TreeNode>q1=new ArrayDeque<TreeNode>(); if (root2==null||root1==null) return false; else { q1.add(root1); while (!q1.isEmpty()) { TreeNode t1=q1.poll(); if(jud(t1, root2)) return true; else { if(t1.left!=null)q1.add(t1.left); if(t1.right!=null)q1.add(t1.right); } } return false; } } public boolean jud(TreeNode root1,TreeNode root2) { if(root2==null)return true; else if(root1==null) { return false; } else if(root1.val==root2.val) { return (jud(root1.left, root2.left)&&jud(root1.right,root2.right)); } else { return false; } } }
参考评论区：
主要思想差不多吧，要注重子树和子结构的区别。当然个别大佬把HasSubtree函数用递归写了感觉效率很差，就不贴了有兴趣的可以自己研究哈！
18 二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述
二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
思路：
最直观和好想的肯定是递归法。遇到二叉树这种未知结构大部分都可以采用递归求解，只需要交换节点左右子树即可。而上述的递归过程大致如下：
二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 //step1 第三层交换 8 / \ 6 10 / \ / \ 7 5 11 9 //step2 第二层交换，第一层不需要交换 8 / \ 10 6 / \ / \ 11 9 7 5
实现代码为：
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public void Mirror(TreeNode root) { if(root==null) return; TreeNode teamNode=root.right; root.right=root.left; root.left=teamNode; if(root.left!=null) {Mirror(root.left);} if(root.right!=null) {Mirror(root.right);} } }
19 顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路：
这题其实方法还是蛮重要的。个人主要两个想法吧：
思路一：模拟
大家都知道是顺时针进行旋转式的输出。那么这本身就是一次运动，那么我们就可以模拟这个光标的运动，一直到结束。
想法虽然简单，但是实现起来很麻烦！比如，你可能需要用参数标记当前的方向，还可能需要用个boolean数组判断是否走过和是否越界问题。还可能需要多个if else当判定当前结束选择下一个方向。想想这个代码一定是很臃肿的。虽然可以实现，有兴趣的可以尝试。
思路二：数学计算(不一定说的很好可以自行理解)
正常情况下：一个顺时针是进行四次！但是每次走的位置咱们是可以确定的。咱么假设竖的为X,横的为Y。
先不考虑走完的问题。每次走的四次开始的坐标和结束的坐标是可以算出来的！因为相当于每走一圈横纵坐标都减二。而开始和结束位置分别加1和减1。所以每次走的结束位置可以准确表示出来。
考虑走完的问题。肯定是根据窄的走完。问题还有奇偶的问题。如果偶数的话可以刚好走完，而奇数需要特殊判断一下省略最后一次循环一些步骤才行！
其他注意点。当循环添加一轮的时候，实际上当前的坐标是有变化的。需要手动修正一下
实现代码为：
import java.util.ArrayList; public class Solution { public ArrayList<Integer> printMatrix(int [][] matrix) { ArrayList<Integer> list=new ArrayList<Integer>(); int xlen=matrix.length; int ylen=matrix[0].length; int min=Math.min(xlen, ylen); int x=0;//上下 纵坐标 int y=0;//左右 横坐标 for(int i=0;i<(min+1)/2;i++) { for(;y<ylen-i;y++) {list.add(matrix[x][y]);}y--;x++; for(;x<xlen-i;x++) {list.add(matrix[x][y]);}x--;y--; if(i==xlen/2)continue; for(;y>=i;y--) {list.add(matrix[x][y]);}y++;x--; if(i==ylen/2)continue; for(;x>i;x--) {list.add(matrix[x][y]);}x++;y++; } return list; } }
20 包含main函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：
这题感觉这样要求返回栈中最小元素为O(1),那么说明需要有个常数min来维护这个最小值，可以直接返回。而这个min维护的时候只需要注意两点：
push加入的时候是不是更小，如果更小的话需要更新这个min。
pop元素是不是和min一样大。如果比min大不需要管。但是如果和min一样大那么就需要遍历重新确定min。当然整个函数的最大开销也就在这里了。
实现代码为：
import java.util.Stack; public class Solution { private int a[]=new int [1000]; private int index=0 ; private int min=Integer.MAX_VALUE; public void push(int node) { a[index]=node; if(a[index]<min)min=a[index]; index++; } public void pop() { if(a[--index]==min) { min=Integer.MAX_VALUE; for(int i=0;i<index;i++) { if(a[i]<min) { min=a[i]; } } } } public int top() { return a[index-1]; } public int min() { return min; } }
21 栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：
这题核心思想是模拟吧。给了压入序列看是不是弹出序列。我们假设这就是个弹出序列。然后根据这个弹出序列的顺序。将第一个数组的数据一个一个压入栈。当遇到在弹出序列当前位置的值时候就弹出。最终如果栈为空那么说明假设成立，如果不为空说明这个假设失败，就不是弹出序列。
实现代码为：
import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int[] pushA, int[] popA) { Stack<Integer> stack = new Stack<Integer>(); int index = 0; for (int i = 0; i < pushA.length; i++) {// 找到第一个push元素的位置 stack.push(pushA[i]); //while (!stack.isEmpty()) { while (!stack.isEmpty()&&stack.peek() == popA[index]) { stack.pop(); index++; //} //break; } } if (stack.size() == 0) return true; else { return false; } } }
22 从下往上打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：
用队列，就是二叉树的层序遍历。bfs的思想。
实现代码：
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Queue; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer>list=new ArrayList<Integer>(); if(root==null)return list; Queue<TreeNode>q1=new ArrayDeque<>(); q1.add(root); while (!q1.isEmpty()) { TreeNode node=q1.poll(); list.add(node.val); if(node.left!=null) {q1.add(node.left);} if(node.right!=null) {q1.add(node.right);} } return list; } }
23 二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
这个题和前面的前中确定构造二叉树那题思想很想。后序遍历顺序为左区域 右区域 根，其中每个节点的左区域肯定小于根，右区域全部大于根。同样里面的每个小区域也满足这个要求，再考虑一下边界和特殊情况，合理使用递归即可！
实现代码：
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if (sequence.length == 0) return false; return jud(sequence, 0, sequence.length - 1); } public boolean jud(int a[],int left,int right)//左右包含左和右 { int index=0;int mid=0; if(left>=right)return true; for(;index<right;index++) { if(a[index]>a[right]) break; } mid=index; for(;index<right;index++) { if(a[index]<a[right])break; } if(index!=right)return false; else { return jud(a, left, mid-1)&&jud(a, mid, right-1); } } }
24 二叉树中和为某一值的路径
题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
思路：
dfs深度优先遍历。要注意的是要遍历到叶子节点的路径。如果有中途遍历的时候路径满足而非叶子节点是不停止的。
dfs(TreeNode root, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> list2
而这样一个dfs函数target是个参数，每到达一个点会减去对应值。list是当前遍历的路径存储列表。而这个dfs是一个回溯的过程，list根据递归过程元素是不断变化的。所以这个list不能直接加到list2中。当遍历到根节点的时候满足条件要用新的list3复制list的值加入到list2中。如果对这个地方不理解请百度深度优先搜索或者回溯法 。 当然更多还需要自己理解的。
另外，要求路径中较长的路径在前面。这里我就实现了个Comparator排个序就行了。
实现代码为：
import java.util.ArrayList; import java.util.Comparator; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<Integer> team = new ArrayList<Integer>(); ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); if (root == null) { return list; } dfs(root, target, team, list); return list; } static Comparator<ArrayList<Integer>> comparator = new Comparator<ArrayList<Integer>>() { public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { // TODO Auto-generated method stub return o2.size() - o1.size(); } }; public void dfs(TreeNode root, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> list2) { if (target < 0) {// 停止 } else { list.add((Integer) root.val); target -= root.val; if (root.left != null) dfs(root.left, target, list, list2); if (root.right != null) dfs(root.right, target , list, list2); if (root.left==null&&root.right==null&&target == 0) {//叶子节点 ArrayList<Integer> list3 = new ArrayList<Integer>(); list3.addAll(list); list2.add(list3); } target+=root.val; list.remove((Integer) root.val); } } }
参考评论区
评论区看到有个递归写的非常好，比我的要精简很多，但是没有保证最短的在前面(需要自己排序一下，为了更好实现可以写个新函数代替这个只能在返回的函数中只需进行一次排序)。但是过了说明这个数据还是很水的。大家可以参考这个过程。
25 复杂链表的复制
题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路：
说实话，这题自己还卡了不少时间。刚开始一直没想到该怎么处理。后面经过自己不断思考终于克服了！——你虽然是链表，但我想怎么搞怎么搞(搞个数组)。
首先明确，他让我们克隆，也就是不能引用原链表的任何一个节点。也就是要100%的创造和克隆。大致分析思路如下：
- 它每个节点有一个next，有一个random。也就是一个指向后面，一个瞎指的。 如果两个指针同时考虑真的太复杂了，那我先分开考虑。只看next他就是一个链表。对吧(先不考虑循环)
- 我们用个RandomListNode list[]遍历链表将链表各个节点存进去。RandomListNode clone[]是我们想克隆的数组。至于克隆数组每个对应位子应该和list是相似的。并且每个next应该指向下一位clone[i].next=clone[i+1],至于每个random的位置。我们可以挨个遍历list中random的相对位置，然后clone的random也指向相应位置。这个是开销最大的部分，时间复杂度为O(n2).但是我自己没想到更好的方法，后面参考题解如果有更好方法会进行更新吧。
实现代码为：
/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ public class Solution { public RandomListNode Clone(RandomListNode pHead) { //step1 计算有多少个 int count=0; RandomListNode team=pHead; while(team!=null) {count++;team=team.next;if(team==pHead)break;}//先不考虑是否会是循环链表 //step2 将每个位置的指针存在 RandomListNode list[]=new RandomListNode[count+1]; RandomListNode clone[]=new RandomListNode[count+1]; team=pHead; count=0; while(team!=null) { clone[count]=new RandomListNode(team.label); list[count++]=team; team=team.next; if(team==pHead)break; } //step3 克隆指针 for(int i=0;i<count;i++) { clone[i].next=clone[i+1]; for(int j=0;j<count;j++) { if(list[i].random==list[j]) { clone[i].random=clone[j]; break; } } } return clone[0]; } }
参考讨论区：
这题在讨论区发现很多人再用的非常巧妙的效率很高的方法(谁是原创也不知道)。
实现代码为：
链接：https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba?f=discussion 来源：牛客网 /* *解题思路： *1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面； *2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next; *3、拆分链表，将链表拆分为原链表和复制后的链表 */ public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) { return null; } RandomListNode currentNode = pHead; //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面； while(currentNode != null){ RandomListNode cloneNode = new RandomListNode(currentNode.label); RandomListNode nextNode = currentNode.next; currentNode.next = cloneNode; cloneNode.next = nextNode; currentNode = nextNode; } currentNode = pHead; //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next; while(currentNode != null) { currentNode.next.random = currentNode.random==null?null:currentNode.random.next; currentNode = currentNode.next.next; } //3、拆分链表，将链表拆分为原链表和复制后的链表 currentNode = pHead; RandomListNode pCloneHead = pHead.next; while(currentNode != null) { RandomListNode cloneNode = currentNode.next; currentNode.next = cloneNode.next; cloneNode.next = cloneNode.next==null?null:cloneNode.next.next; currentNode = currentNode.next; } return pCloneHead; } }
