数学
反转链表
1 | public class Test{ |
2 | public ListNode reverseList(ListNode head){ |
3 | ListNode pre=null; |
4 | ListNode cur=head; |
5 | |
6 | while(cur!=null){ |
7 | ListNode temp=cur.next; |
8 | cur.next=pre; |
9 | pre=cur; |
10 | cur=temp; |
11 | } |
12 | return pre; |
13 | } |
14 | } |
数组中和为target
1 | public class Test{ |
2 | public int[] twoSum(int[]nums,int target){ |
3 | int n=nums.length; |
4 | int[] result=new int[2]; |
5 | |
6 | HashMap<Integer,Integer> map=new HashMap<>(); |
7 | |
8 | for(int i=0;i<n;i++){ |
9 | map.put(nums[i],i); |
10 | } |
11 | |
12 | for(int i=0;i<n;i++){ |
13 | int ans=target-nums[i]; |
14 | if(map.containsKey(ans)&&map.get(ans)!=i){ |
15 | result[0]=i; |
16 | result[1]=map.get(ans); |
17 | } |
18 | } |
19 | return result; |
20 | |
21 | } |
22 | } |
相亲树问题
1 | //求除了本身之外的所有约树之和 |
2 | public int sumn(int m){ |
3 | int n=0; |
4 | for (int i=1;i<=m/2;i++){ |
5 | if(m%i==0){ |
6 | n=n+i; |
7 | } |
8 | } |
9 | return n; |
10 | } |
11 | |
12 | public static void main(String[] args) { |
13 | ArrayList<Integer> list=new ArrayList<>(); |
14 | |
15 | amicablenumber amicablenumber = new amicablenumber(); |
16 | |
17 | int i=1; |
18 | |
19 | while(i<3000){ |
20 | int sumn = amicablenumber.sumn(i); |
21 | if(i==amicablenumber.sumn(sumn) && sumn!=i){ |
22 | list.add(i); |
23 | list.add(sumn); |
24 | } |
25 | i++; |
26 | } |
27 | |
28 | for (Integer l : list) { |
29 | System.out.println(l); |
30 | } |
31 | } |
全排列
1 | public List<List<Integer>> permute(int[]nums){ |
2 | List<List<Integer>>res =new ArrayList<>(); |
3 | List<Integer> list = new ArrayList<>(); |
4 | int n=nums.length; |
5 | for(int i=0;i<n;i++){ |
6 | list.add(nums[i]); |
7 | } |
8 | digui(0,n,list,res); |
9 | |
10 | return res; |
11 | } |
12 | |
13 | public void digui(int begin,int n, List<Integer> list,List<List<Integer>>res){ |
14 | if(begin==n){ |
15 | res.add(new ArrayList<>(list)); |
16 | } |
17 | else { |
18 | for(int i=begin;i<n;i++){ |
19 | int temp=list.get(i); |
20 | list.set(i,list.get(begin)); |
21 | list.set(begin,temp); |
22 | |
23 | digui(begin+1,n,list,res); |
24 | |
25 | temp=list.get(i); |
26 | list.set(i,list.get(begin)); |
27 | list.set(begin,temp); |
28 | } |
29 | |
30 | } |
31 | } |
求质数
1 | public List<Integer> prime(int n){ |
2 | List<Integer> list =new ArrayList<>(); |
3 | for(int i=2;i<n;i++){ |
4 | if(judeg(i)){ |
5 | list.add(i); |
6 | } |
7 | } |
8 | return list; |
9 | |
10 | } |
11 | |
12 | public boolean judeg(int num){ |
13 | for(int i=2;i<num;i++){ |
14 | if(num%i==0){ |
15 | return false; |
16 | } |
17 | } |
18 | return true; |
19 | } |
20 | |
21 | public static void main(String[] args) { |
22 | Primenumber primenumber = new Primenumber(); |
23 | List<Integer> prime = primenumber.prime(100); |
24 | for (Integer integer : prime) { |
25 | System.out.println(integer); |
26 | } |
27 | } |
给定一个函数rand100(),它可以随机返回1 - 100的一个整数,要求用这个函数实现rand10000()
100*(rand100()-1)+rand100()
用rand100()实现rand500()
1 | public void rand500(){ |
2 | int res=501; |
3 | while(res>500){ |
4 | res=100*(rand100()-1)+rand100(); |
5 | } |
6 | return res; |
7 | } |
8 | |
9 | |
10 | //取模 |
11 | public void rand500(){ |
12 | int res=501; |
13 | res=100*(rand100()-1)+rand100(); |
14 | |
15 | return res%500+1; |
16 | } |
数组中的第k个最大数
1 | public int findKthLargest(int []nums,int k){ |
2 | Arrays.sort(nums); |
3 | int result=nums[0]; |
4 | for(int i=0;i<nums.length;i++){ |
5 | if(i+k==nums.length){ |
6 | result=nums[i]; |
7 | } |
8 | } |
9 | return result; |
10 | } |
快速排序
1 | public void quicksort(int[] nums,int left,int right){ |
2 | if(left>=right){ |
3 | return; |
4 | } |
5 | int p=partition(nums,left,right); |
6 | |
7 | quicksort(nums, left,p-1); |
8 | quicksort(nums,p+1,right); |
9 | |
10 | |
11 | } |
12 | |
13 | public int partition(int[]nums,int left,int right){ |
14 | int i=left+1; |
15 | int j=right; |
16 | int value=nums[left]; |
17 | |
18 | while(true){ |
19 | |
20 | while(i<right &&nums[i]<value ){ |
21 | i++; |
22 | } |
23 | while(j>left &&nums[j]>value){ |
24 | j--; |
25 | } |
26 | if(i>=j){ |
27 | break; |
28 | } |
29 | swap(nums,i,j); |
30 | |
31 | } |
32 | swap(nums,left,j); |
33 | |
34 | |
35 | return j; |
36 | |
37 | } |
38 | |
39 | public void swap(int[] nums,int i,int j){ |
40 | int temp=nums[i]; |
41 | nums[i]=nums[j]; |
42 | nums[j]=temp; |
43 | |
44 | } |
x的开平方(Leet69)
1 | public int sqrt(int x){ |
2 | if(x==0 ||x==1){ |
3 | return x; |
4 | } |
5 | |
6 | double left=0; |
7 | double right=x; |
8 | |
9 | double mid=x/2; |
10 | |
11 | while ((int)left<(int)right){ |
12 | if(mid*mid>x){ |
13 | right=mid; |
14 | mid=(left+right)/2; |
15 | } |
16 | if(mid*mid<=x){ |
17 | left=mid; |
18 | mid=(left+right)/2; |
19 | } |
20 | } |
21 | return (int)mid; |
22 | } |
1 | public int sqrt(int x){ |
2 | double res=x; |
3 | while (res*res>x){ |
4 | res=(res+x/res)/2; |
5 | } |
6 | return (int)res; |
7 | } |
树
前缀树
1 | /** |
2 | * Your Trie object will be instantiated and called as such: |
3 | * Trie obj = new Trie(); |
4 | * obj.insert(word); |
5 | * boolean param_2 = obj.search(word); |
6 | * boolean param_3 = obj.startsWith(prefix); |
7 | */ |
8 | |
9 | public class Leet208 { |
10 | private TrieNode root; |
11 | |
12 | /** Initialize your data structure here. */ |
13 | public Leet208() { |
14 | root=new TrieNode(); |
15 | } |
16 | |
17 | /** Inserts a word into the trie. */ |
18 | public void insert(String word) { |
19 | TrieNode node=root; |
20 | for(int i=0;i<word.length();i++){ |
21 | char cur=word.charAt(i); |
22 | if(!node.containsKey(cur)){ |
23 | node.put(cur,new TrieNode()); |
24 | } |
25 | node=node.get(cur); |
26 | } |
27 | node.setEnd(); |
28 | } |
29 | |
30 | public TrieNode searchPrefix(String word){ |
31 | TrieNode node=root; |
32 | for(int i=0;i<word.length();i++){ |
33 | char cur=word.charAt(i); |
34 | if(node.containsKey(cur)){ |
35 | node=node.get(cur); |
36 | } |
37 | else { |
38 | return null; |
39 | } |
40 | } |
41 | return node; |
42 | } |
43 | |
44 | /** Returns if the word is in the trie. */ |
45 | public boolean search(String word) { |
46 | TrieNode node=searchPrefix(word); |
47 | return node!=null && node.isEnd(); |
48 | } |
49 | |
50 | /** Returns if there is any word in the trie that starts with the given prefix. */ |
51 | public boolean startsWith(String prefix) { |
52 | TrieNode node=searchPrefix(prefix); |
53 | return node!=null; |
54 | } |
55 | } |
二叉树的深度(Leet104)
1 | //最大深度 |
2 | public int maxDepth(TreeNode root){ |
3 | int count=0; |
4 | if(root!=null){ |
5 | int left=maxDepth(root.left); |
6 | int right=maxDepth(root.right); |
7 | count=Math.max(left,right)+1; |
8 | } |
9 | |
10 | return count; |
11 | } |
12 | |
13 | //最小深度 |
14 | public int minDepth(TreeNode root){ |
15 | int count=0; |
16 | if(root!=null){ |
17 | int left=minDepth(root.left); |
18 | int right=minDepth(root.right); |
19 | count=Math.min(left,right)+1; |
20 | } |
21 | return count; |
22 | } |
平衡二叉树(Leet110)
1 | boolean flag=true; |
2 | public boolean isbalance(TreeNode root){ |
3 | depth(root); |
4 | return flag; |
5 | } |
6 | //还是要用的二叉树深度的求法 |
7 | public int depth(TreeNode root){ |
8 | |
9 | int count=0; |
10 | if(root!=null){ |
11 | int left=depth(root.left); |
12 | int right=depth(root.right); |
13 | if(Math.abs(left-right)>1){ |
14 | flag=false; |
15 | } |
16 | count = Math.max(left,right)+1; |
17 | } |
18 | return count; |
19 | } |
将有序数组转换为二叉搜索树(有序数组构造平衡二叉树)(Leet108)
1 | public TreeNode sortedArrayToBST(int[] nums) { |
2 | return sorted(nums, 0, nums.length); |
3 | } |
4 | |
5 | public TreeNode sorted(int[]nums,int start,int end){ |
6 | if(start==end){ |
7 | return null; |
8 | } |
9 | int mid=(start+end)/2; |
10 | TreeNode root=new TreeNode(nums[mid]); |
11 | root.left=sorted(nums,start,mid); |
12 | root.right=sorted(nums,mid+1,end); |
13 | return root; |
14 | |
15 | } |
验证二叉搜索树(Leet98)
1 | TreeNode pre=null; |
2 | |
3 | public boolean isValidBST(TreeNode root) { |
4 | if(root==null){ |
5 | return true; |
6 | } |
7 | if(!isValidBST(root.left))return false; |
8 | if(pre!=null&& pre.val>=root.val)return false; |
9 | pre=root; |
10 | return isValidBST(root.right); |
11 | } |
中序遍历树(Leet94)
1 | public List<Integer> inorderTraversal(TreeNode root) { |
2 | List<Integer> list =new ArrayList<>(); |
3 | digui(root,list); |
4 | return list; |
5 | |
6 | } |
7 | public void digui(TreeNode root,List<Integer>list){ |
8 | if(root!=null){ |
9 | digui(root.left,list); |
10 | list.add(root.val); |
11 | digui(root.right,list); |
12 | } |
13 | } |
二叉树中的最大路径和(Leet124)
1 | int res=Integer.MIN_VALUE; |
2 | public int maxPathSum(TreeNode root){ |
3 | digui(root); |
4 | return res; |
5 | |
6 | } |
7 | |
8 | public int digui(TreeNode root){ |
9 | if(root==null)return 0; |
10 | |
11 | int left=digui(root.left); |
12 | int right=digui(root.right); |
13 | res=Math.max(left+right+root.val,res); |
14 | return Math.max(0,Math.max(left,right)+root.val); |
15 | } |
树的最长路径
1 | int ans=1; |
2 | public int diameterOfBinaryTree(TreeNode root) { |
3 | depth(root); |
4 | return ans-1; |
5 | |
6 | } |
7 | |
8 | public int depth(TreeNode root){ |
9 | if(root!=null){ |
10 | int left=depth(root.left); |
11 | int right=depth(root.right); |
12 | |
13 | ans=Math.max(ans,left+right+1); |
14 | return Math.max(left,right)+1; |
15 | } |
16 | return 0; |
17 | } |
判断一个数组是不是二叉搜索树
1 | public class PosTree { |
2 | public boolean VerifySquenceOfBST(int []sequence){ |
3 | if(sequence.length==0) return false; |
4 | return IsTreeBST(sequence,0,sequence.length-1); |
5 | } |
6 | |
7 | public boolean IsTreeBST(int[] sequence, int start, int end) { |
8 | if(end<=start) return true; |
9 | int i=start; |
10 | for(;i<end;i++){ |
11 | if(sequence[i]>sequence[end]) break; |
12 | |
13 | } |
14 | |
15 | for(int j=i;j<end;j++){ |
16 | if(sequence[j]<sequence[end]) return false; |
17 | |
18 | } |
19 | return IsTreeBST(sequence,start,i-1) |
20 | && IsTreeBST(sequence,i,end-1); |
21 | } |
22 | } |
字符串处理
最长回文子串
1 | public String longestPalindrome(String s){ |
2 | if(s.length()<=1){ |
3 | return s; |
4 | } |
5 | String result=null; |
6 | int max=0; |
7 | |
8 | for(int i=0;i<s.length();i++){ |
9 | for(int j=i;j<s.length();j++){ |
10 | String szi=s.substring(i,j+1); |
11 | if(szi.length()>max && judge(szi)){ |
12 | max=szi.length(); |
13 | result=szi; |
14 | } |
15 | } |
16 | } |
17 | return result; |
18 | } |
19 | |
20 | public boolean judge(String szi){ |
21 | int i=0; |
22 | int j=szi.length()-1; |
23 | |
24 | while(i<=j){ |
25 | if(szi.charAt(i)==szi.charAt(j)){ |
26 | i++; |
27 | j--; |
28 | } |
29 | else { |
30 | return false; |
31 | } |
32 | |
33 | } |
34 | return true; |
35 | } |
解码方法:字母和数字的映射问题:给定一个字母和数字的映射关系,如 1-26 对应a-z,然后输入一个数字型的字符串如“123”,请输出所有可能的字母型字符串,“abc”和“aw”和”lc”。(Leet91)
1 | public int numDecodings(String s) { |
2 | int n=s.length(); |
3 | int[] result=new int[n+1]; |
4 | |
5 | result[n]=1; |
6 | result[n-1]=s.charAt(n-1)!='0'?1:0; |
7 | |
8 | for(int i=n-2;i>=0;i--){ |
9 | if(s.charAt(i)=='0')continue; |
10 | else { |
11 | if(Integer.parseInt(s.substring(i,i+2))<=26){ |
12 | result[i]=result[i+1]+result[i+2]; |
13 | } |
14 | else { |
15 | result[i]=result[i+1]; |
16 | } |
17 | } |
18 | |
19 | } |
20 | return result[0]; |
21 | } |
链表
两个有序链表的合并(Leet21)
1 | public ListNode merge(ListNode l1,ListNode l2){ |
2 | ListNode res=new ListNode(0); |
3 | ListNode p=res; |
4 | |
5 | while (l1!=null && l2!=null){ |
6 | if(l1.val<=l2.val){ |
7 | p.next=l1; |
8 | l1=l1.next; |
9 | } |
10 | else { |
11 | p.next=l2; |
12 | l2=l2.next; |
13 | } |
14 | p=p.next; |
15 | } |
16 | if(l1==null){ |
17 | p.next=l2; |
18 | } |
19 | if(l2==null){ |
20 | p.next=l1; |
21 | } |
22 | return res.next; |
23 | |
24 | } |