快乐学习
前程无忧、中华英才非你莫属!

Day1-LeetCode入门到精通

前言

重温基础,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));
        }
 

打赏

未经允许不得转载:同乐学堂 » Day1-LeetCode入门到精通

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

特别的技术,给特别的你!

联系QQ:1071235258QQ群:226134712
error: Sorry,暂时内容不可复制!