字符串、数组:当我踏上算法之路,我发现...

2020.09.30 09:09:52
84
阅读约 7 分钟

img

字符串 #

括号生成(中等) #

题干:
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例:

输入:n = 3
输出:[
       "((()))",
       "(()())",
       "(())()",
       "()(())", 
       "()()()"
     ]

解法:对于这种题目,分析一波可以发现可以用回溯算法来解,首先我们需要知道边界条件,在这里,可以是左括号与右括号的数量,当他们与题目给出的n相等时,循环可以终止

 if(left==n && right==n){
         ....
         return;
        }

当左括号与右括号数量不满足给定数量时,我们可以向右侧增加(),相应的增加左右括号数量并进入下一层递归。

  if(n>left) dfs(n, result, s+"(",left+1,right);
  if(n>right) dfs(n, result, s+")",left,right+1);

最后,当右括号比左括号多时,我们需要舍弃该结果

if(right>left) return;

这种情况发生在,例如:当我们刚开始循环时,会在右侧分别加入(),然而,加入右括号的情况是无法满足一对闭合的括号这个条件的,因为括号始终会在右侧加入。

最终的解法

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result =  new ArrayList<>();
        dfs(n,result,"",0,0);
        return result;
    }

    private void dfs(int n, List<String> result, String s,int left,int right) {
        if(left==n && right==n){
         result.add(s);
         return;
        }

        if(right>left) return;
        
        if(n>left) dfs(n, result, s+"(",left+1,right);
        if(n>right) dfs(n, result, s+")",left,right+1);
    }
}

查找常用字符串 #

题干:
给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

例子1:

输入:["bella","label","roller"]
输出:["e","l","l"]

例子2:

输入:["cool","lock","cook"]
输出:["c","o"]

大佬的思路:根据题干,给定字符串仅有小写字母组成,因此可以维护一个minfreq来储存所有字母出现的最小次数,每次遍历完一个单词之后更新最小值即可。

大佬的解法:

class Solution {
    public List<String> commonChars(String[] A) {
        int[] minfreq = new int[26];
        Arrays.fill(minfreq, Integer.MAX_VALUE);
        for (String word: A) {
            int[] freq = new int[26];
            int length = word.length();
            for (int i = 0; i < length; ++i) {
                char ch = word.charAt(i);
                ++freq[ch - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                minfreq[i] = Math.min(minfreq[i], freq[i]);
            }
        }
(begin)
        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < minfreq[i]; ++j) {
                ans.add(String.valueOf((char) (i + 'a')));
            }
        }
     (/end)   
        return ans;
    }
}

要学习的写法:

int[] minfreq = new int[26];
Arrays.fill(minfreq, Integer.MAX_VALUE);
++freq[ch - 'a'];

比较含退格的字符串 #

题干:
给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

实例1:
输入:S = "ab#c", T = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。

实例2:
输入:S = "ab##", T = "c#d#"
输出:true
解释:S 和 T 都会变成 “”。

解法:对于像这种有进有出的题目,适合用栈来解决,也就是所谓的入栈和弹栈。
首先我们需要维护一个栈结构

Stack<Character> ans = new Stack();

当我们遇到普通字符串时,直接压入栈中,如果是#号,则pop掉元素

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String S) {
        Stack<Character> ans = new Stack();
        for (char c: S.toCharArray()) {
            if (c != '#')
                ans.push(c);
            else if (!ans.empty())
                ans.pop();
        }
        return String.valueOf(ans);
    }
}

最终比较两个字符串,可以看出

  • 时间复杂度:O(M + N),,其中 M,N 是字符串 S 和 T 的长度。
  • 空间复杂度:O(M + N)。

最长公共前缀 #

题干:

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

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

例子:

输入: ["flower","flow","flight"]
输出: "fl"

所有输入只包含小写字母 a-z 。

没啥好说的,直接暴力解法,虽然只能击败20%,但好写。

解法:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0) return "";
        String res= "";
        for (int i = 0; i <= strs[0].length(); i++) {
             String prefix = strs[0].substring(0, i);
            for (int j = 1; j < strs.length; j++) {
              
                if(!strs[j].startsWith(prefix)) return res;
            }
            res = prefix;
        }
        return res;
    }
}

基本计算器 #

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例1:

输入: "3+2*2"
输出: 7

示例2:

输入: " 3/2 "
输出: 1

示例3:

输入: " 3+5 / 2 "
输出: 5

思路:先从 加减法入手,逐步扩展到乘除,最后考虑递归运算括号内的式子。
解法:

