刷题记录帖

I am a fresh new coding learner and I just started to learn to code from this January.
Where  am I now?
I didn't have any coding experience in my previous study and work. I studied some online coures about Java and Algrithm. Now I have finished 66 LeetCode problems.
I finished most of problems with tag ListNode and know most trick and basic operation of it.

I plan to work on a specific type of problems each week. During this week, I plan to finish most frequent problems and problems with high evaluation.

394. Decode String
done

Find the bug of the following code
class Solution {
    public String decodeString(String s) {
        StringBuilder ans = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        Character[] ch = s.toCharArray();        for(int i=0; i<ch.length; i++){
            Character c = ch;
            if(Character.isDigit(c)||c=='['||Character.isLetter(c)){
                stack.push(c);
            }else{
                StringBuilder helper = new StringBuilder();
                while(stack.peek()!='['){
                    helper.append(stack.pop());
                }
                stack.pop();
                StringBuilder helper1= new StringBuilder();
                StringBuilder num = new StringBuilder();
                while(!stack.isEmpty()&&Character.isDigit(stack.peek())){   
                    num.append(stack.pop());
                }
                 int tag =Integer.parseInt(num.reverse().toString());
                while(tag!=0){
                    helper1.append(helper.toString());
                    tag--;
                }
                String decode = helper1.toString();
                Char[] ch1= decode.toCharArray();
                for(int j=ch1.length-1; j>=0;j--){
                    stack.push(ch1[j]);
                }
            }
        }
        while(!stack.isEmpty()){
            ans.append(Stack.pop());
        }
        return ans.reverse().toString();
    }
}
Study another method.
And compare the idea.
Summary for string and character.
150. Evaluate Reverse Polish Notation

739. Daily Temperatures
Arrays.fill(next, Integer.MAX_VALUE);
This method assigns the specified data type value to each element of the specified range of the specified array.

Syntax:
// Makes all elements of a[] equal to "val"
public static void fill(int[] a, int val)

// Makes elements from from_Index (inclusive) to to_Index
// (exclusive) equal to "val"
public static void fill(int[] a, int from_Index, int to_Index, int val)

This method doesn't return any value.
Approach #1: Next Array [Accepted]
Approach #2: Stack [Accepted]

496. Next Greater Element I
find the bug of following code:
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i= nums2.length()-1; i>=0;i--){
            while(!stack.isEmpty() && nums2>stack.peek() ){
                stack.pop();
            }
            int find=stack.isEmpty? -1:stack.peek();
            map.push(nums2[i],find);
            stack.push(nums2[i]);
        }
        for(int k=0; k<nums1.length(); k++){
            int temp = nums1[k];
            nums1[k]=map.get(temp);
        }
        return nums1;
    }
}

503. Next Greater Element II
array.length : length is a final variable applicable for arrays. With the help of length variable, we can obtain the size of the array.
string.length() : length() method is a final variable which is applicable for string objects. length() method returns the number of characters presents in the string.

735. Asteroid Collision
good idea~simulation
605. Can Place Flowers
think about it[/i][/i]

286. Walls and Gates
write down another idea.
learn to write with directions.
study why there is out of bound error.
200. Number of Islands
learn to write using directions.
study why there is out of bound error.
752. Open the Lock
int y = ((node.charAt(i) - '0') + d + 10) % 10;
                        String nei = node.substring(0, i) + ("" + y)(why) + node.substring(i+1);

public static int openLock(String[] deadends, String target) {
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));

List addAll() Method in Java with Examples
q.addAll(getSuccessors(node));
private static List<String> getSuccessors(String str) {
        List<String> res = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            res.add(str.substring(0, i) + (str.charAt(i) == '0' ? 9 :  str.charAt(i) - '0' - 1) + str.substring(i+1));
            res.add(str.substring(0, i) + (str.charAt(i) == '9' ? 0 :  str.charAt(i) - '0' + 1) + str.substring(i+1));
        }
        return res;
    }
Syntax:

boolean addAll(Collection c)
Parameters: This function has a single parameter, i.e, Collection c, whose elements are to be appended to the list.

practice tmr
https://leetcode.com/problems/op ... 2B-how-to-avoid-TLE

127. Word Ladder
Good!
https://leetcode.com/problems/wo ... pted-Java-solution-(BFS)


279. Perfect Squares
study tmr

268. Missing Number
Finish the XOR method.
Q: why n definitely in the array, there will be chance that n is missing.
learn the idea of Gauss' Formula.
The basic idea is to find the difference. ways to find difference is to compare by substrating.

189. Rotate Array
in this problem, there is a good way to find the relation between new index and old index if use the method which need to use extra array.
ans[(i+k)%n]=nums[i];
Another way: Using Cyclic Replacements

