java几道数据算法实例

152. 乘积最大子数组

class Solution { public int maxProduct(int[] nums) { if(nums.length==0){ return 0; } int[] dpMax = new int[nums.length]; dpMax[0] = nums[0]; int[] dpMin = new int[nums.length]; dpMin[0] = nums[0]; int max = nums[0]; for(int i = 1;i<nums.length;i++){ dpMax[i] = Math.max(dpMin[i-1]*nums[i],Math.max(nums[i],dpMax[i-1]*nums[i])); dpMin[i] = Math.min(dpMax[i-1]*nums[i],Math.min(nums[i],dpMin[i-1]*nums[i])); max = Math.max(max,dpMax[i]); } return max; } } 

class Solution { public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的，一个保存最小的。 for(int i=0; i<nums.length; i++){ //如果数组的数是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。 if(nums[i] < 0){ int tmp = imax; imax = imin; imin = tmp; } imax = Math.max(imax*nums[i], nums[i]); imin = Math.min(imin*nums[i], nums[i]); max = Math.max(max, imax); } return max; } } 

面试题 16.20. T9键盘

class Solution { public List<String> getValidT9Words(String num, String[] words) { List<String> ans = new ArrayList<>(); Map<Character, Character> map = new HashMap<>(); map.put('a', '2'); map.put('b', '2'); map.put('c', '2'); map.put('d', '3'); map.put('e', '3'); map.put('f', '3'); map.put('g', '4'); map.put('h', '4'); map.put('i', '4'); map.put('j', '5'); map.put('k', '5'); map.put('l', '5'); map.put('m', '6'); map.put('n', '6'); map.put('o', '6'); map.put('p', '7'); map.put('q', '7'); map.put('r', '7'); map.put('s', '7'); map.put('t', '8'); map.put('u', '8'); map.put('v', '8'); map.put('w', '9'); map.put('x', '9'); map.put('y', '9'); map.put('z', '9'); boolean matched = true; for(String word:words){ matched = true; for(int i = 0;i<word.length();i++){ if(map.get(word.charAt(i)) != num.charAt(i)){ matched = false; break; } } if(matched){ ans.add(word); } } return ans; } } 

class Solution { List<String> res; public List<String> getValidT9Words(String num, String[] words) { res = new ArrayList<>(); int len = num.length(); Trie trie = new Trie(); for(String word : words){ trie.insert(word); } String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; TrieNode cur = trie.root; dfs(num.toCharArray(), 0, cur, map); return res; } private void dfs(char[] chs, int i, TrieNode cur, String[] map){ if(i == chs.length){ return; } for(char ch : map[chs[i] - '0'].toCharArray()){ TrieNode temp = cur.childern[ch - 'a']; if(temp == null){ continue; }else{ if(temp.end){ res.add(temp.val); }else{ dfs(chs, i + 1, temp, map); } } } } class TrieNode{ String val; TrieNode[] childern = new TrieNode[26]; //记录当前节点是否是某个单词的结尾 boolean end = false; public TrieNode() { } public TrieNode(String val) { this.val = val; } } class Trie { TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode cur = root; for(int i = 0; i < word.length(); i++){ int ch = word.charAt(i) - 'a'; if(cur.childern[ch] == null){ cur.childern[ch] = new TrieNode(); } cur = cur.childern[ch]; } cur.end = true; cur.val = word; } } } 

面试题 04.08. 首个共同祖先

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left != null && right != null) return root; else if(left == null) return right; else return left; } } 

你知道的越多，你不知道的越多。

本文地址：https://blog.csdn.net/qq_40722827/article/details/106187058