一、写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。
答案
import java.util.*;
public class Solution {
/**
* 反转字符串
* @param str string字符串
* @return string字符串
*/
public String solve (String str) {
if (str == null || str.length()==0 ) {
return str;
}
return new StringBuilder(str).reverse().toString();
}
}二、输入一个链表，反转链表后，输出新链表的表头。
答案
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode cur=head;
ListNode pre=null;
ListNode next=null;
//做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
//如此就可以做到反转链表的效果
//先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
while(cur!=null){
// 指向下一个位置
next=cur.next;
// 实际链表下一个为上一个
// 保存完next，就可以让head从指向next变成指向pre了，代码如下
cur.next=pre;
// 进行交换 指针后移
// head指向pre后，就继续依次反转下一个节点
// 让pre，head，next依次向后移动一个节点，继续下一次的指针反转
pre=cur;
cur=next;
}
return pre;
}
}三、计算并返回x的平方根（向下取整）
答案
public class Solution {
public int sqrt(int x) {
return (int) Math.sqrt(x);
}
}四、判断给定的链表中是否有环。如果有环则返回true，否则返回false
答案
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
//遍历链表的同时，让前一个节点的next指向head（或者是任意一个指定的内存），
//在后续的遍历中，如果有节点的当前next指向了head，则说明有环。
//破坏链表，达到最快
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode p = head;
while(p!=null){
ListNode aft = p.next;
if(aft==head)
return true;
p.next=head;
p=aft;
}
return false;
}
}快慢指针
public boolean hasCycle(ListNode head) {
if(head==null)
return false;
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow)
return true;
}
return false;
}五、一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
答案
public class Solution {
/**
1.假设当有n个台阶时假设有f(n)种走法。
2.青蛙最后一步要么跨1个台阶要么跨2个台阶。
3.当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。
4.当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2)种走法。
*/
//自顶向下，使用递归
public int jumpFloor(int target) {
if(target==1)
return 1;
else if(target==2)
return 2;
return jumpFloor(target-1)+jumpFloor(target-2);
}
}六、给定一个链表，请判断该链表是否为回文结构。
答案
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 使用栈结构将链表入栈存一遍，等于逆序链表
根据回文特性 正反一样 所以再出栈循环比对即可优化点，可以只比一半
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head==null){
return true;
}
Stack<ListNode> stack=new Stack<>();
ListNode index=head;
while(index!=null){
stack.add(index);
index=index.next;
}
index=head;
while(index!=null){
if(index.val!=stack.pop().val){
return false;
}
index=index.next;
}
return true;
}
}七、给定一个数组，请你编写一个函数，返回该数组排序后的形式。
答案
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
//调用库函数sort；
Arrays.sort(arr);
return arr;
}
}八、求给定二叉树的最大深度，最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。
答案
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 使用栈结构将链表入栈存一遍，等于逆序链表
根据回文特性 正反一样 所以再出栈循环比对即可优化点，可以只比一半
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head==null){
return true;
}
Stack<ListNode> stack=new Stack<>();
ListNode index=head;
while(index!=null){
stack.add(index);
index=index.next;
}
index=head;
while(index!=null){
if(index.val!=stack.pop().val){
return false;
}
index=index.next;
}
return true;
}
}九、给出一个整数数组，请在数组中找出两个加起来等于目标值的数。
你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
假设给出的数组中只存在唯一解
例如：
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2
答案
public class Solution {
public static int[] twoSum (int[] numbers, int target) {
int[] result = new int[2];
for(int i = 0; i < numbers.length; i++) {
for(int j = i+1; j < numbers.length; j++) {
if(numbers[i] + numbers[j] == target) {
//下标从1开始的所以+1
result[0] = i + 1;
result[1] = j + 1;
}
}
}
return result;
}
public static void main(String[] args) {
int[] num={20, 70, 110, 150};
int[] result=twoSum(num,90);
System.out.println(result[0]);
System.out.println(result[1]);
}
}十、JAVA实现两个线程交易打印奇数偶数。
答案
public class ThreadTest implements Runnable {
private static int i = 1;
//synchronized锁对象
private final Object o = new Object();
@Override
public void run() {
while (i <= 100) {
synchronized (o) {
System.out.println("我是" + Thread.currentThread().getName() + ",我打印出了" + i++);
//打印完成之后 唤醒另外一个线程
o.notify();
try {
//唤醒另外一个线程之后，调用wait() 释放synchronized锁 并进入blocking状态
//只有这样才能保证另外一个线程能获取到synchronized锁 并往下执行 实现交替打印
o.wait();
} catch (InterruptedException e) {
System.out.println("ERROR");
}
}
}
}
public static void main(String[] args) {
ThreadTest t = new ThreadTest();
Thread thread1 = new Thread(t, "线程1");
Thread thread2 = new Thread(t, "线程2");
thread1.start();
thread2.start();
}
}十一、java 统计字符串中每个字符出现的次数
答案
- 将字符串转换为字符数组
- 定义双列集合，存储字符串中字符和字符出现次数
- 遍历数组拿到每一个字符，并存储在集合中（存储过程需要做判断，如果集合中不包含这个键，键的值就为1，如果包含，键的值就在原来基础上加1）
import java.util.HashMap;
import java.util.Scanner;
public class vowel {
public static void main (String args[]){
Scanner input = new Scanner(System.in);
String s = input.nextLine();
//将字符串转换成字符数组
char[] arr = s.toCharArray();
//定义双列集合，存储字符串字符以及字符出现的次数
HashMap<Character,Integer> hm = new HashMap<>();
for(char c:arr){
//如果集合中不包含这个键，就将该字符当作键，值为1存储，如果集合中包含这个键，就将值增加1存储
if(!hm.containsKey(c))
hm.put(c, 1);
else
hm.put(c,hm.get(c)+1);
}
for (Character key : hm.keySet()) //hm.keySet()代表所有键的集合
System.out.println(key + "=" + hm.get(key)); //hm.get(key)根据键获取值
}
}十二、用两个栈实现队列
答案
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//压栈
public void push(int node) {
stack1.push(node);
}
//弹栈
public int pop() {
//将第一个栈中内容弹出放入第二个栈中
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
//第二个栈栈顶就是最先进来的元素，即队首
int result=stack2.pop();
//再将第二个栈的元素放回第一个栈
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return result;
}
}