java算法学习
1、
输⼊: "abcabcbb"
输出: 3
解释: 因为⽆重复字符的最长⼦串是
"abc"，所以其长度为 3。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int res = 0;
int end=0,start=0;
Set<Character> set=new HashSet<>();
while(start<n && end<n){
ains(s.charAt(end))){
}else{
set.add(s.charAt(end++));
res=Math.max(res,end-start);
}
学习java的学习方法}
return res;
}
}
2、简化路径
以 Unix 风格给出⼀个⽂件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的⽂件系统中，⼀个点（.）表⽰当前⽬录本⾝；此外，两个点 （..） 表⽰将⽬录切换到上⼀级（指向⽗⽬录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个⽬录名之间必须只有⼀个斜杠 /。最后⼀个⽬录名（如果存在）不能以 / 结尾。此外，规范路径必须是表⽰绝对路径的最短字符串。
⽰例 1：
输⼊："/home/"
输出："/home"
解释：注意，最后⼀个⽬录名后⾯没有斜杠。
⽰例 2：
输⼊："/../"
输出："/"
解释：从根⽬录向上⼀级是不可⾏的，因为根是你可以到达的最⾼级。
⽰例 3：
输⼊："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要⽤⼀个斜杠替换。
⽰例 4：
输⼊："/a/./b/../../c/"
输出："/c"
⽰例 5：
输⼊："/a/../../b/../c//.//"
输出："/c"
⽰例 6：
输⼊："/a//bc/d//././/.."
输出："/a/b/c"
class Solution {
public String simplifyPath(String path) {
Stack<String> stringStack = new Stack<>();
String[] arr = path.split("/");
for(String str:arr)
{
if(str.equals("")||str.equals("."))
continue;
if(str.equals("..")) {
if(!pty())
stringStack.pop();
}
else
stringStack.push(str);
}
String ans = "";
while (!pty())
{
ans="/"+stringStack.pop()+ans;
}
if(ans.equals(""))
return "/";
return ans;
}
}
3、复原IP地址
⽰例:
输⼊: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
思路：DFS加回溯法，到符合条件的String分配就加⼊结果中
List<String> res=new ArrayList<String>();
public List<String> restoreIpAddresses(String s) {
if(s==null||s.length()==0){
return res;
}
String[] str=new String[4];//⽤来存放IP地址的数组，长度固定为4
dfs(s,0,0,str,res);//DFS
return res;
}
//start为当前读取到⼏个IP，cur为当前读取到s的哪⼀位
public void dfs(String s,int start,int cur,String[] str,List<String> res){
if(start==4&&cur==s.length()){//当读取了4个IP并且s遍历完，将结果放⼊res中
String ans="";
for(int i=0;i<4;i++){
ans=ans+str[i]+".";
}
ans=ans.substring(0,ans.length()-1);
res.add(ans);
return;
}
if(start==4&&cur!=s.length()){//当读取了4个IP但s没有遍历完，则直接返回
return;
}
for(int i=cur;i<cur+3&&i<s.length();i++){//每个IP最⼤为255，因此最长3位
String temp=s.substring(cur,i+1);//读取IP地址
if(Integer.valueOf(temp)<=255){
str[start]=temp;
dfs(s,start+1,i+1,str,res);//当前IP符合条件，DFS
str[start]="";//回溯
}
/
/01,012,00这些IP⾮法
if(temp.equals("0")){//如果当前读取到的第⼀位为0，则⽆需再读取后⾯的2、3位情况 break;
}
}
return;
}
}
4、三数和
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序 o(logn)
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字⼤于0，则三数之和⼀定⼤于0，所以结束循环 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int maxArea = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
//计算最⼤⾯积
int currMaxArea = getMaxArea(i, j, grid);
maxArea = Math.max(currMaxArea, maxArea);
}
}
return maxArea;
}
private int getMaxArea(int i, int j, int[][] grid) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
return 0;
}
//通过将经过的岛屿设置为0来确保下次不会重复访问
grid[i][j] = 0;
int upMaxArea = getMaxArea(i - 1, j, grid);
int downMaxArea = getMaxArea(i + 1, j, grid);
int leftMaxArea = getMaxArea(i, j - 1, grid);
int rightMaxArea = getMaxArea(i, j + 1, grid);
return upMaxArea + downMaxArea + leftMaxArea + rightMaxArea + 1;
}
}
class Solution {
public int minArray(int[] numbers) {
//⼆分查
int low=0;
int height=numbers.length-1;
while(low<height){
int mid=low+(height-low)/2;
if(numbers[mid]<numbers[height]){
height=mid;
}else if(numbers[mid]>numbers[height]){ low=mid+1;
}else{
height-=1;
}
}
return numbers[low];
}
}
朋友圈：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论