算法数据结构复习
五一没有出去溜达，就待在宿舍里复习了算法相关知识，希望铜五能上岸吧！许愿一波大厂！
我将把这几天复习的算法相关知识做一个笔记分享出来，一个是为了以后的复习方便，一个是给需要的朋友做一个分享！希望大家相互监督相互鼓励共同进步，都能收到满意的offer!
经典排序篇
冒泡排序
public static int[] BubbleSortTest(int[] arr){
int flag=0; //如果一轮扫描后，发现没有要冒泡的那就直接退出
for(int i=1;i<arr.length;i++){//外循环从第二个开始
for(int j=0;j<arr.length-i;j++){
if(arr[j]>arr[j+1]){
int tem=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tem;
flag++;
}
}
if(flag==0){
break;
}
}
return arr;
} 归并排序
public static void sort(int[] arr, int l, int r, int[] tmp) {
if (r > l) {
int mid = (l + r) / 2;
sort(arr, l, mid, tmp);
sort(arr, mid + 1, r, tmp);
mergeSort(arr, l, mid, r, tmp);
}
}
//真正归并
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
System.out.print("Merge次数"); // 3, 4, 2, 1, -7, 0
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] > arr[j]) {
temp[t++] = arr[j++];
} else {
temp[t++] = arr[i++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
while (right >= left) {
arr[left++] = temp[t++];
}
} 插入排序
public static int[] InsertTest(int[] arr) {
for (int j = 1; j < arr.length; j++) {
int tar = arr[j]; //挑一个数，不断往前插入（打牌）
int count = j - 1;
while (count >= 0 && arr[count] > tar) {
arr[count + 1] = arr[count];
count--;
}
arr[count + 1] = tar;
}
return arr;
} 希尔排序
//与插入排序类似，不过一次往前挪jap个位置
public static int[] ShellSort(int[] arr) {
for (int jap = arr.length / 2; jap > 0; jap /= 2) {
for (int i = jap; i < arr.length; i++) {
int x = i;
while (x - jap >= 0 && arr[x] < arr[x - jap]) {
int tmp = arr[x];
arr[x] = arr[x - jap];
arr[x - jap] = tmp;
x = x - jap;
}
}
}
return arr;
} 快速排序
public static void QuickSort(int[] arr, int low, int high) {
int l = low;
int r = high;
if (l > r) {
return;
}
int tar = arr[l];
while (r > l) {
while (r > l && arr[r] > tar) {
r--;
}
arr[l] = arr[r];
while (r > l && arr[l] < tar) {
l++;
}
arr[r] = arr[l];
}
arr[l] = tar;
QuickSort(arr, low, l - 1);
QuickSort(arr, l + 1, high);
} 选择排序
public static int[] selectSort(int arr[]) {
for (int i = 0; i < arr.length; i++) {
int min = i; //找到最小的下标
for (int j = i + 1; j < arr.length; j++) { //自从i 之前的 肯定都是有序的 下一次找最小的值 就从 i之后开始查找
min = arr[j] > arr[min] ? min : j;
}
// 前面的值和最小的下标做交换
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
} 堆排序（寻找前K大）
// 学习使用堆 并排序返回
public static ArrayList<Integer> Solution(int[] arr, int k) {
if (arr.length < k) {
return new ArrayList<Integer>();
}
ArrayList<Integer> res =new ArrayList<Integer>();
//创建前K个数
int[] a = new int[k];
for (int i = 0; i < k; i++) {
a[i] = arr[i];
}
//前K个数 维持一个大根堆
for(int i=k/2 -1;i>=0;i--){
BigHeap(a,i,k);
}
//后面len - k个数 进入堆中维持一个大顶堆
for(int i=k;i<arr.length;i++){
if(arr[i]<a[0]){
a[0] = arr[i];
BigHeap(a,0,k);
}
}
//将大顶堆输出 就是堆排序
for(int i =a.length-1; i>=0;i--){
int tem=a[i];
a[i] =a[0];
a[0] =tem;
BigHeap(a,0,i);
}
for(int x:a){
res.add(x);
}
return res;
}
//维护这个堆（大根堆）
public static void BigHeap(int[] arr,int index ,int len){
int temp =arr[index];
for(int k = 2*index+1;k<len;k=2*k +1){
if((k+1)<len && arr[k+1] > arr[k]){
k++;
}
if(temp<arr[k]){
arr[index] =arr[k];
index=k;
}else{
break;
}
}
arr[index] =temp;
} 链表篇
K个一组反转链表
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=190&tqId=35192&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public ListNode reverseKGroup (ListNode head, int k) {
if(head==null||head.next==null||k==1){return head;}
ListNode res =new ListNode(0);
res.next=head;
int length=0;
listNode pre =res,cur =head,temp=null;
// 先知道链表长度，看看你需要分成几组进行反转
while(head!=null){
length++;
head=head.next;
}
//链表所有的操作都是从后面往前面维护
for(int i=0;i<length/k;i++){//分成length/k个组进行反转
for(int j=1;j<k;j++){ // 类似于头插法
temp=cur.next;
cur.next=temp.next;
temp.next=pre.next; //链表所有的操作都是从后面往前面维护
pre.next=temp;
}
pre=cur;
cur=cur.next;
}
return res.next;
}
LRU缓存结构
Least Recently Used (LRU 最近最少使用)
// 先定义类变量
HashMap<String,lrNode> map=new HashMap<>();//使用map存储双向链表
lrNode head;// 定义链表头
lrNode tail; //定义链表尾部
int capcity =3; //缓存的容量
//put方法
public void put(String key ,Object val){
// 如果链表为空，直接将头尾设置成该值
if(head==null){
head=new lrNode(key,val);
tail = head;
map.put(key,head);
}
//否则的话去map中看一下这个key存在否
lrNode node=map.get(key);
if(node!=null){
node.val=val;
removeAndInsert(node);
}else{
lrNode tmp=new lrNode(key,val);
//不存在，需要放进map中，放入前先判断容量是否满了
if(map.size()>=capcity){
map.remove(tail.key);
tail=tail.pre;
tail.next=null;
}
map.put(key,tmp);
tmp.next=head;
head.pre=tmp;
head=tmp;
}
//get 方法
public int get(String key ){
lrNode tmp=map.get(key);
if(tmp!=null){
return tmp.val;
removeAndInsert(tmp);
}else{
return -1;
}
}
}
// 将该节点放入头节点
public void removeAndInsert(lrNode node){
//如果本身是头节点那就直接返回
if(node==head){
return;
}else if(node ==tail ){
//删除尾节点
tail=tail.pre;
tail.next=null;
}else {
//中间节点 那也删除
node.next.pre =node.pre;
node.pre.next=node.next;
}
//删除完事了 ，然后插入到头节点
node.next=head;
node.pre=null;
head.pre=node;
head=node;
}
// 定义lrNode的数据结构
class lrNode(){
Object val;
String key ;
lrNode next;
lrNode pre;
lrNode(String key ,Object val){
this.key=key;
this.val=val;
}
} 两个链表第一个公共节点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public ListNode findFirstCommonNode(ListNode pHead1,ListNode pHead2){
if(pHead1==null||pHead2==null){return null;}
ListNode p1=pHead1;
ListNode p2=pHead2;
while(p1.val!=p2.val){
p1=p1.next;
p2=p2.next;
if(p1.val==p2.val){
return p1;
}
if(p1==null){
p1=pHead2;
}
if(p2==null){
p2=pHead1;
}
}
return p1;
}
两数相加
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode a=l1;
ListNode b=l2;
ListNode ans=new ListNode(0); //存储结果
ListNode tmp=ans;
int cary=0; //存储进位
while(a!=null||b!=null||cary!=0){
int m=a==null?0:a.val;
int n=b==null?0:b.val;
int sum =m+n+cary;
cary=sum/10;
int res=sum%10;
ListNode k=new ListNode(res);
tmp.next=k;
tmp=tmp.next;
if(a!=null){
a=a.next;
}
if(b!=null){
b=b.next;
}
}
return ans.next;
} 从尾到头打印链表
https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
{67,0,24,58}
返回值
[58,24,0,67]
static ArrayList<Integer> ans = new ArrayList<>();
//使用递归方式加入
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
System.out.println(listNode.val);
ans.add(listNode.val);
}
return ans;
} 删除倒数第K个节点
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=117&tqId=37750&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
给出的链表为: 1→2→3→4→5, n = 2 .
删除了链表的倒数第 n 个节点之后 ,链表变为 1→2→3→5.
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode cur = new ListNode(0);
cur.next = head;
ListNode one = cur;
ListNode two = cur;
while (n +1 != 0) { //因为前面给链表头加了头
one = one.next;
n--;
}
while (one != null) {
one = one.next;
two = two.next;
}
two.next = two.next.next;
return cur.next;
}
删除链表中重复的节点
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null) {
return pHead;
}
ListNode ans = new ListNode(0);
ans.next = pHead;
ListNode pre = ans;
ListNode last = ans.next; //试探指针
while (last != null) {
if (last.next != null && last.val == last.next.val) { //试探一下是否连续相等
while (last.next != null && last.val == last.next.val) {
last = last.next;
}
pre.next = last.next;
last = last.next;
} else {
pre = pre.next;
last = last.next;
}
}
return ans.next;
}
判断链表是否有环
public static boolean isLoopNodelist(ListNode head){
ListNode fast=head;
ListNode slow=head;
while(fast!=null&& fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast!=null&&fast.val==slow.val){
return true;
}
}
return false;
} 寻找第一个入环节点
https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId=117&tqId=37713&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode node = new ListNode(0);
node.next = head;
ListNode fast = node;
ListNode slow = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { //找到香蕉的点，然后快慢指针一起走
fast = node; //快指针从头开始，一次只走一步
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
} 单链表倒数第K个节点
https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=13&tqId=11167&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public ListNode FindKthToTail (ListNode pHead, int k) {
ListNode fast=pHead;
ListNode slow=pHead;
//需要特殊判断k比链表长度大的情况
while(k>0&& fast!=null){ //需要判断链表空了的时候 k值还比0大的情况 那就直接返回空了
fast=fast.next;
k--;
}
if(k>0){return null;}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
} 合并有序链表
https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=190&tqId=35188&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head=new ListNode(0);
ListNode ans =head; //定义指针，确保原链表不丢失
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
ans.next = l2;
l2 = l2.next;
} else {
ans.next = l1;
l1 = l1.next;
}
ans=ans.next;
}
if (l1 != null) {
ans.next=l1;
}
if(l2!=null){
ans.next=l2;
}
return head.next;
} 复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
//链表的数据结构
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
//给复制出来的节点授予指针
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> ans = new HashMap<>();
RandomListNode tmp = pHead;
while (tmp != null) {
RandomListNode res = new RandomListNode(tmp.label);
ans.put(tmp, res);
tmp = tmp.next;
}
tmp = pHead;
while (tmp != null) {
RandomListNode node = ans.get(tmp);
node.next = ans.get(tmp.next);
node.random = ans.get(tmp.random);
tmp = tmp.next;
}
return ans.getOrDefault(pHead, null);
} 逆序打印链表
public static ListNode reverseOrderListNode(ListNode head) {
if (head == null) {
return null;
}
// 1 4 3 ====> 3 4 1
ListNode p = new ListNode(0);
while (head != null) {
ListNode tmp = head.next;// 4 3
head.next = p.next; //
p.next = head;// null
head = tmp;
}
return p.next;
} 树篇
BFS层序遍历
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=190&tqId=35337&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
Queue<TreeNode> list = new LinkedList<>();
list.add(root);
while (list != null && list.size() != 0) {
int size = list.size();
ArrayList<Integer> tmp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = list.poll();
tmp.add(node.val);
if (node.left != null) {
list.add(node.left);
}
if (node.right != null) {
list.add(node.right);
}
}
ans.add(tmp);
}
return ans;
} 之字形打印二叉树
https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
if (pRoot == null) {
return ans;
}
Queue<TreeNode> list = new LinkedList<>();
int num = 0;
list.add(pRoot);
while (list != null && list.size() != 0) {
int count = list.size(); //放了几个节点
ArrayList<Integer> res = new ArrayList<>();
while (count != 0) { //输出一个父节点 就把左右孩子节点放入到队列中
//可以用for循环也可以用while循环，输出列表的的前size
TreeNode node = list.poll();
res.add(node.val);
if (node.left != null) {
list.add(node.left);
}
if (node.right != null) {
list.add(node.right);
}
count--; //记录放了几个节点
}
num++; //记录当前是多少层
if (num % 2 == 0) { //偶数层 从右往左
for (int i = 0, j = res.size() - 1; i < j; i++, j--) {
int tem = res.get(i);
res.set(i, res.get(j));
res.set(j, tem);
}
ans.add(res);
} else {
ans.add(res);
}
}
return ans;
} 二叉搜索树后续遍历
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
二叉搜索树特点：
左孩子最小，右孩子最大，根节点比左小，比右大
//将数组分割成两个序列，比根节点大的 和比跟节点小的
//然后记录一下各自第一个值的下标，用来判断是否连续；
public static boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length == 0) {
return false;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < sequence.length; i++) {
list.add(sequence[i]);
}
return solve(list);
}
private static boolean solve(ArrayList<Integer> list) {
// 递归终止的条件
if (list.size() == 0 || list.size() == 1) {
return true;
}
ArrayList<Integer> minList = new ArrayList<>(); // 用来保存小于endNumber数字的序列
ArrayList<Integer> maxList = new ArrayList<>(); // 用来保存大于endNumber数字的序列
int endNumber = list.get(list.size() - 1);
int minIndex = -1; // 用来记录minList中第一个数字的位置
int maxIndex = -1; // 用来记录maxList中第一个数字的位置
// 下面这个循环其实就是对当前list序列的一个分割(分割条件就是endNumber)
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > endNumber) {
if (maxIndex == -1) {
maxIndex = i; //记录第一个大于的下标
}
maxList.add(list.get(i));
} else if (list.get(i) < endNumber) {
if (minIndex == -1) {
minIndex = i;//记录第一个小于的下标
}
minList.add(list.get(i));
}
}
if (minIndex != -1 && maxIndex != -1) {
if (minIndex > maxIndex) {
return false; // 本质上使右子树的序列在左子树的前面，不满足后序遍历
}
for (int i = maxIndex; i < list.size(); i++) {
if (list.get(i) < endNumber) {
return false; // 说明在大于endNumber的序列初始位置到末尾，不连续，中间有小于endNumber的数字分割开来
}
}
}
return solve(minList) && solve(maxList); // && -> 每一个子序列都是需要满足的
} 二叉树中和为某值的路径
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ans = new ArrayList<>();
if (root == null) {
return ans;
}
ArrayList<Integer> list = new ArrayList<>();
resolve(root, 0, target, list);
ans.sort((o1,o2)->(o2.size()-o1.size()));
return ans;
}
private void resolve(TreeNode node, int sum, int target, ArrayList<Integer> list) {
if (node != null) {
sum += node.val;
list.add(node.val);
if (node.left == null && node.right == null) {
if (sum == target) {
ArrayList<Integer> res = new ArrayList<>(list);
ans.add(res);
} else {
resolve(node.right, sum, target, list);
resolve(node.left, sum, target, list);
}
//需要回溯
list.remove(list.size()-1);
}
} 二叉树先中后遍历
https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=190&tqId=35221&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
//得到二叉树的 深度 size
public static int getTreeSize(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + getTreeSize(node.left) + getTreeSize(node.right);
}
static int pre = 0, mid = 0, post = 0;
public static int[][] threeOrders(TreeNode root) {
// write code here
int treeSize = getTreeSize(root);
int[][] ans = new int[3][treeSize];
threeTree(root, ans);
return ans;
}
public static void threeTree(TreeNode node, int[][] arr) {
if (node == null) {
return;
}
arr[0][pre++] = node.val;
threeTree(node.left, arr);
arr[1][mid++] = node.val;
threeTree(node.right, arr);
arr[2][post++] = node.val;
}
二叉树最大深度
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=190&tqId=35335&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public int dfs(TreeNode node){
if(node==null){return 0;}
int left= 1+dfs(node.left);
int right=1+dfs(node.right);
return Math.max(left,right);
} 二叉树下一个节点
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
//主要是分为三种情况，第一种情况就是pNode节点有右孩子时，那么pNode的下一个节点就是右孩子对应的那颗子树的最左侧的节点；
// 如果说当前节点的右孩子为空，并且pNode是pNode父亲节点的左孩子，那么直接返回pNode的父亲节点即可；
// 如果说当前节点的右孩子为空，并且pNode是pNode父亲节点的右孩子那么就返回pNode节点的爷爷节点。
// 当然还有些特殊情况，比如说：二叉树的最右侧节点的判断，以及父亲节点是否为空的判断
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode.right != null) {
// 第一种情况，pNode节点的右孩子不为空 那么pNode的下一个节点就是右孩子对应的那颗子树的最左侧的节点；
pNode = pNode.right;
while (pNode.left != null) {
pNode = pNode.left;
}
return pNode;
} else {
TreeLinkNode tempNode = pNode.next;
if (tempNode == null) {
return null;
}
if (tempNode.left == pNode) {
// 第二种情况，当前节点右孩子为空，并且当前节点是父亲节点的左孩子
return tempNode;
} else {
// 第三种情况，当前节点右孩子为空，并且当前节点是父亲节点的右孩子
boolean flag = false;
while (tempNode.next != null) {
if (tempNode.next.left == tempNode) { //只要有一个路径 表示它在左边 那么就返回
flag = true;
break;
}
tempNode = tempNode.next;
}
return flag ? tempNode.next : null; // flag尾true时，说明pNode所指的节点不是二叉树中最右侧节点
}
}
}
}
class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
} 二叉树镜像
https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=13&tqId=11171&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot!=null){
if(pRoot.left!=null){
Mirror(pRoot.left);
}
if(pRoot.right!=null){
Mirror(pRoot.right);
}
TreeNode tmp=pRoot.left;
pRoot.left=pRoot.right;
pRoot.right=tmp;
}
return pRoot;
} 对称二叉树判断
https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
boolean resolve(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null || node2 == null) {
return false;
}
if (node1.val != node2.val) {
return false;
}
return resolve(node1.left, node2.right) && resolve(node1.right, node2.left);
} 判断平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
// 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
private int solve(TreeNode root) {
if (root == null) {
return 0;
}
if (ans) {
int leftsize = solve(root.left);
int rightsize = solve(root.right);
if (Math.abs(rightsize - leftsize) > 1) {
ans = false;
}
return Math.max(leftsize, rightsize)+1;
}
return 0;
} 树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
private boolean judge(TreeNode node1, TreeNode node2) { /// 第二部分，匹配
if (node2 == null) {
return true; /// 说明二叉树B的某一个方向的节点已经完全的匹配成功。
}
if (node1 == null) {
return false; /// 说明在某一方向上，二叉树A中的节点不缺少的，相对于二叉树B
}
if (node1.val == node2.val) {
boolean flag1 = true; /// 默认左子树是匹配的，假如说不匹配，它就会返回false
boolean flag2 = true; /// 默认右子树是匹配的，假如说不匹配，它就会返回false
if (node1.left != null || node2.left != null) {
flag1 = judge(node1.left, node2.left); /// 比较子树A和二叉树B的左子树
}
if (flag1 && (node1.right != null || node2.right != null)) { /// flag1 -> 剪枝
flag2 = judge(node1.right, node2.right); /// 比较子树A和二叉树B的右子树
}
return flag1 && flag2; /// && -> 不光某一个节点的左子树要完全匹配，右子树也是要完全匹配的
} else {
return false;
}
}
/// 二叉树的先序遍历
private boolean dfs(TreeNode node, TreeNode root2) { /// 第一部分，查找
boolean flag = false;
if (node.val == root2.val) {
flag = judge(node, root2); /// 进入第二部分的匹配过程
}
if (flag) {
return true; /// 通过当前节点已经找到二叉树B的完全匹配结果了，就没有必要再往下去遍历二叉树A了。也可以说是剪枝过程
}
boolean flag1 = false; /// 用来记录当前节点的左子树中的查找结果(其实也是包含了匹配的过程)，如果查找成功（包含了匹配过程）返回true
boolean flag2 = false; /// 用来记录当前节点的右子树中的查找结果(其实也是包含了匹配的过程)，如果查找成功（包含了匹配过程）返回true
if (node.left != null) {
flag1 = dfs(node.left, root2); /// 当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的左子树，看否找到二叉树B
}
if ((!flag1) && node.right != null) { /// !flag1-》剪枝
flag2 = dfs(node.right, root2); /// 当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的右子树，看否找到二叉树B
}
return flag1 || flag2; /// || -》只需要找到节点的某一个方向的子树进行匹配成功就行了
} 重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=190&tqId=35426&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
/**输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
int[] pre={1,2,3,4,5,6,7};
int[] in={3,2,4,1,6,5,7};
*/
public static TreeNode myDfs(int[] p,int pl,int pr,int[] in,int il,int ir){
if (pl>pr || il >ir){
return null;
}
TreeNode tree = new TreeNode(p[pl]);
int mid =0;
for(int i=0;i<=ir;i++ ){
if(tree.val==in[i]){
mid =i;
break;
}
}
int leftCount = mid -il;
int rightCount =ir -mid;
tree.left=myDfs(p,pl+1,pl+leftCount,in,il,mid-1);
tree.right=myDfs(p,pr-rightCount+1,pr,in,mid+1,ir);
return tree;
} 字符串篇
大数加法
public static String solve(String s, String t) {
StringBuilder ans = new StringBuilder();
int a = s.length() - 1;
int b = t.length() - 1;
int carry = 0;
while (a > 0 || b > 0 || carry != 0) {
int m = a < 0 ? 0 : s.charAt(a--)-'0'; //字符 需要-’0‘ 才能转换成数字
int n = b < 0 ? 0 : t.charAt(b--)-'0';
int sum = m + n + carry;
ans.append(sum % 10);
carry = sum / 10;
}
return ans.reverse().toString();
} 字符串全排列
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
static ArrayList<String> res = new ArrayList<String>();
public static ArrayList<String> Permutation(String str) {
ArrayList<String> ans = new ArrayList<String>();
char[] tmp = str.toCharArray();
reserve(tmp, 0, tmp.length );
ans=new ArrayList<String>(new HashSet<>(res));
Collections.sort(ans);
return ans;
}
public static void reserve(char[] arr, int index, int length) {
if (index == length) {
System.out.println(change(arr));
res.add(change(arr));
return;
}
for (int i = index; i < length; i++) {
char tem = arr[i];
arr[i] = arr[index];
arr[index] = tem;
reserve(arr, index + 1, length);
tem = arr[i]; // 其实就是去为了消除当前层去递归的时候的进行交换字符的影响，如果不消除的话，那么就会造成原index位置的字符发生变化
arr[i] = arr[index];
arr[index] = tem;
}
}
//将数组转换成字符串
public static String change(char[] arr) {
StringBuilder ans = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
ans.append(arr[i]);
}
return ans.toString();
} 字符串反转
https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public static String ReverseSentence(String str) {
if (str.length() == 0 || str == null) {
return str;
}
StringBuilder ans = new StringBuilder();
int len=str.length();
int l,r=len;
for(int i=len-1;i>=0;i--){
if(str.charAt(i)==' '){
l=i;
ans.append(str.substring(l+1,r));
ans.append(" ");
r=i;
}
}
ans.append(str.substring(0,r));
return ans.toString();
} 字符串消消乐
// 对字符串“ABBCADDDAC“进行逐步去重
public static void cutRepit(String str) {
if (str == null || str.length() == 0) {
return;
}
StringBuilder tmp = new StringBuilder(str);
StringBuilder ans = new StringBuilder();
Boolean same = false;
tmp.append(" ");
char tp = tmp.charAt(0);
for (int i = 1; i < tmp.length(); i++) {
if (tp == tmp.charAt(i)) {
same = true;
} else {
if (!same) {
ans.append(tp);
}
tp = tmp.charAt(i);
same = false;
}
}
if (ans.length()+1 < tmp.length()) {
System.out.println(ans.toString());
cutRepit(ans.toString());
}
} 字符串转换成数字
https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
//将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。
public int StrToInt(String str) {
if(str == null || str.length()<=0)
return 0;
char[] chars = str.toCharArray();
long num=0; //先用long来存储，以防止越界。换算出来的数可能整型溢出
boolean minus=false;
for(int i=0; i<chars.length; i++){
if(i==0 && chars[i]=='-'){
minus=true;
}else if(i==0 && chars[i]=='+'){
minus=false;
}else{
int a=(int) (chars[i]-'0');
if(a<0 || a>9){
return 0;
}
num= (minus==false) ? num*10+a : num*10-a;
if((!minus && num>Integer.MAX_VALUE)//Integer.MAX_VALUE 0x7FFFFFFF
||(minus && num<Integer.MIN_VALUE)){//Integer.MIN_VALUE 0x80000000
return 0;
}
}
}
return (int)num;
} 循环左移字符串
https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public static String LeftRotateString(String str, int n) {
if(str==null||str.length()==0){return "";}
int k = n % str.length();
char[] tmp = str.toCharArray();
StringBuilder ans=new StringBuilder();
for(int i=k;i<tmp.length;i++){
ans.append(tmp[i]);
}
for(int i=0;i<k;i++){
ans.append(tmp[i]);
}
return ans.toString();
} 最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117&tqId=37799&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
public static String LCS (String str1, String str2) {
// write code here
String result = "";
int start = 0;
int end = 1;
while(end<=str2.length()){
String subStr = str2.substring(start,end);
if(str1.contains(subStr)){
result = subStr;
}else{
start++;
}
end++;
}
return result;
} 最长字串NewCode
https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=190&tqId=35220&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
//给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
public static int maxLength(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int maxLength = 0;
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0 ; i < arr.length ; i++){
while (list.contains(arr[i])){
list.removeFirst();
}
list.add(arr[i]);
if (list.size() > maxLength){
System.out.println(list);
maxLength = list.size();
}
}
return maxLength;
} 有效括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117&tqId=37749&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
public static boolean isValid(String s) {
// write code here
if (s == null) return false;
Stack<Character> res = new Stack<>();
char[] arr = s.toCharArray();
for (char c : arr) {
if (c == '{') {
res.push('}');
} else if (c == '(') {
res.push(')');
} else if (c == '[') {
res.push(']');
} else {
if (res.isEmpty() || res.pop() != c) {
return false;
}
}
}
return res.isEmpty();
} 求平方根
https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=190&tqId=35187&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public static void main(String[] args) {
int sqrt = sqrt(8);
System.out.println(sqrt);
}
public static int sqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
long left = 0, right = x;
while (right > left) {
long mid = left + (right - left+1 ) / 2;
long square = mid * mid;
if (square == x) {
return (int) mid;
} else if (square > x) {
right = mid - 1;
} else {
left = mid;
}
}
return (int) left;
} 第一次只出现一次的字符位置
https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
public static void main(String[] args) {
String a = "google";
}
public int FirstNotRepeatingChar(String str) {
Map<Character, Integer> ans = new HashMap<>();
for(int i=0;i<str.length();i++){
ans.put(str.charAt(i),ans.getOrDefault(str.charAt(i),0)+1);
}
for(int i=0;i<str.length();i++){
if(ans.get(str.charAt(i))==1){
return i;
}
}
return -1;
} 数组篇
岛屿数量问题
/* 一个矩阵中只有0和1 每个位置都可以和自己的上下左右 四个位置相连
如果一片1 连在一起，这个部分叫做一个岛 求一个矩阵中有几个岛*/
//测试用例1
public static void main(String[] args) {
int[][] m1 = {
{0, 0, 1, 0, 1, 0},
{1, 1, 1, 0, 1, 0},
{1, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0}
};
int alent = alent(m1);
System.out.println(alent);
}
//获取岛屿数量
public static int alent(int[][] m) {
if (m.length == 0) {
return 0;
}
int M = m.length;
int N = m[0].length;
int res = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) { //循环所有
if (m[i][j] == 1) { //如果有岛屿 那么数量++ 然后将这一片都给感染掉 下次遍历的时候 就不进行岛屿数量++操作了
res++;
infect(m, i, j, M, N); //感染函数
}
}
}
return res;
}
//感染函数
private static void infect(int[][] m, int i, int j, int M, int N) {
if (i < 0 || i >= M || j < 0 || j >= N || m[i][j] != 1) {
return;
}
m[i][j] = 2;
infect(m, i + 1, j, M, N);
infect(m, i - 1, j, M, N);
infect(m, i, j + 1, M, N);
infect(m, i, j - 1, M, N);
} TwoSum
//leetcode第一题
public static int[] twoSum(int[] arr, int tar) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int j = 0; j < arr.length; j++) {
if (map.containsKey(tar - arr[j])) {
if (j != map.get(tar - arr[j])) {
return new int[]{j, map.get(tar - arr[j])};
}
}
}
return null;
}
三数之和
//链接：https://leetcode-cn.com/problems/3sum
/**给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。 **/
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);// -7, -1, 0, 4, 5, 8
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return ans;
}//-4 -1 -1 0 1 1 2
if (i > 0 && nums[i] == nums[i - 1]) { //上一次已经算过了 那就跳过 直接下一次循环
continue;
}
int L = i + 1;
int R = nums.length - 1;
while (R > L) {
int sum = nums[i] + nums[R] + nums[L];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[R], nums[L]));
while (R > L && nums[R] == nums[R - 1]) {
R--;
}
while (R > L && nums[L] == nums[L + 1]) {
L++;
}
R--;
L++;
} else if (sum > 0) {
R--;
} else if (sum < 0) {
L++;
}
}
}
return ans;
} 最长递增子序列
/**
* https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=117&&tqId=37796&&companyId=898&rp=1&ru=/company/home/code/898&qru=/ta/job-code-high/question-ranking
* 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
* <p>
* 输入：
* [2,1,5,3,6,4,8,9,7]
* <p>
* 返回值：
* [1,3,4,8,9]
*/
public class 最长递增子序列 {
public static void main(String[] args) {
int[] arr = {2, 1, 5, 3, 6, 4, 8, 9, 7};
int[] lis = LIS1(arr);
System.out.println(LIS1(arr));
}
/**
* 只求长度大小 不求完整数组的话
*/
public static int[] LIS(int[] arr) {
// write code here
if (arr.length == 0) {
return null;
}
if (arr.length == 1) {
return arr;
}
int[] dp = new int[arr.length];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
res = Math.max(dp[i], res);
}
// 只计算长度的话 那就是 5
System.out.println(res);
return dp;
}
/**
* 真正求完整数组的
*/
public static int[] LIS1(int[] arr) {
// write code here
if(arr == null || arr.length <= 0){
return null;
}
int len = arr.length;
int[] count = new int[len]; // 存长度
int[] end = new int[len]; // 存最长递增子序列
//init
int index = 0; // end 数组下标
end[index] = arr[0];
count[0] = 1;
for(int i = 0; i < len; i++){
if(end[index] < arr[i]){
end[++index] = arr[i];
count[i] = index;
}
else{
int left = 0, right = index;
while(left <= right){
int mid = (left + right) >> 1;
if(end[mid] >= arr[i]){
right = mid - 1;
}
else{
left = mid + 1;
}
}
end[left] = arr[i];
count[i] = left;
}
}
//因为返回的数组要求是字典序，所以从后向前遍历
int[] res = new int[index + 1];
for(int i = len - 1; i >= 0; i--){
if(count[i] == index){
res[index--] = arr[i];
}
}
return res;
}
}
乘积最大子数组
//请你找出数组中乘积最大的连续子数组
//https://leetcode-cn.com/problems/maximum-product-subarray/submissions/
//最小可能变最大，最大可能变最小
public static int maxProduct(int[] nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int mx = maxF, mn = minF;
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));//维护最大的值
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));//维护最小的值
ans = Math.max(maxF, ans);
}
return ans;
} 二分查找
//https://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395?tpId=117&tqId=37829&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
//从左到右，查找到第1个为4的，下标为2，返回2
//二分查找前提是有序（部分或者全部）
public static int search(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
int l = 0;
int r = nums.length - 1;
while (r > l) {
int tmp = l + (r - l) / 2;
if (nums[tmp] > target) {
r = tmp - 1;
} else if (nums[tmp] < target) {
l = tmp + 1;
} else {
r = tmp;
}
}
return nums[l] == target ? l : -1;
} 二维数组中的查找
//https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
/**在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，
输入这样的一个二维数组和一个整数，判断数组中是否含有该整数*/
//可以从左上角 或者右下角开始找
public static boolean Find(int target, int[][] array) {
int row = array.length - 1;
int column = array[0].length - 1;
int r = 0;
while (r <= row && column >= 0) {
if (target == array[r][column]) {
return true;
} else if (target > array[r][column]) {
r++;
} else {
column--;
}
}
return false;
} 和为S的两个数字
//https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
// 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
public ArrayList<Integer> FindNumber(int[] array, int sum) {
int l = 0;
int r = array.length - 1;
ArrayList<Integer> ans = new ArrayList<>();
while (r > l) {
int tmp = array[r] + array[l];
if (tmp > sum) {
r--;
} else if (tmp < sum) {
l++;
} else {
ans.add(array[l]);
ans.add(array[r]);
return ans;
}
}
return ans;
} 奇偶数组顺序问题
//https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=117&tqId=37776&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
//输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public static int[] reOrderArray(int[] array) {
// write code here
int[] arr = new int[array.length];
int nums=0;
//先求出奇数的个数
for(int n:array){
if(n%2!=0){
nums++;
}
}
int l = 0;
int r = nums;
for (int m : array) {
if (m % 2 != 0) {
arr[l++] = m;
} else {
arr[r++] = m;
}
}
return arr;
} 子数组最大和问题
/**
https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=190&tqId=35386&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据
[要求]
时间复杂度为O(n)，空间复杂度为O(1)
*/
public static int maxsumofSubarray(int[] arr) {
if (arr.length == 0 || arr == null) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int sum = arr[0];
int ans = 0;
for (int i = 1; i < arr.length; i++) {
if ((arr[i] + sum) > arr[i]) {
sum = arr[i] + sum;
if(sum>0){
res.add(arr[i]);
}
ans = Math.max(sum, ans);
} else {
sum = arr[i];
if(sum>ans){
res.clear();
res.add(arr[i]);
}
ans = Math.max(sum, ans);
}
}
return ans;
} 寻找峰值79
//leetcode 79题
/**峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，
在这种情况下，返回 任何一个峰值 所在位置即可。*/
//1、暴力法，直接遍历，只要后一个比前一个小，就是峰值
//2、使用二分思想
public static int findNum(int[] arr) {
return search(arr, 0, arr.length - 1);
}
public static int search(int[] arr, int l, int r) {
if (l == r) {
return l;
}
int mid = l + (r - l) / 2;
if (arr[mid] > arr[mid+1]) { //表示下降 那么峰值 一定在前面
return search(arr, l, mid);
} else {
return search(arr, mid + 1, r);
}
} 把数字排成最小的数
/*
https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组{3，32，321}，则
打印出这三个数字能排成的最小数字为321323。
[3,32,321]
返回值
"321323"
*/
public static String PrintMinNumber(int[] numbers) {
StringBuilder ans = new StringBuilder();
if (numbers.length == 0) {
return ans.toString();
}
ArrayList<String> tmp = new ArrayList<>();
for (int a : numbers) {
tmp.add(a+"");
}
//使用自定义比较器
tmp.sort((o1, o2) -> {
String a = o1 + o2;
String b = o2 + o1;
return a.compareTo(b);
});
for (String m : tmp) {
ans.append(m);
}
return ans.toString();
} 数字在升序数组中出现的次数
/*
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
[1,2,3,3,3,3,4,5],3
return 4
*/
public int GetNumberOfK(int[] array, int k) {
if (array.length == 0) return 0;
int firstPosition = findFirstPosition(array, k);
int lastPosition = findLastPosition(array, k);
if (array[firstPosition] != k) {
return 0;
}
//两个位置的差值（下标差值）
return lastPosition - firstPosition + 1;
}
//使用二分，找到该数字第一次出现的位置
private int findFirstPosition(int[] array, int k) {
int l = 0;
int r = array.length - 1;
while (r > l) {
int mid = (r + l) >> 1;
if (array[mid] == k) {
if (mid - 1 >= 0 && array[mid - 1] == k) {
r = mid - 1;
} else {
r = mid;
}
} else if (array[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
//使用二分，找到该数字最后出现的位置
private int findLastPosition(int[] array, int k) {
int l = 0;
int r = array.length - 1;
while (r > l) {
int mid = (r + l) >> 1;
if (array[mid] == k) {
if (mid + 1 < array.length && array[mid + 1] == k) {
l = mid + 1;
} else {
l = mid;
}
} else if (array[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
} 数组中出现次数超过一半的数字
/*
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
如果不存在则输出0。
*/
public static int MoreThanHalfNum_Solution(int[] array) {
Map<Integer,Integer> ans = new HashMap<>();
int target=0;
int sum=0;
for(int x:array){
ans.put(x,ans.getOrDefault(x,0)+1);
if(sum<ans.get(x)){
target=x;
sum=ans.get(x);
}
}
if(sum>array.length/2){
return target;
}else {
return 0;
}
} 数组中只出现一次的数字
/*
https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=13&tqId=11193&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
*/
public static int[] FindNumsAppearOnce(int[] array) {
int[] ans = new int[2];
if (array.length == 0) {
return ans;
}
Map<Integer, Integer> tmp = new HashMap<>();
for (int a : array) {
tmp.put(a, tmp.getOrDefault(a, 0) + 1);
}
int index = 0;
for (Map.Entry<Integer, Integer> a : tmp.entrySet()) {
if (a.getValue() == 1) {
ans[index++] = a.getKey();
}
}
return ans;
}
数组中的第K个最小元素
/** leetcode 92题
在未排序的数组中找到第 k 个最大的元素。
你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素*/
public static int findK1(int[] arr, int k) {
if (k > arr.length) {
return 0;
}
int[] arry = new int[k];
System.arraycopy(arr, 0, arry, 0, k);
for (int i = k / 2 - 1; i >= 0; i--) {
BigHeap(arry, i, k); //前K个数 构建大根堆
}
// 后面的所有的数 维护大根堆
for (int i = k; i < arr.length; i++) {
if (arr[i] < arry[0]) {
arry[0] = arr[i];
BigHeap(arry, 0, k);
}
}
return arry[0];//输出堆顶数字
}
//（调整成大根堆从最后一个非叶子节点开始，维护大根堆从第0个位置开始）
public static void BigHeap(int[] arr, int index, int len) {
int temp = arr[index];
for (int k = 2 * index + 1; k < len; k = 2 * k + 1) {
if (k + 1 < len && arr[k + 1] > arr[k]) {
k++;
}
if (temp < arr[k]) {
arr[index] = arr[k];
index = k;
} else {
break;
}
}
arr[index] = temp;
} 数组中的逆序对
/*
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。
即输出P%1000000007
*/
private static long sum;
public static int InversePairs(int[] array) {
int l = 0;
int r = array.length - 1;
divide(l, r, array);
System.out.println(sum);
return (int) (sum % 1000000007);
}
private static void divide(int l, int r, int[] array) {
if (r != l) {
int mid = (r + l) >> 1;
divide(l, mid, array);
divide(mid + 1, r, array);
merge(l, mid, r, array);
}
}
private static void merge(int l, int mid, int r, int[] arr) {
int[] ans = new int[r - l + 1];
int i = l;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= r) {
if (arr[i] > arr[j]) {
ans[index++] = arr[j++];
sum += mid - i + 1;
} else {
ans[index++] = arr[i++];
}
}
while (i <= mid) {
ans[index++] = arr[i++];
}
while (j <= r) {
ans[index++] = arr[j++];
}
index = 0;
while (r >= l) {
arr[l++] = ans[index++];
}
} 数组中重复的数字
/*
https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524?tpId=13&tqId=11203&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，
但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。
例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
*/
public static int duplicate(int[] numbers) {
if (numbers.length == 0) {
return -1;
}
HashSet<Integer> ans = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (ans.contains(numbers[i])) {
return numbers[i];
} else {
ans.add(numbers[i]);
}
}
return -1;
} 构建乘积数组
/*
https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=11204&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
给定一个数组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]
*/
public static int[] multiply(int[] A) {
int[] ans=new int[A.length];
for(int i=0;i<A.length;i++){
int res=1;
for(int j=0;j<A.length;j++){
if(i!=j){
res=res*A[j];
}
}
ans[i]=res;
}
return ans;
} 查找旋转数组最小值
public static void main(String[] args) {
int [] arr = {4,5,7,1,2,3}; //排序数组 切割后拼接到后面
// 暴力法 直接遍历
// int min=arr[2];
// for(int i=0;i<arr.length;i++){
// min=arr[i]<min?arr[i]:min;
// }
}
/**二分查找法*/
public static int BinarySearch(int[] arr){
if(arr.length==0){
return 0;
}
int l = 0;
int r=arr.length-1;
while(r>l){
int m =l+(r-l)/2;
if(arr[m]>arr[r]){ //中值比you侧大 那么最小值在 中值的右边
l = m+1; // 4 5 7 1 2 3
}else if(arr[m]<arr[r]){
r=m;
}else{ //有重复的值 那么不断往左边靠
r--;
}
}
return arr[r];
} 滑动窗口最大值
/*
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
通过记录之前保存的窗口中的最大值和最大值的下标来去更新当前窗口的最大值，分为两种情况，
第一种情况：之前最大值还在当前数组中，那么就去比较当前区间的右端点和之前记录的最大值即可。
第二种情况：之前保存的最大值不在当前区间，那么就从当前区间的左端点遍历到右端点在重新的找到一个最大值就行了
*/
public static ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ans = new ArrayList<Integer>();
if (size > num.length || num == null || num.length == 0 || size == 0) {
return ans;
}
int max = num[0];
int pos = 0;
// 寻找第一个窗口中的最大值
for (int i = 0; i < size; i++) {
if (max < num[i]) {
max = num[i];
pos = i;
}
}
ans.add(max); //放入结果中
for (int i = size; i < num.length; i++) {
if (i - size + 1 <= pos) {// 新窗口的第一个值 是否在最大值的下标前面
if (num[i] > max) { //在的话 判断新加入的第一个值 是否比最大值大
max = num[i];
pos = i;
}
} else { //否则的话需要重写选举出最大值 上一个最大值已经滑过了
max = num[i - size + 1]; //重新选举最大值 需要进行初始化
for (int j = i - size + 1; j <= i; j++) {
if (num[j] > max) {
max = num[j];
pos = j;
}
}
}
ans.add(max);
}
return ans;
} 矩阵中的路径
/*
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&tqId=11218&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子
y --->
x [[a,b,c,e],
| [s,f,c,s],
| [a,d,e,e]],
"abcced"
true
*/
public boolean hasPath(char[][] matrix, String word) {
boolean[][] flag = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (solve(matrix, word, i, j, flag, 0)) {
return true;
}
}
}
return false;
}
private boolean solve(char[][] matrix, String word, int x, int y, boolean[][] flag, int index) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || flag[x][y]) {
return false;
}
if (matrix[x][y] != word.charAt(index)) {
return false;
}
if (index == word.length() - 1) {
return true;
}
flag[x][y]=true;
boolean fl= solve(matrix, word, x+1, y, flag,index+1)||
solve(matrix, word, x-1, y, flag,index+1)||
solve(matrix, word, x, y+1, flag,index+1)||
solve(matrix, word, x, y-1, flag,index+1);
flag[x][y]=false;
return fl;
} 路径和问题
/*
https://leetcode-cn.com/problems/unique-paths/description/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public static int uniquePaths(int m, int n) {
int[][] ans = new int[m][n];
for (int i = 0; i < m; i++) {
ans[i][0] = 1;
}
for (int i = 0; i < n; i++) {
ans[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
}
}
return ans[m - 1][n - 1];
} 顺时针打印矩阵
/*
https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字
y---->
x 1,2,3,4,
| 8,12,16,15,
| 14,13,9,5,
6,7,11,10.
*/
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> ans = new ArrayList<>();
int flag = 1;// 1->right, 2->down, 3->left, 4->up
int x = 0;
int y = 0;
boolean[][] vis = new boolean[matrix.length][matrix[0].length]; // 这个就是用来标记已经走过的点
while (ans.size() < matrix.length * matrix[0].length) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || vis[x][y]) { // vis[x][y] -> 已经遍历过的位置也当作越界处理
if (flag == 1) {
flag = 2; // 往下走
y--; // 消除越界的影响
x++; // 本质上就是到达下一个位置的横坐标
} else if (flag == 2) {
flag = 3; // 往左走
x--; // 消除越界的影响
y--; // 本质上就是到达下一个位置的纵坐标
} else if (flag == 3) {
flag = 4; // 往上走
y++; // 消除越界的影响
x--; // 本质上就是到达下一个位置的横坐标
} else {
flag = 1;//往右走
x++; // 消除越界的影响
y++; // 本质上就是到达下一个位置的纵坐标
}
} else {
ans.add(matrix[x][y]);
vis[x][y] = true; // 去标记已经遍历过的位置
// 根据flag的值更新遍历矩阵的下标x，y的值
if (flag == 1) {
y++;
} else if (flag == 2) {
x++;
} else if (flag == 3) {
y--;
} else {
x--;
}
}
}
return ans;
} 数字篇
不用加减乘除做加法
/*
https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
输入
复制
1,2
返回值
复制
3
*/
public int Add(int num1,int num2) {
int sum1, sum2;
do{
sum1 = num1 ^ num2;
sum2 = (num1 & num2) << 1;
num1 = sum1;
num2 = sum2;
}while (num2 != 0);
return num1;
} 丑数
/*
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
*/
public static int GetUglyNumber_Solution(int index) {
if(index==0){
return 0;
}
int[] ans = new int[index];
int index1 = 0;
int index2 = 0;
int index3 = 0;
ans[0] = 1;
for (int i = 1; i < index; i++) {
ans[i] = Math.min(ans[index1] * 2, Math.min(ans[index2] * 3, ans[index3] * 5));
if (ans[i] == ans[index1]*2) {
index1++;
}
if (ans[i] == ans[index2]*3) {
index2++;
}
if (ans[i] == ans[index3]*5) {
index3++;
}
}
return ans[index - 1];
} 二进制中1的个数
/*
https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
*/
public static int NumberOf1(int n) {
int res=0;
// while(n!=0){
// res=res+(n&1);
// n=n>>>1;
// }
while(n!=0){
res++;
n=n&(n-1);
}
return res;
} 变态跳台阶
/*
https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
*/
public static int jumpFloorII(int target) {
if (target <= 1) {
return target;
}
int[] ans = new int[target + 1];
int sum = 1;
for (int i = 2; i <= target; i++) {
ans[i] = sum + 1; //第i阶 等于第i-1阶的情况加上 从起点直接跳到i的情况（需要+1）
sum = sum + ans[i]; //更新1到第i阶的情况（记录走到当前阶 的所有步数）
}
System.out.println(sum);
return ans[target];
} 变种跳台阶--II
/**
* 1、有n阶台阶 可以一次跳a步，也可以一次跳b步 求所有的走法
* n=11 a=3 b=5
* 输出：
* 335 533 353
*/
public static void jump(int[] arr, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> ans) {
if (target < 0) {
return;
}
if(target==0){
ans.add(new ArrayList<>(path));
return;
}
for(int i=0;i<arr.length;i++){
path.add(arr[i]);
int sum = target-arr[i];
jump(arr,sum,path,ans);
path.remove(path.size()-1);
}
} 和为S的正数序列
/*
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,
他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你
能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输入
9
返回值
[[2,3,4],[4,5]]
*/
public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
//存放结果
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow = 1,phigh = 2;
while(phigh > plow){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur = (phigh + plow) * (phigh - plow + 1) / 2;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=plow;i<=phigh;i++){
list.add(i);
}
result.add(list);
plow++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur < sum){
phigh++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
}
return result;
} 孩子们的游戏
/*
https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,
然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,
继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,
并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,
哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
*/
public static void main(String[] args) {
LastRemaining_Solution(5,3);
}
public static int LastRemaining_Solution(int n, int m) {
if (n < 1 || m < 1) return -1;
int[] array = new int[n];
int i = -1, step = 0, count = n;
while (count > 0) { //跳出循环时将最后一个元素也设置为了-1
i++; //指向上一个被删除对象的下一个元素。
if (i >= n) { //模拟环。
i = 0;
}
if (array[i] == -1) {
continue;
} //跳过被删除的对象。
step++; //记录已走过的。
if (step == m) { //找到待删除的对象。
array[i] = -1;
step = 0;
count--;
}
}
return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
} 快乐数
/*
*https://leetcode-cn.com/problems/happy-number/solution/kuai-le-de-zhi-shi-dian-zeng-jia-liao-by-sweetiee/
* 输入: 19
* 输出: true
* 解释: 1*1+9*9=82
* 8*8 + 2*2 = 68
* 6*6 + 8*8 = 100
* 1*1 + 0*0 + 0*0 = 1
**/
public int squareSum(int n) {
int sum = 0;
while(n > 0){
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
public boolean isHappy(int n) {
//类似快慢指针
int slow = n, fast = squareSum(n);
while (slow != fast){
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
};
return slow == 1;
} 扑克牌顺子
/*
https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
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。
[0,3,2,6,4]
返回值
true
*/
// 先去统计出数组中0的个数，然后在对数组排序，最后判断数组中相邻两个位置之间是否需要0填充以及0的个数是否够用即可
public static boolean IsContinuous(int[] numbers) {
if (numbers.length == 0) {
return false;
}
int sum=0;
for(int x:numbers){
if(x==0){
sum++;
}
}
Arrays.sort(numbers);
for(int i=sum+1;i<numbers.length;i++){
sum-=numbers[i]-numbers[i-1]-1;
if(sum<0||numbers[i]==numbers[i-1]){
return false;
}
}
return true;
} 数字的整数次方
/*
https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
*/
public static double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
double ans = 1;
int ex = exponent >= 0 ? exponent : -exponent;
for (int i = 0; i < ex; i++) {
ans = ans * base;
}
if (exponent > 0) {
return ans;
} else {
return 1 / ans;
}
} 数据流中的中位数
/*
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，
使用GetMedian()方法获取当前读取数据的中位数。
*/
private PriorityQueue<Integer> queue1 = new PriorityQueue<>(((o1, o2) -> (o2 - o1))); // 中位数的左区间 > 大顶堆
private PriorityQueue<Integer> queue2 = new PriorityQueue<>(); // 中位数的右区间 > 小顶堆
private int sum = 0; // 数据流中个数
public void Insert(Integer num) {
if (sum % 2 == 0) { // 1 2 3 4 5
// 当两个堆的元素个数一样的时候，此时新增一个元素，放入大顶堆(左区间)
queue1.add(num);
} else {
queue2.add(num);
}
if (!queue2.isEmpty() && queue1.peek() > queue2.peek()) {
int temp1 = queue1.poll();
int temp2 = queue2.poll();
queue1.add(temp2);
queue2.add(temp1);
}
sum++;
}
public Double GetMedian() {
if (sum % 2 == 1) {
return (double) queue1.peek();
} else {
return (queue1.peek() + queue2.peek()) / 2.0;
}
} 整数中1出现的次数
/*
https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,
可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
*/
public int NumberOf1Between1AndN_Solution(int n) {
if(n==0){return 0;}
int sum = 1;
for (int i = n; i >= 1; i--) {
int m = i;
while (m > 9) {
if (m % 10 == 1) {
sum++;
}
m = m / 10;
if(m==1) {
sum++;
}
}
}
return sum;
} 机器人的运动范围
/*
https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），
因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
请问该机器人能够达到多少个格子？
输入
5,10,10
返回值
21
*/
int sum=0;
public int movingCount(int threshold, int rows, int cols) {
sum=0;
boolean[][] vis = new boolean[rows][cols];
solve(0, 0, rows, cols, vis, threshold);
return sum;
}
//计算当前位置是否能到达
private int cule(int x,int y){
int res=0;
while(x!=0){
res+=x%10;
x=x/10;
}
while(y!=0){
res+=y%10;
y=y/10;
}
return res;
}
private void solve(int x, int y, int rows, int cols, boolean[][] vis, int k) {
if(x<0||y<0||x>=rows||y>=cols||vis[x][y]||cule(x,y)>k){
return ;
}
vis[x][y]=true;
sum++;
solve( x-1, y, rows, cols, vis, k);
solve( x+1, y, rows, cols, vis, k);
solve( x, y-1, rows, cols, vis, k);
solve( x, y+1, rows, cols, vis, k);
} 跳台阶
public static int Jump3(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
} 栈篇
两个栈实现队列
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
// 入栈 直接入
//如果你要出栈 自己出 为空了 那就找我要 我一次全部给你
public void push(int node) {
stack1.push(node);
}
public int pop() {
//出
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
} 包含Min函数的栈
/*
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
*/
Stack<Integer> data = new Stack<>();
Stack<Integer> min = new Stack<>();
public void push(int node) {
if (min.isEmpty()) {
min.push(node);
} else {
if (min.peek() > node) {
min.push(node);
} else {
min.push(min.peek());
}
}
data.push(node);
}
public void pop() {
data.pop();
min.pop();
}
public int top() {
return data.peek();
}
public int min() {
return min.peek();
} 栈的压入弹出顺序
/*
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。
（注意：这两个序列的长度是相等的）
*/
public static void main(String[] args) {
int[] t1 = {1, 2, 3, 4, 5};
int[] t2 = {4, 5, 3, 2, 1};
boolean b = IsPopOrder(t1, t2);
System.out.println(b);
}
public static boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA.length == 0 || popA.length == 0 || popA.length != pushA.length) {
return false;
}
Stack<Integer> ans = new Stack<>();
int popindex = 0;
for (int i = 0; i < pushA.length; i++) {
ans.push(pushA[i]);
while (!ans.isEmpty() && ans.peek() == popA[popindex]) {
ans.pop();
popindex++;
}
}
return ans.isEmpty();
} 
查看15道真题和解析