class Solution {
    public int calculate(LinkedList<Character> s) {
        Stack<Integer> stk = new Stack<>();

        // 记录结果
        int num = 0;
        char sign='+';
        while (s.size()!=0){
            char c = s.pop();
            if(Character.isDigit(c)) num = 10*num + (c-'0');
            if(c=='(') num = calculate(s);

            // 如果不是数字,就是遇到了下一个字符, i==s.length() -1 比较关键
            if((!Character.isDigit(c) && c != ' ') || s.size()==0){
                int pre;
(begin)
                switch (sign){
                    case '+':
                        stk.push(num); break;
                    case '-':
                        stk.push(-num); break;
                    case '*':
                        pre = stk.pop();
                        stk.push(pre*num); break;
                    case '/':
                        pre = stk.pop();
                        stk.push(pre/num); break;
                }
(/end)
                // 更新符号,数字清零
                sign =c;
                num=0;
            }

            if(c==')') break;
        }

        // 将栈中所有结果求和
        int res =0 ;
        while (!stk.isEmpty()){
            res+=stk.pop();
        }
        return  res;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        LinkedList<Character> characters = new LinkedList<>();
        String s = "3+2*2";
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            characters.add(aChar);
        }

        int calculate = solution.calculate( characters);
        System.out.println(calculate);
    }

}

根据字符串出现频率排序 #

题干:
给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。

解法:

class Solution {
    public String frequencySort(String s) {
        int[] letters = new int[128];
        for (char c : s.toCharArray()) letters[c]++;
         // 构造一个大顶堆,用来放置较大的元素。
        PriorityQueue<Character> heap = new PriorityQueue<>(128, (a, b) -> Integer.compare(letters[b], letters[a]));
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < letters.length; ++i) {
            if (letters[i] != 0) {
                heap.offer((char)i);
            }
        }

        while (!heap.isEmpty()) {
            char c = heap.poll();
            while (letters[c]-- > 0) {
                res.append(c);
            }
        }
        return res.toString();
    }
}
 

字符串的相加问题 #

题干:
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

思路:构建一个stringbuffer用来拼接结果字符串,从尾部开始累加两个字符串值,逢10进1,循环结束后,若高位不为零,补1,最终将字符串反向即可得到和结果。
解法:

class Solution {
     public String addStrings(String a, String b) {
        
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(),b.length()), carry = 0;

        for (int i = 0; i < n; i++) {
            carry += i< a.length()? (a.charAt(a.length()-1-i)-'0'):0;
            carry += i< b.length()? (b.charAt(b.length()-1-i)-'0'):0;

            ans.append((char) carry%10);
            carry /=10;
        }

        if (carry > 0) {
            ans.append('1');
        }
        return   ans.reverse().toString();
    }
}

数组 #

魔术索引(简单) #

题干:
魔术索引。 在数组A[0…n-1]中,有所谓的魔术索引,满足条件A[i] = i。给定一个有序整数数组,编写一种方法找出魔术索引,若有的话,在数组A中找出一个魔术索引,如果没有,则返回-1。若有多个魔术索引,返回索引值最小的一个
例子:

 输入:nums = [0, 2, 3, 4, 5]
 输出:0
 说明: 0下标的元素为0

解法:

class Solution {
      public int findMagicIndex(int[] nums) {
        for (int i = 0; i < nums.length;) {
            if(nums[i]==i){
                return i;
            }
            // 跳跃
             // jump as long as we can
            i = Math.max(i + 1, nums[i]);
        }
        return -1;
    }
}

两数之和 #

题干:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

例子:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // 如果map中有值,取出相应的索引
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            // 将键值对放入map
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

最长上升子序列的长度 #

题干:
给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

方法一:动态规划

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 维护一个dp数组
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
    // 若当前数字比前面的数字大,比较当前maxval与储存的dp[j]的大小。
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

方法二:贪心+二分查找

public class Solution {

    public int lengthOfLIS (int[] arr) {
       if (arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length+1];
        int len = 1;
        dp[1]=arr[0];

        for(int i=1;i<arr.length;++i){
        // 若当前数字比前一个大,直接添加数字到尾部。
            if(arr[i]>dp[len]) dp[++len] = arr[i];
            else{
           // 否则的话,二分查找第一个存在于dp中小于当前数字的数字,并将它添加到dp[pos+1]
                    int l=1,r=len,pos=0;
                    while(l<=r){
                        int mid = (l+r)/2;
                        if(dp[mid]<arr[i]){
                            pos=mid;
                            l=mid+1;
                        }
                        else r=mid-1;
                    }
                        dp[pos+1]= arr[i];
            }
        }
        return len;
    }
}

最长连续递增序列 #

题干:
给定一个未经排序的整数数组,找到最长且连续的的递增序列,并返回该序列的长度。

实例1:

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为5和7在原数组里被4隔开。 。

解答:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return 1;
        int[] dp = new int[nums.length];
        int maxans = 0;
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]>nums[i-1])  dp[i]=dp[i-1]+1;
            else dp[i]=1;
            maxans=Math.max(maxans,dp[i]);
        }
        return maxans;
    }
}
阅读:84 . 字数:1869 发布于 2 个月前
Copyright 2018-2020 Siques