剑指offer 36.二叉搜索树与双向链表 medium

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val = _val;}public Node(int _val,Node _left,Node _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {List list=new ArrayList<>();public Node treeToDoublyList(Node root) {if(root==null) return null;inorder(root);for(int i=0;iNode node=list.get(i);node.left=i==0?list.get(list.size()-1):list.get(i-1);node.right=i==list.size()-1?list.get(0):list.get(i+1);}return list.get(0);}void inorder(Node node){if(node==null) return;inorder(node.left);list.add(node);inorder(node.right);}
}

有一点需要注意，就是但root==null的时候，返回null
如果不判断这个边界条件的话通不过
时间复杂度O(n),空间复杂度O(n)

有一个hard题，二叉树的序列化，跳过去了

剑指offer 38.字符串的排序 medium

class Solution {public String[] permutation(String s) {Set set=new HashSet<>();char[] arr=s.toCharArray();boolean[] visited=new boolean[arr.length];dfs(arr,"",visited,set);return set.toArray(new String[0]);}void dfs(char[] arr,String s,boolean[] visited,Set set){if(s.length()==arr.length){set.add(s);return;}for(int i=0;iif(visited[i]) continue;visited[i]=true;dfs(arr,s+String.valueOf(arr[i]),visited,set);visited[i]=false;}}
}

dfs的思想
其中 void dfs(char[] arr,String s,boolean[] visited,Set set)
char[] arr为char数组，记录字符串s中每个字符
s为本次dfs的字符串结果
boolean[] visited记录字符是否出现过
Set set是记录结果

剑指offer 39.数组中出现次数超过一般的数字 easy

class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];}
}

剑指Offer 40.最小的k个数 easy

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if(arr.length==0) return new int[0];quiksort(arr,0,arr.length-1);int[] res=new int[k];for(int i=0;ires[i]=arr[i];}return res;}void quiksort(int[] arr,int left,int right){int leftIndex=left,rightIndex=right;if(left>=right) return;int key=arr[left];while(leftwhile(left=key){right--;}arr[left]=arr[right];while(leftleft++;}arr[right]=arr[left];}arr[left]=key;quiksort(arr,leftIndex,left-1);quiksort(arr,right+1,rightIndex);}
}

写了一个快排，各个排序算法还需要复习一下
时间复杂度O(nlogN),空间复杂度O(logN)

跳过了一个hard，数据流中的中位数

剑指Offer 42.连续子数组的最大和 easy

class Solution {public int maxSubArray(int[] nums) {int[] dp=new int[nums.length];dp[0]=nums[0];int max=nums[0];for(int i=1;idp[i]=Math.max(dp[i-1]+nums[i],nums[i]);max=Math.max(dp[i],max);}return max;}
}

动态规划的思想
dp[i]代表以i为结尾的连续子数组的最大和
时间复杂度O(N),空间复杂度O(n)
这道题还有更好的方法，空间复杂度可以简化为O(1)

跳过了一道hard

剑指 Offer 44. 数字序列中某一位的数字

class Solution {public int findNthDigit(int n) {int digit = 1;long start = 1;long count = 9;while (n > count) { // 1.n -= count;digit += 1;start *= 10;count = digit * start * 9;}long num = start + (n - 1) / digit; // 2.return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.}
}

蚌埠住了，好难

剑指 Offer 46. 把数字翻译成字符串 medium

class Solution {public int translateNum(int num) {String s=num+"";int a=1,b=1;for(int i=1;iString substring=s.substring(i-1,i+1);if(substring.compareTo("10")>=0&&substring.compareTo("26")<0){b=b+a;a=b-a;}else{a=b;}}return b;}
}

动态规划的思想
注意string.compareTo()这个函数
时间复杂度O(n),空间复杂度O(1)