算法总结-每日一题-（10月22日停更，搞别的专题去了）

书到用时方恨少，每到面试的时候才觉得一道算法题也不会。功夫在平时，今天开始每日一题（工作日），持续更新，做个记录，也激励、监督下自己。

1.两数之和（9月17日）

思路：(因为数组本身没有包含某元素的方法，所以考虑将数据放入map)

1.考虑hash表，key为数组元素对应的值，value为下标，

2.考虑只循环一次，将target减去某一个值。再看原来数组里是否包含剩下的

 public static int[] twoSum(int[] nums, int target) {Map map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int res = target - nums[i];if (map.containsKey(res)) {return new int[]{map.get(res), i};}map.put(nums[i], i);}return null;}

明日题：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 

2.无重复字符的最长子串（9月18日，咋感觉有点难，先TODO吧，继续往后面看）

10月25日，来补作业了，做了十几道题之后想明白了，哈哈

题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路：如例一，先找abca，第4个是a，那需要从b开始找，bcab，如何判断有没有重复元素，可以用set.add()方法，看是否能添加成功；最终的返回结果用int来接收，每次往set中放完元素，则和result进行比较，result小于set.size()，则交换。最开始说到的abca，出现了重复元素，如何再从b开始找，即i-set.size()+1，set.size()记录的是上个无重复元素的长度

//最长字符子串public static int lengthOfLongestSubstring(String s) {char[] chars = s.toCharArray();Set set = new HashSet<>();int result = 0;int i = 0;while (i < chars.length) {if (set.add(chars[i])) {i++;} else {i = i - set.size() + 1;set.clear();}if (result < set.size()) {result = set.size();}}return result;}

2.1 今天遇到一个场景，一个list中有重复数据，如何去重之后还保持顺序

思路：新new一个list，用set.add()方法判断是否能新增成功，如果成功就放入新new的list中，如果不能，就跳过，这样新new的list就是去重后并且不重复的list

 private List dislodgeRepeat(List list) {Set set = new HashSet();List newList = new ArrayList<>();for (String element : list) {//set能添加进去就代表不是重复的元素if (set.add(element)) {newList.add(element);}}list.clear();list.addAll(newList);return list;}

3.求圆周率PI，京东面试题（9月19日）

4.回文数（9月22日）

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

思路1:

考虑将其转化为StringBuffer，利用反转方法，反转后判断字符串还是否相等。

 //利用字符串反转private static boolean huiWenShu(int x) {if (x < 0) {return false;}if (x == 0) {return true;}String s = String.valueOf(x);StringBuilder sb = new StringBuilder(s);if (sb.reverse().toString().equals(s)) {return true;}return false;}

思路2:

利用纯数学的方式，首先找到最大位K是多少，如12321 为10000，判断第一位和最后一位是否相等，（第一位：x/k；最后一位x%10）；然后去掉第一位和最后一位（去掉首位：x%k；去掉末尾：x/10），再将K缩小100，重复上面的过程，直到x大于0；

private static boolean huiWenShu2(int x) {if (x < 0) {return false;}if (x == 0) {return true;}//判断x有几位int k = 1;int temp = x;while (temp > 0) {temp = temp / 10;k *= 10;}if (k > 1) {k = k / 10;}//判断第一位和最后一位是否相等while (x > 0) {int left = x / k; //获取x最左一位的值int right = x % 10; //获取x最右一位的值if (left != right) return false;//计算新的x的divx = x % k;x = x / 10;k /= 100;}return true;}

5.最长公共子串（9月22日，今天时间多，再来一道）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

如：输入：strs = ["flower","flow","flight"] 输出："fl"

思路：

1.先找出数组中最短那个字符串

2.按个穷举其前缀

3.跟剩下的字符串做对比

 //最长公共前缀public static String longestCommonPrefix(String[] strs) {String res = "";if (strs.length <= 0) {return res;}if (strs.length == 1) {return strs[0];}//寻找最短字

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！