剑指offer_刷题笔记_Java
前言
世人皆知算法与数据结构的重要性,做技术的人,还是要专心于技术.让我们刷起来吧
算法的重要性
首先,回答一下大家的疑惑点:
为什么刷算法?
1.大厂必考算法.(更考察面试者能力,能刷大量面试者,能全面考察面试者)
2.算法提升思维能力,需要理解-->练习-->调试-->优化-->积累
3.算法能提高代码的运行效率,从时间空间上调优;确实对工作有用
怎么学算法？
1.学习数据结构。谈到算法,一定与数据结构分不开,所以需要我们先了解一些常用的数据结构。
2.理解时间空间复杂度分析。怎么确定算法的好坏，时间最优或空间最优，功能正确，鲁棒性强，性能稳定。
3.了解自己擅长语言的常用工具类和方法，这个可以先简单了解，用到的时候再深入了解
4.直接开刷，其他都没用，直接写，coding能力很重要。
怎么刷算法？
讲一下小编作为在职人是怎么快速刷算法的：
1.每天上班通勤时间看一下算法题目，简单思考后看下题解，截图
2.中午饭点看一下题目，再次想一下题解，再次查看截图对比
3.下班后，直接开刷，第一面可以先写伪代码，即思路；然后卡壳了看原代码。
4.通过后将代码记录，对代码进行简化和优化，代码短一点或者好理解一点
5.思维导图对已刷问题进行总结和分析
6.二刷，此时不要看笔记，直接写，考察自己的coding和思考能力。将错误点和调试信息记录在笔记中。
....无休止的复习....
（大概一天9道算法，加班就会学到一两点；周末复习，一天二十多道）
总结：多利用碎片时间，多练，做好笔记和复习;解完一个题的成就感不比游戏吃鸡、王者五杀有意思多了？
刷算法有什么推荐吗？
1.B站左神视频 ，左神的书 《程序员代码面试指南》
2.剑指offer书籍、极客时间--数据结构与算法之美、小灰算法之旅（漫画学算法）
3.网上一些博客、Github上一些源码、力扣牛客题解、已答题的排名第一解
链表反转
三个指针next、head、pre；注意特殊情况直接返回
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//特殊情况，链表为空或者长度为1的情况，直接返回
if(head == null || head.next==null){
return head;
}
//
ListNode pre = null; // 当前节点的前一个节点
ListNode next = null; // 当前节点的下一个节点
while(head!=null){
next = head.next;//记下当前节点的下一个节点
head.next = pre; //断链且指向当前节点的前一个节点
pre = head; //重新记录前节点
head = next; //重新记录当前节点
}
return pre;
}
} 快排
package sort;
public class QuickSort {
public static void main(String[] args) {
int[] aa= {1,3,4,5,1,44,5,66,55};
quickSort(aa);
}
static void quickSort(int[] a) {
if (a == null || a.length < 2) {
return;
}
quickSort( a, 0, a.length - 1);
}
static void quickSort(int[] a, int left, int right) {
if(left<right){
swap(a, right, left + (int) (Math.random() * (right - left + 1)));//随机快排
int[] p = partition(a, left, right);
quickSort(a, left, p[0] - 1);
quickSort(a, p[1] + 1, right);
}
}
static int[] partition(int[] a, int left, int right) {
int less = left - 1;
int more = right;
while(left<more){
if(a[right]>a[left]){
swap(a,++less,left++);
}else if (a[right]<a[left]){
swap(a,--more,left);
}else {
left++;
}
}
swap(a,more,right);
return new int[]{less+1,more};
}
static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
堆排序
package sort;
public class HeapSort {
public static void main(String[] args) {
int[] a = {3, 4, 2,6};
heapSort(a);
for (int i: a) {
System.out.println(i+" ");
}
}
public static void heapSort(int[] a) {
if(a==null||a.length<2) return;//数组为空为1位,直接返回
for (int i = 0; i < a.length; i++) {
heapInsert(a, i); //将数组构建成大顶堆
}
int heapSize = a.length; //初始化heapSize
swap(a, 0, --heapSize); //取出堆顶元素,与堆最后一个叶子节点元素交换
while (heapSize > 0) { //如果堆还有元素
heapIfy(a, 0, heapSize);//调整堆
swap(a, 0, --heapSize);//继续取出堆顶元素,与堆最后一个叶子节点元素交换
}
}
static void heapInsert(int[] a, int index) {
// int aa=(index-1)>>1; //使用位运算,当index=0时,parent为-1
//while(index>0&&a[index]>a[((index-1)>>1)]){ //此时需要加上index>0
// parent = (index - 1) / 2; //(index-1)/2 是父节点位置
while (a[(index - 1) / 2] < a[index]) {//边界值分析:当到顶点时,index=0;父节点(0-1)/2=0;同样跳出循环
swap(a, (index - 1) / 2, index);
index = (index - 1) / 2;
}
}
static void heapIfy(int[] a, int index, int heapSize) {
// 1.首先与两个子节点中较大值比较；当子节点存在比自己大的节点时，交换；并更新index；
// 2.重复步骤1，直到比子节点都大、或者不存在子节点时，停止
int left = index * 2 + 1;
while (left < heapSize) {
int largest = left + 1 < heapSize && a[left] < a[left + 1] ? left + 1 : left;
if (a[index] < a[largest]) {
swap(a, index, largest);
index = largest;
left = index * 2 + 1;
} else break;
}
}
static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
归并排序
package sort;
//归并排序(时间复杂度为N*logN,稳定;数据库,Java,Python的对象排序都用它)
//原因(优点):稳定,速度较快,空间复杂度为N;
//合并时看子数组规模,大时用归并,小时用插入,都稳定;
// 对应Java中的timiSort
//思想:将数组分为两个数组,将两个数组排序后合并;
//子数组的排序可以递归调用归并排序,规模较小时用插入排序
//涉及理论:插入排序,分治法,递归
public class MergeSort {
public static void main(String[] args) {
int[] a = {1, 4, 7, 8, 3, 6, 9};
print(a);
mergeSort(a);
print(a);
}
//归并排序 总,入口
public static void mergeSort(int[] a){
if(a==null||a.length<2)return;
mergeSort(a,0,a.length-1);
}
//拆分
static void mergeSort(int[] a, int left, int right) {
if (left <right) {
//取中间值,拆分
int mid = left + ((right - left) >> 1);
//拆分左边
mergeSort(a, left, mid);
//拆分右边
mergeSort(a, mid + 1, right);
//合并
merge(a, left, mid , right);
}
}
static void merge(int[] a, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int r = mid+1 ;
int i = 0;
int l = left;
while (l <= mid && r <= right) {
help[i++]=a[l]<=a[r]?a[l++]:a[r++];
}
while (l <= mid) {
help[i++] = a[l++];
}
while (r <= right) {
help[i++] = a[r++];
}
for (int m = 0; m < help.length; m++) {
a[left + m] = help[m];
}
}
static void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
插入排序
package sort;
import java.util.Arrays;
import static sort.SelectionSort.*;
//插入排序(相对冒泡和选择较好,但时间复杂仍为n**2,空间为1,稳定)
//思想:同打牌,将新摸到的牌插入到已排好的牌面上
//操作:每次将后面的数插入到前面已排好的数组中
public class InsertionSort {
public static void main(String[] args) {
int[] a = {2,3,6,8,5,6,5,32,4,32,4};
print(a);
insertionSort(a);
System.out.println();
int index =halfSearch(a,8);
System.out.println(index);
print(a);
}
static void insertionSort(int[] a ){ //NK
//插入排序
for(int j=1;j<a.length;j++) { //N
for (int i = j; i > 0; i--) { //k
if (a[i] < a[i - 1]) swap(a, i, i - 1); //可以不换,多用个变量,直接移动后插入
}
}
//折半插入
for (int i=1;i<a.length;i++){
//找到插入的位置
int temp =a[i];
int left=0;
int right=i-1;
int mid;
//
while(left<=right){
mid=left +(right-left)/2;
if(a[mid]>temp){
right =mid-1;
}else{
left=mid+1;
}
}
//一次循环,把值插到该插入的位置
for (int j = i; j > left; j--) {
a[j]=a[j-1];
}
a[left]=temp;
}
}
}
LRU
设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
- set(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
[要求]
- set和get方法的时间复杂度为O(1)
- 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
- 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案
思想：设置链表实现LRU，用hashmap优化到O(1)
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
private Map<Integer, Node> map = new HashMap<>();
private Node head = new Node(-1,-1);
private Node tail = new Node(-1,-1);
private int k;
public int[] LRU (int[][] operators, int k) {
this.k = k;
head.next = tail;
tail.prev = head;
int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
int[] res = new int[len];
for(int i = 0, j = 0; i < operators.length; i++) {
if(operators[i][0] == 1) {
set(operators[i][1], operators[i][2]);
} else {
res[j++] = get(operators[i][1]);
}
}
return res;
}
private void set(int key, int val) {
if(get(key) > -1) {
map.get(k).val = val;
} else {
if(map.size() == k) {
int rk = tail.prev.key;
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
map.remove(rk);
}
Node node = new Node(key, val);
map.put(key, node);
moveToHead(node);
}
}
private int get(int key) {
if(map.containsKey(key)) {
Node node = map.get(key);
node.prev.next = node.next;
node.next.prev = node.prev;
moveToHead(node);
return node.val;
}
return -1;
}
private void moveToHead(Node node) {
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
static class Node{
int key, val;
Node prev, next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
} 直接用LinkedHashMap：
LRU = Least Recently Used （最近最少使用）
本题提示了可供操作的两种方法get和set，而数据类型是key-value模式的，自然想到Map类型去实现；
其次，对最近读取的值(题目要求保存到数组返回)，和最近set的值，都是LRU值，那么关键点有两个：
1.在于当map容量达到k值的时候，如果set，需要删除最初保存的值同时put进去最新的值
2.get获取LRU的map里的值，如果没有，返回-1，存在则返回key对应value，同时要删除key之前在map里面的位置，使用put放入这对key-value
根据LinkedHashMap的特性，知道他的key是按照顺序存放的，这样删除第一个放进去的值(最不常用的值)很方便
把上述过程转化为代码就是
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU (int[][] operators, int k) {
// write code here
LinkedHashMap<Integer,Integer> lruMap = new LinkedHashMap<Integer,Integer>();
ArrayList<Integer> result = new ArrayList();
for(int[] opat:operators){
int key = opat[1];
switch(opat[0]){
case 1:
int value = opat[2];
if(lruMap.size()<k){
lruMap.put(key,value);
}else{
Iterator ot = lruMap.keySet().iterator();
lruMap.remove(ot.next());
lruMap.put(key,value);
}
break;
case 2:
if(lruMap.containsKey(key)){
int val = lruMap.get(key);
result.add(val);
lruMap.remove(key);
lruMap.put(key,val);
}else{
result.add(-1);
}
break;
default:
}
}
int[] resultArr = new int[result.size()];
int i=0;
for(int a:result){
resultArr[i++]=a;
}
// for(int i=0;i< re.length;i++){
// re[i]=list.get(i);
//}
return resultArr;
}
} 判断链表有无环
思想：
1.快慢指针法（最优）q != null && q.next !=null
2.hashset找重复（最简单）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
//快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
ListNode q=head;
ListNode p=head;
while(q!=null&&q.next!=null){
q=q.next.next;
p=p.next;
if(q==p){
return true;
}
}
return false;
}
} /**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
//set方法
import java.util.*;
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set= new HashSet<>();
while(head!=null){
if(set.contains(head)){
return true;
}else{
set.add(head);
head=head.next;
}
}
return false;
}
} 4.2有环找出环节点
相遇后将其中一个指针指向头部，两个指针一起走，一次走一步。会在节点处相遇。
方法二、用hash存信息，时间O(1)，空间O(N)
4.3找出环长
慢指针从环节点开始走，快指针留在节点处，慢指针每走一步，count++；相遇即为环长度。
4.4输出环的部分
慢指针从环节点开始走，快指针留在节点处，慢指针每走一步，打印；直到相遇为止。
二叉树的遍历
分别按照二叉树先序，中序和后序打印所有的节点。
递归，函数放什么位置就是什么序。比如先序：先返回当前节点，递归左，递归右
| 先序：根左右 | 中序：左根右 | 后序：左右根 |
|---|---|---|
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
int flag = 0, flag1 = 0, flag2 = 0;//必须三个变量定位在类里
public int[][] threeOrders (TreeNode root) {
// write code here
int[][] nums = new int[3][getRootSize(root)];
getOrder(root, nums);
return nums;
}
//DFS--递归遍历
public void getOrder(TreeNode root, int[][] nums){
if(root == null){return ;} //终止条件
nums[0][flag++] = root.val;
getOrder(root.left, nums);
nums[1][flag1++] = root.val;
getOrder(root.right, nums);
nums[2][flag2++] = root.val;
}
//递归算树的节点数
public int getRootSize(TreeNode root){
if(root == null){return 0;} //终止条件
return 1 + getRootSize(root.left) + getRootSize(root.right);
}
} 二分查找
l、m、r三个指针指向前中后，表示接下来的范围。当l<r时，target一直与中间值比较。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果目标值存在返回下标，否则返回 -1
* @param nums int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] nums, int target) {
if(nums==null || nums.length==0) return -1;
int l=0;
int r=nums.length-1;
int mid=(l+r)>>1;//更快 // int m=l+(r-l)>>1;//健壮性更强，效率更低,过不了
//核心代码--二分模板
while(l<r){
mid=(l+r)>>1;
if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}else{
r=mid;
}
}
return nums[l]==target?l:-1;
}
} 统计字符串个数，并排序
先用hashMap存个数，不存在即直接放，存在即将值+1；
再用list将hashMap中的Entry元素装入
重写Collections的sort方法，按值排序
import java.util.*;
import java.util.Map.*;
class Wandbox
{
public static void main(String[] args)
{
String[] a = new String[10];
a[0]="ada"; a[1]="ada"; a[2]="adc"; a[3]="ada";
a[4]="ada"; a[5]="add"; a[6]="ada"; a[7]="ada";
//放入hashMap
HashMap<String,Integer> ct = new HashMap<>();
for(int i=0;i<a.length;i++){
if(!ct.containsKey(a[i])){
ct.put(a[i],1);
}else{
int n=ct.get(a[i]);
n++;
ct.put(a[i],n);
}
}
//装入list，排序
List<Map.Entry<String,Integer>> list = new ArrayList<>(ct.entrySet()); //将map的entryset放入list集合
//对list进行排序，并通过Comparator传入自定义的排序规则
Collections.sort(list,new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
return o1.getValue()-o2.getValue(); //重写排序规则，小于0表示升序，大于0表示降序
}
});
//用迭代器对list中的键值对元素进行遍历
Iterator<Map.Entry<String, Integer>> iter = list.iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> item = iter.next();
String key = item.getKey();
int value = item.getValue();
System.out.println("键 "+key+" 值 "+value);
}
}
}
二维数组查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
二分查找思想：先找到整个二维数组的中间值，取右上[左下也可]；
然后开始遍历，大于往下走，小于往左走；找到即返回true，到头没找到返回false。
最坏时间复杂度O(N+M)：n为长，m为高
public class Solution {
public boolean Find(int target, int [][] array) {
//右上开始找
int row = 0;
int col = array[0].length-1;//-1
//最后一行或者最左一列，取消
while(row<array.length && col>=0){
//找到返回
if(array[row][col]==target){
return true;
//大于往左
} else if(array[row][col]>target){
col--; //
//小于往下
}else{
row++;
}
}
//最后都没找到返回false
return false;
}
} 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
普通方法：
1.直接使用Java的replace()
2.用一个stringBuilder，遍历字符串，遇到' '添加"%20",其他正常append
最优解：（需能直接操作字符串的语言）
- 计算空格个数
- 将字符串底层数值扩容：+空格个数*2
- 双指针，一个从尾到头遍历，一个从原字符串尾到头遍历，遇到' '依次改为'0'、'2'、'%'，其余正常复制
- （为什么反着来，不会覆盖有效数据）
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return string字符串
*/
public String replaceSpace (String s) {
// write code here
//直接是使用replace函数
return s.replace(" ","%20");
}
} import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return string字符串
*/
public String replaceSpace (String s) {
// write code here
//转化成字符数组
char[] help = s.toCharArray();
StringBuilder sb = new StringBuilder();
//遍历，为空格则添加"%20"，否则原样添加
for(int i=0;i<help.length;i++){
if(help[i]==' '){//注意是' ',因为是字符
sb.append("%20");
}else{
sb.append(help[i]);
}
}
return sb.toString();//sb.toString() 注意()因为是方法
}
} 从头到尾打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
1.将链表直接加入数组中，数组反转输出（等于用栈）
2.递归，每次都先访问下一个节点，直到根节点，开始加入数值（等于用栈
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
//将list创建在外面
ArrayList<Integer> al = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode==null) return al;//终止条件
//递归
printListFromTailToHead(listNode.next);
//最后一个节点先添加，然后回到倒数第二个添加
al.add(listNode.val);
return al;
}
} /**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> al = new ArrayList<>();
while(listNode!=null){
al.add(listNode.val);
listNode=listNode.next;
}
Collections.reverse(al);//直接反转
return al;
}
} 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
| 前序：根左右 | 中序：左根右 |
|---|---|
通过前序，在中序找到当前根，将其分为左右子树；对左右树做相同操作。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//重写方法，传入一个树的前序中序
return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
}
//前序遍历的子树范围 + 中序遍历的子树范围
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
//递归的终止条件，任一个范围为空
if(startPre>endPre||startIn>endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);//根赋值
//遍历中序数组，找到子树的根节点
for(int i=0;i<=endIn;i++){ //注意等于，因为endIn是最后一个
if(in[i]==pre[startPre]){
//对子树的左子树做递归操作 i-startIn为中序找出的左树节点个数+startpre
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn, i-1);
//对子树的右子树做递归操作
root.right=reConstructBinaryTree(pre, startPre+i-startIn+1,endPre,in,i+1, endIn);
break;
}
}
return root;
}
} 两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
栈A只存，栈B只取；如果栈B空了，向栈A要，一要就给全部。都空了，不给！
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//栈1只压入
public void push(int node) {
stack1.push(node);
}
//栈2只弹出
public int pop() {
//都空了不准取
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("queue is empty");
}
//如果栈2空了，就找栈1取，每次取全部
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop(); //别忘了返回
}
} 旋转数组的最小值
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
二分查找的特殊情况
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int l =0;
int r =array.length-1;
//直接用二分
while(l<r){
//取中
int mid = (l+r)>>1;
//大于最后一个数，最小数在右边
if(array[mid]>array[r]){
l=mid+1;
//等于，可能需要遍历，先右边减一
}else if(array[mid]==array[r]){
r--;
//小于，在左边，但是该值可能为最小值
}else{
r=mid;
}
}
return array[l]; //返回的是数组值
}
} 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n\leq 39n≤39
//递归
public class Solution {
public int Fibonacci(int n) {
if(n<2) return n;
return Fibonacci(n-1)+Fibonacci(n-2);
}
} //动态规划
public class Solution {
public int Fibonacci(int n) {
int a = 0;
int b = 1;
while(n>0){
b+=a;
a=b-a;
n--;
}
return a;
}
} 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
//递归
public class Solution {
public int jumpFloor(int target) {
if(target < 4) return target;
return jumpFloor(target-1)+jumpFloor(target-2);
}
} //动态规划
public class Solution {
public int jumpFloor(int target) {
if(target < 4) return target;
int a = 3;
int b = 2;
for(int i = 4; i <= target; i++) {
a = a + b;
b = a - b;
}
return a;
}
} 跳台阶拓展
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
发现规律：f(n)=2*f(n-1)
//递归
public class Solution {
public int jumpFloorII(int target) {
if(target<3)return target;
return 2*jumpFloorII(target-1);
}
} 矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
比如n=3时，2*3的矩形块有3种覆盖方法：
发现规律后，是斐波那契数列:f(n)=f(n-1)+f(n-2)
public class Solution {
public int rectCover(int target) {
if(target<4){//结束条件
return target;
}else{
//递归
return rectCover(target-1)+rectCover(target-2);
}
}
} 二进制中1的个数
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
记住公式：n=(n-1)&n;除去当前数二进制的最后一个1。
因为&相同返回1，(n-1)&n等于将最后1个1后的全归为0。正负皆可。
public class Solution {
public int NumberOf1(int n) {
int count=0;
while(n!=0){ //考虑负数 一定是!=0 不能是>0
++count;
n=(n-1)&n;
}
return count;
}
} 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
考虑次方的符号即可。
public class Solution {
public double Power(double base, int exponent) {
int flag =1;//符号
if (exponent ==0){ //次方等于0，返回1
return 1.0d;
}else if(exponent <0){//次方小于0，转为正数，计算完后取倒数
exponent=-exponent;
flag = -1;
}
double result =1.0d;
for(int i=0;i<exponent;i++){//正常求次方
result*=base;
}
return flag>0?result:1/result;
}
} public class Solution {
public double Power(double base, int exponent) {
if (exponent ==0){
return 1.0d;
}
if(exponent<0){//如果次方小于0；可以将底数取倒数，指数取绝对值
exponent=-exponent;
base=1/base;
}
double result =1.0;//将返回值初始化
while(exponent-->0){//正常求次方
result*=base;
}
return result;
}
} 调整数值顺序，奇数放偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
partition的过程：若不做到稳定，用快排的partition可以做到时间O(N)空间O(1)
稳定的话：
1.辅助数组：先遍历找出奇数的个数；然后再遍历，奇数放前面，偶数放临界点后面。时间O(N)空间O(N)
2.冒泡排序：冒泡的过程中，如果相邻两数，偶前奇后，则交换。时间O(N^2)空间O(1)
import java.util.*;
public class Solution {
public int[] reOrderArray (int[] array) {
int[] a = new int[array.length];
int n=0;
for(int i:array){
if((i&1)==1) n++;
}
int l=0;
for(int i:array){
if((i&1)==1) a[l++]=i;
else a[n++]=i;
}
return a;
}
} import java.util.*;
public class Solution {
public int[] reOrderArray (int[] array) {
// write code here
//奇数个数
int num=0;
int[] arr = new int[array.length];
for(int i=0;i<array.length;i++){
if((array[i]&1)!=0){
num++;
}
}
//奇数放前面，偶数放后面
int i=0;
int j=num;
for(int a : array){
if((a&1)==1){
arr[i++]=a;
}else{
arr[num++]=a;
}
}
return arr;
}
} import java.util.*;
public class Solution {
public int[] reOrderArray (int[] array) {
// write code here
//冒泡排序
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-i-1;j++){
//如果相邻两数 偶前奇后，换
if(((array[j]&1)==0)&&((array[j+1]&1)==1)){
int temp =array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
return array;
}
} 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
双指针，一个先走k步，然后同时走，当先指针到尾时，后指针指向倒数第k个
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
ListNode first = pHead;
while(first!=null&&k-->0){
first=first.next;
}
if(first==null&&k>0) return null;//需要考虑刚好是第一个
ListNode p= pHead;
while(first!=null){
first=first.next;
p=p.next;
}
return p;
}
} import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null) {
return null;
}
//初始化当前位置，先后指针
int currentIndex = 0;
ListNode first = pHead;
ListNode second = pHead;
//先指针先走k步
while (currentIndex < k && first != null ) {
first = first.next;
currentIndex++;
}
//先指针到尾时，后指针指向倒数第K个
while (first != null) {
first = first.next;
second = second.next;
}
//如果链表长度比k小，返回null；否则返回倒数第k个
return currentIndex < k?null:second;
}
} 合并有序链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
等同于归并排序的merge过程
/*
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;
if(list2==null)return list1;
ListNode head = new ListNode(0);//设置了哨兵
ListNode root = head; //必须用一个节点来记录
//核心代码——merge过程
while(list1!=null&&list2!=null){
//比较大小，将小的复制到新链表上
if(list1.val<=list2.val){
head.next =list1;
head=head.next;
list1=list1.next;
}else{
head.next =list2;
head=list2;
list2=list2.next;
}
}
//当某一个链表为空以后，直接将另一个接上,不用while了
if(list1!=null){
head.next=list1;
}
if(list2!=null){
head.next=list2;
}
return root.next;
}
} 树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null)return false;//任一个为空树返回false
//比较两个树，完全相同或者左右子树包含即返回true
return dfs(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
//深度遍历比较两树
private boolean dfs(TreeNode root1,TreeNode root2){
//子树已比较结束，返回true
if(root2==null)return true;
//如果母树为空了，或者当前节点不同，不同 ;必须先判断空
if(root1==null||root1.val!=root2.val)return false;
//都不符合，即当前节点相同，接着比较左右子树
return dfs(root1.left,root2.left)&&dfs(root1.right,root2.right);
}
} 二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
//递归按层去交换左右节点
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror (TreeNode pRoot) {
// 递归终止条件
if(pRoot==null) return pRoot;
//交换左右孩子
TreeNode temp =pRoot.left;
pRoot.left=pRoot.right;
pRoot.right=temp;
//递归左右子树
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
} 顺时针打印数组
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
将一次顺时针抽象出来四个变量，即上下左右，每次打印最外围的矩形。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> a = new ArrayList<Integer>();
//为空，或长宽为0
if(matrix==null || matrix[0].length==0 || matrix.length ==0){
return a;
}
int up = 0;
int down = matrix.length-1;
int left = 0;
int right =matrix[0].length-1;
//核心代码
while(true){
for(int i=left;i<=right;i++){
a.add(matrix[up][i]);
}
up++;
if(up>down) break;
for(int i=up;i<=down;i++){
a.add(matrix[i][right]);
}
right--;
if(left>right) break;
for(int i=right;i>=left;i--){
a.add(matrix[down][i]);
}
down--;
if(up>down) break;
for(int i=down;i>=up;i--){
a.add(matrix[i][left]);
}
left++;
if(left>right) break;
}
return a;
}
} min栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
1.两个栈，一个栈正常装，另一个栈装当前最小值
import java.util.Stack;
public class Solution {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
public void push(int node) {
s1.push(node);
if(s2.isEmpty()||s2.peek()>=node){
s2.push(node);
}
}
public void pop() {
if(s1.peek()==s2.peek()){
s1.pop();
s2.pop();
}else{
s1.pop();
}
}
public int top() {
return s1.peek();
}
public int min() {
return s2.peek();
}
} import java.util.Stack;
public class Solution {
Stack<Integer> s1 = new Stack();
Stack<Integer> s2 = new Stack();
public void push(int node) {
s1.push(node);
if(s2.isEmpty()||s2.peek()>=node){
s2.push(node);
}else{
s2.push(s2.peek());
}
}
public void pop() {
s1.pop();
s2.pop();
}
public int top() {
return s1.peek();
}
public int min() {
return s2.peek();
}
} 栈的压入弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
1.用个辅助栈
将压入序列的压入栈中，如果与弹出序列当前值相等则弹出，否则继续压入。最后判断栈是否为空。
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> s = new Stack<>();
int i=0;
for(int a : pushA){
s.push(a);
//弹就一直弹,直到任一个到边界或者不匹配为止
while(!s.isEmpty()&&i<popA.length){
//查看栈顶与当前值是否相等
if(s.peek()==popA[i]){
i++;
s.pop();
}else{
break;
}
}
}
return s.isEmpty();
}
} 层序遍历
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
使用队列来实现层序遍历
import java.util.ArrayList;
/**
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<>();//list装
ArrayList<TreeNode> queue = new ArrayList<>();//queue去遍历
if(root==null){
return list;
}
queue.add(root);
while(queue.size()!=0){
TreeNode temp = queue.remove(0);//弹出队首到list中，并装入左右节点
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
list.add(temp.val);
}
return list;
}
} 二叉搜索树的后序遍历
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
//BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），
//如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，
//后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
return verify(sequence,0,sequence.length - 1);
}
private boolean verify(int [] sequence,int left,int right) {
//递归结束
if(left >= right){
return true;
}
//先找到中间值，即不属于左子树的第一个节点
int middle = left;
while(sequence[middle] < sequence[right]){
middle++;
}
//看右子树是否满足大于最后一个节点
for(int i = middle; i < right ; i++){ //
if(sequence[i] < sequence[right]){
return false;
}
}
// 递归左右子树是否为二叉搜索树
return verify(sequence,left, middle -1) && verify(sequence,middle,right - 1);
}
} 二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<Integer> path= new ArrayList<>();
ArrayList<ArrayList<Integer>> ans= new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
dfs(root,target,0);//深度遍历（当前节点，目标值，当前和）
return ans;
}
public void dfs(TreeNode root,int target,int sum){
if(root==null) return;
if(sum+root.val>target) return;
//最后叶子节点
if(root.left==null&&root.right==null){
//等于目标值
if(sum+root.val ==target){
path.add(root.val);
ans.add(new ArrayList<>(path));//new Arralist
path.remove(path.size()-1);
}
return;//一条路径找完
}
path.add(root.val);
//递归找左右
dfs(root.left,target,sum+root.val);
dfs(root.right,target,sum+root.val);
path.remove(path.size()-1);
}
} 随机指针链表复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
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) {
if(pHead==null){
return null;
}
RandomListNode node =pHead;
//每一个节点后加入一个节点
while(node!=null){
RandomListNode copy = new RandomListNode(node.label);
copy.next=node.next;
node.next=copy;
//将节点后移
node=copy.next;
}
//将随机指针加上
node=pHead;
while(node!=null){
if(node.random!=null){
node.next.random=node.random.next;
}
node=node.next.next;
}
//将链表拆分
node=pHead;//原链表当前结点
RandomListNode root =pHead.next;//复制链表头结点
RandomListNode temp = root;//复制链表当前节点
while(node!=null){
node.next=temp.next;
temp.next=node.next==null?null:node.next.next;//只能这里判断是否为空
node=node.next;
temp=temp.next;
}
return root;
}
} 二叉搜索树和双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode pre = null;//定义在外面，函数能一直访问到
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null) return null;//中止条件+空判断
//
Convert(pRootOfTree.right);//右边递归
//将当前节点转为双向链表
if(pre!=null){
pRootOfTree.right=pre;
pre.left=pRootOfTree;
}
pre=pRootOfTree;//为空先直接赋值，不为空则转为链表后转到下一个
Convert(pRootOfTree.left);//左边递归
return pre;//因为是反着的，所以直接返回，即为正序
}
} 字符串的排序
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
先找到全排列（去重），装入list中，排序，输出。
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
List<String> res = new ArrayList<>();
if(str!=null&&str.length()>0){
//去找排列
Permutation(str.toCharArray(),0,res);
//排序
Collections.sort(res);
}
return (ArrayList)res;
}
//核心代码 回溯法
////对chs[i~length-1]范围内的字符数组完成全排列,并将结果存入res中
void Permutation(char[] cs,int i,List<String> list){
//i遍历到尾后，查看当前排列是否存在
if(i==cs.length-1){
String val = String.valueOf(cs);
if(!list.contains(val))
list.add(val);
}else{
for(int j=i;j<cs.length;j++){
swap(cs,i,j);//先换
Permutation(cs,i+1,list);//找全排列 i+1
swap(cs,i,j);//换回来
}
}
}
void swap(char[] cs,int i,int j){
char temp =cs[i];
cs[i]=cs[j];
cs[j]=temp;
}
} 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
1.候选数，先通过遍历选出候选数；再遍历算出候选数的次数，是否超1半
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0||array==null) return 0;
int temp = array[0];
int count =1;
for(int i=1;i<array.length;i++){
if(array[i]==temp){
count++;
}else{
count--;
}
if(count==0){
temp=array[i];
count++;
}
}
count=0;
for(int i:array){
if(temp==i){
count++;
}
}
return count>array.length/2?temp:0;
}
} public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0||array==null)return 0;
if(array.length==1)return array[0];
//找候选数，先默认为第一个
int count=1;
int temp =array[0];
for(int i=1;i<array.length;i++){
if(array[i]==temp)count++;
else count--;
if(count==0){
temp=array[i];
count++;}
}
//计算次数
count=0;
for(int i:array){
if(i==temp)count++;
}
//返回
return count>(array.length>>1)?temp:0;
}
} 最小的k个数
topk
简单堆排，top小就小根堆，取顶直到k个。
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] a, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(k>a.length||a==null) return res;
for(int i=0;i<a.length;i++){
heapInsert(a,i);
}
int heapSize = a.length;
while(k-->0 && heapSize>0){
res.add(a[0]);
swap(a,0,--heapSize);
heapIfy(a,0,heapSize);
}
return res;
}
//构建堆
void heapInsert(int[] a,int i){
int p = (i-1)/2;
while(a[p]>a[i]){
swap(a,i,p);
i=p;
p=(i-1)/2;
}
}
//堆的自调
void heapIfy(int[] a,int i,int heapSize){
int l = i*2+1;
while(l<heapSize){
int max = l+1<heapSize && a[l+1]<a[l]?l+1:l;
if(a[max]<a[i]){
swap(a,max,i);
i=max;
l = i*2+1;
}else{
break;//break一定得有,不小就退出了
}
}
}
void swap(int[] a, int i,int j){
int temp =a[i];
a[i]=a[j];
a[j]=temp;
}
} 连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
1.两个变量：当前数的正数和，已遍历最大和（当前盈利、峰值、东山再起）
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length<1||array==null)return 0;
int dp=array[0];//先将第一个赋值给dp,当前数的最大和
int max=dp;
for(int i = 1;i<array.length;i++){
if(dp>0){
dp+=array[i];
}else{
dp=array[i];
}
max=Math.max(dp,max);
}
return max;
}
} public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0||array==null)return 0;
int dp=array[0];
int max=dp;
for(int i=1;i<array.length;i++){
dp =dp>0?dp+array[i]:array[i];
max=Math.max(dp,max);
}
return max;
}
} 整数中1出现的次数
求出1
13的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
需找到规律：从位数去考虑，当前位数，低位，高位。根据当前位数去选择对应公式，high*i
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count=0;
for(int i=1;i<=n;i*=10){ //i代表位数
int high=n/(i*10); //更高位数字
int low=n%i; //更低位数字
int cur=n/i%10;
if(cur==0){
count+=high*i;
}else if(cur==1){
count+=high*i+(low+1);
}else{
count+=(high+1)*i;
}
}
return count;
}
}
// 思路
// 如果是从头到尾遍历(n次)，对每一个数字都计算其1的个数（lgn次），则时间复杂度为O(nlogn)，运算效率太低。因此必须总结规律，提高效率。
// 总结规律如下（思路比《剑指OFFER》一书简单）：
// 对于整数n，我们将这个整数分为三部分：当前位数字cur，更高位数字high，更低位数字low，如：对于n=21034，当位数是十位时，cur=3，high=210，low=4。
// 我们从个位到最高位 依次计算每个位置出现1的次数：
// 1）当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100~00199，01100~01199，……，20100~20199。一共有21*100种情况，即high*100;
// 2）当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000~01999，11000~11999，21000~21034。一共有2*1000+（34+1）种情况，即high*1000+(low+1)。
// 3）当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010~00019，……，21010~21019。一共有（210+1）*10种情况，即(high+1)*10。
// 这个方法只需要遍历每个位数，对于整数n，其位数一共有lgn个，所以时间复杂度为O(logn)。 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
1.排序后拼接；排序的比较方法：比较拼接后的结果谁更小
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
ArrayList<Integer> a= new ArrayList<>();
for(int i:numbers){
a.add(i);
}
Collections.sort(a,new Comparator<Integer>(){//()不能省
//重写比较方法
public int compare(Integer a,Integer b){
String s1=a+""+b;
String s2=b+""+a;
return s1.compareTo(s2);
}
});
String s="";
for(int i:a){
s+=i;
}
return s;
}
} 丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
1.使用三个队列，一个数组；质因子为2、3、5的队列，比较队首元素，最小的装入数组中；同时在三个队中加入该数的丑数倍数合
2.省去三个队列，用指针来替换空间
public class Solution {
public int GetUglyNumber_Solution(int n) {
// 1 2 3 4 5 6
while(n<7) return n;//特殊情况直接返回,可以不要
int[] dp= new int[n];
dp[0]=1;
int i2=0,i3=0,i5=0;//丑数队列指针
for(int i=1;i<n;i++){
dp[i]=Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));
if(dp[i]==dp[i2]*2) i2++;//用指针来记录队列头对应元素 dp[i2]*2
if(dp[i]==dp[i3]*3) i3++;
if(dp[i]==dp[i5]*5) i5++;
}
return dp[n-1];
}
} 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
1.计数排序:因为26个字母,对应的ASCII码小于128,可直接用int[128]
ASCII码:(码值--字符)
| 48 -- 0 | 65--A | 90--Z | 97--a | 122--z |
|---|---|---|---|---|
2.hashMap
//计数排序
public class Solution {
public int FirstNotRepeatingChar(String str) {
int [] mp = new int[128];//计数数组
for(int i=0;i<str.length();i++){
mp[str.charAt(i)]++;//字符对应下标的数+1
}
for(int i=0;i<str.length();i++){
if(mp[str.charAt(i)]==1)//找到第一个为1的
return i;
}
return -1;
}
} import java.util.*;
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str==null||str.length()<1||str=="")return -1;
HashMap<Character,Integer> map = new HashMap<>();
char[] a =str.toCharArray();
for(char i:a){
if(map.containsKey(i)){
int count=map.get(i);
map.put(i,++count);
}else{
map.put(i,1);
}
}
for(int i=0;i<a.length;i++){
if(map.get(a[i])==1)
return i;
}
return -1;
}
} 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
public class Solution {
int cnt=0;//需要全局变量计数
public int InversePairs(int [] array) {
int[] t= new int[array.length];
mergeSort(array,t,0,array.length-1);//归并排序
return cnt;
}
void mergeSort(int[] a,int[] t,int l,int r){
if(l<r){
int m = (l+r)>>1,i=l,j=m+1,k=0;//初始化所有变量
mergeSort(a,t,l,m);//左归并
mergeSort(a,t,j,r);//右归并
while(i<=m && j<=r){//合并,merge
if(a[i]<=a[j]){
t[k++]=a[i++];
}else{
t[k++]=a[j++];
cnt +=m-i+1;//返回逆序对
cnt%=1000000007; //必须在此余
}
}
//当一边为空,另一边全加入
while(i<=m){
t[k++]=a[i++];
}
while(j<=r){
t[k++]=a[j++];
}
//别忘了将排序后的复制到原数组中,不是原地排序
for(int p=0;p<k;p++){
a[l+p]=t[p];
}
}
}
} public class Solution {
int count=0;
public int InversePairs(int [] array) {
if(array==null||array.length==0)return 0;
mergeSort(array,0,array.length-1);
return count;
}
void mergeSort(int[] a,int l,int r){
if(l<r){
int mid =(l+r)>>1;
mergeSort(a,l,mid);
mergeSort(a,mid+1,r);
merge(a,l,r,mid);
}
}
void merge(int[] a,int l,int r,int mid){
int[] help = new int [r-l+1];
int left=l;
int right=mid+1;
int index=0;
while(left<=mid&&right<=r){
if(a[left]<=a[right]){
help[index++]=a[left++];
}else{
help[index++]=a[right++];
count+=(mid-left+1);
count%=1000000007;
}
}
while(left<=mid){
help[index++]=a[left++];
}
while(right<=r){
help[index++]=a[right++];
}
for(int i=0;i<help.length;i++){
a[l+i]=help[i];
}
}
} 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
拓展:判断两个有环链表是否相交
判断两个单链表相交
方法1.用hashset来存信息，相同即相交。
方法2.双指针：核心思想，走共同的长度，必在交点处相交
1.让两个指针同时从两个链表头开始走，当一个当null后指向另一个链表接着走；直到他俩相交。特殊情况，任一个链表头结点为null直接返回不相交。
2.算出两个链表的长度,双指针,让长链表的先走差长,必在节点处相交
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//任一个为空直接返回
if(pHead1==null||pHead2==null) return null;
//双指针
ListNode p1 =pHead1;
ListNode p2 =pHead2;
//不同则一直循环
while(p1!=p2){
p1=p1.next;
p2=p2.next;
if(p1==p2){
return p1;//相同返回
}
if(p1==null){
p1=pHead2;//走到头则走另一条链表
}
if(p2==null){
p2=pHead1;//走到头则走另一条链表
}
}
return p1;
}
} /*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead2==null||pHead1==null)return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1!=p2){
p1=p1==null?pHead2:p1.next;
p2=p2==null?pHead1:p2.next;
if(p1==p2)return p1;
}
return p1;//如果相等直接返回
}
}
//最优解不一定正确,本质是走同样长的路程,如果不为空且不相交,此程序会一直跑
//应求长度和差长,多两个变量;如果不相交,走完返回null //set
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.*;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> set = new HashSet<>();
while(pHead1!=null){
set.add(pHead1);
pHead1=pHead1.next;
}
while(pHead2!=null){
if(set.contains(pHead2))
return pHead2;
pHead2=pHead2.next;
}
return null;
}
} 统计一个数字在升序数组中出现的次数
统计一个数字在升序数组中出现的次数。
二分的变化
二分找到左右边界，然后返回右-左+1；
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length==0||array==null)return 0;
int left=leftSearch(array,k,0,array.length-1);
System.out.println();
if(left>=0){
int right=rightSearch(array,k,left,array.length-1);
return right-left+1;
}else{
return 0;
}
}
int leftSearch(int [] array , int k,int l,int r){
while(l<r){
int mid = (l+r)>>1;
if(array[mid]<k){
l=mid+1;
}else if(array[mid]>k){
r=mid-1;
}else{
r=mid;
}
}
return array[l]==k?l:-1;
}
int rightSearch(int [] array , int k,int l,int r){
while(l<r){
int mid = (l+r)>>1;
if(array[mid]<k){
l=mid+1;
}else if(array[mid]>k){
r=mid-1;
}else if(mid+1<=r&&array[mid+1]==k){//这一步很关键，先不越界，其次等于k，才加1
l=mid+1;
}else{
return mid;
}
}
return array[l]==k?l:-1;
}
} 二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)return 0;//终止条件
int left = TreeDepth(root.left);
int right =TreeDepth(root.right);
return Math.max(left,right)+1;
}
} public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
return 1+Math.max(TreeDepth(root.left),TreeDepth(root.right));
}
} 层序遍历：队列方法
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)return 0;
ArrayList<TreeNode> queue= new ArrayList<>();
int depth=0,count=0,nextcount=1;//三个变量
queue.add(root);
while(queue.size()!=0){
TreeNode top = queue.get(0);
queue.remove(0);
count++;
if(top.left!=null) queue.add(top.left);
if(top.right!=null) queue.add(top.right);
if(count==nextcount){
count=0;
nextcount=queue.size();
depth++;
}
}
return depth;
}
} /**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> q = new LinkedList<>();
int deapth=0;
if(root!=null)q.add(root);
while(!q.isEmpty()){
for(int i=q.size();i>0;i--){
TreeNode node = q.poll();
if(node.left!=null)q.add(node.left);
if(node.right!=null)q.add(node.right);
}
deapth++;
}
return deapth;
}
} 判断平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
//暴力递归
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root==null)return true;
return Math.abs(depth(root.left)-depth(root.right))<=1 && IsBalanced_Solution(root.left)&& IsBalanced_Solution(root.right);
}
int depth(TreeNode root){
if(root==null)return 0;
int left=depth(root.left);
int right=depth(root.right);
return Math.max(left,right)+1;
}
} //改进版
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return depth(root)!= -1;
}
int depth(TreeNode root){
if(root==null)return 0;
int left=depth(root.left);
if(left==-1)return -1;
int right=depth(root.right);
if(right==-1)return -1;
//不是平衡二叉树,高度变为-1
return Math.abs(left-right)>1?-1:Math.max(left,right)+1;
}
} 数组中只出现一次的两个数
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
1.用^可求出单个;分成两组可求出两个 (&负数 || &1 1左移)
2.用hash
//位运算版1
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
int[] a=new int[2];
int i=0;
for(int v:array)i^=v;
//负数--补码:取反加1, i&=-i 取到为1那一位
i&=-i;
for(int v:array){
if((v&i)==0)a[0]^=v;
else a[1]^=v;
}
//小的在前
Arrays.sort(a);
return a;
}
} //位运算版2
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
int[] a=new int[2];
int x=array[0];
for(int i=1;i<array.length;i++){
x^=array[i];
}
//找出二进制第几位为1
int m=1;
while((m&x)==0){
m=m<<1;
}
//找出那两个数
for(int i:array){
if((i&m)==0){
a[0]^=i;
}else{
a[1]^=i;
}
}
//swap
if(a[0]>a[1]){
a[0]=a[0]^a[1];
a[1]=a[0]^a[1];
a[0]=a[0]^a[1];
}
return a;
}
} //hashset
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
HashSet<Integer> re = new HashSet<Integer>();
for(int i:array){
if(re.contains(i)){
re.remove(i);
}else{
re.add(i);
}
}
Iterator it = re.iterator();
int[] a= new int[2];
int i=0;
while(it.hasNext()){
a[i++]=(int)it.next();
if(i>1)break;
}
return a;
}
} 和为s的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer> > res = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int l=1,r=2;
while(l<r){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur=(l+r)*(r-l+1)>>1;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur==sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=l;i<=r;i++) list.add(i);
res.add(list);
r++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur<sum){
r++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
l++;
}
}
return res;
}
} 和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
返回值描述:
对应每个测试案例，输出两个数，小的先输出。
//最优解;双指针,左右夹逼
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
int l=0,r=array.length-1;
while(l<r){
int cur=array[l]+array[r];
if(cur==sum){
list.add(array[l]);
list.add(array[r]);
break;
}else if(cur<sum){
l++;
}else{
r--;
}
}
return list;
}
} import java.util.*;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
HashSet<Integer> set= new HashSet<>();
for(int i:array) set.add(i);
for(int i:array){
if(set.contains(sum-i)){
list.add(i);
list.add(sum-i);
break;
}
}
return list;
}
} 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length()<=n)return str;
StringBuilder sb= new StringBuilder();
char[] s=str.toCharArray();
sb.append(s,n,s.length-n);
sb.append(s,0,n);
return sb.toString();
}
}
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length()<=n)return str;
String left=str.substring(0,n);
String right=str.substring(n,str.length());
return right+left;
}
} public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length()<=n)return str;
return str.substring(n)+str.substring(0,n);
}
} 翻转单词顺序列
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
输入
"nowcoder. a am I"返回值
"I am a nowcoder."
public class Solution {
public String ReverseSentence(String str) {
if(str==null||str.length()==0) return str;
StringBuilder sb= new StringBuilder();
int len = str.length();
int l=0,r=len;
//反着添加
for(int i=len-1;i>=0;i--){
if(str.charAt(i)==' '){
l=i+1;
sb.append(str.substring(l,r));
sb.append(" ");
r=i;
}
}
sb.append(str.substring(0,r));//添加第一个单词
return sb.toString();
}
} //最优解 两次反转,如果可以操作字符串空间为O(1)
import java.util.*;
public class Solution {
public String ReverseSentence(String str) {
if(str==null||str.length()==0) return str;
char[] c=str.toCharArray();
for(int i=0,l=0;i<=c.length;i++){//<=length
if(i==c.length||c[i]==' '){//核心代码 到尾部或为空格,反转 ;判断尾必须在前
reverse(c,l,i-1);
l=i+1;
}
}
reverse(c,0,c.length-1);
return new String(c);
}
//反转函数
void reverse(char[] c,int l,int r){
while(l<r){
swap(c,l++,r--);
}
}
void swap(char[] c,int i,int j){
char temp= c[i];
c[i]=c[j];
c[j]=temp;
}
} 扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
示例1
输入
[0,3,2,6,4]返回值
true
必须满足两个条件
除0外没有重复的数
max - min < 5
牌数为5
//最简单解
//看一堆数是否连续,0可以代替任何数
//解法:查看除0以外最大数和最小数的差值,差值需小于数组长度
// 数组中如除零外有重复直接报错
import java.util.*;
public class Solution {
public boolean IsContinuous(int [] numbers) {
//特殊情况,直接返回false
if(numbers.length<1||numbers==null)return false;
//创建一个set
HashSet<Integer> set = new HashSet<>();
for(int i:numbers){
if(set.contains(i)){//重复报错
return false;
}else{//不存在,且不为0,装入
if(i!=0)set.add(i);
}
}
//比较差值与数组长度
return Collections.max(set)-Collections.min(set)<numbers.length?true:false;
}
} //较优解
import java.util.*;
public class Solution {
public boolean IsContinuous(int [] numbers) {
if(numbers.length<1||numbers==null)return false;
int zeroNum=0;//零个数
int gapNum=0;//间隙
Arrays.sort(numbers);
for(int i=0;i<numbers.length-1;i++){
if(numbers[i]==0){
zeroNum++;
continue;
}
if(numbers[i]==numbers[i+1]){
return false;
}
gapNum=gapNum+numbers[i+1]-numbers[i]-1;
}
if(gapNum>zeroNum){
return false;
}
return true;
}
} //烧脑解
import java.util.*;
public class Solution {
public boolean IsContinuous(int [] numbers) {
if(numbers.length<1||numbers==null)return false;
int min=14;//最小
int max=-1;//最大
int flag=0;//是否重复
for(int i=0;i<numbers.length;i++){
int n=numbers[i];
if(n<0||n>13)return false;//非法输入
if(n==0)continue;//不算0
//判断重复--二进制+位运算--想象成Boolean数组,0为false,1为true
if(((flag>>n)&1)==1)return false;//判断第n位是否为1
flag=flag|(1<<n);//将第n位置为1
//计算最大间隙
if(n>max)max=n;
if(n<min)min=n;
if(max-min>=numbers.length)return false;
}
return true;
}
} 约瑟夫环问题
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
示例1
输入
5,3返回值
3
public class Solution {
//找到状态转移方程式：
// f(n)=(f(n-1)+m)%n
public int LastRemaining_Solution(int n, int m) {
if(n<1||m<1) return -1;//异常判断
if(n==1)return 0;//终止条件
return (LastRemaining_Solution(n-1,m)+m)%n;
}
} public class Solution {
//找到状态转移方程式：
// f(n)=(f(n-1)+m)%n
//非递归版
public int LastRemaining_Solution(int n, int m) {
if(n<1||m<1) return -1;//异常判断
int re = 0;
for(int i=2;i<=n;i++){
re=(re+m)%i;//%i
}
return re;
}
} 求1+2+...+n（不能用乘除法、判断语句）
题目描述
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例1
输入
5返回
15
public class Solution {
// n*(n+1)/2
//不能用乘除法， (n平方+n)>>1
public int Sum_Solution(int n) {
int res = (int)Math.pow(n,2)+n;
return res>>1;
}
} public class Solution {
//递归
//终止条件不能用if写，用短路
public int Sum_Solution(int n) {
int res=n;
//当 n=0时，短路，不执行递归。直接到return res。 不为0时，执行递归操作
boolean flag = n>0 &&((res+=Sum_Solution(n-1))>0);
return res;
}
} 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
位运算题,注意积累. ^ & 常用
public class Solution {
//无进位和 a =a^b
//进位和 b =a&b
//进位 (a&b)<<1
//当进位和为0时，返回
public int Add(int num1,int num2) {
while(num2!=0){
int temp =(num1&num2)<<1;//拿一个变量存其中某一个值，因为同时对num1 num2操作
num1^= num2;
num2 = temp;
}
return num1;
}
} 把字符串转换成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
能以+ 、-开头,其他都得为数字
public class Solution {
public int StrToInt(String str) {
if(str==null||str.length()==0) return 0;
char[] ans = str.toCharArray();
int result=0;
for(int i=0;i<ans.length;i++){
if(i==0&&(ans[i]=='+'||ans[i]=='-')){
//0位可以为+或者-;注意短路写法
}else if(ans[i]<'0'||ans[i]>'9'){
return 0;//其他位不为数字直接返回不合法,0
}else{//注意当前位 :ans[i]-'0' ,直接减去0的ASCII码转化为int型
result=result*10+(ans[i]-'0');//正常整数直接相加
}
}
result=ans[0]=='-'?result*(-1):result;//判断正负
return result;
}
} 数组中的重复数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
涉及重复优先考虑hashset
import java.util.*;
//set去重,存在返回
public class Solution {
public int duplicate (int[] numbers) {
HashSet<Integer> set= new HashSet<>();
for(int i:numbers){
if(set.contains(i)) return i;//存在直接返回
set.add(i);
}
return -1;//存在不合法输入输出-1
}
} 最优解:空间O(1) 时间O(N) 因为题目的特殊性导致有最优解--原地替换
//题目的特殊性--数组长度 n 数字范围 0~n-1 如果全不同排序,一定会出现自己在自己数字下标位置.
//因此当数字不在自己应在位置时,将数字与自己数字下标数比较,不同就换
import java.util.*;
public class Solution {
/**
如果是找出任意一个不重复的数字 可以采用以下方法
遍历该数组 将每一个元素与下标的对应元素比较 如果不一致 那么交换两个元素的位置 直到出现该元素与对应的位置元素相同 即为重复的数字
这种方法不能查到第一个出现的原因是可能本来在最后重复的数字 被换到前面导致成为了先出现的
*/
public int duplicate (int[] numbers) {
int temp;
for(int i=0;i<numbers.length;i++){
//若第i位不在自己排序后的下标
while(i!=numbers[i]){
//将数字与自己下标的数字进行比较,一样则直接返回
if(numbers[i]==numbers[numbers[i]])return numbers[i];
//不一样则直接交换
temp=numbers[i];
numbers[i]=numbers[temp];
numbers[temp]=temp;
}
}
return -1;
}
} 构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]*A[i+1]...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
输入
[1,2,3,4,5]返回值
[120,60,40,30,24]
//最优解
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {// 2 3 4 5
int[] re = new int[A.length];
//先正着算一次,求出正三角形
re[0]=1;//先将0位赋值为1
for(int i=1;i<re.length;i++){// 1 2 2*3 2*3*4
re[i]=re[i-1]*A[i-1];
}
//再倒着算一次,求出倒三角形,再与正相乘(不包含自身)
int temp=1;//保存倒三角形
for(int i=A.length-2;i>=0;i--){ //1*3*4*5 2*4*5 2*3*5 2*3*4
temp*=A[i+1];//倒三角形
re[i]=re[i]*temp;//相差得到结果
}
return re;
}
} --正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与"aa.a"和"ab*a"均不匹配
示例1
输入
"aaa","a*a"返回值
true
//递归法
import java.util.*;
public class Solution {
public boolean match (String str, String pattern) {
if (pattern.length() == 0) return str.length() == 0;//终止条件
//当前位匹配
boolean match = (str.length() > 0 && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.'));// str>0时, 一对一匹配 或为'.'
//后续位匹配
if (pattern.length() > 1 && pattern.charAt(1) == '*') {// 有*
// 0个 || 多个
return match(str, pattern.substring(2)) || (match && match(str.substring(1), pattern));
// 匹配0个,模式串忽略*与当前位; *匹配多个的时候,首先得当前位匹配,注意短路写法
}else {// 无*
return match && match(str.substring(1), pattern.substring(1));//短路写法,继续匹配的前提是当前位匹配
}
}
} 动态规划版:
import java.util.*;
public class Solution {
public boolean match (String str, String pattern) {
//1.初始化
int m=str.length();
int n=pattern.length();
boolean dp[][]=new boolean[m+1][n+1];//用于存放两个空字符串的结果 dp[i][j] 表示模式串前j个是否与字符串前i个匹配
dp[0][0]=true; //两个为空,默认匹配
for(int j=1;j<=n;j++){//实际上模式串和字符串的起点为0(所以后面的下标都是i-1 j-1)
if(pattern.charAt(j-1)=='*'&&dp[0][j-2]){
dp[0][j]=true;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(str.charAt(i-1)==pattern.charAt(j-1)||pattern.charAt(j-1)=='.'){//正常匹配
dp[i][j]=dp[i-1][j-1];
}else if(pattern.charAt(j-1)=='*'){//有*存在时
if(dp[i][j-2]==true){//匹配0个
dp[i][j]=dp[i][j-2];
}else{//匹配多个
char pre=pattern.charAt(j-2);
if(pre==str.charAt(i-1)||pre=='.'){//匹配多个前,先得前一个字符匹配上
dp[i][j]=dp[i-1][j];
}
}
}
}
}
return dp[m][n];
}
} 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
输入
"123.45e+6"返回值
true输入
"1.2.3"返回值
false
import java.util.*;
public class Solution {
//常规题,但要考虑全面
public boolean isNumeric (String str) {
if(str==null||str.length()<1||str=="")return false;
char[] a = str.toCharArray();
boolean lsign=false,rsign=false,point=false,hasE=false;//小数点,e,e左右符号
int eIndex = a.length;//e出现的坐标
for(int i=0;i<a.length;i++){
if(a[i]=='+'||a[i]=='-'){//判断符号
if(i<eIndex){//e左边运算符只能有一个，并且只能在第一位
if (i!=0||lsign) return false;
lsign =true;
}else{//e右边运算符只能有一个,并且只能紧挨e后面
if(rsign||i-eIndex!=1) return false;
rsign=true;
}
}else if(a[i]=='.'){//小数点只能有一个，并且必须在e前面
if(point || i>eIndex) return false;
point = true;
}else if(a[i]=='e'||a[i]=='E'){//e只能有一个，并且不能在首位和末位
if(hasE||i==0||i==a.length-1) return false;
hasE = true;
eIndex = i;
}else if(a[i]<'0'||a[i]>'9'){//不能出现.+-.eE和数字以外的字符
return false;
}else{}//数字不处理,该行可以省略
}
return true;
}
} 字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
返回值描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
因为是流,然后返回第一个不重复. hashmap 和 队列
import java.util.*;
public class Solution {
//Insert one char from stringstream
HashMap<Character,Integer> map = new HashMap<>();
ArrayList<Character> queue = new ArrayList<>();
public void Insert(char ch)
{
if(map.containsKey(ch)){
int count=map.get(ch);
count++;
map.put(ch,count);
}else{
map.put(ch,1);
queue.add(ch);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
while(!queue.isEmpty()){
char first = queue.get(0);
if(map.get(first)==1){
return first;
}else{
queue.remove(0);
}
}
return '#';
}
} 因为只有字符,可以用类似位图 和 记录下标,省空间.
public class Solution {
int index =0; //index用于记录某个字符出现的位置
int[] a = new int[128];//按ASCII码存放每个字符出现的位置
{//初始化数组为-1，表示都未出现过
for(int i=0;i<a.length;i++) a[i]=-1;
}
public void Insert(char ch)
{ //若未出现过
if(a[ch]==-1){//arr[ch]和arr[(int)ch]是一样的,
a[ch]=index;
}else{//出现过置为-2,记为重复
a[ch]=-2;
}
index++;//坐标+1
}
public char FirstAppearingOnce()
{
int minIndex =Integer.MAX_VALUE;//记录第一个不重复坐标
char ch='#';
for(int i=0;i<a.length;i++){//不重复,且是第一个
if(a[i]>=0 && a[i]<minIndex){//找到最小的坐标,前提不重复且存在即大于0
minIndex=a[i];
ch=(char)i;
}
}
return ch;
}
} 链表环节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
//使用set求解,空间复杂度为O(N)
import java.util.*;
public class Solution {
HashSet<ListNode> set= new HashSet<>();
public ListNode EntryNodeOfLoop(ListNode pHead) {
while(pHead!=null){
if(set.contains(pHead))return pHead;
set.add(pHead);
pHead=pHead.next;
}
return null;
}
} //链表问题优先考虑双指针
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null||pHead.next==null) return null; //为空或只有一个 直接返回
ListNode f = pHead;
ListNode s = pHead;
//快指针到头,返回null
while(f!=null&&f.next!=null){//快指针不越界
f=f.next.next;
s=s.next;
if(f==s){//第一次相遇,说明有环
f=pHead;//将指针放到链表头
while(f!=s){//都走一步,直到相遇
f=f.next;
s=s.next;
}
return f;
}
}
return null;
}
} 删除链表中重复的节点
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输入
{1,2,3,3,4,4,5}返回值
{1,2,5}
//使用hashmap求解
import java.util.*;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
//用hashmap统计每个节点重复的次数
HashMap<Integer,Integer> map= new HashMap<>();
ListNode p = pHead;
while(p!=null){
if(map.containsKey(p.val)){
int count = map.get(p.val);
count++;
map.put(p.val,count);
}else{
map.put(p.val,1);
}
p=p.next;
}
//将重复的节点删除
//利用哨兵,可以简化操作,如第一个就是重复或者全是重复的情况
ListNode pre=new ListNode(0);
ListNode head=pre;
pre.next=pHead;
p=pHead;
while(p!=null){
if(map.get(p.val)>1){
pre.next=p.next;
p=pre.next;
}else{
pre=p;
p=p.next;
}
}
return head.next;
}
} //可以直接暴力求解,是最优解;但是对细节掌握的难度更大
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null || pHead.next==null) return pHead;
//设置哨兵,空指针，放置第一个和第二个相等的情况,现在这两个指针保证了不相等
ListNode empty = new ListNode(0);
empty.next=pHead;
ListNode pre = empty;
ListNode cur = pHead;
//核心代码,删除重复节点
while(cur!=null){
//如果下一个不为空,当前指针内容等于下一个,直接略过
if(cur.next!=null&&cur.val==cur.next.val){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
//直到不相等,停止
pre.next=cur.next//将pre.next直接移到不等的节点上
cur=cur.next;
}else{
//如果与下一个不等,两个指针顺移
pre=pre.next;
cur=cur.next;
}
}
return empty.next;
}
} 二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
//中序遍历:左根右
public class Solution {
TreeLinkNode GetNext(TreeLinkNode node){
if(node==null) return null;
if(node.right!=null){ //如果有右子树，则找右子树的最左节点
node = node.right;
while(node.left!=null){
node = node.left;
}
return node;
}
while(node.next!=null){ //没右子树，有父,则找第一个当前节点是父节点左孩子的节点
if(node.next.left==node) {//若为父的左孩子,返回父,即根
return node.next;
}
node = node.next;
}
return null; //退到了根节点仍没找到，则返回null;对应最右边的叶子节点情况
}
} 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null) return true; //空树判断
return same(pRoot.left,pRoot.right);//将左右进行是否相同比较
}
boolean same(TreeNode left,TreeNode right){
if(left==null&&right==null) return true;//左右为空,相同
if(left==null||right==null) return false;//只有一个空,不同
if(left.val!=right.val) return false;//值不同,不同 --不能值相同就返回相同,因为还要比较下一层子树是否相同
return same(left.left,right.right)&&same(left.right,right.left);//对称着比较,且需要都相同
}
} //相同写法2,改了一点代码
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null)return true;
return same(pRoot.left,pRoot.right);
}
boolean same(TreeNode left,TreeNode right){
if(left==null) return right==null;//当左为空,判断右是否为空
if(right==null)return left==null;//当为空,判断右是否为空
if(left.val!=right.val)return false;
return same(left.left,right.right)&&same(left.right,right.left);
}
} 按之字形打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
示例1
输入
{8,6,10,5,7,9,11}返回值
[[8],[10,6],[5,7,9,11]]
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
//层序遍历+判断行号
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
LinkedList<TreeNode> q = new LinkedList<>();
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
boolean rev= true;
q.add(pRoot);
while(!q.isEmpty()){//空节点也装入队列
int size =q.size();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode node=q.poll();
if(node==null){continue;}//空节点不装入list
if(rev){
list.add(node.val);
}else{
list.add(0,node.val);
}
q.offer(node.left);
q.offer(node.right);
}
if(list.size()!=0){res.add(list);}
rev=!rev;
}
return res;
}
} //二刷写法,此写法更简洁,队列不装入空节点
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(pRoot!=null) queue.add(pRoot);
int row = 1;//默认有1层
while(!queue.isEmpty()){//队列不装入空节点
ArrayList<Integer> list = new ArrayList<>();
for(int i=queue.size();i>0;i--){//技巧,每次输出一层时先将该层个数记录
TreeNode cur =queue.poll();
list.add(cur.val);
if(cur.left!=null) queue.add(cur.left);//只装非空,先左后右
if(cur.right!=null) queue.add(cur.right);
}
if((row&1)==0)Collections.reverse(list);//偶数层反转
res.add(list);
row++;
}
return res;
}
} 把二叉树打印成多行
层序遍历包括行号
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
输入
{8,6,10,5,7,9,11}返回值
[[8],[6,10],[5,7,9,11]]
//层序遍历
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(pRoot == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(pRoot);
while(!q.isEmpty()){//空节点不装入队列
int size = q.size();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode now = q.poll();
list.add(now.val);
if(now.left != null)
q.offer(now.left);
if(now.right != null)
q.offer(now.right);
}
res.add(list);
}
return res;
}
} //二刷,相同代码,略微改动 层序遍历
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(pRoot!=null) queue.add(pRoot);
while(!queue.isEmpty()){//空节点不装入队列
ArrayList<Integer> list = new ArrayList<>();
for(int i=queue.size();i>0;i--){
TreeNode cur =queue.poll();
list.add(cur.val);
if(cur.left!=null) queue.add(cur.left);
if(cur.right!=null) queue.add(cur.right);
}
res.add(list);
}
return res;
}
} 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
// 1
// 2 3
//4 5 6 7
// 1,2,4,#,#,5,#,#,3,6,#,#,7,#,#
// 0
public class Solution {
int index = -1; //记录当前序列化节点下标
//递归写法 前序遍历序列化
String Serialize(TreeNode root) {
if(root==null) return "#";
return root.val+","+Serialize(root.left)+","+Serialize(root.right);
}
//递归写法 反序列化
TreeNode Deserialize(String str) {
index++;
int len =str.length();
if(index>=len) return null;//终止条件
String[] strr=str.split(",");
TreeNode node = null;
if(!strr[index].equals("#")){//不为空，按前序遍历反序列化
//先处理根,再操作左右,前序遍历
node = new TreeNode(Integer.valueOf(strr[index]));
node.left=Deserialize(str);
node.right=Deserialize(str);
}
return node;
}
} 二叉搜索树的第k个节点
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
//中序遍历即为顺序的 空间O(N)
import java.util.*;
public class Solution {
ArrayList<TreeNode> list= new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k) {
getOrder(pRoot);
for(TreeNode i:list){
if(--k==0)
return i;
}
return null;
}
void getOrder(TreeNode pRoot){
if(pRoot==null)return ;
getOrder(pRoot.left);
list.add(pRoot);
getOrder(pRoot.right);
}
} //空间O(n)
import java.util.*;
public class Solution {
ArrayList<TreeNode> list= new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k) {
getOrder(pRoot);
if(k<1) return null; //k小于1,返回非法
if(k<=list.size())return list.get(k-1);
return null;//k大于数组长度,非法
}
void getOrder(TreeNode pRoot){
if(pRoot==null)return ;
getOrder(pRoot.left);
list.add(pRoot);
getOrder(pRoot.right);
}
} //递归法
public class Solution {
int count=0;
TreeNode node;
TreeNode KthNode(TreeNode pRoot, int k) {
if(k<1)return null;
getOrder(pRoot,k);
return node;
}
//中序遍历找第k
void getOrder(TreeNode pRoot, int k){
if(pRoot==null)return;//终止条件
getOrder(pRoot.left,k);//递归左子树
//此节点操作,判断是否为第k个节点
count++;
if(k==count){
node=pRoot;
return;
}
getOrder(pRoot.right,k);//右子树
}
} 数据流的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
import java.util.*;
public class Solution {
int cnt=0;
//小根堆放大数,大根堆放小数
PriorityQueue<Integer> low = new PriorityQueue<>();
PriorityQueue<Integer> high = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);
}
});
public void Insert(Integer num) {
cnt++;
//放前判断奇偶
if((cnt&1)==1){
//放入大根堆时,先放入小根堆中,再取小根堆的堆顶元素放入大根堆
if(!low.isEmpty()&&num>low.peek()){
low.offer(num);
num=low.poll();
}
high.offer(num);
}else{
//放入小根堆同理
if(!high.isEmpty()&&num<high.peek()){
high.offer(num);
num=high.poll();
}
low.offer(num);
}
}
public Double GetMedian() {
//取中位数时,判断奇偶
double res=0;
if((cnt&1)==1){
res = high.peek();
}else{
res =(high.peek()+low.peek())/2.0;
}
return res;
}
} //二刷,相同解法;写法更优
import java.util.*;
public class Solution {
Queue<Integer> low = new PriorityQueue<>();
Queue<Integer> high = new PriorityQueue<>((x,y)->(y-x));
//装入数
public void Insert(Integer num) {//先装小根堆的话,奇数取小根堆 堆顶
if(low.size()!=high.size()){//装大前,先装入小根堆,再取小根堆的 堆顶 到大根堆
low.add(num);
high.add(low.poll());
}else{
high.add(num);
low.add(high.poll());
}
}
//取中位数
public Double GetMedian() {//奇数,两个堆元素不等,取小 ;相等,取两个顶平均
return low.size()!=high.size()? (double)low.peek():(low.peek()+high.peek())/2.0;
//(double)本来可以省略,因为int转double,小转大,精度不缺失;但是牛客不强转会报错
}
} 滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空
输入
[2,3,4,2,6,2,5,1],3返回值
[4,4,6,6,6,5]
/**
用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if(num==null||num.length<1||size>num.length||size<1) return res;
ArrayDeque<Integer> q = new ArrayDeque<>();//双端队列,装每个最大值的下标
//核心代码
for(int i=0;i<num.length;i++){//将当前值的下标加入双端队列中
int begin= i+1-size;//窗口的左侧第一个下标
//队为空
if(q.isEmpty()) q.add(i);//为空时,先装入第一个下标
//如果最大值过期,直接删除
if(begin>q.peekFirst()){
q.pollFirst();
}
//队不为空时，新增当前值时,将小于它的值全部移除
while((!q.isEmpty())&&num[q.peekLast()]<=num[i])
q.pollLast();//删除小于的值
q.add(i);//添加新值
//窗口完整
if(begin>=0) res.add(num[q.peekFirst()]);//开始录入滑动窗口最大值
}
return res;
}
} 返回数组版
题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空
示例1
输入
[2,3,4,2,6,2,5,1],3返回值
[4,4,6,6,6,5]
//时间复杂度过大,只跑了85%的用例
import java.util.*;
public class Solution {
public int[] slidingwindowMax (int[] arr, int w) {
//异常判断
int len =arr.length;
int[] a = new int[0];
if(arr==null||arr.length<1||w>len)return a;
//双端队列存当前可能最大值下标
ArrayDeque<Integer> q = new ArrayDeque<>();
int len2=len-w+1;
int[] help = new int[len2];
int index = 0;//窗口的最左坐标
for(int i=0;i<arr.length;i++){
index =i+1-w;
if(q.isEmpty()) q.add(i);
//如果最大值过期,将最大值移除
if(index>q.peekFirst())q.removeFirst();
//添加元素,将比自己小的移除
while(!q.isEmpty()&&arr[q.getLast()]<=arr[i]) {
q.removeLast();
}
q.add(i);//添加
//当窗口完整时,取队首元素
if(index>=0) help[index]=arr[q.getFirst()];//边界值等于0,数组下标从0开始--!!
}
return help;
}
} 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 \begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ \end{bmatrix}\quad⎣⎡a*sabfdcceese*⎦⎤ 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例1
输入
"ABCESFCSADEE",3,4,"ABCCED"返回值
true
import java.util.*;
public class Solution {
public boolean hasPath (String matrix, int rows, int cols, String str) {
// 特殊情况返回
if(matrix==null||matrix.length()==0) return false;
if(str==null||str.length()==0)return true;
boolean[][] isUsed = new boolean[rows][cols];// 记录使用过的元素
for(int i=0;i<rows;i++)
for(int j=0;j<cols;j++){// 每个位置元素都开始一次
if(helper(i,j,0,matrix,str,isUsed))return true;
}
return false;
}
boolean helper(int row,int col,int curIndex,String matrix,String str,boolean[][] isUsed){
// 检查范围、检查是否走过该点，检查是否已经str对应的字符串是否到头
if(row<0||row>=isUsed.length||col<0||col>=isUsed[0].length||isUsed[row][col]||curIndex>=str.length())
return false;
//如果当前字符与矩阵该位置相等
if(str.charAt(curIndex)==matrix.charAt(row*isUsed[0].length+col)){
//如果是最后一个字符直接返回true，匹配成功
if(str.length()==curIndex+1) return true;
//其余则接着匹配，先将此点记为已走
isUsed[row][col]=true;
boolean result;
//上
result = helper(row-1,col,curIndex+1,matrix,str,isUsed);
if(result) return true;// 找到之后就不同向其他方向找，直接退出递归
//下
result=helper(row+1,col,curIndex+1,matrix,str,isUsed);
if(result) return true;
//左
result=helper(row,col-1,curIndex+1,matrix,str,isUsed);
if(result) return true;
//右
result=helper(row,col+1,curIndex+1,matrix,str,isUsed);
if(result) return true;
isUsed[row][col]=false;//不匹配则回溯
}
return false;
}
} 机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
示例1
输入
5,10,10返回值
21
public class Solution {
public int movingCount(int threshold, int rows, int cols) {
int flag[][] = new int[rows][cols];
return helper(0,0,rows,cols,flag,threshold);
}
int helper(int i ,int j,int rows,int cols,int[][] flag,int threshold){
//上下左右四个边界 行坐标和列坐标的数位之和大于k 已走过
if(i<0 || i>= rows || j<0||j>=cols||numSum(i)+numSum(j)>threshold||flag[i][j]==1)return 0;
flag[i][j]=1;//否则将此位置为1
//返回上下左右四个方向的数+当前这一步
return helper(i-1,j,rows,cols,flag,threshold)
+ helper(i+1,j,rows,cols,flag,threshold)
+ helper(i,j-1,rows,cols,flag,threshold)
+ helper(i,j+1,rows,cols,flag,threshold)
+ 1;
}
//坐标的数位之和
int numSum(int i){
//将当前数 各位数相加
int sum=0;
do{
sum+=i%10;
}while((i=i/10)>0);
return sum;
}
} 剪绳子
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:
输入一个数n，意义见题面。（2 <= n <= 60）返回值描述:
输出答案。示例1
输入
8返回值
18
//数学解法 当分解为e时最大；整数中3与e最近，所以尽量选3，一定最大
public class Solution {
public int cutRope(int target) {
if(target<0) return -1;//错误输入直接判断
//因为一定要分，所以不足分出3的返回此数-1
if(target <4 && target>0){
return target-1;
} //因为牛客测试用例较少,3-8行可以省略.没有小于3的用例
//核心代码
//假如为4，分成2与2,直接返回 4
//当大于4时，尽量分出3，并直接乘法
int max=1;
while(target>4){
target-=3;//分
max*=3;//乘
}
return max*target;
}
} 字符串变形
字符串变形
限定语言：Kotlin、Typescript、Python、C++、Groovy、Rust、C#、Java、Go、C、Scala、Javascript、Ruby、Swift、Php、Python 3
对于一个给定的字符串，我们需要在线性(也就是O(n))的时间里对它做一些变形。首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如"Hello World"变形后就变成了"wORLD hELLO"。
输入描述
给定一个字符串s以及它的长度n(1≤n≤500)输出描述
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。示例1
输入
"This is a sample",16输出
"SAMPLE A IS tHIS"
import java.util.*;
public class Solution {
public String trans(String s, int n) {
// write code here
if(s==null||s.length()<1||s=="")return "";
StringBuilder sb = new StringBuilder();
//反转
int start=0, end = n;
for(int i=n-1;i>=0;i--){
if(s.charAt(i)==' '){
start = i+1;
sb.append(s,start,end);
//添加字符数组最后一个参数是长度
//添加的是字符串参数是起始坐标和最终坐标,不包括最终坐标的左闭右开区间
sb.append(" ");
end=i;
}
}
//考虑第一个
sb.append(s,0,end);
//转大小写
// 97-65=32
char[] help = sb.toString().toCharArray();
for(int i=0;i<n;i++){
if(help[i]<='z'&&help[i]>='a'){
help[i]=(char)(help[i]-32);
}else if(help[i]<='Z'&&help[i]>='A'){
help[i]=(char)(help[i]+32);}
}
return new String(help);
}
} import java.util.*;
//方法2:利用split分割单词,来达到逆序
public class Solution {
public String trans(String s, int n) {
// write code here
if(s==null||s.length()<1||s=="")return "";
//转大小写
// 97-65=32
char[] help = s.toCharArray();
for(int i=0;i<n;i++){
if(help[i]<='z'&&help[i]>='a'){
help[i]=(char)(help[i]-32);
}else if(help[i]<='Z'&&help[i]>='A'){
help[i]=(char)(help[i]+32);}
}
String[] sh = new String(help).split(" ");
StringBuilder sb = new StringBuilder();
//反转
for(int i=sh.length-1;i>=0;i--){
sb.append(sh[i]);
if(i>0){
sb.append(" ");}
}
//考虑空格开头或者多个空格分隔情况,该解不能通过全部用例
//如果记录空格位置,然后再利用长度-位置算出倒序的位置,添加上空格.
return sb.toString();
}
} import java.util.*;
//方法3:两次反转,来达到逆序;如果语言可以直接操作字符串,空间度为O(1)
public class Solution {
public String trans(String s, int n) {
// write code here
if(s==null||s.length()<1||s=="")return "";
//转大小写
// 97-65=32
char[] help = s.toCharArray();
for(int i=0;i<n;i++){
if(help[i]<='z'&&help[i]>='a'){
help[i]=(char)(help[i]-32);
}else if(help[i]<='Z'&&help[i]>='A'){
help[i]=(char)(help[i]+32);}
}
//反转第一次,将各单词自身顺序逆序
for(int i=0,l=0;i<=help.length;i++){
if(i==help.length||help[i]==' '){
reverse(help,l,i-1);
l=i+1;
}
}
//第二次整体反转,达到题目效果
reverse(help,0,n-1);
return new String(help);
}
void reverse(char[] c,int l,int r){
while(l<r){
swap(c,l++,r--);
}
}
void swap(char[] c,int l,int r){
char temp =c[l];
c[l]=c[r];
c[r]=temp;
}
} 
查看8道真题和解析