复健型力扣刷题笔记d2

目录

代码部分

题9

题13

题14

题20

题4

 题21

题15

java小知识部分

题9

题13

题14

题20

题4

题15


代码部分

题9

        给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

        参考评论进行修改后的代码:

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        else if (x == 0) return true;
        else
        {
            int xorigion = x;
            int X = 0;
            while (x != 0)
            {
                X = X * 10 + x % 10;
                x = x / 10;                  
            }
            if(X == xorigion) return true;
            else return false;
        }
    }
}

        首先判断掉特殊情况。对于剩下来的,通过一个while循环求得他的回文数。最后判断return。

题13

        罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000  

        例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

        通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

        I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
        X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
        C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
        给定一个罗马数字,将其转换成整数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

        自己的代码,有点长,但是时间100%,内存95%:

class Solution {
    public int romanToInt(String s) {
        char [] S = s.toCharArray();
        int res = 0;
        for(int i = 0 ; i < S.length ; i ++)
        {
            if((i+1)< S.length)
            {
                if(S[i] == 'I')
                {
                    if(S[i+1] != 'V' && S[i+1] != 'X')
                    {
                        res += 1;
                    }
                    else if(S[i+1] == 'V')
                    {
                        res += 4;
                        i ++;
                    }
                    else if(S[i+1] == 'X')
                    {
                        res += 9;
                        i ++;
                    }
                }
                else if(S[i] == 'X')
                {
                    if(S[i+1] != 'L' && S[i+1] != 'C')
                    {
                        res += 10;
                    }
                    else if(S[i+1] == 'L')
                    {
                        res += 40;
                        i ++;
                    }
                    else if(S[i+1] == 'C')
                    {
                        res += 90;
                        i ++;
                    }
                }
                else if(S[i] == 'C')
                {
                    if(S[i+1] != 'D' && S[i+1] != 'M')
                    {
                        res += 100;
                    }
                    else if(S[i+1] == 'D')
                    {
                        res += 400;
                        i ++;
                    }
                    else if(S[i+1] == 'M')
                    {
                        res += 900;
                        i ++;
                    }
                }
                else if(S[i] == 'V') res += 5;
                else if(S[i] == 'L') res += 50;
                else if(S[i] == 'D') res += 500;
                else if(S[i] == 'M') res += 1000;
                }
            else
            {
                if(S[i] == 'I') res +=1;
                else if(S[i] == 'V') res += 5;
                else if(S[i] == 'X') res += 10;
                else if(S[i] == 'L') res += 50;
                else if(S[i] == 'C') res += 100;
                else if(S[i] == 'D') res += 500;
                else if(S[i] == 'M') res += 1000;
            }
        }
        return res;
    }
}

        运用了编译原理的思想,先判断两个一组的字符(IV,IX,XL,XC,CD,CM),再判断单个字符。

题14

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

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

        修了几遍之后的暴力递归代码:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int len = strs.length ;
        String res;
        if(len == 0) return "";
        if(len == 1) return strs[0];
        if(strs[0].length() == 0) return "";

        char [] string1 , string2 , nextarray;
        string1 = strs[0].toCharArray();
        string2 = strs[1].toCharArray();
        nextarray = new char[200];
        for(int i = 0 ; i < 200 ; i++)
        {
            nextarray[i] = 'A';
        }
        int i = 0;
        while(i < string1.length && i < string2.length && string1[i] == string2[i])
        {
            nextarray[i] = string1[i];
            i ++;
        }
        String nextstring = new String(nextarray);
        String [] tonext = new String[len-1];
        tonext[0] = nextstring;
        for(int j = 1 ; j < len -1 ; j ++)
        {
            tonext[j] = strs[j+1];
        }
        if(len == 2) 
        {
            i = 0;
            while(nextarray[i] != 'A') i ++;
            nextstring = nextstring.substring(0,i);
            return nextstring;
        }
        res = longestCommonPrefix(tonext);

        return res;
    }
}

        先判断掉特殊情况。将前两个字符串转数组,声明初始化char数组nextarray用于存放前缀。求前两个字符串的最长前缀,存入nextarray数组。声明字符串nextstring将nextarray数组转为字符串,将nextstring字符串与剩余字符串存入字符串数组tonext。

        判断若当前只有两个字符串,则return当前的最长前缀。

        进递归。

题20

        给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

        有效字符串需满足:

        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

        自己的代码如下,使用栈解决:

