1.两数之和

 数组可以有重复元素,所以与力扣的第一题稍微有点不同

 public int[] twoSum(int[] numbers, int target) {int n = numbers.length;HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {int realTarget = target - numbers[i];if (map.containsKey(realTarget)&&map.get(realTarget)!=i) {return new int[]{map.get(realTarget)+1,i+1};}else map.put(numbers[i], i);}throw  new IllegalArgumentException("No solution");}

2.顺时针旋转矩阵 

处理用一个新的数组进行处理之外,该题的空间复杂度可以缩减到O1但是需要逐层处理,因为每次交换会掩盖掉之前的数字

 public int[][] rotateMatrix(int[][] mat, int n) {//一层一层的进行交换,从最外层开始进行交换int rotateTimes=n/2;int i=0,low=0,high=n-1;while (i++<rotateTimes){for (int j = 0; j < high - low; j++) {//用1 4 13 15交换来举例int temp=mat[low][low+j];//记录1的值mat[low][low+j]=mat[high-j][low];//13换到1的位置mat[high-j][low]=mat[high][high-j];//16换到13的位置mat[high][high-j]=mat[low+j][high];//4换到16的位置mat[low+j][high]=temp;//1换到4的位置}low+=1;//往内层循环走,最低层+1high-=1;//最高层-1}return mat;}

合并字符串

 public String WordsMerge (String[] Words) {StringBuilder sb= new StringBuilder("");for (String word : Words) {sb.append(word);}int n=sb.length();char last=sb.charAt(0);for (int i = 1; i <n ; i++) {if(sb.charAt(i)==last){//左闭右开区间sb.replace(i-1,i+1,"  ");last=' ';}last=sb.charAt(i);}//清除所有的"  "return sb.toString().trim();}

旅行

public int Travel (int N, int V, int[] A, Point[] list) {//初始化优先队列 {费用,城市索引}PriorityQueue<int[]> queue=new PriorityQueue<>(//按照城市费用升序,如果相等就按照索引升序 (如有多个花费一样的则首先去编号小的城市)(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);//初始化入度数组、后置城市数组int[] Indeg=new int[N];int[][] limit=new int[N][N];//给后置城市数组和入度数组赋值for(Point p:list){limit[p.x-1][p.y-1]=1;Indeg[p.y-1]++;}//如果入度为0，则表示可以访问，加入到队列for(int i=0;i<N;i++){if(Indeg[i]==0){queue.offer(new int[]{A[i],i});}}//记录最多可去城市数目int cnt=0;while(!queue.isEmpty()){int[] city=queue.poll();//取出最小的数int cost=city[0];//费用int id=city[1];//索引//如果剩余花费不够，则直接跳出循环if(V<cost) break;//费用够,减去当前费用V-=cost;cnt++;//可以去的城市数量增加for(int j=0;j<N;j++){//存在后置城市if(limit[id][j]==1){//后置城市的入度减一Indeg[j]--;//如果入度为0，则加入到队列if(Indeg[j]==0){queue.offer(new int[]{A[j],j});}}}}return cnt;}

枪打出头鸟

暴力解法: 

public long solve(int n, int[] a) {//当前位置的荒唐度int[] dp = new int[n];//basedp[0] = 0;for (int i = 1; i < n; i++) {for (int j = i-1; j >=0; j--) {if (a[i] < a[j] ) {dp[i]=j+1;break;}}}//注意整形溢出问题long res=0;for (int i : dp) {res+=i;}return res;}

栈解法:

 //如果前置元素比后置元素小,那么往后的元素肯定会击中后置元素,于是前置小的元素就没用了
//,这也是可以利用栈来解决的原因public long solve(int n, int[] a) {long ans = 0;Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {//如果栈不为空并且栈中的数据小于当前数据(说明打不到),栈中的元素一直弹出while (!stack.empty() && a[i] >= a[stack.peek()]) stack.pop();//如果到这里栈不为空的话说明有能被枪打到的元素 其值为索引+1if (!stack.empty()) ans += stack.peek() + 1;//无论如何都把当前元素索引放进栈中stack.push(i);}return ans;}

翻转链表

 public ListNode ReverseList(ListNode head) {if (head == null) return null;if (head.next == null) return head;ListNode pre=null;ListNode cur=head;ListNode nex;while (cur!=null){//保留后续节点nex= cur.next;//指向前置节点cur.next=pre;//前置节点后移pre=cur;//当前节点后移cur=nex;}return pre;}

k个一组进行翻转

•  正常翻转步骤并且对k进行计数
• 当前节点为null的时候,恢复链表(再翻转,传入的是Prev节点)
• head.next递归调用

public ListNode reverseKGroup (ListNode head, int k) {ListNode prev = null,curr = head;ListNode next;int times = k;while (times-- > 0){//经过k次以内的循环,已经超过了链表的长度if(curr == null){//将当前翻转过的链表进行还原 //对于1->2->3->4->5 k=3来说//当遍历到curr==null的时候 prev=5 此时的链表情况为 3->2->1--->(5->4->null)//restore后3->2->1->4->5return restore(prev);}//在k次之内进行链表的翻转next= curr.next;curr.next = prev;prev = curr;curr = next;}//头结点(现在是尾节点)的下一个节点为翻转链表后的头节点 1->2->3->4 2->1->4->3head.next = reverseKGroup(curr, k);return prev;}private ListNode restore(ListNode head){    //不足k个时再反转还原ListNode prev = null,curr = head;ListNode next;while (curr != null){next=curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}

未排序数组最长连续子数组长度 

    public int maxlenEqualK(int[] arr, int k) {if (arr == null || arr.length == 0) return 0;int n = arr.length;HashMap<Integer, Integer> map = new HashMap<>();//记录每一个和以及出现的位置map.put(0, -1);//初始化int res = 0;int sum = 0;for (int i = 0; i < n; i++) {sum += arr[i];//如果满足条件就比较当前最大值if (map.containsKey(sum - k)) res = Math.max(res, i - map.get(sum - k));//没有当前和就将其放入哈希表,因为是按照顺序遍历的,后面如果出现同样的和可以直接舍弃if (!map.containsKey(sum)) map.put(sum, i);}return res;}

字符串出现次数的TopK问题

 侧重于对哈希表进行排序处理

    public String[][] topKstrings (String[] strings, int k) {HashMap<String, Integer> map = new HashMap<>();for (int i = 0; i < strings.length; i++) {map.put(strings[i],map.getOrDefault(strings[i],0)+1);}//使用list对HashMap进行排序ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>();list.addAll(map.entrySet());//指定排序规则Collections.sort(list,(m1,m2)->{//出现的次数相等按照字符集升序(要选择小的那个),否则按照出现次数降序return m1.getValue()==m2.getValue()?m1.getKey().compareTo(m2.getKey()):m2.getValue()-m1.getValue();});if(k>strings.length)k=strings.length;String[][] ans=new String[k][2];for (int i = 0; i <k ; i++) {ans[i][0]=list.get(i).getKey();ans[i][1]=list.get(i).getValue().toString();}return ans;}

计算机算数

 堆可以处理大部分需要重新排列结果和原数据集的题目

 //由于计算机只能计算一次,所以每次取两个最小的值进行计算public long solve (int n, int c, int[] a) {long res=0;PriorityQueue<Integer> pq=new PriorityQueue<>();for (int i : a) {pq.offer(i);}while (pq.size()!=1){int x=pq.poll();int y=pq.poll();int xy=x+y;res+=xy;pq.offer(xy);}return c*res;}

寻找第k大的数字

构造一个大顶堆 

public int findKth(int[] a, int n, int K) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer integer, Integer t1) {return t1.compareTo(integer);}});for (int i = 0; i < n; i++) {priorityQueue.offer(a[i]);}//k先--再比对是否为0while (--K!=0){priorityQueue.poll();}return priorityQueue.peek();}

加密完全二叉树

long res=0;public long tree1 (int[] a) {if(a==null||a.length==0)return 0;TreeNode root = build(a, 1);getSum(root);return res;}private TreeNode build(int[]a,int index){if(index>a.length)return null;TreeNode treeNode = new TreeNode(a[index-1]);//二叉树性质,左节点等于父节点位置*2 注意不能使用(索引+1)*2,如果从0开始//(0+1)*2导致下一个访问的索引为2treeNode.left=build(a,index*2);treeNode.right=build(a,index*2+1);return treeNode;}private void getSum(TreeNode root){if(root==null)return;if(root.left!=null)res+=root.val^root.left.val;if(root.right!=null)res+=root.val^root.right.val;getSum(root.left);getSum(root.right);}

也可以不构造二叉树直接使用数组:

 public long tree1 (int[] a) {//初始化结果变量long res=0L;int n=a.length;//根据数组访问树中所有节点for(int i=1;2*i<=n;i++){//左子节点对应编号int l=2*i;//右子节点对应编号int r=2*i+1;//计算异或和if(l<=n){res+=a[i-1]^a[l-1];}if(r<=n){res+=a[i-1]^a[r-1];}}return res;}

二叉树的个数

其实是对1000000007取模

前置知识:两数乘积的模等于两数模的乘积,由于其中序遍历单调递增,所以它是一个搜索二叉树

左节点只能放比自己小的,右节点只能放比自己大的

当节点为i的时候,左子树的节点个数为i-1右子树为n-i个节点,知道这个条件就可以使用动态规划来做

 public int numberOfTree(int n) {//初始化dp数组long[] dp = new long[n + 1];//没有节点和只有一个节点的情况dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {//找到每一个节点(从1到i的每一个数对应一个节点)为根的情况，并进行累加//左子树的数量为j-1,右子树的数量为i-jfor (int j = 1; j <= i; j++) {dp[i] = (dp[i] + dp[j - 1] * dp[i - j]) % mod;}}return (int) dp[n];}

寻找重复的数

public int search (int n, int[] a) {//让数组中的元素和1-n进行异或操作int res=0;for (int i = 1; i <= n; i++) {res^=i;System.out.println(res);res^=a[i-1];System.out.println(res);}//最后一个元素还没有进行异或int last=a[n];System.out.println(res^last);return res^last;}

交换字符串

 要保证交换后字典序大,只需保证交换之后大的字符在前面就行了

public int turn (String s, int k) {int n=s.length();int res=0;//分为k组for(int i=0;i<k;i++){//临时计数数组int[] cnt=new int[26];for(int j=i;j<n;j+=k){//当前字符对应下标int index=s.charAt(j)-'a';for(int id=0;id<index;id++){//如果有小于当前字符的情况，则加上对应次数res+=cnt[id];}//当前字符计数加一cnt[index]++;}}return res;}

青蛙跳台阶-一次跳一层或者两层,问跳到n层有多少方法

 public int jumpFloor(int target) {if(target==1||target==2)return target;//跳上n级台阶的跳法int[] dp = new int[target+1];dp[1]=1;dp[2]=2;for (int i = 3; i < dp.length; i++) {dp[i]=dp[i-1]+dp[i-2];}return dp[target];}

计算器--加减乘和括号

 public int calculate(String s) {//使用list来存储字符串List<Character> list = new ArrayList<>();for (int i = 0; i < s.length(); i++) {list.add(s.charAt(i));}return helper(list);}private int helper(List<Character> s) {Stack<Integer> stack = new Stack<>();// 记录 num 前的符号，初始化为 +char sign = '+';int num = 0, res = 0;while (s.size() > 0) {//不断的移除获取到第一个元素(其实就和遍历一样)char c = s.remove(0);//数字累加if (Character.isDigit(c)) {num = 10 * num + (c - '0');}//遇到前括号递归,我们需要先算出括号的结果,括号包含的算式我们认为是一个数字就行了if (c == '(') num = helper(s);if ((!Character.isDigit(c) && c != ' ') || s.size() == 0) {//这里查看的其实是上一个符号,因为num也是遍历到当前符号的上一个数switch (sign) {//加减法直接把数字带着符号push进去,等着最后计算case '+':stack.push(num);break;case '-':stack.push(-num);break;//遇到乘除法就直接拿出上一个数来运算   case '*':stack.push(stack.pop()*num);break;case '/':stack.push(stack.peek()/num);break;}//更新符号为当前符号，数字清零sign=c;num=0;}if(c==')')break;//遇到右括号递归结束}//计算所有栈里的值while (!stack.isEmpty()){res+=stack.pop();}return res;}