And use reverse.


35. Search Insert Position
you can use binary search but i use iterative.
Time complexity O(logn) is better than O(n)?


33. Search in Rotated Sorted Array
binary search.
i will check tmr.

56. Merge Intervals
related questions. Meeting room. I need to check how i solved those questions.
not finish yet.

16. 3Sum Closest
https://leetcode.com/problems/3s ... ava-solution-with-O(n2)-for-reference
https://leetcode.com/problems/3s ... -24-line-Java-code-(beats-94.57-run-times)
https://leetcode.com/problems/3s ... solution-in-Chinese
再这里我知道了算法优化这种概念。
没有完成

137. Single Number II

use hashset：
class Solution {
  public int singleNumber(int[] nums) {
    Set<Long> set = new HashSet<>();
    long sumSet = 0, sumArray = 0;
    for(int n : nums) {
      sumArray += n;
      set.add((long)n);
    }
    for(Long s : set) sumSet += s;
    return (int)((3 * sumSet - sumArray) / 2);
  }
}

Question
Set<Long> set = new HashSet<>();
HashSet <Long> set = new HashSet<>();
区别是什么？
why the number type is long in set?
没弄明白为什么那个case不过？

Good example to learn implementation of hash map and hash set.
use hashmap to count frequency and record it. good to learn.

Good example to learn bitwise operator.
not fully understand yet 9/11
Similar to 268. Missing Number


34. Find First and Last Position of Element in Sorted Array

Finish linear scan
Binary search not finish. 9/11/2019


39. Combination Sum
18. 4Sum
16. 3Sum Closest

169. Majority Element
use hashmap to count numbers.allows us to count element occurrences efficiently
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
这一行理解一下

169. Majority Element
Approach 4 之后没有看

217. Contains Duplicate
Take away:
O(n)
O(nlgn) is faster

61. Rotate List
finish another way of doing it. use two poiter.
the main point is how to deal with situation when k is larger than size of listnode.

189. Rotate Array
Approach #3 Using Cyclic Replacements
observe property of array. move the number by k index.

16. 3Sum Closest
finished it today.

33. Search in Rotated Sorted Array
Finished one pass solution

137. Single Number II
still dont understand the bit manipulation

34. Find First and Last Position of Element in Sorted Array
Binary Search not understand it
219. Contains Duplicate II
not finish

238. Product of Array Except Self
finish

219. Contains Duplicate II
Approach #1 (Naive Linear Search)
A proach that use sliding window.

Another two approach not study yet

566. Reshape the Matrix
I initially want to use two pointers,
正确的思想却没有坚持

I found a mistake:

// Queue<Integer> helper = new Queue<Integer>();
        Queue<Integer> helper = new LinkedList<Integer>();

Also remember this:
array_name[row_index][column_index] = value;

Approach #3 Using division and modulus
not liaojie yet


977. Squares of a Sorted Array
I finished the sorted way.

two pointer has error, debug tomorrow

259. 3Sum Smaller

try but not solved.

153. Find Minimum in Rotated Sorted Array
solve in linear scan
binary search not finish, there is problem.

星期六休假一天

studied following questions:
Meeting Rooms
Meeting Rooms II
56. Merge Intervals: not finish yet.

But there something I need to remember:
comparator.
Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0]!=b[0]) return Integer.compare(a[0], b[0]);
                else return Integer.compare(a[1], b[1]);
            }            
        });

Also difference about linkedlist and arraylist:
https://www.geeksforgeeks.org/array-of-arraylist-in-java/
https://www.geeksforgeeks.org/arraylist-of-arraylist-in-java/
technique to deal with different size of array.:
https://www.geeksforgeeks.org/jagged-array-in-java/
Array-related Techniques
https://leetcode.com/explore/lea ... 04/conclusion/1155/

13. Roman to Integer

use HashMap.
use Switch. tmr practice !
937. Reorder Data in Log Files
String basic operation

split/isDigit/compareTo

387. First Unique Character in a String
get frequency of each charater.
use hashmap.

the technique of usins two pointers are not done yet
have a look what is more efficient?

125. Valid Palindrome
learn the method: isLetterOrDigit().
not finish yet.

s=s.toLowerCase().replaceAll("[^a-z0-9]", "");
a technique to replace

415. Add Strings
toCharArray()
int a = i >= 0 ? (num1Array[i--] - '0') : 0;
StringBuilder sb = new StringBuilder();

compare reading: ListNode, array
not finish yet

58. Length of Last Word
there is bug

13. Roman to Integer

finish switch method.
387. First Unique Character in a String
freq[s.charAt(i)-'a']++;