class Solution {
    public boolean isValid(String s) {
        char[] S = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0 ; i < S.length ; i++)
        {
            if(S[i] == '(') stack.push(')');
            else if(S[i] == '[') stack.push(']');
            else if(S[i] == '{') stack.push('}');
            else
            {
                if(stack.isEmpty() == true) return false;
                else if(S[i] != stack.pop()) return false;
            }
        }
        if(stack.isEmpty()) return true;
        else return false;
    }
}

        对于每个前括号((,[,{),进栈它对应的另一半括号,这样可以在出栈比较时减少判断的次数。

题4

        给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

        算法的时间复杂度应该为 O(log (m+n)) 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

        自己的代码如下,过长了,有很大改进空间:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 , len2;
        len1 = nums1.length;
        len2 = nums2.length;
        int flag1 = (len1+len2)/2;;
        int med1 = 0 , med2 = 0;
        double med11 ,med22 , med = 0;
        if(len1 == 0 && len2 ==0) return med;
        if((len1+len2)%2 == 0) //偶数
        {
            int i1 = 0 , i2 = 0;
            for(int i = flag1 ; i >= 0 ; i--)
            {
                if(i != 0)
                {
                    if(i1 == len1)
                    {
                        med1 = nums2[i2];
                        i2 ++;
                    }
                    else if(i2 == len2)
                    {
                        med1 = nums1[i1];
                        i1 ++;
                    }
                    else if(nums1[i1] > nums2[i2])
                    {
                        med1 = nums2[i2];
                        i2 ++;
                    }
                    else if(nums1[i1] <= nums2[i2])
                    {
                        med1 = nums1[i1];
                        i1 ++;
                    }
                }
                else if(i == 0)
                {
                    if(i1 == len1)
                    {
                        med2 = nums2[i2];
                        i2 ++;
                    }
                    else if(i2 == len2)
                    {
                        med2 = nums1[i1];
                        i1 ++;
                    }
                    else if(nums1[i1] > nums2[i2])
                    {
                        med2 = nums2[i2];
                        i2 ++;
                    }
                    else if(nums1[i1] <= nums2[i2])
                    {
                        med2 = nums1[i1];
                        i1 ++;
                    }
                }
            }
            med11 = (double)med1;
            med22 = (double)med2;
            med = (med11 + med22) / 2;
        }
        else //奇数
        {
            int i1 = 0 , i2 = 0;
            for(int i = flag1 ; i >= 0 ; i--)
            {
                if(i1 == len1)
                {
                    med = nums2[i2];
                    i2 ++;
                }
                else if(i2 == len2)
                {
                    med = nums1[i1];
                    i1 ++;
                }
                else if(nums1[i1] > nums2[i2])
                {
                    med = nums2[i2];
                    i2 ++;
                }
                else if(nums1[i1] <= nums2[i2])
                {
                    med = nums1[i1];
                    i1 ++;
                }
            }
        }
        return med;
    }
}

        先判断掉特殊情况。判断两个数组的长度之和为偶数还是奇数,并分开来运算。偶数需要取中间两个数求平均值,奇数需要取中间一个数,也即偶数需要取复健型力扣刷题笔记d2小的数与复健型力扣刷题笔记d2小的数,而奇数需要取复健型力扣刷题笔记d2小的数。通过for循环取得数,在循环中需首先判断越界情况。

 题21

        将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

        自己的代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){return list2;}
        if(list2 == null){return list1;}
        ListNode root = new ListNode();
        ListNode res = root;
        while(list1 != null && list2 != null)
        {
            if(list1.val <= list2.val)
            {
                res.next = list1;
                res = res.next;
                list1 = list1.next;
            }
            else
            {
                res.next = list2;
                res = res.next;
                list2 = list2.next;
            }
        }
        if(list1 == null && list2 != null)
        {
            res.next = list2;
        }
        else if(list2 == null && list1 != null)
        {
            res.next = list1;
        }
        return root.next;

    }
}

        先判断掉特殊情况。判断原链表val值,并将小者节点接到目标链表上。若一条用完,就把另一条直接接上去。

题15

        给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

        注意:答案中不可以包含重复的三元组。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

        借鉴修改后的代码:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        int a , b , c , j , k;
        if(len < 3) {return res;}
        if(len == 3 && nums[0]+nums[1]+nums[2] != 0) {return res;}
        if(len == 3 && nums[0]+nums[1]+nums[2] == 0) 
        {
            res.add(Arrays.asList(nums[0],nums[1],nums[2]));
            return res;
        }
        Arrays.sort(nums);
        for(int i = 0 ; i < len ; i++)
        {
            if(nums[i] > 0) {return res;}
            if(i > 0 && nums[i] == nums[i-1]) {continue;}
            a = nums[i];
            j = i + 1;
            k = len -1;
            while(j < k)
            {
                b = nums[j];
                c = nums[k];
                if(a + b + c == 0)
                {
                    res.add(Arrays.asList(a,b,c));
                    j ++;
                    k --;
                    while(j < k && j > i + 1 && nums[j] == nums[j-1]) {j ++;}
                    while(j < k && k < len -1 && nums[k] == nums[k+1]) {k --;}
                }
                else if(a + b + c > 0) {k--;}
                else if(a + b + c < 0) {j++;}
            }
        }
        return res;
    }
}

        先判断掉特殊情况。先对数组排序。使用for循环进行nums[i]的顺序遍历,判断掉特殊情况。使用j,k来定位i后面的数组部分,并分别指向这一部分的首和尾。利用while循环保证j始终在k之前。判断三者之和是否等于0,并根据与0关系调整j,k位置。

        在其中加入防止重复取数的判断。

java小知识部分

题9

        有特殊情况的话先判断掉。

题13

        对于数组、链表都要判断是否越界的问题。

        +=,-=连起来才是一个运算符,中间不可以加空格。

题14

        数组长度是.length,字符串长度是.length()。

        字符串截断用:

nextstring = nextstring.substring(0,i);

题20

        栈的各种操作:

Stack<Character> stack = new Stack<Character>(); //栈的声明
stack.push(')'); //入栈
stack.isEmpty() //出栈
stack.pop() //判断栈空

题4

        if判断中先判断越界情况再判断其他情况。

题15

        数据类型List,意为List由List组成,内层List由int组成。

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

         加入新的数据的方法:

res.add(Arrays.asList(nums[0],nums[1],nums[2]));

        排序方法:

Arrays.sort(nums);

上一篇:【无标题】


下一篇:IIC实战---》BH1750FVI光照强度传感器