Li Kou 1480. Dynamic sum of one-dimensional array 383. Ransom letter 412. Fizz buzz

 1480. The dynamic sum of one-dimensional arrays  

subject ： Give you an array nums . Array 「 Dynamic and 」 The calculation formula of is ：runningSum[i] = sum(nums[0]…nums[i]) .

Please return nums Dynamic and .

Answer key ： If you don't want to destroy the source data , You can define a new array . Calculate the length of a one-dimensional array C++ Use in nums.size(); Java Use in nums.length;

C++ 

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for(int i=1;i<nums.size();i++){
            nums[i]=nums[i-1]+nums[i];
        }
        return nums;
    }
};

Java

class Solution {
    public int[] runningSum(int[] nums) {
        
        for(int i=1;i<nums.length;i++){
            nums[i]+=nums[i-1];
        }
        return nums;

    }
}

383. Ransom letter

Here are two strings ：ransomNote and magazine , Judge ransomNote Can it be done by magazine The characters inside make up .

If possible , return true ; Otherwise return to false .

magazine Each character in can only be in ransomNote Used once in .

  Answer key ： Count the number of occurrences of each character . Need to put string Type to char type

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
       
        //String[] arr1 = ransomNote.split(""); // Define separator , Array of strings 
        //String[] arr2 = magazine.split("");
        char[] arr1 = ransomNote.toCharArray(); // A character is an element , A character array 
        char[] arr2 = magazine.toCharArray();
        if(arr1.length>arr2.length){
            return false;
        }
        int[] alphabet=new int[26];
        for(int i=0;i<arr2.length;i++){
            alphabet[arr2[i]-'a']++; //'' character ,“” character string 

        } 
        for(int i=0;i<arr1.length;i++){
            if(--alphabet[arr1[i]-'a']<0){
                return false;
            }
        }  
        return true;

    }
}

Use for(:) Grammar format

for(variable : collection) statement

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        if(ransomNote.length() > magazine.length()) {
            return false;
        }

        int[] cnt = new int[26];

        for(char c : magazine.toCharArray()) {
            cnt[c - 'a'] ++;
        }
        for(char c : ransomNote.toCharArray()) {
            cnt[c - 'a'] --;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

412. Fizz Buzz

Give you an integer n , Find out from 1 To n Of each integer Fizz Buzz Express , And use string array answer（ Subscript from 1 Start ） Return results , among ：

answer[i] == "FizzBuzz" If i At the same time 3 and 5 Multiple .
answer[i] == "Fizz" If i yes 3 Multiple .
answer[i] == "Buzz" If i yes 5 Multiple .
answer[i] == i （ In string form ） If none of the above conditions are met .

Answer key ：C++ of use to_string() Convert a number to a string

Java Middle number 、 String conversion

//  Number to string  method1
		int number = 5;
		String str = String.valueOf(number);
		System.out.println(str);

//  Number to string  method2
		int number = 5;
		Integer itr = number;  //int Box as object , Call the object's toString Method 
		String str = itr.toString(); // Or directly  String str = Integer.toString(number);
		System.out.println(str);

//  Number to string  method3
		int number = 5;
		String str = number + "";
		System.out.println(str);

//  String to number 
		String str = "123";
		int number = Integer.parseInt(str);		
		System.out.println(number);

Java

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> answer=new ArrayList<String>(n);
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0){
                answer.add("FizzBuzz");
            }
            else if(i%3==0){
                answer.add("Fizz");
            }
            else if(i%5==0){
                answer.add("Buzz");
            }
            else{
                answer.add(i+"");
            }
        }
        return answer;
    }
}

C++

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> ans;
        for(int i=1;i<=n;i++){
            string s="";
            if(i%3==0) s+="Fizz";
            if(i%5==0) s+="Buzz";
            if(s.size()==0)s=to_string(i);
            ans.push_back(s);
        }
        return ans;
    }
};

876. The middle node of a list

Given a header node as  head  The non empty single chain table of , Returns the middle node of the linked list .

If there are two intermediate nodes , Then return to the second intermediate node .

Answer key ： Calculate the number of nodes in the linked list , Go to the intermediate node . Method 2 ： Fast and slow nodes , Go two at a time , Walk one slow node at a time .

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> v;
        while(head!=nullptr){
            v.push_back(head);
            head=head->next;
        }
        return v[v.size()/2];
    }
};

 Java

/**
 * 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 middleNode(ListNode head) {
        ListNode ans=head;
        int len=1;
        while(ans.next!=null){
            len++;
            ans=ans.next;
        }
        ans=head;
        System.out.println(len);
        for(int i=0;i<len/2;i++){
            ans=ans.next;  
        }
       
        return ans;
    }
}

C++ Use the speed pointer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=NULL&&fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

1342. Turn the number into 0 The number of operations

Give you a nonnegative integer  num , Please go back and turn it into 0 The number of steps required . If the current number is even , You need to divide it by 2 ; otherwise , subtract 1 .

Answer key ： Calculate directly according to the topic flow . According to the bit operation, the execution efficiency can be improved .

C++

class Solution {
public:
    int numberOfSteps(int num) {
        int temp=num;
        int step=0;
        while(temp!=0){
            if(temp%2==0) temp/=2;
            else temp--;
            step++;
        }
        return step;
    }
};

C++ Using bit operations

class Solution {
public:
    int numberOfSteps(int num) {
        int step=0;
        while(num>0){
            step+=(num&1)+1;//temp yes even,step+1;temp yes uneven,step+2
            num>>=1;//÷2 operation 
        }
        return max(step-1,0);
    }
};