因为力扣没有剑指了，所以只能去牛客刷了，我草
PS：有的和力扣烧鸡100重复了，跳过
链表部分 public class Solution { ArrayList<Integer> list=new ArrayList<Integer>(); public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ListNode p=listNode; if(p!=null) { printListFromTailToHead(p.next); list.add(p.val); } return list; } }
一开始把list写函数里面了，大错特错
public ListNode ReverseList (ListNode head) { // write code here ListNode l=null; ListNode m=head; while(m!=null) { ListNode r=m.next; m.next=l; l=m; m=r; } return l; }
一开始return的m，后来发现m都null了，return锤子
这题比较简单，弱智思路一个一个比就行了，然后最后把剩下的全加上去
public ListNode Merge (ListNode pHead1, ListNode pHead2) { // write code here ListNode dummy=new ListNode(0); ListNode p=dummy; while(pHead1!=null&&pHead2!=null) { if(pHead1.val<=pHead2.val) { p.next=pHead1; pHead1=pHead1.next; }else { p.next=pHead2; pHead2=pHead2.next; } p=p.next; } while(pHead1!=null) { p.next=pHead1; p=p.next; pHead1=pHead1.next; } while(pHead2!=null) { p.next=pHead2; p=p.next; pHead2=pHead2.next; } return dummy.next; }
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1=pHead1;ListNode p2=pHead2; int lenp1=0; while(p1!=null) { p1=p1.next; lenp1++; } int lenp2=0; while(p2!=null) { p2=p2.next; lenp2++; } p1=pHead1;p2=pHead2; if(lenp1>lenp2) { int k=lenp1-lenp2; while(k>0) { p1=p1.next; k--; } }else { int k=lenp2-lenp1; while(k>0) { p2=p2.next; k--; } } while(p1!=p2) { p1=p1.next; p2=p2.next; } return p1; }
长的先走
public ListNode FindKthToTail (ListNode pHead, int k) { // write code here if(pHead==null)return null; ListNode p=pHead; ListNode q=pHead; int len=0; ListNode m=pHead; while(m!=null) { len++; m=m.next; } if(len<k)return null; while(k>0) { q=q.next; k--; } while(q!=null) { q=q.next; p=p.next; } return p; }
老生常谈的题目了，注意pHead为空的情况
反正有个公式，背吧懒得推导
总的来说就是
1.先判断与有无环，套路
2.把fast放到head结点，和slow一起一个一个走，相遇为入口节点
为什么呢，不知道
public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead==null) return null; ListNode slow=pHead; ListNode fast=pHead; while(fast!=null&&fast.next!=null) { fast=fast.next.next; slow=slow.next; if(slow==fast) break; } if(fast==null||fast.next==null)return null; fast=pHead; // 与第一次相遇的结点相同速度出发，相遇结点为入口结点 while(fast!=slow) { fast=fast.next; slow=slow.next; } return fast; }
public ListNode deleteNode (ListNode head, int val) { // write code here if(head==null)return null; ListNode p=head; if(p.val==val) { return head.next; } while(p.next!=null) { if(p.next.val==val)//注意，这里直接把p当pre用就行了，也就是说判断P.next是不是val即可 { ListNode q=p.next; p.next=q.next; q.next=null; return head; } p=p.next; } return null; }
注意第一个节点
public ListNode deleteDuplication(ListNode head) { ListNode dummy=new ListNode(-1); ListNode tail=dummy; while(head!=null) { if(head.next==null||head.next.val!=head.val) { tail.next=head; tail=head; } while(head.next!=null&&head.next.val==head.val)head=head.next; head=head.next; } tail.next=null; //这一步至关重要，比如12233455,如果最后不断掉，那么会返回1455 return dummy.next; }
我一开始的傻逼想法：用set，false了就删掉，后来发现这样能保留第一个重复的节点，我是傻逼
树 经典递归，反正等于子树高度加一
public int TreeDepth(TreeNode root) { if(root==null)return 0;//这一句一写还用考虑left,right=null吗？ else return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1; }
注意点：
1.如何判断一层：队列size
2.如何实现”之“，直接用Collections.reverse()，就不用麻烦的后端插入Arraylist和前端插入Arraylist了
public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) { // 思路：双端队列，奇数层翻转（从0开始），偶数层不翻转 ArrayList<ArrayList<Integer>> res=new ArrayList<>(); if(pRoot==null)return res; Deque <TreeNode>dq=new LinkedList<TreeNode>(); boolean flag=true; dq.offer(pRoot); while(!dq.isEmpty()) { ArrayList<Integer> aa=new ArrayList<>(); int n=dq.size();//这一层有多少node flag=!flag; for(int i=0;i<n;i++) { TreeNode p=dq.pollFirst(); aa.add(p.val); if(p.left!=null) dq.offer(p.left); if(p.right!=null) dq.offer(p.right); } if(flag) { Collections.reverse(aa); } res.add(aa); } return res; }
ArrayList<Integer>res=new ArrayList<>(); public int KthNode (TreeNode proot, int k) { if(proot==null||k==0)return -1;//空，或者没k mid(proot);//中序遍历获得升序数组 if(k>res.size())return -1;//没这么多node return res.get(k-1); } public void mid(TreeNode root) { if(root==null)return; mid(root.left); res.add(root.val); mid(root.right); }
知识点：二叉搜索树中序遍历为升序序列
这题力扣烧鸡100也有，之前就稀里糊涂过去了
额其实842期末也有，但当时也是稀里糊涂过去了
注意点放注释里了
这个是力扣是上我写的，傻逼牛客有问题，算了
public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTreeHelper(preorder,0,preorder.length,inorder,0,inorder.length); } public TreeNode buildTreeHelper(int[]preorder,int pstart,int pend,int []inorder,int istart,int iend) { //pstart:前序数组中左子树的开头，pend:前序数组中左子树的结束,左闭右开 //istart:终须数组中左子树的开头,iend:终须数组中左子树的结束，左闭右开 if(pstart==pend) return null; int root_val=preorder[pstart];//前序数组第一个为更节点 TreeNode root=new TreeNode(root_val); int iroot_index=0;//中序遍历中根节点的位置 for(int i=istart;i<iend;i++) { if(root_val==inorder[i]) { iroot_index=i; break; } } int lefnum=iroot_index-istart;//左子树的长度，等于中序遍历中，根节点的位置减去开头 root.left=buildTreeHelper(preorder,pstart+1,pstart+lefnum+1,inorder,istart,iroot_index); root.right=buildTreeHelper(preorder,pstart+lefnum+1,pend,inorder,iroot_index+1,iend); return root; }
这题目很好，思路是什么
1.b是子结构，那么b的左右子树也就是a的左右子树的子结构
2.所以怎么办，递归的从a中寻找b的根节点看能不能找到，能找到那么则比较其左右子树是不是子结构即可
public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { //思路:递归，root2是子哦结构，那么root2的左右子树也都是子结构 //所以我们先找roo1和root2相等的，然后找root1的左右子树有没有 //返回条件是什么？有空 return (root1!=null&&root2!=null)&&(recur(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2)); } //详解：因为要判断b是不是a的，所以b肯定比a小 //所以这里比较子结构，其实就是一个一个去比较值等不等，等的话就再去递归判断他的左右子树上节点等不等 //这里是比较两个部分是不是对应的子结构 public boolean recur(TreeNode a,TreeNode b) { if(b==null)return true;//说明b已经比较完了，下面没了，那么说明是真 if(a==null||a.val!=b.val)return false;//如果a为空，也就是说a不够长了，或者值不相等，那么肯定不是 return recur(a.left,b.left)&&recur(a.right,b.right); } }
这题就是普通递归交换左右子树，但是牛客这个有点傻逼，非要我return一个什么东西
我return牛魔
public TreeNode Mirror (TreeNode root) { TreeNode p=root; if(root == null) { return null; } if(root.left == null && root.right == null) { return root; } TreeNode temp = root.left; root.left = root.right;//这样把整个子树也都交换过去了 root.right = temp; Mirror(root.left); Mirror(root.right); return p; }
byd这牛客给这个例子我都没看明白
这不就是层序遍历么？
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer>res=new ArrayList<>(); if(root==null) return res; Queue<TreeNode>q=new ArrayDeque<>(); q.offer(root); while(!q.isEmpty()) { TreeNode cur=q.poll(); res.add(cur.val); if(cur.left!=null) q.offer(cur.left); if(cur.right!=null) q.offer(cur.right); } return res; }
这题很容易想到分治法，但我还是不熟悉用helper
and终止条件没把握，我是傻逼
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length==0)return false; return recur(sequence,0,sequence.length-1); } public boolean recur(int []sequence,int i,int j) { if(i>=j)return true;//i>=j说明此子树结点数<=1，不用判断了 int p=i; while(sequence[p]<sequence[j])p++;//sequence[len-1]为root int m=p;//m为第一个大于root值的位置，讲sequece分割为左右子树了[i,m-1] while(sequence[p]>sequence[j])p++; //此时p为第一个小于root值的位置，分割为[m,p] //按理来说，p应该等于j，因为小于sequence[j]的都应该在左子树当中 //如果不等于，说明错了 return (p==j)&&recur(sequence,i,m-1)&&recur(sequence,m,j-1); } }
我卡在哪里了：在想如果超过了怎么把前面的吐出来
解决办法：不用吐出来，没遍历到一个，tmpsum加p.val，然后比较即可
wait，此题定义路径为根节点到叶子结点，那么更不不需要讨论吐出来。。。我是傻逼
用加的，不用减的，超过了和没超过一样的，反正都是不等于
public class Solution { private static int sumVal=-1; private boolean flag=false; public boolean hasPathSum (TreeNode root, int sum) { sumVal=sum; // write code here dfs(root,0); return flag; } public void dfs(TreeNode p, int tmpsum) { if(p==null)return; if(p.left!=null) { dfs(p.left,tmpsum+p.val); } if(p.left==null&&p.right==null) { boolean tmpflag=tmpsum+p.val==sumVal; flag=flag||tmpflag;//防止别的路径已经找到了，但是被新的false覆盖 } if(p.right!=null) { dfs(p.right,tmpsum+p.val); } } }
这题又让我练了一下回溯法
import java.util.*; public class Solution { //回溯法+二叉树题目 //回溯法不知道几部了，反正就是定义回溯函数，然侯加入，然后回调 public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); ArrayList<Integer> path=new ArrayList<>(); if(root==null)return res; preorderdfs(root,target,res,path);//定义函数 return res; } public void preorderdfs(TreeNode root,int targetsum,ArrayList<ArrayList<Integer>> res,ArrayList<Integer> path) { path.add(root.val);//加入 if(root.left==null&&root.right==null) { if(targetsum-root.val==0) { res.add(new ArrayList<>(path));//这里一定要这么写，为什么我不知道 } return;/* 为什么这里不remove呢，因为我们remove的操作实在回溯了之后的那个语句做的，发现没有 终止条件：找到叶子结点了，但是和不是target，终止 */ } if(root.left!=null) { preorderdfs(root.left,targetsum-root.val,res,path); path.remove(path.size()-1);//回溯 } if(root.right!=null) { preorderdfs(root.right,targetsum-root.val,res,path); path.remove(path.size()-1);//回溯 } } }
我妄想用一个指正解决问题，那不可能
public TreeNode head = null; //中序遍历当前值的上一位，初值为最小值，先定为null public TreeNode pre = null; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) //中序递归，叶子为空则返回 return null; //首先递归到最左最小值 Convert(pRootOfTree.left); //找到最小值，初始化head与pre if(pre == null){ head = pRootOfTree; pre = pRootOfTree; } //当前节点与上一节点建立连接，将pre设置为当前值 else{ pre.right = pRootOfTree; pRootOfTree.left = pre; pre = pRootOfTree; } Convert(pRootOfTree.right); return head; }
此题很简单吗，先递归求高度，然后递归求是不是平衡
public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pRoot TreeNode类 * @return bool布尔型 */ public boolean IsBalanced_Solution (TreeNode pRoot) { // write code here if(pRoot==null) return true; int leftdeep=deep(pRoot.left); int rightdeep=deep(pRoot.right); if(leftdeep-rightdeep>1||leftdeep-rightdeep<-1) return false; return IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right); } public int deep(TreeNode root) { if(root==null) return 0; return Math.max(deep(root.left),deep(root.right))+1; } }
分情况讨论：
如果给出的结点有右子节点，则最终要返回的下一个结点即右子树的最左下的结点
如果给出的结点无右子节点，且当前结点是其父节点的左子节点，则返回其父节点
如果给出的结点无右子节点，且当前结点是其父节点的右子节点，则先要沿着左上方父节点爬树，一直爬到当前结点是其父节点的左子节点为止，返回的就是这个父节点；或者没有满足上述情况的则返回为NULL
public TreeLinkNode GetNext(TreeLinkNode node) { if(node.right!=null) { TreeLinkNode p=node.right; while(p.left!=null) { p=p.left; } return p; } if(node.next!=null&&node.next.left==node) { return node.next; } if(node.next!=null) { TreeLinkNode p=node.next; while(p.next!=null&&p.next.right==p)p=p.next; return p.next; } return null; }
我的一个误区：最小元比较时还在判断left和right，然而只要比较值是不是相等就行了
public class Solution { public boolean isSymmetrical (TreeNode pRoot) { if(pRoot==null)return true; // write code here return Helper(pRoot.left,pRoot.right); } public boolean Helper(TreeNode r1,TreeNode r2) { if(r1==null&&r2==null)return true; if(r1==null||r2==null||r1.val!=r2.val)//就是这里，直接比较值就行了，不要比较left.val什么的 { return false; } return Helper(r1.left,r2.right)&&Helper(r1.right,r2.left); } }
和“之字型打印“是一个道理
只要记住：判断是否已经一行，int n=dq.size()即可
public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) { // write code here Deque<TreeNode> dq=new LinkedList<TreeNode>(); ArrayList<ArrayList<Integer>>res=new ArrayList<>(); if(pRoot==null)return res; dq.offer(pRoot); while(!dq.isEmpty()) { ArrayList<Integer>ans=new ArrayList<>(); int n=dq.size(); for(int i=0;i<n;i++) { TreeNode p=dq.pollFirst(); ans.add(p.val); if(p.left!=null) dq.offer(p.left); if(p.right!=null) dq.offer(p.right); } res.add(new ArrayList<>(ans)); } return res; }
此题很重要，建议每次做都看一下力扣的解答
栈 没什么高级的，就是pop时把一个栈全pop到另一个栈里，在pop。。。
public: void push(int node) { stack1.push(node); } int pop() { while(!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } int res=stack2.top(); stack2.pop(); while(!stack2.empty()) { stack1.push(stack2.top()); stack2.pop(); } return res; } private: stack<int> stack1; stack<int> stack2;
这一题解法的原理是什么？
如果压入和弹出序列是符合的，那么按照这个序列走，一定能走完
所以你只要按照给的顺序走一遍就行了
public boolean IsPopOrder (int[] pushV, int[] popV) { // write code here int n=pushV.length; Stack<Integer>s=new Stack<>(); int j=0; for(int i=0;i<n;i++) { while(j<n&&(s.isEmpty()||s.peek()!=popV[i])) { s.push(pushV[j]); j++; } if(s.peek()==popV[i]) { s.pop(); }else return false; } return true; }
熟悉javaapi用的
public String ReverseSentence(String str) { String []arr=str.split(" "); Stack<String>stk=new Stack<String>(); for(String s:arr) { stk.push(s); } StringBuilder res=new StringBuilder(); while(!stk.isEmpty()){ res.append(stk.pop()); res.append(" "); } return res.toString().substring(0,res.toString().length()-1); }
用优先队列，注意如何创建最大堆
public ArrayList<Integer> maxInWindows (int[] num, int size) { // write code here ArrayList<Integer> res=new ArrayList<>(); if(num.length==0||size==0||num.length<size)return res; PriorityQueue<Integer>pq=new PriorityQueue<>((o1,o2)->o2-o1); for(int i=0;i<size;i++)pq.add(num[i]); res.add(pq.peek()); for(int i=1;i+size-1<num.length;i++) { pq.remove(num[i-1]); pq.add(num[i+size-1]); res.add(pq.peek()); } return res; }
搜索算法部分 private int bisearch(int[] data, double k){ int left = 0; int right = data.length - 1; //二分左右界 while(left <= right){ int mid = (left + right) / 2; if(data[mid] < k) left = mid + 1; else if(data[mid] > k) right = mid - 1; } return left; } public int GetNumberOfK(int [] array , int k) { //分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k return bisearch(array, k + 0.5) - bisearch(array, k - 0.5); }
一眼二分，但是我一开始想说递归二分，然后发现只要求左右边界就行了
思路二：直接求左右边界
import java.util.*; public class Solution { //思路：二分找左边界，二分找有边界，然后相减即可 public int GetNumberOfK (int[] nums, int k) { int a=getLeft(nums,k); int b=getRight(nums,k); return b-a-1; } public int getLeft(int []nums,int k) { int l=0,r=nums.length-1;//左臂右臂 while(l<=r) { int mid=(l+r)/2; if(nums[mid]<k) { l=mid+1; } else { r=mid-1; } } return r; } public int getRight(int []nums, int k) { int l=0,r=nums.length-1; while(l<=r) { int mid=(l+r)/2; if(nums[mid]>k) { r=mid-1; }else { l=mid+1; } } return l; } }
这题和力扣上还不同，这题剑指有相同值，力扣没有
所以这一题，剑指offer的方法更有通用性，掌握这个
public int minNumberInRotateArray (int[] nums) { //思路：旋转后的数组分为两个部分，也就是两个升序序列 //我们要找的值其实就是第二段升序序列的第一个数 //我们找到mid，然后和nums[j]比较，如果小于他，那么nums[mid]就在第二段序列里 //如果大于他，那么就在第一段序列里，那么更新left //如果小于他那么就在第二段 序列里面，更新right int l=0,r=nums.length-1; while(l<r)//左闭右开 { int m=(l+r)/2; if(nums[m]>nums[r]) { l=m+1;//左边闭区间，所以必须+1 }else if(nums[m]<nums[r]) { r=m;//右边开区间，所以不用 }else { r--; } } return nums[l]; }
注意事项在注释里面
public boolean Find (int target, int[][] array) { // write code here int i=0,j=array[0].length-1; while(i<array.length&&j>=0) { if(target>array[i][j]) { i++; } else if(target<array[i][j]) { j--; } else { return true; } } return false; }
思路啊，三种方法：
两层遍历
对每个子数组用二分
这种方法，鉴定为观察能力极强
这个题目要注意的是：字符串里有重复字符，abb’与ab’b，bab’与b’ab，bb’a与b’ba都是重复的，难点在于去除这些重复
由此为了去重，我们可以定义一个规则，即对于相同数，我们人为定序，如上例子中11'2345,我们指定重复数字首次要放入某一个框位时，只能放重复数字的第一个，如这里只能放1，放1'的情况直接过滤，其他框位同理
具体做法：
step 1：先对字符串按照字典序排序，获取第一个排列情况。
step 2：准备一个空串暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了。
step 3：每次递归从头遍历字符串，获取字符加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用，也不需要将其纳入。
step 4：进入下一层递归前将vis数组当前位置标记为使用过。
step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入字符串的元素，
step 6：临时字符串长度到达原串长度就是一种排列情况。
import java.util.*; public class Solution { public ArrayList<String> Permutation (String str) { // write code here ArrayList<String>res=new ArrayList<>(); char[]charStr=str.toCharArray(); Arrays.sort(charStr); boolean[]visit=new boolean[charStr.length]; StringBuffer temp=new StringBuffer(); back(res,charStr,temp,visit); return res; } public void back(ArrayList<String>res,char[]str,StringBuffer temp,boolean[]visit) { if(temp.length()==str.length) { res.add(new String(temp)); return; } for(int i=0;i<str.length;i++) { if(visit[i]) { continue;//这个元素用过了，跳过 } if(i>0&&str[i-1]==str[i]&&!visit[i-1])//这里表示的是回溯过来的，1 1' 2 3 从1’开始取的情况，这个时候因为回溯了，所以1的visit的false，但是1' 与1会重复，所以不能取 { continue; } visit[i]=true; temp.append(str[i]); back(res,str,temp,visit); visit[i]=false; temp.deleteCharAt(temp.length()-1); } } }
这题有一说一，规律太难找，只能反复刷记住了
public int findKthNumber(int k) { //k是整个序列中的位置 int digit=1;//位数，一位数二位数这种 long start=1;//每位数的起始数字，就是1,10,100,1000 long count=9;//每种位数的数，各占多少位置,个位数9位，十位数180位 //首先k所在的数字是几位数,一直减掉1、2、3.。。。位数的数量即可 while(k>count) { k-=count; start*=10; digit+=1; count=9*start*digit; } //减完之后，最后剩下的k其实就是，第k个digit位数(从 0开始) //然后获得，k所在的是哪一个数字 long num=start+(k-1)/digit;//因为序列从第“0”个数字开始,start是n位数的第一个，也就是10,100,1000.。。然后k-1/digit相当于偏移量 //确定他是哪一位 String s=Long.toString(num); int res=s.charAt((k-1)%digit)-'0'; return res; }
动态规划 记住杀卡尔的动态规划五部曲
public int FindGreatestSumOfSubArray (int[] array) { // write code here int []dp=new int[array.length]; dp[0]=array[0]; for(int i=1;i<array.length;i++) { dp[i]=Math.max(dp[i-1]+array[i],array[i]); } int res=Integer.MIN_VALUE; for(int i=0;i<dp.length;i++) { res=Math.max(res,dp[i]); } return res; }
思路其实就是维护left和right，因为要返回最长的，所以还得维护maxleft,maxright
public int[] FindGreatestSumOfSubArray (int[] array) { // write code here int len = array.length; int []dp = new int[len]; ArrayList<Integer>list = new ArrayList<>(); dp[0] = array[0]; int left = 0, right = 0; int maxleft = 0, maxright = 0; int maxsum = dp[0];//注意此处初始化 for (int i = 1; i < len; i++) { right++; dp[i] = Math.max(dp[i - 1] + array[i], array[i]); if (dp[i - 1] + array[i] < array[i]) { left = right; //重置了 } //遇到新的最大值了 if (dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (maxright - maxleft + 1)) { //因为要返回最长的 maxsum = dp[i]; maxleft = left; maxright = right; } } int []res = new int[maxright - maxleft + 1]; for(int i=maxleft,j=0;i<=maxright;i++,j++) { res[j]=array[i]; } return res; }
public int Fibonacci (int n) { // write code here int []dp=new int [n+1]; dp[1]=1; dp[2]=1; for(int i=3;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }
比较简单，和机器人走路是一个套路
public int maxValue (int[][] grid) { // write code here int m=grid.length; int n=grid[0].length; int [][]dp=new int[m][n]; dp[0][0]=grid[0][0]; for(int i=1;i<n;i++) { dp[0][i]=dp[0][i-1]+grid[0][i]; } for(int j=1;j<m;j++) { dp[j][0]=dp[j-1][0]+grid[j][0]; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[m-1][n-1]; }
说是动态规划，但我一开始用的暴力
public int lengthOfLongestSubstring (String s) { // write code here int left=0,right=1; if(s.length()==0)return 0; if(s.length()==1)return 1; int maxlen=0; while(right<s.length()) { if(hassame(s.substring(left,right+1))) { left++; }else { maxlen=Math.max(maxlen,right-left+1); right++; } } return maxlen; } public boolean hassame(String s) { Set<Character>set=new HashSet<Character>(); for(int i=0;i<s.length();i++) { if(!set.add(s.charAt(i))) { return true; } } return false; }
后来我自己写的动态规划
public int lengthOfLongestSubstring (String s) { // write code here //思路：好像和最大子数组和差不多？ //dp[i]:以i结尾的最长不包含重复字符的子串长度 //dp[i]=dp[i-1]+1,当s.charat(i)不和前面的重复 //否则dp[i]=1 //如何判断充不重复呢 int len=s.length(); int[]dp=new int[len]; dp[0]=1; int left=0,right=0; int maxleft=0,maxright=0; int maxlen=1; for(int i=1;i<len;i++) { right++; char c=s.charAt(i); if(s.substring(left,right).indexOf(c)>=0) { dp[i]=1; left=right; }else { dp[i]=dp[i-1]+1; if(right-left+1>maxlen) { maxlen=right-left+1; maxleft=left; maxright=right; } } } return maxlen; }
又错了，发现错哪了吗
更新left的时候，我们应该更新到重复元素的第一个个左边，而不是直接更新到right
修改：
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int lengthOfLongestSubstring (String s) { // write code here //思路：好像和最大子数组和差不多？ //dp[i]:以i结尾的最长不包含重复字符的子串长度 //dp[i]=dp[i-1]+1,当s.charat(i)不和前面的重复 //否则dp[i]=1 //如何判断充不重复呢 int len=s.length(); int[]dp=new int[len]; dp[0]=1; int left=0,right=0; int maxleft=0,maxright=0; int maxlen=1; for(int i=1;i<len;i++) { right++; char c=s.charAt(i); int index=s.indexOf(c,left); if(index>=left&&index<right)//修改部分 { dp[i]=1; left=index+1; }else { dp[i]=dp[i-1]+1; if(right-left+1>maxlen) { maxlen=right-left+1; maxleft=left; maxright=right; } } } return maxlen; } }
力扣上给了我们滑动窗口的方法
public int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<>(); int maxLen = 0;//用于记录最大不重复子串的长度 int left = 0;//滑动窗口左指针 for (int i = 0; i < s.length() ; i++) { /** 1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）, 此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值； 2、如果当前字符 ch 包含在 map中，此时有2类情况： 1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a， 那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca； 2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b， 而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0； 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时 应该不变，left始终为2，子段变成 ba才对。 为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1). 另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i， 因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！ */ if(map.containsKey(s.charAt(i))) { left = Math.max(left , map.get(s.charAt(i))+1); } //不管是否更新left，都要更新 s.charAt(i) 的位置！ map.put(s.charAt(i) , i); maxLen = Math.max(maxLen , i-left+1); } return maxLen; }
其实这个方法就是用i,代替了right
public int solve (String nums) { if(nums.length()==0||nums.charAt(0)=='0') return 0; int []dp=new int[nums.length()]; dp[0]=1; for(int i=1;i<dp.length;i++) { if(nums.charAt(i)!='0') { dp[i]=dp[i-1];//先默认都一样 } int num=(nums.charAt(i-1)-'0')*10+(nums.charAt(i)-'0');//计算自己和前一个平起来的两位数 if(num>=10&&num<=26) { //如果在范围内可以表示 if(i==1) dp[i]+=1; else dp[i]+=dp[i-2]; } } return dp[nums.length()-1]; }
有条件的青蛙跳台阶问题，需要判断i-1和i组成的二位数是否可以表示，这里的关键在于如何处理“0
这题目太他妈难了，面试之前突击一下吧
public boolean isMatch(String s, String p) { //dp[i][j],s0 i-1，是否匹配p 0 ,j-1这样方便初始化 //这题也太他妈难了 if(s==null||p==null)return false; int slen=s.length(),plen=p.length(); boolean[][]dp=new boolean[slen+1][plen+1]; dp[0][0]=true; for(int j=1;j<plen+1;j++) { if(p.charAt(j-1)=='*')dp[0][j]=dp[0][j-2];//s是空串，如果j-1的位置是*,那么就把j-2删掉，再比较前面的 } for(int i=1;i<slen+1;i++) { for(int j=1;j<plen+1;j++) { if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.')//如果相等或者j是点，因为点可以任意匹配， { dp[i][j]=dp[i-1][j-1]; }else if(p.charAt(j-1)=='*')//如果是*，那么得看i-1和j-2匹不匹配 { if(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.') { dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-1][j]; }else{ dp[i][j]=dp[i][j-2]; } } } } return dp[slen][plen]; }
排序算法 public int duplicate (int[] numbers) { // write code here HashSet<Integer>set=new HashSet<Integer>(); for(int i=0;i<numbers.length;i++) { if(!set.add(numbers[i])) { return numbers[i]; } } return -1; }
用set，鉴定为易
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { // write code here ArrayList<Integer>list=new ArrayList<Integer>(); Arrays.sort(input); for(int i=0;i<k;i++) { list.add(input[i]); } return list; }
· 以上 为弱智解法
public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型ArrayList */ public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) { ArrayList<Integer> res = new ArrayList<>(k); //根据题意要求，如果K>数组的长度，返回一个空的数组 if (k > input.length || k == 0) return res; quickSort(input, res, k, 0, input.length - 1); return res; } private void quickSort(int[] input, ArrayList<Integer> res, int k, int left, int right) { //快排的实现方式有多种，我们选择了其中的一种 int start = left; int end = right; while (left < right) { while (left < right && input[right] >= input[start]) { right--; } while (left < right && input[left] <= input[start]) { left++; } swap(input, left, right); } swap(input, left, start); //注意这里，start是数组中元素的下标。在start之前的元素都是比start指向的元素小， //后面的都是比他大。如果k==start，正好start之前的k个元素是我们要找的，也就是 //数组中最小的k个，如果k>start，说明前k个元素不够，我们还要往后再找找。如果 //k<start，说明前k个足够了，我们只需要在start之前找k个即可。 if (left > k) { quickSort(input, res, k, start, left - 1); } else if (left < k) { quickSort(input, res, k, left + 1, end); } else { //取前面的k个即可 for (int m = 0; m < k; ++m) { res.add(input[m]); } } } private void swap(int[] arr, int i, int j) { if (i == j) return; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
· 快排，一次排序可以确认pivot在排序后的数组里的位置，只要比较这个位置和k即可
然而还有更好的方法，那就是堆排序
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { // write code here PriorityQueue<Integer>pq=new PriorityQueue<>();//默认创建是小顶堆 for(int i=0;i<input.length;i++) { pq.add(input[i]); } ArrayList<Integer>res=new ArrayList<>(); while(k>0) { res.add(pq.peek()); pq.poll(); k--; } return res; }
弱智方法一：
冒泡排序，记录总共交换了多少次
经典最后一个用例超时
public int InversePairs (int[] nums) { // write code here int res=0; for(int i=0;i<nums.length-1;i++) { for(int j=0;j<nums.length-i-1;j++) { if(nums[j]>nums[j+1]) { swap(nums,j,j+1); res++; } } } return res; } public void swap(int nums[],int i,int j) { int t=nums[i]; nums[i]=nums[j]; nums[j]=t; }
归并排序法：归并排序爷还不熟，后面继续熟悉
class Solution { int count=0; public int reversePairs(int[] nums) { this.count=0; mergeSort(nums,0,nums.length-1); return count; } public void mergeSort(int []nums,int left,int right) { if(left>=right)return ; int mid=(left+right)/2; mergeSort(nums,left,mid); mergeSort(nums,mid+1,right); merge(nums,left,mid,right); } public void merge(int []nums,int left,int mid,int right) { int []tmp=new int[right-left+1]; int i=left; int j=mid+1; int t=0; while(i<=mid&&j<=right) { if(nums[i]<=nums[j]) { tmp[t++]=nums[i++]; }else { count+=mid-i+1; tmp[t++]=nums[j++]; } } while(i<=mid) tmp[t++]=nums[i++]; while(j<=right) tmp[t++]=nums[j++]; for(int k=0;k<tmp.length;k++) nums[left+k]=tmp[k]; } }
这个思路很无敌，一个最小堆一个最大堆，那么两个的头就是中间的元素
public class Solution { PriorityQueue<Integer> max=new PriorityQueue<>();//保存较大的一般 PriorityQueue<Integer> min=new PriorityQueue<>((o1,o2)->o2.compareTo(o1)); //保存较小的一半 public void Insert(Integer num) { min.offer(num);//先进较小的一半 max.offer(min.poll());//然后把较小的里面最大的弄到较大的一半里面 //因为java里/2是四舍五入的，所以要保证较小的一半比较大的一半不少 if(min.size()<max.size()) min.offer(max.poll()); } public Double GetMedian() { if(min.size()>max.size())//大，说明是奇数个 { return(double) min.peek(); } else//相等，说明是偶数个 { return (double)(min.peek()+max.peek())/2; } }
位运算部分 傻逼位运算是最恶心的题目，我操你妈
思路：快速幂方法
计算x64,可以直接，x,x2,x4,x8….
计算x77,可以直接x,x2,x4…..x76,最后再乘x得到x77
但是你从左往右你怎么知道要不要乘x呢
所以我们倒过来求，对于x(a),我们求x(a/2) =yjava中是向下取整
要是a为偶数，xa=y2,要是是奇数，xa=y2*x
即可
//为了防止坑爹用力，把n变成long public class Solution { public double Power(double x, int n) { long N =n; return N>=0?quick(x,N):1.0/quick(x,-N); } public double quick(double x, long n) { if(n==0)return 1.0; double y=quick(x,n/2); return n%2==0?y*y:y*y*x; } }
方法一：没说不能用递归啊，那我们可以直接递归
public int Sum_Solution(int n) { return n==0?0:Sum_Solution(n-1)+n; }
记住：有一个性质：n&(n-1)可以消除二进制表示的n中最后的一个1 ，反正你记住就行了
public int NumberOf1 (int n) { // write code here int res=0; while(n!=0) { res+=1; n=n&(n-1);//不断这样，直到n里1全没了，那就是n变成0了 } return res; }
首先题目对空间复杂度有要求，所以不能用哈希表
我们知道，数组中只出现一次的一个数字，可以直接将数组里所有的数异或（^) 利用异或同0异1的性质求出来
但是此处是两个数字，怎么办呢
知识点：x&-x可以取出二进制x中最低位的那个1
那么我们要把数字分为两类
如果我们任然将所有的数字都异或，得到一个x，那么他就是只出现一次的两个数字x1与x2的异或
然后我们将x&-x，得到它最低位的那个1,我们假设这一位是k位
因为是二进制，所以所有数的k位只有两种可能，1或者0
这样把所有的数分成了两类，一类是k位是0，一类是k位是1
因为除了x1,x2 其他都出现了两次
所以出现了两次的数，会被分在同一类中，而因为x1异或x2，也就是x第k位是1，所以x1和X2的第k位必然不同
所以x1与x2会被分为不同的类当中
public int[] FindNumsAppearOnce (int[] nums) { // write code here int xorsum=0; for(int num:nums) { xorsum^=num; } int lsb=(xorsum==Integer.MIN_VALUE?xorsum:xorsum&(-xorsum));//xorsum是-2147483648的时候变为正数会溢出，因为32位的int正数范围是0~2147483647,而为什么是min.value时，直接返回xorsum呢，因为-2147483638二进制是1000000000，最低位的1其实就是她自己 int t1=0,t2=0; for(int num:nums) { if((lsb&num)!=0) { t1^=num; }else { t2^=num; } } if(t1>t2) { return new int[]{t2,t1}; } return new int[]{t1,t2}; }
其他算法部分 此题思路也无敌，但我没看懂，二刷的时候再看看吧
public int[] multiply (int[] A) { // write code here int[]B=new int[A.length]; B[0]=1; for(int i=1;i<A.length;i++) B[i]=B[i-1]*A[i-1]; int temp=1; for(int i=A.length-1;i>=0;i--) { B[i]*=temp; temp*=A[i]; } return B; }
考察方法的
public int FirstNotRepeatingChar (String str) { // write code here for(int i=0;i<str.length();i++) { if(str.lastIndexOf(str.charAt(i))==i&&str.indexOf(str.charAt(i))==i) { return i; } } return -1; }
这题目南软有一种快速排序的方法，但我我忘了
方法一：就是建新数组
public int[] reOrderArray (int[] array) { // write code here int n=array.length; int []res=new int[n]; int odd=0; for(int i=0;i<n;i++) { if(array[i]%2==1) odd++; } int x=0,y=odd; for(int i=0;i<n;i++) { if(array[i]%2==1) { res[x]=array[i]; x++; } else { res[y]=array[i]; y++; } } return res; }
方法二：原地排序，先鸽了
思路：对于string类型，a+b>b+a的话，那么就排序
public String PrintMinNumber (int[] numbers) { // write code here if(numbers==null||numbers.length==0) return ""; String[]nums=new String[numbers.length]; for(int i=0;i<numbers.length;i++) nums[i]=numbers[i]+""; Arrays.sort(nums,new Comparator<String>(){//重写compare函数 public int compare(String s1,String s2){ return (s1+s2).compareTo((s2+s1));//规则是：返回值大于0则交换 //String.compareto:如果左大于右，则返回大于0的值 //跟这里需求是一样的，把大的换到后面 } }); StringBuilder res=new StringBuilder(); for(int i=0;i<nums.length;i++) res.append(nums[i]); return res.toString(); }
我的评价：看k神的题解，背下来
public int countDigitOne(int n) { int digit=1,res=0; int high=n/10,cur=n%10,low=0; while(high!=0||cur!=0) { if(cur==0)res+=high*digit; else if(cur==1)res+=high*digit+low+1; else res+=(high+1)*digit; low+=cur*digit; cur=high%10; high/=10; digit*=10; } return res; }
滑动窗口法，简直是天才
public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) { // write code here //滑动窗口法，大了就左边出去，小了就右边进来 ArrayList<ArrayList<Integer>> res=new ArrayList<>(); int low=1,high=2; while(low<high) { int cur=(high+low)*(high-low+1)/2;//计算和 if(cur==sum) { ArrayList<Integer> list=new ArrayList<>(); for(int i=low;i<=high;i++) { list.add(i); } res.add(list); low++; } else if(cur<sum) { high++; } else { low++; } } return res; }
我的误区：还是l=0，r=1去滑动窗口，但是这样不对
应该r=最末尾的地方，这样可以避免什么，避免你们从同一侧向右，然后r++，而l又要从0开始遍历，那不就相当于两层for了吗
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<Integer>(); //左右双指针 int left = 0, right = array.length - 1; //对撞双指针 while(left < right){ //相加等于sum，找到目标 if(array[left] + array[right] == sum){ res.add(array[left]); res.add(array[right]); break; //和太大，缩小右边 }else if(array[left] + array[right] > sum) right--; //和太小，扩大左边 else left++; } return res; }
public int[] printNumbers (int n) { // write code here int size=1; while(n>0) { size=size*10; n--; } int[]res=new int[size-1]; for(int i=1;i<size;i++) { res[i-1]=i; } return res; }
暴力，没啥可说的
思路：所以我们就将res[i]去乘以 2、3、5，然后比较出最小的那个，就是我们当前的下一个丑数了。
但是前面有那么多数，如何比较呢，维护i2,i3,i5
public int GetUglyNumber_Solution (int index) { // write code here if(index<=6)return index; int i2=0,i3=0,i5=0;//从1开始，每个丑数都需要乘一次2,3,5 //i2,i3,i5代表的就是从1开始，每个丑数乘2,3,5 int[] res=new int[index]; res[0]=1;//1是第一个丑数 for(int i=1;i<index;i++) { res[i]=Math.min(res[i2]*2,Math.min(res[i3]*3,res[i5]*5)); if(res[i]==res[i2]*2)//如果这一次被选择的是i2上的数乘2，那么i2++ i2++; if(res[i]==res[i3]*3) i3++; if(res[i]==res[i5]*5) i5++; } return res[index-1]; }
想起来一个思路了，那就是倒过来推，推出剩下的那个在原来全员都在的情况下，他的下标是什么
这题还不能用模拟，因为会超时
我们看力扣题解里的”换个角度理解xxx”
制定规则：当去除一个人之后，把去除的那个人的后一个人作为下标0，然后去除的人的前面的人 全部排到后面去
只剩最后一个人的时候，他的下标必定是0，然后我们反推出他在人全在的时候下标是哪个
正过来：先删除，然后左移m-1位
反过来：先加回去，然后右移m位，如果溢出了，就加到最前面
反过来的公式：[当前位置+m(右移m位)]%i(如果溢出就加到最前面) i是当前有多少个数字
public int iceBreakingGame(int num, int target) { int pos=0;//最后剩下下标肯定是0 for(int i=2;i<=num;i++) { pos=(pos+target)%i; } return pos; }
第一种弱智方法：
public class Solution { //Insert one char from stringstream HashMap<Character,Integer>map=new HashMap<>(); StringBuilder s=new StringBuilder(); public void Insert(char ch) { map.put(ch,map.getOrDefault(ch,0)+1); s.append(ch); } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(int i=0;i<s.length();i++) { if(map.get(s.charAt(i))==1) { return s.charAt(i); } } return '#'; } }
第二种：用linkedHashmap的有序性
public class Solution { //Insert one char from stringstream private Map<Character,Integer>map=new LinkedHashMap<>(); public void Insert(char ch) { if(map.containsKey(ch)) { map.put(ch,map.get(ch)+1); }else { map.put(ch,1); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(Map.Entry<Character,Integer>set:map.entrySet()) { if(set.getValue()==1) { return set.getKey(); } } return '#'; } }
比第一种快了一半
y用宫水三叶的方法模拟
class Solution { //按照宫水三叶的思路，先进行处理，然后分情况判断,如果有E，那就分别判断左右，没有就整体判断 //然后我们把所有的e换成E //小数：就是小数点的左右至少有一方有数字 //整数：至少有一位数字 //E的左边可以是整数和小数，右边必须是整数 public boolean validNumber(String s) { s=s.trim(); int n=s.length(),l=0,r=n-1; s=s.replace('e', 'E'); int idx=0; while(idx<n&&s.charAt(idx)!='E')idx++; if(idx==n) { return check(s, true); }else { return check(s.substring(0,idx), true)&&check(s.substring(idx+1), false); } } public boolean check(String s ,boolean isDecimal) { if(s.equals(".")||s.equals(""))return false;//这一半只有个符号和空，那就false int n=s.length(); boolean once=true;//是不是只有一个小数点 for(int i=0;i<n;i++) { char c=s.charAt(i); if(c=='+'||c=='-') { if(i!=0||i==n-1)return false; }else if(c=='.') { if(!isDecimal)//不被允许有小数的部分 { return false; } if(!once)return false;//已经出现过小数点了 once=false; boolean a=i-1>=0&&Character.isDigit(s.charAt(i-1));//左边是不是数字 boolean b=i+1<n&&Character.isDigit(s.charAt(i+1));//右边是不是数字 if(!(a||b))return false; }else if(!Character.isDigit(c)){ return false; } } return true; } }
数学结论：尽量以长度3切，这样最大
public int cuttingBamboo(int n) { if(n<4)return n-1; int res=1; while (n>4) { res*=3; n-=3; } return res*n; }
还是和上一题一样的思路，只不过在循环过程和最后要取模
public int cuttingBamboo(int n) { if(n<4)return n-1; long res=1; while(n>4) { res=res*3%1000000007; n-=3; } return (int)(res*n%1000000007); }\ //积的结果取余等于 每个乘数取余的乘积再取余
但是在牛客里，这样的方法会超时，我们采用快速幂的方法，可以将时间复杂度降低
回溯 class Solution { public boolean exist(char[][] board, String word) { int h = board.length, w = board[0].length; boolean[][] visited = new boolean[h][w]; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { boolean flag=check(board,visited,i,j,word,0); if(flag) { return true; } } } return false; } public boolean check(char[][]board,boolean[][]visited,int i ,int j,String s,int k) { if(board[i][j]!=s.charAt(k)) { return false; }else if(k==s.length()-1)//长度一样了 { return true; } visited[i][j]=true; boolean result=false; int[][]dirs={{0,1},{0,-1},{1,0},{-1,0}}; for(int[]dir:dirs) { int newi=i+dir[0],newj=j+dir[1]; if(newi>=0&&newi<board.length&&newj>=0&&newj<board[0].length) { if(!visited[newi][newj]) { boolean flag=check(board,visited,newi,newj,s,k+1);//递归查询他周边的 if(flag) { result=true;//说明这条路径可以找到 break;//不用再找了 } } } } visited[i][j]=false;//回溯 return result; } }
应该要知道flag是什么用处？是用来剪枝的，就是说找到了 一条路径后，直接设置flag为true，退出整个搜索过程
这个比上一题简单啊，我草
class Solution { public int wardrobeFinishing(int m, int n, int cnt) { int res=0; boolean[][]visited=new boolean[m][n]; return dfs(visited, m, n, cnt, 0, 0); } public int dfs(boolean[][]visited,int m,int n,int cnt,int i,int j) { if(i>=m||j>=n||sums(i)+sums(j)>cnt||visited[i][j])return 0; visited[i][j]=true; return 1+dfs(visited,m,n,cnt,i+1,j)+dfs(visited, m, n, cnt, i, j+1); } int sums(int x) { int s=0; while (x!=0) { s+=x%10; x=x/10; } return s; } }
为什么这题不用回溯？就是不用啊
