LeetCode
package Simple;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* 2020/2/6
* LeetCode简单题型,数组的两个数之和问题
*/
class Solution {
public static void main(String[] args) {
int[] a={2,7,11,15};
int[] b=twoSum(a,18);
System.out.println(Arrays.toString(b));
int[] c=twoSum2(a,18);
System.out.println(Arrays.toString(c));
}
//自己写的简单方法,如果没有两个数,异常处理
public static int[] twoSum(int[] nums, int target) {
for(int i=0;ifor(int j=i+1;j if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
// int[]a =new int[2];
// if(nums[i]+nums[j]==target){
// a[0]=i;
// a[1]=j;
// }
}
}
throw new IllegalArgumentException("No two sum value");
}
//力扣大神Map集合,如果这个集合中包含target-第一个数,那么就存入map集合
public static int[] twoSum2(int[] nums, int target) {
Mapmap = new HashMap<> ();
/*每遍历一次num数组,就把该数组对应的数值以及下标存入map
如果该map集合中有相减之后的数,就把那个数的下标与当前数的下标返回新数组
*/
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum value");
}
}
2.回文数的判断
package Simple; import java.util.Scanner; /** * 2020/2/8 判断一个数是否回文数:思路:整数转化为字符串 * 121 121是回文数 * -121 121- 不是回文数(负数不是) * 10 01不是回文数(最后一位是0的不是) */ public class PalindRome { public static void main(String[] args) { System.out.println(isPalindRome1("121")); System.out.println(isPalindRome1("-121")); System.out.println(isPalindRome1("10")); System.out.println(isPalindRome1("1841")); System.out.println(isPalindRome1("18441")); System.out.println(isPalindRome1("184481")); //System.out.println(isPalindRome()); System.out.println(isPalindRome2(121)); System.out.println(isPalindRome2(-121)); System.out.println(isPalindRome2(10)); testReverse(); } //从键盘输入判断 public static boolean isPalindRome() { Scanner s = new Scanner(System.in); String number = s.next(); char[] a = number.toCharArray(); int left=0; int right=a.length-1; while (left <= right) { if ((a[left] == a[right]) && (a[a.length - 1] != 0) && (a.length > 0)) { left++;right--; } else { return false; } } return true; } //给定一个字符串转化为字符数组;两个指针分别指向数组的首尾,依次向中间聚拢,判断对称位是否相等 public static boolean isPalindRome1(String string) { char[] a = string.toCharArray(); int left=0; int right=a.length-1; while (left <= right) { if ((a[left] == a[right]) && (a[a.length - 1] != 0) && (a.length > 0)) { left++;right--; } else { return false; } } return true; } //reverse方法(LeetCode) public static boolean isPalindRome2(int x) { if(x<0){ return false; } String s=Integer.toString(x); String s1=new StringBuilder(s).reverse().toString(); if(s.equals(s1)){ return true; } return false; } //reverse方法需要先new StringBuilder对象,才能调用该方法,然后用toString方法打印 public static void testReverse(){ String a="ahcbd"; System.out.println(new StringBuilder(a).reverse().toString()); String b="122432"; System.out.println(new StringBuilder(b).reverse().toString()); } }
3.
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"]输出: "fl"
示例 2: 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
/** * 最长公共子序列 * 2020/2/23 */ public class SubStringDemo { public static void main(String[] args) { String[] array={"leet","let","lecy"}; System.out.println(longestCommonPrefix(array)); } public static String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; //先比较第一个字符串与第二个串的公共串;再用前两个的公共串与第三个串比较 for (int i = 0; i < strs[0].length() ; i++){ char c = strs[0].charAt(i);//c=l for (int j = 1; j < strs.length; j ++) { if (i == strs[j].length() || strs[j].charAt(i) != c) return strs[0].substring(0, i); } } return strs[0]; } }
4.括号匹配
package Simple; import java.util.Stack; //括号匹配,添加栈数据结构 public class KuoHaoMatch { public static void main(String[] args) { char[] c={'{','(',')','}','[',']'}; char[] c2={'}','['}; char[] c3={'{','[','}',']'}; System.out.println(match(c)); System.out.println(match(c2)); System.out.println(match(c3)); } public static boolean match(char[] ch) { if (ch.length % 2 == 1 || ch[0]=='}' || ch[0]==']' || ch[0]==')') { return false; } Stack stack = new Stack(); for (int i = 0; i < ch.length; i++) { if (ch[i] == '[' || ch[i] == '(' || ch[i] == '{') { stack.push(ch[i]); } else { char c=(char) stack.peek(); //注意match2方法的顺序,左边应该是栈顶元素,第二个参数是右括号 if(match2(c, ch[i])){ stack.pop(); }else { return false; } } } return true; } public static boolean match2(char c,char c2){ if(c=='{' && c2=='}'){ return true; } else if(c=='[' && c2==']') { return true; } else if(c=='(' && c2==')'){ return true; } else { return false; } } }
5.最长公共子序列
package Simple; /** * 最长公共子序列 * 2020/2/27 */ public class LargetSubSequence { public static void main(String[] args) { int[] a={-2,3,-1,1,-3}; System.out.println(maxSubArray(a)); int[] b={-2,3,-1,1,3}; System.out.println(maxSubArray(b)); int[] c={2,3,-1,1,-3}; System.out.println(maxSubArray(c)); int[] d={-2,-3,-1,-1,-3}; System.out.println(maxSubArray(d)); } /** * 动态规划的是首先对数组进行遍历,当前最大连续子序列和为 sum,结果为 ans * 如果 sum > 0,则说明 sum 对结果有增益效果,则 sum 保留并加上当前遍历数字 * 如果 sum <= 0,则说明 sum 对结果无增益效果,需要舍弃,则 sum 直接更新为当前遍历数字 * 每次比较 sum 和 ans的大小,将最大值置为ans,遍历结束返回结果 * 时间复杂度:O(n) * @param nums * @return */ public static int maxSubArray(int[] nums) { int ans = nums[0]; int sum = 0; //遍历数组,如果当前的和加上新的数据之后>0,就加上;比较sum和ans /** * sum=0;sum=-2;ans=0;(不加第一个数) * sum=3;ans=3;(加上第二个数) * sum=2,ans=3;(加上第三个数后) * sum=3,ans=3;(第四个数) * sum=0;ans=3;(不加上第五个数) */ for(int i=0;i) { if(sum > 0) { sum += nums[i]; } else { sum = nums[i]; } ans = Math.max(ans, sum); } return ans; } }
6.最后一个单词的长度
package Simple; /** * 最后一个单词长度 * 2020/3/2 * 排除最后一个是空格的情况 */ public class LastWordLength { public static void main(String[] args) { System.out.println(lastWord("hello hello ")); System.out.println(lastWord("hello hello")); System.out.println(lastWord("hello hello st")); System.out.println(lastWord("da")); System.out.println(lastWord("")); } public static int lastWord(String s){ // if(s.length()==0){ // return 0; // } int end=s.length()-1; while (end>=0 && s.charAt(end)==' '){ end--; } int start=end;//不是空格的位置 //start遇到空格后就说明单词结束 while (start>=0 && s.charAt(start)!=' '){ start--; } return end-start; } }
注:相当于两个指针的情况
7.查找数组中只出现了一次数的情况
/** * 一个非空数组,别的数字都出现了两次; * 找只出现了一次的数字,要求线性时间复杂度 */ public class SingleNumber { public static void main(String[] args) { int[] a={1,2,3,3,2}; int[] b={2,4,5,2,5}; int[] c={2,4,5,2,4}; int[] d={2,4,5,2,4,7,7,8,0,0,8}; int[] e={2,2,1}; System.out.println(number(a)); System.out.println(number(b)); System.out.println(number(c)); System.out.println(number(d)); System.out.println(number(e)); } // public static int number(int[] a){ // int start=0; // int end=a.length-1; // while(end>0 && start>=0&& start// if(a[start]!=a[end]){ // end--; // }else if(end==0) { // return a[start]; // } // else{ // start++; // end=a.length-1; // } // } // return a[start]; // } public static int number(int[] nums){ Map map=new HashMap(); for(int num:nums){ if(!map.containsKey(num)){ map.put(num,null); }else { map.remove(num); } } return map.keySet().iterator().next(); } }
8.将数组中含0的数放在数组最后
// 2020/3/4 含0的数字放在最后,不含0的原样输出 public class MoveZeroes{ public static void main(String[] args) { int[] a={0,0,4,0,6}; put(a); System.out.println("-----------"); int[] b={0,8,9,0,6}; put(b); System.out.println("-----------"); int[] c={8,4,7}; put(c); System.out.println("-----------"); int[] d={2,1}; put(d); } public static void put(int[] nums){ if(nums==null) { return; } //注意数组的赋值 //int[] a=nums; int[] a=new int[nums.length]; for(int i=0;i){ a[i]=nums[i]; } //两个指针i和j int j = 0; for(int i=1;i ) { //当前元素!=0,就把其交换到左边,等于0的交换到右边 if(nums[i]!=0) { int tmp = nums[i]; nums[i] = nums[j]; nums[j++] = tmp;//交换后j需要++ } } if((nums[nums.length-1])!=0){ System.out.println(Arrays.toString(a)); }else { System.out.println(Arrays.toString(nums)); } } }
注:数组的赋值(for循环)
9.
public class AddDigits { public static void main(String[] args) { System.out.println(add(-2)); System.out.println(add(22)); } public static int add(int num){ if(num>=0){ return (num-1)%9+1; }else { return num; } } }
10.循环字符串 abcd bcda word orda
11.找出输入字符串能组成的最大Good数
import java.util.Scanner; public class GoodCount { public static void main(String[] args) { Scanner s=new Scanner(System.in); System.out.println("请输入字符串"); String ss=s.nextLine(); if(!ss.contains("G")&&!ss.contains("o")&&!ss.contains("d")){ System.out.println(0); }else { System.out.println(countG("Good", ss)); } } public static int countG(String target,String InStr){ int i=0; int j=0; int count=0; while (j){ if(target.charAt(i)==InStr.charAt(j)) { i++; } j++; if((InStr.charAt(j)=='d')&&(i==3)){ count++; i=0; } } return count; } }
12.360笔试:
import java.util.LinkedList; import java.util.List; public class Swap { public static void main(String[] args) { int[] b={1,2,1}; array(5,3,b); } public static void array(int m,int n,int[] b) { Listlist = new LinkedList<>(); for (int i = 0; i < m; i++) { list.add(i + 1); } System.out.println(list.toString()); for (int j = 0; j < n; j++) { if (b[j] == 1) { Integer zero = ((LinkedList ) list).getFirst(); ((LinkedList ) list).removeFirst(); ((LinkedList ) list).addLast(zero); } else if (b[j] == 2) { if(list.size()%2==0) { for (int i = 0; i < m; ) { int tem = list.get(i + 1); list.set(i + 1, list.get(i)); list.set(i, tem); i = i + 2; } }else { for (int i = 0; i < m-1; ) { int tem = list.get(i + 1); list.set(i + 1, list.get(i)); list.set(i, tem); i = i + 2; } } } } System.out.println(list.toString()); } }
13.