判断链表有环
public class linkedListCycle {
public static boolean isCycle(Node head) {
Node p1 = head;
Node p2 = head;
while (p2!=null && p2.next!=null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
return true;
}
}
return false;
}
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) throws Exception {
Node node1 = new Node(5);
Node node2 = new Node(3);
Node node3 = new Node(7);
Node node4 = new Node(2);
Node node5 = new Node(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node2;
System.out.println(isCycle(node1));
}
}
最小数栈
import java.util.Stack;
public class MinStack {
private Stack mainStack = new Stack();
private Stack minStack = new Stack();
public void push(int element) {
mainStack.push(element);
//如果辅助栈为空，或新元素小于等于辅助栈栈顶，则新元素压入辅助栈
if (minStack.empty() || element <= minStack.peek()) {
minStack.push(element);
}
}
public Integer pop() {
//如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
if (mainStack.peek().equals(minStack.peek())) {
minStack.pop();
}
return mainStack.pop();
}
public int getMin() throws Exception {
if (mainStack.empty()) {
throw new Exception("stack is empty");
}
return minStack.peek();
}
public static void main(String[] args) throws Exception {
MinStack stack = new MinStack();
stack.push(4);
stack.push(9);
stack.push(7);
stack.push(3);
stack.push(8);
stack.push(5);
System.out.println(stack.getMin());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.getMin());
}
}
最大公约数
public class GreatestCommonDivisor {
public static int getGreatestCommonDivisor(int a, int b){
int big = a>b ? a:b;
int small = a1; i--){
if(small%i==0 && big%i==0){
return i;
}
}
return 1;
}
public static int getGreatestCommonDivisorV2(int a, int b){
int big = a>b ? a:b;
int small = ab ? a:b;
int small = a> 1, b >> 1)<<1;
} else if((a&1)==0 && (b&1)!=0){
return gcd(a >> 1, b);
} else if((a&1)!=0 && (b&1)==0){
return gcd(a, b >> 1);
} else {
int big = a>b ? a:b;
int small = a
2的幂
public class PowerOf2 {
public static boolean isPowerOf2(int num) {
int temp = 1;
while(temp<=num){
if(temp == num){
return true;
}
temp = temp*2;
}
return false;
}
public static boolean isPowerOf2V2(int num) {
int temp = 1;
while(temp<=num){
if(temp == num){
return true;
}
temp = temp<<1;
}
return false;
}
public static boolean isPowerOf2V3(int num) {
return (num&num-1) == 0;
}
public static void main(String[] args) {
System.out.println(isPowerOf2V3(32));
System.out.println(isPowerOf2V3(19));
}
}
最大有序距离
public class MaxSortedDistance {
public static int getMaxSortedDistance(int[] array){
//1.得到数列的最大值和最小值
int max = array[0];
int min = array[0];
for(int i=1; i max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
int d = max - min;
//如果max和min相等，说明数组所有元素都相等，返回0
if(d == 0){
return 0;
}
//2.初始化桶
int bucketNum = array.length;
Bucket[] buckets = new Bucket[bucketNum];
for(int i = 0; i < bucketNum; i++){
buckets[i] = new Bucket();
}
//3.遍历原始数组，确定每个桶的最大最小值
for(int i = 0; i < array.length; i++){
//确定数组元素所归属的桶下标
int index = ((array[i] - min) * (bucketNum-1) / d);
if(buckets[index].min==null || buckets[index].min>array[i]){
buckets[index].min = array[i];
}
if(buckets[index].max==null || buckets[index].max maxDistance) {
maxDistance = buckets[i].min - leftMax;
}
leftMax = buckets[i].max;
}
return maxDistance;
}
private static class Bucket {
Integer min;
Integer max;
}
public static void main(String[] args) {
int[] array = new int[] {2,6,3,4,5,10,9};
System.out.println(getMaxSortedDistance(array));
}
}
用栈实现队列
import java.util.Stack;
public class StackQueue {
private Stack stackA = new Stack();
private Stack stackB = new Stack();
public void enQueue(int element) {
stackA.push(element);
}
public Integer deQueue() {
if(stackB.isEmpty()){
if(stackA.isEmpty()){
return null;
}
transfer();
}
return stackB.pop();
}
private void transfer(){
while (!stackA.isEmpty()){
stackB.push(stackA.pop());
}
}
public static void main(String[] args) throws Exception {
StackQueue stackQueue = new StackQueue();
stackQueue.enQueue(1);
stackQueue.enQueue(2);
stackQueue.enQueue(3);
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
stackQueue.enQueue(4);
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
}
}
最近数字
import java.util.Arrays;
public class FindNearestNumber {
public static int[] findNearestNumber(int[] numbers){
//1.从后向前查看逆序区域，找到逆序区域的前一位，也就是数字置换的边界
int index = findTransferPoint(numbers);
//如果数字置换边界是0，说明整个数组已经逆序，无法得到更大的相同数字组成的整数，返回null
if(index == 0){
return null;
}
//2.把逆序区域的前一位和逆序区域中刚刚大于它的数字交换位置
//拷贝入参，避免直接修改入参
int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
exchangeHead(numbersCopy, index);
//3.把原来的逆序区域转为顺序
reverse(numbersCopy, index);
return numbersCopy;
}
private static int findTransferPoint(int[] numbers){
for(int i=numbers.length-1; i>0; i--){
if(numbers[i] > numbers[i-1]){
return i;
}
}
return 0;
}
private static int[] exchangeHead(int[] numbers, int index){
int head = numbers[index-1];
for(int i=numbers.length-1; i>0; i--){
if(head < numbers[i]){
numbers[index-1] = numbers[i];
numbers[i] = head;
break;
}
}
return numbers;
}
private static int[] reverse(int[] num, int index){
for(int i=index,j=num.length-1; i
删除整数的k个数字，获得删除后的最小值
public class RemoveKDigits {
public static String removeKDigits(String num, int k) {
for(int i=0; i num.charAt(j+1)){
num = num.substring(0, j) + num.substring(j+1,num.length());
hasCut = true;
break;
}
}
//如果没有找到要删除的数字，则删除最后一个数字
if(!hasCut){
num = num.substring(0, num.length()-1);
}
}
//清除整数左侧的数字0
int start = 0;
for(int j=0; j 0 && stack[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
//如果遇到数字0，且栈为空，0不入栈
if('0' == c && top == 0){
newLength--;
if(newLength <= 0){
return "0";
}
continue;
}
//遍历到的当前数字入栈
stack[top++] = c;
}
// 用栈构建新的整数字符串
return newLength<=0 ? "0" : new String(stack, 0, newLength);
}
public static void main(String[] args) {
System.out.println(removeKDigits("1593212", 3));
System.out.println(removeKDigits("30200", 1));
System.out.println(removeKDigits("10", 2));
System.out.println(removeKDigits("541270936", 3));
System.out.println(removeKDigits("1593212", 4));
System.out.println(removeKDigits("1000020000000010", 2));
}
}
大整数求和
public class BigNumberSum {
public static String bigNumberSum(String bigNumberA, String bigNumberB) {
//1.把两个大整数用数组逆序存储，数组长度等于较大整数位数+1
int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
int[] arrayA = new int[maxLength+1];
for(int i=0; i< bigNumberA.length(); i++){
arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
}
int[] arrayB = new int[maxLength+1];
for(int i=0; i< bigNumberB.length(); i++){
arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
}
//2.构建result数组，数组长度等于较大整数位数+1
int[] result = new int[maxLength+1];
//3.遍历数组，按位相加
for(int i=0; i= 10){
temp = temp-10;
result[i+1] = 1;
}
result[i] = temp;
}
//4.把result数组再次逆序并转成String
StringBuilder sb = new StringBuilder();
//是否找到大整数的最高有效位
boolean findFirst = false;
for (int i = result.length - 1; i >= 0; i--) {
if(!findFirst){
if(result[i] == 0){
continue;
}
findFirst = true;
}
sb.append(result[i]);
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(bigNumberSum("426709752318", "95481253129"));
}
}
获得金矿最优收益
public class GoldMining {
public static int getBestGoldMiningV3(int w, int[] p, int[] g){
//创建当前结果
int[] results = new int[w+1];
//填充一维数组
for(int i=1; i<=g.length; i++){
for(int j=w; j>=1; j--){
if(j>=p[i-1]){
results[j] = Math.max(results[j], results[j-p[i-1]]+ g[i-1]);
}
}
}
//返回最后一个格子的值
return results[w];
}
public static int getBestGoldMiningV2(int w, int[] p, int[] g){
//创建表格
int[][] resultTable = new int[g.length+1][w+1];
//填充表格
for(int i=1; i<=g.length; i++){
for(int j=1; j<=w; j++){
if(j
找到缺失的数字
public class FindLostNum {
public static int[] findLostNum(int[] array) {
//用于存储两个出现奇数次的整数
int result[] = new int[2];
//第一次整体异或
int xorResult = 0;
for(int i=0;i
