1、找出字符串中第一个只出现一次的字符 解题思路： 参考 对于char 的字符来说，总共有256种不同的字符，因此只需统计每一个字符在字符串中出现的次数就可以了，这样的话，使用一个哈希表就能解决这个问题。 定义哈希表的键值是字符，而值是该字符出现的次数。同时从头开始扫描字符串两次。第一次扫描字符串时，没扫描到一个字符，就在哈希表找到对应的项，把相应的值加1，这样，就能快速的找到第一个只出现一次的字符了。 第一次扫描时，在哈希表中更新第一个字符出现的次数的时间是O（1）。如果字符串长度为n，那么第一次扫描的时间复杂度是O（n）。第二次扫描时，同样在O(1)时间内能读出一个字符出现的次数，所以时间复杂度仍然是O（n）。这样算起来，总的时间复杂度是O（n）。同时，只需要一个包含256个字符的辅助数组就能解决，大小是1kb，由于这个数组的大小是一个常数，因此可以认为这种算法的空间复杂度为O（1）。
private static void solution() { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String str = sc.nextLine(); int[] table = new int[256]; for (int i = 0, len = str.length(); i < len; i++) { table[str.charAt(i)]++; } boolean flag = true; for (int i = 0, len = str.length(); i < len; i++) { if (table[str.charAt(i)] == 1) { System.out.println(str.charAt(i)); flag = false; //找到第一个值出现一次的字符即可 break; } } if (flag) { System.out.println(-1); } } } public int firstUniqChar(String s) { int[] arr = new int[256]; //遍历一遍 把每个字符出现的次数记录下来 for (int i=0, len=s.length(); i<len; i++) { arr[s.charAt(i)]++; } char c = 0; //第二遍 遍历 按字符串顺序查找 第一个只出现一次的字符 先被找到 for (int i=0, len=s.length(); i<len; i++) { if (arr[s.charAt(i)] == 1) { c = s.charAt(i); break; } } return s.indexOf(c); } //虽然慢，也是一种思路 一个从前面找，有个从后面找，如果唯一，返回的下标肯定相同 public int firstUniqChar(String s) { int l = -1, h = -1; for (int i=0,len=s.length(); i<len; i++) { l = s.indexOf(s.charAt(i)); h = s.lastIndexOf(s.charAt(i)); if (l == h) { return l; } } return -1; }2、变量定义问题 错误示范
private static void solution() { //共享一个buffer，一直追加 StringBuffer sb = new StringBuffer(); Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int num = sc.nextInt(); sc.nextLine(); for (int i = 0; i < num; i++) { 。。。 } System.out.println(sb.toString()); } }正确定义
private static void solution() { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { //每次需要定义自己的buffer StringBuffer sb = new StringBuffer(); int num = sc.nextInt(); sc.nextLine(); for (int i = 0; i < num; i++) { 。。。 } System.out.println(sb.toString()); } }3、多输入处理
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String ss = sc.nextLine(); String sl = sc.nextLine(); System.out.println(solution(ss,sl)); } } //只写单个判断的方法，循环放在主函数中处理 private static boolean solution(String ss, String sl) { for (int i=0, len=ss.length(); i<len; i++) { if (sl.indexOf(ss.charAt(i)) == -1) { //可以看到 contains也是使用indexOf来实现的 //if (sl.contains(ss.charAt(i))) { //public boolean contains(CharSequence s) { //return indexOf(s.toString()) > -1; //} return false; } } return true; } //循环放在Solution中，返回void，需要使用sout来输出，繁琐 private static void solution2() { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String ss = sc.nextLine(); String sl = sc.nextLine(); boolean flag = false; for (int i = 0, len = ss.length(); i < len; i++) { if (sl.indexOf(ss.charAt(i)) == -1) { System.out.println(false); flag = true; //若有一个字符没有找到 输出false 退出 否则会输出多个false break; } } if (flag) { } else { System.out.println(true); } } } }4、参数解析 这个方法真他喵的巧
/** * 1.参数分隔符为空格 * 2.对于用“”包含起来的参数，如果中间有空格，不能解析为多个参数。 * 比如在命令行输入xcopy /s “C:\program files” “d:\”时， * 参数仍然是4个，第3个参数应该是字符串C:\program files， * 而不是C:\program，注意输出参数时，需要将“”去掉，引号不存在嵌套情况。 * 3.参数不定长 * 4.输入由用例保证，不会出现不符合要求的输入 */ private static void solution(String str) { StringBuffer sb = new StringBuffer(); int len = 0; int quotaNum = 0; //遍历这个串 for (int i = 0; i < str.length(); i++){ //是引号 记数 不加入 if (str.charAt(i) == '\"') { quotaNum++; continue; } //非空格 只能是字符 加入（引号在前一步去掉了） if (str.charAt(i) != ' '){ sb.append(str.charAt(i)); //引号成对 或者没有引号 此时的空格都需要换行 //没有引号 quotaNum==0 那么空格就会换行 并且空格不会加入buffer //引号成对了 换行 //引号成对之后 空格换行 } else if (quotaNum % 2 == 0) { sb.append('\n'); len++; //是空格 需要加入 }else { sb.append(' '); } } System.out.println(len+1); System.out.println(sb.toString()); }受到启发之后，又做了道类似的题目
* 题目： 将一个字符中所有出现的数字前后加上符号“*”，其他字符保持不变 * 输入： Jkdi234klowe90a3 * 输出： Jkdi*234*klowe*90*a*3* private static void solution(String str) { StringBuilder sb = new StringBuilder(); int num = 0; for (int i=0, len=str.length(); i<len; i++) { char c = str.charAt(i); //如果 * 是偶数 if (num % 2 == 0) { //不是数字 加入 if (!(c >= 48 && c <= 57)) { sb.append(c); //是数字 加* 加入数字 } else if (c >= 48 && c <= 57) { sb.append('*'); sb.append(c); num++; } //如果 * 是奇数 } else { //遇到字母 先加入 * if (!(c >= 48 && c <= 57)) { sb.append('*'); sb.append(c); num++; //遇到数字 直接加入 } else { sb.append(c); } } } //如果最后一个数字 需要加最后一个* if (num % 2 == 1) { sb.append('*'); } System.out.print(sb.toString()); System.out.println(); }5、素数判断
private static boolean isPrime(int num) { //假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。 int sqrt = (int)Math.sqrt(num); for (int i=2; i<=sqrt; i++) { if (num % i == 0) { return false; } } return true; }6、求解立方根
private static double getCubeRoot(double input) { double min = 0; double max = input; double mid = 0; while ((max - min) > 0.001) { mid = (max + min) / 2; if (mid * mid * mid > input) { max = mid; } else if (mid * mid * mid < input) { min = mid; } else { return mid; } } return max; //都可以 //return min; }7、大写正确检测
我们定义，在以下情况时，单词的大写用法是正确的： 全部字母都是大写，比如"USA"。 单词中所有字母都不是大写，比如"leetcode"。 如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。 String rex1 = "[a-z]"; String rex2 = "[A-Z]"; public boolean detectCapitalUse(String word) { String str = word.substring(1,word.length()); //首字母小写 if (String.valueOf(word.charAt(0)).matches(rex1)) { //剩余全部小写 if (lowerCase(str)) { return true; } else { return false; } } //首字母大写 if (String.valueOf(word.charAt(0)).matches(rex2)) { //剩余全部小写 或者 剩余全部大写 if (lowerCase(str) || upperCase(str)) { return true; } else { return false; } } return false; } private boolean lowerCase(String s) { for (int i=0; i<s.length(); i++) { if (!(String.valueOf(s.charAt(i)).matches(rex1))) { return false; } } return true; } private boolean upperCase(String s) { for (int i=0; i<s.length(); i++) { if (!(String.valueOf(s.charAt(i)).matches(rex2))) { return false; } } return true; } 他人的解法 * 判断大小写字母数量 大写 || 小写 等于字符串长度 true * 只有一个大写 是不是在首位即可**8、验证回文串 ** 要点1：边界 要点2：一次遍历，不使用额外空间
/** * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 * 输入: "A man, a plan, a canal: Panama" * 输出: true * * 输入: "race a car" * 输出: false */ public boolean isPalindrome(String s) { String s1 = s.toLowerCase(); String rex = "[a-zA-Z0-9]"; int l=0, h=s1.length()-1; while (l < h) { //是字母或者数字 //如果用if 只能跳过一个 若出现连续的非字母数字 无法辨别 //如果不加l<h的话 会出现下标移除 例如两个空格" "，l会一直++,直到溢出 while (!String.valueOf(s1.charAt(l)).matches(rex) && l<h) { l++; } while (!String.valueOf(s1.charAt(h)).matches(rex) && l<h) { h--; } if (s1.charAt(l) != s1.charAt(h)) { return false; } l++; h--; } return true; }9、异或的使用
异或 aabbc=c;给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。力扣136，给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) { int result = nums[0]; for (int i=1,len=nums.length; i<len; i++) { result ^= nums[i]; } return result; }力扣268，给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。
public int missingNumber(int[] nums) { //因为数字从0-n少一个，而数组下标是从0-n-1，只需要添加一个n，全部异或即可(添加0，异或i+1亦可) int res = nums.length; for (int i=0,len=nums.length; i<len; i++) { res ^= nums[i]; res ^= i; } return res; }10、公约数 && 公倍数 最大公约数 4536=21； 36!=15； 21=6； 15%6=3； 6%3=0；
最小公倍数 x * y / 最大 公约数
private static void solution(int x, int y) { int g = -1; while (true) { g = x % y; if (g == 0) { System.out.println(y); break; } x = y; y = g; } }11、找出数组中重复的数
/** * 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, * 其中有些元素出现两次而其他元素出现一次。 */ public List<Integer> findDuplicates(int[] nums) { List<Integer> res = new ArrayList<>(); for(int i = 0;i < nums.length;i++){ //如果当前元素小于0，则表示之前出现过，加入结果集 if(nums[Math.abs(nums[i])-1] < 0){ res.add(Math.abs(nums[i])); }else{ nums[Math.abs(nums[i])-1] *= -1; } } return res; }12、最长递增子序列
