一 、基本数据类型
1.A+B问题
public class Solution {
/**
* @param a: An integer
* @param b: An integer
* @return: The sum of a and b
*/
public int aplusb(int a, int b) {
return a+b;
}
}
2.反转一个三位整数
public int reverseInteger(int number) {
if(number>=100 && number<1000){
int a = number%10;
int b = number/10%10;
int c = number/100%10;
return a*100+b*10+c;
}
return -1;
}
3.计算圆周长和面积
public double[] calculate(int r) {
double[] a = new double[2];
a[0] = 2 * 3.14 * r;
a[1] = 3.14 * r * r;
return a;
}
4.巴什博弈
public boolean canWinBash(int n) {
// Write your code here
return n%4!=0;
}
1+3=4；只要最后对方拿时，剩余石头数是4，则我方必赢，因为无论对方拿几，我方都能一次拿完；
题目变为：n能不能变为4，由此发现只要我们首次取n%4个石头，对方就会从4的倍数开始取（因为我们取走了余数，剩余一定被4整除），那么接下来，无论对方取几（1,2,3都不大于4），我们总能让对方一直处于4的倍数状态，直到获胜，
因此题目最终变为：n能否被4整除；如不能则我方获胜，如果能则我方失败；
二、判断语句
5.判断数字与字母字符
public boolean isAlphanumeric(char c) {
// write your code here
// return Character.isLetter(c) || Character.isDigit(c);
return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z')|| (c >= 'a' && c <= 'z');
}
6.闰年
public boolean isLeapYear(int n) {
return (n % 4 == 0 && (n % 100 != 0 || n % 400 == 0));
}
7.大小写转换
解题思路
ASCII编码表中，A=65，a=97，以此类推，每个小写字母与大写字母间隔32，所以小写字母转大写字母，直接小写字母-32就ok，大写字母转小写字母的话就+32，毕竟人家表上写的好好的，对照着用呗。
public char lowercaseToUppercase(char character) {
// write your code here
return character -= 32;
}
8.月份天数
public int getTheMonthDays(int year, int month) {
int[] day = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
if (month == 2) {
if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
return 29;
}
}
return day[month];
}
9.简单计算器
public int calculate(int a, char operator, int b) {
// write your code here
switch (operator) {
case '*':
return a * b;
case '/':
return a / b;
case '-':
return a - b;
default:
return a + b;
}
}
10.三数之中的最大值
public int maxOfThreeNumbers(int num1, int num2, int num3) {
// write your code here
int a=num1>num2?num1:num2;//a为num1henum2中最大值
return a>num3?a:num3;
}
三、数组和循环
11.打印X
public List<String> printX(int n) {
ArrayList<String> res=new ArrayList<>();//创建一个存放String类型属性的ArrayList，名称为res
char[] line=new char[n];//创建一个长度为n的字符型数组line
for(int i=0;i<n;i++){//外循环遍历正整数n的次数
for(int j=0;j<n;j++){//该循环为了辅助初始化字符型数组中的每个属性
line[j]=' ';//初始化字符型数组中的每个属性
}
line[i]='X';//左边对应位置赋值"X“
line[n-i-1]='X';//右边对应位置赋值“X”
res.add(String.valueOf(line));//将得到的line转换成字符串的形式增加到ArrayList
}
return res;//返回ArrayList
}
12.数组的最大值
public float maxOfArray(float[] A) {
// write your code here
float max = A[0];
for(int i = 0;i < A.length;i++){
if(max < A[i]){
max = A[i];
}
}
return max;
}
13.生成给定大小的数组
public List<Integer> generate(int size) {
// write your code here
List<Integer> list = new ArrayList<>(size);
for(int i = 0;i < size;i++){
list.add(i+1);
}
return list;
}
14.移动零
算法：双指针
算法思路
使用两个指针right和left，left为新数组的指针，right为原数组的指针，原数组指针向后扫，遇到非0的数就赋值给新数组的指针位置，并将新数组指针向后移动
代码思路
将两个指针先指向0，即数组头部
right向后扫描，当遇到非0数即nums[right] != 0时，将其赋值给新数组指针指向的位置，即nums[left] = nums[right]，并将left向后移动一位
若新数组指针还未指向尾部，即剩余的位置都是0，将剩余数组赋值为0
复杂度分析
N表示数组nums长度
空间复杂度：O(1)
时间复杂度：O(N)
public void moveZeroes(int[] nums) {
//将两个指针先指向数组头部
int left = 0, right = 0;
while (right < nums.length) {
// 遇到非0数赋值给新数组指针指向的位置
if (nums[right] != 0) {
nums[left] = nums[right];
// 将left向后移动一位
left++;
}
right++;
}
// 若新数组指针还未指向尾部，将剩余数组赋值为0
while (left < nums.length) {
nums[left] = 0;
left++;
}
}
15.寻找最大值
public int maxNum(List<Integer> nums) {
// write your code here
int max = nums.get(0);
for(int num : nums){
if(num > max){
max = num;
}
}
return max;
}
16.交换数组两个元素
public void swapIntegers(int[] A, int index1, int index2) {
// write your code here
if(!(A.length > 0 )|| A[index1] == A[index2]){return;}
int temp = A[index1];
A[index1] = A[index2];
A[index2] = temp;
}
17.Fizz buzz问题
public List<String> fizzBuzz(int n) {
List<String> res = new LinkedList<>();
for (int i = 1; i <= n; i++) {
String w = help(i, 3, "fizz") +help(i,15," ") + help(i, 5, "buzz");
if (w.equals("")) {
w += i;
}
res.add(w);
}
return res;
}
public String help(int n, int div, String w) {
return n % div == 0 ? w : "";
}
18.冰雹猜想
public int getAnswer(int num) {
// write your code here.
int count = 0;
while(num > 1){
if(num %2 ==0){
num /=2;
count++;
}else{
num = 3*num+1;
count++;
}
}
return count;
}
19.加一
public int[] plusOne(int[] digits) {
// write your code here
int i= digits.length-1;
digits[i]+=1;
while(digits[i]==10&&i>0){
digits[i]=0;
digits[--i]+=1;
}
if(digits[0]==10){
digits = new int[digits.length+1];
digits[0]=1;
}
return digits;
}
20.回文数 ||
第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串,比较简单
public boolean isPalindrome(int n) {
// Write your code here
//使用字符串
String res = Integer.toBinaryString(n);
char [] chars = res.toCharArray();
for(int i = 0;i < chars.length/2;i++){
if(chars[i] != chars[chars.length-i-1]){
return false;
}
}
return true;
}
21.整数排序
使用冒泡排序
public void sortIntegers(int[] A) {
// write your code here
for(int i =0;i < A.length-1;i++){
for(int j = 0;j < A.length-i-1;j++){
int temp = 0;
if(A[j] > A[j+1]){
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
22.寻找素数
public List<Integer> prime(int n) {
// write your code here
List<Integer> list = new ArrayList<>();
boolean loop = true;
for(int i = 2;i <= n;i++){
loop = true;
for(int j = 2;j < 10;j++){
if(i!=j){
if(i%j==0){
loop = false;
break;
}
}else{
continue;
}
}
if(loop == true){
list.add(i);
}
}
return list;
}
23.数组第二大数
public int secondMax(int[] nums) {
// write your code here
int max = nums[0];
int second = nums[1];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
second = max;
max = nums[i];
} else if (nums[i] <= max && nums[i] >= second) {
second = nums[i];
}
}
return second;
}
24.主元素
public int majorityNumber(List<Integer> nums) {
// write your code here
Map<Integer, Integer> count = new HashMap();
for(int i : nums) {
if(count.containsKey(i)) {
int v = count.get(i);
count.replace(i, ++v);
} else {
count.put(i, 1);
}
if(count.get(i) > nums.size()/2) {
return i;
}
}
return -1;
}
25.杨辉三角
public List<List<Integer>> calcYangHuisTriangle(int n) {
List<List<Integer> > res = new ArrayList<>();
int i, j;
if (n == 0) {
return res;
}
for (i = 0; i < n; ++i) {
List<Integer> t = new ArrayList<Integer>();
t.add(1);
for (j = 1; j < i; ++j) {
t.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
if (i > 0) {
t.add(1);
}
res.add(t);
}
return res;
}
26.旋转数组
rotate之前数组中位置i的元素在rotate之后位于位置(i+k) % nums.length
public int[] rotate(int[] nums, int k) {
// Write your code here
if (nums == null || k == 0) {
return nums;
}
k = (k % nums.length);
int[] helper = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
helper[(i+k)%nums.length] = nums[i];
}
return helper;
}
27.翻转数组
public void reverseArray(int[] nums) {
// initialization
int i = 0;
int j = nums.length - 1;
int tmp;
// i and j not meet yet
while (i < j) {
// swap nums[i] and nums[j]
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
// ++i;
// --j;
i += 1;
j -= 1;
}
}
28.分解质因数
解题思路：
先求得一个质数数组，然后从小到大遍历该数组，若题目所给整数能够被某质数整除，则将该数加入答案值数组。
算法流程：
- 从小到大遍历[2,up]，若num能够被i整除则循环除以i直到不能被整除，每次除以i都向答案值数组增加一个i，因为是从小到大遍历，则必定只有质数能被取为因数
- up一般设定为sqrt(num)，因为一个数大于其根号的质因数最多只有一个，那么遍历其根号内的数可以将时间复杂度减小至根号n，若遍历完prime后该数不为1，则其值为最后一个质因数
public List<Integer> primeFactorization(int num) {
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i * i <= num; i++) {
while (num % i == 0) {
num = num / i;
factors.add(i);
}
}
//若最后剩余数不为1，则为最后一个质因数
if (num != 1) {
factors.add(num);
}
return factors;
}
29.反转字符串中的单词
public String reverseWords(String s) {
// write your code here
if (s.length() == 0 || s == null) {
return "";
}
StringBuffer res = new StringBuffer();
// 以” “分割字符串，末尾的空格会在数组中不存在
String[] split = s.split(" ");
for (int i = split.length - 1; i >= 0; i--) {
if (!"".equals(split[i])) {
// 第一个添加不了空格，因为长度还为0，然后添加单词。
// 再是""+单词的组合，最后一个肯定不会多空格。
if (res.length()>0){
res.append(" ");
}
res.append(split[i]);
}
}
return res.toString();
}
30.数组剔除元素后的乘积
public List<Long> productExcludeItself(List<Integer> nums) {
long[] res = new long[nums.size()];
long left = 1;
res[0] = 1;
for(int i = 1 ; i < nums.size(); i++ ) {
left = left * (long)nums.get(i - 1);
res[i] = left;
}
long right = 1;
for(int i = nums.size() - 2; i >= 0 ; i-- ) {
right = right * nums.get(i + 1);
res[i] = res[i] * right;
}
List<Long> result = new ArrayList<>();
for(long num : res) {
result.add(num);
}
return result;
}
四、字符串与循环
31.旋转字符串
public void rotateString(char[] str, int offset)
{
if (str == null || str.length == 0 || offset == 0) return;
offset = offset % str.length;
String sstr = new String(str);
String B = sstr.substring(str.length - offset, str.length);
String A = sstr.substring(0, str.length - offset);
String res = B.concat(A);
char[] res_c = res.toCharArray();
//str = res.toCharArray(); 不會被更新
for (int i = 0; i < res_c.length; i++)
{
str[i] = res_c[i];
}
}
32.回文数
public boolean isPalindrome(int num) {
if(num<10) return true;
String s=String.valueOf(num);
int l=s.length();
for(int i=0;i<l/2;i++){
if(s.charAt(i)!=s.charAt(l-i-1)){
return false;
}
}
return true;
}
33.大小写转换 II
public String lowercaseToUppercase2(String str) {
// write your code here
char[] s = str.toCharArray();
for (int i = 0; i < s.length; i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
s[i] -= 32;
}
}
return String.valueOf(s);
}
34.最后一个单词的长度
public int lengthOfLastWord(String s) {
// write your code here
String[] arr = s.trim().split(" ");
String a = "";
if("" != arr[arr.length-1]){
a = arr[arr.length-1];
}
return a.length();
}
35.最大字母
public String largestLetter(String s) {
// write your code here
Set<Character> characters = new HashSet<>();
for (char chr: s.toCharArray()) {
characters.add(chr);
}
for (int i = 25; i >= 0; i--) {
char low = (char)((int)'a' + i);
char upper = (char)((int)'A' + i);
if (characters.contains(low) && characters.contains(upper)) {
return String.valueOf(upper);
}
}
return "NO";
}
36.首字母大写
public String capitalizesFirst (String s) {
// Write your code here
StringBuilder strBld = new StringBuilder();
char preChar = ' ';
int offset = 'a' - 'A';
for (char chr: s.toCharArray()) {
if (preChar == ' ' && chr != ' ') {
strBld.append((char)(chr - offset));
} else {
strBld.append(chr);
}
preChar = chr;
}
return strBld.toString();
}
37.转换字符串到整数
public int stringToInteger(String target) {
// write your code here
return Integer.valueOf(target);
}
38.字符串查找
public int strStr(String source, String target) {
// Write your code here
return source.indexOf(target);
}
39.转换成小写字母
public String toLowerCase(String str) {
// Write your code here
char[]words = str.toCharArray();
for(int i = 0;i < words.length;i++){
if(words[i] >= 'A' && words[i] <= 'Z' ){
words[i] = (char)(words[i]+32);
}
}
return String.valueOf(words);
}
40. 两字符串和
public String SumofTwoStrings(String A, String B) {
// write your code here
String result = "";
int lenA = A.length(), lenB = B.length();
int Aindex = lenA - 1, Bindex = lenB - 1;
while(Aindex >= 0 && Bindex >= 0){
int temp = (A.charAt(Aindex) - '0') + (B.charAt(Bindex) - '0');
result = String.valueOf(temp) + result;
Aindex--; Bindex--;
}
if(Aindex >= 0) result = A.substring(0, Aindex + 1) + result;
if(Bindex >= 0) result = B.substring(0, Bindex + 1) + result;
return result;
}
41.最长单词
public List<String> longestWords(String[] dictionary) {
// write your code here
List<String> list = new ArrayList<>();
if (dictionary.length == 0) {
return list;
}
list.add(dictionary[0]);
for (int i = 1; i < dictionary.length; i++) {
if(dictionary[i].length() > list.get(list.size() - 1).length()) {
list.clear();
list.add(dictionary[i]);
} else if (dictionary[i].length() == list.get(list.size() - 1).length()) {
list.add(dictionary[i]);
} else {
continue;
}
}
return list;
}
五、栈与队列
42.小括号匹配
public boolean matchParentheses(String string) {
// write your code here
Stack stack = new Stack();
for(int i = 0;i < string.length();i++){
if(string.charAt(i) == '('){
stack.push(')');
}else if(string.charAt(i) == ')'){
if(stack.isEmpty()){
return false;
}
if(stack.peek().equals(')')){
stack.pop();
}
}
}
return stack.isEmpty();
}
43.有效的括号序列
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
44.实现栈
public class Stack {
List<Integer> list = new ArrayList<Integer>();
/*
* @param x: An integer
* @return: nothing
*/
public void push(int x) {
// write your code here
list.add(x);
}
/*
* @return: nothing
*/
public void pop() {
// write your code here
list.remove(list.size()-1);
// return list.remove(-1);
}
/*
* @return: An integer
*/
public int top() {
// write your code here
// return list.get(-1);
return list.get(list.size()-1);
}
/*
* @return: True if the stack is empty
*/
public boolean isEmpty() {
// write your code here
return list.isEmpty();
}
}
45.队列维护
public class MyQueue {
/*
* @param item: An integer
* @return: nothing
*/
Node first;
Node last;
public MyQueue(){
first = null;
last = null;
}
// 队列是FIFO,所以设置first、last两个节点方便入队和出队操作。
public void enqueue(int item) {
// write your code here
if(first == null) {
// 采用先new再赋值，不会增加多余的节点。
last = new Node(item);
first = last;
}
else {
last.next = new Node(item);
last = last.next;
}
}
/*
* @return: An integer
*/
public int dequeue() {
// write your code here
int res = 0;
if(first != null) {
res = first.val;
first = first.next;
return res;
}
// first == null时，意味者队列已经没有元素，返回-1
return -1;
}
}
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
46.二阶阶乘
public long doubleFactorial(int n) {
// Write your code here
long sum = n;
for(int i = 1; i < n; i++){
if(n % 2 == 0 && i % 2 == 0){
sum *=i;
}else if(n % 2 == 1 && i % 2 == 1){
sum *=i;
}
}
return sum;
}
六、简单递归
47.斐波纳契数列
非递归写法
public int fibonacci(int n) {
// write your code here
if(n == 1)return 0;
if(n == 2)return 1;
int res = 0;
int fb0 = 0;
int fb1 = 1;
for(int i = 3;i <= n;i++){
res = fb0 +fb1;
fb0 = fb1;
fb1 = res;
}
return res;
}
递归写法
public int Fibonacci(int n) {
if(n == 0) {
return 0;
}
if(n == 1) {
return 1;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
## 48. 二叉树的前序遍历
```java
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
// write your code here
List<Integer> result = new ArrayList<>();
traversal(root, result);
return result;
}
private void traversal(TreeNode node, List<Integer> result) {
if (node == null) return;
result.add(node.val);
traversal(node.left, result);
traversal(node.right, result);
}
}
49.二叉树的中序遍历
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: A Tree
* @return: Inorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
// write your code here
List<Integer> result = new ArrayList<>();
traversal(root, result);
return result;
}
private void traversal(TreeNode node, List<Integer> result) {
if (node == null) return;
traversal(node.left, result);
result.add(node.val);
traversal(node.right, result);
}
}
50.二叉树的后序遍历
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
public List<Integer> postorderTraversal(TreeNode root) {
// write your code here
List<Integer> result = new ArrayList<>();
traversal(root, result);
return result;
}
private void traversal(TreeNode node, List<Integer> result) {
if (node == null) return;
traversal(node.left, result);
traversal(node.right, result);
result.add(node.val);
}
}
更多推荐
初阶必刷编程50题
发布评论