前言
重温基础，LeetCode刷起：“号称：谷歌筛码工”。
public class LeetCode {
public static int[] twoSumHash(int[] nums, int target) {
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; ++i) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
}
map.put(target - nums[i], i);
}
return null;
}
public static int[] twoSumFor(int[] nums, int target) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return null;
}
public static int reverse(int x) {
long res = 0;
for (; x != 0; x /= 10)
res = res * 10 + x % 10;
return res > Integer.MAX_VALUE || res < Integer.MIN_VALUE ? 0 : (int) res;
}
// %:取余数 /：取商的整数
// 取余（取模）有个规律就是：左边小于右边，结果为左边，左边大于右边，看余数
// 组合符号 +=；*=；/=；-=：表示自身通过这些运算符计算后再赋值给自己
public boolean isPalindrome(int x) {
if (x < 0) return false;
int copyX = x, reverse = 0;
while (copyX > 0) {
reverse = reverse * 10 + copyX % 10;
copyX /= 10;
}
return x == reverse;
}
// 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；
//
// 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；
//
// 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9。
//可以利用 map 来完成罗马数字的 7 个数字符号：I、V、X、L、C、D、M 和整数的映射关系，然后根据上面的解释来模拟完成即可。
public static int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int len = s.length(); // 获取字符串的长度。
// charAt 方法返回位于字符串的指定索引处的字符。该字符串的索引从零开始
int sum = map.get(s.charAt(len - 1)); // 获取最后一个字符串索引的对应的整数
// i++：先赋值，后计算；
// ++i；先计算，后赋值。
// 在for循环中没有却别，只是前置 ++ -- 效率比后置++ -- 效率要高
// 原因:在Java中i++语句是需要一个临时变量取存储返回自增前的值，而++i不需要
for (int i = len - 2; i >= 0; --i) {
if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
sum -= map.get(s.charAt(i));
} else {
sum += map.get(s.charAt(i));
}
}
return sum;
}
//leetcode的方法
public static String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
String pre = strs[0];
int i = 1;
while(i < strs.length){
//拿第一个做模板，匹配到数组中第一个元素的最长公共前缀字符串，然后以这个为模板，以此类推匹配下边所有的元素，最后返回最终模板
//indexOf是检测子串并返回子串起始位置的函数
while(strs[i].indexOf(pre) != 0)
//如果pre不是子串，就去掉pre末尾一位重新比较，直到是子串或者pre长度0时就会跳出本次循环去匹配下一轮外循环
pre = pre.substring(0,pre.length()-1);
i++;
}
return pre;
}
// 给定一个只包含字符'(', ')', '{', '}', '[' and ']'的字符串，确定输入字符串是否有效。
// 如果输入字符串有效：
// 必须使用相同类型的括号关闭左括号。
// 必须以正确的顺序关闭左括号。
// 请注意，空字符串也被视为有效。
// 思路：判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，
// 当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否何其匹配，不匹配的话直接返回 false 即可，
// 最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，
// 有个细节注意下 top = 1;，从而省去了之后判空的操作和 top - 1 导致数组越界的错误
public boolean isValid(String s) {
char[] stack = new char[s.length() + 1];
int top = 1;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack[top++] = c;
} else if (c == ')' && stack[--top] != '(') {
return false;
} else if (c == ']' && stack[--top] != '[') {
return false;
} else if (c == '}' && stack[--top] != '{') {
return false;
}
}
return top == 1;
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
ListNode() {
}
//添加节点
public void add(int newdata) {
ListNode newNode = new ListNode(newdata);
if (this.next == null) {
this.next = newNode;
} else {
this.next.add(newdata);
}
}
//输出
public void print() {
System.out.print(this.val + "-->");
if (this.next != null) {
this.next.print();
}
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode temp = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
temp.next = l1 != null ? l1 : l2;
return head.next;
}
// 从一个有序的数组中移除重复的元素，并返回之后数组的长度
/**
* 删除有序数组中重复元素
*/
public static int[] removeRepeat(int[] a){
int N = a.length;
int[] arr = new int[N];
for(int i = 0;i < N; i++){
arr[i] = a[i]; //保护性复制
}
int len = N;
for(int i = 0; i < len; i++){
//记录重复元素个数
int repeatCnt = 0;
for(int j = i + 1;j < len;j++){
if(arr[j] == arr[i]){
//如果重复，repeatCnt加1
repeatCnt++;
} else if(arr[j] > arr[i]){
//及时跳出循环
break;
}
}
//如果重复，开始移动元素
if(repeatCnt > 0){
for(int k = i + repeatCnt + 1; k < len;k++){
arr[k - repeatCnt] = arr[k];
}
//数组长度减小
len = len - repeatCnt;
}
}
//结果数组
int[] result = new int[len];
for(int i = 0;i < len; i++){
result[i] = arr[i];
}
return result;
}
/**到指定元素，并返回排除指定元素后数组
* @param A 需要筛选的数组
* @param elem 指定元素
* @return 排除指定元素后数组
*/
public static int[] removeElement(int[] A, int elem) {
int index = 0;
for (int i = 0; i < A.length; i++)
if (A[i] != elem) {
A[index] = A[i];
index++;
}
int[] newArrays = Arrays.copyOf(A, index);
return newArrays;
}
public int strStr(String haystack, String needle) {
int l1 = haystack.length(), l2 = needle.length();
if (l1 < l2) return -1;
for (int i = 0; ; i++) {
if (i + l2 > l1) return -1;
for (int j = 0; ; j++) {
if (j == l2) return i;
if (haystack.charAt(i + j) != needle.charAt(j)) break;
}
}
}
}
单元测试
单元测试
// 0、从一个数组里面返回两个数相加等于9的索引。
@Test
public void testSumRetKey() {
long time1 = System.currentTimeMillis();
int[] nums = new int[]{11, 6, 2, 7};
int[] keys = twoSumHash(nums, 9);
for (int s : keys) {
System.out.println(s);
}
long time2 = System.currentTimeMillis();
System.out.println("当前程序耗时：" + (time2 - time1) + "ms");
}
// 1、 把一个整数进行逆序输出
@Test
public void testReverse() {
System.out.println(reverse(123));
}
// 2、 判断一个有符号整型数是否是回文，也就是逆序过来的整数和原整数相同
@Test
public void huiWen() {
System.out.println(isPalindrome(22));
}
// 罗马数字转换成整数。
@Test
public void luoMan() {
System.out.println(romanToInt("I"));
}
// 3、求所有字符串的最长公共前缀，即数组的所有字符串都包含这个前缀
@Test
public void findStrPre() {
String[] strArray = {"flower", "flow", "flight"};
System.out.println(longestCommonPrefix(strArray));
}
// 4、判断括号匹配是否正确
@Test
public void KuoHao() {
String str = "()[]{}";
System.out.println(isValid(str));
}
// 5、合并两个排好序的列表
@Test
public void HebingList() {
ListNode L1 = new ListNode();
L1.add(2);
L1.add(3);
L1.add(6);
ListNode L2 = new ListNode();
L2.add(2);
L2.add(4);
L2.add(5);
ListNode L3 = mergeTwoLists(L1,L2);
L3.print();
}
// 6、 删除有序数组的重复元素
@Test
public void removeRe(){
int[] sortArr = { 1,3,3,4,5,5,5,7,8,9,9,9 };
int[] Arr = removeRepeat(sortArr);
System.out.println(Arr.length);
for (int itm: Arr) {
System.out.println(itm);
}
}
// 7、删除指定的元素
@Test
public void delEle() {
int[] Arr = { 1,3,3,4,5,5,5,7,8,9,9,9 };
int[] arr1 = removeElement(Arr,9);
for (int i:arr1) {
System.out.println(i);
}
}
// 8、查找子字符串在主字符串第一次出现的索引
@Test
public void findStrPOS(){
String str1 ="hello";
String str2 ="ll";
System.out.println(strStr(str1,str2));
}
打赏
微信扫一扫，打赏作者吧～
同乐学堂
