1.Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”
解释：
P I N
A L S I G
Y A H R
P I
思路：先确定有几行数据，存储数据先递增再递减
package com.exerice;
import java.util.ArrayList;
import java.util.List;
//Z字形变化
public class ZTest {
public static void main(String[] args) {
String s="LEETCOD";
System.out.println(convert(s,3));
}
public static String convert(String s, int numRows) {
if(numRows <2){ return s;}
List result = new ArrayList<>();
for(int i=0;i
2.字符串转换整数 (atoi)
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Solution {
public int myAtoi(String s) {
int result=0;
String regex="^[\+\-]?\d+";
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(s.trim());
if (m.find()){
try{
result=Integer.parseInt(m.group());
}catch (Exception e){
result = s.trim().charAt(0) == '-' ? Integer.MIN_VALUE: Integer.MAX_VALUE;
}
}
return result;
}
}
3.盛最多水的容器
https://leetcode-cn.com/problems/container-with-most-water/
class Solution {
public int maxArea(int[] height) {
int i=0,j=height.length-1;
int max=0;
while(i
4.整数转罗马数字
class Solution {
public String intToRoman(int num) {
String[] ge={"","I","II","III","IV","V","VI","VII","VIII","IX"};
String[] shi={"","X","XX","XXX","XL","L", "LX", "LXX", "LXXX", "XC"};
String[] bai={"","C","CC","CCC","CD","D","DC", "DCC", "DCCC", "CM"};
String[] qian={"","M","MM","MMM"};
StringBuilder result=new StringBuilder();
result.append(qian[num/1000]).append(bai[num%1000/100]).append(shi[num%100/10]).append(ge[num%10]);
return result.toString();
}
}
5.罗马数字转整数
class Solution {
public int romanToInt(String s) {
Map symbolValues = new HashMap() {{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};
int result=0;
for(int i=0;i
6.最长公共前缀
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
package com.exerice;
public class LongestPubString {
public static void main(String[] args) {
String[] strings={"aabbcc","aabb","aabcdef"};
System.out.println(pub(strings));
}
public static String pub(String[] strings){
String ret =strings[0];
for(int i=1;i
7.最接近的三数之和
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int jishu= nums[0]+nums[1]+nums[2];
Arrays.sort(nums);
for(int i=0;i0 &&nums[i]==nums[i-1]) continue;
int j = i+1, k = nums.length - 1;
while (jtarget){
k--;
}else if(sum < target){
j++;
}else {
return jishu;
}
}
}
return jishu;
}
}
8.电话号码的字母组合
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
package com.exerice;
import java.util.*;
//电话号码的字母组合，用队列解决
public class letterCombinations {
public static void main(String[] args) {
String digits="23";
System.out.println(letterCombinations(digits));
}
public static List letterCombinations(String digits) {
if(digits == null || digits.length() ==0){
return new ArrayList<>();
}
String[] phone ={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
Queue stringQueue =new linkedList<>();
stringQueue.offer("");
for(int i=0;i) stringQueue;
}
}
9.连续最长子序列
package com.exerice;
//最长递增子序列
//输入：nums = [10,9,2,5,3,7,101,18]
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
public class IncreasingsTest {
public static void main(String[] args) {
int[] arr = {10, 9, 2, 5, 3, 7, 101, 1};
System.out.println(length(arr));
}
public static int length(int[] arr) {
int len = arr.length;
int[] num = new int[len];
num[0] = 1;
int max = 1;
for (int i = 1; i < len; i++) {
num[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
num[i] = Math.max(num[i], num[j] + 1);
}
}
max = Math.max(max, num[i]);
}
return max;
}
}
10.括号生成
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
package com.exerice;
import java.util.ArrayList;
import java.util.List;
//括号生成,输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 解题思路
// 1. 将问题抽象成树形结构遍历问题
// 2.判断是是否是有效括号
public class KuoHaoNewTest {
public static void main(String[] args) {
int n =3;
System.out.println(generateParenthesis(3));
}
public static List generateParenthesis(int n) {
List res = new ArrayList<>();
List result = new ArrayList<>();
if(n<=0){return res;}
dnf(n,"",res);
for(String key:res){
if(isvalid(key)){
result.add(key);
}
}
return result;
}
public static void dnf(int n,String path,List res){
if(path.length() == 2*n){
res.add(path);
return;
}
dnf(n,path+"(",res);
dnf(n,path+")",res);
}
//https://leetcode-cn.com/problems/generate-parentheses/solution/pei-yang-chou-xiang-si-wei-hui-su-jie-fa-7dwu/
//判断是否是有效括号
public static boolean isvalid(String str){
while (str.contains("()")){
str=str.replaceAll("\(\)","");
}
return str.length()==0;
}
}
11.全排列
import java.util.ArrayList;
import java.util.List;
public class AllZuHeTest {
public static void main(String[] args) {
int[] arr = {1, 2};
System.out.println(all(arr));
}
public static List> all(int[] arr) {
List> lists = new ArrayList<>();
List path = new ArrayList<>();
dfs(arr, -1, path, lists);
return lists;
}
public static void dfs(int[] nums, int index, List path, List> lists) {
if(path.size() == nums.length){
lists.add(new ArrayList<>(path));
return;
}
for(int i=0;i
12.全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
package com.exerice;
import java.util.ArrayList;
import java.util.List;
public class AllZuHeTest2 {
public static void main(String[] args) {
int[] arr = {1,1,2};
System.out.println(all(arr));
}
public static List> all(int[] arr) {
List> lists = new ArrayList<>();
List path = new ArrayList<>();
boolean[] used= new boolean[arr.length];
dfs(arr, -1, path, lists,used);
return lists;
}
public static void dfs(int[] nums, int index, List path, List> lists,boolean[] used) {
if(path.size() == nums.length){
lists.add(new ArrayList<>(path));
return;
}
for(int i=0;i0 &&nums[i]== nums[i-1] && used[i-1]){continue;}
path.add(nums[i]);
used[i] = true;
dfs(nums,i,path,lists,used);
used[i] = false;
path.remove(path.size()-1);
}
}
}
13.链表两两交换
package com.exerice;
//两两交换链表中的节点
//如果链表中至少有两个节点，则在两两交换链表中的节点之后
// ，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。
// 链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系
// ，即可完成整个链表的两两交换。
public class ListNodeTranfer {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode NewHead = head.next;
head.next=swapPairs(NewHead.next);
NewHead.next=head;
return NewHead;
}
}
14.链表反转
package com.testfan.ll;
//链表反转
public class ListNodeTest2 {
public ListNode test3(ListNode head) {
ListNode result = null;
ListNode cur = head;
while (cur != null) {
ListNode node = cur.next;
cur.next = result;
result = cur;
cur = node;
}
return result;
}
}
14.有N个手机，编号为1-N，点开一次开灯再点一次关灯。第一次开所有点灯，第二次开编号为2的倍数的灯，第三次开编号为3的倍数的灯，。。。。m次
package com.testfan.ll;
import java.util.HashMap;
//思路：定义一个map,key存放灯的编号，value存放点了几次。点一次加1，奇数的就是亮的灯
public class KaiDenTest {
public static void main(String[] args) {
System.out.println(light(5,3));
}
public static int light(int n,int m){
int liangDengNUm =0;
HashMap resultMap = new HashMap<>();
for(int i=1;i 
